]>
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 | |
19 | the Free Software Foundation, 59 Temple Place - Suite 330, | |
20 | Boston, MA 02111-1307, USA. */ | |
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 DN |
42 | #include "tree-pass.h" |
43 | #include "convert.h" | |
44 | #include "params.h" | |
45 | ||
46 | ||
47 | /* Structure to map a variable to its alias set and keep track of the | |
48 | virtual operands that will be needed to represent it. */ | |
49 | struct alias_map_d | |
50 | { | |
51 | /* Variable and its alias set. */ | |
52 | tree var; | |
53 | HOST_WIDE_INT set; | |
54 | ||
55 | /* Total number of virtual operands that will be needed to represent | |
56 | all the aliases of VAR. */ | |
57 | long total_alias_vops; | |
58 | ||
59 | /* Nonzero if the aliases for this memory tag have been grouped | |
60 | already. Used in group_aliases. */ | |
61 | unsigned int grouped_p : 1; | |
62 | ||
63 | /* Set of variables aliased with VAR. This is the exact same | |
64 | information contained in VAR_ANN (VAR)->MAY_ALIASES, but in | |
65 | bitmap form to speed up alias grouping. */ | |
66 | sbitmap may_aliases; | |
67 | }; | |
68 | ||
69 | ||
70 | /* Alias information used by compute_may_aliases and its helpers. */ | |
71 | struct alias_info | |
72 | { | |
73 | /* SSA names visited while collecting points-to information. If bit I | |
74 | is set, it means that SSA variable with version I has already been | |
75 | visited. */ | |
d0ce8e4c | 76 | sbitmap ssa_names_visited; |
6de9cd9a DN |
77 | |
78 | /* Array of SSA_NAME pointers processed by the points-to collector. */ | |
79 | varray_type processed_ptrs; | |
80 | ||
81 | /* Variables whose address is still needed. */ | |
82 | bitmap addresses_needed; | |
83 | ||
84 | /* ADDRESSABLE_VARS contains all the global variables and locals that | |
85 | have had their address taken. */ | |
86 | struct alias_map_d **addressable_vars; | |
87 | size_t num_addressable_vars; | |
88 | ||
89 | /* POINTERS contains all the _DECL pointers with unique memory tags | |
90 | that have been referenced in the program. */ | |
91 | struct alias_map_d **pointers; | |
92 | size_t num_pointers; | |
93 | ||
94 | /* Number of function calls found in the program. */ | |
95 | size_t num_calls_found; | |
96 | ||
97 | /* Array of counters to keep track of how many times each pointer has | |
98 | been dereferenced in the program. This is used by the alias grouping | |
99 | heuristic in compute_flow_insensitive_aliasing. */ | |
100 | varray_type num_references; | |
101 | ||
102 | /* Total number of virtual operands that will be needed to represent | |
103 | all the aliases of all the pointers found in the program. */ | |
104 | long total_alias_vops; | |
105 | ||
106 | /* Variables that have been written to. */ | |
107 | bitmap written_vars; | |
108 | ||
109 | /* Pointers that have been used in an indirect store operation. */ | |
110 | bitmap dereferenced_ptrs_store; | |
111 | ||
112 | /* Pointers that have been used in an indirect load operation. */ | |
113 | bitmap dereferenced_ptrs_load; | |
114 | }; | |
115 | ||
116 | ||
117 | /* Counters used to display statistics on alias analysis. */ | |
118 | struct alias_stats_d | |
119 | { | |
120 | unsigned int alias_queries; | |
121 | unsigned int alias_mayalias; | |
122 | unsigned int alias_noalias; | |
123 | unsigned int simple_queries; | |
124 | unsigned int simple_resolved; | |
125 | unsigned int tbaa_queries; | |
126 | unsigned int tbaa_resolved; | |
6de9cd9a DN |
127 | }; |
128 | ||
129 | ||
130 | /* Local variables. */ | |
131 | static struct alias_stats_d alias_stats; | |
132 | ||
133 | /* Local functions. */ | |
134 | static void compute_flow_insensitive_aliasing (struct alias_info *); | |
135 | static void dump_alias_stats (FILE *); | |
136 | static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT); | |
137 | static tree create_memory_tag (tree type, bool is_type_tag); | |
138 | static tree get_tmt_for (tree, struct alias_info *); | |
139 | static tree get_nmt_for (tree); | |
140 | static void add_may_alias (tree, tree); | |
53b4bf74 | 141 | static void replace_may_alias (tree, size_t, tree); |
6de9cd9a DN |
142 | static struct alias_info *init_alias_info (void); |
143 | static void delete_alias_info (struct alias_info *); | |
144 | static void compute_points_to_and_addr_escape (struct alias_info *); | |
145 | static void compute_flow_sensitive_aliasing (struct alias_info *); | |
146 | static void setup_pointers_and_addressables (struct alias_info *); | |
147 | static bool collect_points_to_info_r (tree, tree, void *); | |
148 | static bool is_escape_site (tree, size_t *); | |
149 | static void add_pointed_to_var (struct alias_info *, tree, tree); | |
6de9cd9a DN |
150 | static void create_global_var (void); |
151 | static void collect_points_to_info_for (struct alias_info *, tree); | |
152 | static bool ptr_is_dereferenced_by (tree, tree, bool *); | |
153 | static void maybe_create_global_var (struct alias_info *ai); | |
154 | static void group_aliases (struct alias_info *); | |
9ae2a5d1 DN |
155 | static void set_pt_anything (tree ptr); |
156 | static void set_pt_malloc (tree ptr); | |
6de9cd9a DN |
157 | |
158 | /* Global declarations. */ | |
159 | ||
160 | /* Call clobbered variables in the function. If bit I is set, then | |
161 | REFERENCED_VARS (I) is call-clobbered. */ | |
162 | bitmap call_clobbered_vars; | |
163 | ||
a6d02559 | 164 | /* Addressable variables in the function. If bit I is set, then |
ee536902 DN |
165 | REFERENCED_VARS (I) has had its address taken. Note that |
166 | CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related. An | |
167 | addressable variable is not necessarily call-clobbered (e.g., a | |
168 | local addressable whose address does not escape) and not all | |
169 | call-clobbered variables are addressable (e.g., a local static | |
170 | variable). */ | |
a6d02559 DN |
171 | bitmap addressable_vars; |
172 | ||
6de9cd9a DN |
173 | /* When the program has too many call-clobbered variables and call-sites, |
174 | this variable is used to represent the clobbering effects of function | |
175 | calls. In these cases, all the call clobbered variables in the program | |
176 | are forced to alias this variable. This reduces compile times by not | |
a32b97a2 | 177 | having to keep track of too many V_MAY_DEF expressions at call sites. */ |
6de9cd9a DN |
178 | tree global_var; |
179 | ||
180 | ||
181 | /* Compute may-alias information for every variable referenced in function | |
182 | FNDECL. | |
183 | ||
184 | Alias analysis proceeds in 3 main phases: | |
185 | ||
186 | 1- Points-to and escape analysis. | |
187 | ||
188 | This phase walks the use-def chains in the SSA web looking for three | |
189 | things: | |
190 | ||
191 | * Assignments of the form P_i = &VAR | |
192 | * Assignments of the form P_i = malloc() | |
193 | * Pointers and ADDR_EXPR that escape the current function. | |
194 | ||
195 | The concept of 'escaping' is the same one used in the Java world. When | |
196 | a pointer or an ADDR_EXPR escapes, it means that it has been exposed | |
197 | outside of the current function. So, assignment to global variables, | |
406eab99 RK |
198 | function arguments and returning a pointer are all escape sites, as are |
199 | conversions between pointers and integers. | |
6de9cd9a DN |
200 | |
201 | This is where we are currently limited. Since not everything is renamed | |
202 | into SSA, we lose track of escape properties when a pointer is stashed | |
203 | inside a field in a structure, for instance. In those cases, we are | |
204 | assuming that the pointer does escape. | |
205 | ||
206 | We use escape analysis to determine whether a variable is | |
207 | call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable | |
208 | is call-clobbered. If a pointer P_i escapes, then all the variables | |
209 | pointed-to by P_i (and its memory tag) also escape. | |
210 | ||
211 | 2- Compute flow-sensitive aliases | |
212 | ||
213 | We have two classes of memory tags. Memory tags associated with the | |
214 | pointed-to data type of the pointers in the program. These tags are | |
215 | called "type memory tag" (TMT). The other class are those associated | |
216 | with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that | |
217 | when adding operands for an INDIRECT_REF *P_i, we will first check | |
218 | whether P_i has a name tag, if it does we use it, because that will have | |
219 | more precise aliasing information. Otherwise, we use the standard type | |
220 | tag. | |
221 | ||
222 | In this phase, we go through all the pointers we found in points-to | |
223 | analysis and create alias sets for the name memory tags associated with | |
224 | each pointer P_i. If P_i escapes, we mark call-clobbered the variables | |
225 | it points to and its tag. | |
226 | ||
227 | ||
228 | 3- Compute flow-insensitive aliases | |
229 | ||
230 | This pass will compare the alias set of every type memory tag and every | |
231 | addressable variable found in the program. Given a type memory tag TMT | |
232 | and an addressable variable V. If the alias sets of TMT and V conflict | |
233 | (as computed by may_alias_p), then V is marked as an alias tag and added | |
234 | to the alias set of TMT. | |
235 | ||
236 | For instance, consider the following function: | |
237 | ||
238 | foo (int i) | |
239 | { | |
4244df06 | 240 | int *p, a, b; |
6de9cd9a DN |
241 | |
242 | if (i > 10) | |
243 | p = &a; | |
244 | else | |
4244df06 | 245 | p = &b; |
6de9cd9a DN |
246 | |
247 | *p = 3; | |
6de9cd9a DN |
248 | a = b + 2; |
249 | return *p; | |
250 | } | |
251 | ||
252 | After aliasing analysis has finished, the type memory tag for pointer | |
253 | 'p' will have two aliases, namely variables 'a' and 'b'. Every time | |
254 | pointer 'p' is dereferenced, we want to mark the operation as a | |
255 | potential reference to 'a' and 'b'. | |
256 | ||
257 | foo (int i) | |
258 | { | |
259 | int *p, a, b; | |
260 | ||
261 | if (i_2 > 10) | |
262 | p_4 = &a; | |
263 | else | |
264 | p_6 = &b; | |
265 | # p_1 = PHI <p_4(1), p_6(2)>; | |
266 | ||
a32b97a2 BB |
267 | # a_7 = V_MAY_DEF <a_3>; |
268 | # b_8 = V_MAY_DEF <b_5>; | |
6de9cd9a DN |
269 | *p_1 = 3; |
270 | ||
a32b97a2 | 271 | # a_9 = V_MAY_DEF <a_7> |
6de9cd9a DN |
272 | # VUSE <b_8> |
273 | a_9 = b_8 + 2; | |
274 | ||
275 | # VUSE <a_9>; | |
276 | # VUSE <b_8>; | |
277 | return *p_1; | |
278 | } | |
279 | ||
280 | In certain cases, the list of may aliases for a pointer may grow too | |
281 | large. This may cause an explosion in the number of virtual operands | |
282 | inserted in the code. Resulting in increased memory consumption and | |
283 | compilation time. | |
284 | ||
285 | When the number of virtual operands needed to represent aliased | |
286 | loads and stores grows too large (configurable with @option{--param | |
287 | max-aliased-vops}), alias sets are grouped to avoid severe | |
288 | compile-time slow downs and memory consumption. See group_aliases. */ | |
289 | ||
290 | static void | |
291 | compute_may_aliases (void) | |
292 | { | |
293 | struct alias_info *ai; | |
294 | ||
295 | memset (&alias_stats, 0, sizeof (alias_stats)); | |
296 | ||
297 | /* Initialize aliasing information. */ | |
298 | ai = init_alias_info (); | |
299 | ||
300 | /* For each pointer P_i, determine the sets of variables that P_i may | |
301 | point-to. For every addressable variable V, determine whether the | |
302 | address of V escapes the current function, making V call-clobbered | |
303 | (i.e., whether &V is stored in a global variable or if its passed as a | |
304 | function call argument). */ | |
305 | compute_points_to_and_addr_escape (ai); | |
306 | ||
307 | /* Collect all pointers and addressable variables, compute alias sets, | |
308 | create memory tags for pointers and promote variables whose address is | |
309 | not needed anymore. */ | |
310 | setup_pointers_and_addressables (ai); | |
311 | ||
312 | /* Compute flow-sensitive, points-to based aliasing for all the name | |
313 | memory tags. Note that this pass needs to be done before flow | |
314 | insensitive analysis because it uses the points-to information | |
315 | gathered before to mark call-clobbered type tags. */ | |
316 | compute_flow_sensitive_aliasing (ai); | |
317 | ||
318 | /* Compute type-based flow-insensitive aliasing for all the type | |
319 | memory tags. */ | |
320 | compute_flow_insensitive_aliasing (ai); | |
321 | ||
322 | /* If the program has too many call-clobbered variables and/or function | |
323 | calls, create .GLOBAL_VAR and use it to model call-clobbering | |
324 | semantics at call sites. This reduces the number of virtual operands | |
325 | considerably, improving compile times at the expense of lost | |
326 | aliasing precision. */ | |
327 | maybe_create_global_var (ai); | |
328 | ||
329 | /* Debugging dumps. */ | |
330 | if (dump_file) | |
331 | { | |
332 | dump_referenced_vars (dump_file); | |
333 | if (dump_flags & TDF_STATS) | |
334 | dump_alias_stats (dump_file); | |
335 | dump_points_to_info (dump_file); | |
336 | dump_alias_info (dump_file); | |
337 | } | |
338 | ||
339 | /* Deallocate memory used by aliasing data structures. */ | |
340 | delete_alias_info (ai); | |
6de9cd9a DN |
341 | } |
342 | ||
343 | struct tree_opt_pass pass_may_alias = | |
344 | { | |
345 | "alias", /* name */ | |
346 | NULL, /* gate */ | |
347 | compute_may_aliases, /* execute */ | |
348 | NULL, /* sub */ | |
349 | NULL, /* next */ | |
350 | 0, /* static_pass_number */ | |
351 | TV_TREE_MAY_ALIAS, /* tv_id */ | |
0a050485 | 352 | PROP_cfg | PROP_ssa, /* properties_required */ |
c1b763fa | 353 | PROP_alias, /* properties_provided */ |
6de9cd9a DN |
354 | 0, /* properties_destroyed */ |
355 | 0, /* todo_flags_start */ | |
356 | TODO_dump_func | TODO_rename_vars | |
7f9e6d2a AP |
357 | | TODO_ggc_collect | TODO_verify_ssa |
358 | | TODO_verify_stmts, /* todo_flags_finish */ | |
9f8628ba | 359 | 0 /* letter */ |
6de9cd9a DN |
360 | }; |
361 | ||
856e49c2 JL |
362 | /* Count the number of calls in the function and conditionally |
363 | create GLOBAL_VAR. This is performed before translation | |
364 | into SSA (and thus before alias analysis) to avoid compile time | |
365 | and memory utilization explosions in functions with many | |
366 | of calls and call clobbered variables. */ | |
367 | ||
368 | static void | |
369 | count_calls_and_maybe_create_global_var (void) | |
370 | { | |
371 | struct alias_info ai; | |
372 | basic_block bb; | |
373 | bool temp; | |
374 | ||
375 | memset (&ai, 0, sizeof (struct alias_info)); | |
376 | ||
377 | /* First count the number of calls in the IL. */ | |
378 | FOR_EACH_BB (bb) | |
379 | { | |
380 | block_stmt_iterator si; | |
381 | ||
382 | for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) | |
383 | { | |
384 | tree stmt = bsi_stmt (si); | |
385 | ||
386 | if (get_call_expr_in (stmt) != NULL_TREE) | |
387 | ai.num_calls_found++; | |
388 | } | |
389 | } | |
390 | ||
391 | /* If there are no call clobbered variables, then maybe_create_global_var | |
392 | will always create a GLOBAL_VAR. At this point we do not want that | |
393 | behavior. So we turn on one bit in CALL_CLOBBERED_VARs, call | |
394 | maybe_create_global_var, then reset the bit to its original state. */ | |
395 | temp = bitmap_bit_p (call_clobbered_vars, 0); | |
396 | bitmap_set_bit (call_clobbered_vars, 0); | |
397 | maybe_create_global_var (&ai); | |
398 | if (!temp) | |
399 | bitmap_clear_bit (call_clobbered_vars, 0); | |
400 | } | |
401 | ||
402 | struct tree_opt_pass pass_maybe_create_global_var = | |
403 | { | |
404 | "maybe_create_global_var", /* name */ | |
405 | NULL, /* gate */ | |
406 | count_calls_and_maybe_create_global_var, /* execute */ | |
407 | NULL, /* sub */ | |
408 | NULL, /* next */ | |
409 | 0, /* static_pass_number */ | |
410 | TV_TREE_MAY_ALIAS, /* tv_id */ | |
411 | PROP_cfg, /* properties_required */ | |
412 | 0, /* properties_provided */ | |
413 | 0, /* properties_destroyed */ | |
414 | 0, /* todo_flags_start */ | |
415 | 0, /* todo_flags_finish */ | |
416 | 0 /* letter */ | |
417 | }; | |
6de9cd9a DN |
418 | |
419 | /* Initialize the data structures used for alias analysis. */ | |
420 | ||
421 | static struct alias_info * | |
422 | init_alias_info (void) | |
423 | { | |
424 | struct alias_info *ai; | |
c1b763fa | 425 | static bool aliases_computed_p = false; |
6de9cd9a DN |
426 | |
427 | ai = xcalloc (1, sizeof (struct alias_info)); | |
d0ce8e4c SB |
428 | ai->ssa_names_visited = sbitmap_alloc (num_ssa_names); |
429 | sbitmap_zero (ai->ssa_names_visited); | |
6de9cd9a DN |
430 | VARRAY_TREE_INIT (ai->processed_ptrs, 50, "processed_ptrs"); |
431 | ai->addresses_needed = BITMAP_XMALLOC (); | |
432 | VARRAY_UINT_INIT (ai->num_references, num_referenced_vars, "num_references"); | |
433 | ai->written_vars = BITMAP_XMALLOC (); | |
434 | ai->dereferenced_ptrs_store = BITMAP_XMALLOC (); | |
435 | ai->dereferenced_ptrs_load = BITMAP_XMALLOC (); | |
436 | ||
53b4bf74 DN |
437 | /* If aliases have been computed before, clear existing information. */ |
438 | if (aliases_computed_p) | |
439 | { | |
3cd8c58a | 440 | unsigned i; |
a912a223 AP |
441 | basic_block bb; |
442 | ||
443 | /* Make sure that every statement has a valid set of operands. | |
444 | If a statement needs to be scanned for operands while we | |
445 | compute aliases, it may get erroneous operands because all | |
446 | the alias relations are not built at that point. | |
447 | FIXME: This code will become obsolete when operands are not | |
448 | lazily updated. */ | |
449 | FOR_EACH_BB (bb) | |
450 | { | |
451 | block_stmt_iterator si; | |
452 | for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) | |
453 | get_stmt_operands (bsi_stmt (si)); | |
454 | } | |
53b4bf74 | 455 | |
53b4bf74 DN |
456 | /* Similarly, clear the set of addressable variables. In this |
457 | case, we can just clear the set because addressability is | |
458 | only computed here. */ | |
459 | bitmap_clear (addressable_vars); | |
460 | ||
461 | /* Clear flow-insensitive alias information from each symbol. */ | |
462 | for (i = 0; i < num_referenced_vars; i++) | |
463 | { | |
90e34bd6 DN |
464 | tree var = referenced_var (i); |
465 | var_ann_t ann = var_ann (var); | |
466 | ||
53b4bf74 | 467 | ann->is_alias_tag = 0; |
c1b763fa | 468 | ann->may_aliases = NULL; |
90e34bd6 DN |
469 | |
470 | /* Since we are about to re-discover call-clobbered | |
471 | variables, clear the call-clobbered flag. Variables that | |
472 | are intrinsically call-clobbered (globals, local statics, | |
473 | etc) will not be marked by the aliasing code, so we can't | |
474 | remove them from CALL_CLOBBERED_VARS. */ | |
475 | if (ann->mem_tag_kind != NOT_A_TAG || !is_global_var (var)) | |
476 | clear_call_clobbered (var); | |
53b4bf74 DN |
477 | } |
478 | ||
479 | /* Clear flow-sensitive points-to information from each SSA name. */ | |
480 | for (i = 1; i < num_ssa_names; i++) | |
481 | { | |
482 | tree name = ssa_name (i); | |
483 | ||
8b547e44 | 484 | if (!name || !POINTER_TYPE_P (TREE_TYPE (name))) |
53b4bf74 DN |
485 | continue; |
486 | ||
487 | if (SSA_NAME_PTR_INFO (name)) | |
488 | { | |
489 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); | |
490 | ||
491 | /* Clear all the flags but keep the name tag to | |
492 | avoid creating new temporaries unnecessarily. If | |
493 | this pointer is found to point to a subset or | |
494 | superset of its former points-to set, then a new | |
495 | tag will need to be created in create_name_tags. */ | |
496 | pi->pt_anything = 0; | |
497 | pi->pt_malloc = 0; | |
498 | pi->value_escapes_p = 0; | |
499 | pi->is_dereferenced = 0; | |
500 | if (pi->pt_vars) | |
501 | bitmap_clear (pi->pt_vars); | |
53b4bf74 DN |
502 | } |
503 | } | |
504 | } | |
505 | ||
c1b763fa DN |
506 | /* Next time, we will need to reset alias information. */ |
507 | aliases_computed_p = true; | |
508 | ||
6de9cd9a DN |
509 | return ai; |
510 | } | |
511 | ||
512 | ||
513 | /* Deallocate memory used by alias analysis. */ | |
514 | ||
515 | static void | |
516 | delete_alias_info (struct alias_info *ai) | |
517 | { | |
518 | size_t i; | |
519 | ||
d0ce8e4c | 520 | sbitmap_free (ai->ssa_names_visited); |
6de9cd9a | 521 | ai->processed_ptrs = NULL; |
d1f9044b | 522 | BITMAP_XFREE (ai->addresses_needed); |
6de9cd9a DN |
523 | |
524 | for (i = 0; i < ai->num_addressable_vars; i++) | |
525 | { | |
526 | sbitmap_free (ai->addressable_vars[i]->may_aliases); | |
527 | free (ai->addressable_vars[i]); | |
528 | } | |
529 | free (ai->addressable_vars); | |
530 | ||
531 | for (i = 0; i < ai->num_pointers; i++) | |
532 | { | |
533 | sbitmap_free (ai->pointers[i]->may_aliases); | |
534 | free (ai->pointers[i]); | |
535 | } | |
536 | free (ai->pointers); | |
537 | ||
538 | ai->num_references = NULL; | |
d1f9044b AP |
539 | BITMAP_XFREE (ai->written_vars); |
540 | BITMAP_XFREE (ai->dereferenced_ptrs_store); | |
541 | BITMAP_XFREE (ai->dereferenced_ptrs_load); | |
6de9cd9a DN |
542 | |
543 | free (ai); | |
544 | } | |
545 | ||
546 | ||
547 | /* Walk use-def chains for pointer PTR to determine what variables is PTR | |
548 | pointing to. */ | |
549 | ||
550 | static void | |
551 | collect_points_to_info_for (struct alias_info *ai, tree ptr) | |
552 | { | |
1e128c5f | 553 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr))); |
6de9cd9a | 554 | |
d0ce8e4c | 555 | if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr))) |
6de9cd9a | 556 | { |
d0ce8e4c | 557 | SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)); |
53b4bf74 | 558 | walk_use_def_chains (ptr, collect_points_to_info_r, ai, true); |
6de9cd9a | 559 | VARRAY_PUSH_TREE (ai->processed_ptrs, ptr); |
6de9cd9a DN |
560 | } |
561 | } | |
562 | ||
563 | ||
564 | /* Helper for ptr_is_dereferenced_by. Called by walk_tree to look for | |
7ccf35ed | 565 | (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */ |
6de9cd9a DN |
566 | |
567 | static tree | |
568 | find_ptr_dereference (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data) | |
569 | { | |
570 | tree ptr = (tree) data; | |
571 | ||
1b096a0a | 572 | if (INDIRECT_REF_P (*tp) |
6de9cd9a DN |
573 | && TREE_OPERAND (*tp, 0) == ptr) |
574 | return *tp; | |
575 | ||
576 | return NULL_TREE; | |
577 | } | |
578 | ||
579 | ||
7ccf35ed DN |
580 | /* Return true if STMT contains (ALIGN/MISALIGNED_)INDIRECT_REF <PTR>. |
581 | *IS_STORE is set to 'true' if the dereference is on the LHS of an | |
582 | assignment. */ | |
6de9cd9a DN |
583 | |
584 | static bool | |
585 | ptr_is_dereferenced_by (tree ptr, tree stmt, bool *is_store) | |
586 | { | |
587 | *is_store = false; | |
588 | ||
589 | if (TREE_CODE (stmt) == MODIFY_EXPR | |
590 | || (TREE_CODE (stmt) == RETURN_EXPR | |
591 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)) | |
592 | { | |
593 | tree e, lhs, rhs; | |
594 | ||
595 | e = (TREE_CODE (stmt) == RETURN_EXPR) ? TREE_OPERAND (stmt, 0) : stmt; | |
596 | lhs = TREE_OPERAND (e, 0); | |
597 | rhs = TREE_OPERAND (e, 1); | |
598 | ||
599 | if (EXPR_P (lhs) | |
600 | && walk_tree (&lhs, find_ptr_dereference, ptr, NULL)) | |
601 | { | |
602 | *is_store = true; | |
603 | return true; | |
604 | } | |
605 | else if (EXPR_P (rhs) | |
606 | && walk_tree (&rhs, find_ptr_dereference, ptr, NULL)) | |
607 | { | |
608 | return true; | |
609 | } | |
610 | } | |
611 | else if (TREE_CODE (stmt) == ASM_EXPR) | |
612 | { | |
613 | if (walk_tree (&ASM_OUTPUTS (stmt), find_ptr_dereference, ptr, NULL) | |
614 | || walk_tree (&ASM_CLOBBERS (stmt), find_ptr_dereference, ptr, NULL)) | |
615 | { | |
616 | *is_store = true; | |
617 | return true; | |
618 | } | |
619 | else if (walk_tree (&ASM_INPUTS (stmt), find_ptr_dereference, ptr, NULL)) | |
620 | { | |
621 | return true; | |
622 | } | |
623 | } | |
624 | ||
625 | return false; | |
626 | } | |
627 | ||
628 | ||
629 | /* Traverse use-def links for all the pointers in the program to collect | |
630 | address escape and points-to information. | |
631 | ||
632 | This is loosely based on the same idea described in R. Hasti and S. | |
633 | Horwitz, ``Using static single assignment form to improve | |
634 | flow-insensitive pointer analysis,'' in SIGPLAN Conference on | |
635 | Programming Language Design and Implementation, pp. 97-105, 1998. */ | |
636 | ||
637 | static void | |
638 | compute_points_to_and_addr_escape (struct alias_info *ai) | |
639 | { | |
640 | basic_block bb; | |
3cd8c58a | 641 | unsigned i; |
4c124b4c AM |
642 | tree op; |
643 | ssa_op_iter iter; | |
6de9cd9a DN |
644 | |
645 | timevar_push (TV_TREE_PTA); | |
646 | ||
647 | FOR_EACH_BB (bb) | |
648 | { | |
649 | bb_ann_t block_ann = bb_ann (bb); | |
650 | block_stmt_iterator si; | |
651 | ||
652 | for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) | |
653 | { | |
6de9cd9a DN |
654 | bitmap addr_taken; |
655 | tree stmt = bsi_stmt (si); | |
656 | bool stmt_escapes_p = is_escape_site (stmt, &ai->num_calls_found); | |
87c476a2 | 657 | bitmap_iterator bi; |
6de9cd9a DN |
658 | |
659 | /* Mark all the variables whose address are taken by the | |
660 | statement. Note that this will miss all the addresses taken | |
661 | in PHI nodes (those are discovered while following the use-def | |
662 | chains). */ | |
663 | get_stmt_operands (stmt); | |
664 | addr_taken = addresses_taken (stmt); | |
665 | if (addr_taken) | |
87c476a2 ZD |
666 | EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi) |
667 | { | |
668 | tree var = referenced_var (i); | |
669 | bitmap_set_bit (ai->addresses_needed, var_ann (var)->uid); | |
670 | if (stmt_escapes_p) | |
671 | mark_call_clobbered (var); | |
672 | } | |
6de9cd9a DN |
673 | |
674 | if (stmt_escapes_p) | |
675 | block_ann->has_escape_site = 1; | |
676 | ||
4c124b4c | 677 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE) |
6de9cd9a | 678 | { |
6de9cd9a | 679 | var_ann_t v_ann = var_ann (SSA_NAME_VAR (op)); |
313679b0 | 680 | struct ptr_info_def *pi; |
6de9cd9a DN |
681 | bool is_store; |
682 | ||
683 | /* If the operand's variable may be aliased, keep track | |
684 | of how many times we've referenced it. This is used | |
685 | for alias grouping in compute_flow_sensitive_aliasing. | |
686 | Note that we don't need to grow AI->NUM_REFERENCES | |
687 | because we are processing regular variables, not | |
688 | memory tags (the array's initial size is set to | |
689 | NUM_REFERENCED_VARS). */ | |
690 | if (may_be_aliased (SSA_NAME_VAR (op))) | |
691 | (VARRAY_UINT (ai->num_references, v_ann->uid))++; | |
692 | ||
693 | if (!POINTER_TYPE_P (TREE_TYPE (op))) | |
694 | continue; | |
695 | ||
696 | collect_points_to_info_for (ai, op); | |
697 | ||
50dc9a88 | 698 | pi = SSA_NAME_PTR_INFO (op); |
6de9cd9a DN |
699 | if (ptr_is_dereferenced_by (op, stmt, &is_store)) |
700 | { | |
50dc9a88 DN |
701 | /* Mark OP as dereferenced. In a subsequent pass, |
702 | dereferenced pointers that point to a set of | |
703 | variables will be assigned a name tag to alias | |
704 | all the variables OP points to. */ | |
705 | pi->is_dereferenced = 1; | |
6de9cd9a DN |
706 | |
707 | /* Keep track of how many time we've dereferenced each | |
708 | pointer. Again, we don't need to grow | |
709 | AI->NUM_REFERENCES because we're processing | |
710 | existing program variables. */ | |
711 | (VARRAY_UINT (ai->num_references, v_ann->uid))++; | |
712 | ||
713 | /* If this is a store operation, mark OP as being | |
714 | dereferenced to store, otherwise mark it as being | |
715 | dereferenced to load. */ | |
716 | if (is_store) | |
717 | bitmap_set_bit (ai->dereferenced_ptrs_store, v_ann->uid); | |
718 | else | |
719 | bitmap_set_bit (ai->dereferenced_ptrs_load, v_ann->uid); | |
720 | } | |
721 | else if (stmt_escapes_p) | |
722 | { | |
723 | /* Note that even if STMT is an escape point, pointer OP | |
724 | will not escape if it is being dereferenced. That's | |
725 | why we only check for escape points if OP is not | |
726 | dereferenced by STMT. */ | |
313679b0 | 727 | pi->value_escapes_p = 1; |
6de9cd9a DN |
728 | |
729 | /* If the statement makes a function call, assume | |
730 | that pointer OP will be dereferenced in a store | |
731 | operation inside the called function. */ | |
732 | if (get_call_expr_in (stmt)) | |
92965c56 DN |
733 | { |
734 | bitmap_set_bit (ai->dereferenced_ptrs_store, v_ann->uid); | |
735 | pi->is_dereferenced = 1; | |
736 | } | |
6de9cd9a DN |
737 | } |
738 | } | |
739 | ||
740 | /* Update reference counter for definitions to any | |
741 | potentially aliased variable. This is used in the alias | |
742 | grouping heuristics. */ | |
4c124b4c | 743 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF) |
6de9cd9a | 744 | { |
6de9cd9a DN |
745 | tree var = SSA_NAME_VAR (op); |
746 | var_ann_t ann = var_ann (var); | |
747 | bitmap_set_bit (ai->written_vars, ann->uid); | |
748 | if (may_be_aliased (var)) | |
749 | (VARRAY_UINT (ai->num_references, ann->uid))++; | |
823f0809 DN |
750 | |
751 | if (POINTER_TYPE_P (TREE_TYPE (op))) | |
752 | collect_points_to_info_for (ai, op); | |
6de9cd9a DN |
753 | } |
754 | ||
a32b97a2 | 755 | /* Mark variables in V_MAY_DEF operands as being written to. */ |
4c124b4c | 756 | FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS) |
6de9cd9a | 757 | { |
a32b97a2 BB |
758 | tree var = SSA_NAME_VAR (op); |
759 | var_ann_t ann = var_ann (var); | |
760 | bitmap_set_bit (ai->written_vars, ann->uid); | |
761 | } | |
762 | ||
6de9cd9a DN |
763 | /* After promoting variables and computing aliasing we will |
764 | need to re-scan most statements. FIXME: Try to minimize the | |
765 | number of statements re-scanned. It's not really necessary to | |
766 | re-scan *all* statements. */ | |
767 | modify_stmt (stmt); | |
768 | } | |
769 | } | |
770 | ||
771 | timevar_pop (TV_TREE_PTA); | |
772 | } | |
773 | ||
774 | ||
d8903b30 DN |
775 | /* Create name tags for all the pointers that have been dereferenced. |
776 | We only create a name tag for a pointer P if P is found to point to | |
777 | a set of variables (so that we can alias them to *P) or if it is | |
778 | the result of a call to malloc (which means that P cannot point to | |
779 | anything else nor alias any other variable). | |
780 | ||
781 | If two pointers P and Q point to the same set of variables, they | |
782 | are assigned the same name tag. */ | |
783 | ||
784 | static void | |
785 | create_name_tags (struct alias_info *ai) | |
786 | { | |
787 | size_t i; | |
788 | ||
789 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) | |
790 | { | |
791 | tree ptr = VARRAY_TREE (ai->processed_ptrs, i); | |
792 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); | |
793 | ||
50dc9a88 | 794 | if (pi->pt_anything || !pi->is_dereferenced) |
9ae2a5d1 DN |
795 | { |
796 | /* No name tags for pointers that have not been | |
50dc9a88 | 797 | dereferenced or point to an arbitrary location. */ |
9ae2a5d1 DN |
798 | pi->name_mem_tag = NULL_TREE; |
799 | continue; | |
800 | } | |
d8903b30 | 801 | |
eb59b8de | 802 | if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars)) |
d8903b30 DN |
803 | { |
804 | size_t j; | |
53b4bf74 | 805 | tree old_name_tag = pi->name_mem_tag; |
d8903b30 DN |
806 | |
807 | /* If PTR points to a set of variables, check if we don't | |
808 | have another pointer Q with the same points-to set before | |
809 | creating a tag. If so, use Q's tag instead of creating a | |
810 | new one. | |
811 | ||
812 | This is important for not creating unnecessary symbols | |
813 | and also for copy propagation. If we ever need to | |
814 | propagate PTR into Q or vice-versa, we would run into | |
815 | problems if they both had different name tags because | |
816 | they would have different SSA version numbers (which | |
817 | would force us to take the name tags in and out of SSA). */ | |
d8903b30 DN |
818 | for (j = 0; j < i; j++) |
819 | { | |
820 | tree q = VARRAY_TREE (ai->processed_ptrs, j); | |
821 | struct ptr_info_def *qi = SSA_NAME_PTR_INFO (q); | |
822 | ||
823 | if (qi | |
824 | && qi->pt_vars | |
825 | && qi->name_mem_tag | |
826 | && bitmap_equal_p (pi->pt_vars, qi->pt_vars)) | |
827 | { | |
828 | pi->name_mem_tag = qi->name_mem_tag; | |
829 | break; | |
830 | } | |
831 | } | |
832 | ||
53b4bf74 DN |
833 | /* If we didn't find a pointer with the same points-to set |
834 | as PTR, create a new name tag if needed. */ | |
d8903b30 DN |
835 | if (pi->name_mem_tag == NULL_TREE) |
836 | pi->name_mem_tag = get_nmt_for (ptr); | |
53b4bf74 DN |
837 | |
838 | /* If the new name tag computed for PTR is different than | |
839 | the old name tag that it used to have, then the old tag | |
840 | needs to be removed from the IL, so we mark it for | |
841 | renaming. */ | |
842 | if (old_name_tag && old_name_tag != pi->name_mem_tag) | |
843 | bitmap_set_bit (vars_to_rename, var_ann (old_name_tag)->uid); | |
d8903b30 DN |
844 | } |
845 | else if (pi->pt_malloc) | |
846 | { | |
847 | /* Otherwise, create a unique name tag for this pointer. */ | |
848 | pi->name_mem_tag = get_nmt_for (ptr); | |
849 | } | |
850 | else | |
851 | { | |
852 | /* Only pointers that may point to malloc or other variables | |
853 | may receive a name tag. If the pointer does not point to | |
854 | a known spot, we should use type tags. */ | |
9ae2a5d1 DN |
855 | set_pt_anything (ptr); |
856 | continue; | |
d8903b30 DN |
857 | } |
858 | ||
38e05395 DN |
859 | TREE_THIS_VOLATILE (pi->name_mem_tag) |
860 | |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr))); | |
861 | ||
d8903b30 DN |
862 | /* Mark the new name tag for renaming. */ |
863 | bitmap_set_bit (vars_to_rename, var_ann (pi->name_mem_tag)->uid); | |
864 | } | |
865 | } | |
866 | ||
867 | ||
868 | ||
6de9cd9a DN |
869 | /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for |
870 | the name memory tag (NMT) associated with P_i. If P_i escapes, then its | |
871 | name tag and the variables it points-to are call-clobbered. Finally, if | |
872 | P_i escapes and we could not determine where it points to, then all the | |
873 | variables in the same alias set as *P_i are marked call-clobbered. This | |
874 | is necessary because we must assume that P_i may take the address of any | |
875 | variable in the same alias set. */ | |
876 | ||
877 | static void | |
878 | compute_flow_sensitive_aliasing (struct alias_info *ai) | |
879 | { | |
880 | size_t i; | |
881 | ||
d8903b30 DN |
882 | create_name_tags (ai); |
883 | ||
6de9cd9a DN |
884 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) |
885 | { | |
3cd8c58a | 886 | unsigned j; |
6de9cd9a | 887 | tree ptr = VARRAY_TREE (ai->processed_ptrs, i); |
313679b0 | 888 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
6de9cd9a | 889 | var_ann_t v_ann = var_ann (SSA_NAME_VAR (ptr)); |
87c476a2 | 890 | bitmap_iterator bi; |
6de9cd9a | 891 | |
313679b0 | 892 | if (pi->value_escapes_p || pi->pt_anything) |
6de9cd9a DN |
893 | { |
894 | /* If PTR escapes or may point to anything, then its associated | |
50dc9a88 | 895 | memory tags and pointed-to variables are call-clobbered. */ |
313679b0 DN |
896 | if (pi->name_mem_tag) |
897 | mark_call_clobbered (pi->name_mem_tag); | |
6de9cd9a DN |
898 | |
899 | if (v_ann->type_mem_tag) | |
900 | mark_call_clobbered (v_ann->type_mem_tag); | |
901 | ||
50dc9a88 | 902 | if (pi->pt_vars) |
87c476a2 ZD |
903 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) |
904 | { | |
905 | mark_call_clobbered (referenced_var (j)); | |
906 | } | |
6de9cd9a DN |
907 | } |
908 | ||
909 | /* Set up aliasing information for PTR's name memory tag (if it has | |
910 | one). Note that only pointers that have been dereferenced will | |
911 | have a name memory tag. */ | |
313679b0 | 912 | if (pi->name_mem_tag && pi->pt_vars) |
87c476a2 ZD |
913 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) |
914 | { | |
915 | add_may_alias (pi->name_mem_tag, referenced_var (j)); | |
e03a46f5 | 916 | add_may_alias (v_ann->type_mem_tag, referenced_var (j)); |
87c476a2 | 917 | } |
6de9cd9a DN |
918 | |
919 | /* If the name tag is call clobbered, so is the type tag | |
920 | associated with the base VAR_DECL. */ | |
313679b0 | 921 | if (pi->name_mem_tag |
6de9cd9a | 922 | && v_ann->type_mem_tag |
313679b0 | 923 | && is_call_clobbered (pi->name_mem_tag)) |
6de9cd9a DN |
924 | mark_call_clobbered (v_ann->type_mem_tag); |
925 | } | |
926 | } | |
927 | ||
928 | ||
929 | /* Compute type-based alias sets. Traverse all the pointers and | |
930 | addressable variables found in setup_pointers_and_addressables. | |
931 | ||
932 | For every pointer P in AI->POINTERS and addressable variable V in | |
933 | AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's type | |
934 | memory tag (TMT) if their alias sets conflict. V is then marked as | |
935 | an alias tag so that the operand scanner knows that statements | |
936 | containing V have aliased operands. */ | |
937 | ||
938 | static void | |
939 | compute_flow_insensitive_aliasing (struct alias_info *ai) | |
940 | { | |
941 | size_t i; | |
942 | ||
943 | /* Initialize counter for the total number of virtual operands that | |
944 | aliasing will introduce. When AI->TOTAL_ALIAS_VOPS goes beyond the | |
945 | threshold set by --params max-alias-vops, we enable alias | |
946 | grouping. */ | |
947 | ai->total_alias_vops = 0; | |
948 | ||
949 | /* For every pointer P, determine which addressable variables may alias | |
950 | with P's type memory tag. */ | |
951 | for (i = 0; i < ai->num_pointers; i++) | |
952 | { | |
953 | size_t j; | |
954 | struct alias_map_d *p_map = ai->pointers[i]; | |
955 | tree tag = var_ann (p_map->var)->type_mem_tag; | |
956 | var_ann_t tag_ann = var_ann (tag); | |
957 | ||
958 | p_map->total_alias_vops = 0; | |
959 | p_map->may_aliases = sbitmap_alloc (num_referenced_vars); | |
960 | sbitmap_zero (p_map->may_aliases); | |
961 | ||
962 | for (j = 0; j < ai->num_addressable_vars; j++) | |
963 | { | |
964 | struct alias_map_d *v_map; | |
965 | var_ann_t v_ann; | |
966 | tree var; | |
967 | bool tag_stored_p, var_stored_p; | |
968 | ||
969 | v_map = ai->addressable_vars[j]; | |
970 | var = v_map->var; | |
971 | v_ann = var_ann (var); | |
972 | ||
973 | /* Skip memory tags and variables that have never been | |
974 | written to. We also need to check if the variables are | |
975 | call-clobbered because they may be overwritten by | |
0bab1c88 JL |
976 | function calls. |
977 | ||
978 | Note this is effectively random accessing elements in | |
979 | the sparse bitset, which can be highly inefficient. | |
980 | So we first check the call_clobbered status of the | |
981 | tag and variable before querying the bitmap. */ | |
982 | tag_stored_p = is_call_clobbered (tag) | |
983 | || bitmap_bit_p (ai->written_vars, tag_ann->uid); | |
984 | var_stored_p = is_call_clobbered (var) | |
985 | || bitmap_bit_p (ai->written_vars, v_ann->uid); | |
6de9cd9a DN |
986 | if (!tag_stored_p && !var_stored_p) |
987 | continue; | |
988 | ||
989 | if (may_alias_p (p_map->var, p_map->set, var, v_map->set)) | |
990 | { | |
991 | size_t num_tag_refs, num_var_refs; | |
992 | ||
993 | num_tag_refs = VARRAY_UINT (ai->num_references, tag_ann->uid); | |
994 | num_var_refs = VARRAY_UINT (ai->num_references, v_ann->uid); | |
995 | ||
996 | /* Add VAR to TAG's may-aliases set. */ | |
997 | add_may_alias (tag, var); | |
998 | ||
999 | /* Update the total number of virtual operands due to | |
1000 | aliasing. Since we are adding one more alias to TAG's | |
1001 | may-aliases set, the total number of virtual operands due | |
1002 | to aliasing will be increased by the number of references | |
1003 | made to VAR and TAG (every reference to TAG will also | |
1004 | count as a reference to VAR). */ | |
1005 | ai->total_alias_vops += (num_var_refs + num_tag_refs); | |
1006 | p_map->total_alias_vops += (num_var_refs + num_tag_refs); | |
1007 | ||
1008 | /* Update the bitmap used to represent TAG's alias set | |
1009 | in case we need to group aliases. */ | |
1010 | SET_BIT (p_map->may_aliases, var_ann (var)->uid); | |
1011 | } | |
1012 | } | |
1013 | } | |
1014 | ||
1810f6ed DN |
1015 | /* Since this analysis is based exclusively on symbols, it fails to |
1016 | handle cases where two pointers P and Q have different memory | |
1017 | tags with conflicting alias set numbers but no aliased symbols in | |
1018 | common. | |
1019 | ||
1020 | For example, suppose that we have two memory tags TMT.1 and TMT.2 | |
1021 | such that | |
1022 | ||
1023 | may-aliases (TMT.1) = { a } | |
1024 | may-aliases (TMT.2) = { b } | |
1025 | ||
1026 | and the alias set number of TMT.1 conflicts with that of TMT.2. | |
1027 | Since they don't have symbols in common, loads and stores from | |
1028 | TMT.1 and TMT.2 will seem independent of each other, which will | |
1029 | lead to the optimizers making invalid transformations (see | |
1030 | testsuite/gcc.c-torture/execute/pr15262-[12].c). | |
1031 | ||
1032 | To avoid this problem, we do a final traversal of AI->POINTERS | |
1033 | looking for pairs of pointers that have no aliased symbols in | |
1034 | common and yet have conflicting alias set numbers. */ | |
1810f6ed DN |
1035 | for (i = 0; i < ai->num_pointers; i++) |
1036 | { | |
1037 | size_t j; | |
1038 | struct alias_map_d *p_map1 = ai->pointers[i]; | |
1039 | tree tag1 = var_ann (p_map1->var)->type_mem_tag; | |
1040 | sbitmap may_aliases1 = p_map1->may_aliases; | |
1041 | ||
1042 | for (j = i + 1; j < ai->num_pointers; j++) | |
1043 | { | |
1044 | struct alias_map_d *p_map2 = ai->pointers[j]; | |
1045 | tree tag2 = var_ann (p_map2->var)->type_mem_tag; | |
1810f6ed DN |
1046 | sbitmap may_aliases2 = p_map2->may_aliases; |
1047 | ||
1048 | /* If the pointers may not point to each other, do nothing. */ | |
1049 | if (!may_alias_p (p_map1->var, p_map1->set, p_map2->var, p_map2->set)) | |
1050 | continue; | |
1051 | ||
1052 | /* The two pointers may alias each other. If they already have | |
1053 | symbols in common, do nothing. */ | |
874437bc | 1054 | if (sbitmap_any_common_bits (may_aliases1, may_aliases2)) |
1810f6ed DN |
1055 | continue; |
1056 | ||
1057 | if (sbitmap_first_set_bit (may_aliases2) >= 0) | |
1058 | { | |
1059 | size_t k; | |
1060 | ||
1061 | /* Add all the aliases for TAG2 into TAG1's alias set. | |
1062 | FIXME, update grouping heuristic counters. */ | |
1063 | EXECUTE_IF_SET_IN_SBITMAP (may_aliases2, 0, k, | |
1064 | add_may_alias (tag1, referenced_var (k))); | |
1065 | sbitmap_a_or_b (may_aliases1, may_aliases1, may_aliases2); | |
1810f6ed DN |
1066 | } |
1067 | else | |
1068 | { | |
1069 | /* Since TAG2 does not have any aliases of its own, add | |
1070 | TAG2 itself to the alias set of TAG1. */ | |
1071 | add_may_alias (tag1, tag2); | |
1072 | } | |
1073 | } | |
1074 | } | |
1075 | ||
6de9cd9a DN |
1076 | if (dump_file) |
1077 | fprintf (dump_file, "%s: Total number of aliased vops: %ld\n", | |
1078 | get_name (current_function_decl), | |
1079 | ai->total_alias_vops); | |
1080 | ||
1081 | /* Determine if we need to enable alias grouping. */ | |
1082 | if (ai->total_alias_vops >= MAX_ALIASED_VOPS) | |
1083 | group_aliases (ai); | |
1084 | } | |
1085 | ||
1086 | ||
1087 | /* Comparison function for qsort used in group_aliases. */ | |
1088 | ||
1089 | static int | |
1090 | total_alias_vops_cmp (const void *p, const void *q) | |
1091 | { | |
1092 | const struct alias_map_d **p1 = (const struct alias_map_d **)p; | |
1093 | const struct alias_map_d **p2 = (const struct alias_map_d **)q; | |
1094 | long n1 = (*p1)->total_alias_vops; | |
1095 | long n2 = (*p2)->total_alias_vops; | |
1096 | ||
1097 | /* We want to sort in descending order. */ | |
1098 | return (n1 > n2 ? -1 : (n1 == n2) ? 0 : 1); | |
1099 | } | |
1100 | ||
1101 | /* Group all the aliases for TAG to make TAG represent all the | |
1102 | variables in its alias set. Update the total number | |
1103 | of virtual operands due to aliasing (AI->TOTAL_ALIAS_VOPS). This | |
1104 | function will make TAG be the unique alias tag for all the | |
1105 | variables in its may-aliases. So, given: | |
1106 | ||
1107 | may-aliases(TAG) = { V1, V2, V3 } | |
1108 | ||
1109 | This function will group the variables into: | |
1110 | ||
1111 | may-aliases(V1) = { TAG } | |
1112 | may-aliases(V2) = { TAG } | |
1113 | may-aliases(V2) = { TAG } */ | |
1114 | ||
1115 | static void | |
1116 | group_aliases_into (tree tag, sbitmap tag_aliases, struct alias_info *ai) | |
1117 | { | |
1118 | size_t i; | |
1119 | var_ann_t tag_ann = var_ann (tag); | |
1120 | size_t num_tag_refs = VARRAY_UINT (ai->num_references, tag_ann->uid); | |
1121 | ||
1122 | EXECUTE_IF_SET_IN_SBITMAP (tag_aliases, 0, i, | |
1123 | { | |
1124 | tree var = referenced_var (i); | |
1125 | var_ann_t ann = var_ann (var); | |
1126 | ||
1127 | /* Make TAG the unique alias of VAR. */ | |
1128 | ann->is_alias_tag = 0; | |
1129 | ann->may_aliases = NULL; | |
1130 | ||
1131 | /* Note that VAR and TAG may be the same if the function has no | |
1132 | addressable variables (see the discussion at the end of | |
9cf737f8 | 1133 | setup_pointers_and_addressables). */ |
6de9cd9a DN |
1134 | if (var != tag) |
1135 | add_may_alias (var, tag); | |
1136 | ||
1137 | /* Reduce total number of virtual operands contributed | |
1138 | by TAG on behalf of VAR. Notice that the references to VAR | |
1139 | itself won't be removed. We will merely replace them with | |
1140 | references to TAG. */ | |
1141 | ai->total_alias_vops -= num_tag_refs; | |
1142 | }); | |
1143 | ||
1144 | /* We have reduced the number of virtual operands that TAG makes on | |
1145 | behalf of all the variables formerly aliased with it. However, | |
1146 | we have also "removed" all the virtual operands for TAG itself, | |
1147 | so we add them back. */ | |
1148 | ai->total_alias_vops += num_tag_refs; | |
1149 | ||
1150 | /* TAG no longer has any aliases. */ | |
1151 | tag_ann->may_aliases = NULL; | |
1152 | } | |
1153 | ||
1154 | ||
1155 | /* Group may-aliases sets to reduce the number of virtual operands due | |
1156 | to aliasing. | |
1157 | ||
1158 | 1- Sort the list of pointers in decreasing number of contributed | |
1159 | virtual operands. | |
1160 | ||
1161 | 2- Take the first entry in AI->POINTERS and revert the role of | |
1162 | the memory tag and its aliases. Usually, whenever an aliased | |
1163 | variable Vi is found to alias with a memory tag T, we add Vi | |
1164 | to the may-aliases set for T. Meaning that after alias | |
1165 | analysis, we will have: | |
1166 | ||
1167 | may-aliases(T) = { V1, V2, V3, ..., Vn } | |
1168 | ||
1169 | This means that every statement that references T, will get 'n' | |
1170 | virtual operands for each of the Vi tags. But, when alias | |
1171 | grouping is enabled, we make T an alias tag and add it to the | |
1172 | alias set of all the Vi variables: | |
1173 | ||
1174 | may-aliases(V1) = { T } | |
1175 | may-aliases(V2) = { T } | |
1176 | ... | |
1177 | may-aliases(Vn) = { T } | |
1178 | ||
1179 | This has two effects: (a) statements referencing T will only get | |
1180 | a single virtual operand, and, (b) all the variables Vi will now | |
1181 | appear to alias each other. So, we lose alias precision to | |
1182 | improve compile time. But, in theory, a program with such a high | |
1183 | level of aliasing should not be very optimizable in the first | |
1184 | place. | |
1185 | ||
1186 | 3- Since variables may be in the alias set of more than one | |
1187 | memory tag, the grouping done in step (2) needs to be extended | |
1188 | to all the memory tags that have a non-empty intersection with | |
1189 | the may-aliases set of tag T. For instance, if we originally | |
1190 | had these may-aliases sets: | |
1191 | ||
1192 | may-aliases(T) = { V1, V2, V3 } | |
1193 | may-aliases(R) = { V2, V4 } | |
1194 | ||
1195 | In step (2) we would have reverted the aliases for T as: | |
1196 | ||
1197 | may-aliases(V1) = { T } | |
1198 | may-aliases(V2) = { T } | |
1199 | may-aliases(V3) = { T } | |
1200 | ||
1201 | But note that now V2 is no longer aliased with R. We could | |
1202 | add R to may-aliases(V2), but we are in the process of | |
1203 | grouping aliases to reduce virtual operands so what we do is | |
1204 | add V4 to the grouping to obtain: | |
1205 | ||
1206 | may-aliases(V1) = { T } | |
1207 | may-aliases(V2) = { T } | |
1208 | may-aliases(V3) = { T } | |
1209 | may-aliases(V4) = { T } | |
1210 | ||
1211 | 4- If the total number of virtual operands due to aliasing is | |
1212 | still above the threshold set by max-alias-vops, go back to (2). */ | |
1213 | ||
1214 | static void | |
1215 | group_aliases (struct alias_info *ai) | |
1216 | { | |
1217 | size_t i; | |
6de9cd9a DN |
1218 | |
1219 | /* Sort the POINTERS array in descending order of contributed | |
1220 | virtual operands. */ | |
1221 | qsort (ai->pointers, ai->num_pointers, sizeof (struct alias_map_d *), | |
1222 | total_alias_vops_cmp); | |
1223 | ||
6de9cd9a DN |
1224 | /* For every pointer in AI->POINTERS, reverse the roles of its tag |
1225 | and the tag's may-aliases set. */ | |
1226 | for (i = 0; i < ai->num_pointers; i++) | |
1227 | { | |
1228 | size_t j; | |
1229 | tree tag1 = var_ann (ai->pointers[i]->var)->type_mem_tag; | |
1230 | sbitmap tag1_aliases = ai->pointers[i]->may_aliases; | |
1231 | ||
1232 | /* Skip tags that have been grouped already. */ | |
1233 | if (ai->pointers[i]->grouped_p) | |
1234 | continue; | |
1235 | ||
1236 | /* See if TAG1 had any aliases in common with other type tags. | |
1237 | If we find a TAG2 with common aliases with TAG1, add TAG2's | |
1238 | aliases into TAG1. */ | |
1239 | for (j = i + 1; j < ai->num_pointers; j++) | |
1240 | { | |
1241 | sbitmap tag2_aliases = ai->pointers[j]->may_aliases; | |
1242 | ||
874437bc | 1243 | if (sbitmap_any_common_bits (tag1_aliases, tag2_aliases)) |
6de9cd9a DN |
1244 | { |
1245 | tree tag2 = var_ann (ai->pointers[j]->var)->type_mem_tag; | |
1246 | ||
1247 | sbitmap_a_or_b (tag1_aliases, tag1_aliases, tag2_aliases); | |
1248 | ||
1249 | /* TAG2 does not need its aliases anymore. */ | |
1250 | sbitmap_zero (tag2_aliases); | |
1251 | var_ann (tag2)->may_aliases = NULL; | |
1252 | ||
1253 | /* TAG1 is the unique alias of TAG2. */ | |
1254 | add_may_alias (tag2, tag1); | |
1255 | ||
1256 | ai->pointers[j]->grouped_p = true; | |
1257 | } | |
1258 | } | |
1259 | ||
1260 | /* Now group all the aliases we collected into TAG1. */ | |
1261 | group_aliases_into (tag1, tag1_aliases, ai); | |
1262 | ||
1263 | /* If we've reduced total number of virtual operands below the | |
1264 | threshold, stop. */ | |
1265 | if (ai->total_alias_vops < MAX_ALIASED_VOPS) | |
1266 | break; | |
1267 | } | |
1268 | ||
1269 | /* Finally, all the variables that have been grouped cannot be in | |
1270 | the may-alias set of name memory tags. Suppose that we have | |
1271 | grouped the aliases in this code so that may-aliases(a) = TMT.20 | |
1272 | ||
1273 | p_5 = &a; | |
1274 | ... | |
a32b97a2 | 1275 | # a_9 = V_MAY_DEF <a_8> |
6de9cd9a DN |
1276 | p_5->field = 0 |
1277 | ... Several modifications to TMT.20 ... | |
1278 | # VUSE <a_9> | |
1279 | x_30 = p_5->field | |
1280 | ||
1281 | Since p_5 points to 'a', the optimizers will try to propagate 0 | |
1282 | into p_5->field, but that is wrong because there have been | |
1283 | modifications to 'TMT.20' in between. To prevent this we have to | |
1284 | replace 'a' with 'TMT.20' in the name tag of p_5. */ | |
1285 | for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++) | |
1286 | { | |
1287 | size_t j; | |
1288 | tree ptr = VARRAY_TREE (ai->processed_ptrs, i); | |
313679b0 | 1289 | tree name_tag = SSA_NAME_PTR_INFO (ptr)->name_mem_tag; |
6de9cd9a DN |
1290 | varray_type aliases; |
1291 | ||
1292 | if (name_tag == NULL_TREE) | |
1293 | continue; | |
1294 | ||
1295 | aliases = var_ann (name_tag)->may_aliases; | |
1296 | for (j = 0; aliases && j < VARRAY_ACTIVE_SIZE (aliases); j++) | |
1297 | { | |
1298 | tree alias = VARRAY_TREE (aliases, j); | |
1299 | var_ann_t ann = var_ann (alias); | |
bbc630f5 DN |
1300 | |
1301 | if (ann->mem_tag_kind == NOT_A_TAG && ann->may_aliases) | |
6de9cd9a | 1302 | { |
53b4bf74 DN |
1303 | tree new_alias; |
1304 | ||
1e128c5f GB |
1305 | gcc_assert (VARRAY_ACTIVE_SIZE (ann->may_aliases) == 1); |
1306 | ||
53b4bf74 DN |
1307 | new_alias = VARRAY_TREE (ann->may_aliases, 0); |
1308 | replace_may_alias (name_tag, j, new_alias); | |
6de9cd9a DN |
1309 | } |
1310 | } | |
1311 | } | |
1312 | ||
6de9cd9a DN |
1313 | if (dump_file) |
1314 | fprintf (dump_file, | |
1315 | "%s: Total number of aliased vops after grouping: %ld%s\n", | |
1316 | get_name (current_function_decl), | |
1317 | ai->total_alias_vops, | |
1318 | (ai->total_alias_vops < 0) ? " (negative values are OK)" : ""); | |
1319 | } | |
1320 | ||
1321 | ||
1322 | /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */ | |
1323 | ||
1324 | static void | |
1325 | create_alias_map_for (tree var, struct alias_info *ai) | |
1326 | { | |
1327 | struct alias_map_d *alias_map; | |
1328 | alias_map = xcalloc (1, sizeof (*alias_map)); | |
1329 | alias_map->var = var; | |
fbc87627 | 1330 | alias_map->set = get_alias_set (var); |
6de9cd9a DN |
1331 | ai->addressable_vars[ai->num_addressable_vars++] = alias_map; |
1332 | } | |
1333 | ||
1334 | ||
1335 | /* Create memory tags for all the dereferenced pointers and build the | |
1336 | ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias | |
1337 | sets. Based on the address escape and points-to information collected | |
1338 | earlier, this pass will also clear the TREE_ADDRESSABLE flag from those | |
1339 | variables whose address is not needed anymore. */ | |
1340 | ||
1341 | static void | |
1342 | setup_pointers_and_addressables (struct alias_info *ai) | |
1343 | { | |
1344 | size_t i, n_vars, num_addressable_vars, num_pointers; | |
1345 | ||
1346 | /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */ | |
1347 | num_addressable_vars = num_pointers = 0; | |
1348 | for (i = 0; i < num_referenced_vars; i++) | |
1349 | { | |
1350 | tree var = referenced_var (i); | |
1351 | ||
1352 | if (may_be_aliased (var)) | |
1353 | num_addressable_vars++; | |
1354 | ||
1355 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
1356 | { | |
26e79d10 RH |
1357 | /* Since we don't keep track of volatile variables, assume that |
1358 | these pointers are used in indirect store operations. */ | |
1359 | if (TREE_THIS_VOLATILE (var)) | |
1360 | bitmap_set_bit (ai->dereferenced_ptrs_store, var_ann (var)->uid); | |
6de9cd9a DN |
1361 | |
1362 | num_pointers++; | |
1363 | } | |
1364 | } | |
1365 | ||
1366 | /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are | |
1367 | always going to be slightly bigger than we actually need them | |
1368 | because some TREE_ADDRESSABLE variables will be marked | |
1369 | non-addressable below and only pointers with unique type tags are | |
1370 | going to be added to POINTERS. */ | |
1371 | ai->addressable_vars = xcalloc (num_addressable_vars, | |
1372 | sizeof (struct alias_map_d *)); | |
1373 | ai->pointers = xcalloc (num_pointers, sizeof (struct alias_map_d *)); | |
1374 | ai->num_addressable_vars = 0; | |
1375 | ai->num_pointers = 0; | |
1376 | ||
1377 | /* Since we will be creating type memory tags within this loop, cache the | |
1378 | value of NUM_REFERENCED_VARS to avoid processing the additional tags | |
1379 | unnecessarily. */ | |
1380 | n_vars = num_referenced_vars; | |
1381 | ||
1382 | for (i = 0; i < n_vars; i++) | |
1383 | { | |
1384 | tree var = referenced_var (i); | |
1385 | var_ann_t v_ann = var_ann (var); | |
1386 | ||
d8903b30 DN |
1387 | /* Name memory tags already have flow-sensitive aliasing |
1388 | information, so they need not be processed by | |
1810f6ed DN |
1389 | compute_flow_insensitive_aliasing. Similarly, type memory |
1390 | tags are already accounted for when we process their | |
1391 | associated pointer. */ | |
6de9cd9a DN |
1392 | if (v_ann->mem_tag_kind != NOT_A_TAG) |
1393 | continue; | |
1394 | ||
1395 | /* Remove the ADDRESSABLE flag from every addressable variable whose | |
1396 | address is not needed anymore. This is caused by the propagation | |
1397 | of ADDR_EXPR constants into INDIRECT_REF expressions and the | |
1398 | removal of dead pointer assignments done by the early scalar | |
1399 | cleanup passes. */ | |
1400 | if (TREE_ADDRESSABLE (var)) | |
1401 | { | |
1402 | if (!bitmap_bit_p (ai->addresses_needed, v_ann->uid) | |
57e28d7d | 1403 | && TREE_CODE (var) != RESULT_DECL |
c597ef4e | 1404 | && !is_global_var (var)) |
6de9cd9a | 1405 | { |
d8903b30 DN |
1406 | /* The address of VAR is not needed, remove the |
1407 | addressable bit, so that it can be optimized as a | |
1408 | regular variable. */ | |
6de9cd9a DN |
1409 | mark_non_addressable (var); |
1410 | ||
1411 | /* Since VAR is now a regular GIMPLE register, we will need | |
1412 | to rename VAR into SSA afterwards. */ | |
1413 | bitmap_set_bit (vars_to_rename, v_ann->uid); | |
1414 | } | |
a6d02559 DN |
1415 | else |
1416 | { | |
1417 | /* Add the variable to the set of addressables. Mostly | |
1418 | used when scanning operands for ASM_EXPRs that | |
1419 | clobber memory. In those cases, we need to clobber | |
1420 | all call-clobbered variables and all addressables. */ | |
1421 | bitmap_set_bit (addressable_vars, v_ann->uid); | |
1422 | } | |
6de9cd9a DN |
1423 | } |
1424 | ||
1425 | /* Global variables and addressable locals may be aliased. Create an | |
1426 | entry in ADDRESSABLE_VARS for VAR. */ | |
1427 | if (may_be_aliased (var)) | |
1428 | { | |
1429 | create_alias_map_for (var, ai); | |
1430 | bitmap_set_bit (vars_to_rename, var_ann (var)->uid); | |
1431 | } | |
1432 | ||
1433 | /* Add pointer variables that have been dereferenced to the POINTERS | |
1434 | array and create a type memory tag for them. */ | |
c1b763fa | 1435 | if (POINTER_TYPE_P (TREE_TYPE (var))) |
6de9cd9a | 1436 | { |
c1b763fa DN |
1437 | if ((bitmap_bit_p (ai->dereferenced_ptrs_store, v_ann->uid) |
1438 | || bitmap_bit_p (ai->dereferenced_ptrs_load, v_ann->uid))) | |
1439 | { | |
1440 | tree tag; | |
1441 | var_ann_t t_ann; | |
1442 | ||
1443 | /* If pointer VAR still doesn't have a memory tag | |
1444 | associated with it, create it now or re-use an | |
1445 | existing one. */ | |
1446 | tag = get_tmt_for (var, ai); | |
1447 | t_ann = var_ann (tag); | |
1448 | ||
1449 | /* The type tag will need to be renamed into SSA | |
1450 | afterwards. Note that we cannot do this inside | |
1451 | get_tmt_for because aliasing may run multiple times | |
1452 | and we only create type tags the first time. */ | |
1453 | bitmap_set_bit (vars_to_rename, t_ann->uid); | |
1454 | ||
1455 | /* Associate the tag with pointer VAR. */ | |
1456 | v_ann->type_mem_tag = tag; | |
1457 | ||
1458 | /* If pointer VAR has been used in a store operation, | |
1459 | then its memory tag must be marked as written-to. */ | |
1460 | if (bitmap_bit_p (ai->dereferenced_ptrs_store, v_ann->uid)) | |
1461 | bitmap_set_bit (ai->written_vars, t_ann->uid); | |
1462 | ||
1463 | /* If pointer VAR is a global variable or a PARM_DECL, | |
1464 | then its memory tag should be considered a global | |
1465 | variable. */ | |
c597ef4e | 1466 | if (TREE_CODE (var) == PARM_DECL || is_global_var (var)) |
c1b763fa DN |
1467 | mark_call_clobbered (tag); |
1468 | ||
1469 | /* All the dereferences of pointer VAR count as | |
1470 | references of TAG. Since TAG can be associated with | |
1471 | several pointers, add the dereferences of VAR to the | |
1472 | TAG. We may need to grow AI->NUM_REFERENCES because | |
1473 | we have been adding name and type tags. */ | |
1474 | if (t_ann->uid >= VARRAY_SIZE (ai->num_references)) | |
1475 | VARRAY_GROW (ai->num_references, t_ann->uid + 10); | |
1476 | ||
1477 | VARRAY_UINT (ai->num_references, t_ann->uid) | |
1478 | += VARRAY_UINT (ai->num_references, v_ann->uid); | |
1479 | } | |
1480 | else | |
1481 | { | |
1482 | /* The pointer has not been dereferenced. If it had a | |
1483 | type memory tag, remove it and mark the old tag for | |
1484 | renaming to remove it out of the IL. */ | |
1485 | var_ann_t ann = var_ann (var); | |
1486 | tree tag = ann->type_mem_tag; | |
1487 | if (tag) | |
1488 | { | |
1489 | bitmap_set_bit (vars_to_rename, var_ann (tag)->uid); | |
1490 | ann->type_mem_tag = NULL_TREE; | |
1491 | } | |
1492 | } | |
6de9cd9a DN |
1493 | } |
1494 | } | |
6de9cd9a DN |
1495 | } |
1496 | ||
1497 | ||
a32b97a2 BB |
1498 | /* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At |
1499 | every call site, we need to emit V_MAY_DEF expressions to represent the | |
6de9cd9a DN |
1500 | clobbering effects of the call for variables whose address escapes the |
1501 | current function. | |
1502 | ||
1503 | One approach is to group all call-clobbered variables into a single | |
1504 | representative that is used as an alias of every call-clobbered variable | |
1505 | (.GLOBAL_VAR). This works well, but it ties the optimizer hands because | |
1506 | references to any call clobbered variable is a reference to .GLOBAL_VAR. | |
1507 | ||
a32b97a2 BB |
1508 | The second approach is to emit a clobbering V_MAY_DEF for every |
1509 | call-clobbered variable at call sites. This is the preferred way in terms | |
1510 | of optimization opportunities but it may create too many V_MAY_DEF operands | |
1511 | if there are many call clobbered variables and function calls in the | |
1512 | function. | |
6de9cd9a DN |
1513 | |
1514 | To decide whether or not to use .GLOBAL_VAR we multiply the number of | |
1515 | function calls found by the number of call-clobbered variables. If that | |
1516 | product is beyond a certain threshold, as determined by the parameterized | |
1517 | values shown below, we use .GLOBAL_VAR. | |
1518 | ||
1519 | FIXME. This heuristic should be improved. One idea is to use several | |
1520 | .GLOBAL_VARs of different types instead of a single one. The thresholds | |
1521 | have been derived from a typical bootstrap cycle, including all target | |
1522 | libraries. Compile times were found increase by ~1% compared to using | |
1523 | .GLOBAL_VAR. */ | |
1524 | ||
1525 | static void | |
1526 | maybe_create_global_var (struct alias_info *ai) | |
1527 | { | |
3cd8c58a | 1528 | unsigned i, n_clobbered; |
87c476a2 | 1529 | bitmap_iterator bi; |
6de9cd9a | 1530 | |
53b4bf74 | 1531 | /* No need to create it, if we have one already. */ |
e0d3bb46 DN |
1532 | if (global_var == NULL_TREE) |
1533 | { | |
1534 | /* Count all the call-clobbered variables. */ | |
1535 | n_clobbered = 0; | |
87c476a2 ZD |
1536 | EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) |
1537 | { | |
1538 | n_clobbered++; | |
1539 | } | |
6de9cd9a | 1540 | |
e0d3bb46 DN |
1541 | /* Create .GLOBAL_VAR if we have too many call-clobbered |
1542 | variables. We also create .GLOBAL_VAR when there no | |
1543 | call-clobbered variables to prevent code motion | |
1544 | transformations from re-arranging function calls that may | |
1545 | have side effects. For instance, | |
6de9cd9a | 1546 | |
e0d3bb46 | 1547 | foo () |
6de9cd9a DN |
1548 | { |
1549 | int a = f (); | |
1550 | g (); | |
1551 | h (a); | |
1552 | } | |
1553 | ||
e0d3bb46 DN |
1554 | There are no call-clobbered variables in foo(), so it would |
1555 | be entirely possible for a pass to want to move the call to | |
1556 | f() after the call to g(). If f() has side effects, that | |
1557 | would be wrong. Creating .GLOBAL_VAR in this case will | |
1558 | insert VDEFs for it and prevent such transformations. */ | |
1559 | if (n_clobbered == 0 | |
1560 | || ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD) | |
1561 | create_global_var (); | |
1562 | } | |
6de9cd9a DN |
1563 | |
1564 | /* If the function has calls to clobbering functions and .GLOBAL_VAR has | |
1565 | been created, make it an alias for all call-clobbered variables. */ | |
1566 | if (global_var) | |
87c476a2 | 1567 | EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) |
6de9cd9a DN |
1568 | { |
1569 | tree var = referenced_var (i); | |
1570 | if (var != global_var) | |
1571 | { | |
1572 | add_may_alias (var, global_var); | |
1573 | bitmap_set_bit (vars_to_rename, var_ann (var)->uid); | |
1574 | } | |
87c476a2 | 1575 | } |
6de9cd9a DN |
1576 | } |
1577 | ||
1578 | ||
1579 | /* Return TRUE if pointer PTR may point to variable VAR. | |
1580 | ||
1581 | MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR | |
1582 | This is needed because when checking for type conflicts we are | |
1583 | interested in the alias set of the memory location pointed-to by | |
1584 | PTR. The alias set of PTR itself is irrelevant. | |
1585 | ||
1586 | VAR_ALIAS_SET is the alias set for VAR. */ | |
1587 | ||
1588 | static bool | |
1589 | may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set, | |
1590 | tree var, HOST_WIDE_INT var_alias_set) | |
1591 | { | |
1592 | tree mem; | |
1593 | var_ann_t v_ann, m_ann; | |
1594 | ||
1595 | alias_stats.alias_queries++; | |
1596 | alias_stats.simple_queries++; | |
1597 | ||
1598 | /* By convention, a variable cannot alias itself. */ | |
1599 | mem = var_ann (ptr)->type_mem_tag; | |
1600 | if (mem == var) | |
1601 | { | |
1602 | alias_stats.alias_noalias++; | |
1603 | alias_stats.simple_resolved++; | |
1604 | return false; | |
1605 | } | |
1606 | ||
1607 | v_ann = var_ann (var); | |
1608 | m_ann = var_ann (mem); | |
1609 | ||
1e128c5f | 1610 | gcc_assert (m_ann->mem_tag_kind == TYPE_TAG); |
6de9cd9a DN |
1611 | |
1612 | alias_stats.tbaa_queries++; | |
1613 | ||
1614 | /* If VAR is a pointer with the same alias set as PTR, then dereferencing | |
1615 | PTR can't possibly affect VAR. Note, that we are specifically testing | |
1616 | for PTR's alias set here, not its pointed-to type. We also can't | |
1617 | do this check with relaxed aliasing enabled. */ | |
1618 | if (POINTER_TYPE_P (TREE_TYPE (var)) | |
391f9afb DN |
1619 | && var_alias_set != 0 |
1620 | && mem_alias_set != 0) | |
6de9cd9a DN |
1621 | { |
1622 | HOST_WIDE_INT ptr_alias_set = get_alias_set (ptr); | |
1623 | if (ptr_alias_set == var_alias_set) | |
1624 | { | |
1625 | alias_stats.alias_noalias++; | |
1626 | alias_stats.tbaa_resolved++; | |
1627 | return false; | |
1628 | } | |
1629 | } | |
1630 | ||
1631 | /* If the alias sets don't conflict then MEM cannot alias VAR. */ | |
1632 | if (!alias_sets_conflict_p (mem_alias_set, var_alias_set)) | |
1633 | { | |
1810f6ed DN |
1634 | alias_stats.alias_noalias++; |
1635 | alias_stats.tbaa_resolved++; | |
1636 | return false; | |
6de9cd9a DN |
1637 | } |
1638 | ||
6de9cd9a DN |
1639 | alias_stats.alias_mayalias++; |
1640 | return true; | |
1641 | } | |
1642 | ||
1643 | ||
1644 | /* Add ALIAS to the set of variables that may alias VAR. */ | |
1645 | ||
1646 | static void | |
1647 | add_may_alias (tree var, tree alias) | |
1648 | { | |
1649 | size_t i; | |
1650 | var_ann_t v_ann = get_var_ann (var); | |
1651 | var_ann_t a_ann = get_var_ann (alias); | |
1652 | ||
1e128c5f | 1653 | gcc_assert (var != alias); |
6de9cd9a DN |
1654 | |
1655 | if (v_ann->may_aliases == NULL) | |
1656 | VARRAY_TREE_INIT (v_ann->may_aliases, 2, "aliases"); | |
1657 | ||
1658 | /* Avoid adding duplicates. */ | |
1659 | for (i = 0; i < VARRAY_ACTIVE_SIZE (v_ann->may_aliases); i++) | |
1660 | if (alias == VARRAY_TREE (v_ann->may_aliases, i)) | |
1661 | return; | |
1662 | ||
e30b0ae2 DN |
1663 | /* If VAR is a call-clobbered variable, so is its new ALIAS. |
1664 | FIXME, call-clobbering should only depend on whether an address | |
1665 | escapes. It should be independent of aliasing. */ | |
1666 | if (is_call_clobbered (var)) | |
1667 | mark_call_clobbered (alias); | |
1668 | ||
1669 | /* Likewise. If ALIAS is call-clobbered, so is VAR. */ | |
1670 | else if (is_call_clobbered (alias)) | |
1671 | mark_call_clobbered (var); | |
1672 | ||
6de9cd9a DN |
1673 | VARRAY_PUSH_TREE (v_ann->may_aliases, alias); |
1674 | a_ann->is_alias_tag = 1; | |
1675 | } | |
1676 | ||
1677 | ||
53b4bf74 DN |
1678 | /* Replace alias I in the alias sets of VAR with NEW_ALIAS. */ |
1679 | ||
1680 | static void | |
1681 | replace_may_alias (tree var, size_t i, tree new_alias) | |
1682 | { | |
1683 | var_ann_t v_ann = var_ann (var); | |
1684 | VARRAY_TREE (v_ann->may_aliases, i) = new_alias; | |
e30b0ae2 DN |
1685 | |
1686 | /* If VAR is a call-clobbered variable, so is NEW_ALIAS. | |
1687 | FIXME, call-clobbering should only depend on whether an address | |
1688 | escapes. It should be independent of aliasing. */ | |
1689 | if (is_call_clobbered (var)) | |
1690 | mark_call_clobbered (new_alias); | |
1691 | ||
1692 | /* Likewise. If NEW_ALIAS is call-clobbered, so is VAR. */ | |
1693 | else if (is_call_clobbered (new_alias)) | |
1694 | mark_call_clobbered (var); | |
53b4bf74 DN |
1695 | } |
1696 | ||
1697 | ||
1698 | /* Mark pointer PTR as pointing to an arbitrary memory location. */ | |
1699 | ||
1700 | static void | |
1701 | set_pt_anything (tree ptr) | |
1702 | { | |
1703 | struct ptr_info_def *pi = get_ptr_info (ptr); | |
1704 | ||
1705 | pi->pt_anything = 1; | |
1706 | pi->pt_malloc = 0; | |
53b4bf74 DN |
1707 | |
1708 | /* The pointer used to have a name tag, but we now found it pointing | |
1709 | to an arbitrary location. The name tag needs to be renamed and | |
1710 | disassociated from PTR. */ | |
1711 | if (pi->name_mem_tag) | |
1712 | { | |
1713 | bitmap_set_bit (vars_to_rename, var_ann (pi->name_mem_tag)->uid); | |
1714 | pi->name_mem_tag = NULL_TREE; | |
1715 | } | |
1716 | } | |
1717 | ||
1718 | ||
1719 | /* Mark pointer PTR as pointing to a malloc'd memory area. */ | |
1720 | ||
1721 | static void | |
1722 | set_pt_malloc (tree ptr) | |
1723 | { | |
1724 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); | |
1725 | ||
1726 | /* If the pointer has already been found to point to arbitrary | |
8c27b7d4 | 1727 | memory locations, it is unsafe to mark it as pointing to malloc. */ |
53b4bf74 DN |
1728 | if (pi->pt_anything) |
1729 | return; | |
1730 | ||
1731 | pi->pt_malloc = 1; | |
1732 | } | |
1733 | ||
1734 | ||
0cde4a2c NS |
1735 | /* Given two different pointers DEST and ORIG. Merge the points-to |
1736 | information in ORIG into DEST. AI is as in | |
1737 | collect_points_to_info. */ | |
6de9cd9a DN |
1738 | |
1739 | static void | |
1740 | merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig) | |
1741 | { | |
313679b0 | 1742 | struct ptr_info_def *dest_pi, *orig_pi; |
6de9cd9a | 1743 | |
730bddf2 DN |
1744 | gcc_assert (dest != orig); |
1745 | ||
6de9cd9a DN |
1746 | /* Make sure we have points-to information for ORIG. */ |
1747 | collect_points_to_info_for (ai, orig); | |
1748 | ||
313679b0 DN |
1749 | dest_pi = get_ptr_info (dest); |
1750 | orig_pi = SSA_NAME_PTR_INFO (orig); | |
6de9cd9a | 1751 | |
313679b0 | 1752 | if (orig_pi) |
6de9cd9a | 1753 | { |
d8903b30 DN |
1754 | /* Notice that we never merge PT_MALLOC. This attribute is only |
1755 | true if the pointer is the result of a malloc() call. | |
1756 | Otherwise, we can end up in this situation: | |
1757 | ||
1758 | P_i = malloc (); | |
1759 | ... | |
1760 | P_j = P_i + X; | |
1761 | ||
3eebae0b DN |
1762 | P_j would be marked as PT_MALLOC, however we currently do not |
1763 | handle cases of more than one pointer pointing to the same | |
1764 | malloc'd area. | |
1765 | ||
1766 | FIXME: If the merging comes from an expression that preserves | |
1767 | the PT_MALLOC attribute (copy assignment, address | |
1768 | arithmetic), we ought to merge PT_MALLOC, but then both | |
1769 | pointers would end up getting different name tags because | |
1770 | create_name_tags is not smart enough to determine that the | |
1771 | two come from the same malloc call. Copy propagation before | |
1772 | aliasing should cure this. */ | |
0cde4a2c NS |
1773 | gcc_assert (orig_pi != dest_pi); |
1774 | ||
d8903b30 | 1775 | dest_pi->pt_malloc = 0; |
6de9cd9a | 1776 | |
53b4bf74 DN |
1777 | if (orig_pi->pt_malloc || orig_pi->pt_anything) |
1778 | set_pt_anything (dest); | |
1779 | ||
1780 | if (!dest_pi->pt_anything | |
1781 | && orig_pi->pt_vars | |
eb59b8de | 1782 | && !bitmap_empty_p (orig_pi->pt_vars)) |
6de9cd9a | 1783 | { |
313679b0 | 1784 | if (dest_pi->pt_vars == NULL) |
6de9cd9a | 1785 | { |
313679b0 DN |
1786 | dest_pi->pt_vars = BITMAP_GGC_ALLOC (); |
1787 | bitmap_copy (dest_pi->pt_vars, orig_pi->pt_vars); | |
6de9cd9a DN |
1788 | } |
1789 | else | |
67299d91 | 1790 | bitmap_ior_into (dest_pi->pt_vars, orig_pi->pt_vars); |
d8903b30 | 1791 | } |
6de9cd9a | 1792 | } |
50dc9a88 DN |
1793 | else |
1794 | set_pt_anything (dest); | |
6de9cd9a DN |
1795 | } |
1796 | ||
1797 | ||
20c16b36 | 1798 | /* Add EXPR to the list of expressions pointed-to by PTR. */ |
6de9cd9a DN |
1799 | |
1800 | static void | |
20c16b36 | 1801 | add_pointed_to_expr (struct alias_info *ai, tree ptr, tree expr) |
6de9cd9a | 1802 | { |
20c16b36 DN |
1803 | if (TREE_CODE (expr) == WITH_SIZE_EXPR) |
1804 | expr = TREE_OPERAND (expr, 0); | |
6de9cd9a | 1805 | |
53b4bf74 | 1806 | get_ptr_info (ptr); |
6de9cd9a | 1807 | |
20c16b36 DN |
1808 | if (TREE_CODE (expr) == CALL_EXPR |
1809 | && (call_expr_flags (expr) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))) | |
6de9cd9a | 1810 | { |
20c16b36 DN |
1811 | /* If EXPR is a malloc-like call, then the area pointed to PTR |
1812 | is guaranteed to not alias with anything else. */ | |
1813 | set_pt_malloc (ptr); | |
1814 | } | |
1815 | else if (TREE_CODE (expr) == ADDR_EXPR) | |
1816 | { | |
1817 | /* Found P_i = ADDR_EXPR */ | |
1818 | add_pointed_to_var (ai, ptr, expr); | |
1819 | } | |
1820 | else if (TREE_CODE (expr) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (expr))) | |
1821 | { | |
1822 | /* Found P_i = Q_j. */ | |
1823 | merge_pointed_to_info (ai, ptr, expr); | |
1824 | } | |
1825 | else if (TREE_CODE (expr) == PLUS_EXPR || TREE_CODE (expr) == MINUS_EXPR) | |
1826 | { | |
1827 | /* Found P_i = PLUS_EXPR or P_i = MINUS_EXPR */ | |
1828 | tree op0 = TREE_OPERAND (expr, 0); | |
1829 | tree op1 = TREE_OPERAND (expr, 1); | |
1830 | ||
1831 | /* Both operands may be of pointer type. FIXME: Shouldn't | |
1832 | we just expect PTR + OFFSET always? */ | |
1833 | if (POINTER_TYPE_P (TREE_TYPE (op0)) | |
1834 | && TREE_CODE (op0) != INTEGER_CST) | |
1835 | { | |
1836 | if (TREE_CODE (op0) == SSA_NAME) | |
1837 | merge_pointed_to_info (ai, ptr, op0); | |
1838 | else if (TREE_CODE (op0) == ADDR_EXPR) | |
1839 | add_pointed_to_var (ai, ptr, op0); | |
1840 | else | |
1841 | set_pt_anything (ptr); | |
1842 | } | |
53b4bf74 | 1843 | |
20c16b36 DN |
1844 | if (POINTER_TYPE_P (TREE_TYPE (op1)) |
1845 | && TREE_CODE (op1) != INTEGER_CST) | |
1846 | { | |
1847 | if (TREE_CODE (op1) == SSA_NAME) | |
1848 | merge_pointed_to_info (ai, ptr, op1); | |
1849 | else if (TREE_CODE (op1) == ADDR_EXPR) | |
1850 | add_pointed_to_var (ai, ptr, op1); | |
1851 | else | |
1852 | set_pt_anything (ptr); | |
1853 | } | |
1854 | ||
1855 | /* Neither operand is a pointer? VAR can be pointing anywhere. | |
1856 | FIXME: Shouldn't we abort here? If we get here, we found | |
1857 | PTR = INT_CST + INT_CST, which should not be a valid pointer | |
1858 | expression. */ | |
1859 | if (!(POINTER_TYPE_P (TREE_TYPE (op0)) | |
1860 | && TREE_CODE (op0) != INTEGER_CST) | |
1861 | && !(POINTER_TYPE_P (TREE_TYPE (op1)) | |
1862 | && TREE_CODE (op1) != INTEGER_CST)) | |
1863 | set_pt_anything (ptr); | |
1864 | } | |
1865 | else | |
1866 | { | |
1867 | /* If we can't recognize the expression, assume that PTR may | |
1868 | point anywhere. */ | |
1869 | set_pt_anything (ptr); | |
6de9cd9a DN |
1870 | } |
1871 | } | |
1872 | ||
1873 | ||
1874 | /* If VALUE is of the form &DECL, add DECL to the set of variables | |
1875 | pointed-to by PTR. Otherwise, add VALUE as a pointed-to expression by | |
1876 | PTR. AI is as in collect_points_to_info. */ | |
1877 | ||
1878 | static void | |
1879 | add_pointed_to_var (struct alias_info *ai, tree ptr, tree value) | |
1880 | { | |
53b4bf74 | 1881 | struct ptr_info_def *pi = get_ptr_info (ptr); |
92965c56 DN |
1882 | tree pt_var; |
1883 | size_t uid; | |
53b4bf74 | 1884 | |
1e128c5f | 1885 | gcc_assert (TREE_CODE (value) == ADDR_EXPR); |
6de9cd9a | 1886 | |
92965c56 | 1887 | pt_var = TREE_OPERAND (value, 0); |
6615c446 | 1888 | if (REFERENCE_CLASS_P (pt_var)) |
92965c56 | 1889 | pt_var = get_base_address (pt_var); |
6de9cd9a | 1890 | |
92965c56 DN |
1891 | if (pt_var && SSA_VAR_P (pt_var)) |
1892 | { | |
1893 | uid = var_ann (pt_var)->uid; | |
1894 | bitmap_set_bit (ai->addresses_needed, uid); | |
53b4bf74 | 1895 | |
50dc9a88 DN |
1896 | if (pi->pt_vars == NULL) |
1897 | pi->pt_vars = BITMAP_GGC_ALLOC (); | |
1898 | bitmap_set_bit (pi->pt_vars, uid); | |
1899 | ||
1900 | /* If the variable is a global, mark the pointer as pointing to | |
1901 | global memory (which will make its tag a global variable). */ | |
1902 | if (is_global_var (pt_var)) | |
1903 | pi->pt_global_mem = 1; | |
6de9cd9a | 1904 | } |
6de9cd9a DN |
1905 | } |
1906 | ||
1907 | ||
1908 | /* Callback for walk_use_def_chains to gather points-to information from the | |
1909 | SSA web. | |
1910 | ||
1911 | VAR is an SSA variable or a GIMPLE expression. | |
1912 | ||
1913 | STMT is the statement that generates the SSA variable or, if STMT is a | |
1914 | PHI_NODE, VAR is one of the PHI arguments. | |
1915 | ||
1916 | DATA is a pointer to a structure of type ALIAS_INFO. */ | |
1917 | ||
1918 | static bool | |
1919 | collect_points_to_info_r (tree var, tree stmt, void *data) | |
1920 | { | |
1921 | struct alias_info *ai = (struct alias_info *) data; | |
1922 | ||
1923 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
1924 | { | |
1925 | fprintf (dump_file, "Visiting use-def links for "); | |
1926 | print_generic_expr (dump_file, var, dump_flags); | |
1927 | fprintf (dump_file, "\n"); | |
1928 | } | |
1929 | ||
1e128c5f | 1930 | switch (TREE_CODE (stmt)) |
6de9cd9a | 1931 | { |
823f0809 DN |
1932 | case RETURN_EXPR: |
1933 | if (TREE_CODE (TREE_OPERAND (stmt, 0)) != MODIFY_EXPR) | |
1934 | abort (); | |
1935 | stmt = TREE_OPERAND (stmt, 0); | |
1936 | /* FALLTHRU */ | |
1937 | ||
1e128c5f GB |
1938 | case MODIFY_EXPR: |
1939 | { | |
1940 | tree rhs = TREE_OPERAND (stmt, 1); | |
1941 | STRIP_NOPS (rhs); | |
20c16b36 | 1942 | add_pointed_to_expr (ai, var, rhs); |
1e128c5f GB |
1943 | break; |
1944 | } | |
20c16b36 | 1945 | |
1e128c5f | 1946 | case ASM_EXPR: |
6de9cd9a | 1947 | /* Pointers defined by __asm__ statements can point anywhere. */ |
53b4bf74 | 1948 | set_pt_anything (var); |
1e128c5f | 1949 | break; |
6de9cd9a | 1950 | |
1e128c5f GB |
1951 | case NOP_EXPR: |
1952 | if (IS_EMPTY_STMT (stmt)) | |
1953 | { | |
1954 | tree decl = SSA_NAME_VAR (var); | |
1955 | ||
1956 | if (TREE_CODE (decl) == PARM_DECL) | |
20c16b36 | 1957 | add_pointed_to_expr (ai, var, decl); |
1e128c5f | 1958 | else if (DECL_INITIAL (decl)) |
20c16b36 | 1959 | add_pointed_to_expr (ai, var, DECL_INITIAL (decl)); |
1e128c5f | 1960 | else |
20c16b36 | 1961 | add_pointed_to_expr (ai, var, decl); |
1e128c5f GB |
1962 | } |
1963 | break; | |
20c16b36 | 1964 | |
1e128c5f GB |
1965 | case PHI_NODE: |
1966 | { | |
1967 | /* It STMT is a PHI node, then VAR is one of its arguments. The | |
1968 | variable that we are analyzing is the LHS of the PHI node. */ | |
1969 | tree lhs = PHI_RESULT (stmt); | |
6de9cd9a | 1970 | |
1e128c5f GB |
1971 | switch (TREE_CODE (var)) |
1972 | { | |
1973 | case ADDR_EXPR: | |
1974 | add_pointed_to_var (ai, lhs, var); | |
1975 | break; | |
1976 | ||
1977 | case SSA_NAME: | |
730bddf2 DN |
1978 | /* Avoid unnecessary merges. */ |
1979 | if (lhs != var) | |
1980 | merge_pointed_to_info (ai, lhs, var); | |
1e128c5f GB |
1981 | break; |
1982 | ||
1983 | default: | |
1984 | gcc_assert (is_gimple_min_invariant (var)); | |
20c16b36 | 1985 | add_pointed_to_expr (ai, lhs, var); |
1e128c5f GB |
1986 | break; |
1987 | } | |
1988 | break; | |
1989 | } | |
20c16b36 | 1990 | |
1e128c5f GB |
1991 | default: |
1992 | gcc_unreachable (); | |
1993 | } | |
1994 | ||
6de9cd9a DN |
1995 | return false; |
1996 | } | |
1997 | ||
1998 | ||
1999 | /* Return true if STMT is an "escape" site from the current function. Escape | |
2000 | sites those statements which might expose the address of a variable | |
2001 | outside the current function. STMT is an escape site iff: | |
2002 | ||
2003 | 1- STMT is a function call, or | |
2004 | 2- STMT is an __asm__ expression, or | |
2005 | 3- STMT is an assignment to a non-local variable, or | |
2006 | 4- STMT is a return statement. | |
2007 | ||
2008 | If NUM_CALLS_P is not NULL, the counter is incremented if STMT contains | |
2009 | a function call. */ | |
2010 | ||
2011 | static bool | |
2012 | is_escape_site (tree stmt, size_t *num_calls_p) | |
2013 | { | |
2014 | if (get_call_expr_in (stmt) != NULL_TREE) | |
2015 | { | |
2016 | if (num_calls_p) | |
2017 | (*num_calls_p)++; | |
2018 | ||
2019 | return true; | |
2020 | } | |
2021 | else if (TREE_CODE (stmt) == ASM_EXPR) | |
2022 | return true; | |
2023 | else if (TREE_CODE (stmt) == MODIFY_EXPR) | |
2024 | { | |
2025 | tree lhs = TREE_OPERAND (stmt, 0); | |
2026 | ||
2027 | /* Get to the base of _REF nodes. */ | |
2028 | if (TREE_CODE (lhs) != SSA_NAME) | |
2029 | lhs = get_base_address (lhs); | |
2030 | ||
2031 | /* If we couldn't recognize the LHS of the assignment, assume that it | |
2032 | is a non-local store. */ | |
2033 | if (lhs == NULL_TREE) | |
2034 | return true; | |
2035 | ||
406eab99 RK |
2036 | /* If the RHS is a conversion between a pointer and an integer, the |
2037 | pointer escapes since we can't track the integer. */ | |
2038 | if ((TREE_CODE (TREE_OPERAND (stmt, 1)) == NOP_EXPR | |
2039 | || TREE_CODE (TREE_OPERAND (stmt, 1)) == CONVERT_EXPR | |
2040 | || TREE_CODE (TREE_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR) | |
2041 | && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND | |
2042 | (TREE_OPERAND (stmt, 1), 0))) | |
2043 | && !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))) | |
2044 | return true; | |
2045 | ||
6de9cd9a DN |
2046 | /* If the LHS is an SSA name, it can't possibly represent a non-local |
2047 | memory store. */ | |
2048 | if (TREE_CODE (lhs) == SSA_NAME) | |
2049 | return false; | |
2050 | ||
2051 | /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a | |
2052 | local variables we cannot be sure if it will escape, because we | |
2053 | don't have information about objects not in SSA form. Need to | |
2054 | implement something along the lines of | |
2055 | ||
2056 | J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. | |
2057 | Midkiff, ``Escape analysis for java,'' in Proceedings of the | |
2058 | Conference on Object-Oriented Programming Systems, Languages, and | |
2059 | Applications (OOPSLA), pp. 1-19, 1999. */ | |
2060 | return true; | |
2061 | } | |
2062 | else if (TREE_CODE (stmt) == RETURN_EXPR) | |
2063 | return true; | |
2064 | ||
2065 | return false; | |
2066 | } | |
2067 | ||
2068 | ||
2069 | /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag | |
2070 | is considered to represent all the pointers whose pointed-to types are | |
2071 | in the same alias set class. Otherwise, the tag represents a single | |
2072 | SSA_NAME pointer variable. */ | |
2073 | ||
2074 | static tree | |
2075 | create_memory_tag (tree type, bool is_type_tag) | |
2076 | { | |
2077 | var_ann_t ann; | |
2078 | tree tag = create_tmp_var_raw (type, (is_type_tag) ? "TMT" : "NMT"); | |
2079 | ||
2080 | /* By default, memory tags are local variables. Alias analysis will | |
2081 | determine whether they should be considered globals. */ | |
2082 | DECL_CONTEXT (tag) = current_function_decl; | |
2083 | ||
6de9cd9a DN |
2084 | /* Memory tags are by definition addressable. This also prevents |
2085 | is_gimple_ref frome confusing memory tags with optimizable | |
2086 | variables. */ | |
2087 | TREE_ADDRESSABLE (tag) = 1; | |
2088 | ||
2089 | ann = get_var_ann (tag); | |
2090 | ann->mem_tag_kind = (is_type_tag) ? TYPE_TAG : NAME_TAG; | |
2091 | ann->type_mem_tag = NULL_TREE; | |
2092 | ||
d8903b30 | 2093 | /* Add the tag to the symbol table. */ |
6de9cd9a | 2094 | add_referenced_tmp_var (tag); |
6de9cd9a DN |
2095 | |
2096 | return tag; | |
2097 | } | |
2098 | ||
2099 | ||
2100 | /* Create a name memory tag to represent a specific SSA_NAME pointer P_i. | |
2101 | This is used if P_i has been found to point to a specific set of | |
2102 | variables or to a non-aliased memory location like the address returned | |
2103 | by malloc functions. */ | |
2104 | ||
2105 | static tree | |
2106 | get_nmt_for (tree ptr) | |
2107 | { | |
313679b0 DN |
2108 | struct ptr_info_def *pi = get_ptr_info (ptr); |
2109 | tree tag = pi->name_mem_tag; | |
6de9cd9a DN |
2110 | |
2111 | if (tag == NULL_TREE) | |
c597ef4e | 2112 | tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false); |
6de9cd9a | 2113 | |
50dc9a88 DN |
2114 | /* If PTR is a PARM_DECL, it points to a global variable or malloc, |
2115 | then its name tag should be considered a global variable. */ | |
2116 | if (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL | |
2117 | || pi->pt_malloc | |
2118 | || pi->pt_global_mem) | |
c597ef4e | 2119 | mark_call_clobbered (tag); |
6de9cd9a DN |
2120 | |
2121 | return tag; | |
2122 | } | |
2123 | ||
2124 | ||
2125 | /* Return the type memory tag associated to pointer PTR. A memory tag is an | |
2126 | artificial variable that represents the memory location pointed-to by | |
2127 | PTR. It is used to model the effects of pointer de-references on | |
2128 | addressable variables. | |
2129 | ||
2130 | AI points to the data gathered during alias analysis. This function | |
2131 | populates the array AI->POINTERS. */ | |
2132 | ||
2133 | static tree | |
2134 | get_tmt_for (tree ptr, struct alias_info *ai) | |
2135 | { | |
2136 | size_t i; | |
2137 | tree tag; | |
2138 | tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); | |
2139 | HOST_WIDE_INT tag_set = get_alias_set (tag_type); | |
2140 | ||
2141 | /* To avoid creating unnecessary memory tags, only create one memory tag | |
2142 | per alias set class. Note that it may be tempting to group | |
2143 | memory tags based on conflicting alias sets instead of | |
2144 | equivalence. That would be wrong because alias sets are not | |
2145 | necessarily transitive (as demonstrated by the libstdc++ test | |
2146 | 23_containers/vector/cons/4.cc). Given three alias sets A, B, C | |
2147 | such that conflicts (A, B) == true and conflicts (A, C) == true, | |
2148 | it does not necessarily follow that conflicts (B, C) == true. */ | |
2149 | for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++) | |
2150 | { | |
2151 | struct alias_map_d *curr = ai->pointers[i]; | |
0a050485 | 2152 | if (tag_set == curr->set) |
6de9cd9a DN |
2153 | { |
2154 | tag = var_ann (curr->var)->type_mem_tag; | |
2155 | break; | |
2156 | } | |
2157 | } | |
2158 | ||
2159 | /* If VAR cannot alias with any of the existing memory tags, create a new | |
2160 | tag for PTR and add it to the POINTERS array. */ | |
2161 | if (tag == NULL_TREE) | |
2162 | { | |
2163 | struct alias_map_d *alias_map; | |
2164 | ||
53b4bf74 DN |
2165 | /* If PTR did not have a type tag already, create a new TMT.* |
2166 | artificial variable representing the memory location | |
2167 | pointed-to by PTR. */ | |
2168 | if (var_ann (ptr)->type_mem_tag == NULL_TREE) | |
2169 | tag = create_memory_tag (tag_type, true); | |
2170 | else | |
2171 | tag = var_ann (ptr)->type_mem_tag; | |
6de9cd9a DN |
2172 | |
2173 | /* Add PTR to the POINTERS array. Note that we are not interested in | |
2174 | PTR's alias set. Instead, we cache the alias set for the memory that | |
2175 | PTR points to. */ | |
2176 | alias_map = xcalloc (1, sizeof (*alias_map)); | |
2177 | alias_map->var = ptr; | |
2178 | alias_map->set = tag_set; | |
2179 | ai->pointers[ai->num_pointers++] = alias_map; | |
2180 | } | |
2181 | ||
c04f07f4 | 2182 | /* If the pointed-to type is volatile, so is the tag. */ |
38e05395 | 2183 | TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type); |
c04f07f4 | 2184 | |
bbc630f5 DN |
2185 | /* Make sure that the type tag has the same alias set as the |
2186 | pointed-to type. */ | |
1e128c5f | 2187 | gcc_assert (tag_set == get_alias_set (tag)); |
bbc630f5 | 2188 | |
6de9cd9a DN |
2189 | return tag; |
2190 | } | |
2191 | ||
2192 | ||
2193 | /* Create GLOBAL_VAR, an artificial global variable to act as a | |
2194 | representative of all the variables that may be clobbered by function | |
2195 | calls. */ | |
2196 | ||
2197 | static void | |
2198 | create_global_var (void) | |
2199 | { | |
2200 | global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"), | |
b07f8ee2 | 2201 | void_type_node); |
6de9cd9a DN |
2202 | DECL_ARTIFICIAL (global_var) = 1; |
2203 | TREE_READONLY (global_var) = 0; | |
58907cda | 2204 | DECL_EXTERNAL (global_var) = 1; |
6de9cd9a DN |
2205 | TREE_STATIC (global_var) = 1; |
2206 | TREE_USED (global_var) = 1; | |
2207 | DECL_CONTEXT (global_var) = NULL_TREE; | |
2208 | TREE_THIS_VOLATILE (global_var) = 0; | |
2209 | TREE_ADDRESSABLE (global_var) = 0; | |
2210 | ||
2211 | add_referenced_tmp_var (global_var); | |
2212 | bitmap_set_bit (vars_to_rename, var_ann (global_var)->uid); | |
2213 | } | |
2214 | ||
2215 | ||
2216 | /* Dump alias statistics on FILE. */ | |
2217 | ||
2218 | static void | |
2219 | dump_alias_stats (FILE *file) | |
2220 | { | |
2221 | const char *funcname | |
673fda6b | 2222 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
6de9cd9a DN |
2223 | fprintf (file, "\nAlias statistics for %s\n\n", funcname); |
2224 | fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries); | |
2225 | fprintf (file, "Total alias mayalias results:\t%u\n", | |
2226 | alias_stats.alias_mayalias); | |
2227 | fprintf (file, "Total alias noalias results:\t%u\n", | |
2228 | alias_stats.alias_noalias); | |
2229 | fprintf (file, "Total simple queries:\t%u\n", | |
2230 | alias_stats.simple_queries); | |
2231 | fprintf (file, "Total simple resolved:\t%u\n", | |
2232 | alias_stats.simple_resolved); | |
2233 | fprintf (file, "Total TBAA queries:\t%u\n", | |
2234 | alias_stats.tbaa_queries); | |
2235 | fprintf (file, "Total TBAA resolved:\t%u\n", | |
2236 | alias_stats.tbaa_resolved); | |
6de9cd9a DN |
2237 | } |
2238 | ||
2239 | ||
2240 | /* Dump alias information on FILE. */ | |
2241 | ||
2242 | void | |
2243 | dump_alias_info (FILE *file) | |
2244 | { | |
2245 | size_t i; | |
2246 | const char *funcname | |
673fda6b | 2247 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
6de9cd9a | 2248 | |
53b4bf74 DN |
2249 | fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname); |
2250 | ||
2251 | fprintf (file, "Aliased symbols\n\n"); | |
2252 | for (i = 0; i < num_referenced_vars; i++) | |
2253 | { | |
2254 | tree var = referenced_var (i); | |
2255 | if (may_be_aliased (var)) | |
2256 | dump_variable (file, var); | |
2257 | } | |
2258 | ||
2259 | fprintf (file, "\nDereferenced pointers\n\n"); | |
2260 | for (i = 0; i < num_referenced_vars; i++) | |
2261 | { | |
2262 | tree var = referenced_var (i); | |
2263 | var_ann_t ann = var_ann (var); | |
2264 | if (ann->type_mem_tag) | |
2265 | dump_variable (file, var); | |
2266 | } | |
2267 | ||
2268 | fprintf (file, "\nType memory tags\n\n"); | |
2269 | for (i = 0; i < num_referenced_vars; i++) | |
2270 | { | |
2271 | tree var = referenced_var (i); | |
2272 | var_ann_t ann = var_ann (var); | |
2273 | if (ann->mem_tag_kind == TYPE_TAG) | |
2274 | dump_variable (file, var); | |
2275 | } | |
2276 | ||
2277 | fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname); | |
2278 | ||
2279 | fprintf (file, "SSA_NAME pointers\n\n"); | |
2280 | for (i = 1; i < num_ssa_names; i++) | |
2281 | { | |
2282 | tree ptr = ssa_name (i); | |
d804d490 DN |
2283 | struct ptr_info_def *pi; |
2284 | ||
2285 | if (ptr == NULL_TREE) | |
2286 | continue; | |
2287 | ||
2288 | pi = SSA_NAME_PTR_INFO (ptr); | |
53b4bf74 DN |
2289 | if (!SSA_NAME_IN_FREE_LIST (ptr) |
2290 | && pi | |
2291 | && pi->name_mem_tag) | |
2292 | dump_points_to_info_for (file, ptr); | |
2293 | } | |
6de9cd9a | 2294 | |
53b4bf74 | 2295 | fprintf (file, "\nName memory tags\n\n"); |
6de9cd9a DN |
2296 | for (i = 0; i < num_referenced_vars; i++) |
2297 | { | |
2298 | tree var = referenced_var (i); | |
2299 | var_ann_t ann = var_ann (var); | |
53b4bf74 | 2300 | if (ann->mem_tag_kind == NAME_TAG) |
6de9cd9a DN |
2301 | dump_variable (file, var); |
2302 | } | |
2303 | ||
2304 | fprintf (file, "\n"); | |
2305 | } | |
2306 | ||
2307 | ||
2308 | /* Dump alias information on stderr. */ | |
2309 | ||
2310 | void | |
2311 | debug_alias_info (void) | |
2312 | { | |
2313 | dump_alias_info (stderr); | |
2314 | } | |
2315 | ||
2316 | ||
313679b0 DN |
2317 | /* Return the alias information associated with pointer T. It creates a |
2318 | new instance if none existed. */ | |
2319 | ||
de66168d | 2320 | struct ptr_info_def * |
313679b0 DN |
2321 | get_ptr_info (tree t) |
2322 | { | |
2323 | struct ptr_info_def *pi; | |
2324 | ||
1e128c5f | 2325 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); |
313679b0 DN |
2326 | |
2327 | pi = SSA_NAME_PTR_INFO (t); | |
2328 | if (pi == NULL) | |
2329 | { | |
2330 | pi = ggc_alloc (sizeof (*pi)); | |
2331 | memset ((void *)pi, 0, sizeof (*pi)); | |
2332 | SSA_NAME_PTR_INFO (t) = pi; | |
2333 | } | |
2334 | ||
2335 | return pi; | |
2336 | } | |
2337 | ||
2338 | ||
6de9cd9a DN |
2339 | /* Dump points-to information for SSA_NAME PTR into FILE. */ |
2340 | ||
d8903b30 | 2341 | void |
6de9cd9a DN |
2342 | dump_points_to_info_for (FILE *file, tree ptr) |
2343 | { | |
313679b0 | 2344 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
6de9cd9a | 2345 | |
6de9cd9a DN |
2346 | print_generic_expr (file, ptr, dump_flags); |
2347 | ||
d8903b30 | 2348 | if (pi) |
6de9cd9a | 2349 | { |
d8903b30 DN |
2350 | if (pi->name_mem_tag) |
2351 | { | |
2352 | fprintf (file, ", name memory tag: "); | |
2353 | print_generic_expr (file, pi->name_mem_tag, dump_flags); | |
2354 | } | |
6de9cd9a | 2355 | |
d8903b30 DN |
2356 | if (pi->is_dereferenced) |
2357 | fprintf (file, ", is dereferenced"); | |
6de9cd9a | 2358 | |
d8903b30 DN |
2359 | if (pi->value_escapes_p) |
2360 | fprintf (file, ", its value escapes"); | |
6de9cd9a | 2361 | |
d8903b30 DN |
2362 | if (pi->pt_anything) |
2363 | fprintf (file, ", points-to anything"); | |
6de9cd9a | 2364 | |
d8903b30 DN |
2365 | if (pi->pt_malloc) |
2366 | fprintf (file, ", points-to malloc"); | |
6de9cd9a | 2367 | |
d8903b30 DN |
2368 | if (pi->pt_vars) |
2369 | { | |
2370 | unsigned ix; | |
87c476a2 | 2371 | bitmap_iterator bi; |
d8903b30 DN |
2372 | |
2373 | fprintf (file, ", points-to vars: { "); | |
87c476a2 ZD |
2374 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix, bi) |
2375 | { | |
2376 | print_generic_expr (file, referenced_var (ix), dump_flags); | |
2377 | fprintf (file, " "); | |
2378 | } | |
d8903b30 DN |
2379 | fprintf (file, "}"); |
2380 | } | |
6de9cd9a DN |
2381 | } |
2382 | ||
2383 | fprintf (file, "\n"); | |
2384 | } | |
2385 | ||
2386 | ||
d8903b30 DN |
2387 | /* Dump points-to information for VAR into stderr. */ |
2388 | ||
2389 | void | |
2390 | debug_points_to_info_for (tree var) | |
2391 | { | |
2392 | dump_points_to_info_for (stderr, var); | |
2393 | } | |
2394 | ||
2395 | ||
6de9cd9a DN |
2396 | /* Dump points-to information into FILE. NOTE: This function is slow, as |
2397 | it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */ | |
2398 | ||
2399 | void | |
2400 | dump_points_to_info (FILE *file) | |
2401 | { | |
2402 | basic_block bb; | |
2403 | block_stmt_iterator si; | |
2404 | size_t i; | |
4c124b4c | 2405 | ssa_op_iter iter; |
6de9cd9a | 2406 | const char *fname = |
673fda6b | 2407 | lang_hooks.decl_printable_name (current_function_decl, 2); |
6de9cd9a DN |
2408 | |
2409 | fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname); | |
2410 | ||
2411 | /* First dump points-to information for the default definitions of | |
2412 | pointer variables. This is necessary because default definitions are | |
2413 | not part of the code. */ | |
2414 | for (i = 0; i < num_referenced_vars; i++) | |
2415 | { | |
2416 | tree var = referenced_var (i); | |
2417 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
2418 | { | |
2419 | var_ann_t ann = var_ann (var); | |
2420 | if (ann->default_def) | |
2421 | dump_points_to_info_for (file, ann->default_def); | |
2422 | } | |
2423 | } | |
2424 | ||
2425 | /* Dump points-to information for every pointer defined in the program. */ | |
2426 | FOR_EACH_BB (bb) | |
2427 | { | |
2428 | tree phi; | |
2429 | ||
17192884 | 2430 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
2431 | { |
2432 | tree ptr = PHI_RESULT (phi); | |
2433 | if (POINTER_TYPE_P (TREE_TYPE (ptr))) | |
2434 | dump_points_to_info_for (file, ptr); | |
2435 | } | |
2436 | ||
2437 | for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) | |
2438 | { | |
4c124b4c AM |
2439 | tree stmt = bsi_stmt (si); |
2440 | tree def; | |
2441 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) | |
2442 | if (POINTER_TYPE_P (TREE_TYPE (def))) | |
2443 | dump_points_to_info_for (file, def); | |
6de9cd9a DN |
2444 | } |
2445 | } | |
2446 | ||
2447 | fprintf (file, "\n"); | |
2448 | } | |
2449 | ||
2450 | ||
2451 | /* Dump points-to info pointed by PTO into STDERR. */ | |
2452 | ||
2453 | void | |
2454 | debug_points_to_info (void) | |
2455 | { | |
2456 | dump_points_to_info (stderr); | |
2457 | } | |
2458 | ||
2459 | /* Dump to FILE the list of variables that may be aliasing VAR. */ | |
2460 | ||
2461 | void | |
2462 | dump_may_aliases_for (FILE *file, tree var) | |
2463 | { | |
2464 | varray_type aliases; | |
2465 | ||
2466 | if (TREE_CODE (var) == SSA_NAME) | |
2467 | var = SSA_NAME_VAR (var); | |
2468 | ||
2469 | aliases = var_ann (var)->may_aliases; | |
2470 | if (aliases) | |
2471 | { | |
2472 | size_t i; | |
2473 | fprintf (file, "{ "); | |
2474 | for (i = 0; i < VARRAY_ACTIVE_SIZE (aliases); i++) | |
2475 | { | |
2476 | print_generic_expr (file, VARRAY_TREE (aliases, i), dump_flags); | |
2477 | fprintf (file, " "); | |
2478 | } | |
2479 | fprintf (file, "}"); | |
2480 | } | |
2481 | } | |
2482 | ||
2483 | ||
2484 | /* Dump to stderr the list of variables that may be aliasing VAR. */ | |
2485 | ||
2486 | void | |
2487 | debug_may_aliases_for (tree var) | |
2488 | { | |
2489 | dump_may_aliases_for (stderr, var); | |
2490 | } | |
ab8907ef RH |
2491 | |
2492 | /* Return true if VAR may be aliased. */ | |
2493 | ||
2494 | bool | |
2495 | may_be_aliased (tree var) | |
2496 | { | |
2497 | /* Obviously. */ | |
2498 | if (TREE_ADDRESSABLE (var)) | |
2499 | return true; | |
2500 | ||
ab8907ef RH |
2501 | /* Globally visible variables can have their addresses taken by other |
2502 | translation units. */ | |
2503 | if (DECL_EXTERNAL (var) || TREE_PUBLIC (var)) | |
2504 | return true; | |
2505 | ||
bb1058e4 JW |
2506 | /* Automatic variables can't have their addresses escape any other way. |
2507 | This must be after the check for global variables, as extern declarations | |
2508 | do not have TREE_STATIC set. */ | |
2509 | if (!TREE_STATIC (var)) | |
2510 | return false; | |
2511 | ||
ab8907ef RH |
2512 | /* If we're in unit-at-a-time mode, then we must have seen all occurrences |
2513 | of address-of operators, and so we can trust TREE_ADDRESSABLE. Otherwise | |
2514 | we can only be sure the variable isn't addressable if it's local to the | |
2515 | current function. */ | |
2516 | if (flag_unit_at_a_time) | |
2517 | return false; | |
2518 | if (decl_function_context (var) == current_function_decl) | |
2519 | return false; | |
2520 | ||
2521 | return true; | |
2522 | } | |
2523 |