* var-tracking.c (insn_stack_adjust_offset_pre_post): If insn has a
[official-gcc.git] / gcc / tree-ssa-alias.c
blob655056b53f7a0f2ca1622b7d56ce58b1147f05fd
1 /* Alias analysis for trees.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
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.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
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"
38 #include "gimple.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
41 #include "tree-pass.h"
42 #include "tree-ssa-structalias.h"
43 #include "convert.h"
44 #include "params.h"
45 #include "ipa-type-escape.h"
46 #include "vec.h"
47 #include "bitmap.h"
48 #include "vecprim.h"
49 #include "pointer-set.h"
50 #include "alloc-pool.h"
52 /* Broad overview of how aliasing works:
54 First we compute points-to sets, which is done in
55 tree-ssa-structalias.c
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.
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.
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.
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.
86 These are eliminated in a later phase, as we will see.
88 The rest of the phases are located in tree-ssa-alias.c
90 The next phase after points-to set computation is called
91 "setup_pointers_and_addressables"
93 This pass does 3 main things:
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.
105 After this function is run, all variables that will ever have an
106 SMT, have one, though its aliases are not filled in.
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.
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.
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.
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.
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.
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.
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.
163 After this, memory partitioning is computed (by the function
164 compute_memory_partitions) and alias sets are reworked accordingly.
166 Lastly, we delete partitions with no symbols, and clean up after
167 ourselves. */
170 /* Alias information used by compute_may_aliases and its helpers. */
171 struct alias_info
173 /* SSA names visited while collecting points-to information. If bit I
174 is set, it means that SSA variable with version I has already been
175 visited. */
176 sbitmap ssa_names_visited;
178 /* Array of SSA_NAME pointers processed by the points-to collector. */
179 VEC(tree,heap) *processed_ptrs;
181 /* ADDRESSABLE_VARS contains all the global variables and locals that
182 have had their address taken. */
183 struct alias_map_d **addressable_vars;
184 size_t num_addressable_vars;
186 /* POINTERS contains all the _DECL pointers with unique memory tags
187 that have been referenced in the program. */
188 struct alias_map_d **pointers;
189 size_t num_pointers;
191 /* Variables that have been written to directly (i.e., not through a
192 pointer dereference). */
193 struct pointer_set_t *written_vars;
195 /* Pointers that have been used in an indirect store operation. */
196 struct pointer_set_t *dereferenced_ptrs_store;
198 /* Pointers that have been used in an indirect load operation. */
199 struct pointer_set_t *dereferenced_ptrs_load;
203 /* Structure to map a variable to its alias set. */
204 struct alias_map_d
206 /* Variable and its alias set. */
207 tree var;
208 alias_set_type set;
212 /* Counters used to display statistics on alias analysis. */
213 struct alias_stats_d
215 unsigned int alias_queries;
216 unsigned int alias_mayalias;
217 unsigned int alias_noalias;
218 unsigned int simple_queries;
219 unsigned int simple_resolved;
220 unsigned int tbaa_queries;
221 unsigned int tbaa_resolved;
222 unsigned int structnoaddress_queries;
223 unsigned int structnoaddress_resolved;
227 /* Local variables. */
228 static struct alias_stats_d alias_stats;
229 static bitmap_obstack alias_bitmap_obstack;
231 /* Local functions. */
232 static void compute_flow_insensitive_aliasing (struct alias_info *);
233 static void dump_alias_stats (FILE *);
234 static tree create_memory_tag (tree type, bool is_type_tag);
235 static tree get_smt_for (tree, struct alias_info *);
236 static tree get_nmt_for (tree);
237 static void add_may_alias (tree, tree);
238 static struct alias_info *init_alias_info (void);
239 static void delete_alias_info (struct alias_info *);
240 static void compute_flow_sensitive_aliasing (struct alias_info *);
241 static void setup_pointers_and_addressables (struct alias_info *);
242 static void update_alias_info (struct alias_info *);
243 static void create_global_var (void);
244 static void maybe_create_global_var (void);
245 static void set_pt_anything (tree);
247 void debug_mp_info (VEC(mem_sym_stats_t,heap) *);
249 static alloc_pool mem_sym_stats_pool;
251 /* Return memory reference stats for symbol VAR. Create a new slot in
252 cfun->gimple_df->mem_sym_stats if needed. */
254 static struct mem_sym_stats_d *
255 get_mem_sym_stats_for (tree var)
257 void **slot;
258 struct mem_sym_stats_d *stats;
259 struct pointer_map_t *map = gimple_mem_ref_stats (cfun)->mem_sym_stats;
261 gcc_assert (map);
263 slot = pointer_map_insert (map, var);
264 if (*slot == NULL)
266 stats = (struct mem_sym_stats_d *) pool_alloc (mem_sym_stats_pool);
267 memset (stats, 0, sizeof (*stats));
268 stats->var = var;
269 *slot = (void *) stats;
271 else
272 stats = (struct mem_sym_stats_d *) *slot;
274 return stats;
278 /* Return memory reference statistics for variable VAR in function FN.
279 This is computed by alias analysis, but it is not kept
280 incrementally up-to-date. So, these stats are only accurate if
281 pass_may_alias has been run recently. If no alias information
282 exists, this function returns NULL. */
284 static mem_sym_stats_t
285 mem_sym_stats (struct function *fn, tree var)
287 void **slot;
288 struct pointer_map_t *stats_map = gimple_mem_ref_stats (fn)->mem_sym_stats;
290 if (stats_map == NULL)
291 return NULL;
293 slot = pointer_map_contains (stats_map, var);
294 if (slot == NULL)
295 return NULL;
297 return (mem_sym_stats_t) *slot;
301 /* Set MPT to be the memory partition associated with symbol SYM. */
303 static inline void
304 set_memory_partition (tree sym, tree mpt)
306 #if defined ENABLE_CHECKING
307 if (mpt)
308 gcc_assert (TREE_CODE (mpt) == MEMORY_PARTITION_TAG
309 && !is_gimple_reg (sym));
310 #endif
312 var_ann (sym)->mpt = mpt;
313 if (mpt)
315 if (MPT_SYMBOLS (mpt) == NULL)
316 MPT_SYMBOLS (mpt) = BITMAP_ALLOC (&alias_bitmap_obstack);
318 bitmap_set_bit (MPT_SYMBOLS (mpt), DECL_UID (sym));
320 /* MPT inherits the call-clobbering attributes from SYM. */
321 if (is_call_clobbered (sym))
323 MTAG_GLOBAL (mpt) = 1;
324 mark_call_clobbered (mpt, ESCAPE_IS_GLOBAL);
330 /* Mark variable VAR as being non-addressable. */
332 static void
333 mark_non_addressable (tree var)
335 tree mpt;
337 if (!TREE_ADDRESSABLE (var))
338 return;
340 mpt = memory_partition (var);
342 clear_call_clobbered (var);
343 TREE_ADDRESSABLE (var) = 0;
345 if (mpt)
347 /* Note that it's possible for a symbol to have an associated
348 MPT and the MPT have a NULL empty set. During
349 init_alias_info, all MPTs get their sets cleared out, but the
350 symbols still point to the old MPTs that used to hold them.
351 This is done so that compute_memory_partitions can now which
352 symbols are losing or changing partitions and mark them for
353 renaming. */
354 if (MPT_SYMBOLS (mpt))
355 bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var));
356 set_memory_partition (var, NULL_TREE);
361 /* qsort comparison function to sort type/name tags by DECL_UID. */
363 static int
364 sort_tags_by_id (const void *pa, const void *pb)
366 const_tree const a = *(const_tree const *)pa;
367 const_tree const b = *(const_tree const *)pb;
369 return DECL_UID (a) - DECL_UID (b);
372 /* Initialize WORKLIST to contain those memory tags that are marked call
373 clobbered. Initialized WORKLIST2 to contain the reasons these
374 memory tags escaped. */
376 static void
377 init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
378 VEC (int, heap) **worklist2,
379 bitmap on_worklist)
381 referenced_var_iterator rvi;
382 tree curr;
384 FOR_EACH_REFERENCED_VAR (curr, rvi)
386 if (MTAG_P (curr) && is_call_clobbered (curr))
388 VEC_safe_push (tree, heap, *worklist, curr);
389 VEC_safe_push (int, heap, *worklist2,
390 var_ann (curr)->escape_mask);
391 bitmap_set_bit (on_worklist, DECL_UID (curr));
396 /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
397 ALIAS is not already marked call clobbered, and is a memory
398 tag. */
400 static void
401 add_to_worklist (tree alias, VEC (tree, heap) **worklist,
402 VEC (int, heap) **worklist2, int reason,
403 bitmap on_worklist)
405 if (MTAG_P (alias) && !is_call_clobbered (alias)
406 && !bitmap_bit_p (on_worklist, DECL_UID (alias)))
408 VEC_safe_push (tree, heap, *worklist, alias);
409 VEC_safe_push (int, heap, *worklist2, reason);
410 bitmap_set_bit (on_worklist, DECL_UID (alias));
414 /* Mark aliases of TAG as call clobbered, and place any tags on the
415 alias list that were not already call clobbered on WORKLIST. */
417 static void
418 mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
419 VEC (int, heap) **worklist2, bitmap on_worklist)
421 bitmap aliases;
422 bitmap_iterator bi;
423 unsigned int i;
424 tree entry;
425 var_ann_t ta = var_ann (tag);
427 if (!MTAG_P (tag))
428 return;
429 aliases = may_aliases (tag);
430 if (!aliases)
431 return;
433 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
435 entry = referenced_var (i);
436 /* If you clobber one part of a structure, you
437 clobber the entire thing. While this does not make
438 the world a particularly nice place, it is necessary
439 in order to allow C/C++ tricks that involve
440 pointer arithmetic to work. */
441 if (!unmodifiable_var_p (entry))
443 add_to_worklist (entry, worklist, worklist2, ta->escape_mask,
444 on_worklist);
445 mark_call_clobbered (entry, ta->escape_mask);
450 /* Tags containing global vars need to be marked as global.
451 Tags containing call clobbered vars need to be marked as call
452 clobbered. */
454 static void
455 compute_tag_properties (void)
457 referenced_var_iterator rvi;
458 tree tag;
459 bool changed = true;
460 VEC (tree, heap) *taglist = NULL;
462 FOR_EACH_REFERENCED_VAR (tag, rvi)
464 if (!MTAG_P (tag))
465 continue;
466 VEC_safe_push (tree, heap, taglist, tag);
469 /* We sort the taglist by DECL_UID, for two reasons.
470 1. To get a sequential ordering to make the bitmap accesses
471 faster.
472 2. Because of the way we compute aliases, it's more likely that
473 an earlier tag is included in a later tag, and this will reduce
474 the number of iterations.
476 If we had a real tag graph, we would just topo-order it and be
477 done with it. */
478 qsort (VEC_address (tree, taglist),
479 VEC_length (tree, taglist),
480 sizeof (tree),
481 sort_tags_by_id);
483 /* Go through each tag not marked as global, and if it aliases
484 global vars, mark it global.
486 If the tag contains call clobbered vars, mark it call
487 clobbered.
489 This loop iterates because tags may appear in the may-aliases
490 list of other tags when we group. */
492 while (changed)
494 unsigned int k;
496 changed = false;
497 for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
499 bitmap ma;
500 bitmap_iterator bi;
501 unsigned int i;
502 tree entry;
503 bool tagcc = is_call_clobbered (tag);
504 bool tagglobal = MTAG_GLOBAL (tag);
506 if (tagcc && tagglobal)
507 continue;
509 ma = may_aliases (tag);
510 if (!ma)
511 continue;
513 EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi)
515 entry = referenced_var (i);
516 /* Call clobbered entries cause the tag to be marked
517 call clobbered. */
518 if (!tagcc && is_call_clobbered (entry))
520 mark_call_clobbered (tag, var_ann (entry)->escape_mask);
521 tagcc = true;
522 changed = true;
525 /* Global vars cause the tag to be marked global. */
526 if (!tagglobal && is_global_var (entry))
528 MTAG_GLOBAL (tag) = true;
529 changed = true;
530 tagglobal = true;
533 /* Early exit once both global and cc are set, since the
534 loop can't do any more than that. */
535 if (tagcc && tagglobal)
536 break;
540 VEC_free (tree, heap, taglist);
543 /* Set up the initial variable clobbers, call-uses and globalness.
544 When this function completes, only tags whose aliases need to be
545 clobbered will be set clobbered. Tags clobbered because they
546 contain call clobbered vars are handled in compute_tag_properties. */
548 static void
549 set_initial_properties (struct alias_info *ai)
551 unsigned int i;
552 referenced_var_iterator rvi;
553 tree var;
554 tree ptr;
555 bool any_pt_anything = false;
556 enum escape_type pt_anything_mask = 0;
558 FOR_EACH_REFERENCED_VAR (var, rvi)
560 if (is_global_var (var))
562 if (!unmodifiable_var_p (var))
563 mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
565 else if (TREE_CODE (var) == PARM_DECL
566 && gimple_default_def (cfun, var)
567 && POINTER_TYPE_P (TREE_TYPE (var)))
569 tree def = gimple_default_def (cfun, var);
570 get_ptr_info (def)->value_escapes_p = 1;
571 get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
575 if (!clobber_what_escaped ())
577 any_pt_anything = true;
578 pt_anything_mask |= ESCAPE_TO_CALL;
581 compute_call_used_vars ();
583 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
585 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
586 tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
588 /* A pointer that only escapes via a function return does not
589 add to the call clobber or call used solution.
590 To exclude ESCAPE_TO_PURE_CONST we would need to track
591 call used variables separately or compute those properly
592 in the operand scanner. */
593 if (pi->value_escapes_p
594 && pi->escape_mask & ~ESCAPE_TO_RETURN)
596 /* If PTR escapes then its associated memory tags and
597 pointed-to variables are call-clobbered. */
598 if (pi->name_mem_tag)
599 mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
601 if (tag)
602 mark_call_clobbered (tag, pi->escape_mask);
605 /* If the name tag is call clobbered, so is the symbol tag
606 associated with the base VAR_DECL. */
607 if (pi->name_mem_tag
608 && tag
609 && is_call_clobbered (pi->name_mem_tag))
610 mark_call_clobbered (tag, pi->escape_mask);
612 /* Name tags and symbol tags that we don't know where they point
613 to, might point to global memory, and thus, are clobbered.
615 FIXME: This is not quite right. They should only be
616 clobbered if value_escapes_p is true, regardless of whether
617 they point to global memory or not.
618 So removing this code and fixing all the bugs would be nice.
619 It is the cause of a bunch of clobbering. */
620 if ((pi->pt_global_mem || pi->pt_anything)
621 && pi->memory_tag_needed && pi->name_mem_tag)
623 mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
624 MTAG_GLOBAL (pi->name_mem_tag) = true;
627 if ((pi->pt_global_mem || pi->pt_anything)
628 && pi->memory_tag_needed
629 && tag)
631 mark_call_clobbered (tag, ESCAPE_IS_GLOBAL);
632 MTAG_GLOBAL (tag) = true;
636 /* If a pt_anything pointer escaped we need to mark all addressable
637 variables call clobbered. */
638 if (any_pt_anything)
640 bitmap_iterator bi;
641 unsigned int j;
643 EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, j, bi)
645 tree var = referenced_var (j);
646 if (!unmodifiable_var_p (var))
647 mark_call_clobbered (var, pt_anything_mask);
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. */
656 static void
657 compute_call_clobbered (struct alias_info *ai)
659 VEC (tree, heap) *worklist = NULL;
660 VEC (int,heap) *worklist2 = NULL;
661 bitmap on_worklist;
663 timevar_push (TV_CALL_CLOBBER);
664 on_worklist = BITMAP_ALLOC (NULL);
666 set_initial_properties (ai);
667 init_transitive_clobber_worklist (&worklist, &worklist2, on_worklist);
668 while (VEC_length (tree, worklist) != 0)
670 tree curr = VEC_pop (tree, worklist);
671 int reason = VEC_pop (int, worklist2);
673 bitmap_clear_bit (on_worklist, DECL_UID (curr));
674 mark_call_clobbered (curr, reason);
675 mark_aliases_call_clobbered (curr, &worklist, &worklist2, on_worklist);
677 VEC_free (tree, heap, worklist);
678 VEC_free (int, heap, worklist2);
679 BITMAP_FREE (on_worklist);
680 compute_tag_properties ();
681 timevar_pop (TV_CALL_CLOBBER);
685 /* Dump memory partition information to FILE. */
687 static void
688 dump_memory_partitions (FILE *file)
690 unsigned i, npart;
691 unsigned long nsyms;
692 tree mpt;
694 fprintf (file, "\nMemory partitions\n\n");
695 for (i = 0, npart = 0, nsyms = 0;
696 VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, i, mpt);
697 i++)
699 if (mpt)
701 bitmap syms = MPT_SYMBOLS (mpt);
702 unsigned long n = (syms) ? bitmap_count_bits (syms) : 0;
704 fprintf (file, "#%u: ", i);
705 print_generic_expr (file, mpt, 0);
706 fprintf (file, ": %lu elements: ", n);
707 dump_decl_set (file, syms);
708 npart++;
709 nsyms += n;
713 fprintf (file, "\n%u memory partitions holding %lu symbols\n", npart, nsyms);
717 /* Dump memory partition information to stderr. */
719 void
720 debug_memory_partitions (void)
722 dump_memory_partitions (stderr);
726 /* Return true if memory partitioning is required given the memory
727 reference estimates in STATS. */
729 static inline bool
730 need_to_partition_p (struct mem_ref_stats_d *stats)
732 long num_vops = stats->num_vuses + stats->num_vdefs;
733 long avg_vops = CEIL (num_vops, stats->num_mem_stmts);
734 return (num_vops > (long) MAX_ALIASED_VOPS
735 && avg_vops > (long) AVG_ALIASED_VOPS);
739 /* Count the actual number of virtual operators in CFUN. Note that
740 this is only meaningful after virtual operands have been populated,
741 so it should be invoked at the end of compute_may_aliases.
743 The number of virtual operators are stored in *NUM_VDEFS_P and
744 *NUM_VUSES_P, the number of partitioned symbols in
745 *NUM_PARTITIONED_P and the number of unpartitioned symbols in
746 *NUM_UNPARTITIONED_P.
748 If any of these pointers is NULL the corresponding count is not
749 computed. */
751 static void
752 count_mem_refs (long *num_vuses_p, long *num_vdefs_p,
753 long *num_partitioned_p, long *num_unpartitioned_p)
755 gimple_stmt_iterator gsi;
756 basic_block bb;
757 long num_vdefs, num_vuses, num_partitioned, num_unpartitioned;
758 referenced_var_iterator rvi;
759 tree sym;
761 num_vuses = num_vdefs = num_partitioned = num_unpartitioned = 0;
763 if (num_vuses_p || num_vdefs_p)
764 FOR_EACH_BB (bb)
765 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
767 gimple stmt = gsi_stmt (gsi);
768 if (gimple_references_memory_p (stmt))
770 num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
771 num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
775 if (num_partitioned_p || num_unpartitioned_p)
776 FOR_EACH_REFERENCED_VAR (sym, rvi)
778 if (is_gimple_reg (sym))
779 continue;
781 if (memory_partition (sym))
782 num_partitioned++;
783 else
784 num_unpartitioned++;
787 if (num_vdefs_p)
788 *num_vdefs_p = num_vdefs;
790 if (num_vuses_p)
791 *num_vuses_p = num_vuses;
793 if (num_partitioned_p)
794 *num_partitioned_p = num_partitioned;
796 if (num_unpartitioned_p)
797 *num_unpartitioned_p = num_unpartitioned;
801 /* The list is sorted by increasing partitioning score (PSCORE).
802 This score is computed such that symbols with high scores are
803 those that are least likely to be partitioned. Given a symbol
804 MP->VAR, PSCORE(S) is the result of the following weighted sum
806 PSCORE(S) = FW * 64 + FR * 32
807 + DW * 16 + DR * 8
808 + IW * 4 + IR * 2
809 + NO_ALIAS
811 where
813 FW Execution frequency of writes to S
814 FR Execution frequency of reads from S
815 DW Number of direct writes to S
816 DR Number of direct reads from S
817 IW Number of indirect writes to S
818 IR Number of indirect reads from S
819 NO_ALIAS State of the NO_ALIAS* flags
821 The basic idea here is that symbols that are frequently
822 written-to in hot paths of the code are the last to be considered
823 for partitioning. */
825 static inline long
826 mem_sym_score (mem_sym_stats_t mp)
828 return mp->frequency_writes * 64 + mp->frequency_reads * 32
829 + mp->num_direct_writes * 16 + mp->num_direct_reads * 8
830 + mp->num_indirect_writes * 4 + mp->num_indirect_reads * 2
831 + var_ann (mp->var)->noalias_state;
835 /* Dump memory reference stats for function CFUN to FILE. */
837 void
838 dump_mem_ref_stats (FILE *file)
840 long actual_num_vuses, actual_num_vdefs;
841 long num_partitioned, num_unpartitioned;
842 struct mem_ref_stats_d *stats;
844 stats = gimple_mem_ref_stats (cfun);
846 count_mem_refs (&actual_num_vuses, &actual_num_vdefs, &num_partitioned,
847 &num_unpartitioned);
849 fprintf (file, "\nMemory reference statistics for %s\n\n",
850 lang_hooks.decl_printable_name (current_function_decl, 2));
852 fprintf (file, "Number of memory statements: %ld\n",
853 stats->num_mem_stmts);
854 fprintf (file, "Number of call sites: %ld\n",
855 stats->num_call_sites);
856 fprintf (file, "Number of pure/const call sites: %ld\n",
857 stats->num_pure_const_call_sites);
858 fprintf (file, "Number of asm sites: %ld\n",
859 stats->num_asm_sites);
860 fprintf (file, "Estimated number of loads: %ld (%ld/stmt)\n",
861 stats->num_vuses,
862 (stats->num_mem_stmts)
863 ? CEIL (stats->num_vuses, stats->num_mem_stmts)
864 : 0);
865 fprintf (file, "Actual number of loads: %ld (%ld/stmt)\n",
866 actual_num_vuses,
867 (stats->num_mem_stmts)
868 ? CEIL (actual_num_vuses, stats->num_mem_stmts)
869 : 0);
871 if (actual_num_vuses > stats->num_vuses + (stats->num_vuses / 25))
872 fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
874 fprintf (file, "Estimated number of stores: %ld (%ld/stmt)\n",
875 stats->num_vdefs,
876 (stats->num_mem_stmts)
877 ? CEIL (stats->num_vdefs, stats->num_mem_stmts)
878 : 0);
879 fprintf (file, "Actual number of stores: %ld (%ld/stmt)\n",
880 actual_num_vdefs,
881 (stats->num_mem_stmts)
882 ? CEIL (actual_num_vdefs, stats->num_mem_stmts)
883 : 0);
885 if (actual_num_vdefs > stats->num_vdefs + (stats->num_vdefs / 25))
886 fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
888 fprintf (file, "Partitioning thresholds: MAX = %d AVG = %d "
889 "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS, AVG_ALIASED_VOPS,
890 stats->num_mem_stmts && need_to_partition_p (stats) ? "" : "NO ");
891 fprintf (file, "Number of partitioned symbols: %ld\n", num_partitioned);
892 fprintf (file, "Number of unpartitioned symbols: %ld\n", num_unpartitioned);
896 /* Dump memory reference stats for function FN to stderr. */
898 void
899 debug_mem_ref_stats (void)
901 dump_mem_ref_stats (stderr);
905 /* Dump memory reference stats for variable VAR to FILE. */
907 static void
908 dump_mem_sym_stats (FILE *file, tree var)
910 mem_sym_stats_t stats = mem_sym_stats (cfun, var);
912 if (stats == NULL)
913 return;
915 fprintf (file, "read frequency: %6ld, write frequency: %6ld, "
916 "direct reads: %3ld, direct writes: %3ld, "
917 "indirect reads: %4ld, indirect writes: %4ld, symbol: ",
918 stats->frequency_reads, stats->frequency_writes,
919 stats->num_direct_reads, stats->num_direct_writes,
920 stats->num_indirect_reads, stats->num_indirect_writes);
921 print_generic_expr (file, stats->var, 0);
922 fprintf (file, ", tags: ");
923 dump_decl_set (file, stats->parent_tags);
927 /* Dump memory reference stats for variable VAR to stderr. */
929 void
930 debug_mem_sym_stats (tree var)
932 dump_mem_sym_stats (stderr, var);
935 /* Dump memory reference stats for variable VAR to FILE. For use
936 of tree-dfa.c:dump_variable. */
938 void
939 dump_mem_sym_stats_for_var (FILE *file, tree var)
941 mem_sym_stats_t stats = mem_sym_stats (cfun, var);
943 if (stats == NULL)
944 return;
946 fprintf (file, ", score: %ld", mem_sym_score (stats));
947 fprintf (file, ", direct reads: %ld", stats->num_direct_reads);
948 fprintf (file, ", direct writes: %ld", stats->num_direct_writes);
949 fprintf (file, ", indirect reads: %ld", stats->num_indirect_reads);
950 fprintf (file, ", indirect writes: %ld", stats->num_indirect_writes);
953 /* Dump memory reference stats for all memory symbols to FILE. */
955 static void
956 dump_all_mem_sym_stats (FILE *file)
958 referenced_var_iterator rvi;
959 tree sym;
961 FOR_EACH_REFERENCED_VAR (sym, rvi)
963 if (is_gimple_reg (sym))
964 continue;
966 dump_mem_sym_stats (file, sym);
971 /* Dump memory reference stats for all memory symbols to stderr. */
973 void
974 debug_all_mem_sym_stats (void)
976 dump_all_mem_sym_stats (stderr);
980 /* Dump the MP_INFO array to FILE. */
982 static void
983 dump_mp_info (FILE *file, VEC(mem_sym_stats_t,heap) *mp_info)
985 unsigned i;
986 mem_sym_stats_t mp_p;
988 for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
989 if (!mp_p->partitioned_p)
990 dump_mem_sym_stats (file, mp_p->var);
994 /* Dump the MP_INFO array to stderr. */
996 void
997 debug_mp_info (VEC(mem_sym_stats_t,heap) *mp_info)
999 dump_mp_info (stderr, mp_info);
1003 /* Update memory reference stats for symbol VAR in statement STMT.
1004 NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times
1005 that VAR is read/written in STMT (indirect reads/writes are not
1006 recorded by this function, see compute_memory_partitions). */
1008 void
1009 update_mem_sym_stats_from_stmt (tree var, gimple stmt, long num_direct_reads,
1010 long num_direct_writes)
1012 mem_sym_stats_t stats;
1014 gcc_assert (num_direct_reads >= 0 && num_direct_writes >= 0);
1016 stats = get_mem_sym_stats_for (var);
1018 stats->num_direct_reads += num_direct_reads;
1019 stats->frequency_reads += ((long) gimple_bb (stmt)->frequency
1020 * num_direct_reads);
1022 stats->num_direct_writes += num_direct_writes;
1023 stats->frequency_writes += ((long) gimple_bb (stmt)->frequency
1024 * num_direct_writes);
1028 /* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should
1029 be partitioned before MP2->VAR, 0 if they are the same or 1 if
1030 MP1->VAR should be partitioned after MP2->VAR. */
1032 static inline int
1033 compare_mp_info_entries (mem_sym_stats_t mp1, mem_sym_stats_t mp2)
1035 long pscore1 = mem_sym_score (mp1);
1036 long pscore2 = mem_sym_score (mp2);
1038 if (pscore1 < pscore2)
1039 return -1;
1040 else if (pscore1 > pscore2)
1041 return 1;
1042 else
1043 return DECL_UID (mp1->var) - DECL_UID (mp2->var);
1047 /* Comparison routine for qsort. The list is sorted by increasing
1048 partitioning score (PSCORE). This score is computed such that
1049 symbols with high scores are those that are least likely to be
1050 partitioned. */
1052 static int
1053 mp_info_cmp (const void *p, const void *q)
1055 mem_sym_stats_t e1 = *((const mem_sym_stats_t *) p);
1056 mem_sym_stats_t e2 = *((const mem_sym_stats_t *) q);
1057 return compare_mp_info_entries (e1, e2);
1061 /* Sort the array of reference counts used to compute memory partitions.
1062 Elements are sorted in ascending order of execution frequency and
1063 descending order of virtual operators needed. */
1065 static inline void
1066 sort_mp_info (VEC(mem_sym_stats_t,heap) *list)
1068 unsigned num = VEC_length (mem_sym_stats_t, list);
1070 if (num < 2)
1071 return;
1073 if (num == 2)
1075 if (compare_mp_info_entries (VEC_index (mem_sym_stats_t, list, 0),
1076 VEC_index (mem_sym_stats_t, list, 1)) > 0)
1078 /* Swap elements if they are in the wrong order. */
1079 mem_sym_stats_t tmp = VEC_index (mem_sym_stats_t, list, 0);
1080 VEC_replace (mem_sym_stats_t, list, 0,
1081 VEC_index (mem_sym_stats_t, list, 1));
1082 VEC_replace (mem_sym_stats_t, list, 1, tmp);
1085 return;
1088 /* There are 3 or more elements, call qsort. */
1089 qsort (VEC_address (mem_sym_stats_t, list),
1090 VEC_length (mem_sym_stats_t, list),
1091 sizeof (mem_sym_stats_t),
1092 mp_info_cmp);
1096 /* Return the memory partition tag (MPT) associated with memory
1097 symbol SYM. */
1099 static tree
1100 get_mpt_for (tree sym)
1102 tree mpt;
1104 /* Don't create a new tag unnecessarily. */
1105 mpt = memory_partition (sym);
1106 if (mpt == NULL_TREE)
1108 mpt = create_tag_raw (MEMORY_PARTITION_TAG, TREE_TYPE (sym), "MPT");
1109 TREE_ADDRESSABLE (mpt) = 0;
1110 add_referenced_var (mpt);
1111 VEC_safe_push (tree, heap, gimple_ssa_operands (cfun)->mpt_table, mpt);
1112 gcc_assert (MPT_SYMBOLS (mpt) == NULL);
1113 set_memory_partition (sym, mpt);
1116 return mpt;
1120 /* Add MP_P->VAR to a memory partition and return the partition. */
1122 static tree
1123 find_partition_for (mem_sym_stats_t mp_p)
1125 unsigned i;
1126 VEC(tree,heap) *mpt_table;
1127 tree mpt;
1129 mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1130 mpt = NULL_TREE;
1132 /* Find an existing partition for MP_P->VAR. */
1133 for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
1135 mem_sym_stats_t mpt_stats;
1137 /* If MPT does not have any symbols yet, use it. */
1138 if (MPT_SYMBOLS (mpt) == NULL)
1139 break;
1141 /* Otherwise, see if MPT has common parent tags with MP_P->VAR,
1142 but avoid grouping clobbered variables with non-clobbered
1143 variables (otherwise, this tends to creates a single memory
1144 partition because other call-clobbered variables may have
1145 common parent tags with non-clobbered ones). */
1146 mpt_stats = get_mem_sym_stats_for (mpt);
1147 if (mp_p->parent_tags
1148 && mpt_stats->parent_tags
1149 && is_call_clobbered (mpt) == is_call_clobbered (mp_p->var)
1150 && bitmap_intersect_p (mpt_stats->parent_tags, mp_p->parent_tags))
1151 break;
1153 /* If no common parent tags are found, see if both MPT and
1154 MP_P->VAR are call-clobbered. */
1155 if (is_call_clobbered (mpt) && is_call_clobbered (mp_p->var))
1156 break;
1159 if (mpt == NULL_TREE)
1160 mpt = get_mpt_for (mp_p->var);
1161 else
1162 set_memory_partition (mp_p->var, mpt);
1164 mp_p->partitioned_p = true;
1166 mark_sym_for_renaming (mp_p->var);
1167 mark_sym_for_renaming (mpt);
1169 return mpt;
1173 /* Rewrite the alias set for TAG to use the newly created partitions.
1174 If TAG is NULL, rewrite the set of call-clobbered variables.
1175 NEW_ALIASES is a scratch bitmap to build the new set of aliases for
1176 TAG. */
1178 static void
1179 rewrite_alias_set_for (tree tag, bitmap new_aliases)
1181 bitmap_iterator bi;
1182 unsigned i;
1183 tree mpt, sym;
1185 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
1187 sym = referenced_var (i);
1188 mpt = memory_partition (sym);
1189 if (mpt)
1190 bitmap_set_bit (new_aliases, DECL_UID (mpt));
1191 else
1192 bitmap_set_bit (new_aliases, DECL_UID (sym));
1195 /* Rebuild the may-alias array for TAG. */
1196 bitmap_copy (MTAG_ALIASES (tag), new_aliases);
1200 /* Determine how many virtual operands can be saved by partitioning
1201 MP_P->VAR into MPT. When a symbol S is thrown inside a partition
1202 P, every virtual operand that used to reference S will now
1203 reference P. Whether it reduces the number of virtual operands
1204 depends on:
1206 1- Direct references to S are never saved. Instead of the virtual
1207 operand to S, we will now have a virtual operand to P.
1209 2- Indirect references to S are reduced only for those memory tags
1210 holding S that already had other symbols partitioned into P.
1211 For instance, if a memory tag T has the alias set { a b S c },
1212 the first time we partition S into P, the alias set will become
1213 { a b P c }, so no virtual operands will be saved. However, if
1214 we now partition symbol 'c' into P, then the alias set for T
1215 will become { a b P }, so we will be saving one virtual operand
1216 for every indirect reference to 'c'.
1218 3- Is S is call-clobbered, we save as many virtual operands as
1219 call/asm sites exist in the code, but only if other
1220 call-clobbered symbols have been grouped into P. The first
1221 call-clobbered symbol that we group does not produce any
1222 savings.
1224 MEM_REF_STATS points to CFUN's memory reference information. */
1226 static void
1227 estimate_vop_reduction (struct mem_ref_stats_d *mem_ref_stats,
1228 mem_sym_stats_t mp_p, tree mpt)
1230 unsigned i;
1231 bitmap_iterator bi;
1232 mem_sym_stats_t mpt_stats;
1234 /* We should only get symbols with indirect references here. */
1235 gcc_assert (mp_p->num_indirect_reads > 0 || mp_p->num_indirect_writes > 0);
1237 /* Note that the only statistics we keep for MPT is the set of
1238 parent tags to know which memory tags have had alias members
1239 partitioned, and the indicator has_call_clobbered_vars.
1240 Reference counts are not important for MPT. */
1241 mpt_stats = get_mem_sym_stats_for (mpt);
1243 /* Traverse all the parent tags for MP_P->VAR. For every tag T, if
1244 partition P is already grouping aliases of T, then reduce the
1245 number of virtual operands by the number of direct references
1246 to T. */
1247 if (mp_p->parent_tags)
1249 if (mpt_stats->parent_tags == NULL)
1250 mpt_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1252 EXECUTE_IF_SET_IN_BITMAP (mp_p->parent_tags, 0, i, bi)
1254 if (bitmap_bit_p (mpt_stats->parent_tags, i))
1256 /* Partition MPT is already partitioning symbols in the
1257 alias set for TAG. This means that we are now saving
1258 1 virtual operand for every direct reference to TAG. */
1259 tree tag = referenced_var (i);
1260 mem_sym_stats_t tag_stats = mem_sym_stats (cfun, tag);
1261 mem_ref_stats->num_vuses -= tag_stats->num_direct_reads;
1262 mem_ref_stats->num_vdefs -= tag_stats->num_direct_writes;
1264 else
1266 /* This is the first symbol in tag I's alias set that is
1267 being grouped under MPT. We will not save any
1268 virtual operands this time, but record that MPT is
1269 grouping a symbol from TAG's alias set so that the
1270 next time we get the savings. */
1271 bitmap_set_bit (mpt_stats->parent_tags, i);
1276 /* If MP_P->VAR is call-clobbered, and MPT is already grouping
1277 call-clobbered symbols, then we will save as many virtual
1278 operands as asm/call sites there are. */
1279 if (is_call_clobbered (mp_p->var))
1281 if (mpt_stats->has_call_clobbered_vars)
1282 mem_ref_stats->num_vdefs -= mem_ref_stats->num_call_sites
1283 + mem_ref_stats->num_asm_sites;
1284 else
1285 mpt_stats->has_call_clobbered_vars = true;
1290 /* Helper for compute_memory_partitions. Transfer reference counts
1291 from pointers to their pointed-to sets. Counters for pointers were
1292 computed by update_alias_info. MEM_REF_STATS points to CFUN's
1293 memory reference information. */
1295 static void
1296 update_reference_counts (struct mem_ref_stats_d *mem_ref_stats)
1298 unsigned i;
1299 bitmap_iterator bi;
1300 mem_sym_stats_t sym_stats;
1302 for (i = 1; i < num_ssa_names; i++)
1304 tree ptr;
1305 struct ptr_info_def *pi;
1307 ptr = ssa_name (i);
1308 if (ptr
1309 && POINTER_TYPE_P (TREE_TYPE (ptr))
1310 && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1311 && pi->memory_tag_needed)
1313 unsigned j;
1314 bitmap_iterator bj;
1315 tree tag;
1316 mem_sym_stats_t ptr_stats, tag_stats;
1318 /* If PTR has flow-sensitive points-to information, use
1319 PTR's name tag, otherwise use the symbol tag associated
1320 with PTR's symbol. */
1321 if (pi->name_mem_tag)
1322 tag = pi->name_mem_tag;
1323 else
1324 tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
1326 ptr_stats = get_mem_sym_stats_for (ptr);
1327 tag_stats = get_mem_sym_stats_for (tag);
1329 /* TAG has as many direct references as dereferences we
1330 found for its parent pointer. */
1331 tag_stats->num_direct_reads += ptr_stats->num_direct_reads;
1332 tag_stats->num_direct_writes += ptr_stats->num_direct_writes;
1334 /* All the dereferences of pointer PTR are considered direct
1335 references to PTR's memory tag (TAG). In turn,
1336 references to TAG will become virtual operands for every
1337 symbol in TAG's alias set. So, for every symbol ALIAS in
1338 TAG's alias set, add as many indirect references to ALIAS
1339 as direct references there are for TAG. */
1340 if (MTAG_ALIASES (tag))
1341 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, j, bj)
1343 tree alias = referenced_var (j);
1344 sym_stats = get_mem_sym_stats_for (alias);
1346 /* All the direct references to TAG are indirect references
1347 to ALIAS. */
1348 sym_stats->num_indirect_reads += ptr_stats->num_direct_reads;
1349 sym_stats->num_indirect_writes += ptr_stats->num_direct_writes;
1350 sym_stats->frequency_reads += ptr_stats->frequency_reads;
1351 sym_stats->frequency_writes += ptr_stats->frequency_writes;
1353 /* Indicate that TAG is one of ALIAS's parent tags. */
1354 if (sym_stats->parent_tags == NULL)
1355 sym_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1356 bitmap_set_bit (sym_stats->parent_tags, DECL_UID (tag));
1361 /* Call-clobbered symbols are indirectly written at every
1362 call/asm site. */
1363 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
1365 tree sym = referenced_var (i);
1366 sym_stats = get_mem_sym_stats_for (sym);
1367 sym_stats->num_indirect_writes += mem_ref_stats->num_call_sites
1368 + mem_ref_stats->num_asm_sites;
1371 /* Addressable symbols are indirectly written at some ASM sites.
1372 Since only ASM sites that clobber memory actually affect
1373 addressable symbols, this is an over-estimation. */
1374 EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
1376 tree sym = referenced_var (i);
1377 sym_stats = get_mem_sym_stats_for (sym);
1378 sym_stats->num_indirect_writes += mem_ref_stats->num_asm_sites;
1383 /* Helper for compute_memory_partitions. Add all memory symbols to
1384 *MP_INFO_P and compute the initial estimate for the total number of
1385 virtual operands needed. MEM_REF_STATS points to CFUN's memory
1386 reference information. On exit, *TAGS_P will contain the list of
1387 memory tags whose alias set need to be rewritten after
1388 partitioning. */
1390 static void
1391 build_mp_info (struct mem_ref_stats_d *mem_ref_stats,
1392 VEC(mem_sym_stats_t,heap) **mp_info_p,
1393 VEC(tree,heap) **tags_p)
1395 tree var;
1396 referenced_var_iterator rvi;
1398 FOR_EACH_REFERENCED_VAR (var, rvi)
1400 mem_sym_stats_t sym_stats;
1401 tree old_mpt;
1403 /* We are only interested in memory symbols other than MPTs. */
1404 if (is_gimple_reg (var) || TREE_CODE (var) == MEMORY_PARTITION_TAG)
1405 continue;
1407 /* Collect memory tags into the TAGS array so that we can
1408 rewrite their alias sets after partitioning. */
1409 if (MTAG_P (var) && MTAG_ALIASES (var))
1410 VEC_safe_push (tree, heap, *tags_p, var);
1412 /* Since we are going to re-compute partitions, any symbols that
1413 used to belong to a partition must be detached from it and
1414 marked for renaming. */
1415 if ((old_mpt = memory_partition (var)) != NULL)
1417 mark_sym_for_renaming (old_mpt);
1418 set_memory_partition (var, NULL_TREE);
1419 mark_sym_for_renaming (var);
1422 sym_stats = get_mem_sym_stats_for (var);
1424 /* Add VAR's reference info to MP_INFO. Note that the only
1425 symbols that make sense to partition are those that have
1426 indirect references. If a symbol S is always directly
1427 referenced, partitioning it will not reduce the number of
1428 virtual operators. The only symbols that are profitable to
1429 partition are those that belong to alias sets and/or are
1430 call-clobbered. */
1431 if (sym_stats->num_indirect_reads > 0
1432 || sym_stats->num_indirect_writes > 0)
1433 VEC_safe_push (mem_sym_stats_t, heap, *mp_info_p, sym_stats);
1435 /* Update the number of estimated VOPS. Note that direct
1436 references to memory tags are always counted as indirect
1437 references to their alias set members, so if a memory tag has
1438 aliases, do not count its direct references to avoid double
1439 accounting. */
1440 if (!MTAG_P (var) || !MTAG_ALIASES (var))
1442 mem_ref_stats->num_vuses += sym_stats->num_direct_reads;
1443 mem_ref_stats->num_vdefs += sym_stats->num_direct_writes;
1446 mem_ref_stats->num_vuses += sym_stats->num_indirect_reads;
1447 mem_ref_stats->num_vdefs += sym_stats->num_indirect_writes;
1452 /* Compute memory partitions. A memory partition (MPT) is an
1453 arbitrary grouping of memory symbols, such that references to one
1454 member of the group is considered a reference to all the members of
1455 the group.
1457 As opposed to alias sets in memory tags, the grouping into
1458 partitions is completely arbitrary and only done to reduce the
1459 number of virtual operands. The only rule that needs to be
1460 observed when creating memory partitions is that given two memory
1461 partitions MPT.i and MPT.j, they must not contain symbols in
1462 common.
1464 Memory partitions are used when putting the program into Memory-SSA
1465 form. In particular, in Memory-SSA PHI nodes are not computed for
1466 individual memory symbols. They are computed for memory
1467 partitions. This reduces the amount of PHI nodes in the SSA graph
1468 at the expense of precision (i.e., it makes unrelated stores affect
1469 each other).
1471 However, it is possible to increase precision by changing this
1472 partitioning scheme. For instance, if the partitioning scheme is
1473 such that get_mpt_for is the identity function (that is,
1474 get_mpt_for (s) = s), this will result in ultimate precision at the
1475 expense of huge SSA webs.
1477 At the other extreme, a partitioning scheme that groups all the
1478 symbols in the same set results in minimal SSA webs and almost
1479 total loss of precision.
1481 There partitioning heuristic uses three parameters to decide the
1482 order in which symbols are processed. The list of symbols is
1483 sorted so that symbols that are more likely to be partitioned are
1484 near the top of the list:
1486 - Execution frequency. If a memory references is in a frequently
1487 executed code path, grouping it into a partition may block useful
1488 transformations and cause sub-optimal code generation. So, the
1489 partition heuristic tries to avoid grouping symbols with high
1490 execution frequency scores. Execution frequency is taken
1491 directly from the basic blocks where every reference is made (see
1492 update_mem_sym_stats_from_stmt), which in turn uses the
1493 profile guided machinery, so if the program is compiled with PGO
1494 enabled, more accurate partitioning decisions will be made.
1496 - Number of references. Symbols with few references in the code,
1497 are partitioned before symbols with many references.
1499 - NO_ALIAS attributes. Symbols with any of the NO_ALIAS*
1500 attributes are partitioned after symbols marked MAY_ALIAS.
1502 Once the list is sorted, the partitioning proceeds as follows:
1504 1- For every symbol S in MP_INFO, create a new memory partition MP,
1505 if necessary. To avoid memory partitions that contain symbols
1506 from non-conflicting alias sets, memory partitions are
1507 associated to the memory tag that holds S in its alias set. So,
1508 when looking for a memory partition for S, the memory partition
1509 associated with one of the memory tags holding S is chosen. If
1510 none exists, a new one is created.
1512 2- Add S to memory partition MP.
1514 3- Reduce by 1 the number of VOPS for every memory tag holding S.
1516 4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the
1517 average number of VOPS per statement is less than
1518 AVG_ALIASED_VOPS, stop. Otherwise, go to the next symbol in the
1519 list. */
1521 static void
1522 compute_memory_partitions (void)
1524 tree tag;
1525 unsigned i;
1526 mem_sym_stats_t mp_p;
1527 VEC(mem_sym_stats_t,heap) *mp_info;
1528 bitmap new_aliases;
1529 VEC(tree,heap) *tags;
1530 struct mem_ref_stats_d *mem_ref_stats;
1531 int prev_max_aliased_vops;
1533 mem_ref_stats = gimple_mem_ref_stats (cfun);
1534 gcc_assert (mem_ref_stats->num_vuses == 0 && mem_ref_stats->num_vdefs == 0);
1536 if (mem_ref_stats->num_mem_stmts == 0)
1537 return;
1539 timevar_push (TV_MEMORY_PARTITIONING);
1541 mp_info = NULL;
1542 tags = NULL;
1543 prev_max_aliased_vops = MAX_ALIASED_VOPS;
1545 /* Since we clearly cannot lower the number of virtual operators
1546 below the total number of memory statements in the function, we
1547 may need to adjust MAX_ALIASED_VOPS beforehand. */
1548 if (MAX_ALIASED_VOPS < mem_ref_stats->num_mem_stmts)
1549 MAX_ALIASED_VOPS = mem_ref_stats->num_mem_stmts;
1551 /* Update reference stats for all the pointed-to variables and
1552 memory tags. */
1553 update_reference_counts (mem_ref_stats);
1555 /* Add all the memory symbols to MP_INFO. */
1556 build_mp_info (mem_ref_stats, &mp_info, &tags);
1558 /* No partitions required if we are below the threshold. */
1559 if (!need_to_partition_p (mem_ref_stats))
1561 if (dump_file)
1562 fprintf (dump_file, "\nMemory partitioning NOT NEEDED for %s\n",
1563 get_name (current_function_decl));
1564 goto done;
1567 /* Sort the MP_INFO array so that symbols that should be partitioned
1568 first are near the top of the list. */
1569 sort_mp_info (mp_info);
1571 if (dump_file)
1573 fprintf (dump_file, "\nMemory partitioning NEEDED for %s\n\n",
1574 get_name (current_function_decl));
1575 fprintf (dump_file, "Memory symbol references before partitioning:\n");
1576 dump_mp_info (dump_file, mp_info);
1579 /* Create partitions for variables in MP_INFO until we have enough
1580 to lower the total number of VOPS below MAX_ALIASED_VOPS or if
1581 the average number of VOPS per statement is below
1582 AVG_ALIASED_VOPS. */
1583 for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
1585 tree mpt;
1587 /* If we are below the threshold, stop. */
1588 if (!need_to_partition_p (mem_ref_stats))
1589 break;
1591 mpt = find_partition_for (mp_p);
1592 estimate_vop_reduction (mem_ref_stats, mp_p, mpt);
1595 /* After partitions have been created, rewrite alias sets to use
1596 them instead of the original symbols. This way, if the alias set
1597 was computed as { a b c d e f }, and the subset { b e f } was
1598 grouped into partition MPT.3, then the new alias set for the tag
1599 will be { a c d MPT.3 }.
1601 Note that this is not strictly necessary. The operand scanner
1602 will always check if a symbol belongs to a partition when adding
1603 virtual operands. However, by reducing the size of the alias
1604 sets to be scanned, the work needed inside the operand scanner is
1605 significantly reduced. */
1606 new_aliases = BITMAP_ALLOC (&alias_bitmap_obstack);
1608 for (i = 0; VEC_iterate (tree, tags, i, tag); i++)
1610 rewrite_alias_set_for (tag, new_aliases);
1611 bitmap_clear (new_aliases);
1614 BITMAP_FREE (new_aliases);
1616 if (dump_file)
1618 fprintf (dump_file, "\nMemory symbol references after partitioning:\n");
1619 dump_mp_info (dump_file, mp_info);
1622 done:
1623 /* Free allocated memory. */
1624 VEC_free (mem_sym_stats_t, heap, mp_info);
1625 VEC_free (tree, heap, tags);
1627 MAX_ALIASED_VOPS = prev_max_aliased_vops;
1629 timevar_pop (TV_MEMORY_PARTITIONING);
1632 /* Compute may-alias information for every variable referenced in function
1633 FNDECL.
1635 Alias analysis proceeds in 3 main phases:
1637 1- Points-to and escape analysis.
1639 This phase walks the use-def chains in the SSA web looking for three
1640 things:
1642 * Assignments of the form P_i = &VAR
1643 * Assignments of the form P_i = malloc()
1644 * Pointers and ADDR_EXPR that escape the current function.
1646 The concept of 'escaping' is the same one used in the Java world. When
1647 a pointer or an ADDR_EXPR escapes, it means that it has been exposed
1648 outside of the current function. So, assignment to global variables,
1649 function arguments and returning a pointer are all escape sites, as are
1650 conversions between pointers and integers.
1652 This is where we are currently limited. Since not everything is renamed
1653 into SSA, we lose track of escape properties when a pointer is stashed
1654 inside a field in a structure, for instance. In those cases, we are
1655 assuming that the pointer does escape.
1657 We use escape analysis to determine whether a variable is
1658 call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable
1659 is call-clobbered. If a pointer P_i escapes, then all the variables
1660 pointed-to by P_i (and its memory tag) also escape.
1662 2- Compute flow-sensitive aliases
1664 We have two classes of memory tags. Memory tags associated with the
1665 pointed-to data type of the pointers in the program. These tags are
1666 called "symbol memory tag" (SMT). The other class are those associated
1667 with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
1668 when adding operands for an INDIRECT_REF *P_i, we will first check
1669 whether P_i has a name tag, if it does we use it, because that will have
1670 more precise aliasing information. Otherwise, we use the standard symbol
1671 tag.
1673 In this phase, we go through all the pointers we found in points-to
1674 analysis and create alias sets for the name memory tags associated with
1675 each pointer P_i. If P_i escapes, we mark call-clobbered the variables
1676 it points to and its tag.
1679 3- Compute flow-insensitive aliases
1681 This pass will compare the alias set of every symbol memory tag and
1682 every addressable variable found in the program. Given a symbol
1683 memory tag SMT and an addressable variable V. If the alias sets of
1684 SMT and V conflict (as computed by may_alias_p), then V is marked
1685 as an alias tag and added to the alias set of SMT.
1687 For instance, consider the following function:
1689 foo (int i)
1691 int *p, a, b;
1693 if (i > 10)
1694 p = &a;
1695 else
1696 p = &b;
1698 *p = 3;
1699 a = b + 2;
1700 return *p;
1703 After aliasing analysis has finished, the symbol memory tag for pointer
1704 'p' will have two aliases, namely variables 'a' and 'b'. Every time
1705 pointer 'p' is dereferenced, we want to mark the operation as a
1706 potential reference to 'a' and 'b'.
1708 foo (int i)
1710 int *p, a, b;
1712 if (i_2 > 10)
1713 p_4 = &a;
1714 else
1715 p_6 = &b;
1716 # p_1 = PHI <p_4(1), p_6(2)>;
1718 # a_7 = VDEF <a_3>;
1719 # b_8 = VDEF <b_5>;
1720 *p_1 = 3;
1722 # a_9 = VDEF <a_7>
1723 # VUSE <b_8>
1724 a_9 = b_8 + 2;
1726 # VUSE <a_9>;
1727 # VUSE <b_8>;
1728 return *p_1;
1731 In certain cases, the list of may aliases for a pointer may grow too
1732 large. This may cause an explosion in the number of virtual operands
1733 inserted in the code. Resulting in increased memory consumption and
1734 compilation time.
1736 When the number of virtual operands needed to represent aliased
1737 loads and stores grows too large (configurable with option --param
1738 max-aliased-vops and --param avg-aliased-vops), alias sets are
1739 grouped to avoid severe compile-time slow downs and memory
1740 consumption. See compute_memory_partitions. */
1742 unsigned int
1743 compute_may_aliases (void)
1745 struct alias_info *ai;
1747 timevar_push (TV_TREE_MAY_ALIAS);
1749 memset (&alias_stats, 0, sizeof (alias_stats));
1751 /* Initialize aliasing information. */
1752 ai = init_alias_info ();
1754 /* For each pointer P_i, determine the sets of variables that P_i may
1755 point-to. For every addressable variable V, determine whether the
1756 address of V escapes the current function, making V call-clobbered
1757 (i.e., whether &V is stored in a global variable or if its passed as a
1758 function call argument). */
1759 compute_points_to_sets ();
1761 /* Update various related attributes like escaped addresses,
1762 pointer dereferences for loads and stores. This is used
1763 when creating name tags and alias sets. */
1764 update_alias_info (ai);
1766 /* Collect all pointers and addressable variables, compute alias sets,
1767 create memory tags for pointers and promote variables whose address is
1768 not needed anymore. */
1769 setup_pointers_and_addressables (ai);
1771 /* Compute type-based flow-insensitive aliasing for all the type
1772 memory tags. */
1773 compute_flow_insensitive_aliasing (ai);
1775 /* Compute flow-sensitive, points-to based aliasing for all the name
1776 memory tags. */
1777 compute_flow_sensitive_aliasing (ai);
1779 /* Compute call clobbering information. */
1780 compute_call_clobbered (ai);
1782 /* If the program makes no reference to global variables, but it
1783 contains a mixture of pure and non-pure functions, then we need
1784 to create use-def and def-def links between these functions to
1785 avoid invalid transformations on them. */
1786 maybe_create_global_var ();
1788 /* Compute memory partitions for every memory variable. */
1789 compute_memory_partitions ();
1791 /* Remove partitions with no symbols. Partitions may end up with an
1792 empty MPT_SYMBOLS set if a previous round of alias analysis
1793 needed to partition more symbols. Since we don't need those
1794 partitions anymore, remove them to free up the space. */
1796 tree mpt;
1797 unsigned i;
1798 VEC(tree,heap) *mpt_table;
1800 mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1801 i = 0;
1802 while (i < VEC_length (tree, mpt_table))
1804 mpt = VEC_index (tree, mpt_table, i);
1805 if (MPT_SYMBOLS (mpt) == NULL)
1806 VEC_unordered_remove (tree, mpt_table, i);
1807 else
1808 i++;
1812 /* Populate all virtual operands and newly promoted register operands. */
1814 gimple_stmt_iterator gsi;
1815 basic_block bb;
1816 FOR_EACH_BB (bb)
1817 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1818 update_stmt_if_modified (gsi_stmt (gsi));
1821 /* Debugging dumps. */
1822 if (dump_file)
1824 dump_mem_ref_stats (dump_file);
1825 dump_alias_info (dump_file);
1826 dump_points_to_info (dump_file);
1828 if (dump_flags & TDF_STATS)
1829 dump_alias_stats (dump_file);
1831 if (dump_flags & TDF_DETAILS)
1832 dump_referenced_vars (dump_file);
1835 /* Report strict aliasing violations. */
1836 strict_aliasing_warning_backend ();
1838 /* Deallocate memory used by aliasing data structures. */
1839 delete_alias_info (ai);
1841 if (need_ssa_update_p ())
1842 update_ssa (TODO_update_ssa);
1844 timevar_pop (TV_TREE_MAY_ALIAS);
1846 return 0;
1849 /* Data structure used to count the number of dereferences to PTR
1850 inside an expression. */
1851 struct count_ptr_d
1853 tree ptr;
1854 unsigned num_stores;
1855 unsigned num_loads;
1859 /* Helper for count_uses_and_derefs. Called by walk_tree to look for
1860 (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
1862 static tree
1863 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
1865 struct walk_stmt_info *wi_p = (struct walk_stmt_info *) data;
1866 struct count_ptr_d *count_p = (struct count_ptr_d *) wi_p->info;
1868 /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld,
1869 pointer 'ptr' is *not* dereferenced, it is simply used to compute
1870 the address of 'fld' as 'ptr + offsetof(fld)'. */
1871 if (TREE_CODE (*tp) == ADDR_EXPR)
1873 *walk_subtrees = 0;
1874 return NULL_TREE;
1877 if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
1879 if (wi_p->is_lhs)
1880 count_p->num_stores++;
1881 else
1882 count_p->num_loads++;
1885 return NULL_TREE;
1889 /* Count the number of direct and indirect uses for pointer PTR in
1890 statement STMT. The number of direct uses is stored in
1891 *NUM_USES_P. Indirect references are counted separately depending
1892 on whether they are store or load operations. The counts are
1893 stored in *NUM_STORES_P and *NUM_LOADS_P. */
1895 void
1896 count_uses_and_derefs (tree ptr, gimple stmt, unsigned *num_uses_p,
1897 unsigned *num_loads_p, unsigned *num_stores_p)
1899 ssa_op_iter i;
1900 tree use;
1902 *num_uses_p = 0;
1903 *num_loads_p = 0;
1904 *num_stores_p = 0;
1906 /* Find out the total number of uses of PTR in STMT. */
1907 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1908 if (use == ptr)
1909 (*num_uses_p)++;
1911 /* Now count the number of indirect references to PTR. This is
1912 truly awful, but we don't have much choice. There are no parent
1913 pointers inside INDIRECT_REFs, so an expression like
1914 '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
1915 find all the indirect and direct uses of x_1 inside. The only
1916 shortcut we can take is the fact that GIMPLE only allows
1917 INDIRECT_REFs inside the expressions below. */
1918 if (is_gimple_assign (stmt)
1919 || gimple_code (stmt) == GIMPLE_RETURN
1920 || gimple_code (stmt) == GIMPLE_ASM
1921 || is_gimple_call (stmt))
1923 struct walk_stmt_info wi;
1924 struct count_ptr_d count;
1926 count.ptr = ptr;
1927 count.num_stores = 0;
1928 count.num_loads = 0;
1930 memset (&wi, 0, sizeof (wi));
1931 wi.info = &count;
1932 walk_gimple_op (stmt, count_ptr_derefs, &wi);
1934 *num_stores_p = count.num_stores;
1935 *num_loads_p = count.num_loads;
1938 gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
1941 /* Remove memory references stats for function FN. */
1943 void
1944 delete_mem_ref_stats (struct function *fn)
1946 if (gimple_mem_ref_stats (fn)->mem_sym_stats)
1948 free_alloc_pool (mem_sym_stats_pool);
1949 pointer_map_destroy (gimple_mem_ref_stats (fn)->mem_sym_stats);
1951 gimple_mem_ref_stats (fn)->mem_sym_stats = NULL;
1955 /* Initialize memory reference stats. */
1957 static void
1958 init_mem_ref_stats (void)
1960 struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
1962 mem_sym_stats_pool = create_alloc_pool ("Mem sym stats",
1963 sizeof (struct mem_sym_stats_d),
1964 100);
1965 memset (mem_ref_stats, 0, sizeof (struct mem_ref_stats_d));
1966 mem_ref_stats->mem_sym_stats = pointer_map_create ();
1970 /* Helper for init_alias_info. Reset existing aliasing information. */
1972 static void
1973 reset_alias_info (void)
1975 referenced_var_iterator rvi;
1976 tree var;
1977 unsigned i;
1978 bitmap active_nmts, all_nmts;
1980 /* Clear the set of addressable variables. We do not need to clear
1981 the TREE_ADDRESSABLE bit on every symbol because we are going to
1982 re-compute addressability here. */
1983 bitmap_clear (gimple_addressable_vars (cfun));
1985 active_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
1986 all_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
1988 /* Clear flow-insensitive alias information from each symbol. */
1989 FOR_EACH_REFERENCED_VAR (var, rvi)
1991 if (is_gimple_reg (var))
1992 continue;
1994 if (MTAG_P (var))
1995 MTAG_ALIASES (var) = NULL;
1997 /* Memory partition information will be computed from scratch. */
1998 if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
1999 MPT_SYMBOLS (var) = NULL;
2001 /* Collect all the name tags to determine if we have any
2002 orphaned that need to be removed from the IL. A name tag
2003 will be orphaned if it is not associated with any active SSA
2004 name. */
2005 if (TREE_CODE (var) == NAME_MEMORY_TAG)
2006 bitmap_set_bit (all_nmts, DECL_UID (var));
2008 /* Since we are about to re-discover call-clobbered
2009 variables, clear the call-clobbered flag. */
2010 clear_call_clobbered (var);
2013 /* There should be no call-clobbered variable left. */
2014 gcc_assert (bitmap_empty_p (gimple_call_clobbered_vars (cfun)));
2016 /* Clear the call-used variables. */
2017 bitmap_clear (gimple_call_used_vars (cfun));
2019 /* Clear flow-sensitive points-to information from each SSA name. */
2020 for (i = 1; i < num_ssa_names; i++)
2022 tree name = ssa_name (i);
2024 if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
2025 continue;
2027 if (SSA_NAME_PTR_INFO (name))
2029 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
2031 /* Clear all the flags but keep the name tag to
2032 avoid creating new temporaries unnecessarily. If
2033 this pointer is found to point to a subset or
2034 superset of its former points-to set, then a new
2035 tag will need to be created in create_name_tags. */
2036 pi->pt_anything = 0;
2037 pi->pt_null = 0;
2038 pi->value_escapes_p = 0;
2039 pi->memory_tag_needed = 0;
2040 pi->is_dereferenced = 0;
2041 if (pi->pt_vars)
2042 bitmap_clear (pi->pt_vars);
2044 /* Add NAME's name tag to the set of active tags. */
2045 if (pi->name_mem_tag)
2046 bitmap_set_bit (active_nmts, DECL_UID (pi->name_mem_tag));
2050 /* Name memory tags that are no longer associated with an SSA name
2051 are considered stale and should be removed from the IL. All the
2052 name tags that are in the set ALL_NMTS but not in ACTIVE_NMTS are
2053 considered stale and marked for renaming. */
2054 bitmap_and_compl_into (all_nmts, active_nmts);
2055 mark_set_for_renaming (all_nmts);
2057 BITMAP_FREE (all_nmts);
2058 BITMAP_FREE (active_nmts);
2062 /* Initialize the data structures used for alias analysis. */
2064 static struct alias_info *
2065 init_alias_info (void)
2067 struct alias_info *ai;
2068 referenced_var_iterator rvi;
2069 tree var;
2070 static bool alias_bitmap_obstack_initialized;
2072 ai = XCNEW (struct alias_info);
2073 ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
2074 sbitmap_zero (ai->ssa_names_visited);
2075 ai->processed_ptrs = VEC_alloc (tree, heap, 50);
2076 ai->written_vars = pointer_set_create ();
2077 ai->dereferenced_ptrs_store = pointer_set_create ();
2078 ai->dereferenced_ptrs_load = pointer_set_create ();
2080 /* Clear out all memory reference stats. */
2081 init_mem_ref_stats ();
2083 /* If aliases have been computed before, clear existing information. */
2084 if (gimple_aliases_computed_p (cfun))
2085 reset_alias_info ();
2086 else
2088 /* If this is the first time we compute aliasing information,
2089 every non-register symbol will need to be put into SSA form
2090 (the initial SSA form only operates on GIMPLE registers). */
2091 FOR_EACH_REFERENCED_VAR (var, rvi)
2092 if (!is_gimple_reg (var))
2093 mark_sym_for_renaming (var);
2096 /* Next time, we will need to reset alias information. */
2097 cfun->gimple_df->aliases_computed_p = true;
2098 if (alias_bitmap_obstack_initialized)
2099 bitmap_obstack_release (&alias_bitmap_obstack);
2100 bitmap_obstack_initialize (&alias_bitmap_obstack);
2101 alias_bitmap_obstack_initialized = true;
2103 return ai;
2107 /* Deallocate memory used by alias analysis. */
2109 static void
2110 delete_alias_info (struct alias_info *ai)
2112 size_t i;
2114 sbitmap_free (ai->ssa_names_visited);
2116 VEC_free (tree, heap, ai->processed_ptrs);
2118 for (i = 0; i < ai->num_addressable_vars; i++)
2119 free (ai->addressable_vars[i]);
2120 free (ai->addressable_vars);
2122 for (i = 0; i < ai->num_pointers; i++)
2123 free (ai->pointers[i]);
2124 free (ai->pointers);
2126 pointer_set_destroy (ai->written_vars);
2127 pointer_set_destroy (ai->dereferenced_ptrs_store);
2128 pointer_set_destroy (ai->dereferenced_ptrs_load);
2129 free (ai);
2131 delete_mem_ref_stats (cfun);
2132 delete_points_to_sets ();
2136 /* Used for hashing to identify pointer infos with identical
2137 pt_vars bitmaps. */
2139 static int
2140 eq_ptr_info (const void *p1, const void *p2)
2142 const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
2143 const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
2144 return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
2147 static hashval_t
2148 ptr_info_hash (const void *p)
2150 const struct ptr_info_def *n = (const struct ptr_info_def *) p;
2151 return bitmap_hash (n->pt_vars);
2155 /* Create name tags for all the pointers that have been dereferenced.
2156 We only create a name tag for a pointer P if P is found to point to
2157 a set of variables (so that we can alias them to *P) or if it is
2158 the result of a call to malloc (which means that P cannot point to
2159 anything else nor alias any other variable).
2161 If two pointers P and Q point to the same set of variables, they
2162 are assigned the same name tag. */
2164 static void
2165 create_name_tags (void)
2167 size_t i;
2168 VEC (tree, heap) *with_ptvars = NULL;
2169 tree ptr;
2170 htab_t ptr_hash;
2172 /* Collect the list of pointers with a non-empty points to set. */
2173 for (i = 1; i < num_ssa_names; i++)
2175 tree ptr = ssa_name (i);
2176 struct ptr_info_def *pi;
2178 if (!ptr
2179 || !POINTER_TYPE_P (TREE_TYPE (ptr))
2180 || !SSA_NAME_PTR_INFO (ptr))
2181 continue;
2183 pi = SSA_NAME_PTR_INFO (ptr);
2185 if (pi->pt_anything || !pi->memory_tag_needed)
2187 /* No name tags for pointers that have not been
2188 dereferenced or point to an arbitrary location. */
2189 pi->name_mem_tag = NULL_TREE;
2190 continue;
2193 /* Set pt_anything on the pointers without pt_vars filled in so
2194 that they are assigned a symbol tag. */
2195 if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
2196 VEC_safe_push (tree, heap, with_ptvars, ptr);
2197 else
2198 set_pt_anything (ptr);
2201 /* If we didn't find any pointers with pt_vars set, we're done. */
2202 if (!with_ptvars)
2203 return;
2205 ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
2207 /* Now go through the pointers with pt_vars, and find a name tag
2208 with the same pt_vars as this pointer, or create one if one
2209 doesn't exist. */
2210 for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
2212 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2213 tree old_name_tag = pi->name_mem_tag;
2214 struct ptr_info_def **slot;
2216 /* If PTR points to a set of variables, check if we don't
2217 have another pointer Q with the same points-to set before
2218 creating a tag. If so, use Q's tag instead of creating a
2219 new one.
2221 This is important for not creating unnecessary symbols
2222 and also for copy propagation. If we ever need to
2223 propagate PTR into Q or vice-versa, we would run into
2224 problems if they both had different name tags because
2225 they would have different SSA version numbers (which
2226 would force us to take the name tags in and out of SSA). */
2227 slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
2228 if (*slot)
2229 pi->name_mem_tag = (*slot)->name_mem_tag;
2230 else
2232 *slot = pi;
2234 /* If we didn't find a pointer with the same points-to set
2235 as PTR, create a new name tag if needed. */
2236 if (pi->name_mem_tag == NULL_TREE)
2237 pi->name_mem_tag = get_nmt_for (ptr);
2240 /* If the new name tag computed for PTR is different than
2241 the old name tag that it used to have, then the old tag
2242 needs to be removed from the IL, so we mark it for
2243 renaming. */
2244 if (old_name_tag && old_name_tag != pi->name_mem_tag)
2245 mark_sym_for_renaming (old_name_tag);
2247 /* Inherit volatility from the pointed-to type. */
2248 TREE_THIS_VOLATILE (pi->name_mem_tag)
2249 |= TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
2251 /* Mark the new name tag for renaming. */
2252 mark_sym_for_renaming (pi->name_mem_tag);
2255 htab_delete (ptr_hash);
2257 VEC_free (tree, heap, with_ptvars);
2261 /* Union the alias set SET into the may-aliases for TAG. */
2263 static void
2264 union_alias_set_into (tree tag, bitmap set)
2266 bitmap ma = MTAG_ALIASES (tag);
2268 if (bitmap_empty_p (set))
2269 return;
2271 if (!ma)
2272 ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack);
2273 bitmap_ior_into (ma, set);
2277 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
2278 the name memory tag (NMT) associated with P_i. If P_i escapes, then its
2279 name tag and the variables it points-to are call-clobbered. Finally, if
2280 P_i escapes and we could not determine where it points to, then all the
2281 variables in the same alias set as *P_i are marked call-clobbered. This
2282 is necessary because we must assume that P_i may take the address of any
2283 variable in the same alias set. */
2285 static void
2286 compute_flow_sensitive_aliasing (struct alias_info *ai)
2288 size_t i;
2289 tree ptr;
2291 timevar_push (TV_FLOW_SENSITIVE);
2293 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2295 if (!find_what_p_points_to (ptr))
2296 set_pt_anything (ptr);
2299 create_name_tags ();
2301 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2303 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2305 /* Set up aliasing information for PTR's name memory tag (if it has
2306 one). Note that only pointers that have been dereferenced will
2307 have a name memory tag. */
2308 if (pi->name_mem_tag && pi->pt_vars)
2310 if (!bitmap_empty_p (pi->pt_vars))
2311 union_alias_set_into (pi->name_mem_tag, pi->pt_vars);
2314 timevar_pop (TV_FLOW_SENSITIVE);
2318 /* Return TRUE if at least one symbol in TAG2's alias set is also
2319 present in TAG1's alias set. */
2321 static bool
2322 have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases)
2325 /* This is the old behavior of have_common_aliases_p, which is to
2326 return false if both sets are empty, or one set is and the other
2327 isn't. */
2328 if (tag1aliases == NULL || tag2aliases == NULL)
2329 return false;
2331 return bitmap_intersect_p (tag1aliases, tag2aliases);
2334 /* Compute type-based alias sets. Traverse all the pointers and
2335 addressable variables found in setup_pointers_and_addressables.
2337 For every pointer P in AI->POINTERS and addressable variable V in
2338 AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
2339 memory tag (SMT) if their alias sets conflict. V is then marked as
2340 an aliased symbol so that the operand scanner knows that statements
2341 containing V have aliased operands. */
2343 static void
2344 compute_flow_insensitive_aliasing (struct alias_info *ai)
2346 referenced_var_iterator rvi;
2347 tree var;
2348 size_t i;
2350 timevar_push (TV_FLOW_INSENSITIVE);
2351 /* For every pointer P, determine which addressable variables may alias
2352 with P's symbol memory tag. */
2353 for (i = 0; i < ai->num_pointers; i++)
2355 size_t j;
2356 struct alias_map_d *p_map = ai->pointers[i];
2357 tree tag = symbol_mem_tag (p_map->var);
2358 tree var;
2360 for (j = 0; j < ai->num_addressable_vars; j++)
2362 struct alias_map_d *v_map;
2363 var_ann_t v_ann;
2364 bool tag_stored_p, var_stored_p;
2366 v_map = ai->addressable_vars[j];
2367 var = v_map->var;
2368 v_ann = var_ann (var);
2370 /* Skip memory tags and variables that have never been
2371 written to. We also need to check if the variables are
2372 call-clobbered because they may be overwritten by
2373 function calls. */
2374 tag_stored_p = pointer_set_contains (ai->written_vars, tag)
2375 || is_call_clobbered (tag);
2376 var_stored_p = pointer_set_contains (ai->written_vars, var)
2377 || is_call_clobbered (var);
2378 if (!tag_stored_p && !var_stored_p)
2379 continue;
2381 if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
2383 /* Add VAR to TAG's may-aliases set. */
2384 add_may_alias (tag, var);
2389 /* Since this analysis is based exclusively on symbols, it fails to
2390 handle cases where two pointers P and Q have different memory
2391 tags with conflicting alias set numbers but no aliased symbols in
2392 common.
2394 For example, suppose that we have two memory tags SMT.1 and SMT.2
2395 such that
2397 may-aliases (SMT.1) = { a }
2398 may-aliases (SMT.2) = { b }
2400 and the alias set number of SMT.1 conflicts with that of SMT.2.
2401 Since they don't have symbols in common, loads and stores from
2402 SMT.1 and SMT.2 will seem independent of each other, which will
2403 lead to the optimizers making invalid transformations (see
2404 testsuite/gcc.c-torture/execute/pr15262-[12].c).
2406 To avoid this problem, we do a final traversal of AI->POINTERS
2407 looking for pairs of pointers that have no aliased symbols in
2408 common and yet have conflicting alias set numbers. */
2409 for (i = 0; i < ai->num_pointers; i++)
2411 size_t j;
2412 struct alias_map_d *p_map1 = ai->pointers[i];
2413 tree tag1 = symbol_mem_tag (p_map1->var);
2414 bitmap may_aliases1 = MTAG_ALIASES (tag1);
2416 for (j = 0; j < ai->num_pointers; j++)
2418 struct alias_map_d *p_map2 = ai->pointers[j];
2419 tree tag2 = symbol_mem_tag (p_map2->var);
2420 bitmap may_aliases2 = may_aliases (tag2);
2422 /* By convention tags don't alias themselves. */
2423 if (tag1 == tag2)
2424 continue;
2426 /* If the pointers may not point to each other, do nothing. */
2427 if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
2428 continue;
2430 /* The two pointers may alias each other. If they already have
2431 symbols in common, do nothing. */
2432 if (have_common_aliases_p (may_aliases1, may_aliases2))
2433 continue;
2435 add_may_alias (tag1, tag2);
2439 /* We have to add all HEAP variables to all SMTs aliases bitmaps.
2440 As we don't know which effective type the HEAP will have we cannot
2441 do better here and we need the conflicts with obfuscated pointers
2442 (a simple (*(int[n] *)ptr)[i] will do, with ptr from a VLA array
2443 allocation). */
2444 for (i = 0; i < ai->num_pointers; i++)
2446 struct alias_map_d *p_map = ai->pointers[i];
2447 tree tag = symbol_mem_tag (p_map->var);
2449 FOR_EACH_REFERENCED_VAR (var, rvi)
2451 if (var_ann (var)->is_heapvar)
2452 add_may_alias (tag, var);
2456 timevar_pop (TV_FLOW_INSENSITIVE);
2460 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */
2462 static void
2463 create_alias_map_for (tree var, struct alias_info *ai)
2465 struct alias_map_d *alias_map;
2466 alias_map = XCNEW (struct alias_map_d);
2467 alias_map->var = var;
2468 alias_map->set = get_alias_set (var);
2469 ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
2473 /* Update related alias information kept in AI. This is used when
2474 building name tags, alias sets and deciding grouping heuristics.
2475 STMT is the statement to process. This function also updates
2476 ADDRESSABLE_VARS. */
2478 static void
2479 update_alias_info_1 (gimple stmt, struct alias_info *ai)
2481 bitmap addr_taken;
2482 use_operand_p use_p;
2483 ssa_op_iter iter;
2484 bool stmt_dereferences_ptr_p;
2485 enum escape_type stmt_escape_type = is_escape_site (stmt);
2486 struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
2488 stmt_dereferences_ptr_p = false;
2490 if (stmt_escape_type == ESCAPE_TO_CALL
2491 || stmt_escape_type == ESCAPE_TO_PURE_CONST)
2493 mem_ref_stats->num_call_sites++;
2494 if (stmt_escape_type == ESCAPE_TO_PURE_CONST)
2495 mem_ref_stats->num_pure_const_call_sites++;
2497 else if (stmt_escape_type == ESCAPE_TO_ASM)
2498 mem_ref_stats->num_asm_sites++;
2500 /* Mark all the variables whose address are taken by the statement. */
2501 addr_taken = gimple_addresses_taken (stmt);
2502 if (addr_taken)
2503 bitmap_ior_into (gimple_addressable_vars (cfun), addr_taken);
2505 /* Process each operand use. For pointers, determine whether they
2506 are dereferenced by the statement, or whether their value
2507 escapes, etc. */
2508 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2510 tree op, var;
2511 var_ann_t v_ann;
2512 struct ptr_info_def *pi;
2513 unsigned num_uses, num_loads, num_stores;
2515 op = USE_FROM_PTR (use_p);
2517 /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
2518 to the set of addressable variables. */
2519 if (TREE_CODE (op) == ADDR_EXPR)
2521 bitmap addressable_vars = gimple_addressable_vars (cfun);
2523 gcc_assert (gimple_code (stmt) == GIMPLE_PHI);
2524 gcc_assert (addressable_vars);
2526 /* PHI nodes don't have annotations for pinning the set
2527 of addresses taken, so we collect them here.
2529 FIXME, should we allow PHI nodes to have annotations
2530 so that they can be treated like regular statements?
2531 Currently, they are treated as second-class
2532 statements. */
2533 add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
2534 continue;
2537 /* Ignore constants (they may occur in PHI node arguments). */
2538 if (TREE_CODE (op) != SSA_NAME)
2539 continue;
2541 var = SSA_NAME_VAR (op);
2542 v_ann = var_ann (var);
2544 /* The base variable of an SSA name must be a GIMPLE register, and thus
2545 it cannot be aliased. */
2546 gcc_assert (!may_be_aliased (var));
2548 /* We are only interested in pointers. */
2549 if (!POINTER_TYPE_P (TREE_TYPE (op)))
2550 continue;
2552 pi = get_ptr_info (op);
2554 /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
2555 if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
2557 SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
2558 VEC_safe_push (tree, heap, ai->processed_ptrs, op);
2561 /* If STMT is a PHI node, then it will not have pointer
2562 dereferences and it will not be an escape point. */
2563 if (gimple_code (stmt) == GIMPLE_PHI)
2564 continue;
2566 /* Determine whether OP is a dereferenced pointer, and if STMT
2567 is an escape point, whether OP escapes. */
2568 count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
2570 /* For directly dereferenced pointers we can apply
2571 TBAA-pruning to their points-to set. We may not count the
2572 implicit dereferences &PTR->FLD here. */
2573 if (num_loads + num_stores > 0)
2574 pi->is_dereferenced = 1;
2576 /* Handle a corner case involving address expressions of the
2577 form '&PTR->FLD'. The problem with these expressions is that
2578 they do not represent a dereference of PTR. However, if some
2579 other transformation propagates them into an INDIRECT_REF
2580 expression, we end up with '*(&PTR->FLD)' which is folded
2581 into 'PTR->FLD'.
2583 So, if the original code had no other dereferences of PTR,
2584 the aliaser will not create memory tags for it, and when
2585 &PTR->FLD gets propagated to INDIRECT_REF expressions, the
2586 memory operations will receive no VDEF/VUSE operands.
2588 One solution would be to have count_uses_and_derefs consider
2589 &PTR->FLD a dereference of PTR. But that is wrong, since it
2590 is not really a dereference but an offset calculation.
2592 What we do here is to recognize these special ADDR_EXPR
2593 nodes. Since these expressions are never GIMPLE values (they
2594 are not GIMPLE invariants), they can only appear on the RHS
2595 of an assignment and their base address is always an
2596 INDIRECT_REF expression. */
2597 if (is_gimple_assign (stmt)
2598 && gimple_assign_rhs_code (stmt) == ADDR_EXPR
2599 && !is_gimple_val (gimple_assign_rhs1 (stmt)))
2601 /* If the RHS if of the form &PTR->FLD and PTR == OP, then
2602 this represents a potential dereference of PTR. */
2603 tree rhs = gimple_assign_rhs1 (stmt);
2604 tree base = get_base_address (TREE_OPERAND (rhs, 0));
2605 if (TREE_CODE (base) == INDIRECT_REF
2606 && TREE_OPERAND (base, 0) == op)
2607 num_loads++;
2610 if (num_loads + num_stores > 0)
2612 /* Mark OP as dereferenced. In a subsequent pass,
2613 dereferenced pointers that point to a set of
2614 variables will be assigned a name tag to alias
2615 all the variables OP points to. */
2616 pi->memory_tag_needed = 1;
2618 /* ??? For always executed direct dereferences we can
2619 apply TBAA-pruning to their escape set. */
2621 /* If this is a store operation, mark OP as being
2622 dereferenced to store, otherwise mark it as being
2623 dereferenced to load. */
2624 if (num_stores > 0)
2625 pointer_set_insert (ai->dereferenced_ptrs_store, var);
2626 else
2627 pointer_set_insert (ai->dereferenced_ptrs_load, var);
2629 /* Update the frequency estimate for all the dereferences of
2630 pointer OP. */
2631 update_mem_sym_stats_from_stmt (op, stmt, num_loads, num_stores);
2633 /* Indicate that STMT contains pointer dereferences. */
2634 stmt_dereferences_ptr_p = true;
2637 if (stmt_escape_type != NO_ESCAPE && num_loads + num_stores < num_uses)
2639 /* If STMT is an escape point and STMT contains at
2640 least one direct use of OP, then the value of OP
2641 escapes and so the pointed-to variables need to
2642 be marked call-clobbered. */
2643 pi->value_escapes_p = 1;
2644 pi->escape_mask |= stmt_escape_type;
2646 /* If the statement makes a function call, assume
2647 that pointer OP will be dereferenced in a store
2648 operation inside the called function. */
2649 if (is_gimple_call (stmt)
2650 || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL)
2652 pointer_set_insert (ai->dereferenced_ptrs_store, var);
2653 pi->memory_tag_needed = 1;
2658 if (gimple_code (stmt) == GIMPLE_PHI)
2659 return;
2661 /* Mark stored variables in STMT as being written to and update the
2662 memory reference stats for all memory symbols referenced by STMT. */
2663 if (gimple_references_memory_p (stmt))
2665 unsigned i;
2666 bitmap_iterator bi;
2668 mem_ref_stats->num_mem_stmts++;
2670 /* Notice that we only update memory reference stats for symbols
2671 loaded and stored by the statement if the statement does not
2672 contain pointer dereferences and it is not a call/asm site.
2673 This is to avoid double accounting problems when creating
2674 memory partitions. After computing points-to information,
2675 pointer dereference statistics are used to update the
2676 reference stats of the pointed-to variables, so here we
2677 should only update direct references to symbols.
2679 Indirect references are not updated here for two reasons: (1)
2680 The first time we compute alias information, the sets
2681 LOADED/STORED are empty for pointer dereferences, (2) After
2682 partitioning, LOADED/STORED may have references to
2683 partitions, not the original pointed-to variables. So, if we
2684 always counted LOADED/STORED here and during partitioning, we
2685 would count many symbols more than once.
2687 This does cause some imprecision when a statement has a
2688 combination of direct symbol references and pointer
2689 dereferences (e.g., MEMORY_VAR = *PTR) or if a call site has
2690 memory symbols in its argument list, but these cases do not
2691 occur so frequently as to constitute a serious problem. */
2692 if (gimple_stored_syms (stmt))
2693 EXECUTE_IF_SET_IN_BITMAP (gimple_stored_syms (stmt), 0, i, bi)
2695 tree sym = referenced_var (i);
2696 pointer_set_insert (ai->written_vars, sym);
2697 if (!stmt_dereferences_ptr_p
2698 && stmt_escape_type != ESCAPE_TO_CALL
2699 && stmt_escape_type != ESCAPE_TO_PURE_CONST
2700 && stmt_escape_type != ESCAPE_TO_ASM)
2701 update_mem_sym_stats_from_stmt (sym, stmt, 0, 1);
2704 if (!stmt_dereferences_ptr_p
2705 && gimple_loaded_syms (stmt)
2706 && stmt_escape_type != ESCAPE_TO_CALL
2707 && stmt_escape_type != ESCAPE_TO_PURE_CONST
2708 && stmt_escape_type != ESCAPE_TO_ASM)
2709 EXECUTE_IF_SET_IN_BITMAP (gimple_loaded_syms (stmt), 0, i, bi)
2710 update_mem_sym_stats_from_stmt (referenced_var (i), stmt, 1, 0);
2714 /* Update various related attributes like escaped addresses,
2715 pointer dereferences for loads and stores. This is used
2716 when creating name tags and alias sets. */
2718 static void
2719 update_alias_info (struct alias_info *ai)
2721 basic_block bb;
2723 FOR_EACH_BB (bb)
2725 gimple_stmt_iterator gsi;
2726 gimple phi;
2728 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2730 phi = gsi_stmt (gsi);
2731 if (is_gimple_reg (PHI_RESULT (phi)))
2732 update_alias_info_1 (phi, ai);
2735 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2736 update_alias_info_1 (gsi_stmt (gsi), ai);
2740 /* Create memory tags for all the dereferenced pointers and build the
2741 ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
2742 sets. Based on the address escape and points-to information collected
2743 earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
2744 variables whose address is not needed anymore. */
2746 static void
2747 setup_pointers_and_addressables (struct alias_info *ai)
2749 size_t num_addressable_vars, num_pointers;
2750 referenced_var_iterator rvi;
2751 tree var;
2752 VEC (tree, heap) *varvec = NULL;
2753 safe_referenced_var_iterator srvi;
2755 /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
2756 num_addressable_vars = num_pointers = 0;
2758 FOR_EACH_REFERENCED_VAR (var, rvi)
2760 if (may_be_aliased (var))
2761 num_addressable_vars++;
2763 if (POINTER_TYPE_P (TREE_TYPE (var)))
2765 /* Since we don't keep track of volatile variables, assume that
2766 these pointers are used in indirect store operations. */
2767 if (TREE_THIS_VOLATILE (var))
2768 pointer_set_insert (ai->dereferenced_ptrs_store, var);
2770 num_pointers++;
2774 /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
2775 always going to be slightly bigger than we actually need them
2776 because some TREE_ADDRESSABLE variables will be marked
2777 non-addressable below and only pointers with unique symbol tags are
2778 going to be added to POINTERS. */
2779 ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
2780 ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
2781 ai->num_addressable_vars = 0;
2782 ai->num_pointers = 0;
2784 FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
2786 /* Name memory tags already have flow-sensitive aliasing
2787 information, so they need not be processed by
2788 compute_flow_insensitive_aliasing. Similarly, symbol memory
2789 tags are already accounted for when we process their
2790 associated pointer.
2792 Structure fields, on the other hand, have to have some of this
2793 information processed for them, but it's pointless to mark them
2794 non-addressable (since they are fake variables anyway). */
2795 if (MTAG_P (var))
2796 continue;
2798 /* Remove the ADDRESSABLE flag from every addressable variable whose
2799 address is not needed anymore. This is caused by the propagation
2800 of ADDR_EXPR constants into INDIRECT_REF expressions and the
2801 removal of dead pointer assignments done by the early scalar
2802 cleanup passes. */
2803 if (TREE_ADDRESSABLE (var))
2805 if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var))
2806 && TREE_CODE (var) != RESULT_DECL
2807 && !is_global_var (var))
2809 bool okay_to_mark = true;
2811 /* Since VAR is now a regular GIMPLE register, we will need
2812 to rename VAR into SSA afterwards. */
2813 mark_sym_for_renaming (var);
2815 /* The address of VAR is not needed, remove the
2816 addressable bit, so that it can be optimized as a
2817 regular variable. */
2818 if (okay_to_mark)
2820 /* The memory partition holding VAR will no longer
2821 contain VAR, and statements referencing it will need
2822 to be updated. */
2823 if (memory_partition (var))
2824 mark_sym_for_renaming (memory_partition (var));
2826 mark_non_addressable (var);
2831 /* Global variables and addressable locals may be aliased. Create an
2832 entry in ADDRESSABLE_VARS for VAR. */
2833 if (may_be_aliased (var))
2835 create_alias_map_for (var, ai);
2836 mark_sym_for_renaming (var);
2839 /* Add pointer variables that have been dereferenced to the POINTERS
2840 array and create a symbol memory tag for them. */
2841 if (POINTER_TYPE_P (TREE_TYPE (var)))
2843 if ((pointer_set_contains (ai->dereferenced_ptrs_store, var)
2844 || pointer_set_contains (ai->dereferenced_ptrs_load, var)))
2846 tree tag, old_tag;
2847 var_ann_t t_ann;
2849 /* If pointer VAR still doesn't have a memory tag
2850 associated with it, create it now or re-use an
2851 existing one. */
2852 tag = get_smt_for (var, ai);
2853 t_ann = var_ann (tag);
2855 /* The symbol tag will need to be renamed into SSA
2856 afterwards. Note that we cannot do this inside
2857 get_smt_for because aliasing may run multiple times
2858 and we only create symbol tags the first time. */
2859 mark_sym_for_renaming (tag);
2861 /* Similarly, if pointer VAR used to have another type
2862 tag, we will need to process it in the renamer to
2863 remove the stale virtual operands. */
2864 old_tag = symbol_mem_tag (var);
2865 if (old_tag)
2866 mark_sym_for_renaming (old_tag);
2868 /* Associate the tag with pointer VAR. */
2869 set_symbol_mem_tag (var, tag);
2871 /* If pointer VAR has been used in a store operation,
2872 then its memory tag must be marked as written-to. */
2873 if (pointer_set_contains (ai->dereferenced_ptrs_store, var))
2874 pointer_set_insert (ai->written_vars, tag);
2876 else
2878 /* The pointer has not been dereferenced. If it had a
2879 symbol memory tag, remove it and mark the old tag for
2880 renaming to remove it out of the IL. */
2881 tree tag = symbol_mem_tag (var);
2882 if (tag)
2884 mark_sym_for_renaming (tag);
2885 set_symbol_mem_tag (var, NULL_TREE);
2891 VEC_free (tree, heap, varvec);
2895 /* Determine whether to use .GLOBAL_VAR to model call clobbering
2896 semantics. If the function makes no references to global
2897 variables and contains at least one call to a non-pure function,
2898 then we need to mark the side-effects of the call using .GLOBAL_VAR
2899 to represent all possible global memory referenced by the callee. */
2901 static void
2902 maybe_create_global_var (void)
2904 /* No need to create it, if we have one already. */
2905 if (gimple_global_var (cfun) == NULL_TREE)
2907 struct mem_ref_stats_d *stats = gimple_mem_ref_stats (cfun);
2909 /* Create .GLOBAL_VAR if there are no call-clobbered
2910 variables and the program contains a mixture of pure/const
2911 and regular function calls. This is to avoid the problem
2912 described in PR 20115:
2914 int X;
2915 int func_pure (void) { return X; }
2916 int func_non_pure (int a) { X += a; }
2917 int foo ()
2919 int a = func_pure ();
2920 func_non_pure (a);
2921 a = func_pure ();
2922 return a;
2925 Since foo() has no call-clobbered variables, there is
2926 no relationship between the calls to func_pure and
2927 func_non_pure. Since func_pure has no side-effects, value
2928 numbering optimizations elide the second call to func_pure.
2929 So, if we have some pure/const and some regular calls in the
2930 program we create .GLOBAL_VAR to avoid missing these
2931 relations. */
2932 if (bitmap_empty_p (gimple_call_clobbered_vars (cfun))
2933 && stats->num_call_sites > 0
2934 && stats->num_pure_const_call_sites > 0
2935 && stats->num_call_sites > stats->num_pure_const_call_sites)
2936 create_global_var ();
2941 /* Return TRUE if pointer PTR may point to variable VAR.
2943 MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
2944 This is needed because when checking for type conflicts we are
2945 interested in the alias set of the memory location pointed-to by
2946 PTR. The alias set of PTR itself is irrelevant.
2948 VAR_ALIAS_SET is the alias set for VAR. */
2950 bool
2951 may_alias_p (tree ptr, alias_set_type mem_alias_set,
2952 tree var, alias_set_type var_alias_set,
2953 bool alias_set_only)
2955 tree mem;
2957 alias_stats.alias_queries++;
2958 alias_stats.simple_queries++;
2960 /* By convention, a variable cannot alias itself. */
2961 mem = symbol_mem_tag (ptr);
2962 if (mem == var)
2964 alias_stats.alias_noalias++;
2965 alias_stats.simple_resolved++;
2966 return false;
2969 /* If -fargument-noalias-global is > 2, pointer arguments may
2970 not point to anything else. */
2971 if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
2973 alias_stats.alias_noalias++;
2974 alias_stats.simple_resolved++;
2975 return false;
2978 /* If -fargument-noalias-global is > 1, pointer arguments may
2979 not point to global variables. */
2980 if (flag_argument_noalias > 1 && is_global_var (var)
2981 && TREE_CODE (ptr) == PARM_DECL)
2983 alias_stats.alias_noalias++;
2984 alias_stats.simple_resolved++;
2985 return false;
2988 /* If the pointed to memory has alias set zero, or the pointer
2989 is ref-all, or the pointer decl is marked that no TBAA is to
2990 be applied, the MEM can alias VAR. */
2991 if (mem_alias_set == 0
2992 || DECL_POINTER_ALIAS_SET (ptr) == 0
2993 || TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (ptr))
2994 || DECL_NO_TBAA_P (ptr))
2996 alias_stats.alias_mayalias++;
2997 alias_stats.simple_resolved++;
2998 return true;
3001 gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
3003 alias_stats.tbaa_queries++;
3005 /* If the alias sets don't conflict then MEM cannot alias VAR. */
3006 if (mem_alias_set != var_alias_set
3007 && !alias_set_subset_of (mem_alias_set, var_alias_set))
3009 alias_stats.alias_noalias++;
3010 alias_stats.tbaa_resolved++;
3011 return false;
3014 /* If VAR is a record or union type, PTR cannot point into VAR
3015 unless there is some explicit address operation in the
3016 program that can reference a field of the type pointed-to by
3017 PTR. This also assumes that the types of both VAR and PTR
3018 are contained within the compilation unit, and that there is
3019 no fancy addressing arithmetic associated with any of the
3020 types involved. */
3021 if (mem_alias_set != 0 && var_alias_set != 0)
3023 tree ptr_type = TREE_TYPE (ptr);
3024 tree var_type = TREE_TYPE (var);
3026 /* The star count is -1 if the type at the end of the
3027 pointer_to chain is not a record or union type. */
3028 if (!alias_set_only &&
3029 0 /* FIXME tuples ipa_type_escape_star_count_of_interesting_type (var_type) >= 0*/)
3031 int ptr_star_count = 0;
3033 /* ipa_type_escape_star_count_of_interesting_type is a
3034 little too restrictive for the pointer type, need to
3035 allow pointers to primitive types as long as those
3036 types cannot be pointers to everything. */
3037 while (POINTER_TYPE_P (ptr_type))
3039 /* Strip the *s off. */
3040 ptr_type = TREE_TYPE (ptr_type);
3041 ptr_star_count++;
3044 /* There does not appear to be a better test to see if
3045 the pointer type was one of the pointer to everything
3046 types. */
3047 if (ptr_star_count > 0)
3049 alias_stats.structnoaddress_queries++;
3050 if (ipa_type_escape_field_does_not_clobber_p (var_type,
3051 TREE_TYPE (ptr)))
3053 alias_stats.structnoaddress_resolved++;
3054 alias_stats.alias_noalias++;
3055 return false;
3058 else if (ptr_star_count == 0)
3060 /* If PTR_TYPE was not really a pointer to type, it cannot
3061 alias. */
3062 alias_stats.structnoaddress_queries++;
3063 alias_stats.structnoaddress_resolved++;
3064 alias_stats.alias_noalias++;
3065 return false;
3070 alias_stats.alias_mayalias++;
3071 return true;
3074 /* Return true, if PTR may point to a global variable. */
3076 bool
3077 may_point_to_global_var (tree ptr)
3079 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3081 /* If we do not have points-to information for this variable,
3082 we have to punt. */
3083 if (!pi
3084 || !pi->name_mem_tag)
3085 return true;
3087 /* The name memory tag is marked as global variable if the points-to
3088 set contains a global variable. */
3089 return is_global_var (pi->name_mem_tag);
3092 /* Add ALIAS to the set of variables that may alias VAR. */
3094 static void
3095 add_may_alias (tree var, tree alias)
3097 /* Don't allow self-referential aliases. */
3098 gcc_assert (var != alias);
3100 /* ALIAS must be addressable if it's being added to an alias set. */
3101 #if 1
3102 TREE_ADDRESSABLE (alias) = 1;
3103 #else
3104 gcc_assert (may_be_aliased (alias));
3105 #endif
3107 /* VAR must be a symbol or a name tag. */
3108 gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG
3109 || TREE_CODE (var) == NAME_MEMORY_TAG);
3111 if (MTAG_ALIASES (var) == NULL)
3112 MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack);
3114 bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias));
3118 /* Mark pointer PTR as pointing to an arbitrary memory location. */
3120 static void
3121 set_pt_anything (tree ptr)
3123 struct ptr_info_def *pi = get_ptr_info (ptr);
3125 pi->pt_anything = 1;
3126 /* Anything includes global memory. */
3127 pi->pt_global_mem = 1;
3128 pi->pt_vars = NULL;
3130 /* The pointer used to have a name tag, but we now found it pointing
3131 to an arbitrary location. The name tag needs to be renamed and
3132 disassociated from PTR. */
3133 if (pi->name_mem_tag)
3135 mark_sym_for_renaming (pi->name_mem_tag);
3136 pi->name_mem_tag = NULL_TREE;
3141 /* Return true if STMT is an "escape" site from the current function. Escape
3142 sites those statements which might expose the address of a variable
3143 outside the current function. STMT is an escape site iff:
3145 1- STMT is a function call, or
3146 2- STMT is an __asm__ expression, or
3147 3- STMT is an assignment to a non-local variable, or
3148 4- STMT is a return statement.
3150 Return the type of escape site found, if we found one, or NO_ESCAPE
3151 if none. */
3153 enum escape_type
3154 is_escape_site (gimple stmt)
3156 if (is_gimple_call (stmt))
3158 if (gimple_call_flags (stmt) & (ECF_PURE | ECF_CONST))
3159 return ESCAPE_TO_PURE_CONST;
3161 return ESCAPE_TO_CALL;
3163 else if (gimple_code (stmt) == GIMPLE_ASM)
3164 return ESCAPE_TO_ASM;
3165 else if (is_gimple_assign (stmt))
3167 tree lhs = gimple_assign_lhs (stmt);
3169 /* Get to the base of _REF nodes. */
3170 if (TREE_CODE (lhs) != SSA_NAME)
3171 lhs = get_base_address (lhs);
3173 /* If we couldn't recognize the LHS of the assignment, assume that it
3174 is a non-local store. */
3175 if (lhs == NULL_TREE)
3176 return ESCAPE_UNKNOWN;
3178 if (gimple_assign_cast_p (stmt))
3180 tree from = TREE_TYPE (gimple_assign_rhs1 (stmt));
3181 tree to = TREE_TYPE (lhs);
3183 /* If the RHS is a conversion between a pointer and an integer, the
3184 pointer escapes since we can't track the integer. */
3185 if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
3186 return ESCAPE_BAD_CAST;
3189 /* If the LHS is an SSA name, it can't possibly represent a non-local
3190 memory store. */
3191 if (TREE_CODE (lhs) == SSA_NAME)
3192 return NO_ESCAPE;
3194 /* If the LHS is a non-global decl, it isn't a non-local memory store.
3195 If the LHS escapes, the RHS escape is dealt with in the PTA solver. */
3196 if (DECL_P (lhs)
3197 && !is_global_var (lhs))
3198 return NO_ESCAPE;
3200 /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
3201 local variables we cannot be sure if it will escape, because we
3202 don't have information about objects not in SSA form. Need to
3203 implement something along the lines of
3205 J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
3206 Midkiff, ``Escape analysis for java,'' in Proceedings of the
3207 Conference on Object-Oriented Programming Systems, Languages, and
3208 Applications (OOPSLA), pp. 1-19, 1999. */
3209 return ESCAPE_STORED_IN_GLOBAL;
3211 else if (gimple_code (stmt) == GIMPLE_RETURN)
3212 return ESCAPE_TO_RETURN;
3214 return NO_ESCAPE;
3217 /* Create a new memory tag of type TYPE.
3218 Does NOT push it into the current binding. */
3220 tree
3221 create_tag_raw (enum tree_code code, tree type, const char *prefix)
3223 tree tmp_var;
3225 tmp_var = build_decl (code, create_tmp_var_name (prefix), type);
3227 /* Memory tags are always writable and non-static. */
3228 TREE_READONLY (tmp_var) = 0;
3229 TREE_STATIC (tmp_var) = 0;
3231 /* It doesn't start out global. */
3232 MTAG_GLOBAL (tmp_var) = 0;
3233 TREE_USED (tmp_var) = 1;
3235 return tmp_var;
3238 /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
3239 is considered to represent all the pointers whose pointed-to types are
3240 in the same alias set class. Otherwise, the tag represents a single
3241 SSA_NAME pointer variable. */
3243 static tree
3244 create_memory_tag (tree type, bool is_type_tag)
3246 tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
3247 type, (is_type_tag) ? "SMT" : "NMT");
3249 /* By default, memory tags are local variables. Alias analysis will
3250 determine whether they should be considered globals. */
3251 DECL_CONTEXT (tag) = current_function_decl;
3253 /* Memory tags are by definition addressable. */
3254 TREE_ADDRESSABLE (tag) = 1;
3256 set_symbol_mem_tag (tag, NULL_TREE);
3258 /* Add the tag to the symbol table. */
3259 add_referenced_var (tag);
3261 return tag;
3265 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
3266 This is used if P_i has been found to point to a specific set of
3267 variables or to a non-aliased memory location like the address returned
3268 by malloc functions. */
3270 static tree
3271 get_nmt_for (tree ptr)
3273 struct ptr_info_def *pi = get_ptr_info (ptr);
3274 tree tag = pi->name_mem_tag;
3276 if (tag == NULL_TREE)
3277 tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
3278 return tag;
3282 /* Return the symbol memory tag associated to pointer PTR. A memory
3283 tag is an artificial variable that represents the memory location
3284 pointed-to by PTR. It is used to model the effects of pointer
3285 de-references on addressable variables.
3287 AI points to the data gathered during alias analysis. This
3288 function populates the array AI->POINTERS. */
3290 static tree
3291 get_smt_for (tree ptr, struct alias_info *ai)
3293 size_t i;
3294 tree tag;
3295 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
3296 alias_set_type tag_set = get_alias_set (tag_type);
3298 /* To avoid creating unnecessary memory tags, only create one memory tag
3299 per alias set class. Note that it may be tempting to group
3300 memory tags based on conflicting alias sets instead of
3301 equivalence. That would be wrong because alias sets are not
3302 necessarily transitive (as demonstrated by the libstdc++ test
3303 23_containers/vector/cons/4.cc). Given three alias sets A, B, C
3304 such that conflicts (A, B) == true and conflicts (A, C) == true,
3305 it does not necessarily follow that conflicts (B, C) == true. */
3306 for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
3308 struct alias_map_d *curr = ai->pointers[i];
3309 tree curr_tag = symbol_mem_tag (curr->var);
3310 if (tag_set == curr->set)
3312 tag = curr_tag;
3313 break;
3317 /* If VAR cannot alias with any of the existing memory tags, create a new
3318 tag for PTR and add it to the POINTERS array. */
3319 if (tag == NULL_TREE)
3321 struct alias_map_d *alias_map;
3323 /* If PTR did not have a symbol tag already, create a new SMT.*
3324 artificial variable representing the memory location
3325 pointed-to by PTR. */
3326 tag = symbol_mem_tag (ptr);
3327 if (tag == NULL_TREE)
3328 tag = create_memory_tag (tag_type, true);
3330 /* Add PTR to the POINTERS array. Note that we are not interested in
3331 PTR's alias set. Instead, we cache the alias set for the memory that
3332 PTR points to. */
3333 alias_map = XCNEW (struct alias_map_d);
3334 alias_map->var = ptr;
3335 alias_map->set = tag_set;
3336 ai->pointers[ai->num_pointers++] = alias_map;
3339 /* If the pointed-to type is volatile, so is the tag. */
3340 TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
3342 /* Make sure that the symbol tag has the same alias set as the
3343 pointed-to type or at least accesses through the pointer will
3344 alias that set. The latter can happen after the vectorizer
3345 created pointers of vector type. */
3346 gcc_assert (tag_set == get_alias_set (tag)
3347 || alias_set_subset_of (tag_set, get_alias_set (tag)));
3349 return tag;
3353 /* Create GLOBAL_VAR, an artificial global variable to act as a
3354 representative of all the variables that may be clobbered by function
3355 calls. */
3357 static void
3358 create_global_var (void)
3360 tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
3361 void_type_node);
3362 DECL_ARTIFICIAL (global_var) = 1;
3363 TREE_READONLY (global_var) = 0;
3364 DECL_EXTERNAL (global_var) = 1;
3365 TREE_STATIC (global_var) = 1;
3366 TREE_USED (global_var) = 1;
3367 DECL_CONTEXT (global_var) = NULL_TREE;
3368 TREE_THIS_VOLATILE (global_var) = 0;
3369 TREE_ADDRESSABLE (global_var) = 0;
3371 create_var_ann (global_var);
3372 mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
3373 add_referenced_var (global_var);
3374 mark_sym_for_renaming (global_var);
3375 cfun->gimple_df->global_var = global_var;
3379 /* Dump alias statistics on FILE. */
3381 static void
3382 dump_alias_stats (FILE *file)
3384 const char *funcname
3385 = lang_hooks.decl_printable_name (current_function_decl, 2);
3386 fprintf (file, "\nAlias statistics for %s\n\n", funcname);
3387 fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
3388 fprintf (file, "Total alias mayalias results:\t%u\n",
3389 alias_stats.alias_mayalias);
3390 fprintf (file, "Total alias noalias results:\t%u\n",
3391 alias_stats.alias_noalias);
3392 fprintf (file, "Total simple queries:\t%u\n",
3393 alias_stats.simple_queries);
3394 fprintf (file, "Total simple resolved:\t%u\n",
3395 alias_stats.simple_resolved);
3396 fprintf (file, "Total TBAA queries:\t%u\n",
3397 alias_stats.tbaa_queries);
3398 fprintf (file, "Total TBAA resolved:\t%u\n",
3399 alias_stats.tbaa_resolved);
3400 fprintf (file, "Total non-addressable structure type queries:\t%u\n",
3401 alias_stats.structnoaddress_queries);
3402 fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
3403 alias_stats.structnoaddress_resolved);
3407 /* Dump alias information on FILE. */
3409 void
3410 dump_alias_info (FILE *file)
3412 size_t i;
3413 const char *funcname
3414 = lang_hooks.decl_printable_name (current_function_decl, 2);
3415 referenced_var_iterator rvi;
3416 tree var;
3418 fprintf (file, "\nAlias information for %s\n\n", funcname);
3420 dump_memory_partitions (file);
3422 fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
3424 fprintf (file, "Aliased symbols\n\n");
3426 FOR_EACH_REFERENCED_VAR (var, rvi)
3428 if (may_be_aliased (var))
3429 dump_variable (file, var);
3432 fprintf (file, "\nDereferenced pointers\n\n");
3434 FOR_EACH_REFERENCED_VAR (var, rvi)
3435 if (symbol_mem_tag (var))
3436 dump_variable (file, var);
3438 fprintf (file, "\nSymbol memory tags\n\n");
3440 FOR_EACH_REFERENCED_VAR (var, rvi)
3442 if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
3443 dump_variable (file, var);
3446 fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
3448 fprintf (file, "SSA_NAME pointers\n\n");
3449 for (i = 1; i < num_ssa_names; i++)
3451 tree ptr = ssa_name (i);
3452 struct ptr_info_def *pi;
3454 if (ptr == NULL_TREE)
3455 continue;
3457 pi = SSA_NAME_PTR_INFO (ptr);
3458 if (!SSA_NAME_IN_FREE_LIST (ptr)
3459 && pi
3460 && pi->name_mem_tag)
3461 dump_points_to_info_for (file, ptr);
3464 fprintf (file, "\nName memory tags\n\n");
3466 FOR_EACH_REFERENCED_VAR (var, rvi)
3468 if (TREE_CODE (var) == NAME_MEMORY_TAG)
3469 dump_variable (file, var);
3472 fprintf (file, "\n");
3476 /* Dump alias information on stderr. */
3478 void
3479 debug_alias_info (void)
3481 dump_alias_info (stderr);
3485 /* Return the alias information associated with pointer T. It creates a
3486 new instance if none existed. */
3488 struct ptr_info_def *
3489 get_ptr_info (tree t)
3491 struct ptr_info_def *pi;
3493 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
3495 pi = SSA_NAME_PTR_INFO (t);
3496 if (pi == NULL)
3498 pi = GGC_CNEW (struct ptr_info_def);
3499 SSA_NAME_PTR_INFO (t) = pi;
3502 return pi;
3505 /* Dump points-to information for SSA_NAME PTR into FILE. */
3507 void
3508 dump_points_to_info_for (FILE *file, tree ptr)
3510 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3512 print_generic_expr (file, ptr, dump_flags);
3514 if (pi)
3516 if (pi->name_mem_tag)
3518 fprintf (file, ", name memory tag: ");
3519 print_generic_expr (file, pi->name_mem_tag, dump_flags);
3522 if (pi->is_dereferenced)
3523 fprintf (file, ", is dereferenced");
3524 else if (pi->memory_tag_needed)
3525 fprintf (file, ", is dereferenced in call");
3527 if (pi->value_escapes_p)
3528 fprintf (file, ", its value escapes");
3530 if (pi->pt_anything)
3531 fprintf (file, ", points-to anything");
3533 if (pi->pt_null)
3534 fprintf (file, ", points-to NULL");
3536 if (pi->pt_vars)
3538 fprintf (file, ", points-to vars: ");
3539 dump_decl_set (file, pi->pt_vars);
3543 fprintf (file, "\n");
3547 /* Dump points-to information for VAR into stderr. */
3549 void
3550 debug_points_to_info_for (tree var)
3552 dump_points_to_info_for (stderr, var);
3556 /* Dump points-to information into FILE. NOTE: This function is slow, as
3557 it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
3559 void
3560 dump_points_to_info (FILE *file ATTRIBUTE_UNUSED)
3562 basic_block bb;
3563 gimple_stmt_iterator si;
3564 ssa_op_iter iter;
3565 const char *fname =
3566 lang_hooks.decl_printable_name (current_function_decl, 2);
3567 referenced_var_iterator rvi;
3568 tree var;
3570 fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
3572 /* First dump points-to information for the default definitions of
3573 pointer variables. This is necessary because default definitions are
3574 not part of the code. */
3575 FOR_EACH_REFERENCED_VAR (var, rvi)
3577 if (POINTER_TYPE_P (TREE_TYPE (var)))
3579 tree def = gimple_default_def (cfun, var);
3580 if (def)
3581 dump_points_to_info_for (file, def);
3585 /* Dump points-to information for every pointer defined in the program. */
3586 FOR_EACH_BB (bb)
3588 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
3590 gimple phi = gsi_stmt (si);
3591 tree ptr = PHI_RESULT (phi);
3592 if (POINTER_TYPE_P (TREE_TYPE (ptr)))
3593 dump_points_to_info_for (file, ptr);
3596 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
3598 gimple stmt = gsi_stmt (si);
3599 tree def;
3600 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3601 if (TREE_CODE (def) == SSA_NAME
3602 && POINTER_TYPE_P (TREE_TYPE (def)))
3603 dump_points_to_info_for (file, def);
3607 fprintf (file, "\n");
3611 /* Dump points-to info pointed to by PTO into STDERR. */
3613 void
3614 debug_points_to_info (void)
3616 dump_points_to_info (stderr);
3619 /* Dump to FILE the list of variables that may be aliasing VAR. */
3621 void
3622 dump_may_aliases_for (FILE *file, tree var)
3624 bitmap aliases;
3626 aliases = MTAG_ALIASES (var);
3627 if (aliases)
3629 bitmap_iterator bi;
3630 unsigned int i;
3631 tree al;
3633 fprintf (file, "{ ");
3634 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
3636 al = referenced_var (i);
3637 print_generic_expr (file, al, dump_flags);
3638 fprintf (file, " ");
3640 fprintf (file, "}");
3645 /* Dump to stderr the list of variables that may be aliasing VAR. */
3647 void
3648 debug_may_aliases_for (tree var)
3650 dump_may_aliases_for (stderr, var);
3653 /* Return true if VAR may be aliased. */
3655 bool
3656 may_be_aliased (tree var)
3658 /* Obviously. */
3659 if (TREE_ADDRESSABLE (var))
3660 return true;
3662 /* Globally visible variables can have their addresses taken by other
3663 translation units. */
3664 if (MTAG_P (var)
3665 && MTAG_GLOBAL (var))
3666 return true;
3667 else if (!MTAG_P (var)
3668 && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
3669 return true;
3671 /* Automatic variables can't have their addresses escape any other
3672 way. This must be after the check for global variables, as
3673 extern declarations do not have TREE_STATIC set. */
3674 if (!TREE_STATIC (var))
3675 return false;
3677 return false;
3680 /* The following is based on code in add_stmt_operand to ensure that the
3681 same defs/uses/vdefs/vuses will be found after replacing a reference
3682 to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
3683 is the address of var. Return a memtag for the ptr, after adding the
3684 proper may_aliases to it (which are the aliases of var, if it has any,
3685 or var itself). */
3687 static tree
3688 add_may_alias_for_new_tag (tree tag, tree var)
3690 bitmap aliases = NULL;
3692 if (MTAG_P (var))
3693 aliases = may_aliases (var);
3695 /* Case 1: |aliases| == 1 */
3696 if (aliases
3697 && bitmap_single_bit_set_p (aliases))
3699 tree ali = referenced_var (bitmap_first_set_bit (aliases));
3700 if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
3701 return ali;
3704 /* Case 2: |aliases| == 0 */
3705 if (aliases == NULL)
3706 add_may_alias (tag, var);
3707 else
3709 /* Case 3: |aliases| > 1 */
3710 union_alias_set_into (tag, aliases);
3712 return tag;
3715 /* Create a new symbol tag for PTR. Construct the may-alias list of
3716 this type tag so that it has the aliasing of VAR according to the
3717 location accessed by EXPR.
3719 Note, the set of aliases represented by the new symbol tag are not
3720 marked for renaming. */
3722 void
3723 new_type_alias (tree ptr, tree var, tree expr)
3725 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
3726 tree tag;
3727 tree ali = NULL_TREE;
3728 HOST_WIDE_INT offset, size, maxsize;
3729 tree ref;
3731 gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
3732 gcc_assert (!MTAG_P (var));
3734 ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
3735 gcc_assert (ref);
3737 tag = create_memory_tag (tag_type, true);
3738 set_symbol_mem_tag (ptr, tag);
3740 ali = add_may_alias_for_new_tag (tag, var);
3742 set_symbol_mem_tag (ptr, ali);
3743 MTAG_GLOBAL (tag) = is_global_var (var);
3747 /* Reset the call_clobbered flags on our referenced vars. In
3748 theory, this only needs to be done for globals. */
3750 static unsigned int
3751 reset_cc_flags (void)
3753 tree var;
3754 referenced_var_iterator rvi;
3756 FOR_EACH_REFERENCED_VAR (var, rvi)
3757 var_ann (var)->call_clobbered = false;
3758 return 0;
3761 struct gimple_opt_pass pass_reset_cc_flags =
3764 GIMPLE_PASS,
3765 NULL, /* name */
3766 NULL, /* gate */
3767 reset_cc_flags, /* execute */
3768 NULL, /* sub */
3769 NULL, /* next */
3770 0, /* static_pass_number */
3771 0, /* tv_id */
3772 PROP_referenced_vars |PROP_cfg, /* properties_required */
3773 0, /* properties_provided */
3774 0, /* properties_destroyed */
3775 0, /* todo_flags_start */
3776 0 /* todo_flags_finish */
3781 /* A dummy pass to cause aliases to be computed via TODO_rebuild_alias. */
3783 struct gimple_opt_pass pass_build_alias =
3786 GIMPLE_PASS,
3787 "alias", /* name */
3788 NULL, /* gate */
3789 NULL, /* execute */
3790 NULL, /* sub */
3791 NULL, /* next */
3792 0, /* static_pass_number */
3793 0, /* tv_id */
3794 PROP_cfg | PROP_ssa, /* properties_required */
3795 PROP_alias, /* properties_provided */
3796 0, /* properties_destroyed */
3797 0, /* todo_flags_start */
3798 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */