]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Alias analysis for trees. |
058dcc25 | 2 | Copyright (C) 2004, 2005, 2006, 2007 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 | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
26 | #include "rtl.h" | |
27 | #include "tm_p.h" | |
28 | #include "hard-reg-set.h" | |
29 | #include "basic-block.h" | |
30 | #include "timevar.h" | |
31 | #include "expr.h" | |
32 | #include "ggc.h" | |
33 | #include "langhooks.h" | |
34 | #include "flags.h" | |
35 | #include "function.h" | |
36 | #include "diagnostic.h" | |
37 | #include "tree-dump.h" | |
eadf906f | 38 | #include "tree-gimple.h" |
6de9cd9a DN |
39 | #include "tree-flow.h" |
40 | #include "tree-inline.h" | |
6de9cd9a | 41 | #include "tree-pass.h" |
e8ca4159 | 42 | #include "tree-ssa-structalias.h" |
6de9cd9a DN |
43 | #include "convert.h" |
44 | #include "params.h" | |
ea900239 | 45 | #include "ipa-type-escape.h" |
c75ab022 | 46 | #include "vec.h" |
a3648cfc | 47 | #include "bitmap.h" |
e3df376d | 48 | #include "vecprim.h" |
38635499 | 49 | #include "pointer-set.h" |
603802e7 | 50 | #include "alloc-pool.h" |
a3648cfc | 51 | |
6e2dc028 DB |
52 | /* Broad overview of how aliasing works: |
53 | ||
54 | First we compute points-to sets, which is done in | |
55 | tree-ssa-structalias.c | |
56 | ||
57 | During points-to set constraint finding, a bunch of little bits of | |
58 | information is collected. | |
59 | This is not done because it is necessary for points-to, but because | |
60 | points-to has to walk every statement anyway. The function performing | |
61 | this collecting is update_alias_info. | |
62 | ||
63 | Bits update_alias_info collects include: | |
64 | 1. Directly escaping variables and variables whose value escapes | |
65 | (using is_escape_site). This is the set of variables and values that | |
66 | escape prior to transitive closure of the clobbers. | |
67 | 2. The set of variables dereferenced on the LHS (into | |
68 | dereferenced_ptr_stores) | |
69 | 3. The set of variables dereferenced on the RHS (into | |
70 | dereferenced_ptr_loads) | |
71 | 4. The set of all pointers we saw. | |
72 | 5. The number of loads and stores for each variable | |
73 | 6. The number of statements touching memory | |
74 | 7. The set of address taken variables. | |
75 | ||
76 | ||
77 | #1 is computed by a combination of is_escape_site, and counting the | |
78 | number of uses/deref operators. This function properly accounts for | |
79 | situations like &ptr->field, which is *not* a dereference. | |
80 | ||
81 | After points-to sets are computed, the sets themselves still | |
82 | contain points-to specific variables, such as a variable that says | |
83 | the pointer points to anything, a variable that says the pointer | |
84 | points to readonly memory, etc. | |
85 | ||
86 | These are eliminated in a later phase, as we will see. | |
87 | ||
88 | The rest of the phases are located in tree-ssa-alias.c | |
89 | ||
90 | The next phase after points-to set computation is called | |
91 | "setup_pointers_and_addressables" | |
92 | ||
93 | This pass does 3 main things: | |
94 | ||
95 | 1. All variables that can have TREE_ADDRESSABLE removed safely (IE | |
96 | non-globals whose address is not taken), have TREE_ADDRESSABLE | |
97 | removed. | |
98 | 2. All variables that may be aliased (which is the set of addressable | |
99 | variables and globals) at all, are marked for renaming, and have | |
100 | symbol memory tags created for them. | |
101 | 3. All variables which are stored into have their SMT's added to | |
102 | written vars. | |
103 | ||
104 | ||
105 | After this function is run, all variables that will ever have an | |
106 | SMT, have one, though its aliases are not filled in. | |
107 | ||
108 | The next phase is to compute flow-insensitive aliasing, which in | |
109 | our case, is a misnomer. it is really computing aliasing that | |
110 | requires no transitive closure to be correct. In particular, it | |
111 | uses stack vs non-stack, TBAA, etc, to determine whether two | |
112 | symbols could *ever* alias . This phase works by going through all | |
113 | the pointers we collected during update_alias_info, and for every | |
114 | addressable variable in the program, seeing if they alias. If so, | |
115 | the addressable variable is added to the symbol memory tag for the | |
116 | pointer. | |
117 | ||
118 | As part of this, we handle symbol memory tags that conflict but | |
119 | have no aliases in common, by forcing them to have a symbol in | |
120 | common (through unioning alias sets or adding one as an alias of | |
121 | the other), or by adding one as an alias of another. The case of | |
122 | conflicts with no aliases in common occurs mainly due to aliasing | |
123 | we cannot see. In particular, it generally means we have a load | |
124 | through a pointer whose value came from outside the function. | |
125 | Without an addressable symbol to point to, they would get the wrong | |
126 | answer. | |
127 | ||
128 | After flow insensitive aliasing is computed, we compute name tags | |
129 | (called compute_flow_sensitive_info). We walk each pointer we | |
130 | collected and see if it has a usable points-to set. If so, we | |
131 | generate a name tag using that pointer, and make an alias bitmap for | |
132 | it. Name tags are shared between all things with the same alias | |
133 | bitmap. The alias bitmap will be translated from what points-to | |
134 | computed. In particular, the "anything" variable in points-to will be | |
135 | transformed into a pruned set of SMT's and their aliases that | |
136 | compute_flow_insensitive_aliasing computed. | |
137 | Note that since 4.3, every pointer that points-to computed a solution for | |
138 | will get a name tag (whereas before 4.3, only those whose set did | |
139 | *not* include the anything variable would). At the point where name | |
140 | tags are all assigned, symbol memory tags are dead, and could be | |
141 | deleted, *except* on global variables. Global variables still use | |
142 | symbol memory tags as of right now. | |
143 | ||
144 | After name tags are computed, the set of clobbered variables is | |
145 | transitively closed. In particular, we compute the set of clobbered | |
146 | variables based on the initial set of clobbers, plus the aliases of | |
147 | pointers which either escape, or have their value escape. | |
148 | ||
149 | After this, maybe_create_global_var is run, which handles a corner | |
150 | case where we have no call clobbered variables, but have pure and | |
151 | non-pure functions. | |
152 | ||
153 | Staring at this function, I now remember it is a hack for the fact | |
154 | that we do not mark all globals in the program as call clobbered for a | |
155 | function unless they are actually used in that function. Instead, we | |
156 | only mark the set that is actually clobbered. As a result, you can | |
157 | end up with situations where you have no call clobbered vars set. | |
158 | ||
159 | After maybe_create_global_var, we set pointers with the REF_ALL flag | |
160 | to have alias sets that include all clobbered | |
161 | memory tags and variables. | |
162 | ||
163 | After this, memory partitioning is computed (by the function | |
164 | compute_memory_partitions) and alias sets are reworked accordingly. | |
165 | ||
166 | Lastly, we delete partitions with no symbols, and clean up after | |
167 | ourselves. */ | |
168 | ||
38635499 | 169 | /* Structure to map a variable to its alias set. */ |
6de9cd9a DN |
170 | struct alias_map_d |
171 | { | |
172 | /* Variable and its alias set. */ | |
173 | tree var; | |
4862826d | 174 | alias_set_type set; |
38635499 | 175 | }; |
6de9cd9a | 176 | |
6de9cd9a | 177 | |
6de9cd9a DN |
178 | /* Counters used to display statistics on alias analysis. */ |
179 | struct alias_stats_d | |
180 | { | |
181 | unsigned int alias_queries; | |
182 | unsigned int alias_mayalias; | |
183 | unsigned int alias_noalias; | |
184 | unsigned int simple_queries; | |
185 | unsigned int simple_resolved; | |
186 | unsigned int tbaa_queries; | |
187 | unsigned int tbaa_resolved; | |
ea900239 DB |
188 | unsigned int structnoaddress_queries; |
189 | unsigned int structnoaddress_resolved; | |
6de9cd9a DN |
190 | }; |
191 | ||
192 | ||
193 | /* Local variables. */ | |
194 | static struct alias_stats_d alias_stats; | |
306219a2 | 195 | static bitmap_obstack alias_bitmap_obstack; |
6de9cd9a DN |
196 | |
197 | /* Local functions. */ | |
198 | static void compute_flow_insensitive_aliasing (struct alias_info *); | |
05a58ad4 | 199 | static void finalize_ref_all_pointers (struct alias_info *); |
6de9cd9a | 200 | static void dump_alias_stats (FILE *); |
4862826d | 201 | static bool may_alias_p (tree, alias_set_type, tree, alias_set_type, bool); |
6de9cd9a | 202 | static tree create_memory_tag (tree type, bool is_type_tag); |
38635499 | 203 | static tree get_smt_for (tree, struct alias_info *); |
6de9cd9a | 204 | static tree get_nmt_for (tree); |
306219a2 | 205 | static void add_may_alias (tree, tree); |
6de9cd9a DN |
206 | static struct alias_info *init_alias_info (void); |
207 | static void delete_alias_info (struct alias_info *); | |
6de9cd9a DN |
208 | static void compute_flow_sensitive_aliasing (struct alias_info *); |
209 | static void setup_pointers_and_addressables (struct alias_info *); | |
6de9cd9a | 210 | static void create_global_var (void); |
e9e0aa2c DN |
211 | static void maybe_create_global_var (void); |
212 | static void set_pt_anything (tree); | |
213 | ||
214 | void debug_mp_info (VEC(mem_sym_stats_t,heap) *); | |
215 | ||
603802e7 | 216 | static alloc_pool mem_sym_stats_pool; |
79bedddc | 217 | |
e9e0aa2c DN |
218 | /* Return memory reference stats for symbol VAR. Create a new slot in |
219 | cfun->gimple_df->mem_sym_stats if needed. */ | |
220 | ||
221 | static struct mem_sym_stats_d * | |
222 | get_mem_sym_stats_for (tree var) | |
223 | { | |
224 | void **slot; | |
225 | struct mem_sym_stats_d *stats; | |
226 | struct pointer_map_t *map = gimple_mem_ref_stats (cfun)->mem_sym_stats; | |
227 | ||
228 | gcc_assert (map); | |
229 | ||
230 | slot = pointer_map_insert (map, var); | |
231 | if (*slot == NULL) | |
232 | { | |
603802e7 DB |
233 | stats = pool_alloc (mem_sym_stats_pool); |
234 | memset (stats, 0, sizeof (*stats)); | |
e9e0aa2c DN |
235 | stats->var = var; |
236 | *slot = (void *) stats; | |
237 | } | |
238 | else | |
239 | stats = (struct mem_sym_stats_d *) *slot; | |
240 | ||
241 | return stats; | |
242 | } | |
243 | ||
6de9cd9a | 244 | |
cfff829f RG |
245 | /* Return memory reference statistics for variable VAR in function FN. |
246 | This is computed by alias analysis, but it is not kept | |
247 | incrementally up-to-date. So, these stats are only accurate if | |
248 | pass_may_alias has been run recently. If no alias information | |
249 | exists, this function returns NULL. */ | |
250 | ||
251 | static mem_sym_stats_t | |
252 | mem_sym_stats (struct function *fn, tree var) | |
253 | { | |
254 | void **slot; | |
255 | struct pointer_map_t *stats_map = gimple_mem_ref_stats (fn)->mem_sym_stats; | |
256 | ||
257 | if (stats_map == NULL) | |
258 | return NULL; | |
259 | ||
260 | slot = pointer_map_contains (stats_map, var); | |
261 | if (slot == NULL) | |
262 | return NULL; | |
263 | ||
264 | return (mem_sym_stats_t) *slot; | |
265 | } | |
266 | ||
267 | ||
e9e0aa2c DN |
268 | /* Set MPT to be the memory partition associated with symbol SYM. */ |
269 | ||
270 | static inline void | |
271 | set_memory_partition (tree sym, tree mpt) | |
272 | { | |
273 | #if defined ENABLE_CHECKING | |
274 | if (mpt) | |
275 | gcc_assert (TREE_CODE (mpt) == MEMORY_PARTITION_TAG | |
276 | && !is_gimple_reg (sym)); | |
277 | #endif | |
278 | ||
279 | var_ann (sym)->mpt = mpt; | |
280 | if (mpt) | |
281 | { | |
282 | if (MPT_SYMBOLS (mpt) == NULL) | |
283 | MPT_SYMBOLS (mpt) = BITMAP_ALLOC (&alias_bitmap_obstack); | |
284 | ||
285 | bitmap_set_bit (MPT_SYMBOLS (mpt), DECL_UID (sym)); | |
286 | ||
287 | /* MPT inherits the call-clobbering attributes from SYM. */ | |
288 | if (is_call_clobbered (sym)) | |
289 | { | |
290 | MTAG_GLOBAL (mpt) = 1; | |
291 | mark_call_clobbered (mpt, ESCAPE_IS_GLOBAL); | |
292 | } | |
293 | } | |
294 | } | |
38635499 | 295 | |
6de9cd9a | 296 | |
38635499 DN |
297 | /* Mark variable VAR as being non-addressable. */ |
298 | ||
299 | static void | |
300 | mark_non_addressable (tree var) | |
301 | { | |
302 | tree mpt; | |
303 | ||
304 | if (!TREE_ADDRESSABLE (var)) | |
305 | return; | |
306 | ||
307 | mpt = memory_partition (var); | |
308 | ||
309 | if (!MTAG_P (var)) | |
b730fa61 | 310 | var_ann (var)->call_clobbered = false; |
38635499 DN |
311 | |
312 | bitmap_clear_bit (gimple_call_clobbered_vars (cfun), DECL_UID (var)); | |
313 | TREE_ADDRESSABLE (var) = 0; | |
314 | ||
315 | if (mpt) | |
316 | { | |
e9e0aa2c DN |
317 | /* Note that it's possible for a symbol to have an associated |
318 | MPT and the MPT have a NULL empty set. During | |
319 | init_alias_info, all MPTs get their sets cleared out, but the | |
320 | symbols still point to the old MPTs that used to hold them. | |
321 | This is done so that compute_memory_partitions can now which | |
322 | symbols are losing or changing partitions and mark them for | |
323 | renaming. */ | |
324 | if (MPT_SYMBOLS (mpt)) | |
325 | bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var)); | |
38635499 DN |
326 | set_memory_partition (var, NULL_TREE); |
327 | } | |
328 | } | |
329 | ||
330 | ||
d16a5e36 DB |
331 | /* qsort comparison function to sort type/name tags by DECL_UID. */ |
332 | ||
333 | static int | |
334 | sort_tags_by_id (const void *pa, const void *pb) | |
335 | { | |
741ac903 KG |
336 | const_tree const a = *(const_tree const *)pa; |
337 | const_tree const b = *(const_tree const *)pb; | |
d16a5e36 DB |
338 | |
339 | return DECL_UID (a) - DECL_UID (b); | |
340 | } | |
341 | ||
342 | /* Initialize WORKLIST to contain those memory tags that are marked call | |
343 | clobbered. Initialized WORKLIST2 to contain the reasons these | |
344 | memory tags escaped. */ | |
345 | ||
346 | static void | |
347 | init_transitive_clobber_worklist (VEC (tree, heap) **worklist, | |
7b765bed DB |
348 | VEC (int, heap) **worklist2, |
349 | bitmap on_worklist) | |
d16a5e36 DB |
350 | { |
351 | referenced_var_iterator rvi; | |
352 | tree curr; | |
353 | ||
354 | FOR_EACH_REFERENCED_VAR (curr, rvi) | |
355 | { | |
356 | if (MTAG_P (curr) && is_call_clobbered (curr)) | |
357 | { | |
358 | VEC_safe_push (tree, heap, *worklist, curr); | |
7b765bed DB |
359 | VEC_safe_push (int, heap, *worklist2, |
360 | var_ann (curr)->escape_mask); | |
361 | bitmap_set_bit (on_worklist, DECL_UID (curr)); | |
d16a5e36 DB |
362 | } |
363 | } | |
364 | } | |
365 | ||
366 | /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if | |
367 | ALIAS is not already marked call clobbered, and is a memory | |
368 | tag. */ | |
369 | ||
370 | static void | |
371 | add_to_worklist (tree alias, VEC (tree, heap) **worklist, | |
7b765bed DB |
372 | VEC (int, heap) **worklist2, int reason, |
373 | bitmap on_worklist) | |
d16a5e36 | 374 | { |
7b765bed DB |
375 | if (MTAG_P (alias) && !is_call_clobbered (alias) |
376 | && !bitmap_bit_p (on_worklist, DECL_UID (alias))) | |
d16a5e36 DB |
377 | { |
378 | VEC_safe_push (tree, heap, *worklist, alias); | |
379 | VEC_safe_push (int, heap, *worklist2, reason); | |
7b765bed | 380 | bitmap_set_bit (on_worklist, DECL_UID (alias)); |
d16a5e36 DB |
381 | } |
382 | } | |
383 | ||
384 | /* Mark aliases of TAG as call clobbered, and place any tags on the | |
385 | alias list that were not already call clobbered on WORKLIST. */ | |
386 | ||
387 | static void | |
388 | mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist, | |
7b765bed | 389 | VEC (int, heap) **worklist2, |
91fe0424 | 390 | bitmap on_worklist, bitmap queued) |
d16a5e36 | 391 | { |
306219a2 | 392 | bitmap aliases; |
3b302421 RG |
393 | bitmap_iterator bi; |
394 | unsigned int i; | |
d16a5e36 DB |
395 | tree entry; |
396 | var_ann_t ta = var_ann (tag); | |
397 | ||
398 | if (!MTAG_P (tag)) | |
399 | return; | |
306219a2 DB |
400 | aliases = may_aliases (tag); |
401 | if (!aliases) | |
d16a5e36 DB |
402 | return; |
403 | ||
3b302421 | 404 | EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi) |
d16a5e36 | 405 | { |
3b302421 | 406 | entry = referenced_var (i); |
7b765bed DB |
407 | /* If you clobber one part of a structure, you |
408 | clobber the entire thing. While this does not make | |
409 | the world a particularly nice place, it is necessary | |
410 | in order to allow C/C++ tricks that involve | |
411 | pointer arithmetic to work. */ | |
412 | if (TREE_CODE (entry) == STRUCT_FIELD_TAG) | |
91fe0424 | 413 | bitmap_set_bit (queued, DECL_UID (SFT_PARENT_VAR (entry))); |
7b765bed DB |
414 | else if (!unmodifiable_var_p (entry)) |
415 | { | |
416 | add_to_worklist (entry, worklist, worklist2, ta->escape_mask, | |
417 | on_worklist); | |
d16a5e36 DB |
418 | mark_call_clobbered (entry, ta->escape_mask); |
419 | } | |
420 | } | |
91fe0424 RG |
421 | if (!bitmap_empty_p (queued)) |
422 | { | |
3b302421 | 423 | EXECUTE_IF_SET_IN_BITMAP (queued, 0, i, bi) |
91fe0424 | 424 | { |
3b302421 | 425 | subvar_t svars = get_subvars_for_var (referenced_var (i)); |
eee717aa RG |
426 | unsigned int i; |
427 | tree subvar; | |
428 | ||
429 | for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i) | |
430 | if (!unmodifiable_var_p (subvar)) | |
431 | mark_call_clobbered (subvar, ta->escape_mask); | |
91fe0424 RG |
432 | } |
433 | bitmap_clear (queued); | |
434 | } | |
d16a5e36 DB |
435 | } |
436 | ||
437 | /* Tags containing global vars need to be marked as global. | |
438 | Tags containing call clobbered vars need to be marked as call | |
439 | clobbered. */ | |
440 | ||
441 | static void | |
442 | compute_tag_properties (void) | |
443 | { | |
444 | referenced_var_iterator rvi; | |
445 | tree tag; | |
446 | bool changed = true; | |
447 | VEC (tree, heap) *taglist = NULL; | |
448 | ||
449 | FOR_EACH_REFERENCED_VAR (tag, rvi) | |
450 | { | |
451 | if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG) | |
452 | continue; | |
453 | VEC_safe_push (tree, heap, taglist, tag); | |
454 | } | |
455 | ||
456 | /* We sort the taglist by DECL_UID, for two reasons. | |
457 | 1. To get a sequential ordering to make the bitmap accesses | |
458 | faster. | |
459 | 2. Because of the way we compute aliases, it's more likely that | |
460 | an earlier tag is included in a later tag, and this will reduce | |
461 | the number of iterations. | |
462 | ||
463 | If we had a real tag graph, we would just topo-order it and be | |
464 | done with it. */ | |
465 | qsort (VEC_address (tree, taglist), | |
466 | VEC_length (tree, taglist), | |
467 | sizeof (tree), | |
468 | sort_tags_by_id); | |
469 | ||
470 | /* Go through each tag not marked as global, and if it aliases | |
471 | global vars, mark it global. | |
472 | ||
473 | If the tag contains call clobbered vars, mark it call | |
474 | clobbered. | |
475 | ||
476 | This loop iterates because tags may appear in the may-aliases | |
477 | list of other tags when we group. */ | |
478 | ||
479 | while (changed) | |
480 | { | |
481 | unsigned int k; | |
482 | ||
483 | changed = false; | |
484 | for (k = 0; VEC_iterate (tree, taglist, k, tag); k++) | |
485 | { | |
306219a2 | 486 | bitmap ma; |
3b302421 RG |
487 | bitmap_iterator bi; |
488 | unsigned int i; | |
d16a5e36 DB |
489 | tree entry; |
490 | bool tagcc = is_call_clobbered (tag); | |
491 | bool tagglobal = MTAG_GLOBAL (tag); | |
492 | ||
493 | if (tagcc && tagglobal) | |
494 | continue; | |
495 | ||
496 | ma = may_aliases (tag); | |
497 | if (!ma) | |
498 | continue; | |
499 | ||
3b302421 | 500 | EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi) |
d16a5e36 | 501 | { |
3b302421 | 502 | entry = referenced_var (i); |
d16a5e36 DB |
503 | /* Call clobbered entries cause the tag to be marked |
504 | call clobbered. */ | |
505 | if (!tagcc && is_call_clobbered (entry)) | |
506 | { | |
507 | mark_call_clobbered (tag, var_ann (entry)->escape_mask); | |
508 | tagcc = true; | |
509 | changed = true; | |
510 | } | |
511 | ||
512 | /* Global vars cause the tag to be marked global. */ | |
513 | if (!tagglobal && is_global_var (entry)) | |
514 | { | |
515 | MTAG_GLOBAL (tag) = true; | |
516 | changed = true; | |
517 | tagglobal = true; | |
518 | } | |
519 | ||
520 | /* Early exit once both global and cc are set, since the | |
521 | loop can't do any more than that. */ | |
522 | if (tagcc && tagglobal) | |
523 | break; | |
524 | } | |
525 | } | |
526 | } | |
527 | VEC_free (tree, heap, taglist); | |
528 | } | |
529 | ||
530 | /* Set up the initial variable clobbers and globalness. | |
531 | When this function completes, only tags whose aliases need to be | |
532 | clobbered will be set clobbered. Tags clobbered because they | |
533 | contain call clobbered vars are handled in compute_tag_properties. */ | |
534 | ||
535 | static void | |
536 | set_initial_properties (struct alias_info *ai) | |
537 | { | |
538 | unsigned int i; | |
539 | referenced_var_iterator rvi; | |
540 | tree var; | |
d96f49bf | 541 | tree ptr; |
91fe0424 RG |
542 | bitmap queued; |
543 | ||
544 | /* Temporary bitmap to avoid quadratic behavior in marking | |
545 | call clobbers. */ | |
546 | queued = BITMAP_ALLOC (&alias_bitmap_obstack); | |
d16a5e36 DB |
547 | |
548 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
549 | { | |
550 | if (is_global_var (var) | |
551 | && (!var_can_have_subvars (var) | |
552 | || get_subvars_for_var (var) == NULL)) | |
553 | { | |
554 | if (!unmodifiable_var_p (var)) | |
555 | mark_call_clobbered (var, ESCAPE_IS_GLOBAL); | |
556 | } | |
557 | else if (TREE_CODE (var) == PARM_DECL | |
5cd4ec7f | 558 | && gimple_default_def (cfun, var) |
d16a5e36 DB |
559 | && POINTER_TYPE_P (TREE_TYPE (var))) |
560 | { | |
5cd4ec7f | 561 | tree def = gimple_default_def (cfun, var); |
d16a5e36 DB |
562 | get_ptr_info (def)->value_escapes_p = 1; |
563 | get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM; | |
564 | } | |
565 | } | |
566 | ||
d96f49bf | 567 | for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) |
d16a5e36 | 568 | { |
d16a5e36 | 569 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
38635499 | 570 | tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr)); |
d16a5e36 DB |
571 | |
572 | if (pi->value_escapes_p) | |
573 | { | |
574 | /* If PTR escapes then its associated memory tags and | |
575 | pointed-to variables are call-clobbered. */ | |
576 | if (pi->name_mem_tag) | |
577 | mark_call_clobbered (pi->name_mem_tag, pi->escape_mask); | |
578 | ||
38635499 DN |
579 | if (tag) |
580 | mark_call_clobbered (tag, pi->escape_mask); | |
d16a5e36 DB |
581 | |
582 | if (pi->pt_vars) | |
583 | { | |
3b302421 RG |
584 | bitmap_iterator bi; |
585 | unsigned int j; | |
586 | EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi) | |
7b765bed | 587 | { |
3b302421 RG |
588 | tree alias = referenced_var (j); |
589 | ||
7b765bed DB |
590 | /* If you clobber one part of a structure, you |
591 | clobber the entire thing. While this does not make | |
592 | the world a particularly nice place, it is necessary | |
593 | in order to allow C/C++ tricks that involve | |
594 | pointer arithmetic to work. */ | |
595 | if (TREE_CODE (alias) == STRUCT_FIELD_TAG) | |
91fe0424 RG |
596 | bitmap_set_bit (queued, DECL_UID (SFT_PARENT_VAR (alias))); |
597 | else if (!unmodifiable_var_p (alias)) | |
598 | mark_call_clobbered (alias, pi->escape_mask); | |
599 | } | |
600 | /* Process variables we need to clobber all parts of. */ | |
601 | if (!bitmap_empty_p (queued)) | |
602 | { | |
3b302421 | 603 | EXECUTE_IF_SET_IN_BITMAP (queued, 0, j, bi) |
7b765bed | 604 | { |
3b302421 | 605 | subvar_t svars = get_subvars_for_var (referenced_var (j)); |
eee717aa RG |
606 | unsigned int i; |
607 | tree subvar; | |
608 | ||
609 | for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i) | |
610 | if (!unmodifiable_var_p (subvar)) | |
611 | mark_call_clobbered (subvar, pi->escape_mask); | |
7b765bed | 612 | } |
91fe0424 | 613 | bitmap_clear (queued); |
7b765bed | 614 | } |
d16a5e36 DB |
615 | } |
616 | } | |
18cd8a03 DN |
617 | |
618 | /* If the name tag is call clobbered, so is the symbol tag | |
d16a5e36 DB |
619 | associated with the base VAR_DECL. */ |
620 | if (pi->name_mem_tag | |
38635499 | 621 | && tag |
d16a5e36 | 622 | && is_call_clobbered (pi->name_mem_tag)) |
38635499 | 623 | mark_call_clobbered (tag, pi->escape_mask); |
d16a5e36 | 624 | |
18cd8a03 | 625 | /* Name tags and symbol tags that we don't know where they point |
d16a5e36 DB |
626 | to, might point to global memory, and thus, are clobbered. |
627 | ||
628 | FIXME: This is not quite right. They should only be | |
629 | clobbered if value_escapes_p is true, regardless of whether | |
630 | they point to global memory or not. | |
631 | So removing this code and fixing all the bugs would be nice. | |
632 | It is the cause of a bunch of clobbering. */ | |
633 | if ((pi->pt_global_mem || pi->pt_anything) | |
634 | && pi->is_dereferenced && pi->name_mem_tag) | |
635 | { | |
636 | mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL); | |
637 | MTAG_GLOBAL (pi->name_mem_tag) = true; | |
638 | } | |
639 | ||
640 | if ((pi->pt_global_mem || pi->pt_anything) | |
18cd8a03 | 641 | && pi->is_dereferenced |
38635499 | 642 | && tag) |
d16a5e36 | 643 | { |
38635499 DN |
644 | mark_call_clobbered (tag, ESCAPE_IS_GLOBAL); |
645 | MTAG_GLOBAL (tag) = true; | |
d16a5e36 DB |
646 | } |
647 | } | |
91fe0424 RG |
648 | |
649 | BITMAP_FREE (queued); | |
d16a5e36 DB |
650 | } |
651 | ||
652 | /* Compute which variables need to be marked call clobbered because | |
653 | their tag is call clobbered, and which tags need to be marked | |
654 | global because they contain global variables. */ | |
655 | ||
656 | static void | |
657 | compute_call_clobbered (struct alias_info *ai) | |
658 | { | |
659 | VEC (tree, heap) *worklist = NULL; | |
7b765bed | 660 | VEC (int,heap) *worklist2 = NULL; |
91fe0424 | 661 | bitmap on_worklist, queued; |
7b765bed | 662 | |
758137cd | 663 | timevar_push (TV_CALL_CLOBBER); |
7b765bed | 664 | on_worklist = BITMAP_ALLOC (NULL); |
91fe0424 | 665 | queued = BITMAP_ALLOC (NULL); |
7b765bed | 666 | |
d16a5e36 | 667 | set_initial_properties (ai); |
7b765bed | 668 | init_transitive_clobber_worklist (&worklist, &worklist2, on_worklist); |
d16a5e36 DB |
669 | while (VEC_length (tree, worklist) != 0) |
670 | { | |
671 | tree curr = VEC_pop (tree, worklist); | |
672 | int reason = VEC_pop (int, worklist2); | |
7b765bed DB |
673 | |
674 | bitmap_clear_bit (on_worklist, DECL_UID (curr)); | |
d16a5e36 | 675 | mark_call_clobbered (curr, reason); |
7b765bed | 676 | mark_aliases_call_clobbered (curr, &worklist, &worklist2, |
91fe0424 | 677 | on_worklist, queued); |
d16a5e36 DB |
678 | } |
679 | VEC_free (tree, heap, worklist); | |
680 | VEC_free (int, heap, worklist2); | |
7b765bed | 681 | BITMAP_FREE (on_worklist); |
91fe0424 | 682 | BITMAP_FREE (queued); |
d16a5e36 | 683 | compute_tag_properties (); |
758137cd | 684 | timevar_pop (TV_CALL_CLOBBER); |
d16a5e36 | 685 | } |
6de9cd9a | 686 | |
38635499 | 687 | |
e9e0aa2c DN |
688 | /* Dump memory partition information to FILE. */ |
689 | ||
690 | static void | |
691 | dump_memory_partitions (FILE *file) | |
38635499 | 692 | { |
e9e0aa2c DN |
693 | unsigned i, npart; |
694 | unsigned long nsyms; | |
695 | tree mpt; | |
38635499 | 696 | |
e9e0aa2c DN |
697 | fprintf (file, "\nMemory partitions\n\n"); |
698 | for (i = 0, npart = 0, nsyms = 0; | |
699 | VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, i, mpt); | |
700 | i++) | |
38635499 | 701 | { |
e9e0aa2c | 702 | if (mpt) |
38635499 | 703 | { |
e9e0aa2c DN |
704 | bitmap syms = MPT_SYMBOLS (mpt); |
705 | unsigned long n = (syms) ? bitmap_count_bits (syms) : 0; | |
706 | ||
707 | fprintf (file, "#%u: ", i); | |
708 | print_generic_expr (file, mpt, 0); | |
709 | fprintf (file, ": %lu elements: ", n); | |
710 | dump_decl_set (file, syms); | |
711 | npart++; | |
712 | nsyms += n; | |
38635499 | 713 | } |
38635499 | 714 | } |
e9e0aa2c DN |
715 | |
716 | fprintf (file, "\n%u memory partitions holding %lu symbols\n", npart, nsyms); | |
717 | } | |
718 | ||
719 | ||
720 | /* Dump memory partition information to stderr. */ | |
721 | ||
722 | void | |
723 | debug_memory_partitions (void) | |
724 | { | |
725 | dump_memory_partitions (stderr); | |
726 | } | |
727 | ||
728 | ||
729 | /* Return true if memory partitioning is required given the memory | |
730 | reference estimates in STATS. */ | |
731 | ||
732 | static inline bool | |
733 | need_to_partition_p (struct mem_ref_stats_d *stats) | |
734 | { | |
735 | long num_vops = stats->num_vuses + stats->num_vdefs; | |
736 | long avg_vops = CEIL (num_vops, stats->num_mem_stmts); | |
737 | return (num_vops > (long) MAX_ALIASED_VOPS | |
738 | && avg_vops > (long) AVG_ALIASED_VOPS); | |
739 | } | |
740 | ||
741 | ||
742 | /* Count the actual number of virtual operators in CFUN. Note that | |
743 | this is only meaningful after virtual operands have been populated, | |
744 | so it should be invoked at the end of compute_may_aliases. | |
745 | ||
746 | The number of virtual operators are stored in *NUM_VDEFS_P and | |
747 | *NUM_VUSES_P, the number of partitioned symbols in | |
748 | *NUM_PARTITIONED_P and the number of unpartitioned symbols in | |
749 | *NUM_UNPARTITIONED_P. | |
750 | ||
751 | If any of these pointers is NULL the corresponding count is not | |
752 | computed. */ | |
753 | ||
754 | static void | |
755 | count_mem_refs (long *num_vuses_p, long *num_vdefs_p, | |
756 | long *num_partitioned_p, long *num_unpartitioned_p) | |
757 | { | |
758 | block_stmt_iterator bsi; | |
759 | basic_block bb; | |
760 | long num_vdefs, num_vuses, num_partitioned, num_unpartitioned; | |
761 | referenced_var_iterator rvi; | |
762 | tree sym; | |
763 | ||
764 | num_vuses = num_vdefs = num_partitioned = num_unpartitioned = 0; | |
765 | ||
766 | if (num_vuses_p || num_vdefs_p) | |
767 | FOR_EACH_BB (bb) | |
768 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
769 | { | |
770 | tree stmt = bsi_stmt (bsi); | |
771 | if (stmt_references_memory_p (stmt)) | |
772 | { | |
773 | num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE); | |
774 | num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF); | |
775 | } | |
776 | } | |
777 | ||
778 | if (num_partitioned_p || num_unpartitioned_p) | |
779 | FOR_EACH_REFERENCED_VAR (sym, rvi) | |
780 | { | |
781 | if (is_gimple_reg (sym)) | |
782 | continue; | |
783 | ||
784 | if (memory_partition (sym)) | |
785 | num_partitioned++; | |
786 | else | |
787 | num_unpartitioned++; | |
788 | } | |
789 | ||
790 | if (num_vdefs_p) | |
791 | *num_vdefs_p = num_vdefs; | |
792 | ||
793 | if (num_vuses_p) | |
794 | *num_vuses_p = num_vuses; | |
795 | ||
796 | if (num_partitioned_p) | |
797 | *num_partitioned_p = num_partitioned; | |
798 | ||
799 | if (num_unpartitioned_p) | |
800 | *num_unpartitioned_p = num_unpartitioned; | |
801 | } | |
802 | ||
803 | ||
cfff829f RG |
804 | /* The list is sorted by increasing partitioning score (PSCORE). |
805 | This score is computed such that symbols with high scores are | |
806 | those that are least likely to be partitioned. Given a symbol | |
807 | MP->VAR, PSCORE(S) is the result of the following weighted sum | |
808 | ||
809 | PSCORE(S) = FW * 64 + FR * 32 | |
810 | + DW * 16 + DR * 8 | |
811 | + IW * 4 + IR * 2 | |
812 | + NO_ALIAS | |
813 | ||
814 | where | |
815 | ||
816 | FW Execution frequency of writes to S | |
817 | FR Execution frequency of reads from S | |
818 | DW Number of direct writes to S | |
819 | DR Number of direct reads from S | |
820 | IW Number of indirect writes to S | |
821 | IR Number of indirect reads from S | |
822 | NO_ALIAS State of the NO_ALIAS* flags | |
823 | ||
824 | The basic idea here is that symbols that are frequently | |
825 | written-to in hot paths of the code are the last to be considered | |
826 | for partitioning. */ | |
827 | ||
828 | static inline long | |
829 | mem_sym_score (mem_sym_stats_t mp) | |
830 | { | |
d7705551 DN |
831 | /* Unpartitionable SFTs are automatically thrown to the bottom of |
832 | the list. They are not stored in partitions, but they are used | |
833 | for computing overall statistics. */ | |
834 | if (TREE_CODE (mp->var) == STRUCT_FIELD_TAG | |
835 | && SFT_UNPARTITIONABLE_P (mp->var)) | |
836 | return LONG_MAX; | |
837 | ||
cfff829f RG |
838 | return mp->frequency_writes * 64 + mp->frequency_reads * 32 |
839 | + mp->num_direct_writes * 16 + mp->num_direct_reads * 8 | |
840 | + mp->num_indirect_writes * 4 + mp->num_indirect_reads * 2 | |
841 | + var_ann (mp->var)->noalias_state; | |
842 | } | |
843 | ||
844 | ||
e9e0aa2c DN |
845 | /* Dump memory reference stats for function CFUN to FILE. */ |
846 | ||
847 | void | |
848 | dump_mem_ref_stats (FILE *file) | |
849 | { | |
850 | long actual_num_vuses, actual_num_vdefs; | |
851 | long num_partitioned, num_unpartitioned; | |
852 | struct mem_ref_stats_d *stats; | |
853 | ||
854 | stats = gimple_mem_ref_stats (cfun); | |
855 | ||
856 | count_mem_refs (&actual_num_vuses, &actual_num_vdefs, &num_partitioned, | |
857 | &num_unpartitioned); | |
858 | ||
859 | fprintf (file, "\nMemory reference statistics for %s\n\n", | |
860 | lang_hooks.decl_printable_name (current_function_decl, 2)); | |
861 | ||
862 | fprintf (file, "Number of memory statements: %ld\n", | |
863 | stats->num_mem_stmts); | |
864 | fprintf (file, "Number of call sites: %ld\n", | |
865 | stats->num_call_sites); | |
866 | fprintf (file, "Number of pure/const call sites: %ld\n", | |
867 | stats->num_pure_const_call_sites); | |
868 | fprintf (file, "Number of asm sites: %ld\n", | |
869 | stats->num_asm_sites); | |
870 | fprintf (file, "Estimated number of loads: %ld (%ld/stmt)\n", | |
871 | stats->num_vuses, | |
872 | (stats->num_mem_stmts) | |
873 | ? CEIL (stats->num_vuses, stats->num_mem_stmts) | |
874 | : 0); | |
875 | fprintf (file, "Actual number of loads: %ld (%ld/stmt)\n", | |
876 | actual_num_vuses, | |
877 | (stats->num_mem_stmts) | |
878 | ? CEIL (actual_num_vuses, stats->num_mem_stmts) | |
879 | : 0); | |
880 | ||
881 | if (actual_num_vuses > stats->num_vuses + (stats->num_vuses / 25)) | |
882 | fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n"); | |
883 | ||
884 | fprintf (file, "Estimated number of stores: %ld (%ld/stmt)\n", | |
885 | stats->num_vdefs, | |
886 | (stats->num_mem_stmts) | |
887 | ? CEIL (stats->num_vdefs, stats->num_mem_stmts) | |
888 | : 0); | |
889 | fprintf (file, "Actual number of stores: %ld (%ld/stmt)\n", | |
890 | actual_num_vdefs, | |
891 | (stats->num_mem_stmts) | |
892 | ? CEIL (actual_num_vdefs, stats->num_mem_stmts) | |
893 | : 0); | |
894 | ||
895 | if (actual_num_vdefs > stats->num_vdefs + (stats->num_vdefs / 25)) | |
896 | fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n"); | |
897 | ||
898 | fprintf (file, "Partitioning thresholds: MAX = %d AVG = %d " | |
899 | "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS, AVG_ALIASED_VOPS, | |
0de107cf | 900 | stats->num_mem_stmts && need_to_partition_p (stats) ? "" : "NO "); |
e9e0aa2c DN |
901 | fprintf (file, "Number of partitioned symbols: %ld\n", num_partitioned); |
902 | fprintf (file, "Number of unpartitioned symbols: %ld\n", num_unpartitioned); | |
903 | } | |
904 | ||
905 | ||
906 | /* Dump memory reference stats for function FN to stderr. */ | |
907 | ||
908 | void | |
909 | debug_mem_ref_stats (void) | |
910 | { | |
911 | dump_mem_ref_stats (stderr); | |
912 | } | |
913 | ||
914 | ||
915 | /* Dump memory reference stats for variable VAR to FILE. */ | |
916 | ||
917 | static void | |
918 | dump_mem_sym_stats (FILE *file, tree var) | |
919 | { | |
920 | mem_sym_stats_t stats = mem_sym_stats (cfun, var); | |
921 | ||
922 | if (stats == NULL) | |
923 | return; | |
924 | ||
925 | fprintf (file, "read frequency: %6ld, write frequency: %6ld, " | |
926 | "direct reads: %3ld, direct writes: %3ld, " | |
927 | "indirect reads: %4ld, indirect writes: %4ld, symbol: ", | |
928 | stats->frequency_reads, stats->frequency_writes, | |
929 | stats->num_direct_reads, stats->num_direct_writes, | |
930 | stats->num_indirect_reads, stats->num_indirect_writes); | |
931 | print_generic_expr (file, stats->var, 0); | |
932 | fprintf (file, ", tags: "); | |
933 | dump_decl_set (file, stats->parent_tags); | |
934 | } | |
935 | ||
936 | ||
937 | /* Dump memory reference stats for variable VAR to stderr. */ | |
938 | ||
939 | void | |
940 | debug_mem_sym_stats (tree var) | |
941 | { | |
942 | dump_mem_sym_stats (stderr, var); | |
943 | } | |
944 | ||
cfff829f RG |
945 | /* Dump memory reference stats for variable VAR to FILE. For use |
946 | of tree-dfa.c:dump_variable. */ | |
947 | ||
948 | void | |
949 | dump_mem_sym_stats_for_var (FILE *file, tree var) | |
950 | { | |
951 | mem_sym_stats_t stats = mem_sym_stats (cfun, var); | |
952 | ||
953 | if (stats == NULL) | |
954 | return; | |
955 | ||
956 | fprintf (file, ", score: %ld", mem_sym_score (stats)); | |
957 | fprintf (file, ", direct reads: %ld", stats->num_direct_reads); | |
958 | fprintf (file, ", direct writes: %ld", stats->num_direct_writes); | |
959 | fprintf (file, ", indirect reads: %ld", stats->num_indirect_reads); | |
960 | fprintf (file, ", indirect writes: %ld", stats->num_indirect_writes); | |
961 | } | |
e9e0aa2c DN |
962 | |
963 | /* Dump memory reference stats for all memory symbols to FILE. */ | |
964 | ||
965 | static void | |
966 | dump_all_mem_sym_stats (FILE *file) | |
967 | { | |
968 | referenced_var_iterator rvi; | |
969 | tree sym; | |
970 | ||
971 | FOR_EACH_REFERENCED_VAR (sym, rvi) | |
972 | { | |
973 | if (is_gimple_reg (sym)) | |
974 | continue; | |
975 | ||
976 | dump_mem_sym_stats (file, sym); | |
977 | } | |
978 | } | |
979 | ||
980 | ||
981 | /* Dump memory reference stats for all memory symbols to stderr. */ | |
982 | ||
983 | void | |
984 | debug_all_mem_sym_stats (void) | |
985 | { | |
986 | dump_all_mem_sym_stats (stderr); | |
987 | } | |
988 | ||
989 | ||
990 | /* Dump the MP_INFO array to FILE. */ | |
991 | ||
992 | static void | |
993 | dump_mp_info (FILE *file, VEC(mem_sym_stats_t,heap) *mp_info) | |
994 | { | |
995 | unsigned i; | |
996 | mem_sym_stats_t mp_p; | |
997 | ||
998 | for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++) | |
999 | if (!mp_p->partitioned_p) | |
1000 | dump_mem_sym_stats (file, mp_p->var); | |
38635499 DN |
1001 | } |
1002 | ||
1003 | ||
1004 | /* Dump the MP_INFO array to stderr. */ | |
1005 | ||
1006 | void | |
e9e0aa2c | 1007 | debug_mp_info (VEC(mem_sym_stats_t,heap) *mp_info) |
38635499 DN |
1008 | { |
1009 | dump_mp_info (stderr, mp_info); | |
1010 | } | |
1011 | ||
1012 | ||
e9e0aa2c DN |
1013 | /* Update memory reference stats for symbol VAR in statement STMT. |
1014 | NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times | |
1015 | that VAR is read/written in STMT (indirect reads/writes are not | |
1016 | recorded by this function, see compute_memory_partitions). */ | |
38635499 | 1017 | |
e9e0aa2c DN |
1018 | void |
1019 | update_mem_sym_stats_from_stmt (tree var, tree stmt, long num_direct_reads, | |
1020 | long num_direct_writes) | |
38635499 | 1021 | { |
e9e0aa2c | 1022 | mem_sym_stats_t stats; |
38635499 | 1023 | |
e9e0aa2c DN |
1024 | gcc_assert (num_direct_reads >= 0 && num_direct_writes >= 0); |
1025 | ||
1026 | stats = get_mem_sym_stats_for (var); | |
1027 | ||
1028 | stats->num_direct_reads += num_direct_reads; | |
1029 | stats->frequency_reads += ((long) bb_for_stmt (stmt)->frequency | |
1030 | * num_direct_reads); | |
1031 | ||
1032 | stats->num_direct_writes += num_direct_writes; | |
1033 | stats->frequency_writes += ((long) bb_for_stmt (stmt)->frequency | |
1034 | * num_direct_writes); | |
1035 | } | |
1036 | ||
1037 | ||
e9e0aa2c DN |
1038 | /* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should |
1039 | be partitioned before MP2->VAR, 0 if they are the same or 1 if | |
1040 | MP1->VAR should be partitioned after MP2->VAR. */ | |
1041 | ||
1042 | static inline int | |
1043 | compare_mp_info_entries (mem_sym_stats_t mp1, mem_sym_stats_t mp2) | |
1044 | { | |
cfff829f RG |
1045 | long pscore1 = mem_sym_score (mp1); |
1046 | long pscore2 = mem_sym_score (mp2); | |
e9e0aa2c DN |
1047 | |
1048 | if (pscore1 < pscore2) | |
38635499 | 1049 | return -1; |
e9e0aa2c DN |
1050 | else if (pscore1 > pscore2) |
1051 | return 1; | |
38635499 | 1052 | else |
cfff829f | 1053 | return DECL_UID (mp1->var) - DECL_UID (mp2->var); |
38635499 DN |
1054 | } |
1055 | ||
1056 | ||
e9e0aa2c DN |
1057 | /* Comparison routine for qsort. The list is sorted by increasing |
1058 | partitioning score (PSCORE). This score is computed such that | |
1059 | symbols with high scores are those that are least likely to be | |
1060 | partitioned. */ | |
1061 | ||
1062 | static int | |
1063 | mp_info_cmp (const void *p, const void *q) | |
1064 | { | |
1065 | mem_sym_stats_t e1 = *((const mem_sym_stats_t *) p); | |
1066 | mem_sym_stats_t e2 = *((const mem_sym_stats_t *) q); | |
1067 | return compare_mp_info_entries (e1, e2); | |
1068 | } | |
1069 | ||
1070 | ||
38635499 | 1071 | /* Sort the array of reference counts used to compute memory partitions. |
e9e0aa2c DN |
1072 | Elements are sorted in ascending order of execution frequency and |
1073 | descending order of virtual operators needed. */ | |
38635499 DN |
1074 | |
1075 | static inline void | |
e9e0aa2c | 1076 | sort_mp_info (VEC(mem_sym_stats_t,heap) *list) |
38635499 | 1077 | { |
e9e0aa2c | 1078 | unsigned num = VEC_length (mem_sym_stats_t, list); |
38635499 DN |
1079 | |
1080 | if (num < 2) | |
1081 | return; | |
1082 | ||
1083 | if (num == 2) | |
1084 | { | |
e9e0aa2c DN |
1085 | if (compare_mp_info_entries (VEC_index (mem_sym_stats_t, list, 0), |
1086 | VEC_index (mem_sym_stats_t, list, 1)) > 0) | |
38635499 DN |
1087 | { |
1088 | /* Swap elements if they are in the wrong order. */ | |
e9e0aa2c DN |
1089 | mem_sym_stats_t tmp = VEC_index (mem_sym_stats_t, list, 0); |
1090 | VEC_replace (mem_sym_stats_t, list, 0, | |
1091 | VEC_index (mem_sym_stats_t, list, 1)); | |
1092 | VEC_replace (mem_sym_stats_t, list, 1, tmp); | |
38635499 DN |
1093 | } |
1094 | ||
1095 | return; | |
1096 | } | |
1097 | ||
1098 | /* There are 3 or more elements, call qsort. */ | |
e9e0aa2c DN |
1099 | qsort (VEC_address (mem_sym_stats_t, list), |
1100 | VEC_length (mem_sym_stats_t, list), | |
1101 | sizeof (mem_sym_stats_t), | |
1102 | mp_info_cmp); | |
38635499 DN |
1103 | } |
1104 | ||
1105 | ||
e9e0aa2c DN |
1106 | /* Return the memory partition tag (MPT) associated with memory |
1107 | symbol SYM. */ | |
38635499 | 1108 | |
e9e0aa2c DN |
1109 | static tree |
1110 | get_mpt_for (tree sym) | |
38635499 | 1111 | { |
e9e0aa2c | 1112 | tree mpt; |
38635499 | 1113 | |
e9e0aa2c DN |
1114 | /* Don't create a new tag unnecessarily. */ |
1115 | mpt = memory_partition (sym); | |
1116 | if (mpt == NULL_TREE) | |
38635499 | 1117 | { |
e9e0aa2c DN |
1118 | mpt = create_tag_raw (MEMORY_PARTITION_TAG, TREE_TYPE (sym), "MPT"); |
1119 | TREE_ADDRESSABLE (mpt) = 0; | |
1120 | add_referenced_var (mpt); | |
1121 | VEC_safe_push (tree, heap, gimple_ssa_operands (cfun)->mpt_table, mpt); | |
1122 | gcc_assert (MPT_SYMBOLS (mpt) == NULL); | |
1123 | set_memory_partition (sym, mpt); | |
1124 | } | |
38635499 | 1125 | |
e9e0aa2c DN |
1126 | return mpt; |
1127 | } | |
38635499 | 1128 | |
38635499 | 1129 | |
e9e0aa2c | 1130 | /* Add MP_P->VAR to a memory partition and return the partition. */ |
38635499 | 1131 | |
e9e0aa2c DN |
1132 | static tree |
1133 | find_partition_for (mem_sym_stats_t mp_p) | |
1134 | { | |
1135 | unsigned i; | |
1136 | VEC(tree,heap) *mpt_table; | |
1137 | tree mpt; | |
38635499 | 1138 | |
e9e0aa2c DN |
1139 | mpt_table = gimple_ssa_operands (cfun)->mpt_table; |
1140 | mpt = NULL_TREE; | |
38635499 | 1141 | |
e9e0aa2c DN |
1142 | /* Find an existing partition for MP_P->VAR. */ |
1143 | for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++) | |
38635499 | 1144 | { |
e9e0aa2c | 1145 | mem_sym_stats_t mpt_stats; |
38635499 | 1146 | |
e9e0aa2c DN |
1147 | /* If MPT does not have any symbols yet, use it. */ |
1148 | if (MPT_SYMBOLS (mpt) == NULL) | |
1149 | break; | |
38635499 | 1150 | |
e9e0aa2c DN |
1151 | /* Otherwise, see if MPT has common parent tags with MP_P->VAR, |
1152 | but avoid grouping clobbered variables with non-clobbered | |
1153 | variables (otherwise, this tends to creates a single memory | |
1154 | partition because other call-clobbered variables may have | |
1155 | common parent tags with non-clobbered ones). */ | |
1156 | mpt_stats = get_mem_sym_stats_for (mpt); | |
1157 | if (mp_p->parent_tags | |
1158 | && mpt_stats->parent_tags | |
1159 | && is_call_clobbered (mpt) == is_call_clobbered (mp_p->var) | |
1160 | && bitmap_intersect_p (mpt_stats->parent_tags, mp_p->parent_tags)) | |
1161 | break; | |
1162 | ||
1163 | /* If no common parent tags are found, see if both MPT and | |
1164 | MP_P->VAR are call-clobbered. */ | |
1165 | if (is_call_clobbered (mpt) && is_call_clobbered (mp_p->var)) | |
1166 | break; | |
1167 | } | |
38635499 | 1168 | |
e9e0aa2c DN |
1169 | if (mpt == NULL_TREE) |
1170 | mpt = get_mpt_for (mp_p->var); | |
1171 | else | |
1172 | set_memory_partition (mp_p->var, mpt); | |
38635499 | 1173 | |
e9e0aa2c | 1174 | mp_p->partitioned_p = true; |
38635499 | 1175 | |
e9e0aa2c DN |
1176 | mark_sym_for_renaming (mp_p->var); |
1177 | mark_sym_for_renaming (mpt); | |
1178 | ||
1179 | return mpt; | |
38635499 DN |
1180 | } |
1181 | ||
1182 | ||
1183 | /* Rewrite the alias set for TAG to use the newly created partitions. | |
1184 | If TAG is NULL, rewrite the set of call-clobbered variables. | |
1185 | NEW_ALIASES is a scratch bitmap to build the new set of aliases for | |
1186 | TAG. */ | |
1187 | ||
1188 | static void | |
1189 | rewrite_alias_set_for (tree tag, bitmap new_aliases) | |
1190 | { | |
3b302421 RG |
1191 | bitmap_iterator bi; |
1192 | unsigned i; | |
38635499 DN |
1193 | tree mpt, sym; |
1194 | ||
3b302421 | 1195 | EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi) |
38635499 | 1196 | { |
3b302421 | 1197 | sym = referenced_var (i); |
e9e0aa2c DN |
1198 | mpt = memory_partition (sym); |
1199 | if (mpt) | |
1200 | bitmap_set_bit (new_aliases, DECL_UID (mpt)); | |
1201 | else | |
1202 | bitmap_set_bit (new_aliases, DECL_UID (sym)); | |
38635499 | 1203 | } |
e9e0aa2c DN |
1204 | |
1205 | /* Rebuild the may-alias array for TAG. */ | |
1206 | bitmap_copy (MTAG_ALIASES (tag), new_aliases); | |
1207 | } | |
1208 | ||
1209 | ||
1210 | /* Determine how many virtual operands can be saved by partitioning | |
1211 | MP_P->VAR into MPT. When a symbol S is thrown inside a partition | |
1212 | P, every virtual operand that used to reference S will now | |
1213 | reference P. Whether it reduces the number of virtual operands | |
1214 | depends on: | |
1215 | ||
1216 | 1- Direct references to S are never saved. Instead of the virtual | |
1217 | operand to S, we will now have a virtual operand to P. | |
1218 | ||
1219 | 2- Indirect references to S are reduced only for those memory tags | |
1220 | holding S that already had other symbols partitioned into P. | |
1221 | For instance, if a memory tag T has the alias set { a b S c }, | |
1222 | the first time we partition S into P, the alias set will become | |
1223 | { a b P c }, so no virtual operands will be saved. However, if | |
1224 | we now partition symbol 'c' into P, then the alias set for T | |
1225 | will become { a b P }, so we will be saving one virtual operand | |
1226 | for every indirect reference to 'c'. | |
1227 | ||
1228 | 3- Is S is call-clobbered, we save as many virtual operands as | |
1229 | call/asm sites exist in the code, but only if other | |
1230 | call-clobbered symbols have been grouped into P. The first | |
1231 | call-clobbered symbol that we group does not produce any | |
1232 | savings. | |
1233 | ||
1234 | MEM_REF_STATS points to CFUN's memory reference information. */ | |
1235 | ||
1236 | static void | |
1237 | estimate_vop_reduction (struct mem_ref_stats_d *mem_ref_stats, | |
1238 | mem_sym_stats_t mp_p, tree mpt) | |
1239 | { | |
1240 | unsigned i; | |
1241 | bitmap_iterator bi; | |
1242 | mem_sym_stats_t mpt_stats; | |
1243 | ||
1244 | /* We should only get symbols with indirect references here. */ | |
1245 | gcc_assert (mp_p->num_indirect_reads > 0 || mp_p->num_indirect_writes > 0); | |
1246 | ||
1247 | /* Note that the only statistics we keep for MPT is the set of | |
1248 | parent tags to know which memory tags have had alias members | |
1249 | partitioned, and the indicator has_call_clobbered_vars. | |
1250 | Reference counts are not important for MPT. */ | |
1251 | mpt_stats = get_mem_sym_stats_for (mpt); | |
1252 | ||
1253 | /* Traverse all the parent tags for MP_P->VAR. For every tag T, if | |
1254 | partition P is already grouping aliases of T, then reduce the | |
1255 | number of virtual operands by the number of direct references | |
1256 | to T. */ | |
1257 | if (mp_p->parent_tags) | |
38635499 | 1258 | { |
e9e0aa2c DN |
1259 | if (mpt_stats->parent_tags == NULL) |
1260 | mpt_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack); | |
38635499 | 1261 | |
e9e0aa2c | 1262 | EXECUTE_IF_SET_IN_BITMAP (mp_p->parent_tags, 0, i, bi) |
38635499 | 1263 | { |
e9e0aa2c DN |
1264 | if (bitmap_bit_p (mpt_stats->parent_tags, i)) |
1265 | { | |
1266 | /* Partition MPT is already partitioning symbols in the | |
1267 | alias set for TAG. This means that we are now saving | |
1268 | 1 virtual operand for every direct reference to TAG. */ | |
1269 | tree tag = referenced_var (i); | |
1270 | mem_sym_stats_t tag_stats = mem_sym_stats (cfun, tag); | |
1271 | mem_ref_stats->num_vuses -= tag_stats->num_direct_reads; | |
1272 | mem_ref_stats->num_vdefs -= tag_stats->num_direct_writes; | |
1273 | } | |
38635499 | 1274 | else |
e9e0aa2c DN |
1275 | { |
1276 | /* This is the first symbol in tag I's alias set that is | |
1277 | being grouped under MPT. We will not save any | |
1278 | virtual operands this time, but record that MPT is | |
1279 | grouping a symbol from TAG's alias set so that the | |
1280 | next time we get the savings. */ | |
1281 | bitmap_set_bit (mpt_stats->parent_tags, i); | |
1282 | } | |
38635499 | 1283 | } |
e9e0aa2c | 1284 | } |
38635499 | 1285 | |
e9e0aa2c DN |
1286 | /* If MP_P->VAR is call-clobbered, and MPT is already grouping |
1287 | call-clobbered symbols, then we will save as many virtual | |
1288 | operands as asm/call sites there are. */ | |
1289 | if (is_call_clobbered (mp_p->var)) | |
1290 | { | |
1291 | if (mpt_stats->has_call_clobbered_vars) | |
1292 | mem_ref_stats->num_vdefs -= mem_ref_stats->num_call_sites | |
1293 | + mem_ref_stats->num_asm_sites; | |
1294 | else | |
1295 | mpt_stats->has_call_clobbered_vars = true; | |
38635499 DN |
1296 | } |
1297 | } | |
1298 | ||
1299 | ||
e9e0aa2c DN |
1300 | /* Helper for compute_memory_partitions. Transfer reference counts |
1301 | from pointers to their pointed-to sets. Counters for pointers were | |
1302 | computed by update_alias_info. MEM_REF_STATS points to CFUN's | |
1303 | memory reference information. */ | |
38635499 DN |
1304 | |
1305 | static void | |
e9e0aa2c | 1306 | update_reference_counts (struct mem_ref_stats_d *mem_ref_stats) |
38635499 | 1307 | { |
3b302421 RG |
1308 | unsigned i; |
1309 | bitmap_iterator bi; | |
e9e0aa2c | 1310 | mem_sym_stats_t sym_stats; |
38635499 | 1311 | |
e9e0aa2c DN |
1312 | for (i = 1; i < num_ssa_names; i++) |
1313 | { | |
1314 | tree ptr; | |
1315 | struct ptr_info_def *pi; | |
38635499 | 1316 | |
e9e0aa2c DN |
1317 | ptr = ssa_name (i); |
1318 | if (ptr | |
1319 | && POINTER_TYPE_P (TREE_TYPE (ptr)) | |
1320 | && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL | |
1321 | && pi->is_dereferenced) | |
1322 | { | |
3b302421 RG |
1323 | unsigned j; |
1324 | bitmap_iterator bj; | |
1325 | tree tag; | |
e9e0aa2c DN |
1326 | mem_sym_stats_t ptr_stats, tag_stats; |
1327 | ||
1328 | /* If PTR has flow-sensitive points-to information, use | |
1329 | PTR's name tag, otherwise use the symbol tag associated | |
1330 | with PTR's symbol. */ | |
1331 | if (pi->name_mem_tag) | |
1332 | tag = pi->name_mem_tag; | |
1333 | else | |
1334 | tag = symbol_mem_tag (SSA_NAME_VAR (ptr)); | |
1335 | ||
1336 | ptr_stats = get_mem_sym_stats_for (ptr); | |
1337 | tag_stats = get_mem_sym_stats_for (tag); | |
1338 | ||
1339 | /* TAG has as many direct references as dereferences we | |
1340 | found for its parent pointer. */ | |
1341 | tag_stats->num_direct_reads += ptr_stats->num_direct_reads; | |
1342 | tag_stats->num_direct_writes += ptr_stats->num_direct_writes; | |
1343 | ||
1344 | /* All the dereferences of pointer PTR are considered direct | |
1345 | references to PTR's memory tag (TAG). In turn, | |
1346 | references to TAG will become virtual operands for every | |
1347 | symbol in TAG's alias set. So, for every symbol ALIAS in | |
1348 | TAG's alias set, add as many indirect references to ALIAS | |
1349 | as direct references there are for TAG. */ | |
1350 | if (MTAG_ALIASES (tag)) | |
3b302421 | 1351 | EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, j, bj) |
e9e0aa2c | 1352 | { |
3b302421 | 1353 | tree alias = referenced_var (j); |
e9e0aa2c DN |
1354 | sym_stats = get_mem_sym_stats_for (alias); |
1355 | ||
1356 | /* All the direct references to TAG are indirect references | |
1357 | to ALIAS. */ | |
1358 | sym_stats->num_indirect_reads += ptr_stats->num_direct_reads; | |
1359 | sym_stats->num_indirect_writes += ptr_stats->num_direct_writes; | |
1360 | sym_stats->frequency_reads += ptr_stats->frequency_reads; | |
1361 | sym_stats->frequency_writes += ptr_stats->frequency_writes; | |
1362 | ||
1363 | /* Indicate that TAG is one of ALIAS's parent tags. */ | |
1364 | if (sym_stats->parent_tags == NULL) | |
1365 | sym_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack); | |
1366 | bitmap_set_bit (sym_stats->parent_tags, DECL_UID (tag)); | |
1367 | } | |
1368 | } | |
1369 | } | |
38635499 | 1370 | |
e9e0aa2c DN |
1371 | /* Call-clobbered symbols are indirectly written at every |
1372 | call/asm site. */ | |
3b302421 | 1373 | EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi) |
38635499 | 1374 | { |
3b302421 | 1375 | tree sym = referenced_var (i); |
e9e0aa2c DN |
1376 | sym_stats = get_mem_sym_stats_for (sym); |
1377 | sym_stats->num_indirect_writes += mem_ref_stats->num_call_sites | |
1378 | + mem_ref_stats->num_asm_sites; | |
38635499 DN |
1379 | } |
1380 | ||
e9e0aa2c DN |
1381 | /* Addressable symbols are indirectly written at some ASM sites. |
1382 | Since only ASM sites that clobber memory actually affect | |
1383 | addressable symbols, this is an over-estimation. */ | |
3b302421 | 1384 | EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi) |
e9e0aa2c | 1385 | { |
3b302421 | 1386 | tree sym = referenced_var (i); |
e9e0aa2c DN |
1387 | sym_stats = get_mem_sym_stats_for (sym); |
1388 | sym_stats->num_indirect_writes += mem_ref_stats->num_asm_sites; | |
1389 | } | |
1390 | } | |
1391 | ||
1392 | ||
1393 | /* Helper for compute_memory_partitions. Add all memory symbols to | |
1394 | *MP_INFO_P and compute the initial estimate for the total number of | |
1395 | virtual operands needed. MEM_REF_STATS points to CFUN's memory | |
1396 | reference information. On exit, *TAGS_P will contain the list of | |
1397 | memory tags whose alias set need to be rewritten after | |
1398 | partitioning. */ | |
1399 | ||
1400 | static void | |
1401 | build_mp_info (struct mem_ref_stats_d *mem_ref_stats, | |
d7705551 DN |
1402 | VEC(mem_sym_stats_t,heap) **mp_info_p, |
1403 | VEC(tree,heap) **tags_p) | |
e9e0aa2c DN |
1404 | { |
1405 | tree var; | |
1406 | referenced_var_iterator rvi; | |
1407 | ||
38635499 DN |
1408 | FOR_EACH_REFERENCED_VAR (var, rvi) |
1409 | { | |
e9e0aa2c DN |
1410 | mem_sym_stats_t sym_stats; |
1411 | tree old_mpt; | |
1412 | ||
1413 | /* We are only interested in memory symbols other than MPTs. */ | |
1414 | if (is_gimple_reg (var) || TREE_CODE (var) == MEMORY_PARTITION_TAG) | |
38635499 DN |
1415 | continue; |
1416 | ||
e9e0aa2c DN |
1417 | /* Collect memory tags into the TAGS array so that we can |
1418 | rewrite their alias sets after partitioning. */ | |
1419 | if (MTAG_P (var) && MTAG_ALIASES (var)) | |
1420 | VEC_safe_push (tree, heap, *tags_p, var); | |
38635499 | 1421 | |
e9e0aa2c DN |
1422 | /* Since we are going to re-compute partitions, any symbols that |
1423 | used to belong to a partition must be detached from it and | |
1424 | marked for renaming. */ | |
1425 | if ((old_mpt = memory_partition (var)) != NULL) | |
1426 | { | |
1427 | mark_sym_for_renaming (old_mpt); | |
1428 | set_memory_partition (var, NULL_TREE); | |
1429 | mark_sym_for_renaming (var); | |
1430 | } | |
38635499 | 1431 | |
e9e0aa2c DN |
1432 | sym_stats = get_mem_sym_stats_for (var); |
1433 | ||
1434 | /* Add VAR's reference info to MP_INFO. Note that the only | |
1435 | symbols that make sense to partition are those that have | |
1436 | indirect references. If a symbol S is always directly | |
1437 | referenced, partitioning it will not reduce the number of | |
1438 | virtual operators. The only symbols that are profitable to | |
1439 | partition are those that belong to alias sets and/or are | |
1440 | call-clobbered. */ | |
1441 | if (sym_stats->num_indirect_reads > 0 | |
1442 | || sym_stats->num_indirect_writes > 0) | |
1443 | VEC_safe_push (mem_sym_stats_t, heap, *mp_info_p, sym_stats); | |
1444 | ||
1445 | /* Update the number of estimated VOPS. Note that direct | |
1446 | references to memory tags are always counted as indirect | |
1447 | references to their alias set members, so if a memory tag has | |
1448 | aliases, do not count its direct references to avoid double | |
1449 | accounting. */ | |
1450 | if (!MTAG_P (var) || !MTAG_ALIASES (var)) | |
1451 | { | |
1452 | mem_ref_stats->num_vuses += sym_stats->num_direct_reads; | |
1453 | mem_ref_stats->num_vdefs += sym_stats->num_direct_writes; | |
1454 | } | |
38635499 | 1455 | |
e9e0aa2c DN |
1456 | mem_ref_stats->num_vuses += sym_stats->num_indirect_reads; |
1457 | mem_ref_stats->num_vdefs += sym_stats->num_indirect_writes; | |
38635499 | 1458 | } |
e9e0aa2c | 1459 | } |
38635499 | 1460 | |
e9e0aa2c DN |
1461 | |
1462 | /* Compute memory partitions. A memory partition (MPT) is an | |
1463 | arbitrary grouping of memory symbols, such that references to one | |
1464 | member of the group is considered a reference to all the members of | |
1465 | the group. | |
1466 | ||
1467 | As opposed to alias sets in memory tags, the grouping into | |
1468 | partitions is completely arbitrary and only done to reduce the | |
1469 | number of virtual operands. The only rule that needs to be | |
1470 | observed when creating memory partitions is that given two memory | |
1471 | partitions MPT.i and MPT.j, they must not contain symbols in | |
1472 | common. | |
1473 | ||
1474 | Memory partitions are used when putting the program into Memory-SSA | |
1475 | form. In particular, in Memory-SSA PHI nodes are not computed for | |
1476 | individual memory symbols. They are computed for memory | |
1477 | partitions. This reduces the amount of PHI nodes in the SSA graph | |
1478 | at the expense of precision (i.e., it makes unrelated stores affect | |
1479 | each other). | |
1480 | ||
1481 | However, it is possible to increase precision by changing this | |
1482 | partitioning scheme. For instance, if the partitioning scheme is | |
1483 | such that get_mpt_for is the identity function (that is, | |
1484 | get_mpt_for (s) = s), this will result in ultimate precision at the | |
1485 | expense of huge SSA webs. | |
1486 | ||
1487 | At the other extreme, a partitioning scheme that groups all the | |
1488 | symbols in the same set results in minimal SSA webs and almost | |
1489 | total loss of precision. | |
1490 | ||
1491 | There partitioning heuristic uses three parameters to decide the | |
1492 | order in which symbols are processed. The list of symbols is | |
1493 | sorted so that symbols that are more likely to be partitioned are | |
1494 | near the top of the list: | |
1495 | ||
1496 | - Execution frequency. If a memory references is in a frequently | |
1497 | executed code path, grouping it into a partition may block useful | |
1498 | transformations and cause sub-optimal code generation. So, the | |
1499 | partition heuristic tries to avoid grouping symbols with high | |
1500 | execution frequency scores. Execution frequency is taken | |
1501 | directly from the basic blocks where every reference is made (see | |
1502 | update_mem_sym_stats_from_stmt), which in turn uses the | |
1503 | profile guided machinery, so if the program is compiled with PGO | |
1504 | enabled, more accurate partitioning decisions will be made. | |
1505 | ||
1506 | - Number of references. Symbols with few references in the code, | |
1507 | are partitioned before symbols with many references. | |
1508 | ||
1509 | - NO_ALIAS attributes. Symbols with any of the NO_ALIAS* | |
1510 | attributes are partitioned after symbols marked MAY_ALIAS. | |
1511 | ||
1512 | Once the list is sorted, the partitioning proceeds as follows: | |
1513 | ||
1514 | 1- For every symbol S in MP_INFO, create a new memory partition MP, | |
1515 | if necessary. To avoid memory partitions that contain symbols | |
1516 | from non-conflicting alias sets, memory partitions are | |
1517 | associated to the memory tag that holds S in its alias set. So, | |
1518 | when looking for a memory partition for S, the memory partition | |
1519 | associated with one of the memory tags holding S is chosen. If | |
1520 | none exists, a new one is created. | |
1521 | ||
1522 | 2- Add S to memory partition MP. | |
1523 | ||
1524 | 3- Reduce by 1 the number of VOPS for every memory tag holding S. | |
1525 | ||
1526 | 4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the | |
1527 | average number of VOPS per statement is less than | |
1528 | AVG_ALIASED_VOPS, stop. Otherwise, go to the next symbol in the | |
1529 | list. */ | |
1530 | ||
1531 | static void | |
1532 | compute_memory_partitions (void) | |
1533 | { | |
1534 | tree tag; | |
1535 | unsigned i; | |
1536 | mem_sym_stats_t mp_p; | |
1537 | VEC(mem_sym_stats_t,heap) *mp_info; | |
1538 | bitmap new_aliases; | |
1539 | VEC(tree,heap) *tags; | |
1540 | struct mem_ref_stats_d *mem_ref_stats; | |
1541 | int prev_max_aliased_vops; | |
1542 | ||
1543 | mem_ref_stats = gimple_mem_ref_stats (cfun); | |
1544 | gcc_assert (mem_ref_stats->num_vuses == 0 && mem_ref_stats->num_vdefs == 0); | |
1545 | ||
1546 | if (mem_ref_stats->num_mem_stmts == 0) | |
1547 | return; | |
1548 | ||
1549 | timevar_push (TV_MEMORY_PARTITIONING); | |
1550 | ||
1551 | mp_info = NULL; | |
1552 | tags = NULL; | |
1553 | prev_max_aliased_vops = MAX_ALIASED_VOPS; | |
1554 | ||
1555 | /* Since we clearly cannot lower the number of virtual operators | |
1556 | below the total number of memory statements in the function, we | |
1557 | may need to adjust MAX_ALIASED_VOPS beforehand. */ | |
1558 | if (MAX_ALIASED_VOPS < mem_ref_stats->num_mem_stmts) | |
1559 | MAX_ALIASED_VOPS = mem_ref_stats->num_mem_stmts; | |
1560 | ||
1561 | /* Update reference stats for all the pointed-to variables and | |
1562 | memory tags. */ | |
1563 | update_reference_counts (mem_ref_stats); | |
1564 | ||
1565 | /* Add all the memory symbols to MP_INFO. */ | |
1566 | build_mp_info (mem_ref_stats, &mp_info, &tags); | |
38635499 DN |
1567 | |
1568 | /* No partitions required if we are below the threshold. */ | |
e9e0aa2c DN |
1569 | if (!need_to_partition_p (mem_ref_stats)) |
1570 | { | |
1571 | if (dump_file) | |
1572 | fprintf (dump_file, "\nMemory partitioning NOT NEEDED for %s\n", | |
1573 | get_name (current_function_decl)); | |
1574 | goto done; | |
1575 | } | |
38635499 | 1576 | |
e9e0aa2c DN |
1577 | /* Sort the MP_INFO array so that symbols that should be partitioned |
1578 | first are near the top of the list. */ | |
38635499 DN |
1579 | sort_mp_info (mp_info); |
1580 | ||
1581 | if (dump_file) | |
1582 | { | |
e9e0aa2c DN |
1583 | fprintf (dump_file, "\nMemory partitioning NEEDED for %s\n\n", |
1584 | get_name (current_function_decl)); | |
1585 | fprintf (dump_file, "Memory symbol references before partitioning:\n"); | |
38635499 DN |
1586 | dump_mp_info (dump_file, mp_info); |
1587 | } | |
1588 | ||
e9e0aa2c DN |
1589 | /* Create partitions for variables in MP_INFO until we have enough |
1590 | to lower the total number of VOPS below MAX_ALIASED_VOPS or if | |
1591 | the average number of VOPS per statement is below | |
1592 | AVG_ALIASED_VOPS. */ | |
1593 | for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++) | |
38635499 | 1594 | { |
e9e0aa2c DN |
1595 | tree mpt; |
1596 | ||
1597 | /* If we are below the threshold, stop. */ | |
1598 | if (!need_to_partition_p (mem_ref_stats)) | |
38635499 DN |
1599 | break; |
1600 | ||
d7705551 DN |
1601 | /* SFTs that are marked unpartitionable should not be added to |
1602 | partitions. These SFTs are special because they mark the | |
1603 | first SFT into a structure where a pointer is pointing to. | |
1604 | This is needed by the operand scanner to find adjacent | |
1605 | fields. See add_vars_for_offset for details. */ | |
1606 | if (TREE_CODE (mp_p->var) == STRUCT_FIELD_TAG | |
1607 | && SFT_UNPARTITIONABLE_P (mp_p->var)) | |
1608 | continue; | |
1609 | ||
e9e0aa2c DN |
1610 | mpt = find_partition_for (mp_p); |
1611 | estimate_vop_reduction (mem_ref_stats, mp_p, mpt); | |
38635499 DN |
1612 | } |
1613 | ||
1614 | /* After partitions have been created, rewrite alias sets to use | |
1615 | them instead of the original symbols. This way, if the alias set | |
1616 | was computed as { a b c d e f }, and the subset { b e f } was | |
1617 | grouped into partition MPT.3, then the new alias set for the tag | |
e9e0aa2c DN |
1618 | will be { a c d MPT.3 }. |
1619 | ||
1620 | Note that this is not strictly necessary. The operand scanner | |
1621 | will always check if a symbol belongs to a partition when adding | |
1622 | virtual operands. However, by reducing the size of the alias | |
1623 | sets to be scanned, the work needed inside the operand scanner is | |
1624 | significantly reduced. */ | |
bbe984fb | 1625 | new_aliases = BITMAP_ALLOC (&alias_bitmap_obstack); |
38635499 | 1626 | |
e9e0aa2c | 1627 | for (i = 0; VEC_iterate (tree, tags, i, tag); i++) |
38635499 | 1628 | { |
e9e0aa2c | 1629 | rewrite_alias_set_for (tag, new_aliases); |
38635499 DN |
1630 | bitmap_clear (new_aliases); |
1631 | } | |
1632 | ||
1633 | BITMAP_FREE (new_aliases); | |
1634 | ||
1635 | if (dump_file) | |
1636 | { | |
e9e0aa2c | 1637 | fprintf (dump_file, "\nMemory symbol references after partitioning:\n"); |
38635499 DN |
1638 | dump_mp_info (dump_file, mp_info); |
1639 | } | |
1640 | ||
1641 | done: | |
1642 | /* Free allocated memory. */ | |
e9e0aa2c DN |
1643 | VEC_free (mem_sym_stats_t, heap, mp_info); |
1644 | VEC_free (tree, heap, tags); | |
1645 | ||
1646 | MAX_ALIASED_VOPS = prev_max_aliased_vops; | |
38635499 DN |
1647 | |
1648 | timevar_pop (TV_MEMORY_PARTITIONING); | |
1649 | } | |
1650 | ||
1651 | ||
6de9cd9a DN |
1652 | /* Compute may-alias information for every variable referenced in function |
1653 | FNDECL. | |
1654 | ||
1655 | Alias analysis proceeds in 3 main phases: | |
1656 | ||
1657 | 1- Points-to and escape analysis. | |
1658 | ||
1659 | This phase walks the use-def chains in the SSA web looking for three | |
1660 | things: | |
1661 | ||
1662 | * Assignments of the form P_i = &VAR | |
1663 | * Assignments of the form P_i = malloc() | |
1664 | * Pointers and ADDR_EXPR that escape the current function. | |
1665 | ||
1666 | The concept of 'escaping' is the same one used in the Java world. When | |
1667 | a pointer or an ADDR_EXPR escapes, it means that it has been exposed | |
1668 | outside of the current function. So, assignment to global variables, | |
406eab99 RK |
1669 | function arguments and returning a pointer are all escape sites, as are |
1670 | conversions between pointers and integers. | |
6de9cd9a DN |
1671 | |
1672 | This is where we are currently limited. Since not everything is renamed | |
1673 | into SSA, we lose track of escape properties when a pointer is stashed | |
1674 | inside a field in a structure, for instance. In those cases, we are | |
1675 | assuming that the pointer does escape. | |
1676 | ||
1677 | We use escape analysis to determine whether a variable is | |
1678 | call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable | |
1679 | is call-clobbered. If a pointer P_i escapes, then all the variables | |
1680 | pointed-to by P_i (and its memory tag) also escape. | |
1681 | ||
1682 | 2- Compute flow-sensitive aliases | |
1683 | ||
1684 | We have two classes of memory tags. Memory tags associated with the | |
1685 | pointed-to data type of the pointers in the program. These tags are | |
18cd8a03 | 1686 | called "symbol memory tag" (SMT). The other class are those associated |
6de9cd9a DN |
1687 | with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that |
1688 | when adding operands for an INDIRECT_REF *P_i, we will first check | |
1689 | whether P_i has a name tag, if it does we use it, because that will have | |
18cd8a03 | 1690 | more precise aliasing information. Otherwise, we use the standard symbol |
6de9cd9a DN |
1691 | tag. |
1692 | ||
1693 | In this phase, we go through all the pointers we found in points-to | |
1694 | analysis and create alias sets for the name memory tags associated with | |
1695 | each pointer P_i. If P_i escapes, we mark call-clobbered the variables | |
1696 | it points to and its tag. | |
1697 | ||
1698 | ||
1699 | 3- Compute flow-insensitive aliases | |
1700 | ||
18cd8a03 DN |
1701 | This pass will compare the alias set of every symbol memory tag and |
1702 | every addressable variable found in the program. Given a symbol | |
1703 | memory tag SMT and an addressable variable V. If the alias sets of | |
1704 | SMT and V conflict (as computed by may_alias_p), then V is marked | |
1705 | as an alias tag and added to the alias set of SMT. | |
6de9cd9a DN |
1706 | |
1707 | For instance, consider the following function: | |
1708 | ||
1709 | foo (int i) | |
1710 | { | |
4244df06 | 1711 | int *p, a, b; |
6de9cd9a DN |
1712 | |
1713 | if (i > 10) | |
1714 | p = &a; | |
1715 | else | |
4244df06 | 1716 | p = &b; |
6de9cd9a DN |
1717 | |
1718 | *p = 3; | |
6de9cd9a DN |
1719 | a = b + 2; |
1720 | return *p; | |
1721 | } | |
1722 | ||
18cd8a03 | 1723 | After aliasing analysis has finished, the symbol memory tag for pointer |
6de9cd9a DN |
1724 | 'p' will have two aliases, namely variables 'a' and 'b'. Every time |
1725 | pointer 'p' is dereferenced, we want to mark the operation as a | |
1726 | potential reference to 'a' and 'b'. | |
1727 | ||
1728 | foo (int i) | |
1729 | { | |
1730 | int *p, a, b; | |
1731 | ||
1732 | if (i_2 > 10) | |
1733 | p_4 = &a; | |
1734 | else | |
1735 | p_6 = &b; | |
1736 | # p_1 = PHI <p_4(1), p_6(2)>; | |
1737 | ||
38635499 DN |
1738 | # a_7 = VDEF <a_3>; |
1739 | # b_8 = VDEF <b_5>; | |
6de9cd9a DN |
1740 | *p_1 = 3; |
1741 | ||
38635499 | 1742 | # a_9 = VDEF <a_7> |
6de9cd9a DN |
1743 | # VUSE <b_8> |
1744 | a_9 = b_8 + 2; | |
1745 | ||
1746 | # VUSE <a_9>; | |
1747 | # VUSE <b_8>; | |
1748 | return *p_1; | |
1749 | } | |
1750 | ||
1751 | In certain cases, the list of may aliases for a pointer may grow too | |
1752 | large. This may cause an explosion in the number of virtual operands | |
1753 | inserted in the code. Resulting in increased memory consumption and | |
1754 | compilation time. | |
1755 | ||
1756 | When the number of virtual operands needed to represent aliased | |
e9e0aa2c DN |
1757 | loads and stores grows too large (configurable with option --param |
1758 | max-aliased-vops and --param avg-aliased-vops), alias sets are | |
1759 | grouped to avoid severe compile-time slow downs and memory | |
1760 | consumption. See compute_memory_partitions. */ | |
6de9cd9a | 1761 | |
7b0e48fb | 1762 | unsigned int |
6de9cd9a DN |
1763 | compute_may_aliases (void) |
1764 | { | |
1765 | struct alias_info *ai; | |
7b0e48fb DB |
1766 | |
1767 | timevar_push (TV_TREE_MAY_ALIAS); | |
6de9cd9a DN |
1768 | |
1769 | memset (&alias_stats, 0, sizeof (alias_stats)); | |
1770 | ||
1771 | /* Initialize aliasing information. */ | |
1772 | ai = init_alias_info (); | |
1773 | ||
1774 | /* For each pointer P_i, determine the sets of variables that P_i may | |
1775 | point-to. For every addressable variable V, determine whether the | |
1776 | address of V escapes the current function, making V call-clobbered | |
1777 | (i.e., whether &V is stored in a global variable or if its passed as a | |
1778 | function call argument). */ | |
e8ca4159 | 1779 | compute_points_to_sets (ai); |
6de9cd9a DN |
1780 | |
1781 | /* Collect all pointers and addressable variables, compute alias sets, | |
1782 | create memory tags for pointers and promote variables whose address is | |
1783 | not needed anymore. */ | |
1784 | setup_pointers_and_addressables (ai); | |
1785 | ||
6de9cd9a DN |
1786 | /* Compute type-based flow-insensitive aliasing for all the type |
1787 | memory tags. */ | |
1788 | compute_flow_insensitive_aliasing (ai); | |
c58936b6 DB |
1789 | |
1790 | /* Compute flow-sensitive, points-to based aliasing for all the name | |
1791 | memory tags. */ | |
1792 | compute_flow_sensitive_aliasing (ai); | |
ca858709 DB |
1793 | |
1794 | /* Compute call clobbering information. */ | |
1795 | compute_call_clobbered (ai); | |
6de9cd9a | 1796 | |
38635499 DN |
1797 | /* If the program makes no reference to global variables, but it |
1798 | contains a mixture of pure and non-pure functions, then we need | |
1799 | to create use-def and def-def links between these functions to | |
1800 | avoid invalid transformations on them. */ | |
e9e0aa2c | 1801 | maybe_create_global_var (); |
6de9cd9a | 1802 | |
05a58ad4 EB |
1803 | /* If the program contains ref-all pointers, finalize may-alias information |
1804 | for them. This pass needs to be run after call-clobbering information | |
1805 | has been computed. */ | |
1806 | if (ai->ref_all_symbol_mem_tag) | |
1807 | finalize_ref_all_pointers (ai); | |
1808 | ||
38635499 DN |
1809 | /* Compute memory partitions for every memory variable. */ |
1810 | compute_memory_partitions (); | |
1811 | ||
e9e0aa2c DN |
1812 | /* Remove partitions with no symbols. Partitions may end up with an |
1813 | empty MPT_SYMBOLS set if a previous round of alias analysis | |
1814 | needed to partition more symbols. Since we don't need those | |
1815 | partitions anymore, remove them to free up the space. */ | |
1816 | { | |
1817 | tree mpt; | |
1818 | unsigned i; | |
1819 | VEC(tree,heap) *mpt_table; | |
1820 | ||
1821 | mpt_table = gimple_ssa_operands (cfun)->mpt_table; | |
1822 | i = 0; | |
1823 | while (i < VEC_length (tree, mpt_table)) | |
1824 | { | |
1825 | mpt = VEC_index (tree, mpt_table, i); | |
1826 | if (MPT_SYMBOLS (mpt) == NULL) | |
1827 | VEC_unordered_remove (tree, mpt_table, i); | |
1828 | else | |
1829 | i++; | |
1830 | } | |
1831 | } | |
1832 | ||
1833 | /* Populate all virtual operands and newly promoted register operands. */ | |
1834 | { | |
1835 | block_stmt_iterator bsi; | |
1836 | basic_block bb; | |
1837 | FOR_EACH_BB (bb) | |
1838 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
1839 | update_stmt_if_modified (bsi_stmt (bsi)); | |
1840 | } | |
1841 | ||
6de9cd9a DN |
1842 | /* Debugging dumps. */ |
1843 | if (dump_file) | |
1844 | { | |
e9e0aa2c DN |
1845 | dump_mem_ref_stats (dump_file); |
1846 | dump_alias_info (dump_file); | |
1847 | dump_points_to_info (dump_file); | |
1848 | ||
6de9cd9a DN |
1849 | if (dump_flags & TDF_STATS) |
1850 | dump_alias_stats (dump_file); | |
e9e0aa2c DN |
1851 | |
1852 | if (dump_flags & TDF_DETAILS) | |
1853 | dump_referenced_vars (dump_file); | |
6de9cd9a | 1854 | } |
e9e0aa2c | 1855 | |
79bedddc SR |
1856 | /* Report strict aliasing violations. */ |
1857 | strict_aliasing_warning_backend (); | |
1858 | ||
6de9cd9a DN |
1859 | /* Deallocate memory used by aliasing data structures. */ |
1860 | delete_alias_info (ai); | |
7b0e48fb DB |
1861 | |
1862 | if (need_ssa_update_p ()) | |
1863 | update_ssa (TODO_update_ssa); | |
1864 | ||
1865 | timevar_pop (TV_TREE_MAY_ALIAS); | |
e9e0aa2c | 1866 | |
c2924966 | 1867 | return 0; |
6de9cd9a DN |
1868 | } |
1869 | ||
a1d13fa1 DN |
1870 | /* Data structure used to count the number of dereferences to PTR |
1871 | inside an expression. */ | |
1872 | struct count_ptr_d | |
1873 | { | |
1874 | tree ptr; | |
1875 | unsigned count; | |
1876 | }; | |
1877 | ||
1878 | ||
1879 | /* Helper for count_uses_and_derefs. Called by walk_tree to look for | |
1880 | (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */ | |
1881 | ||
1882 | static tree | |
17c7e33e | 1883 | count_ptr_derefs (tree *tp, int *walk_subtrees, void *data) |
a1d13fa1 DN |
1884 | { |
1885 | struct count_ptr_d *count_p = (struct count_ptr_d *) data; | |
1886 | ||
17c7e33e DN |
1887 | /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld, |
1888 | pointer 'ptr' is *not* dereferenced, it is simply used to compute | |
1889 | the address of 'fld' as 'ptr + offsetof(fld)'. */ | |
1890 | if (TREE_CODE (*tp) == ADDR_EXPR) | |
1891 | { | |
1892 | *walk_subtrees = 0; | |
1893 | return NULL_TREE; | |
1894 | } | |
1895 | ||
a1d13fa1 DN |
1896 | if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr) |
1897 | count_p->count++; | |
1898 | ||
1899 | return NULL_TREE; | |
1900 | } | |
1901 | ||
1902 | ||
1903 | /* Count the number of direct and indirect uses for pointer PTR in | |
e9e0aa2c DN |
1904 | statement STMT. The number of direct uses is stored in |
1905 | *NUM_USES_P. Indirect references are counted separately depending | |
1906 | on whether they are store or load operations. The counts are | |
1907 | stored in *NUM_STORES_P and *NUM_LOADS_P. */ | |
a1d13fa1 | 1908 | |
0bca51f0 | 1909 | void |
a1d13fa1 | 1910 | count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p, |
e9e0aa2c | 1911 | unsigned *num_loads_p, unsigned *num_stores_p) |
a1d13fa1 DN |
1912 | { |
1913 | ssa_op_iter i; | |
1914 | tree use; | |
1915 | ||
1916 | *num_uses_p = 0; | |
e9e0aa2c DN |
1917 | *num_loads_p = 0; |
1918 | *num_stores_p = 0; | |
a1d13fa1 DN |
1919 | |
1920 | /* Find out the total number of uses of PTR in STMT. */ | |
1921 | FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE) | |
1922 | if (use == ptr) | |
1923 | (*num_uses_p)++; | |
1924 | ||
1925 | /* Now count the number of indirect references to PTR. This is | |
1926 | truly awful, but we don't have much choice. There are no parent | |
1927 | pointers inside INDIRECT_REFs, so an expression like | |
1928 | '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to | |
1929 | find all the indirect and direct uses of x_1 inside. The only | |
1930 | shortcut we can take is the fact that GIMPLE only allows | |
1931 | INDIRECT_REFs inside the expressions below. */ | |
07beea0d | 1932 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT |
a1d13fa1 | 1933 | || (TREE_CODE (stmt) == RETURN_EXPR |
07beea0d | 1934 | && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT) |
a1d13fa1 DN |
1935 | || TREE_CODE (stmt) == ASM_EXPR |
1936 | || TREE_CODE (stmt) == CALL_EXPR) | |
1937 | { | |
1938 | tree lhs, rhs; | |
1939 | ||
07beea0d | 1940 | if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) |
a1d13fa1 | 1941 | { |
07beea0d AH |
1942 | lhs = GIMPLE_STMT_OPERAND (stmt, 0); |
1943 | rhs = GIMPLE_STMT_OPERAND (stmt, 1); | |
a1d13fa1 DN |
1944 | } |
1945 | else if (TREE_CODE (stmt) == RETURN_EXPR) | |
1946 | { | |
1947 | tree e = TREE_OPERAND (stmt, 0); | |
07beea0d AH |
1948 | lhs = GIMPLE_STMT_OPERAND (e, 0); |
1949 | rhs = GIMPLE_STMT_OPERAND (e, 1); | |
a1d13fa1 DN |
1950 | } |
1951 | else if (TREE_CODE (stmt) == ASM_EXPR) | |
1952 | { | |
1953 | lhs = ASM_OUTPUTS (stmt); | |
1954 | rhs = ASM_INPUTS (stmt); | |
1955 | } | |
1956 | else | |
1957 | { | |
1958 | lhs = NULL_TREE; | |
1959 | rhs = stmt; | |
1960 | } | |
1961 | ||
e9e0aa2c DN |
1962 | if (lhs |
1963 | && (TREE_CODE (lhs) == TREE_LIST | |
1964 | || EXPR_P (lhs) | |
1965 | || GIMPLE_STMT_P (lhs))) | |
a1d13fa1 DN |
1966 | { |
1967 | struct count_ptr_d count; | |
1968 | count.ptr = ptr; | |
1969 | count.count = 0; | |
1970 | walk_tree (&lhs, count_ptr_derefs, &count, NULL); | |
e9e0aa2c | 1971 | *num_stores_p = count.count; |
a1d13fa1 DN |
1972 | } |
1973 | ||
e9e0aa2c DN |
1974 | if (rhs |
1975 | && (TREE_CODE (rhs) == TREE_LIST | |
1976 | || EXPR_P (rhs) | |
1977 | || GIMPLE_STMT_P (rhs))) | |
a1d13fa1 DN |
1978 | { |
1979 | struct count_ptr_d count; | |
1980 | count.ptr = ptr; | |
1981 | count.count = 0; | |
1982 | walk_tree (&rhs, count_ptr_derefs, &count, NULL); | |
e9e0aa2c | 1983 | *num_loads_p = count.count; |
a1d13fa1 DN |
1984 | } |
1985 | } | |
1986 | ||
e9e0aa2c DN |
1987 | gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p); |
1988 | } | |
1989 | ||
e9e0aa2c DN |
1990 | /* Remove memory references stats for function FN. */ |
1991 | ||
1992 | void | |
1993 | delete_mem_ref_stats (struct function *fn) | |
1994 | { | |
1995 | if (gimple_mem_ref_stats (fn)->mem_sym_stats) | |
1996 | { | |
603802e7 | 1997 | free_alloc_pool (mem_sym_stats_pool); |
e9e0aa2c DN |
1998 | pointer_map_destroy (gimple_mem_ref_stats (fn)->mem_sym_stats); |
1999 | } | |
e9e0aa2c DN |
2000 | gimple_mem_ref_stats (fn)->mem_sym_stats = NULL; |
2001 | } | |
2002 | ||
2003 | ||
2004 | /* Initialize memory reference stats. */ | |
2005 | ||
2006 | static void | |
2007 | init_mem_ref_stats (void) | |
2008 | { | |
2009 | struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun); | |
2010 | ||
603802e7 DB |
2011 | mem_sym_stats_pool = create_alloc_pool ("Mem sym stats", |
2012 | sizeof (struct mem_sym_stats_d), | |
2013 | 100); | |
e9e0aa2c DN |
2014 | memset (mem_ref_stats, 0, sizeof (struct mem_ref_stats_d)); |
2015 | mem_ref_stats->mem_sym_stats = pointer_map_create (); | |
a1d13fa1 DN |
2016 | } |
2017 | ||
e9e0aa2c | 2018 | |
bbe984fb DN |
2019 | /* Helper for init_alias_info. Reset existing aliasing information. */ |
2020 | ||
2021 | static void | |
2022 | reset_alias_info (void) | |
2023 | { | |
2024 | referenced_var_iterator rvi; | |
2025 | tree var; | |
2026 | unsigned i; | |
2027 | bitmap active_nmts, all_nmts; | |
2028 | ||
2029 | /* Clear the set of addressable variables. We do not need to clear | |
2030 | the TREE_ADDRESSABLE bit on every symbol because we are going to | |
2031 | re-compute addressability here. */ | |
2032 | bitmap_clear (gimple_addressable_vars (cfun)); | |
2033 | ||
2034 | active_nmts = BITMAP_ALLOC (&alias_bitmap_obstack); | |
2035 | all_nmts = BITMAP_ALLOC (&alias_bitmap_obstack); | |
2036 | ||
2037 | /* Clear flow-insensitive alias information from each symbol. */ | |
2038 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
2039 | { | |
2040 | if (is_gimple_reg (var)) | |
2041 | continue; | |
2042 | ||
2043 | if (MTAG_P (var)) | |
2044 | MTAG_ALIASES (var) = NULL; | |
2045 | ||
2046 | /* Memory partition information will be computed from scratch. */ | |
2047 | if (TREE_CODE (var) == MEMORY_PARTITION_TAG) | |
2048 | MPT_SYMBOLS (var) = NULL; | |
2049 | ||
2050 | /* Collect all the name tags to determine if we have any | |
2051 | orphaned that need to be removed from the IL. A name tag | |
2052 | will be orphaned if it is not associated with any active SSA | |
2053 | name. */ | |
2054 | if (TREE_CODE (var) == NAME_MEMORY_TAG) | |
2055 | bitmap_set_bit (all_nmts, DECL_UID (var)); | |
2056 | ||
2057 | /* Since we are about to re-discover call-clobbered | |
2058 | variables, clear the call-clobbered flag. Variables that | |
2059 | are intrinsically call-clobbered (globals, local statics, | |
2060 | etc) will not be marked by the aliasing code, so we can't | |
2061 | remove them from CALL_CLOBBERED_VARS. | |
2062 | ||
2063 | NB: STRUCT_FIELDS are still call clobbered if they are for a | |
2064 | global variable, so we *don't* clear their call clobberedness | |
2065 | just because they are tags, though we will clear it if they | |
2066 | aren't for global variables. */ | |
2067 | if (TREE_CODE (var) == NAME_MEMORY_TAG | |
2068 | || TREE_CODE (var) == SYMBOL_MEMORY_TAG | |
2069 | || TREE_CODE (var) == MEMORY_PARTITION_TAG | |
2070 | || !is_global_var (var)) | |
2071 | clear_call_clobbered (var); | |
2072 | } | |
2073 | ||
2074 | /* Clear flow-sensitive points-to information from each SSA name. */ | |
2075 | for (i = 1; i < num_ssa_names; i++) | |
2076 | { | |
2077 | tree name = ssa_name (i); | |
2078 | ||
2079 | if (!name || !POINTER_TYPE_P (TREE_TYPE (name))) | |
2080 | continue; | |
2081 | ||
2082 | if (SSA_NAME_PTR_INFO (name)) | |
2083 | { | |
2084 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); | |
2085 | ||
2086 | /* Clear all the flags but keep the name tag to | |
2087 | avoid creating new temporaries unnecessarily. If | |
2088 | this pointer is found to point to a subset or | |
2089 | superset of its former points-to set, then a new | |
2090 | tag will need to be created in create_name_tags. */ | |
2091 | pi->pt_anything = 0; | |
2092 | pi->pt_null = 0; | |
2093 | pi->value_escapes_p = 0; | |
2094 | pi->is_dereferenced = 0; | |
2095 | if (pi->pt_vars) | |
2096 | bitmap_clear (pi->pt_vars); | |
2097 | ||
2098 | /* Add NAME's name tag to the set of active tags. */ | |
2099 | if (pi->name_mem_tag) | |
2100 | bitmap_set_bit (active_nmts, DECL_UID (pi->name_mem_tag)); | |
2101 | } | |
2102 | } | |
2103 | ||
2104 | /* Name memory tags that are no longer associated with an SSA name | |
2105 | are considered stale and should be removed from the IL. All the | |
2106 | name tags that are in the set ALL_NMTS but not in ACTIVE_NMTS are | |
2107 | considered stale and marked for renaming. */ | |
2108 | bitmap_and_compl_into (all_nmts, active_nmts); | |
2109 | mark_set_for_renaming (all_nmts); | |
2110 | ||
2111 | BITMAP_FREE (all_nmts); | |
2112 | BITMAP_FREE (active_nmts); | |
2113 | } | |
2114 | ||
2115 | ||
6de9cd9a DN |
2116 | /* Initialize the data structures used for alias analysis. */ |
2117 | ||
2118 | static struct alias_info * | |
2119 | init_alias_info (void) | |
2120 | { | |
2121 | struct alias_info *ai; | |
a3648cfc DB |
2122 | referenced_var_iterator rvi; |
2123 | tree var; | |
6de9cd9a | 2124 | |
e1111e8e | 2125 | ai = XCNEW (struct alias_info); |
d0ce8e4c SB |
2126 | ai->ssa_names_visited = sbitmap_alloc (num_ssa_names); |
2127 | sbitmap_zero (ai->ssa_names_visited); | |
d96f49bf | 2128 | ai->processed_ptrs = VEC_alloc (tree, heap, 50); |
38635499 DN |
2129 | ai->written_vars = pointer_set_create (); |
2130 | ai->dereferenced_ptrs_store = pointer_set_create (); | |
2131 | ai->dereferenced_ptrs_load = pointer_set_create (); | |
6de9cd9a | 2132 | |
e9e0aa2c DN |
2133 | /* Clear out all memory reference stats. */ |
2134 | init_mem_ref_stats (); | |
2135 | ||
53b4bf74 | 2136 | /* If aliases have been computed before, clear existing information. */ |
5cd4ec7f | 2137 | if (gimple_aliases_computed_p (cfun)) |
bbe984fb | 2138 | reset_alias_info (); |
38635499 DN |
2139 | else |
2140 | { | |
2141 | /* If this is the first time we compute aliasing information, | |
2142 | every non-register symbol will need to be put into SSA form | |
2143 | (the initial SSA form only operates on GIMPLE registers). */ | |
2144 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
2145 | if (!is_gimple_reg (var)) | |
2146 | mark_sym_for_renaming (var); | |
2147 | } | |
53b4bf74 | 2148 | |
c1b763fa | 2149 | /* Next time, we will need to reset alias information. */ |
5cd4ec7f | 2150 | cfun->gimple_df->aliases_computed_p = true; |
603802e7 DB |
2151 | if (alias_bitmap_obstack.elements != NULL) |
2152 | bitmap_obstack_release (&alias_bitmap_obstack); | |
306219a2 | 2153 | bitmap_obstack_initialize (&alias_bitmap_obstack); |
c1b763fa | 2154 | |
6de9cd9a DN |
2155 | return ai; |
2156 | } | |
2157 | ||
2158 | ||
2159 | /* Deallocate memory used by alias analysis. */ | |
2160 | ||
2161 | static void | |
2162 | delete_alias_info (struct alias_info *ai) | |
2163 | { | |
2164 | size_t i; | |
2165 | ||
d0ce8e4c | 2166 | sbitmap_free (ai->ssa_names_visited); |
38635499 | 2167 | |
d96f49bf | 2168 | VEC_free (tree, heap, ai->processed_ptrs); |
6de9cd9a DN |
2169 | |
2170 | for (i = 0; i < ai->num_addressable_vars; i++) | |
a3648cfc | 2171 | free (ai->addressable_vars[i]); |
6de9cd9a | 2172 | free (ai->addressable_vars); |
38635499 | 2173 | |
6de9cd9a | 2174 | for (i = 0; i < ai->num_pointers; i++) |
a3648cfc | 2175 | free (ai->pointers[i]); |
6de9cd9a DN |
2176 | free (ai->pointers); |
2177 | ||
38635499 DN |
2178 | pointer_set_destroy (ai->written_vars); |
2179 | pointer_set_destroy (ai->dereferenced_ptrs_store); | |
2180 | pointer_set_destroy (ai->dereferenced_ptrs_load); | |
6de9cd9a | 2181 | free (ai); |
6de9cd9a | 2182 | |
603802e7 | 2183 | delete_mem_ref_stats (cfun); |
e8ca4159 | 2184 | delete_points_to_sets (); |
6de9cd9a DN |
2185 | } |
2186 | ||
e9e0aa2c | 2187 | |
1af4bba8 JH |
2188 | /* Used for hashing to identify pointer infos with identical |
2189 | pt_vars bitmaps. */ | |
e9e0aa2c | 2190 | |
1af4bba8 JH |
2191 | static int |
2192 | eq_ptr_info (const void *p1, const void *p2) | |
2193 | { | |
2194 | const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1; | |
2195 | const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2; | |
2196 | return bitmap_equal_p (n1->pt_vars, n2->pt_vars); | |
2197 | } | |
2198 | ||
2199 | static hashval_t | |
2200 | ptr_info_hash (const void *p) | |
2201 | { | |
2202 | const struct ptr_info_def *n = (const struct ptr_info_def *) p; | |
2203 | return bitmap_hash (n->pt_vars); | |
2204 | } | |
2205 | ||
e9e0aa2c | 2206 | |
d8903b30 DN |
2207 | /* Create name tags for all the pointers that have been dereferenced. |
2208 | We only create a name tag for a pointer P if P is found to point to | |
2209 | a set of variables (so that we can alias them to *P) or if it is | |
2210 | the result of a call to malloc (which means that P cannot point to | |
2211 | anything else nor alias any other variable). | |
2212 | ||
2213 | If two pointers P and Q point to the same set of variables, they | |
2214 | are assigned the same name tag. */ | |
2215 | ||
2216 | static void | |
a4f91294 | 2217 | create_name_tags (void) |
d8903b30 DN |
2218 | { |
2219 | size_t i; | |
fd312e90 DB |
2220 | VEC (tree, heap) *with_ptvars = NULL; |
2221 | tree ptr; | |
1af4bba8 | 2222 | htab_t ptr_hash; |
d8903b30 | 2223 | |
fd312e90 | 2224 | /* Collect the list of pointers with a non-empty points to set. */ |
a4f91294 | 2225 | for (i = 1; i < num_ssa_names; i++) |
d8903b30 | 2226 | { |
a4f91294 DN |
2227 | tree ptr = ssa_name (i); |
2228 | struct ptr_info_def *pi; | |
2229 | ||
2230 | if (!ptr | |
2231 | || !POINTER_TYPE_P (TREE_TYPE (ptr)) | |
2232 | || !SSA_NAME_PTR_INFO (ptr)) | |
2233 | continue; | |
2234 | ||
2235 | pi = SSA_NAME_PTR_INFO (ptr); | |
d8903b30 | 2236 | |
50dc9a88 | 2237 | if (pi->pt_anything || !pi->is_dereferenced) |
9ae2a5d1 DN |
2238 | { |
2239 | /* No name tags for pointers that have not been | |
50dc9a88 | 2240 | dereferenced or point to an arbitrary location. */ |
9ae2a5d1 DN |
2241 | pi->name_mem_tag = NULL_TREE; |
2242 | continue; | |
2243 | } | |
d8903b30 | 2244 | |
fd312e90 | 2245 | /* Set pt_anything on the pointers without pt_vars filled in so |
18cd8a03 | 2246 | that they are assigned a symbol tag. */ |
fd312e90 DB |
2247 | if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars)) |
2248 | VEC_safe_push (tree, heap, with_ptvars, ptr); | |
2249 | else | |
2250 | set_pt_anything (ptr); | |
2251 | } | |
2252 | ||
2253 | /* If we didn't find any pointers with pt_vars set, we're done. */ | |
2254 | if (!with_ptvars) | |
2255 | return; | |
2256 | ||
1af4bba8 | 2257 | ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL); |
e9e0aa2c | 2258 | |
fd312e90 DB |
2259 | /* Now go through the pointers with pt_vars, and find a name tag |
2260 | with the same pt_vars as this pointer, or create one if one | |
2261 | doesn't exist. */ | |
2262 | for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++) | |
2263 | { | |
2264 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); | |
fd312e90 | 2265 | tree old_name_tag = pi->name_mem_tag; |
1af4bba8 | 2266 | struct ptr_info_def **slot; |
fd312e90 DB |
2267 | |
2268 | /* If PTR points to a set of variables, check if we don't | |
2269 | have another pointer Q with the same points-to set before | |
2270 | creating a tag. If so, use Q's tag instead of creating a | |
2271 | new one. | |
2272 | ||
2273 | This is important for not creating unnecessary symbols | |
2274 | and also for copy propagation. If we ever need to | |
2275 | propagate PTR into Q or vice-versa, we would run into | |
2276 | problems if they both had different name tags because | |
2277 | they would have different SSA version numbers (which | |
2278 | would force us to take the name tags in and out of SSA). */ | |
1af4bba8 JH |
2279 | slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT); |
2280 | if (*slot) | |
2281 | pi->name_mem_tag = (*slot)->name_mem_tag; | |
2282 | else | |
d8903b30 | 2283 | { |
1af4bba8 | 2284 | *slot = pi; |
bbe984fb | 2285 | |
1af4bba8 JH |
2286 | /* If we didn't find a pointer with the same points-to set |
2287 | as PTR, create a new name tag if needed. */ | |
2288 | if (pi->name_mem_tag == NULL_TREE) | |
2289 | pi->name_mem_tag = get_nmt_for (ptr); | |
d8903b30 | 2290 | } |
fd312e90 | 2291 | |
fd312e90 DB |
2292 | /* If the new name tag computed for PTR is different than |
2293 | the old name tag that it used to have, then the old tag | |
2294 | needs to be removed from the IL, so we mark it for | |
2295 | renaming. */ | |
2296 | if (old_name_tag && old_name_tag != pi->name_mem_tag) | |
2297 | mark_sym_for_renaming (old_name_tag); | |
bbe984fb DN |
2298 | |
2299 | /* Inherit volatility from the pointed-to type. */ | |
38e05395 | 2300 | TREE_THIS_VOLATILE (pi->name_mem_tag) |
b65e51a8 | 2301 | |= TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (ptr))); |
fd312e90 | 2302 | |
d8903b30 | 2303 | /* Mark the new name tag for renaming. */ |
0bca51f0 | 2304 | mark_sym_for_renaming (pi->name_mem_tag); |
d8903b30 | 2305 | } |
e9e0aa2c | 2306 | |
1af4bba8 | 2307 | htab_delete (ptr_hash); |
fd312e90 DB |
2308 | |
2309 | VEC_free (tree, heap, with_ptvars); | |
d8903b30 DN |
2310 | } |
2311 | ||
e9e0aa2c DN |
2312 | |
2313 | /* Union the alias set SET into the may-aliases for TAG. */ | |
306219a2 DB |
2314 | |
2315 | static void | |
2316 | union_alias_set_into (tree tag, bitmap set) | |
2317 | { | |
2318 | bitmap ma = MTAG_ALIASES (tag); | |
2319 | ||
2320 | if (bitmap_empty_p (set)) | |
2321 | return; | |
2322 | ||
2323 | if (!ma) | |
2324 | ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack); | |
2325 | bitmap_ior_into (ma, set); | |
2326 | } | |
2327 | ||
d8903b30 | 2328 | |
6de9cd9a DN |
2329 | /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for |
2330 | the name memory tag (NMT) associated with P_i. If P_i escapes, then its | |
2331 | name tag and the variables it points-to are call-clobbered. Finally, if | |
2332 | P_i escapes and we could not determine where it points to, then all the | |
2333 | variables in the same alias set as *P_i are marked call-clobbered. This | |
2334 | is necessary because we must assume that P_i may take the address of any | |
2335 | variable in the same alias set. */ | |
2336 | ||
2337 | static void | |
2338 | compute_flow_sensitive_aliasing (struct alias_info *ai) | |
2339 | { | |
2340 | size_t i; | |
d96f49bf | 2341 | tree ptr; |
910fdc79 | 2342 | |
758137cd | 2343 | timevar_push (TV_FLOW_SENSITIVE); |
e5ebbea5 DB |
2344 | set_used_smts (); |
2345 | ||
d96f49bf | 2346 | for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) |
910fdc79 | 2347 | { |
e8ca4159 DN |
2348 | if (!find_what_p_points_to (ptr)) |
2349 | set_pt_anything (ptr); | |
910fdc79 | 2350 | } |
a4f91294 DN |
2351 | |
2352 | create_name_tags (); | |
d8903b30 | 2353 | |
d96f49bf | 2354 | for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++) |
6de9cd9a | 2355 | { |
313679b0 | 2356 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
38635499 | 2357 | tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr)); |
6de9cd9a | 2358 | |
6de9cd9a DN |
2359 | /* Set up aliasing information for PTR's name memory tag (if it has |
2360 | one). Note that only pointers that have been dereferenced will | |
2361 | have a name memory tag. */ | |
313679b0 | 2362 | if (pi->name_mem_tag && pi->pt_vars) |
306219a2 DB |
2363 | { |
2364 | if (!bitmap_empty_p (pi->pt_vars)) | |
2365 | { | |
2366 | union_alias_set_into (pi->name_mem_tag, pi->pt_vars); | |
2367 | union_alias_set_into (tag, pi->pt_vars); | |
2368 | bitmap_clear_bit (MTAG_ALIASES (tag), DECL_UID (tag)); | |
2369 | ||
2370 | /* It may be the case that this the tag uid was the only | |
2371 | bit we had set in the aliases list, and in this case, | |
2372 | we don't want to keep an empty bitmap, as this | |
2373 | asserts in tree-ssa-operands.c . */ | |
2374 | if (bitmap_empty_p (MTAG_ALIASES (tag))) | |
2375 | BITMAP_FREE (MTAG_ALIASES (tag)); | |
2376 | } | |
2377 | } | |
6de9cd9a | 2378 | } |
758137cd | 2379 | timevar_pop (TV_FLOW_SENSITIVE); |
6de9cd9a DN |
2380 | } |
2381 | ||
2382 | ||
306219a2 DB |
2383 | /* Return TRUE if at least one symbol in TAG2's alias set is also |
2384 | present in TAG1's alias set. */ | |
38635499 DN |
2385 | |
2386 | static bool | |
306219a2 | 2387 | have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases) |
38635499 | 2388 | { |
38635499 | 2389 | |
306219a2 DB |
2390 | /* This is the old behavior of have_common_aliases_p, which is to |
2391 | return false if both sets are empty, or one set is and the other | |
2392 | isn't. */ | |
2393 | if ((tag1aliases == NULL && tag2aliases != NULL) | |
2394 | || (tag2aliases == NULL && tag1aliases != NULL) | |
2395 | || (tag1aliases == NULL && tag2aliases == NULL)) | |
38635499 DN |
2396 | return false; |
2397 | ||
306219a2 | 2398 | return bitmap_intersect_p (tag1aliases, tag2aliases); |
38635499 DN |
2399 | } |
2400 | ||
6de9cd9a DN |
2401 | /* Compute type-based alias sets. Traverse all the pointers and |
2402 | addressable variables found in setup_pointers_and_addressables. | |
2403 | ||
2404 | For every pointer P in AI->POINTERS and addressable variable V in | |
18cd8a03 DN |
2405 | AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol |
2406 | memory tag (SMT) if their alias sets conflict. V is then marked as | |
38635499 | 2407 | an aliased symbol so that the operand scanner knows that statements |
6de9cd9a DN |
2408 | containing V have aliased operands. */ |
2409 | ||
2410 | static void | |
2411 | compute_flow_insensitive_aliasing (struct alias_info *ai) | |
2412 | { | |
2413 | size_t i; | |
2414 | ||
758137cd | 2415 | timevar_push (TV_FLOW_INSENSITIVE); |
6de9cd9a | 2416 | /* For every pointer P, determine which addressable variables may alias |
18cd8a03 | 2417 | with P's symbol memory tag. */ |
6de9cd9a DN |
2418 | for (i = 0; i < ai->num_pointers; i++) |
2419 | { | |
2420 | size_t j; | |
2421 | struct alias_map_d *p_map = ai->pointers[i]; | |
38635499 | 2422 | tree tag = symbol_mem_tag (p_map->var); |
99495729 | 2423 | tree var; |
6de9cd9a | 2424 | |
05a58ad4 EB |
2425 | /* Call-clobbering information is not finalized yet at this point. */ |
2426 | if (PTR_IS_REF_ALL (p_map->var)) | |
2427 | continue; | |
2428 | ||
6de9cd9a DN |
2429 | for (j = 0; j < ai->num_addressable_vars; j++) |
2430 | { | |
2431 | struct alias_map_d *v_map; | |
2432 | var_ann_t v_ann; | |
6de9cd9a DN |
2433 | bool tag_stored_p, var_stored_p; |
2434 | ||
2435 | v_map = ai->addressable_vars[j]; | |
2436 | var = v_map->var; | |
2437 | v_ann = var_ann (var); | |
2438 | ||
2439 | /* Skip memory tags and variables that have never been | |
2440 | written to. We also need to check if the variables are | |
2441 | call-clobbered because they may be overwritten by | |
38635499 DN |
2442 | function calls. */ |
2443 | tag_stored_p = pointer_set_contains (ai->written_vars, tag) | |
2444 | || is_call_clobbered (tag); | |
2445 | var_stored_p = pointer_set_contains (ai->written_vars, var) | |
2446 | || is_call_clobbered (var); | |
6de9cd9a DN |
2447 | if (!tag_stored_p && !var_stored_p) |
2448 | continue; | |
ea900239 DB |
2449 | |
2450 | if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false)) | |
6de9cd9a | 2451 | { |
d938e461 DB |
2452 | /* We should never have a var with subvars here, because |
2453 | they shouldn't get into the set of addressable vars */ | |
2454 | gcc_assert (!var_can_have_subvars (var) | |
2455 | || get_subvars_for_var (var) == NULL); | |
c75ab022 | 2456 | |
38635499 | 2457 | /* Add VAR to TAG's may-aliases set. */ |
306219a2 | 2458 | add_may_alias (tag, var); |
6de9cd9a DN |
2459 | } |
2460 | } | |
2461 | } | |
2462 | ||
1810f6ed DN |
2463 | /* Since this analysis is based exclusively on symbols, it fails to |
2464 | handle cases where two pointers P and Q have different memory | |
2465 | tags with conflicting alias set numbers but no aliased symbols in | |
2466 | common. | |
2467 | ||
18cd8a03 | 2468 | For example, suppose that we have two memory tags SMT.1 and SMT.2 |
1810f6ed DN |
2469 | such that |
2470 | ||
18cd8a03 DN |
2471 | may-aliases (SMT.1) = { a } |
2472 | may-aliases (SMT.2) = { b } | |
1810f6ed | 2473 | |
18cd8a03 | 2474 | and the alias set number of SMT.1 conflicts with that of SMT.2. |
1810f6ed | 2475 | Since they don't have symbols in common, loads and stores from |
18cd8a03 | 2476 | SMT.1 and SMT.2 will seem independent of each other, which will |
1810f6ed DN |
2477 | lead to the optimizers making invalid transformations (see |
2478 | testsuite/gcc.c-torture/execute/pr15262-[12].c). | |
2479 | ||
2480 | To avoid this problem, we do a final traversal of AI->POINTERS | |
2481 | looking for pairs of pointers that have no aliased symbols in | |
2482 | common and yet have conflicting alias set numbers. */ | |
1810f6ed DN |
2483 | for (i = 0; i < ai->num_pointers; i++) |
2484 | { | |
2485 | size_t j; | |
2486 | struct alias_map_d *p_map1 = ai->pointers[i]; | |
38635499 | 2487 | tree tag1 = symbol_mem_tag (p_map1->var); |
306219a2 | 2488 | bitmap may_aliases1 = MTAG_ALIASES (tag1); |
1810f6ed | 2489 | |
05a58ad4 EB |
2490 | if (PTR_IS_REF_ALL (p_map1->var)) |
2491 | continue; | |
2492 | ||
1810f6ed DN |
2493 | for (j = i + 1; j < ai->num_pointers; j++) |
2494 | { | |
2495 | struct alias_map_d *p_map2 = ai->pointers[j]; | |
38635499 | 2496 | tree tag2 = symbol_mem_tag (p_map2->var); |
306219a2 | 2497 | bitmap may_aliases2 = may_aliases (tag2); |
1810f6ed | 2498 | |
05a58ad4 EB |
2499 | if (PTR_IS_REF_ALL (p_map2->var)) |
2500 | continue; | |
2501 | ||
1810f6ed | 2502 | /* If the pointers may not point to each other, do nothing. */ |
ea900239 | 2503 | if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true)) |
1810f6ed DN |
2504 | continue; |
2505 | ||
2506 | /* The two pointers may alias each other. If they already have | |
2507 | symbols in common, do nothing. */ | |
306219a2 | 2508 | if (have_common_aliases_p (may_aliases1, may_aliases2)) |
1810f6ed DN |
2509 | continue; |
2510 | ||
306219a2 | 2511 | if (may_aliases2 && !bitmap_empty_p (may_aliases2)) |
1810f6ed | 2512 | { |
306219a2 | 2513 | union_alias_set_into (tag1, may_aliases2); |
1810f6ed DN |
2514 | } |
2515 | else | |
2516 | { | |
2517 | /* Since TAG2 does not have any aliases of its own, add | |
2518 | TAG2 itself to the alias set of TAG1. */ | |
306219a2 | 2519 | add_may_alias (tag1, tag2); |
1810f6ed DN |
2520 | } |
2521 | } | |
38635499 | 2522 | |
1810f6ed | 2523 | } |
758137cd | 2524 | timevar_pop (TV_FLOW_INSENSITIVE); |
6de9cd9a DN |
2525 | } |
2526 | ||
2527 | ||
05a58ad4 EB |
2528 | /* Finalize may-alias information for ref-all pointers. Traverse all |
2529 | the addressable variables found in setup_pointers_and_addressables. | |
2530 | ||
2531 | If flow-sensitive alias analysis has attached a name memory tag to | |
2532 | a ref-all pointer, we will use it for the dereferences because that | |
2533 | will have more precise aliasing information. But if there is no | |
2534 | name tag, we will use a special symbol tag that aliases all the | |
2535 | call-clobbered addressable variables. */ | |
2536 | ||
2537 | static void | |
2538 | finalize_ref_all_pointers (struct alias_info *ai) | |
2539 | { | |
2540 | size_t i; | |
2541 | ||
38635499 DN |
2542 | /* First add the real call-clobbered variables. */ |
2543 | for (i = 0; i < ai->num_addressable_vars; i++) | |
2941f691 | 2544 | { |
38635499 DN |
2545 | tree var = ai->addressable_vars[i]->var; |
2546 | if (is_call_clobbered (var)) | |
306219a2 | 2547 | add_may_alias (ai->ref_all_symbol_mem_tag, var); |
2941f691 | 2548 | } |
6de9cd9a | 2549 | |
38635499 DN |
2550 | /* Then add the call-clobbered pointer memory tags. See |
2551 | compute_flow_insensitive_aliasing for the rationale. */ | |
6de9cd9a DN |
2552 | for (i = 0; i < ai->num_pointers; i++) |
2553 | { | |
38635499 | 2554 | tree ptr = ai->pointers[i]->var, tag; |
773a7861 | 2555 | /* Avoid adding to self and clean up. */ |
38635499 | 2556 | if (PTR_IS_REF_ALL (ptr)) |
773a7861 EB |
2557 | { |
2558 | struct ptr_info_def *pi = get_ptr_info (ptr); | |
2559 | if (pi->is_dereferenced) | |
2560 | pi->pt_anything = 0; | |
2561 | continue; | |
2562 | } | |
38635499 DN |
2563 | tag = symbol_mem_tag (ptr); |
2564 | if (is_call_clobbered (tag)) | |
306219a2 | 2565 | add_may_alias (ai->ref_all_symbol_mem_tag, tag); |
6de9cd9a DN |
2566 | } |
2567 | ||
6de9cd9a DN |
2568 | } |
2569 | ||
2570 | ||
2571 | /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */ | |
2572 | ||
2573 | static void | |
2574 | create_alias_map_for (tree var, struct alias_info *ai) | |
2575 | { | |
2576 | struct alias_map_d *alias_map; | |
e1111e8e | 2577 | alias_map = XCNEW (struct alias_map_d); |
6de9cd9a | 2578 | alias_map->var = var; |
fbc87627 | 2579 | alias_map->set = get_alias_set (var); |
6de9cd9a DN |
2580 | ai->addressable_vars[ai->num_addressable_vars++] = alias_map; |
2581 | } | |
2582 | ||
2583 | ||
2584 | /* Create memory tags for all the dereferenced pointers and build the | |
2585 | ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias | |
2586 | sets. Based on the address escape and points-to information collected | |
2587 | earlier, this pass will also clear the TREE_ADDRESSABLE flag from those | |
2588 | variables whose address is not needed anymore. */ | |
2589 | ||
2590 | static void | |
2591 | setup_pointers_and_addressables (struct alias_info *ai) | |
2592 | { | |
38635499 | 2593 | size_t num_addressable_vars, num_pointers; |
a3648cfc DB |
2594 | referenced_var_iterator rvi; |
2595 | tree var; | |
b9d33488 DB |
2596 | VEC (tree, heap) *varvec = NULL; |
2597 | safe_referenced_var_iterator srvi; | |
6de9cd9a DN |
2598 | |
2599 | /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */ | |
2600 | num_addressable_vars = num_pointers = 0; | |
a3648cfc DB |
2601 | |
2602 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
6de9cd9a | 2603 | { |
6de9cd9a DN |
2604 | if (may_be_aliased (var)) |
2605 | num_addressable_vars++; | |
2606 | ||
2607 | if (POINTER_TYPE_P (TREE_TYPE (var))) | |
2608 | { | |
26e79d10 RH |
2609 | /* Since we don't keep track of volatile variables, assume that |
2610 | these pointers are used in indirect store operations. */ | |
2611 | if (TREE_THIS_VOLATILE (var)) | |
38635499 | 2612 | pointer_set_insert (ai->dereferenced_ptrs_store, var); |
6de9cd9a DN |
2613 | |
2614 | num_pointers++; | |
2615 | } | |
2616 | } | |
2617 | ||
2618 | /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are | |
2619 | always going to be slightly bigger than we actually need them | |
2620 | because some TREE_ADDRESSABLE variables will be marked | |
18cd8a03 | 2621 | non-addressable below and only pointers with unique symbol tags are |
6de9cd9a | 2622 | going to be added to POINTERS. */ |
e1111e8e GDR |
2623 | ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars); |
2624 | ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers); | |
6de9cd9a DN |
2625 | ai->num_addressable_vars = 0; |
2626 | ai->num_pointers = 0; | |
2627 | ||
b9d33488 | 2628 | FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi) |
6de9cd9a | 2629 | { |
c75ab022 | 2630 | subvar_t svars; |
6de9cd9a | 2631 | |
d8903b30 DN |
2632 | /* Name memory tags already have flow-sensitive aliasing |
2633 | information, so they need not be processed by | |
18cd8a03 | 2634 | compute_flow_insensitive_aliasing. Similarly, symbol memory |
1810f6ed | 2635 | tags are already accounted for when we process their |
c75ab022 DB |
2636 | associated pointer. |
2637 | ||
2638 | Structure fields, on the other hand, have to have some of this | |
2639 | information processed for them, but it's pointless to mark them | |
2640 | non-addressable (since they are fake variables anyway). */ | |
326eda4b | 2641 | if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG) |
6de9cd9a DN |
2642 | continue; |
2643 | ||
2644 | /* Remove the ADDRESSABLE flag from every addressable variable whose | |
2645 | address is not needed anymore. This is caused by the propagation | |
2646 | of ADDR_EXPR constants into INDIRECT_REF expressions and the | |
2647 | removal of dead pointer assignments done by the early scalar | |
2648 | cleanup passes. */ | |
e8ca4159 | 2649 | if (TREE_ADDRESSABLE (var)) |
6de9cd9a | 2650 | { |
5cd4ec7f | 2651 | if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var)) |
57e28d7d | 2652 | && TREE_CODE (var) != RESULT_DECL |
c597ef4e | 2653 | && !is_global_var (var)) |
6de9cd9a | 2654 | { |
c75ab022 | 2655 | bool okay_to_mark = true; |
0bca51f0 | 2656 | |
c75ab022 DB |
2657 | /* Since VAR is now a regular GIMPLE register, we will need |
2658 | to rename VAR into SSA afterwards. */ | |
0bca51f0 | 2659 | mark_sym_for_renaming (var); |
c75ab022 | 2660 | |
e8ca4159 DN |
2661 | /* If VAR can have sub-variables, and any of its |
2662 | sub-variables has its address taken, then we cannot | |
2663 | remove the addressable flag from VAR. */ | |
c75ab022 DB |
2664 | if (var_can_have_subvars (var) |
2665 | && (svars = get_subvars_for_var (var))) | |
2666 | { | |
eee717aa RG |
2667 | unsigned int i; |
2668 | tree subvar; | |
c75ab022 | 2669 | |
eee717aa | 2670 | for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i) |
c75ab022 | 2671 | { |
5cd4ec7f | 2672 | if (bitmap_bit_p (gimple_addressable_vars (cfun), |
eee717aa | 2673 | DECL_UID (subvar))) |
c75ab022 | 2674 | okay_to_mark = false; |
eee717aa | 2675 | mark_sym_for_renaming (subvar); |
c75ab022 DB |
2676 | } |
2677 | } | |
0bca51f0 | 2678 | |
d8903b30 DN |
2679 | /* The address of VAR is not needed, remove the |
2680 | addressable bit, so that it can be optimized as a | |
2681 | regular variable. */ | |
c75ab022 | 2682 | if (okay_to_mark) |
38635499 DN |
2683 | { |
2684 | /* The memory partition holding VAR will no longer | |
2685 | contain VAR, and statements referencing it will need | |
2e226e66 | 2686 | to be updated. */ |
38635499 DN |
2687 | if (memory_partition (var)) |
2688 | mark_sym_for_renaming (memory_partition (var)); | |
2689 | ||
2690 | mark_non_addressable (var); | |
2691 | } | |
6de9cd9a DN |
2692 | } |
2693 | } | |
2694 | ||
2695 | /* Global variables and addressable locals may be aliased. Create an | |
2696 | entry in ADDRESSABLE_VARS for VAR. */ | |
38635499 | 2697 | if (may_be_aliased (var)) |
6de9cd9a | 2698 | { |
38635499 DN |
2699 | if (!var_can_have_subvars (var) |
2700 | || get_subvars_for_var (var) == NULL) | |
2701 | create_alias_map_for (var, ai); | |
2702 | ||
0bca51f0 | 2703 | mark_sym_for_renaming (var); |
6de9cd9a DN |
2704 | } |
2705 | ||
2706 | /* Add pointer variables that have been dereferenced to the POINTERS | |
18cd8a03 | 2707 | array and create a symbol memory tag for them. */ |
c1b763fa | 2708 | if (POINTER_TYPE_P (TREE_TYPE (var))) |
6de9cd9a | 2709 | { |
38635499 DN |
2710 | if ((pointer_set_contains (ai->dereferenced_ptrs_store, var) |
2711 | || pointer_set_contains (ai->dereferenced_ptrs_load, var))) | |
c1b763fa | 2712 | { |
38635499 | 2713 | tree tag, old_tag; |
c1b763fa DN |
2714 | var_ann_t t_ann; |
2715 | ||
2716 | /* If pointer VAR still doesn't have a memory tag | |
2717 | associated with it, create it now or re-use an | |
2718 | existing one. */ | |
38635499 | 2719 | tag = get_smt_for (var, ai); |
c1b763fa DN |
2720 | t_ann = var_ann (tag); |
2721 | ||
18cd8a03 | 2722 | /* The symbol tag will need to be renamed into SSA |
c1b763fa | 2723 | afterwards. Note that we cannot do this inside |
38635499 | 2724 | get_smt_for because aliasing may run multiple times |
18cd8a03 | 2725 | and we only create symbol tags the first time. */ |
0bca51f0 DN |
2726 | mark_sym_for_renaming (tag); |
2727 | ||
2728 | /* Similarly, if pointer VAR used to have another type | |
2729 | tag, we will need to process it in the renamer to | |
2730 | remove the stale virtual operands. */ | |
38635499 DN |
2731 | old_tag = symbol_mem_tag (var); |
2732 | if (old_tag) | |
2733 | mark_sym_for_renaming (old_tag); | |
c1b763fa DN |
2734 | |
2735 | /* Associate the tag with pointer VAR. */ | |
38635499 | 2736 | set_symbol_mem_tag (var, tag); |
c1b763fa DN |
2737 | |
2738 | /* If pointer VAR has been used in a store operation, | |
2739 | then its memory tag must be marked as written-to. */ | |
38635499 DN |
2740 | if (pointer_set_contains (ai->dereferenced_ptrs_store, var)) |
2741 | pointer_set_insert (ai->written_vars, tag); | |
c1b763fa DN |
2742 | } |
2743 | else | |
2744 | { | |
2745 | /* The pointer has not been dereferenced. If it had a | |
18cd8a03 | 2746 | symbol memory tag, remove it and mark the old tag for |
c1b763fa | 2747 | renaming to remove it out of the IL. */ |
38635499 | 2748 | tree tag = symbol_mem_tag (var); |
c1b763fa DN |
2749 | if (tag) |
2750 | { | |
0bca51f0 | 2751 | mark_sym_for_renaming (tag); |
38635499 | 2752 | set_symbol_mem_tag (var, NULL_TREE); |
c1b763fa DN |
2753 | } |
2754 | } | |
6de9cd9a DN |
2755 | } |
2756 | } | |
38635499 | 2757 | |
b9d33488 | 2758 | VEC_free (tree, heap, varvec); |
6de9cd9a DN |
2759 | } |
2760 | ||
2761 | ||
38635499 DN |
2762 | /* Determine whether to use .GLOBAL_VAR to model call clobbering |
2763 | semantics. If the function makes no references to global | |
2764 | variables and contains at least one call to a non-pure function, | |
2765 | then we need to mark the side-effects of the call using .GLOBAL_VAR | |
2766 | to represent all possible global memory referenced by the callee. */ | |
6de9cd9a DN |
2767 | |
2768 | static void | |
e9e0aa2c | 2769 | maybe_create_global_var (void) |
6de9cd9a | 2770 | { |
53b4bf74 | 2771 | /* No need to create it, if we have one already. */ |
5cd4ec7f | 2772 | if (gimple_global_var (cfun) == NULL_TREE) |
e0d3bb46 | 2773 | { |
e9e0aa2c DN |
2774 | struct mem_ref_stats_d *stats = gimple_mem_ref_stats (cfun); |
2775 | ||
38635499 | 2776 | /* Create .GLOBAL_VAR if there are no call-clobbered |
90c1d75a DN |
2777 | variables and the program contains a mixture of pure/const |
2778 | and regular function calls. This is to avoid the problem | |
2779 | described in PR 20115: | |
2780 | ||
2781 | int X; | |
2782 | int func_pure (void) { return X; } | |
2783 | int func_non_pure (int a) { X += a; } | |
2784 | int foo () | |
2785 | { | |
2786 | int a = func_pure (); | |
2787 | func_non_pure (a); | |
2788 | a = func_pure (); | |
2789 | return a; | |
2790 | } | |
2791 | ||
2792 | Since foo() has no call-clobbered variables, there is | |
2793 | no relationship between the calls to func_pure and | |
2794 | func_non_pure. Since func_pure has no side-effects, value | |
2795 | numbering optimizations elide the second call to func_pure. | |
2796 | So, if we have some pure/const and some regular calls in the | |
2797 | program we create .GLOBAL_VAR to avoid missing these | |
2798 | relations. */ | |
76e910c6 | 2799 | if (bitmap_empty_p (gimple_call_clobbered_vars (cfun)) |
e9e0aa2c DN |
2800 | && stats->num_call_sites > 0 |
2801 | && stats->num_pure_const_call_sites > 0 | |
2802 | && stats->num_call_sites > stats->num_pure_const_call_sites) | |
e0d3bb46 DN |
2803 | create_global_var (); |
2804 | } | |
6de9cd9a DN |
2805 | } |
2806 | ||
2807 | ||
2808 | /* Return TRUE if pointer PTR may point to variable VAR. | |
2809 | ||
2810 | MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR | |
2811 | This is needed because when checking for type conflicts we are | |
2812 | interested in the alias set of the memory location pointed-to by | |
2813 | PTR. The alias set of PTR itself is irrelevant. | |
2814 | ||
2815 | VAR_ALIAS_SET is the alias set for VAR. */ | |
2816 | ||
2817 | static bool | |
4862826d ILT |
2818 | may_alias_p (tree ptr, alias_set_type mem_alias_set, |
2819 | tree var, alias_set_type var_alias_set, | |
ea900239 | 2820 | bool alias_set_only) |
6de9cd9a DN |
2821 | { |
2822 | tree mem; | |
6de9cd9a DN |
2823 | |
2824 | alias_stats.alias_queries++; | |
2825 | alias_stats.simple_queries++; | |
2826 | ||
2827 | /* By convention, a variable cannot alias itself. */ | |
38635499 | 2828 | mem = symbol_mem_tag (ptr); |
6de9cd9a DN |
2829 | if (mem == var) |
2830 | { | |
2831 | alias_stats.alias_noalias++; | |
2832 | alias_stats.simple_resolved++; | |
2833 | return false; | |
2834 | } | |
0698a1d2 TM |
2835 | |
2836 | /* If -fargument-noalias-global is > 2, pointer arguments may | |
2837 | not point to anything else. */ | |
2838 | if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL) | |
2839 | { | |
2840 | alias_stats.alias_noalias++; | |
2841 | alias_stats.simple_resolved++; | |
2842 | return false; | |
2843 | } | |
2844 | ||
2845 | /* If -fargument-noalias-global is > 1, pointer arguments may | |
d3010d72 AP |
2846 | not point to global variables. */ |
2847 | if (flag_argument_noalias > 1 && is_global_var (var) | |
2848 | && TREE_CODE (ptr) == PARM_DECL) | |
2849 | { | |
2850 | alias_stats.alias_noalias++; | |
2851 | alias_stats.simple_resolved++; | |
2852 | return false; | |
2853 | } | |
6de9cd9a | 2854 | |
f8d66d34 DN |
2855 | /* If either MEM or VAR is a read-only global and the other one |
2856 | isn't, then PTR cannot point to VAR. */ | |
2857 | if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var)) | |
2858 | || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem))) | |
2859 | { | |
2860 | alias_stats.alias_noalias++; | |
2861 | alias_stats.simple_resolved++; | |
2862 | return false; | |
2863 | } | |
2864 | ||
18cd8a03 | 2865 | gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG); |
6de9cd9a | 2866 | |
058dcc25 | 2867 | if (!DECL_NO_TBAA_P (ptr)) |
6de9cd9a | 2868 | { |
058dcc25 | 2869 | alias_stats.tbaa_queries++; |
ea900239 | 2870 | |
058dcc25 ILT |
2871 | /* If the alias sets don't conflict then MEM cannot alias VAR. */ |
2872 | if (!alias_sets_conflict_p (mem_alias_set, var_alias_set)) | |
ea900239 | 2873 | { |
058dcc25 ILT |
2874 | alias_stats.alias_noalias++; |
2875 | alias_stats.tbaa_resolved++; | |
2876 | return false; | |
2877 | } | |
2878 | ||
2879 | /* If VAR is a record or union type, PTR cannot point into VAR | |
2880 | unless there is some explicit address operation in the | |
2881 | program that can reference a field of the type pointed-to by | |
2882 | PTR. This also assumes that the types of both VAR and PTR | |
2883 | are contained within the compilation unit, and that there is | |
2884 | no fancy addressing arithmetic associated with any of the | |
2885 | types involved. */ | |
2886 | if (mem_alias_set != 0 && var_alias_set != 0) | |
2887 | { | |
2888 | tree ptr_type = TREE_TYPE (ptr); | |
2889 | tree var_type = TREE_TYPE (var); | |
2890 | ||
2891 | /* The star count is -1 if the type at the end of the | |
2892 | pointer_to chain is not a record or union type. */ | |
2893 | if ((!alias_set_only) && | |
2894 | ipa_type_escape_star_count_of_interesting_type (var_type) >= 0) | |
ea900239 | 2895 | { |
058dcc25 | 2896 | int ptr_star_count = 0; |
ea900239 | 2897 | |
058dcc25 ILT |
2898 | /* ipa_type_escape_star_count_of_interesting_type is a |
2899 | little too restrictive for the pointer type, need to | |
2900 | allow pointers to primitive types as long as those | |
2901 | types cannot be pointers to everything. */ | |
2902 | while (POINTER_TYPE_P (ptr_type)) | |
2903 | { | |
2904 | /* Strip the *s off. */ | |
2905 | ptr_type = TREE_TYPE (ptr_type); | |
2906 | ptr_star_count++; | |
2907 | } | |
2908 | ||
2909 | /* There does not appear to be a better test to see if | |
2910 | the pointer type was one of the pointer to everything | |
2911 | types. */ | |
2912 | if (ptr_star_count > 0) | |
ea900239 | 2913 | { |
058dcc25 ILT |
2914 | alias_stats.structnoaddress_queries++; |
2915 | if (ipa_type_escape_field_does_not_clobber_p (var_type, | |
2916 | TREE_TYPE (ptr))) | |
2917 | { | |
2918 | alias_stats.structnoaddress_resolved++; | |
2919 | alias_stats.alias_noalias++; | |
2920 | return false; | |
2921 | } | |
2922 | } | |
2923 | else if (ptr_star_count == 0) | |
2924 | { | |
2925 | /* If PTR_TYPE was not really a pointer to type, it cannot | |
2926 | alias. */ | |
2927 | alias_stats.structnoaddress_queries++; | |
ea900239 DB |
2928 | alias_stats.structnoaddress_resolved++; |
2929 | alias_stats.alias_noalias++; | |
2930 | return false; | |
2931 | } | |
2932 | } | |
ea900239 DB |
2933 | } |
2934 | } | |
2935 | ||
6de9cd9a DN |
2936 | alias_stats.alias_mayalias++; |
2937 | return true; | |
2938 | } | |
2939 | ||
2940 | ||
306219a2 | 2941 | /* Add ALIAS to the set of variables that may alias VAR. */ |
6de9cd9a DN |
2942 | |
2943 | static void | |
306219a2 | 2944 | add_may_alias (tree var, tree alias) |
6de9cd9a | 2945 | { |
e8ca4159 | 2946 | /* Don't allow self-referential aliases. */ |
1e128c5f | 2947 | gcc_assert (var != alias); |
6de9cd9a | 2948 | |
e8ca4159 DN |
2949 | /* ALIAS must be addressable if it's being added to an alias set. */ |
2950 | #if 1 | |
2951 | TREE_ADDRESSABLE (alias) = 1; | |
2952 | #else | |
2953 | gcc_assert (may_be_aliased (alias)); | |
2954 | #endif | |
2955 | ||
38635499 DN |
2956 | /* VAR must be a symbol or a name tag. */ |
2957 | gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG | |
2958 | || TREE_CODE (var) == NAME_MEMORY_TAG); | |
2959 | ||
306219a2 DB |
2960 | if (MTAG_ALIASES (var) == NULL) |
2961 | MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack); | |
2962 | ||
2963 | bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias)); | |
6de9cd9a DN |
2964 | } |
2965 | ||
2966 | ||
53b4bf74 DN |
2967 | /* Mark pointer PTR as pointing to an arbitrary memory location. */ |
2968 | ||
2969 | static void | |
2970 | set_pt_anything (tree ptr) | |
2971 | { | |
2972 | struct ptr_info_def *pi = get_ptr_info (ptr); | |
2973 | ||
2974 | pi->pt_anything = 1; | |
e8ca4159 | 2975 | pi->pt_vars = NULL; |
53b4bf74 DN |
2976 | |
2977 | /* The pointer used to have a name tag, but we now found it pointing | |
2978 | to an arbitrary location. The name tag needs to be renamed and | |
2979 | disassociated from PTR. */ | |
2980 | if (pi->name_mem_tag) | |
2981 | { | |
0bca51f0 | 2982 | mark_sym_for_renaming (pi->name_mem_tag); |
53b4bf74 DN |
2983 | pi->name_mem_tag = NULL_TREE; |
2984 | } | |
2985 | } | |
2986 | ||
2987 | ||
6de9cd9a DN |
2988 | /* Return true if STMT is an "escape" site from the current function. Escape |
2989 | sites those statements which might expose the address of a variable | |
2990 | outside the current function. STMT is an escape site iff: | |
2991 | ||
2992 | 1- STMT is a function call, or | |
2993 | 2- STMT is an __asm__ expression, or | |
2994 | 3- STMT is an assignment to a non-local variable, or | |
2995 | 4- STMT is a return statement. | |
2996 | ||
d16a5e36 DB |
2997 | Return the type of escape site found, if we found one, or NO_ESCAPE |
2998 | if none. */ | |
6de9cd9a | 2999 | |
d16a5e36 | 3000 | enum escape_type |
21392f19 | 3001 | is_escape_site (tree stmt) |
6de9cd9a | 3002 | { |
90c1d75a DN |
3003 | tree call = get_call_expr_in (stmt); |
3004 | if (call != NULL_TREE) | |
6de9cd9a | 3005 | { |
90c1d75a | 3006 | if (!TREE_SIDE_EFFECTS (call)) |
21392f19 | 3007 | return ESCAPE_TO_PURE_CONST; |
6de9cd9a | 3008 | |
d16a5e36 | 3009 | return ESCAPE_TO_CALL; |
6de9cd9a DN |
3010 | } |
3011 | else if (TREE_CODE (stmt) == ASM_EXPR) | |
d16a5e36 | 3012 | return ESCAPE_TO_ASM; |
07beea0d | 3013 | else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT) |
6de9cd9a | 3014 | { |
07beea0d | 3015 | tree lhs = GIMPLE_STMT_OPERAND (stmt, 0); |
6de9cd9a DN |
3016 | |
3017 | /* Get to the base of _REF nodes. */ | |
3018 | if (TREE_CODE (lhs) != SSA_NAME) | |
3019 | lhs = get_base_address (lhs); | |
3020 | ||
3021 | /* If we couldn't recognize the LHS of the assignment, assume that it | |
3022 | is a non-local store. */ | |
3023 | if (lhs == NULL_TREE) | |
d16a5e36 | 3024 | return ESCAPE_UNKNOWN; |
6de9cd9a | 3025 | |
07beea0d AH |
3026 | if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == NOP_EXPR |
3027 | || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CONVERT_EXPR | |
3028 | || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR) | |
05a58ad4 | 3029 | { |
07beea0d AH |
3030 | tree from |
3031 | = TREE_TYPE (TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0)); | |
3032 | tree to = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 1)); | |
05a58ad4 EB |
3033 | |
3034 | /* If the RHS is a conversion between a pointer and an integer, the | |
3035 | pointer escapes since we can't track the integer. */ | |
3036 | if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to)) | |
3037 | return ESCAPE_BAD_CAST; | |
3038 | ||
3039 | /* Same if the RHS is a conversion between a regular pointer and a | |
3040 | ref-all pointer since we can't track the SMT of the former. */ | |
3041 | if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from) | |
3042 | && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (to)) | |
3043 | return ESCAPE_BAD_CAST; | |
3044 | } | |
406eab99 | 3045 | |
6de9cd9a DN |
3046 | /* If the LHS is an SSA name, it can't possibly represent a non-local |
3047 | memory store. */ | |
3048 | if (TREE_CODE (lhs) == SSA_NAME) | |
d16a5e36 | 3049 | return NO_ESCAPE; |
6de9cd9a DN |
3050 | |
3051 | /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a | |
3052 | local variables we cannot be sure if it will escape, because we | |
3053 | don't have information about objects not in SSA form. Need to | |
3054 | implement something along the lines of | |
3055 | ||
3056 | J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. | |
3057 | Midkiff, ``Escape analysis for java,'' in Proceedings of the | |
3058 | Conference on Object-Oriented Programming Systems, Languages, and | |
3059 | Applications (OOPSLA), pp. 1-19, 1999. */ | |
d16a5e36 | 3060 | return ESCAPE_STORED_IN_GLOBAL; |
6de9cd9a DN |
3061 | } |
3062 | else if (TREE_CODE (stmt) == RETURN_EXPR) | |
d16a5e36 | 3063 | return ESCAPE_TO_RETURN; |
6de9cd9a | 3064 | |
d16a5e36 | 3065 | return NO_ESCAPE; |
6de9cd9a DN |
3066 | } |
3067 | ||
326eda4b DB |
3068 | /* Create a new memory tag of type TYPE. |
3069 | Does NOT push it into the current binding. */ | |
3070 | ||
38635499 | 3071 | tree |
326eda4b DB |
3072 | create_tag_raw (enum tree_code code, tree type, const char *prefix) |
3073 | { | |
3074 | tree tmp_var; | |
326eda4b | 3075 | |
38635499 | 3076 | tmp_var = build_decl (code, create_tmp_var_name (prefix), type); |
326eda4b | 3077 | |
326eda4b DB |
3078 | /* Make the variable writable. */ |
3079 | TREE_READONLY (tmp_var) = 0; | |
3080 | ||
3081 | /* It doesn't start out global. */ | |
3082 | MTAG_GLOBAL (tmp_var) = 0; | |
3083 | TREE_STATIC (tmp_var) = 0; | |
3084 | TREE_USED (tmp_var) = 1; | |
3085 | ||
3086 | return tmp_var; | |
3087 | } | |
6de9cd9a DN |
3088 | |
3089 | /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag | |
3090 | is considered to represent all the pointers whose pointed-to types are | |
3091 | in the same alias set class. Otherwise, the tag represents a single | |
3092 | SSA_NAME pointer variable. */ | |
3093 | ||
3094 | static tree | |
3095 | create_memory_tag (tree type, bool is_type_tag) | |
3096 | { | |
18cd8a03 DN |
3097 | tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG, |
3098 | type, (is_type_tag) ? "SMT" : "NMT"); | |
6de9cd9a DN |
3099 | |
3100 | /* By default, memory tags are local variables. Alias analysis will | |
3101 | determine whether they should be considered globals. */ | |
3102 | DECL_CONTEXT (tag) = current_function_decl; | |
3103 | ||
e8ca4159 | 3104 | /* Memory tags are by definition addressable. */ |
6de9cd9a DN |
3105 | TREE_ADDRESSABLE (tag) = 1; |
3106 | ||
38635499 | 3107 | set_symbol_mem_tag (tag, NULL_TREE); |
6de9cd9a | 3108 | |
d8903b30 | 3109 | /* Add the tag to the symbol table. */ |
f004ab02 | 3110 | add_referenced_var (tag); |
6de9cd9a DN |
3111 | |
3112 | return tag; | |
3113 | } | |
3114 | ||
3115 | ||
3116 | /* Create a name memory tag to represent a specific SSA_NAME pointer P_i. | |
3117 | This is used if P_i has been found to point to a specific set of | |
3118 | variables or to a non-aliased memory location like the address returned | |
3119 | by malloc functions. */ | |
3120 | ||
3121 | static tree | |
3122 | get_nmt_for (tree ptr) | |
3123 | { | |
313679b0 DN |
3124 | struct ptr_info_def *pi = get_ptr_info (ptr); |
3125 | tree tag = pi->name_mem_tag; | |
6de9cd9a DN |
3126 | |
3127 | if (tag == NULL_TREE) | |
c597ef4e | 3128 | tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false); |
6de9cd9a DN |
3129 | return tag; |
3130 | } | |
3131 | ||
3132 | ||
18cd8a03 DN |
3133 | /* Return the symbol memory tag associated to pointer PTR. A memory |
3134 | tag is an artificial variable that represents the memory location | |
3135 | pointed-to by PTR. It is used to model the effects of pointer | |
3136 | de-references on addressable variables. | |
6de9cd9a | 3137 | |
18cd8a03 DN |
3138 | AI points to the data gathered during alias analysis. This |
3139 | function populates the array AI->POINTERS. */ | |
6de9cd9a DN |
3140 | |
3141 | static tree | |
38635499 | 3142 | get_smt_for (tree ptr, struct alias_info *ai) |
6de9cd9a DN |
3143 | { |
3144 | size_t i; | |
3145 | tree tag; | |
3146 | tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); | |
4862826d | 3147 | alias_set_type tag_set = get_alias_set (tag_type); |
6de9cd9a | 3148 | |
05a58ad4 EB |
3149 | /* We use a unique memory tag for all the ref-all pointers. */ |
3150 | if (PTR_IS_REF_ALL (ptr)) | |
3151 | { | |
3152 | if (!ai->ref_all_symbol_mem_tag) | |
3153 | ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true); | |
3154 | return ai->ref_all_symbol_mem_tag; | |
3155 | } | |
3156 | ||
6de9cd9a DN |
3157 | /* To avoid creating unnecessary memory tags, only create one memory tag |
3158 | per alias set class. Note that it may be tempting to group | |
3159 | memory tags based on conflicting alias sets instead of | |
3160 | equivalence. That would be wrong because alias sets are not | |
3161 | necessarily transitive (as demonstrated by the libstdc++ test | |
3162 | 23_containers/vector/cons/4.cc). Given three alias sets A, B, C | |
3163 | such that conflicts (A, B) == true and conflicts (A, C) == true, | |
3164 | it does not necessarily follow that conflicts (B, C) == true. */ | |
3165 | for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++) | |
3166 | { | |
3167 | struct alias_map_d *curr = ai->pointers[i]; | |
38635499 | 3168 | tree curr_tag = symbol_mem_tag (curr->var); |
3c0b6c43 | 3169 | if (tag_set == curr->set) |
6de9cd9a | 3170 | { |
f8d66d34 | 3171 | tag = curr_tag; |
6de9cd9a DN |
3172 | break; |
3173 | } | |
3174 | } | |
3175 | ||
3176 | /* If VAR cannot alias with any of the existing memory tags, create a new | |
3177 | tag for PTR and add it to the POINTERS array. */ | |
3178 | if (tag == NULL_TREE) | |
3179 | { | |
3180 | struct alias_map_d *alias_map; | |
3181 | ||
18cd8a03 | 3182 | /* If PTR did not have a symbol tag already, create a new SMT.* |
53b4bf74 DN |
3183 | artificial variable representing the memory location |
3184 | pointed-to by PTR. */ | |
38635499 DN |
3185 | tag = symbol_mem_tag (ptr); |
3186 | if (tag == NULL_TREE) | |
53b4bf74 | 3187 | tag = create_memory_tag (tag_type, true); |
6de9cd9a DN |
3188 | |
3189 | /* Add PTR to the POINTERS array. Note that we are not interested in | |
3190 | PTR's alias set. Instead, we cache the alias set for the memory that | |
3191 | PTR points to. */ | |
e1111e8e | 3192 | alias_map = XCNEW (struct alias_map_d); |
6de9cd9a DN |
3193 | alias_map->var = ptr; |
3194 | alias_map->set = tag_set; | |
3195 | ai->pointers[ai->num_pointers++] = alias_map; | |
3196 | } | |
3197 | ||
c04f07f4 | 3198 | /* If the pointed-to type is volatile, so is the tag. */ |
38e05395 | 3199 | TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type); |
c04f07f4 | 3200 | |
18cd8a03 | 3201 | /* Make sure that the symbol tag has the same alias set as the |
bbc630f5 | 3202 | pointed-to type. */ |
1e128c5f | 3203 | gcc_assert (tag_set == get_alias_set (tag)); |
bbc630f5 | 3204 | |
6de9cd9a DN |
3205 | return tag; |
3206 | } | |
3207 | ||
3208 | ||
3209 | /* Create GLOBAL_VAR, an artificial global variable to act as a | |
3210 | representative of all the variables that may be clobbered by function | |
3211 | calls. */ | |
3212 | ||
3213 | static void | |
3214 | create_global_var (void) | |
3215 | { | |
5cd4ec7f JH |
3216 | tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"), |
3217 | void_type_node); | |
6de9cd9a DN |
3218 | DECL_ARTIFICIAL (global_var) = 1; |
3219 | TREE_READONLY (global_var) = 0; | |
58907cda | 3220 | DECL_EXTERNAL (global_var) = 1; |
6de9cd9a DN |
3221 | TREE_STATIC (global_var) = 1; |
3222 | TREE_USED (global_var) = 1; | |
3223 | DECL_CONTEXT (global_var) = NULL_TREE; | |
3224 | TREE_THIS_VOLATILE (global_var) = 0; | |
3225 | TREE_ADDRESSABLE (global_var) = 0; | |
3226 | ||
d16a5e36 DB |
3227 | create_var_ann (global_var); |
3228 | mark_call_clobbered (global_var, ESCAPE_UNKNOWN); | |
f004ab02 | 3229 | add_referenced_var (global_var); |
0bca51f0 | 3230 | mark_sym_for_renaming (global_var); |
5cd4ec7f | 3231 | cfun->gimple_df->global_var = global_var; |
6de9cd9a DN |
3232 | } |
3233 | ||
3234 | ||
3235 | /* Dump alias statistics on FILE. */ | |
3236 | ||
3237 | static void | |
3238 | dump_alias_stats (FILE *file) | |
3239 | { | |
3240 | const char *funcname | |
673fda6b | 3241 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
6de9cd9a DN |
3242 | fprintf (file, "\nAlias statistics for %s\n\n", funcname); |
3243 | fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries); | |
3244 | fprintf (file, "Total alias mayalias results:\t%u\n", | |
3245 | alias_stats.alias_mayalias); | |
3246 | fprintf (file, "Total alias noalias results:\t%u\n", | |
3247 | alias_stats.alias_noalias); | |
3248 | fprintf (file, "Total simple queries:\t%u\n", | |
3249 | alias_stats.simple_queries); | |
3250 | fprintf (file, "Total simple resolved:\t%u\n", | |
3251 | alias_stats.simple_resolved); | |
3252 | fprintf (file, "Total TBAA queries:\t%u\n", | |
3253 | alias_stats.tbaa_queries); | |
3254 | fprintf (file, "Total TBAA resolved:\t%u\n", | |
3255 | alias_stats.tbaa_resolved); | |
ea900239 DB |
3256 | fprintf (file, "Total non-addressable structure type queries:\t%u\n", |
3257 | alias_stats.structnoaddress_queries); | |
3258 | fprintf (file, "Total non-addressable structure type resolved:\t%u\n", | |
3259 | alias_stats.structnoaddress_resolved); | |
6de9cd9a DN |
3260 | } |
3261 | ||
3262 | ||
3263 | /* Dump alias information on FILE. */ | |
3264 | ||
3265 | void | |
3266 | dump_alias_info (FILE *file) | |
3267 | { | |
3268 | size_t i; | |
3269 | const char *funcname | |
673fda6b | 3270 | = lang_hooks.decl_printable_name (current_function_decl, 2); |
a3648cfc DB |
3271 | referenced_var_iterator rvi; |
3272 | tree var; | |
6de9cd9a | 3273 | |
e9e0aa2c DN |
3274 | fprintf (file, "\nAlias information for %s\n\n", funcname); |
3275 | ||
3276 | dump_memory_partitions (file); | |
3277 | ||
53b4bf74 DN |
3278 | fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname); |
3279 | ||
3280 | fprintf (file, "Aliased symbols\n\n"); | |
a3648cfc DB |
3281 | |
3282 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
53b4bf74 | 3283 | { |
53b4bf74 DN |
3284 | if (may_be_aliased (var)) |
3285 | dump_variable (file, var); | |
3286 | } | |
3287 | ||
3288 | fprintf (file, "\nDereferenced pointers\n\n"); | |
a3648cfc DB |
3289 | |
3290 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
38635499 DN |
3291 | if (symbol_mem_tag (var)) |
3292 | dump_variable (file, var); | |
53b4bf74 | 3293 | |
18cd8a03 | 3294 | fprintf (file, "\nSymbol memory tags\n\n"); |
a3648cfc DB |
3295 | |
3296 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
53b4bf74 | 3297 | { |
18cd8a03 | 3298 | if (TREE_CODE (var) == SYMBOL_MEMORY_TAG) |
53b4bf74 DN |
3299 | dump_variable (file, var); |
3300 | } | |
3301 | ||
3302 | fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname); | |
3303 | ||
3304 | fprintf (file, "SSA_NAME pointers\n\n"); | |
3305 | for (i = 1; i < num_ssa_names; i++) | |
3306 | { | |
3307 | tree ptr = ssa_name (i); | |
d804d490 DN |
3308 | struct ptr_info_def *pi; |
3309 | ||
3310 | if (ptr == NULL_TREE) | |
3311 | continue; | |
3312 | ||
3313 | pi = SSA_NAME_PTR_INFO (ptr); | |
53b4bf74 DN |
3314 | if (!SSA_NAME_IN_FREE_LIST (ptr) |
3315 | && pi | |
3316 | && pi->name_mem_tag) | |
3317 | dump_points_to_info_for (file, ptr); | |
3318 | } | |
6de9cd9a | 3319 | |
53b4bf74 | 3320 | fprintf (file, "\nName memory tags\n\n"); |
a3648cfc DB |
3321 | |
3322 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
6de9cd9a | 3323 | { |
326eda4b | 3324 | if (TREE_CODE (var) == NAME_MEMORY_TAG) |
6de9cd9a DN |
3325 | dump_variable (file, var); |
3326 | } | |
3327 | ||
3328 | fprintf (file, "\n"); | |
3329 | } | |
3330 | ||
3331 | ||
3332 | /* Dump alias information on stderr. */ | |
3333 | ||
3334 | void | |
3335 | debug_alias_info (void) | |
3336 | { | |
3337 | dump_alias_info (stderr); | |
3338 | } | |
3339 | ||
3340 | ||
313679b0 DN |
3341 | /* Return the alias information associated with pointer T. It creates a |
3342 | new instance if none existed. */ | |
3343 | ||
de66168d | 3344 | struct ptr_info_def * |
313679b0 DN |
3345 | get_ptr_info (tree t) |
3346 | { | |
3347 | struct ptr_info_def *pi; | |
3348 | ||
1e128c5f | 3349 | gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); |
313679b0 DN |
3350 | |
3351 | pi = SSA_NAME_PTR_INFO (t); | |
3352 | if (pi == NULL) | |
3353 | { | |
b9eae1a9 | 3354 | pi = GGC_CNEW (struct ptr_info_def); |
313679b0 DN |
3355 | SSA_NAME_PTR_INFO (t) = pi; |
3356 | } | |
3357 | ||
3358 | return pi; | |
3359 | } | |
3360 | ||
3361 | ||
6de9cd9a DN |
3362 | /* Dump points-to information for SSA_NAME PTR into FILE. */ |
3363 | ||
d8903b30 | 3364 | void |
6de9cd9a DN |
3365 | dump_points_to_info_for (FILE *file, tree ptr) |
3366 | { | |
313679b0 | 3367 | struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); |
6de9cd9a | 3368 | |
6de9cd9a DN |
3369 | print_generic_expr (file, ptr, dump_flags); |
3370 | ||
d8903b30 | 3371 | if (pi) |
6de9cd9a | 3372 | { |
d8903b30 DN |
3373 | if (pi->name_mem_tag) |
3374 | { | |
3375 | fprintf (file, ", name memory tag: "); | |
3376 | print_generic_expr (file, pi->name_mem_tag, dump_flags); | |
3377 | } | |
6de9cd9a | 3378 | |
d8903b30 | 3379 | if (pi->is_dereferenced) |
bbe984fb | 3380 | fprintf (file, ", is dereferenced"); |
6de9cd9a | 3381 | |
d8903b30 DN |
3382 | if (pi->value_escapes_p) |
3383 | fprintf (file, ", its value escapes"); | |
6de9cd9a | 3384 | |
d8903b30 DN |
3385 | if (pi->pt_anything) |
3386 | fprintf (file, ", points-to anything"); | |
6de9cd9a | 3387 | |
a1d13fa1 DN |
3388 | if (pi->pt_null) |
3389 | fprintf (file, ", points-to NULL"); | |
3390 | ||
d8903b30 DN |
3391 | if (pi->pt_vars) |
3392 | { | |
38635499 DN |
3393 | fprintf (file, ", points-to vars: "); |
3394 | dump_decl_set (file, pi->pt_vars); | |
d8903b30 | 3395 | } |
6de9cd9a DN |
3396 | } |
3397 | ||
3398 | fprintf (file, "\n"); | |
3399 | } | |
3400 | ||
3401 | ||
d8903b30 DN |
3402 | /* Dump points-to information for VAR into stderr. */ |
3403 | ||
3404 | void | |
3405 | debug_points_to_info_for (tree var) | |
3406 | { | |
3407 | dump_points_to_info_for (stderr, var); | |
3408 | } | |
3409 | ||
3410 | ||
6de9cd9a DN |
3411 | /* Dump points-to information into FILE. NOTE: This function is slow, as |
3412 | it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */ | |
3413 | ||
3414 | void | |
3415 | dump_points_to_info (FILE *file) | |
3416 | { | |
3417 | basic_block bb; | |
3418 | block_stmt_iterator si; | |
4c124b4c | 3419 | ssa_op_iter iter; |
6de9cd9a | 3420 | const char *fname = |
673fda6b | 3421 | lang_hooks.decl_printable_name (current_function_decl, 2); |
a3648cfc DB |
3422 | referenced_var_iterator rvi; |
3423 | tree var; | |
6de9cd9a DN |
3424 | |
3425 | fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname); | |
3426 | ||
3427 | /* First dump points-to information for the default definitions of | |
3428 | pointer variables. This is necessary because default definitions are | |
3429 | not part of the code. */ | |
a3648cfc | 3430 | FOR_EACH_REFERENCED_VAR (var, rvi) |
6de9cd9a | 3431 | { |
6de9cd9a DN |
3432 | if (POINTER_TYPE_P (TREE_TYPE (var))) |
3433 | { | |
5cd4ec7f | 3434 | tree def = gimple_default_def (cfun, var); |
df1f6f31 JH |
3435 | if (def) |
3436 | dump_points_to_info_for (file, def); | |
6de9cd9a DN |
3437 | } |
3438 | } | |
3439 | ||
3440 | /* Dump points-to information for every pointer defined in the program. */ | |
3441 | FOR_EACH_BB (bb) | |
3442 | { | |
3443 | tree phi; | |
3444 | ||
17192884 | 3445 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) |
6de9cd9a DN |
3446 | { |
3447 | tree ptr = PHI_RESULT (phi); | |
3448 | if (POINTER_TYPE_P (TREE_TYPE (ptr))) | |
3449 | dump_points_to_info_for (file, ptr); | |
3450 | } | |
3451 | ||
3452 | for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) | |
3453 | { | |
4c124b4c AM |
3454 | tree stmt = bsi_stmt (si); |
3455 | tree def; | |
3456 | FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) | |
e9e0aa2c DN |
3457 | if (TREE_CODE (def) == SSA_NAME |
3458 | && POINTER_TYPE_P (TREE_TYPE (def))) | |
4c124b4c | 3459 | dump_points_to_info_for (file, def); |
6de9cd9a DN |
3460 | } |
3461 | } | |
3462 | ||
3463 | fprintf (file, "\n"); | |
3464 | } | |
3465 | ||
3466 | ||
206048bd | 3467 | /* Dump points-to info pointed to by PTO into STDERR. */ |
6de9cd9a DN |
3468 | |
3469 | void | |
3470 | debug_points_to_info (void) | |
3471 | { | |
3472 | dump_points_to_info (stderr); | |
3473 | } | |
3474 | ||
3475 | /* Dump to FILE the list of variables that may be aliasing VAR. */ | |
3476 | ||
3477 | void | |
3478 | dump_may_aliases_for (FILE *file, tree var) | |
3479 | { | |
306219a2 | 3480 | bitmap aliases; |
6de9cd9a | 3481 | |
306219a2 | 3482 | aliases = MTAG_ALIASES (var); |
6de9cd9a DN |
3483 | if (aliases) |
3484 | { | |
3b302421 RG |
3485 | bitmap_iterator bi; |
3486 | unsigned int i; | |
780e37d3 | 3487 | tree al; |
306219a2 | 3488 | |
6de9cd9a | 3489 | fprintf (file, "{ "); |
3b302421 | 3490 | EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi) |
6de9cd9a | 3491 | { |
3b302421 | 3492 | al = referenced_var (i); |
780e37d3 | 3493 | print_generic_expr (file, al, dump_flags); |
6de9cd9a DN |
3494 | fprintf (file, " "); |
3495 | } | |
3496 | fprintf (file, "}"); | |
3497 | } | |
3498 | } | |
3499 | ||
3500 | ||
3501 | /* Dump to stderr the list of variables that may be aliasing VAR. */ | |
3502 | ||
3503 | void | |
3504 | debug_may_aliases_for (tree var) | |
3505 | { | |
3506 | dump_may_aliases_for (stderr, var); | |
3507 | } | |
ab8907ef | 3508 | |
38635499 | 3509 | |
ab8907ef RH |
3510 | /* Return true if VAR may be aliased. */ |
3511 | ||
3512 | bool | |
3513 | may_be_aliased (tree var) | |
3514 | { | |
3515 | /* Obviously. */ | |
3516 | if (TREE_ADDRESSABLE (var)) | |
3517 | return true; | |
3518 | ||
ab8907ef RH |
3519 | /* Globally visible variables can have their addresses taken by other |
3520 | translation units. */ | |
326eda4b DB |
3521 | if (MTAG_P (var) |
3522 | && (MTAG_GLOBAL (var) || TREE_PUBLIC (var))) | |
3523 | return true; | |
3524 | else if (!MTAG_P (var) | |
38635499 | 3525 | && (DECL_EXTERNAL (var) || TREE_PUBLIC (var))) |
ab8907ef RH |
3526 | return true; |
3527 | ||
38635499 DN |
3528 | /* Automatic variables can't have their addresses escape any other |
3529 | way. This must be after the check for global variables, as | |
3530 | extern declarations do not have TREE_STATIC set. */ | |
bb1058e4 JW |
3531 | if (!TREE_STATIC (var)) |
3532 | return false; | |
3533 | ||
38635499 DN |
3534 | /* If we're in unit-at-a-time mode, then we must have seen all |
3535 | occurrences of address-of operators, and so we can trust | |
3536 | TREE_ADDRESSABLE. Otherwise we can only be sure the variable | |
3537 | isn't addressable if it's local to the current function. */ | |
ab8907ef RH |
3538 | if (flag_unit_at_a_time) |
3539 | return false; | |
38635499 | 3540 | |
ab8907ef RH |
3541 | if (decl_function_context (var) == current_function_decl) |
3542 | return false; | |
3543 | ||
3544 | return true; | |
3545 | } | |
c75ab022 | 3546 | |
cc0968b0 DN |
3547 | /* The following is based on code in add_stmt_operand to ensure that the |
3548 | same defs/uses/vdefs/vuses will be found after replacing a reference | |
3549 | to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value | |
3550 | is the address of var. Return a memtag for the ptr, after adding the | |
3551 | proper may_aliases to it (which are the aliases of var, if it has any, | |
3552 | or var itself). */ | |
3553 | ||
3554 | static tree | |
3555 | add_may_alias_for_new_tag (tree tag, tree var) | |
3556 | { | |
306219a2 DB |
3557 | bitmap aliases = NULL; |
3558 | ||
3559 | if (MTAG_P (var)) | |
3560 | aliases = may_aliases (var); | |
cc0968b0 DN |
3561 | |
3562 | /* Case 1: |aliases| == 1 */ | |
76e910c6 RG |
3563 | if (aliases |
3564 | && bitmap_single_bit_set_p (aliases)) | |
cc0968b0 | 3565 | { |
306219a2 | 3566 | tree ali = referenced_var (bitmap_first_set_bit (aliases)); |
cc0968b0 DN |
3567 | if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG) |
3568 | return ali; | |
3569 | } | |
3570 | ||
3571 | /* Case 2: |aliases| == 0 */ | |
3572 | if (aliases == NULL) | |
306219a2 | 3573 | add_may_alias (tag, var); |
cc0968b0 DN |
3574 | else |
3575 | { | |
3576 | /* Case 3: |aliases| > 1 */ | |
306219a2 | 3577 | union_alias_set_into (tag, aliases); |
cc0968b0 | 3578 | } |
cc0968b0 DN |
3579 | return tag; |
3580 | } | |
86a07404 | 3581 | |
18cd8a03 | 3582 | /* Create a new symbol tag for PTR. Construct the may-alias list of this type |
cc0968b0 DN |
3583 | tag so that it has the aliasing of VAR, or of the relevant subvars of VAR |
3584 | according to the location accessed by EXPR. | |
51540eba | 3585 | |
18cd8a03 | 3586 | Note, the set of aliases represented by the new symbol tag are not marked |
51540eba | 3587 | for renaming. */ |
9cf5a7e3 KB |
3588 | |
3589 | void | |
cc0968b0 | 3590 | new_type_alias (tree ptr, tree var, tree expr) |
9cf5a7e3 | 3591 | { |
9cf5a7e3 | 3592 | tree tag_type = TREE_TYPE (TREE_TYPE (ptr)); |
9cf5a7e3 KB |
3593 | tree tag; |
3594 | subvar_t svars; | |
cc0968b0 DN |
3595 | tree ali = NULL_TREE; |
3596 | HOST_WIDE_INT offset, size, maxsize; | |
3597 | tree ref; | |
d092f0f6 | 3598 | VEC (tree, heap) *overlaps = NULL; |
eee717aa RG |
3599 | unsigned int len, i; |
3600 | tree subvar; | |
3601 | ||
9cf5a7e3 | 3602 | |
38635499 | 3603 | gcc_assert (symbol_mem_tag (ptr) == NULL_TREE); |
326eda4b | 3604 | gcc_assert (!MTAG_P (var)); |
9cf5a7e3 | 3605 | |
cc0968b0 DN |
3606 | ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize); |
3607 | gcc_assert (ref); | |
3608 | ||
3609 | tag = create_memory_tag (tag_type, true); | |
38635499 | 3610 | set_symbol_mem_tag (ptr, tag); |
cc0968b0 | 3611 | |
18cd8a03 | 3612 | /* Add VAR to the may-alias set of PTR's new symbol tag. If VAR has |
9cf5a7e3 | 3613 | subvars, add the subvars to the tag instead of the actual var. */ |
d092f0f6 ZD |
3614 | if (var_can_have_subvars (ref) |
3615 | && (svars = get_subvars_for_var (ref))) | |
9cf5a7e3 | 3616 | { |
eee717aa | 3617 | for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i) |
51540eba | 3618 | { |
cc0968b0 | 3619 | bool exact; |
9cf5a7e3 | 3620 | |
eee717aa RG |
3621 | if (overlap_subvar (offset, maxsize, subvar, &exact)) |
3622 | VEC_safe_push (tree, heap, overlaps, subvar); | |
cc0968b0 | 3623 | } |
d092f0f6 ZD |
3624 | gcc_assert (overlaps != NULL); |
3625 | } | |
3626 | else if (var_can_have_subvars (var) | |
3627 | && (svars = get_subvars_for_var (var))) | |
3628 | { | |
3629 | /* If the REF is not a direct access to VAR (e.g., it is a dereference | |
3630 | of a pointer), we should scan the virtual operands of REF the same | |
3631 | way as tree-ssa-operands do. At the moment, this is somewhat | |
3632 | difficult, so we just give up and add all the subvars of VAR. | |
3633 | On mem-ssa branch, the scanning for virtual operands have been | |
3634 | split from the rest of tree-ssa-operands, so it should be much | |
3635 | easier to fix this problem correctly once mem-ssa is merged. */ | |
eee717aa RG |
3636 | for (i = 0; VEC_iterate (tree, svars, i, subvar); ++i) |
3637 | VEC_safe_push (tree, heap, overlaps, subvar); | |
d092f0f6 ZD |
3638 | |
3639 | gcc_assert (overlaps != NULL); | |
3640 | } | |
3641 | else | |
3642 | ali = add_may_alias_for_new_tag (tag, var); | |
3643 | ||
3644 | len = VEC_length (tree, overlaps); | |
3645 | if (len > 0) | |
3646 | { | |
cc0968b0 | 3647 | if (dump_file && (dump_flags & TDF_DETAILS)) |
d092f0f6 | 3648 | fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len); |
cc0968b0 DN |
3649 | |
3650 | if (len == 1) | |
d092f0f6 | 3651 | ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0)); |
cc0968b0 | 3652 | else if (len > 1) |
d092f0f6 | 3653 | { |
cc0968b0 DN |
3654 | unsigned int k; |
3655 | tree sv_var; | |
3656 | ||
3657 | for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++) | |
51540eba | 3658 | { |
cc0968b0 | 3659 | ali = add_may_alias_for_new_tag (tag, sv_var); |
51540eba | 3660 | |
cc0968b0 DN |
3661 | if (ali != tag) |
3662 | { | |
3663 | /* Can happen only if 'Case 1' of add_may_alias_for_new_tag | |
3664 | took place. Since more than one svar was found, we add | |
3665 | 'ali' as one of the may_aliases of the new tag. */ | |
306219a2 | 3666 | add_may_alias (tag, ali); |
cc0968b0 DN |
3667 | ali = tag; |
3668 | } | |
3669 | } | |
51540eba | 3670 | } |
d092f0f6 | 3671 | VEC_free (tree, heap, overlaps); |
cc0968b0 | 3672 | } |
afa38a95 | 3673 | |
38635499 | 3674 | set_symbol_mem_tag (ptr, ali); |
afa38a95 DN |
3675 | TREE_READONLY (tag) = TREE_READONLY (var); |
3676 | MTAG_GLOBAL (tag) = is_global_var (var); | |
9cf5a7e3 KB |
3677 | } |
3678 | ||
c75ab022 DB |
3679 | /* This represents the used range of a variable. */ |
3680 | ||
3681 | typedef struct used_part | |
3682 | { | |
3683 | HOST_WIDE_INT minused; | |
3684 | HOST_WIDE_INT maxused; | |
31617ef1 DB |
3685 | /* True if we have an explicit use/def of some portion of this variable, |
3686 | even if it is all of it. i.e. a.b = 5 or temp = a.b. */ | |
3687 | bool explicit_uses; | |
3688 | /* True if we have an implicit use/def of some portion of this | |
3689 | variable. Implicit uses occur when we can't tell what part we | |
3690 | are referencing, and have to make conservative assumptions. */ | |
3691 | bool implicit_uses; | |
183596eb RG |
3692 | /* True if the structure is only written to or taken its address. */ |
3693 | bool write_only; | |
c75ab022 DB |
3694 | } *used_part_t; |
3695 | ||
3696 | /* An array of used_part structures, indexed by variable uid. */ | |
3697 | ||
a3648cfc DB |
3698 | static htab_t used_portions; |
3699 | ||
3700 | struct used_part_map | |
3701 | { | |
3702 | unsigned int uid; | |
3703 | used_part_t to; | |
3704 | }; | |
3705 | ||
3706 | /* Return true if the uid in the two used part maps are equal. */ | |
3707 | ||
3708 | static int | |
3709 | used_part_map_eq (const void *va, const void *vb) | |
3710 | { | |
e1111e8e GDR |
3711 | const struct used_part_map *a = (const struct used_part_map *) va; |
3712 | const struct used_part_map *b = (const struct used_part_map *) vb; | |
a3648cfc DB |
3713 | return (a->uid == b->uid); |
3714 | } | |
3715 | ||
3716 | /* Hash a from uid in a used_part_map. */ | |
3717 | ||
3718 | static unsigned int | |
3719 | used_part_map_hash (const void *item) | |
3720 | { | |
3721 | return ((const struct used_part_map *)item)->uid; | |
3722 | } | |
3723 | ||
3724 | /* Free a used part map element. */ | |
3725 | ||
3726 | static void | |
3727 | free_used_part_map (void *item) | |
3728 | { | |
3729 | free (((struct used_part_map *)item)->to); | |
46c73d9a | 3730 | free (item); |
a3648cfc DB |
3731 | } |
3732 | ||
3733 | /* Lookup a used_part structure for a UID. */ | |
3734 | ||
3735 | static used_part_t | |
3736 | up_lookup (unsigned int uid) | |
3737 | { | |
3738 | struct used_part_map *h, in; | |
3739 | in.uid = uid; | |
e1111e8e | 3740 | h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid); |
a3648cfc DB |
3741 | if (!h) |
3742 | return NULL; | |
3743 | return h->to; | |
3744 | } | |
3745 | ||
3746 | /* Insert the pair UID, TO into the used part hashtable. */ | |
3747 | ||
3748 | static void | |
3749 | up_insert (unsigned int uid, used_part_t to) | |
3750 | { | |
3751 | struct used_part_map *h; | |
3752 | void **loc; | |
3753 | ||
e1111e8e | 3754 | h = XNEW (struct used_part_map); |
a3648cfc DB |
3755 | h->uid = uid; |
3756 | h->to = to; | |
3757 | loc = htab_find_slot_with_hash (used_portions, h, | |
3758 | uid, INSERT); | |
46c73d9a DB |
3759 | if (*loc != NULL) |
3760 | free (*loc); | |
a3648cfc DB |
3761 | *(struct used_part_map **) loc = h; |
3762 | } | |
3763 | ||
c75ab022 DB |
3764 | |
3765 | /* Given a variable uid, UID, get or create the entry in the used portions | |
3766 | table for the variable. */ | |
3767 | ||
3768 | static used_part_t | |
3769 | get_or_create_used_part_for (size_t uid) | |
3770 | { | |
3771 | used_part_t up; | |
a3648cfc | 3772 | if ((up = up_lookup (uid)) == NULL) |
c75ab022 | 3773 | { |
e1111e8e | 3774 | up = XCNEW (struct used_part); |
c75ab022 DB |
3775 | up->minused = INT_MAX; |
3776 | up->maxused = 0; | |
31617ef1 DB |
3777 | up->explicit_uses = false; |
3778 | up->implicit_uses = false; | |
183596eb | 3779 | up->write_only = true; |
c75ab022 | 3780 | } |
a3648cfc | 3781 | |
c75ab022 DB |
3782 | return up; |
3783 | } | |
3784 | ||
31617ef1 | 3785 | |
3c0b6c43 | 3786 | /* Create and return a structure sub-variable for field type FIELD at |
3d9b47dc AN |
3787 | offset OFFSET, with size SIZE, of variable VAR. If ALIAS_SET not |
3788 | -1 this field is non-addressable and we should use this alias set | |
3789 | with this field. */ | |
e8ca4159 DN |
3790 | |
3791 | static tree | |
3c0b6c43 | 3792 | create_sft (tree var, tree field, unsigned HOST_WIDE_INT offset, |
d7705551 | 3793 | unsigned HOST_WIDE_INT size, alias_set_type alias_set, |
99739a3e | 3794 | bool base_for_components) |
e8ca4159 | 3795 | { |
35ed859b | 3796 | tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT"); |
e8ca4159 DN |
3797 | |
3798 | /* We need to copy the various flags from VAR to SUBVAR, so that | |
3799 | they are is_global_var iff the original variable was. */ | |
3800 | DECL_CONTEXT (subvar) = DECL_CONTEXT (var); | |
326eda4b | 3801 | MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var); |
e8ca4159 DN |
3802 | TREE_PUBLIC (subvar) = TREE_PUBLIC (var); |
3803 | TREE_STATIC (subvar) = TREE_STATIC (var); | |
3804 | TREE_READONLY (subvar) = TREE_READONLY (var); | |
c245c134 | 3805 | TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var); |
e8ca4159 DN |
3806 | |
3807 | /* Add the new variable to REFERENCED_VARS. */ | |
38635499 | 3808 | set_symbol_mem_tag (subvar, NULL); |
f004ab02 | 3809 | add_referenced_var (subvar); |
dff85230 | 3810 | SFT_PARENT_VAR (subvar) = var; |
3c0b6c43 DB |
3811 | SFT_OFFSET (subvar) = offset; |
3812 | SFT_SIZE (subvar) = size; | |
3d9b47dc | 3813 | SFT_ALIAS_SET (subvar) = alias_set; |
99739a3e RG |
3814 | SFT_BASE_FOR_COMPONENTS_P (subvar) = base_for_components; |
3815 | SFT_UNPARTITIONABLE_P (subvar) = false; | |
d7705551 | 3816 | |
e8ca4159 DN |
3817 | return subvar; |
3818 | } | |
3819 | ||
3820 | ||
c75ab022 DB |
3821 | /* Given an aggregate VAR, create the subvariables that represent its |
3822 | fields. */ | |
3823 | ||
3824 | static void | |
3825 | create_overlap_variables_for (tree var) | |
3826 | { | |
2845f02a | 3827 | VEC(fieldoff_s,heap) *fieldstack = NULL; |
c75ab022 | 3828 | used_part_t up; |
a3648cfc | 3829 | size_t uid = DECL_UID (var); |
c75ab022 | 3830 | |
183596eb RG |
3831 | up = up_lookup (uid); |
3832 | if (!up | |
3833 | || up->write_only) | |
c75ab022 DB |
3834 | return; |
3835 | ||
3d9b47dc | 3836 | push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL, |
99739a3e | 3837 | TREE_TYPE (var)); |
4a648c5d RG |
3838 | /* Make sure to not create SFTs for structs we won't generate variable |
3839 | infos for. See tree-ssa-structalias.c:create_variable_info_for (). */ | |
11948f6b | 3840 | if (VEC_length (fieldoff_s, fieldstack) > 1 |
4a648c5d | 3841 | && VEC_length (fieldoff_s, fieldstack) <= MAX_FIELDS_FOR_FIELD_SENSITIVE) |
c75ab022 DB |
3842 | { |
3843 | subvar_t *subvars; | |
2845f02a | 3844 | fieldoff_s *fo; |
c75ab022 | 3845 | bool notokay = false; |
31617ef1 | 3846 | int fieldcount = 0; |
c75ab022 | 3847 | int i; |
31617ef1 DB |
3848 | HOST_WIDE_INT lastfooffset = -1; |
3849 | HOST_WIDE_INT lastfosize = -1; | |
3850 | tree lastfotype = NULL_TREE; | |
c75ab022 DB |
3851 | |
3852 | /* Not all fields have DECL_SIZE set, and those that don't, we don't | |
3853 | know their size, and thus, can't handle. | |
3854 | The same is true of fields with DECL_SIZE that is not an integer | |
3855 | constant (such as variable sized fields). | |
3856 | Fields with offsets which are not constant will have an offset < 0 | |
3857 | We *could* handle fields that are constant sized arrays, but | |
3858 | currently don't. Doing so would require some extra changes to | |
3859 | tree-ssa-operands.c. */ | |
3860 | ||
2845f02a | 3861 | for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++) |
c75ab022 | 3862 | { |
35ed859b RG |
3863 | if (!fo->size |
3864 | || TREE_CODE (fo->size) != INTEGER_CST | |
c75ab022 DB |
3865 | || fo->offset < 0) |
3866 | { | |
3867 | notokay = true; | |
3868 | break; | |
3869 | } | |
31617ef1 | 3870 | fieldcount++; |
c75ab022 | 3871 | } |
31617ef1 DB |
3872 | |
3873 | /* The current heuristic we use is as follows: | |
3874 | If the variable has no used portions in this function, no | |
3875 | structure vars are created for it. | |
3876 | Otherwise, | |
3877 | If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS, | |
3878 | we always create structure vars for them. | |
3879 | If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and | |
3880 | some explicit uses, we create structure vars for them. | |
3881 | If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and | |
3882 | no explicit uses, we do not create structure vars for them. | |
3883 | */ | |
3884 | ||
3885 | if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS | |
3886 | && !up->explicit_uses) | |
3887 | { | |
3888 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
3889 | { | |
3890 | fprintf (dump_file, "Variable "); | |
3891 | print_generic_expr (dump_file, var, 0); | |
3892 | fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n"); | |
3893 | } | |
3894 | notokay = true; | |
3895 | } | |
3896 | ||
2845f02a | 3897 | /* Bail out, if we can't create overlap variables. */ |
c75ab022 DB |
3898 | if (notokay) |
3899 | { | |
2845f02a | 3900 | VEC_free (fieldoff_s, heap, fieldstack); |
c75ab022 DB |
3901 | return; |
3902 | } | |
2845f02a | 3903 | |
c75ab022 DB |
3904 | /* Otherwise, create the variables. */ |
3905 | subvars = lookup_subvars_for_var (var); | |
eee717aa RG |
3906 | *subvars = VEC_alloc (tree, gc, VEC_length (fieldoff_s, fieldstack)); |
3907 | ||
910fdc79 | 3908 | sort_fieldstack (fieldstack); |
31617ef1 | 3909 | |
eee717aa | 3910 | for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); ++i) |
c75ab022 | 3911 | { |
c75ab022 | 3912 | HOST_WIDE_INT fosize; |
eee717aa | 3913 | tree currfotype, subvar; |
c75ab022 | 3914 | |
35ed859b RG |
3915 | fosize = TREE_INT_CST_LOW (fo->size); |
3916 | currfotype = fo->type; | |
31617ef1 DB |
3917 | |
3918 | /* If this field isn't in the used portion, | |
3919 | or it has the exact same offset and size as the last | |
7b765bed DB |
3920 | field, skip it. Note that we always need the field at |
3921 | offset 0 so we can properly handle pointers to the | |
3922 | structure. */ | |
99739a3e | 3923 | |
7b765bed DB |
3924 | if ((fo->offset != 0 |
3925 | && ((fo->offset <= up->minused | |
3926 | && fo->offset + fosize <= up->minused) | |
3927 | || fo->offset >= up->maxused)) | |
31617ef1 DB |
3928 | || (fo->offset == lastfooffset |
3929 | && fosize == lastfosize | |
3930 | && currfotype == lastfotype)) | |
2845f02a | 3931 | continue; |
99739a3e RG |
3932 | subvar = create_sft (var, fo->type, fo->offset, |
3933 | fosize, fo->alias_set, fo->base_for_components); | |
eee717aa | 3934 | VEC_quick_push (tree, *subvars, subvar); |
e8ca4159 | 3935 | |
c75ab022 DB |
3936 | if (dump_file) |
3937 | { | |
3938 | fprintf (dump_file, "structure field tag %s created for var %s", | |
eee717aa | 3939 | get_name (subvar), get_name (var)); |
c75ab022 | 3940 | fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC, |
eee717aa | 3941 | SFT_OFFSET (subvar)); |
c75ab022 | 3942 | fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC, |
eee717aa | 3943 | SFT_SIZE (subvar)); |
99739a3e | 3944 | fprintf (dump_file, "\n"); |
c75ab022 DB |
3945 | } |
3946 | ||
31617ef1 DB |
3947 | lastfotype = currfotype; |
3948 | lastfooffset = fo->offset; | |
3949 | lastfosize = fosize; | |
c75ab022 | 3950 | } |
d19e9499 DB |
3951 | |
3952 | /* Once we have created subvars, the original is no longer call | |
3953 | clobbered on its own. Its call clobbered status depends | |
3954 | completely on the call clobbered status of the subvars. | |
3955 | ||
3956 | add_referenced_var in the above loop will take care of | |
3957 | marking subvars of global variables as call clobbered for us | |
3958 | to start, since they are global as well. */ | |
3959 | clear_call_clobbered (var); | |
c75ab022 | 3960 | } |
d19e9499 | 3961 | |
2845f02a | 3962 | VEC_free (fieldoff_s, heap, fieldstack); |
c75ab022 DB |
3963 | } |
3964 | ||
3965 | ||
3966 | /* Find the conservative answer to the question of what portions of what | |
3967 | structures are used by this statement. We assume that if we have a | |
3968 | component ref with a known size + offset, that we only need that part | |
3969 | of the structure. For unknown cases, or cases where we do something | |
3970 | to the whole structure, we assume we need to create fields for the | |
3971 | entire structure. */ | |
3972 | ||
3973 | static tree | |
183596eb | 3974 | find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p) |
c75ab022 DB |
3975 | { |
3976 | switch (TREE_CODE (*tp)) | |
3977 | { | |
07beea0d | 3978 | case GIMPLE_MODIFY_STMT: |
183596eb RG |
3979 | /* Recurse manually here to track whether the use is in the |
3980 | LHS of an assignment. */ | |
07beea0d AH |
3981 | find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 0), walk_subtrees, tp); |
3982 | return find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 1), | |
3983 | walk_subtrees, NULL); | |
8ae5e6f2 AP |
3984 | case REALPART_EXPR: |
3985 | case IMAGPART_EXPR: | |
c75ab022 | 3986 | case COMPONENT_REF: |
a916f21d | 3987 | case ARRAY_REF: |
c75ab022 DB |
3988 | { |
3989 | HOST_WIDE_INT bitsize; | |
6bec9271 | 3990 | HOST_WIDE_INT bitmaxsize; |
c75ab022 | 3991 | HOST_WIDE_INT bitpos; |
c75ab022 | 3992 | tree ref; |
6bec9271 RG |
3993 | ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize); |
3994 | if (DECL_P (ref) | |
3995 | && var_can_have_subvars (ref) | |
3996 | && bitmaxsize != -1) | |
3997 | { | |
a3648cfc | 3998 | size_t uid = DECL_UID (ref); |
c75ab022 DB |
3999 | used_part_t up; |
4000 | ||
4001 | up = get_or_create_used_part_for (uid); | |
4002 | ||
4003 | if (bitpos <= up->minused) | |
4004 | up->minused = bitpos; | |
6bec9271 RG |
4005 | if ((bitpos + bitmaxsize >= up->maxused)) |
4006 | up->maxused = bitpos + bitmaxsize; | |
c75ab022 | 4007 | |
6bec9271 RG |
4008 | if (bitsize == bitmaxsize) |
4009 | up->explicit_uses = true; | |
4010 | else | |
4011 | up->implicit_uses = true; | |
183596eb RG |
4012 | if (!lhs_p) |
4013 | up->write_only = false; | |
a3648cfc | 4014 | up_insert (uid, up); |
c75ab022 DB |
4015 | |
4016 | *walk_subtrees = 0; | |
4017 | return NULL_TREE; | |
4018 | } | |
c75ab022 DB |
4019 | } |
4020 | break; | |
a5eadacc DB |
4021 | /* This is here to make sure we mark the entire base variable as used |
4022 | when you take its address. Because our used portion analysis is | |
4023 | simple, we aren't looking at casts or pointer arithmetic to see what | |
4024 | happens when you take the address. */ | |
4025 | case ADDR_EXPR: | |
4026 | { | |
4027 | tree var = get_base_address (TREE_OPERAND (*tp, 0)); | |
4028 | ||
4029 | if (var | |
4030 | && DECL_P (var) | |
4031 | && DECL_SIZE (var) | |
4032 | && var_can_have_subvars (var) | |
4033 | && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) | |
4034 | { | |
4035 | used_part_t up; | |
a3648cfc | 4036 | size_t uid = DECL_UID (var); |
a5eadacc DB |
4037 | |
4038 | up = get_or_create_used_part_for (uid); | |
4039 | ||
4040 | up->minused = 0; | |
4041 | up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); | |
4042 | up->implicit_uses = true; | |
62c577fd RG |
4043 | if (!lhs_p) |
4044 | up->write_only = false; | |
a5eadacc | 4045 | |
a3648cfc | 4046 | up_insert (uid, up); |
a5eadacc DB |
4047 | *walk_subtrees = 0; |
4048 | return NULL_TREE; | |
4049 | } | |
4050 | } | |
4051 | break; | |
651402f1 RG |
4052 | case CALL_EXPR: |
4053 | { | |
5039610b SL |
4054 | int i; |
4055 | int nargs = call_expr_nargs (*tp); | |
4056 | for (i = 0; i < nargs; i++) | |
651402f1 | 4057 | { |
5039610b | 4058 | tree *arg = &CALL_EXPR_ARG (*tp, i); |
11df3da3 | 4059 | if (TREE_CODE (*arg) == ADDR_EXPR) |
5039610b | 4060 | find_used_portions (arg, walk_subtrees, NULL); |
651402f1 RG |
4061 | } |
4062 | *walk_subtrees = 0; | |
4063 | return NULL_TREE; | |
4064 | } | |
c75ab022 DB |
4065 | case VAR_DECL: |
4066 | case PARM_DECL: | |
098209a9 | 4067 | case RESULT_DECL: |
c75ab022 DB |
4068 | { |
4069 | tree var = *tp; | |
4070 | if (DECL_SIZE (var) | |
4071 | && var_can_have_subvars (var) | |
4072 | && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) | |
4073 | { | |
4074 | used_part_t up; | |
a3648cfc | 4075 | size_t uid = DECL_UID (var); |
c75ab022 DB |
4076 | |
4077 | up = get_or_create_used_part_for (uid); | |
4078 | ||
4079 | up->minused = 0; | |
4080 | up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var)); | |
31617ef1 | 4081 | up->implicit_uses = true; |
c75ab022 | 4082 | |
a3648cfc | 4083 | up_insert (uid, up); |
c75ab022 DB |
4084 | *walk_subtrees = 0; |
4085 | return NULL_TREE; | |
4086 | } | |
4087 | } | |
4088 | break; | |
4089 | ||
4090 | default: | |
4091 | break; | |
4092 | ||
4093 | } | |
4094 | return NULL_TREE; | |
4095 | } | |
4096 | ||
c75ab022 DB |
4097 | /* Create structure field variables for structures used in this function. */ |
4098 | ||
c2924966 | 4099 | static unsigned int |
c75ab022 DB |
4100 | create_structure_vars (void) |
4101 | { | |
4102 | basic_block bb; | |
b9d33488 DB |
4103 | safe_referenced_var_iterator rvi; |
4104 | VEC (tree, heap) *varvec = NULL; | |
a3648cfc | 4105 | tree var; |
c75ab022 | 4106 | |
a3648cfc DB |
4107 | used_portions = htab_create (10, used_part_map_hash, used_part_map_eq, |
4108 | free_used_part_map); | |
c75ab022 DB |
4109 | |
4110 | FOR_EACH_BB (bb) | |
4111 | { | |
4112 | block_stmt_iterator bsi; | |
7b765bed DB |
4113 | tree phi; |
4114 | ||
4115 | for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) | |
4116 | { | |
4117 | use_operand_p use; | |
4118 | ssa_op_iter iter; | |
4119 | ||
4120 | FOR_EACH_PHI_ARG (use, phi, iter, SSA_OP_USE) | |
4121 | { | |
4122 | tree op = USE_FROM_PTR (use); | |
4123 | walk_tree_without_duplicates (&op, find_used_portions, | |
4124 | NULL); | |
4125 | } | |
4126 | } | |
4127 | ||
c75ab022 DB |
4128 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) |
4129 | { | |
4130 | walk_tree_without_duplicates (bsi_stmt_ptr (bsi), | |
4131 | find_used_portions, | |
4132 | NULL); | |
4133 | } | |
4134 | } | |
b9d33488 | 4135 | FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi) |
c75ab022 | 4136 | { |
c75ab022 DB |
4137 | /* The C++ FE creates vars without DECL_SIZE set, for some reason. */ |
4138 | if (var | |
4139 | && DECL_SIZE (var) | |
4140 | && var_can_have_subvars (var) | |
326eda4b | 4141 | && !MTAG_P (var) |
c75ab022 DB |
4142 | && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST) |
4143 | create_overlap_variables_for (var); | |
4144 | } | |
a3648cfc | 4145 | htab_delete (used_portions); |
b9d33488 | 4146 | VEC_free (tree, heap, varvec); |
d586d6d1 | 4147 | |
d60ab196 | 4148 | /* Update SSA operands of statements mentioning variables we split. */ |
d586d6d1 JH |
4149 | if (gimple_in_ssa_p (cfun)) |
4150 | FOR_EACH_BB (bb) | |
4151 | { | |
4152 | block_stmt_iterator bsi; | |
4153 | for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) | |
4154 | { | |
4155 | tree stmt = bsi_stmt (bsi); | |
4156 | bool update = false; | |
4157 | unsigned int i; | |
4158 | bitmap_iterator bi; | |
4159 | ||
4160 | if (STORED_SYMS (stmt)) | |
4161 | EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi) | |
4162 | { | |
4163 | tree sym = referenced_var_lookup (i); | |
4164 | if (get_subvars_for_var (sym)) | |
4165 | { | |
7b765bed | 4166 | update = true; |
d586d6d1 JH |
4167 | break; |
4168 | } | |
4169 | } | |
4170 | ||
4171 | if (LOADED_SYMS (stmt) && !update) | |
4172 | EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi) | |
4173 | { | |
4174 | tree sym = referenced_var_lookup (i); | |
4175 | if (get_subvars_for_var (sym)) | |
4176 | { | |
7b765bed | 4177 | update = true; |
d586d6d1 JH |
4178 | break; |
4179 | } | |
4180 | } | |
4181 | ||
4182 | if (stmt_ann (stmt)->addresses_taken && !update) | |
4183 | EXECUTE_IF_SET_IN_BITMAP (stmt_ann (stmt)->addresses_taken, | |
4184 | 0, i, bi) | |
4185 | { | |
4186 | tree sym = referenced_var_lookup (i); | |
4187 | if (get_subvars_for_var (sym)) | |
4188 | { | |
7b765bed | 4189 | update = true; |
d586d6d1 JH |
4190 | break; |
4191 | } | |
4192 | } | |
4193 | ||
4194 | if (update) | |
4195 | update_stmt (stmt); | |
4196 | } | |
4197 | } | |
79bedddc | 4198 | |
7b0e48fb | 4199 | return TODO_rebuild_alias; |
c75ab022 DB |
4200 | } |
4201 | ||
4202 | static bool | |
4203 | gate_structure_vars (void) | |
4204 | { | |
4205 | return flag_tree_salias != 0; | |
4206 | } | |
4207 | ||
4208 | struct tree_opt_pass pass_create_structure_vars = | |
4209 | { | |
4210 | "salias", /* name */ | |
4211 | gate_structure_vars, /* gate */ | |
4212 | create_structure_vars, /* execute */ | |
4213 | NULL, /* sub */ | |
4214 | NULL, /* next */ | |
4215 | 0, /* static_pass_number */ | |
4216 | 0, /* tv_id */ | |
4217 | PROP_cfg, /* properties_required */ | |
4218 | 0, /* properties_provided */ | |
4219 | 0, /* properties_destroyed */ | |
4220 | 0, /* todo_flags_start */ | |
4221 | TODO_dump_func, /* todo_flags_finish */ | |
4222 | 0 /* letter */ | |
4223 | }; | |
fe1f8f44 | 4224 | |
b730fa61 | 4225 | /* Reset the call_clobbered flags on our referenced vars. In |
fe1f8f44 DB |
4226 | theory, this only needs to be done for globals. */ |
4227 | ||
4228 | static unsigned int | |
4229 | reset_cc_flags (void) | |
4230 | { | |
4231 | tree var; | |
4232 | referenced_var_iterator rvi; | |
4233 | ||
4234 | FOR_EACH_REFERENCED_VAR (var, rvi) | |
b730fa61 | 4235 | var_ann (var)->call_clobbered = false; |
fe1f8f44 DB |
4236 | return 0; |
4237 | } | |
4238 | ||
4239 | struct tree_opt_pass pass_reset_cc_flags = | |
4240 | { | |
4241 | NULL, /* name */ | |
4242 | NULL, /* gate */ | |
4243 | reset_cc_flags, /* execute */ | |
4244 | NULL, /* sub */ | |
4245 | NULL, /* next */ | |
4246 | 0, /* static_pass_number */ | |
4247 | 0, /* tv_id */ | |
4248 | PROP_referenced_vars |PROP_cfg, /* properties_required */ | |
4249 | 0, /* properties_provided */ | |
4250 | 0, /* properties_destroyed */ | |
4251 | 0, /* todo_flags_start */ | |
4252 | 0, /* todo_flags_finish */ | |
4253 | 0 /* letter */ | |
4254 | }; | |
f9d02384 MLI |
4255 | |
4256 | static bool | |
4257 | gate_build_alias (void) | |
4258 | { | |
4259 | return !gate_structure_vars(); | |
4260 | } | |
4261 | ||
4262 | ||
4263 | struct tree_opt_pass pass_build_alias = | |
4264 | { | |
4265 | "build_alias", /* name */ | |
4266 | gate_build_alias, /* gate */ | |
4267 | NULL, /* execute */ | |
4268 | NULL, /* sub */ | |
4269 | NULL, /* next */ | |
4270 | 0, /* static_pass_number */ | |
4271 | 0, /* tv_id */ | |
4272 | PROP_cfg | PROP_ssa, /* properties_required */ | |
4273 | PROP_alias, /* properties_provided */ | |
4274 | 0, /* properties_destroyed */ | |
4275 | 0, /* todo_flags_start */ | |
4276 | TODO_rebuild_alias, /* todo_flags_finish */ | |
4277 | 0 /* letter */ | |
4278 | }; |