1 /* Alias analysis for trees.
2 Copyright (C) 2004, 2005, 2006, 2007 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)
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/>. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
33 #include "langhooks.h"
36 #include "diagnostic.h"
37 #include "tree-dump.h"
38 #include "tree-gimple.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
41 #include "tree-pass.h"
42 #include "tree-ssa-structalias.h"
45 #include "ipa-type-escape.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
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
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
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
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
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
169 /* Structure to map a variable to its alias set. */
172 /* Variable and its alias set. */
178 /* Counters used to display statistics on alias analysis. */
181 unsigned int alias_queries;
182 unsigned int alias_mayalias;
183 unsigned int alias_noalias;
184 unsigned int simple_queries;
185 unsigned int simple_resolved;
186 unsigned int tbaa_queries;
187 unsigned int tbaa_resolved;
188 unsigned int structnoaddress_queries;
189 unsigned int structnoaddress_resolved;
193 /* Local variables. */
194 static struct alias_stats_d alias_stats;
195 static bitmap_obstack alias_bitmap_obstack;
197 /* Local functions. */
198 static void compute_flow_insensitive_aliasing (struct alias_info *);
199 static void finalize_ref_all_pointers (struct alias_info *);
200 static void dump_alias_stats (FILE *);
201 static bool may_alias_p (tree, alias_set_type, tree, alias_set_type, bool);
202 static tree create_memory_tag (tree type, bool is_type_tag);
203 static tree get_smt_for (tree, struct alias_info *);
204 static tree get_nmt_for (tree);
205 static void add_may_alias (tree, tree);
206 static struct alias_info *init_alias_info (void);
207 static void delete_alias_info (struct alias_info *);
208 static void compute_flow_sensitive_aliasing (struct alias_info *);
209 static void setup_pointers_and_addressables (struct alias_info *);
210 static void create_global_var (void);
211 static void maybe_create_global_var (void);
212 static void set_pt_anything (tree);
214 void debug_mp_info (VEC(mem_sym_stats_t,heap) *);
216 static alloc_pool mem_sym_stats_pool;
218 /* Return memory reference stats for symbol VAR. Create a new slot in
219 cfun->gimple_df->mem_sym_stats if needed. */
221 static struct mem_sym_stats_d *
222 get_mem_sym_stats_for (tree var)
225 struct mem_sym_stats_d *stats;
226 struct pointer_map_t *map = gimple_mem_ref_stats (cfun)->mem_sym_stats;
230 slot = pointer_map_insert (map, var);
233 stats = pool_alloc (mem_sym_stats_pool);
234 memset (stats, 0, sizeof (*stats));
236 *slot = (void *) stats;
239 stats = (struct mem_sym_stats_d *) *slot;
245 /* Set MPT to be the memory partition associated with symbol SYM. */
248 set_memory_partition (tree sym, tree mpt)
250 #if defined ENABLE_CHECKING
252 gcc_assert (TREE_CODE (mpt) == MEMORY_PARTITION_TAG
253 && !is_gimple_reg (sym));
256 var_ann (sym)->mpt = mpt;
259 if (MPT_SYMBOLS (mpt) == NULL)
260 MPT_SYMBOLS (mpt) = BITMAP_ALLOC (&alias_bitmap_obstack);
262 bitmap_set_bit (MPT_SYMBOLS (mpt), DECL_UID (sym));
264 /* MPT inherits the call-clobbering attributes from SYM. */
265 if (is_call_clobbered (sym))
267 MTAG_GLOBAL (mpt) = 1;
268 mark_call_clobbered (mpt, ESCAPE_IS_GLOBAL);
274 /* Mark variable VAR as being non-addressable. */
277 mark_non_addressable (tree var)
281 if (!TREE_ADDRESSABLE (var))
284 mpt = memory_partition (var);
287 var_ann (var)->call_clobbered = false;
289 bitmap_clear_bit (gimple_call_clobbered_vars (cfun), DECL_UID (var));
290 TREE_ADDRESSABLE (var) = 0;
294 /* Note that it's possible for a symbol to have an associated
295 MPT and the MPT have a NULL empty set. During
296 init_alias_info, all MPTs get their sets cleared out, but the
297 symbols still point to the old MPTs that used to hold them.
298 This is done so that compute_memory_partitions can now which
299 symbols are losing or changing partitions and mark them for
301 if (MPT_SYMBOLS (mpt))
302 bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var));
303 set_memory_partition (var, NULL_TREE);
308 /* qsort comparison function to sort type/name tags by DECL_UID. */
311 sort_tags_by_id (const void *pa, const void *pb)
313 const_tree const a = *(const_tree const *)pa;
314 const_tree const b = *(const_tree const *)pb;
316 return DECL_UID (a) - DECL_UID (b);
319 /* Initialize WORKLIST to contain those memory tags that are marked call
320 clobbered. Initialized WORKLIST2 to contain the reasons these
321 memory tags escaped. */
324 init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
325 VEC (int, heap) **worklist2)
327 referenced_var_iterator rvi;
330 FOR_EACH_REFERENCED_VAR (curr, rvi)
332 if (MTAG_P (curr) && is_call_clobbered (curr))
334 VEC_safe_push (tree, heap, *worklist, curr);
335 VEC_safe_push (int, heap, *worklist2, var_ann (curr)->escape_mask);
340 /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
341 ALIAS is not already marked call clobbered, and is a memory
345 add_to_worklist (tree alias, VEC (tree, heap) **worklist,
346 VEC (int, heap) **worklist2,
349 if (MTAG_P (alias) && !is_call_clobbered (alias))
351 VEC_safe_push (tree, heap, *worklist, alias);
352 VEC_safe_push (int, heap, *worklist2, reason);
356 /* Mark aliases of TAG as call clobbered, and place any tags on the
357 alias list that were not already call clobbered on WORKLIST. */
360 mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
361 VEC (int, heap) **worklist2)
367 var_ann_t ta = var_ann (tag);
371 aliases = may_aliases (tag);
375 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
377 entry = referenced_var (i);
378 if (!unmodifiable_var_p (entry))
380 add_to_worklist (entry, worklist, worklist2, ta->escape_mask);
381 mark_call_clobbered (entry, ta->escape_mask);
386 /* Tags containing global vars need to be marked as global.
387 Tags containing call clobbered vars need to be marked as call
391 compute_tag_properties (void)
393 referenced_var_iterator rvi;
396 VEC (tree, heap) *taglist = NULL;
398 FOR_EACH_REFERENCED_VAR (tag, rvi)
400 if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG)
402 VEC_safe_push (tree, heap, taglist, tag);
405 /* We sort the taglist by DECL_UID, for two reasons.
406 1. To get a sequential ordering to make the bitmap accesses
408 2. Because of the way we compute aliases, it's more likely that
409 an earlier tag is included in a later tag, and this will reduce
410 the number of iterations.
412 If we had a real tag graph, we would just topo-order it and be
414 qsort (VEC_address (tree, taglist),
415 VEC_length (tree, taglist),
419 /* Go through each tag not marked as global, and if it aliases
420 global vars, mark it global.
422 If the tag contains call clobbered vars, mark it call
425 This loop iterates because tags may appear in the may-aliases
426 list of other tags when we group. */
433 for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
439 bool tagcc = is_call_clobbered (tag);
440 bool tagglobal = MTAG_GLOBAL (tag);
442 if (tagcc && tagglobal)
445 ma = may_aliases (tag);
449 EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi)
451 entry = referenced_var (i);
452 /* Call clobbered entries cause the tag to be marked
454 if (!tagcc && is_call_clobbered (entry))
456 mark_call_clobbered (tag, var_ann (entry)->escape_mask);
461 /* Global vars cause the tag to be marked global. */
462 if (!tagglobal && is_global_var (entry))
464 MTAG_GLOBAL (tag) = true;
469 /* Early exit once both global and cc are set, since the
470 loop can't do any more than that. */
471 if (tagcc && tagglobal)
476 VEC_free (tree, heap, taglist);
479 /* Set up the initial variable clobbers and globalness.
480 When this function completes, only tags whose aliases need to be
481 clobbered will be set clobbered. Tags clobbered because they
482 contain call clobbered vars are handled in compute_tag_properties. */
485 set_initial_properties (struct alias_info *ai)
488 referenced_var_iterator rvi;
492 FOR_EACH_REFERENCED_VAR (var, rvi)
494 if (is_global_var (var)
495 && (!var_can_have_subvars (var)
496 || get_subvars_for_var (var) == NULL))
498 if (!unmodifiable_var_p (var))
499 mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
501 else if (TREE_CODE (var) == PARM_DECL
502 && gimple_default_def (cfun, var)
503 && POINTER_TYPE_P (TREE_TYPE (var)))
505 tree def = gimple_default_def (cfun, var);
506 get_ptr_info (def)->value_escapes_p = 1;
507 get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
511 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
513 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
514 tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
516 if (pi->value_escapes_p)
518 /* If PTR escapes then its associated memory tags and
519 pointed-to variables are call-clobbered. */
520 if (pi->name_mem_tag)
521 mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
524 mark_call_clobbered (tag, pi->escape_mask);
530 EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
531 if (!unmodifiable_var_p (referenced_var (j)))
532 mark_call_clobbered (referenced_var (j), pi->escape_mask);
536 /* If the name tag is call clobbered, so is the symbol tag
537 associated with the base VAR_DECL. */
540 && is_call_clobbered (pi->name_mem_tag))
541 mark_call_clobbered (tag, pi->escape_mask);
543 /* Name tags and symbol tags that we don't know where they point
544 to, might point to global memory, and thus, are clobbered.
546 FIXME: This is not quite right. They should only be
547 clobbered if value_escapes_p is true, regardless of whether
548 they point to global memory or not.
549 So removing this code and fixing all the bugs would be nice.
550 It is the cause of a bunch of clobbering. */
551 if ((pi->pt_global_mem || pi->pt_anything)
552 && pi->is_dereferenced && pi->name_mem_tag)
554 mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
555 MTAG_GLOBAL (pi->name_mem_tag) = true;
558 if ((pi->pt_global_mem || pi->pt_anything)
559 && pi->is_dereferenced
562 mark_call_clobbered (tag, ESCAPE_IS_GLOBAL);
563 MTAG_GLOBAL (tag) = true;
568 /* Compute which variables need to be marked call clobbered because
569 their tag is call clobbered, and which tags need to be marked
570 global because they contain global variables. */
573 compute_call_clobbered (struct alias_info *ai)
575 VEC (tree, heap) *worklist = NULL;
576 VEC(int,heap) *worklist2 = NULL;
578 timevar_push (TV_CALL_CLOBBER);
579 set_initial_properties (ai);
580 init_transitive_clobber_worklist (&worklist, &worklist2);
581 while (VEC_length (tree, worklist) != 0)
583 tree curr = VEC_pop (tree, worklist);
584 int reason = VEC_pop (int, worklist2);
586 mark_call_clobbered (curr, reason);
587 mark_aliases_call_clobbered (curr, &worklist, &worklist2);
589 VEC_free (tree, heap, worklist);
590 VEC_free (int, heap, worklist2);
591 compute_tag_properties ();
592 timevar_pop (TV_CALL_CLOBBER);
596 /* Dump memory partition information to FILE. */
599 dump_memory_partitions (FILE *file)
605 fprintf (file, "\nMemory partitions\n\n");
606 for (i = 0, npart = 0, nsyms = 0;
607 VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, i, mpt);
612 bitmap syms = MPT_SYMBOLS (mpt);
613 unsigned long n = (syms) ? bitmap_count_bits (syms) : 0;
615 fprintf (file, "#%u: ", i);
616 print_generic_expr (file, mpt, 0);
617 fprintf (file, ": %lu elements: ", n);
618 dump_decl_set (file, syms);
624 fprintf (file, "\n%u memory partitions holding %lu symbols\n", npart, nsyms);
628 /* Dump memory partition information to stderr. */
631 debug_memory_partitions (void)
633 dump_memory_partitions (stderr);
637 /* Return true if memory partitioning is required given the memory
638 reference estimates in STATS. */
641 need_to_partition_p (struct mem_ref_stats_d *stats)
643 long num_vops = stats->num_vuses + stats->num_vdefs;
644 long avg_vops = CEIL (num_vops, stats->num_mem_stmts);
645 return (num_vops > (long) MAX_ALIASED_VOPS
646 && avg_vops > (long) AVG_ALIASED_VOPS);
650 /* Count the actual number of virtual operators in CFUN. Note that
651 this is only meaningful after virtual operands have been populated,
652 so it should be invoked at the end of compute_may_aliases.
654 The number of virtual operators are stored in *NUM_VDEFS_P and
655 *NUM_VUSES_P, the number of partitioned symbols in
656 *NUM_PARTITIONED_P and the number of unpartitioned symbols in
657 *NUM_UNPARTITIONED_P.
659 If any of these pointers is NULL the corresponding count is not
663 count_mem_refs (long *num_vuses_p, long *num_vdefs_p,
664 long *num_partitioned_p, long *num_unpartitioned_p)
666 block_stmt_iterator bsi;
668 long num_vdefs, num_vuses, num_partitioned, num_unpartitioned;
669 referenced_var_iterator rvi;
672 num_vuses = num_vdefs = num_partitioned = num_unpartitioned = 0;
674 if (num_vuses_p || num_vdefs_p)
676 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
678 tree stmt = bsi_stmt (bsi);
679 if (stmt_references_memory_p (stmt))
681 num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
682 num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
686 if (num_partitioned_p || num_unpartitioned_p)
687 FOR_EACH_REFERENCED_VAR (sym, rvi)
689 if (is_gimple_reg (sym))
692 if (memory_partition (sym))
699 *num_vdefs_p = num_vdefs;
702 *num_vuses_p = num_vuses;
704 if (num_partitioned_p)
705 *num_partitioned_p = num_partitioned;
707 if (num_unpartitioned_p)
708 *num_unpartitioned_p = num_unpartitioned;
712 /* Dump memory reference stats for function CFUN to FILE. */
715 dump_mem_ref_stats (FILE *file)
717 long actual_num_vuses, actual_num_vdefs;
718 long num_partitioned, num_unpartitioned;
719 struct mem_ref_stats_d *stats;
721 stats = gimple_mem_ref_stats (cfun);
723 count_mem_refs (&actual_num_vuses, &actual_num_vdefs, &num_partitioned,
726 fprintf (file, "\nMemory reference statistics for %s\n\n",
727 lang_hooks.decl_printable_name (current_function_decl, 2));
729 fprintf (file, "Number of memory statements: %ld\n",
730 stats->num_mem_stmts);
731 fprintf (file, "Number of call sites: %ld\n",
732 stats->num_call_sites);
733 fprintf (file, "Number of pure/const call sites: %ld\n",
734 stats->num_pure_const_call_sites);
735 fprintf (file, "Number of asm sites: %ld\n",
736 stats->num_asm_sites);
737 fprintf (file, "Estimated number of loads: %ld (%ld/stmt)\n",
739 (stats->num_mem_stmts)
740 ? CEIL (stats->num_vuses, stats->num_mem_stmts)
742 fprintf (file, "Actual number of loads: %ld (%ld/stmt)\n",
744 (stats->num_mem_stmts)
745 ? CEIL (actual_num_vuses, stats->num_mem_stmts)
748 if (actual_num_vuses > stats->num_vuses + (stats->num_vuses / 25))
749 fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
751 fprintf (file, "Estimated number of stores: %ld (%ld/stmt)\n",
753 (stats->num_mem_stmts)
754 ? CEIL (stats->num_vdefs, stats->num_mem_stmts)
756 fprintf (file, "Actual number of stores: %ld (%ld/stmt)\n",
758 (stats->num_mem_stmts)
759 ? CEIL (actual_num_vdefs, stats->num_mem_stmts)
762 if (actual_num_vdefs > stats->num_vdefs + (stats->num_vdefs / 25))
763 fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
765 fprintf (file, "Partitioning thresholds: MAX = %d AVG = %d "
766 "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS, AVG_ALIASED_VOPS,
767 stats->num_mem_stmts && need_to_partition_p (stats) ? "" : "NO ");
768 fprintf (file, "Number of partitioned symbols: %ld\n", num_partitioned);
769 fprintf (file, "Number of unpartitioned symbols: %ld\n", num_unpartitioned);
773 /* Dump memory reference stats for function FN to stderr. */
776 debug_mem_ref_stats (void)
778 dump_mem_ref_stats (stderr);
782 /* Dump memory reference stats for variable VAR to FILE. */
785 dump_mem_sym_stats (FILE *file, tree var)
787 mem_sym_stats_t stats = mem_sym_stats (cfun, var);
792 fprintf (file, "read frequency: %6ld, write frequency: %6ld, "
793 "direct reads: %3ld, direct writes: %3ld, "
794 "indirect reads: %4ld, indirect writes: %4ld, symbol: ",
795 stats->frequency_reads, stats->frequency_writes,
796 stats->num_direct_reads, stats->num_direct_writes,
797 stats->num_indirect_reads, stats->num_indirect_writes);
798 print_generic_expr (file, stats->var, 0);
799 fprintf (file, ", tags: ");
800 dump_decl_set (file, stats->parent_tags);
804 /* Dump memory reference stats for variable VAR to stderr. */
807 debug_mem_sym_stats (tree var)
809 dump_mem_sym_stats (stderr, var);
813 /* Dump memory reference stats for all memory symbols to FILE. */
816 dump_all_mem_sym_stats (FILE *file)
818 referenced_var_iterator rvi;
821 FOR_EACH_REFERENCED_VAR (sym, rvi)
823 if (is_gimple_reg (sym))
826 dump_mem_sym_stats (file, sym);
831 /* Dump memory reference stats for all memory symbols to stderr. */
834 debug_all_mem_sym_stats (void)
836 dump_all_mem_sym_stats (stderr);
840 /* Dump the MP_INFO array to FILE. */
843 dump_mp_info (FILE *file, VEC(mem_sym_stats_t,heap) *mp_info)
846 mem_sym_stats_t mp_p;
848 for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
849 if (!mp_p->partitioned_p)
850 dump_mem_sym_stats (file, mp_p->var);
854 /* Dump the MP_INFO array to stderr. */
857 debug_mp_info (VEC(mem_sym_stats_t,heap) *mp_info)
859 dump_mp_info (stderr, mp_info);
863 /* Update memory reference stats for symbol VAR in statement STMT.
864 NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times
865 that VAR is read/written in STMT (indirect reads/writes are not
866 recorded by this function, see compute_memory_partitions). */
869 update_mem_sym_stats_from_stmt (tree var, tree stmt, long num_direct_reads,
870 long num_direct_writes)
872 mem_sym_stats_t stats;
874 gcc_assert (num_direct_reads >= 0 && num_direct_writes >= 0);
876 stats = get_mem_sym_stats_for (var);
878 stats->num_direct_reads += num_direct_reads;
879 stats->frequency_reads += ((long) bb_for_stmt (stmt)->frequency
882 stats->num_direct_writes += num_direct_writes;
883 stats->frequency_writes += ((long) bb_for_stmt (stmt)->frequency
884 * num_direct_writes);
888 /* The list is sorted by increasing partitioning score (PSCORE).
889 This score is computed such that symbols with high scores are
890 those that are least likely to be partitioned. Given a symbol
891 MP->VAR, PSCORE(S) is the result of the following weighted sum
893 PSCORE(S) = FW * 64 + FR * 32
900 FW Execution frequency of writes to S
901 FR Execution frequency of reads from S
902 DW Number of direct writes to S
903 DR Number of direct reads from S
904 IW Number of indirect writes to S
905 IR Number of indirect reads from S
906 NO_ALIAS State of the NO_ALIAS* flags
908 The basic idea here is that symbols that are frequently
909 written-to in hot paths of the code are the last to be considered
913 pscore (mem_sym_stats_t mp)
915 return mp->frequency_writes * 64 + mp->frequency_reads * 32
916 + mp->num_direct_writes * 16 + mp->num_direct_reads * 8
917 + mp->num_indirect_writes * 4 + mp->num_indirect_reads * 2
918 + var_ann (mp->var)->noalias_state;
922 /* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should
923 be partitioned before MP2->VAR, 0 if they are the same or 1 if
924 MP1->VAR should be partitioned after MP2->VAR. */
927 compare_mp_info_entries (mem_sym_stats_t mp1, mem_sym_stats_t mp2)
929 long pscore1 = pscore (mp1);
930 long pscore2 = pscore (mp2);
932 if (pscore1 < pscore2)
934 else if (pscore1 > pscore2)
941 /* Comparison routine for qsort. The list is sorted by increasing
942 partitioning score (PSCORE). This score is computed such that
943 symbols with high scores are those that are least likely to be
947 mp_info_cmp (const void *p, const void *q)
949 mem_sym_stats_t e1 = *((const mem_sym_stats_t *) p);
950 mem_sym_stats_t e2 = *((const mem_sym_stats_t *) q);
951 return compare_mp_info_entries (e1, e2);
955 /* Sort the array of reference counts used to compute memory partitions.
956 Elements are sorted in ascending order of execution frequency and
957 descending order of virtual operators needed. */
960 sort_mp_info (VEC(mem_sym_stats_t,heap) *list)
962 unsigned num = VEC_length (mem_sym_stats_t, list);
969 if (compare_mp_info_entries (VEC_index (mem_sym_stats_t, list, 0),
970 VEC_index (mem_sym_stats_t, list, 1)) > 0)
972 /* Swap elements if they are in the wrong order. */
973 mem_sym_stats_t tmp = VEC_index (mem_sym_stats_t, list, 0);
974 VEC_replace (mem_sym_stats_t, list, 0,
975 VEC_index (mem_sym_stats_t, list, 1));
976 VEC_replace (mem_sym_stats_t, list, 1, tmp);
982 /* There are 3 or more elements, call qsort. */
983 qsort (VEC_address (mem_sym_stats_t, list),
984 VEC_length (mem_sym_stats_t, list),
985 sizeof (mem_sym_stats_t),
990 /* Return the memory partition tag (MPT) associated with memory
994 get_mpt_for (tree sym)
998 /* Don't create a new tag unnecessarily. */
999 mpt = memory_partition (sym);
1000 if (mpt == NULL_TREE)
1002 mpt = create_tag_raw (MEMORY_PARTITION_TAG, TREE_TYPE (sym), "MPT");
1003 TREE_ADDRESSABLE (mpt) = 0;
1004 add_referenced_var (mpt);
1005 VEC_safe_push (tree, heap, gimple_ssa_operands (cfun)->mpt_table, mpt);
1006 gcc_assert (MPT_SYMBOLS (mpt) == NULL);
1007 set_memory_partition (sym, mpt);
1014 /* Add MP_P->VAR to a memory partition and return the partition. */
1017 find_partition_for (mem_sym_stats_t mp_p)
1020 VEC(tree,heap) *mpt_table;
1023 mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1026 /* Find an existing partition for MP_P->VAR. */
1027 for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
1029 mem_sym_stats_t mpt_stats;
1031 /* If MPT does not have any symbols yet, use it. */
1032 if (MPT_SYMBOLS (mpt) == NULL)
1035 /* Otherwise, see if MPT has common parent tags with MP_P->VAR,
1036 but avoid grouping clobbered variables with non-clobbered
1037 variables (otherwise, this tends to creates a single memory
1038 partition because other call-clobbered variables may have
1039 common parent tags with non-clobbered ones). */
1040 mpt_stats = get_mem_sym_stats_for (mpt);
1041 if (mp_p->parent_tags
1042 && mpt_stats->parent_tags
1043 && is_call_clobbered (mpt) == is_call_clobbered (mp_p->var)
1044 && bitmap_intersect_p (mpt_stats->parent_tags, mp_p->parent_tags))
1047 /* If no common parent tags are found, see if both MPT and
1048 MP_P->VAR are call-clobbered. */
1049 if (is_call_clobbered (mpt) && is_call_clobbered (mp_p->var))
1053 if (mpt == NULL_TREE)
1054 mpt = get_mpt_for (mp_p->var);
1056 set_memory_partition (mp_p->var, mpt);
1058 mp_p->partitioned_p = true;
1060 mark_sym_for_renaming (mp_p->var);
1061 mark_sym_for_renaming (mpt);
1067 /* Rewrite the alias set for TAG to use the newly created partitions.
1068 If TAG is NULL, rewrite the set of call-clobbered variables.
1069 NEW_ALIASES is a scratch bitmap to build the new set of aliases for
1073 rewrite_alias_set_for (tree tag, bitmap new_aliases)
1079 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
1081 sym = referenced_var (i);
1082 mpt = memory_partition (sym);
1084 bitmap_set_bit (new_aliases, DECL_UID (mpt));
1086 bitmap_set_bit (new_aliases, DECL_UID (sym));
1089 /* Rebuild the may-alias array for TAG. */
1090 bitmap_copy (MTAG_ALIASES (tag), new_aliases);
1094 /* Determine how many virtual operands can be saved by partitioning
1095 MP_P->VAR into MPT. When a symbol S is thrown inside a partition
1096 P, every virtual operand that used to reference S will now
1097 reference P. Whether it reduces the number of virtual operands
1100 1- Direct references to S are never saved. Instead of the virtual
1101 operand to S, we will now have a virtual operand to P.
1103 2- Indirect references to S are reduced only for those memory tags
1104 holding S that already had other symbols partitioned into P.
1105 For instance, if a memory tag T has the alias set { a b S c },
1106 the first time we partition S into P, the alias set will become
1107 { a b P c }, so no virtual operands will be saved. However, if
1108 we now partition symbol 'c' into P, then the alias set for T
1109 will become { a b P }, so we will be saving one virtual operand
1110 for every indirect reference to 'c'.
1112 3- Is S is call-clobbered, we save as many virtual operands as
1113 call/asm sites exist in the code, but only if other
1114 call-clobbered symbols have been grouped into P. The first
1115 call-clobbered symbol that we group does not produce any
1118 MEM_REF_STATS points to CFUN's memory reference information. */
1121 estimate_vop_reduction (struct mem_ref_stats_d *mem_ref_stats,
1122 mem_sym_stats_t mp_p, tree mpt)
1126 mem_sym_stats_t mpt_stats;
1128 /* We should only get symbols with indirect references here. */
1129 gcc_assert (mp_p->num_indirect_reads > 0 || mp_p->num_indirect_writes > 0);
1131 /* Note that the only statistics we keep for MPT is the set of
1132 parent tags to know which memory tags have had alias members
1133 partitioned, and the indicator has_call_clobbered_vars.
1134 Reference counts are not important for MPT. */
1135 mpt_stats = get_mem_sym_stats_for (mpt);
1137 /* Traverse all the parent tags for MP_P->VAR. For every tag T, if
1138 partition P is already grouping aliases of T, then reduce the
1139 number of virtual operands by the number of direct references
1141 if (mp_p->parent_tags)
1143 if (mpt_stats->parent_tags == NULL)
1144 mpt_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1146 EXECUTE_IF_SET_IN_BITMAP (mp_p->parent_tags, 0, i, bi)
1148 if (bitmap_bit_p (mpt_stats->parent_tags, i))
1150 /* Partition MPT is already partitioning symbols in the
1151 alias set for TAG. This means that we are now saving
1152 1 virtual operand for every direct reference to TAG. */
1153 tree tag = referenced_var (i);
1154 mem_sym_stats_t tag_stats = mem_sym_stats (cfun, tag);
1155 mem_ref_stats->num_vuses -= tag_stats->num_direct_reads;
1156 mem_ref_stats->num_vdefs -= tag_stats->num_direct_writes;
1160 /* This is the first symbol in tag I's alias set that is
1161 being grouped under MPT. We will not save any
1162 virtual operands this time, but record that MPT is
1163 grouping a symbol from TAG's alias set so that the
1164 next time we get the savings. */
1165 bitmap_set_bit (mpt_stats->parent_tags, i);
1170 /* If MP_P->VAR is call-clobbered, and MPT is already grouping
1171 call-clobbered symbols, then we will save as many virtual
1172 operands as asm/call sites there are. */
1173 if (is_call_clobbered (mp_p->var))
1175 if (mpt_stats->has_call_clobbered_vars)
1176 mem_ref_stats->num_vdefs -= mem_ref_stats->num_call_sites
1177 + mem_ref_stats->num_asm_sites;
1179 mpt_stats->has_call_clobbered_vars = true;
1184 /* Helper for compute_memory_partitions. Transfer reference counts
1185 from pointers to their pointed-to sets. Counters for pointers were
1186 computed by update_alias_info. MEM_REF_STATS points to CFUN's
1187 memory reference information. */
1190 update_reference_counts (struct mem_ref_stats_d *mem_ref_stats)
1194 mem_sym_stats_t sym_stats;
1196 for (i = 1; i < num_ssa_names; i++)
1199 struct ptr_info_def *pi;
1203 && POINTER_TYPE_P (TREE_TYPE (ptr))
1204 && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1205 && pi->is_dereferenced)
1210 mem_sym_stats_t ptr_stats, tag_stats;
1212 /* If PTR has flow-sensitive points-to information, use
1213 PTR's name tag, otherwise use the symbol tag associated
1214 with PTR's symbol. */
1215 if (pi->name_mem_tag)
1216 tag = pi->name_mem_tag;
1218 tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
1220 ptr_stats = get_mem_sym_stats_for (ptr);
1221 tag_stats = get_mem_sym_stats_for (tag);
1223 /* TAG has as many direct references as dereferences we
1224 found for its parent pointer. */
1225 tag_stats->num_direct_reads += ptr_stats->num_direct_reads;
1226 tag_stats->num_direct_writes += ptr_stats->num_direct_writes;
1228 /* All the dereferences of pointer PTR are considered direct
1229 references to PTR's memory tag (TAG). In turn,
1230 references to TAG will become virtual operands for every
1231 symbol in TAG's alias set. So, for every symbol ALIAS in
1232 TAG's alias set, add as many indirect references to ALIAS
1233 as direct references there are for TAG. */
1234 if (MTAG_ALIASES (tag))
1235 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, j, bj)
1237 tree alias = referenced_var (j);
1238 sym_stats = get_mem_sym_stats_for (alias);
1240 /* All the direct references to TAG are indirect references
1242 sym_stats->num_indirect_reads += ptr_stats->num_direct_reads;
1243 sym_stats->num_indirect_writes += ptr_stats->num_direct_writes;
1244 sym_stats->frequency_reads += ptr_stats->frequency_reads;
1245 sym_stats->frequency_writes += ptr_stats->frequency_writes;
1247 /* Indicate that TAG is one of ALIAS's parent tags. */
1248 if (sym_stats->parent_tags == NULL)
1249 sym_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1250 bitmap_set_bit (sym_stats->parent_tags, DECL_UID (tag));
1255 /* Call-clobbered symbols are indirectly written at every
1257 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
1259 tree sym = referenced_var (i);
1260 sym_stats = get_mem_sym_stats_for (sym);
1261 sym_stats->num_indirect_writes += mem_ref_stats->num_call_sites
1262 + mem_ref_stats->num_asm_sites;
1265 /* Addressable symbols are indirectly written at some ASM sites.
1266 Since only ASM sites that clobber memory actually affect
1267 addressable symbols, this is an over-estimation. */
1268 EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
1270 tree sym = referenced_var (i);
1271 sym_stats = get_mem_sym_stats_for (sym);
1272 sym_stats->num_indirect_writes += mem_ref_stats->num_asm_sites;
1277 /* Helper for compute_memory_partitions. Add all memory symbols to
1278 *MP_INFO_P and compute the initial estimate for the total number of
1279 virtual operands needed. MEM_REF_STATS points to CFUN's memory
1280 reference information. On exit, *TAGS_P will contain the list of
1281 memory tags whose alias set need to be rewritten after
1285 build_mp_info (struct mem_ref_stats_d *mem_ref_stats,
1286 VEC(mem_sym_stats_t,heap) **mp_info_p,
1287 VEC(tree,heap) **tags_p)
1290 referenced_var_iterator rvi;
1292 FOR_EACH_REFERENCED_VAR (var, rvi)
1294 mem_sym_stats_t sym_stats;
1297 /* We are only interested in memory symbols other than MPTs. */
1298 if (is_gimple_reg (var) || TREE_CODE (var) == MEMORY_PARTITION_TAG)
1301 /* Collect memory tags into the TAGS array so that we can
1302 rewrite their alias sets after partitioning. */
1303 if (MTAG_P (var) && MTAG_ALIASES (var))
1304 VEC_safe_push (tree, heap, *tags_p, var);
1306 /* Since we are going to re-compute partitions, any symbols that
1307 used to belong to a partition must be detached from it and
1308 marked for renaming. */
1309 if ((old_mpt = memory_partition (var)) != NULL)
1311 mark_sym_for_renaming (old_mpt);
1312 set_memory_partition (var, NULL_TREE);
1313 mark_sym_for_renaming (var);
1316 sym_stats = get_mem_sym_stats_for (var);
1318 /* Add VAR's reference info to MP_INFO. Note that the only
1319 symbols that make sense to partition are those that have
1320 indirect references. If a symbol S is always directly
1321 referenced, partitioning it will not reduce the number of
1322 virtual operators. The only symbols that are profitable to
1323 partition are those that belong to alias sets and/or are
1325 if (sym_stats->num_indirect_reads > 0
1326 || sym_stats->num_indirect_writes > 0)
1327 VEC_safe_push (mem_sym_stats_t, heap, *mp_info_p, sym_stats);
1329 /* Update the number of estimated VOPS. Note that direct
1330 references to memory tags are always counted as indirect
1331 references to their alias set members, so if a memory tag has
1332 aliases, do not count its direct references to avoid double
1334 if (!MTAG_P (var) || !MTAG_ALIASES (var))
1336 mem_ref_stats->num_vuses += sym_stats->num_direct_reads;
1337 mem_ref_stats->num_vdefs += sym_stats->num_direct_writes;
1340 mem_ref_stats->num_vuses += sym_stats->num_indirect_reads;
1341 mem_ref_stats->num_vdefs += sym_stats->num_indirect_writes;
1346 /* Compute memory partitions. A memory partition (MPT) is an
1347 arbitrary grouping of memory symbols, such that references to one
1348 member of the group is considered a reference to all the members of
1351 As opposed to alias sets in memory tags, the grouping into
1352 partitions is completely arbitrary and only done to reduce the
1353 number of virtual operands. The only rule that needs to be
1354 observed when creating memory partitions is that given two memory
1355 partitions MPT.i and MPT.j, they must not contain symbols in
1358 Memory partitions are used when putting the program into Memory-SSA
1359 form. In particular, in Memory-SSA PHI nodes are not computed for
1360 individual memory symbols. They are computed for memory
1361 partitions. This reduces the amount of PHI nodes in the SSA graph
1362 at the expense of precision (i.e., it makes unrelated stores affect
1365 However, it is possible to increase precision by changing this
1366 partitioning scheme. For instance, if the partitioning scheme is
1367 such that get_mpt_for is the identity function (that is,
1368 get_mpt_for (s) = s), this will result in ultimate precision at the
1369 expense of huge SSA webs.
1371 At the other extreme, a partitioning scheme that groups all the
1372 symbols in the same set results in minimal SSA webs and almost
1373 total loss of precision.
1375 There partitioning heuristic uses three parameters to decide the
1376 order in which symbols are processed. The list of symbols is
1377 sorted so that symbols that are more likely to be partitioned are
1378 near the top of the list:
1380 - Execution frequency. If a memory references is in a frequently
1381 executed code path, grouping it into a partition may block useful
1382 transformations and cause sub-optimal code generation. So, the
1383 partition heuristic tries to avoid grouping symbols with high
1384 execution frequency scores. Execution frequency is taken
1385 directly from the basic blocks where every reference is made (see
1386 update_mem_sym_stats_from_stmt), which in turn uses the
1387 profile guided machinery, so if the program is compiled with PGO
1388 enabled, more accurate partitioning decisions will be made.
1390 - Number of references. Symbols with few references in the code,
1391 are partitioned before symbols with many references.
1393 - NO_ALIAS attributes. Symbols with any of the NO_ALIAS*
1394 attributes are partitioned after symbols marked MAY_ALIAS.
1396 Once the list is sorted, the partitioning proceeds as follows:
1398 1- For every symbol S in MP_INFO, create a new memory partition MP,
1399 if necessary. To avoid memory partitions that contain symbols
1400 from non-conflicting alias sets, memory partitions are
1401 associated to the memory tag that holds S in its alias set. So,
1402 when looking for a memory partition for S, the memory partition
1403 associated with one of the memory tags holding S is chosen. If
1404 none exists, a new one is created.
1406 2- Add S to memory partition MP.
1408 3- Reduce by 1 the number of VOPS for every memory tag holding S.
1410 4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the
1411 average number of VOPS per statement is less than
1412 AVG_ALIASED_VOPS, stop. Otherwise, go to the next symbol in the
1416 compute_memory_partitions (void)
1420 mem_sym_stats_t mp_p;
1421 VEC(mem_sym_stats_t,heap) *mp_info;
1423 VEC(tree,heap) *tags;
1424 struct mem_ref_stats_d *mem_ref_stats;
1425 int prev_max_aliased_vops;
1427 mem_ref_stats = gimple_mem_ref_stats (cfun);
1428 gcc_assert (mem_ref_stats->num_vuses == 0 && mem_ref_stats->num_vdefs == 0);
1430 if (mem_ref_stats->num_mem_stmts == 0)
1433 timevar_push (TV_MEMORY_PARTITIONING);
1437 prev_max_aliased_vops = MAX_ALIASED_VOPS;
1439 /* Since we clearly cannot lower the number of virtual operators
1440 below the total number of memory statements in the function, we
1441 may need to adjust MAX_ALIASED_VOPS beforehand. */
1442 if (MAX_ALIASED_VOPS < mem_ref_stats->num_mem_stmts)
1443 MAX_ALIASED_VOPS = mem_ref_stats->num_mem_stmts;
1445 /* Update reference stats for all the pointed-to variables and
1447 update_reference_counts (mem_ref_stats);
1449 /* Add all the memory symbols to MP_INFO. */
1450 build_mp_info (mem_ref_stats, &mp_info, &tags);
1452 /* No partitions required if we are below the threshold. */
1453 if (!need_to_partition_p (mem_ref_stats))
1456 fprintf (dump_file, "\nMemory partitioning NOT NEEDED for %s\n",
1457 get_name (current_function_decl));
1461 /* Sort the MP_INFO array so that symbols that should be partitioned
1462 first are near the top of the list. */
1463 sort_mp_info (mp_info);
1467 fprintf (dump_file, "\nMemory partitioning NEEDED for %s\n\n",
1468 get_name (current_function_decl));
1469 fprintf (dump_file, "Memory symbol references before partitioning:\n");
1470 dump_mp_info (dump_file, mp_info);
1473 /* Create partitions for variables in MP_INFO until we have enough
1474 to lower the total number of VOPS below MAX_ALIASED_VOPS or if
1475 the average number of VOPS per statement is below
1476 AVG_ALIASED_VOPS. */
1477 for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
1481 /* If we are below the threshold, stop. */
1482 if (!need_to_partition_p (mem_ref_stats))
1485 mpt = find_partition_for (mp_p);
1486 estimate_vop_reduction (mem_ref_stats, mp_p, mpt);
1489 /* After partitions have been created, rewrite alias sets to use
1490 them instead of the original symbols. This way, if the alias set
1491 was computed as { a b c d e f }, and the subset { b e f } was
1492 grouped into partition MPT.3, then the new alias set for the tag
1493 will be { a c d MPT.3 }.
1495 Note that this is not strictly necessary. The operand scanner
1496 will always check if a symbol belongs to a partition when adding
1497 virtual operands. However, by reducing the size of the alias
1498 sets to be scanned, the work needed inside the operand scanner is
1499 significantly reduced. */
1500 new_aliases = BITMAP_ALLOC (NULL);
1502 for (i = 0; VEC_iterate (tree, tags, i, tag); i++)
1504 rewrite_alias_set_for (tag, new_aliases);
1505 bitmap_clear (new_aliases);
1508 BITMAP_FREE (new_aliases);
1512 fprintf (dump_file, "\nMemory symbol references after partitioning:\n");
1513 dump_mp_info (dump_file, mp_info);
1517 /* Free allocated memory. */
1518 VEC_free (mem_sym_stats_t, heap, mp_info);
1519 VEC_free (tree, heap, tags);
1521 MAX_ALIASED_VOPS = prev_max_aliased_vops;
1523 timevar_pop (TV_MEMORY_PARTITIONING);
1527 /* Compute may-alias information for every variable referenced in function
1530 Alias analysis proceeds in 3 main phases:
1532 1- Points-to and escape analysis.
1534 This phase walks the use-def chains in the SSA web looking for three
1537 * Assignments of the form P_i = &VAR
1538 * Assignments of the form P_i = malloc()
1539 * Pointers and ADDR_EXPR that escape the current function.
1541 The concept of 'escaping' is the same one used in the Java world. When
1542 a pointer or an ADDR_EXPR escapes, it means that it has been exposed
1543 outside of the current function. So, assignment to global variables,
1544 function arguments and returning a pointer are all escape sites, as are
1545 conversions between pointers and integers.
1547 This is where we are currently limited. Since not everything is renamed
1548 into SSA, we lose track of escape properties when a pointer is stashed
1549 inside a field in a structure, for instance. In those cases, we are
1550 assuming that the pointer does escape.
1552 We use escape analysis to determine whether a variable is
1553 call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable
1554 is call-clobbered. If a pointer P_i escapes, then all the variables
1555 pointed-to by P_i (and its memory tag) also escape.
1557 2- Compute flow-sensitive aliases
1559 We have two classes of memory tags. Memory tags associated with the
1560 pointed-to data type of the pointers in the program. These tags are
1561 called "symbol memory tag" (SMT). The other class are those associated
1562 with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
1563 when adding operands for an INDIRECT_REF *P_i, we will first check
1564 whether P_i has a name tag, if it does we use it, because that will have
1565 more precise aliasing information. Otherwise, we use the standard symbol
1568 In this phase, we go through all the pointers we found in points-to
1569 analysis and create alias sets for the name memory tags associated with
1570 each pointer P_i. If P_i escapes, we mark call-clobbered the variables
1571 it points to and its tag.
1574 3- Compute flow-insensitive aliases
1576 This pass will compare the alias set of every symbol memory tag and
1577 every addressable variable found in the program. Given a symbol
1578 memory tag SMT and an addressable variable V. If the alias sets of
1579 SMT and V conflict (as computed by may_alias_p), then V is marked
1580 as an alias tag and added to the alias set of SMT.
1582 For instance, consider the following function:
1598 After aliasing analysis has finished, the symbol memory tag for pointer
1599 'p' will have two aliases, namely variables 'a' and 'b'. Every time
1600 pointer 'p' is dereferenced, we want to mark the operation as a
1601 potential reference to 'a' and 'b'.
1611 # p_1 = PHI <p_4(1), p_6(2)>;
1626 In certain cases, the list of may aliases for a pointer may grow too
1627 large. This may cause an explosion in the number of virtual operands
1628 inserted in the code. Resulting in increased memory consumption and
1631 When the number of virtual operands needed to represent aliased
1632 loads and stores grows too large (configurable with option --param
1633 max-aliased-vops and --param avg-aliased-vops), alias sets are
1634 grouped to avoid severe compile-time slow downs and memory
1635 consumption. See compute_memory_partitions. */
1638 compute_may_aliases (void)
1640 struct alias_info *ai;
1642 timevar_push (TV_TREE_MAY_ALIAS);
1644 memset (&alias_stats, 0, sizeof (alias_stats));
1646 /* Initialize aliasing information. */
1647 ai = init_alias_info ();
1649 /* For each pointer P_i, determine the sets of variables that P_i may
1650 point-to. For every addressable variable V, determine whether the
1651 address of V escapes the current function, making V call-clobbered
1652 (i.e., whether &V is stored in a global variable or if its passed as a
1653 function call argument). */
1654 compute_points_to_sets (ai);
1656 /* Collect all pointers and addressable variables, compute alias sets,
1657 create memory tags for pointers and promote variables whose address is
1658 not needed anymore. */
1659 setup_pointers_and_addressables (ai);
1661 /* Compute type-based flow-insensitive aliasing for all the type
1663 compute_flow_insensitive_aliasing (ai);
1665 /* Compute flow-sensitive, points-to based aliasing for all the name
1667 compute_flow_sensitive_aliasing (ai);
1669 /* Compute call clobbering information. */
1670 compute_call_clobbered (ai);
1672 /* If the program makes no reference to global variables, but it
1673 contains a mixture of pure and non-pure functions, then we need
1674 to create use-def and def-def links between these functions to
1675 avoid invalid transformations on them. */
1676 maybe_create_global_var ();
1678 /* If the program contains ref-all pointers, finalize may-alias information
1679 for them. This pass needs to be run after call-clobbering information
1680 has been computed. */
1681 if (ai->ref_all_symbol_mem_tag)
1682 finalize_ref_all_pointers (ai);
1684 /* Compute memory partitions for every memory variable. */
1685 compute_memory_partitions ();
1687 /* Remove partitions with no symbols. Partitions may end up with an
1688 empty MPT_SYMBOLS set if a previous round of alias analysis
1689 needed to partition more symbols. Since we don't need those
1690 partitions anymore, remove them to free up the space. */
1694 VEC(tree,heap) *mpt_table;
1696 mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1698 while (i < VEC_length (tree, mpt_table))
1700 mpt = VEC_index (tree, mpt_table, i);
1701 if (MPT_SYMBOLS (mpt) == NULL)
1702 VEC_unordered_remove (tree, mpt_table, i);
1708 /* Populate all virtual operands and newly promoted register operands. */
1710 block_stmt_iterator bsi;
1713 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1714 update_stmt_if_modified (bsi_stmt (bsi));
1717 /* Debugging dumps. */
1720 dump_mem_ref_stats (dump_file);
1721 dump_alias_info (dump_file);
1722 dump_points_to_info (dump_file);
1724 if (dump_flags & TDF_STATS)
1725 dump_alias_stats (dump_file);
1727 if (dump_flags & TDF_DETAILS)
1728 dump_referenced_vars (dump_file);
1731 /* Report strict aliasing violations. */
1732 strict_aliasing_warning_backend ();
1734 /* Deallocate memory used by aliasing data structures. */
1735 delete_alias_info (ai);
1737 if (need_ssa_update_p ())
1738 update_ssa (TODO_update_ssa);
1740 timevar_pop (TV_TREE_MAY_ALIAS);
1745 /* Data structure used to count the number of dereferences to PTR
1746 inside an expression. */
1754 /* Helper for count_uses_and_derefs. Called by walk_tree to look for
1755 (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
1758 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
1760 struct count_ptr_d *count_p = (struct count_ptr_d *) data;
1762 /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld,
1763 pointer 'ptr' is *not* dereferenced, it is simply used to compute
1764 the address of 'fld' as 'ptr + offsetof(fld)'. */
1765 if (TREE_CODE (*tp) == ADDR_EXPR)
1771 if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
1778 /* Count the number of direct and indirect uses for pointer PTR in
1779 statement STMT. The number of direct uses is stored in
1780 *NUM_USES_P. Indirect references are counted separately depending
1781 on whether they are store or load operations. The counts are
1782 stored in *NUM_STORES_P and *NUM_LOADS_P. */
1785 count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
1786 unsigned *num_loads_p, unsigned *num_stores_p)
1795 /* Find out the total number of uses of PTR in STMT. */
1796 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1800 /* Now count the number of indirect references to PTR. This is
1801 truly awful, but we don't have much choice. There are no parent
1802 pointers inside INDIRECT_REFs, so an expression like
1803 '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
1804 find all the indirect and direct uses of x_1 inside. The only
1805 shortcut we can take is the fact that GIMPLE only allows
1806 INDIRECT_REFs inside the expressions below. */
1807 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1808 || (TREE_CODE (stmt) == RETURN_EXPR
1809 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1810 || TREE_CODE (stmt) == ASM_EXPR
1811 || TREE_CODE (stmt) == CALL_EXPR)
1815 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1817 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1818 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1820 else if (TREE_CODE (stmt) == RETURN_EXPR)
1822 tree e = TREE_OPERAND (stmt, 0);
1823 lhs = GIMPLE_STMT_OPERAND (e, 0);
1824 rhs = GIMPLE_STMT_OPERAND (e, 1);
1826 else if (TREE_CODE (stmt) == ASM_EXPR)
1828 lhs = ASM_OUTPUTS (stmt);
1829 rhs = ASM_INPUTS (stmt);
1838 && (TREE_CODE (lhs) == TREE_LIST
1840 || GIMPLE_STMT_P (lhs)))
1842 struct count_ptr_d count;
1845 walk_tree (&lhs, count_ptr_derefs, &count, NULL);
1846 *num_stores_p = count.count;
1850 && (TREE_CODE (rhs) == TREE_LIST
1852 || GIMPLE_STMT_P (rhs)))
1854 struct count_ptr_d count;
1857 walk_tree (&rhs, count_ptr_derefs, &count, NULL);
1858 *num_loads_p = count.count;
1862 gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
1865 /* Remove memory references stats for function FN. */
1868 delete_mem_ref_stats (struct function *fn)
1870 if (gimple_mem_ref_stats (fn)->mem_sym_stats)
1872 free_alloc_pool (mem_sym_stats_pool);
1873 pointer_map_destroy (gimple_mem_ref_stats (fn)->mem_sym_stats);
1875 gimple_mem_ref_stats (fn)->mem_sym_stats = NULL;
1879 /* Initialize memory reference stats. */
1882 init_mem_ref_stats (void)
1884 struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
1886 mem_sym_stats_pool = create_alloc_pool ("Mem sym stats",
1887 sizeof (struct mem_sym_stats_d),
1889 memset (mem_ref_stats, 0, sizeof (struct mem_ref_stats_d));
1890 mem_ref_stats->mem_sym_stats = pointer_map_create ();
1894 /* Initialize the data structures used for alias analysis. */
1896 static struct alias_info *
1897 init_alias_info (void)
1899 struct alias_info *ai;
1900 referenced_var_iterator rvi;
1903 ai = XCNEW (struct alias_info);
1904 ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
1905 sbitmap_zero (ai->ssa_names_visited);
1906 ai->processed_ptrs = VEC_alloc (tree, heap, 50);
1907 ai->written_vars = pointer_set_create ();
1908 ai->dereferenced_ptrs_store = pointer_set_create ();
1909 ai->dereferenced_ptrs_load = pointer_set_create ();
1911 /* Clear out all memory reference stats. */
1912 init_mem_ref_stats ();
1914 /* If aliases have been computed before, clear existing information. */
1915 if (gimple_aliases_computed_p (cfun))
1919 /* Similarly, clear the set of addressable variables. In this
1920 case, we can just clear the set because addressability is
1921 only computed here. */
1922 bitmap_clear (gimple_addressable_vars (cfun));
1924 /* Clear flow-insensitive alias information from each symbol. */
1925 FOR_EACH_REFERENCED_VAR (var, rvi)
1927 if (is_gimple_reg (var))
1931 MTAG_ALIASES (var) = NULL;
1933 /* Memory partition information will be computed from scratch. */
1934 if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
1935 MPT_SYMBOLS (var) = NULL;
1937 /* Since we are about to re-discover call-clobbered
1938 variables, clear the call-clobbered flag. Variables that
1939 are intrinsically call-clobbered (globals, local statics,
1940 etc) will not be marked by the aliasing code, so we can't
1941 remove them from CALL_CLOBBERED_VARS.
1943 NB: STRUCT_FIELDS are still call clobbered if they are
1944 for a global variable, so we *don't* clear their call
1945 clobberedness just because they are tags, though we will
1946 clear it if they aren't for global variables. */
1947 if (TREE_CODE (var) == NAME_MEMORY_TAG
1948 || TREE_CODE (var) == SYMBOL_MEMORY_TAG
1949 || TREE_CODE (var) == MEMORY_PARTITION_TAG
1950 || !is_global_var (var))
1951 clear_call_clobbered (var);
1954 /* Clear flow-sensitive points-to information from each SSA name. */
1955 for (i = 1; i < num_ssa_names; i++)
1957 tree name = ssa_name (i);
1959 if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
1962 if (SSA_NAME_PTR_INFO (name))
1964 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
1966 /* Clear all the flags but keep the name tag to
1967 avoid creating new temporaries unnecessarily. If
1968 this pointer is found to point to a subset or
1969 superset of its former points-to set, then a new
1970 tag will need to be created in create_name_tags. */
1971 pi->pt_anything = 0;
1973 pi->value_escapes_p = 0;
1974 pi->is_dereferenced = 0;
1976 bitmap_clear (pi->pt_vars);
1982 /* If this is the first time we compute aliasing information,
1983 every non-register symbol will need to be put into SSA form
1984 (the initial SSA form only operates on GIMPLE registers). */
1985 FOR_EACH_REFERENCED_VAR (var, rvi)
1986 if (!is_gimple_reg (var))
1987 mark_sym_for_renaming (var);
1990 /* Next time, we will need to reset alias information. */
1991 cfun->gimple_df->aliases_computed_p = true;
1992 if (alias_bitmap_obstack.elements != NULL)
1993 bitmap_obstack_release (&alias_bitmap_obstack);
1994 bitmap_obstack_initialize (&alias_bitmap_obstack);
2000 /* Deallocate memory used by alias analysis. */
2003 delete_alias_info (struct alias_info *ai)
2007 sbitmap_free (ai->ssa_names_visited);
2009 VEC_free (tree, heap, ai->processed_ptrs);
2011 for (i = 0; i < ai->num_addressable_vars; i++)
2012 free (ai->addressable_vars[i]);
2013 free (ai->addressable_vars);
2015 for (i = 0; i < ai->num_pointers; i++)
2016 free (ai->pointers[i]);
2017 free (ai->pointers);
2019 pointer_set_destroy (ai->written_vars);
2020 pointer_set_destroy (ai->dereferenced_ptrs_store);
2021 pointer_set_destroy (ai->dereferenced_ptrs_load);
2024 delete_mem_ref_stats (cfun);
2025 delete_points_to_sets ();
2029 /* Used for hashing to identify pointer infos with identical
2033 eq_ptr_info (const void *p1, const void *p2)
2035 const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
2036 const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
2037 return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
2041 ptr_info_hash (const void *p)
2043 const struct ptr_info_def *n = (const struct ptr_info_def *) p;
2044 return bitmap_hash (n->pt_vars);
2048 /* Create name tags for all the pointers that have been dereferenced.
2049 We only create a name tag for a pointer P if P is found to point to
2050 a set of variables (so that we can alias them to *P) or if it is
2051 the result of a call to malloc (which means that P cannot point to
2052 anything else nor alias any other variable).
2054 If two pointers P and Q point to the same set of variables, they
2055 are assigned the same name tag. */
2058 create_name_tags (void)
2061 VEC (tree, heap) *with_ptvars = NULL;
2065 /* Collect the list of pointers with a non-empty points to set. */
2066 for (i = 1; i < num_ssa_names; i++)
2068 tree ptr = ssa_name (i);
2069 struct ptr_info_def *pi;
2072 || !POINTER_TYPE_P (TREE_TYPE (ptr))
2073 || !SSA_NAME_PTR_INFO (ptr))
2076 pi = SSA_NAME_PTR_INFO (ptr);
2078 if (pi->pt_anything || !pi->is_dereferenced)
2080 /* No name tags for pointers that have not been
2081 dereferenced or point to an arbitrary location. */
2082 pi->name_mem_tag = NULL_TREE;
2086 /* Set pt_anything on the pointers without pt_vars filled in so
2087 that they are assigned a symbol tag. */
2088 if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
2089 VEC_safe_push (tree, heap, with_ptvars, ptr);
2091 set_pt_anything (ptr);
2094 /* If we didn't find any pointers with pt_vars set, we're done. */
2098 ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
2100 /* Now go through the pointers with pt_vars, and find a name tag
2101 with the same pt_vars as this pointer, or create one if one
2103 for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
2105 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2106 tree old_name_tag = pi->name_mem_tag;
2107 struct ptr_info_def **slot;
2109 /* If PTR points to a set of variables, check if we don't
2110 have another pointer Q with the same points-to set before
2111 creating a tag. If so, use Q's tag instead of creating a
2114 This is important for not creating unnecessary symbols
2115 and also for copy propagation. If we ever need to
2116 propagate PTR into Q or vice-versa, we would run into
2117 problems if they both had different name tags because
2118 they would have different SSA version numbers (which
2119 would force us to take the name tags in and out of SSA). */
2120 slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
2122 pi->name_mem_tag = (*slot)->name_mem_tag;
2126 /* If we didn't find a pointer with the same points-to set
2127 as PTR, create a new name tag if needed. */
2128 if (pi->name_mem_tag == NULL_TREE)
2129 pi->name_mem_tag = get_nmt_for (ptr);
2132 /* If the new name tag computed for PTR is different than
2133 the old name tag that it used to have, then the old tag
2134 needs to be removed from the IL, so we mark it for
2136 if (old_name_tag && old_name_tag != pi->name_mem_tag)
2137 mark_sym_for_renaming (old_name_tag);
2139 TREE_THIS_VOLATILE (pi->name_mem_tag)
2140 |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
2142 /* Mark the new name tag for renaming. */
2143 mark_sym_for_renaming (pi->name_mem_tag);
2146 htab_delete (ptr_hash);
2148 VEC_free (tree, heap, with_ptvars);
2152 /* Union the alias set SET into the may-aliases for TAG. */
2155 union_alias_set_into (tree tag, bitmap set)
2157 bitmap ma = MTAG_ALIASES (tag);
2159 if (bitmap_empty_p (set))
2163 ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack);
2164 bitmap_ior_into (ma, set);
2168 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
2169 the name memory tag (NMT) associated with P_i. If P_i escapes, then its
2170 name tag and the variables it points-to are call-clobbered. Finally, if
2171 P_i escapes and we could not determine where it points to, then all the
2172 variables in the same alias set as *P_i are marked call-clobbered. This
2173 is necessary because we must assume that P_i may take the address of any
2174 variable in the same alias set. */
2177 compute_flow_sensitive_aliasing (struct alias_info *ai)
2182 timevar_push (TV_FLOW_SENSITIVE);
2185 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2187 if (!find_what_p_points_to (ptr))
2188 set_pt_anything (ptr);
2191 create_name_tags ();
2193 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2195 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2196 tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
2198 /* Set up aliasing information for PTR's name memory tag (if it has
2199 one). Note that only pointers that have been dereferenced will
2200 have a name memory tag. */
2201 if (pi->name_mem_tag && pi->pt_vars)
2203 if (!bitmap_empty_p (pi->pt_vars))
2205 union_alias_set_into (pi->name_mem_tag, pi->pt_vars);
2206 union_alias_set_into (tag, pi->pt_vars);
2207 bitmap_clear_bit (MTAG_ALIASES (tag), DECL_UID (tag));
2209 /* It may be the case that this the tag uid was the only
2210 bit we had set in the aliases list, and in this case,
2211 we don't want to keep an empty bitmap, as this
2212 asserts in tree-ssa-operands.c . */
2213 if (bitmap_empty_p (MTAG_ALIASES (tag)))
2214 BITMAP_FREE (MTAG_ALIASES (tag));
2218 timevar_pop (TV_FLOW_SENSITIVE);
2222 /* Return TRUE if at least one symbol in TAG2's alias set is also
2223 present in TAG1's alias set. */
2226 have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases)
2229 /* This is the old behavior of have_common_aliases_p, which is to
2230 return false if both sets are empty, or one set is and the other
2232 if ((tag1aliases == NULL && tag2aliases != NULL)
2233 || (tag2aliases == NULL && tag1aliases != NULL)
2234 || (tag1aliases == NULL && tag2aliases == NULL))
2237 return bitmap_intersect_p (tag1aliases, tag2aliases);
2240 /* Compute type-based alias sets. Traverse all the pointers and
2241 addressable variables found in setup_pointers_and_addressables.
2243 For every pointer P in AI->POINTERS and addressable variable V in
2244 AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
2245 memory tag (SMT) if their alias sets conflict. V is then marked as
2246 an aliased symbol so that the operand scanner knows that statements
2247 containing V have aliased operands. */
2250 compute_flow_insensitive_aliasing (struct alias_info *ai)
2254 timevar_push (TV_FLOW_INSENSITIVE);
2255 /* For every pointer P, determine which addressable variables may alias
2256 with P's symbol memory tag. */
2257 for (i = 0; i < ai->num_pointers; i++)
2260 struct alias_map_d *p_map = ai->pointers[i];
2261 tree tag = symbol_mem_tag (p_map->var);
2264 /* Call-clobbering information is not finalized yet at this point. */
2265 if (PTR_IS_REF_ALL (p_map->var))
2268 for (j = 0; j < ai->num_addressable_vars; j++)
2270 struct alias_map_d *v_map;
2272 bool tag_stored_p, var_stored_p;
2274 v_map = ai->addressable_vars[j];
2276 v_ann = var_ann (var);
2278 /* Skip memory tags and variables that have never been
2279 written to. We also need to check if the variables are
2280 call-clobbered because they may be overwritten by
2282 tag_stored_p = pointer_set_contains (ai->written_vars, tag)
2283 || is_call_clobbered (tag);
2284 var_stored_p = pointer_set_contains (ai->written_vars, var)
2285 || is_call_clobbered (var);
2286 if (!tag_stored_p && !var_stored_p)
2289 if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
2291 /* We should never have a var with subvars here, because
2292 they shouldn't get into the set of addressable vars */
2293 gcc_assert (!var_can_have_subvars (var)
2294 || get_subvars_for_var (var) == NULL);
2296 /* Add VAR to TAG's may-aliases set. */
2297 add_may_alias (tag, var);
2302 /* Since this analysis is based exclusively on symbols, it fails to
2303 handle cases where two pointers P and Q have different memory
2304 tags with conflicting alias set numbers but no aliased symbols in
2307 For example, suppose that we have two memory tags SMT.1 and SMT.2
2310 may-aliases (SMT.1) = { a }
2311 may-aliases (SMT.2) = { b }
2313 and the alias set number of SMT.1 conflicts with that of SMT.2.
2314 Since they don't have symbols in common, loads and stores from
2315 SMT.1 and SMT.2 will seem independent of each other, which will
2316 lead to the optimizers making invalid transformations (see
2317 testsuite/gcc.c-torture/execute/pr15262-[12].c).
2319 To avoid this problem, we do a final traversal of AI->POINTERS
2320 looking for pairs of pointers that have no aliased symbols in
2321 common and yet have conflicting alias set numbers. */
2322 for (i = 0; i < ai->num_pointers; i++)
2325 struct alias_map_d *p_map1 = ai->pointers[i];
2326 tree tag1 = symbol_mem_tag (p_map1->var);
2327 bitmap may_aliases1 = MTAG_ALIASES (tag1);
2329 if (PTR_IS_REF_ALL (p_map1->var))
2332 for (j = i + 1; j < ai->num_pointers; j++)
2334 struct alias_map_d *p_map2 = ai->pointers[j];
2335 tree tag2 = symbol_mem_tag (p_map2->var);
2336 bitmap may_aliases2 = may_aliases (tag2);
2338 if (PTR_IS_REF_ALL (p_map2->var))
2341 /* If the pointers may not point to each other, do nothing. */
2342 if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
2345 /* The two pointers may alias each other. If they already have
2346 symbols in common, do nothing. */
2347 if (have_common_aliases_p (may_aliases1, may_aliases2))
2350 if (may_aliases2 && !bitmap_empty_p (may_aliases2))
2352 union_alias_set_into (tag1, may_aliases2);
2356 /* Since TAG2 does not have any aliases of its own, add
2357 TAG2 itself to the alias set of TAG1. */
2358 add_may_alias (tag1, tag2);
2363 timevar_pop (TV_FLOW_INSENSITIVE);
2367 /* Finalize may-alias information for ref-all pointers. Traverse all
2368 the addressable variables found in setup_pointers_and_addressables.
2370 If flow-sensitive alias analysis has attached a name memory tag to
2371 a ref-all pointer, we will use it for the dereferences because that
2372 will have more precise aliasing information. But if there is no
2373 name tag, we will use a special symbol tag that aliases all the
2374 call-clobbered addressable variables. */
2377 finalize_ref_all_pointers (struct alias_info *ai)
2381 /* First add the real call-clobbered variables. */
2382 for (i = 0; i < ai->num_addressable_vars; i++)
2384 tree var = ai->addressable_vars[i]->var;
2385 if (is_call_clobbered (var))
2386 add_may_alias (ai->ref_all_symbol_mem_tag, var);
2389 /* Then add the call-clobbered pointer memory tags. See
2390 compute_flow_insensitive_aliasing for the rationale. */
2391 for (i = 0; i < ai->num_pointers; i++)
2393 tree ptr = ai->pointers[i]->var, tag;
2394 /* Avoid adding to self and clean up. */
2395 if (PTR_IS_REF_ALL (ptr))
2397 struct ptr_info_def *pi = get_ptr_info (ptr);
2398 if (pi->is_dereferenced)
2399 pi->pt_anything = 0;
2402 tag = symbol_mem_tag (ptr);
2403 if (is_call_clobbered (tag))
2404 add_may_alias (ai->ref_all_symbol_mem_tag, tag);
2410 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */
2413 create_alias_map_for (tree var, struct alias_info *ai)
2415 struct alias_map_d *alias_map;
2416 alias_map = XCNEW (struct alias_map_d);
2417 alias_map->var = var;
2418 alias_map->set = get_alias_set (var);
2419 ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
2423 /* Create memory tags for all the dereferenced pointers and build the
2424 ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
2425 sets. Based on the address escape and points-to information collected
2426 earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
2427 variables whose address is not needed anymore. */
2430 setup_pointers_and_addressables (struct alias_info *ai)
2432 size_t num_addressable_vars, num_pointers;
2433 referenced_var_iterator rvi;
2435 VEC (tree, heap) *varvec = NULL;
2436 safe_referenced_var_iterator srvi;
2438 /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
2439 num_addressable_vars = num_pointers = 0;
2441 FOR_EACH_REFERENCED_VAR (var, rvi)
2443 if (may_be_aliased (var))
2444 num_addressable_vars++;
2446 if (POINTER_TYPE_P (TREE_TYPE (var)))
2448 /* Since we don't keep track of volatile variables, assume that
2449 these pointers are used in indirect store operations. */
2450 if (TREE_THIS_VOLATILE (var))
2451 pointer_set_insert (ai->dereferenced_ptrs_store, var);
2457 /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
2458 always going to be slightly bigger than we actually need them
2459 because some TREE_ADDRESSABLE variables will be marked
2460 non-addressable below and only pointers with unique symbol tags are
2461 going to be added to POINTERS. */
2462 ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
2463 ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
2464 ai->num_addressable_vars = 0;
2465 ai->num_pointers = 0;
2467 FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
2471 /* Name memory tags already have flow-sensitive aliasing
2472 information, so they need not be processed by
2473 compute_flow_insensitive_aliasing. Similarly, symbol memory
2474 tags are already accounted for when we process their
2477 Structure fields, on the other hand, have to have some of this
2478 information processed for them, but it's pointless to mark them
2479 non-addressable (since they are fake variables anyway). */
2480 if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG)
2483 /* Remove the ADDRESSABLE flag from every addressable variable whose
2484 address is not needed anymore. This is caused by the propagation
2485 of ADDR_EXPR constants into INDIRECT_REF expressions and the
2486 removal of dead pointer assignments done by the early scalar
2488 if (TREE_ADDRESSABLE (var))
2490 if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var))
2491 && TREE_CODE (var) != RESULT_DECL
2492 && !is_global_var (var))
2494 bool okay_to_mark = true;
2496 /* Since VAR is now a regular GIMPLE register, we will need
2497 to rename VAR into SSA afterwards. */
2498 mark_sym_for_renaming (var);
2500 /* If VAR can have sub-variables, and any of its
2501 sub-variables has its address taken, then we cannot
2502 remove the addressable flag from VAR. */
2503 if (var_can_have_subvars (var)
2504 && (svars = get_subvars_for_var (var)))
2508 for (sv = svars; sv; sv = sv->next)
2510 if (bitmap_bit_p (gimple_addressable_vars (cfun),
2511 DECL_UID (sv->var)))
2512 okay_to_mark = false;
2513 mark_sym_for_renaming (sv->var);
2517 /* The address of VAR is not needed, remove the
2518 addressable bit, so that it can be optimized as a
2519 regular variable. */
2522 /* The memory partition holding VAR will no longer
2523 contain VAR, and statements referencing it will need
2525 if (memory_partition (var))
2526 mark_sym_for_renaming (memory_partition (var));
2528 mark_non_addressable (var);
2533 /* Global variables and addressable locals may be aliased. Create an
2534 entry in ADDRESSABLE_VARS for VAR. */
2535 if (may_be_aliased (var))
2537 if (!var_can_have_subvars (var)
2538 || get_subvars_for_var (var) == NULL)
2539 create_alias_map_for (var, ai);
2541 mark_sym_for_renaming (var);
2544 /* Add pointer variables that have been dereferenced to the POINTERS
2545 array and create a symbol memory tag for them. */
2546 if (POINTER_TYPE_P (TREE_TYPE (var)))
2548 if ((pointer_set_contains (ai->dereferenced_ptrs_store, var)
2549 || pointer_set_contains (ai->dereferenced_ptrs_load, var)))
2554 /* If pointer VAR still doesn't have a memory tag
2555 associated with it, create it now or re-use an
2557 tag = get_smt_for (var, ai);
2558 t_ann = var_ann (tag);
2560 /* The symbol tag will need to be renamed into SSA
2561 afterwards. Note that we cannot do this inside
2562 get_smt_for because aliasing may run multiple times
2563 and we only create symbol tags the first time. */
2564 mark_sym_for_renaming (tag);
2566 /* Similarly, if pointer VAR used to have another type
2567 tag, we will need to process it in the renamer to
2568 remove the stale virtual operands. */
2569 old_tag = symbol_mem_tag (var);
2571 mark_sym_for_renaming (old_tag);
2573 /* Associate the tag with pointer VAR. */
2574 set_symbol_mem_tag (var, tag);
2576 /* If pointer VAR has been used in a store operation,
2577 then its memory tag must be marked as written-to. */
2578 if (pointer_set_contains (ai->dereferenced_ptrs_store, var))
2579 pointer_set_insert (ai->written_vars, tag);
2583 /* The pointer has not been dereferenced. If it had a
2584 symbol memory tag, remove it and mark the old tag for
2585 renaming to remove it out of the IL. */
2586 tree tag = symbol_mem_tag (var);
2589 mark_sym_for_renaming (tag);
2590 set_symbol_mem_tag (var, NULL_TREE);
2596 VEC_free (tree, heap, varvec);
2600 /* Determine whether to use .GLOBAL_VAR to model call clobbering
2601 semantics. If the function makes no references to global
2602 variables and contains at least one call to a non-pure function,
2603 then we need to mark the side-effects of the call using .GLOBAL_VAR
2604 to represent all possible global memory referenced by the callee. */
2607 maybe_create_global_var (void)
2609 /* No need to create it, if we have one already. */
2610 if (gimple_global_var (cfun) == NULL_TREE)
2612 struct mem_ref_stats_d *stats = gimple_mem_ref_stats (cfun);
2614 /* Create .GLOBAL_VAR if there are no call-clobbered
2615 variables and the program contains a mixture of pure/const
2616 and regular function calls. This is to avoid the problem
2617 described in PR 20115:
2620 int func_pure (void) { return X; }
2621 int func_non_pure (int a) { X += a; }
2624 int a = func_pure ();
2630 Since foo() has no call-clobbered variables, there is
2631 no relationship between the calls to func_pure and
2632 func_non_pure. Since func_pure has no side-effects, value
2633 numbering optimizations elide the second call to func_pure.
2634 So, if we have some pure/const and some regular calls in the
2635 program we create .GLOBAL_VAR to avoid missing these
2637 if (bitmap_count_bits (gimple_call_clobbered_vars (cfun)) == 0
2638 && stats->num_call_sites > 0
2639 && stats->num_pure_const_call_sites > 0
2640 && stats->num_call_sites > stats->num_pure_const_call_sites)
2641 create_global_var ();
2646 /* Return TRUE if pointer PTR may point to variable VAR.
2648 MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
2649 This is needed because when checking for type conflicts we are
2650 interested in the alias set of the memory location pointed-to by
2651 PTR. The alias set of PTR itself is irrelevant.
2653 VAR_ALIAS_SET is the alias set for VAR. */
2656 may_alias_p (tree ptr, alias_set_type mem_alias_set,
2657 tree var, alias_set_type var_alias_set,
2658 bool alias_set_only)
2662 alias_stats.alias_queries++;
2663 alias_stats.simple_queries++;
2665 /* By convention, a variable cannot alias itself. */
2666 mem = symbol_mem_tag (ptr);
2669 alias_stats.alias_noalias++;
2670 alias_stats.simple_resolved++;
2674 /* If -fargument-noalias-global is > 2, pointer arguments may
2675 not point to anything else. */
2676 if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
2678 alias_stats.alias_noalias++;
2679 alias_stats.simple_resolved++;
2683 /* If -fargument-noalias-global is > 1, pointer arguments may
2684 not point to global variables. */
2685 if (flag_argument_noalias > 1 && is_global_var (var)
2686 && TREE_CODE (ptr) == PARM_DECL)
2688 alias_stats.alias_noalias++;
2689 alias_stats.simple_resolved++;
2693 /* If either MEM or VAR is a read-only global and the other one
2694 isn't, then PTR cannot point to VAR. */
2695 if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
2696 || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
2698 alias_stats.alias_noalias++;
2699 alias_stats.simple_resolved++;
2703 gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
2705 if (!DECL_NO_TBAA_P (ptr))
2707 alias_stats.tbaa_queries++;
2709 /* If the alias sets don't conflict then MEM cannot alias VAR. */
2710 if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
2712 alias_stats.alias_noalias++;
2713 alias_stats.tbaa_resolved++;
2717 /* If VAR is a record or union type, PTR cannot point into VAR
2718 unless there is some explicit address operation in the
2719 program that can reference a field of the type pointed-to by
2720 PTR. This also assumes that the types of both VAR and PTR
2721 are contained within the compilation unit, and that there is
2722 no fancy addressing arithmetic associated with any of the
2724 if (mem_alias_set != 0 && var_alias_set != 0)
2726 tree ptr_type = TREE_TYPE (ptr);
2727 tree var_type = TREE_TYPE (var);
2729 /* The star count is -1 if the type at the end of the
2730 pointer_to chain is not a record or union type. */
2731 if ((!alias_set_only) &&
2732 ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
2734 int ptr_star_count = 0;
2736 /* ipa_type_escape_star_count_of_interesting_type is a
2737 little too restrictive for the pointer type, need to
2738 allow pointers to primitive types as long as those
2739 types cannot be pointers to everything. */
2740 while (POINTER_TYPE_P (ptr_type))
2742 /* Strip the *s off. */
2743 ptr_type = TREE_TYPE (ptr_type);
2747 /* There does not appear to be a better test to see if
2748 the pointer type was one of the pointer to everything
2750 if (ptr_star_count > 0)
2752 alias_stats.structnoaddress_queries++;
2753 if (ipa_type_escape_field_does_not_clobber_p (var_type,
2756 alias_stats.structnoaddress_resolved++;
2757 alias_stats.alias_noalias++;
2761 else if (ptr_star_count == 0)
2763 /* If PTR_TYPE was not really a pointer to type, it cannot
2765 alias_stats.structnoaddress_queries++;
2766 alias_stats.structnoaddress_resolved++;
2767 alias_stats.alias_noalias++;
2774 alias_stats.alias_mayalias++;
2779 /* Add ALIAS to the set of variables that may alias VAR. */
2782 add_may_alias (tree var, tree alias)
2784 /* Don't allow self-referential aliases. */
2785 gcc_assert (var != alias);
2787 /* ALIAS must be addressable if it's being added to an alias set. */
2789 TREE_ADDRESSABLE (alias) = 1;
2791 gcc_assert (may_be_aliased (alias));
2794 /* VAR must be a symbol or a name tag. */
2795 gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG
2796 || TREE_CODE (var) == NAME_MEMORY_TAG);
2798 if (MTAG_ALIASES (var) == NULL)
2799 MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack);
2801 bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias));
2805 /* Mark pointer PTR as pointing to an arbitrary memory location. */
2808 set_pt_anything (tree ptr)
2810 struct ptr_info_def *pi = get_ptr_info (ptr);
2812 pi->pt_anything = 1;
2815 /* The pointer used to have a name tag, but we now found it pointing
2816 to an arbitrary location. The name tag needs to be renamed and
2817 disassociated from PTR. */
2818 if (pi->name_mem_tag)
2820 mark_sym_for_renaming (pi->name_mem_tag);
2821 pi->name_mem_tag = NULL_TREE;
2826 /* Return true if STMT is an "escape" site from the current function. Escape
2827 sites those statements which might expose the address of a variable
2828 outside the current function. STMT is an escape site iff:
2830 1- STMT is a function call, or
2831 2- STMT is an __asm__ expression, or
2832 3- STMT is an assignment to a non-local variable, or
2833 4- STMT is a return statement.
2835 Return the type of escape site found, if we found one, or NO_ESCAPE
2839 is_escape_site (tree stmt)
2841 tree call = get_call_expr_in (stmt);
2842 if (call != NULL_TREE)
2844 if (!TREE_SIDE_EFFECTS (call))
2845 return ESCAPE_TO_PURE_CONST;
2847 return ESCAPE_TO_CALL;
2849 else if (TREE_CODE (stmt) == ASM_EXPR)
2850 return ESCAPE_TO_ASM;
2851 else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2853 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
2855 /* Get to the base of _REF nodes. */
2856 if (TREE_CODE (lhs) != SSA_NAME)
2857 lhs = get_base_address (lhs);
2859 /* If we couldn't recognize the LHS of the assignment, assume that it
2860 is a non-local store. */
2861 if (lhs == NULL_TREE)
2862 return ESCAPE_UNKNOWN;
2864 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == NOP_EXPR
2865 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CONVERT_EXPR
2866 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
2869 = TREE_TYPE (TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0));
2870 tree to = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 1));
2872 /* If the RHS is a conversion between a pointer and an integer, the
2873 pointer escapes since we can't track the integer. */
2874 if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
2875 return ESCAPE_BAD_CAST;
2877 /* Same if the RHS is a conversion between a regular pointer and a
2878 ref-all pointer since we can't track the SMT of the former. */
2879 if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from)
2880 && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (to))
2881 return ESCAPE_BAD_CAST;
2884 /* If the LHS is an SSA name, it can't possibly represent a non-local
2886 if (TREE_CODE (lhs) == SSA_NAME)
2889 /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
2890 local variables we cannot be sure if it will escape, because we
2891 don't have information about objects not in SSA form. Need to
2892 implement something along the lines of
2894 J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
2895 Midkiff, ``Escape analysis for java,'' in Proceedings of the
2896 Conference on Object-Oriented Programming Systems, Languages, and
2897 Applications (OOPSLA), pp. 1-19, 1999. */
2898 return ESCAPE_STORED_IN_GLOBAL;
2900 else if (TREE_CODE (stmt) == RETURN_EXPR)
2901 return ESCAPE_TO_RETURN;
2906 /* Create a new memory tag of type TYPE.
2907 Does NOT push it into the current binding. */
2910 create_tag_raw (enum tree_code code, tree type, const char *prefix)
2914 tmp_var = build_decl (code, create_tmp_var_name (prefix), type);
2916 /* Make the variable writable. */
2917 TREE_READONLY (tmp_var) = 0;
2919 /* It doesn't start out global. */
2920 MTAG_GLOBAL (tmp_var) = 0;
2921 TREE_STATIC (tmp_var) = 0;
2922 TREE_USED (tmp_var) = 1;
2927 /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
2928 is considered to represent all the pointers whose pointed-to types are
2929 in the same alias set class. Otherwise, the tag represents a single
2930 SSA_NAME pointer variable. */
2933 create_memory_tag (tree type, bool is_type_tag)
2935 tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
2936 type, (is_type_tag) ? "SMT" : "NMT");
2938 /* By default, memory tags are local variables. Alias analysis will
2939 determine whether they should be considered globals. */
2940 DECL_CONTEXT (tag) = current_function_decl;
2942 /* Memory tags are by definition addressable. */
2943 TREE_ADDRESSABLE (tag) = 1;
2945 set_symbol_mem_tag (tag, NULL_TREE);
2947 /* Add the tag to the symbol table. */
2948 add_referenced_var (tag);
2954 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
2955 This is used if P_i has been found to point to a specific set of
2956 variables or to a non-aliased memory location like the address returned
2957 by malloc functions. */
2960 get_nmt_for (tree ptr)
2962 struct ptr_info_def *pi = get_ptr_info (ptr);
2963 tree tag = pi->name_mem_tag;
2965 if (tag == NULL_TREE)
2966 tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
2971 /* Return the symbol memory tag associated to pointer PTR. A memory
2972 tag is an artificial variable that represents the memory location
2973 pointed-to by PTR. It is used to model the effects of pointer
2974 de-references on addressable variables.
2976 AI points to the data gathered during alias analysis. This
2977 function populates the array AI->POINTERS. */
2980 get_smt_for (tree ptr, struct alias_info *ai)
2984 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2985 alias_set_type tag_set = get_alias_set (tag_type);
2987 /* We use a unique memory tag for all the ref-all pointers. */
2988 if (PTR_IS_REF_ALL (ptr))
2990 if (!ai->ref_all_symbol_mem_tag)
2991 ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true);
2992 return ai->ref_all_symbol_mem_tag;
2995 /* To avoid creating unnecessary memory tags, only create one memory tag
2996 per alias set class. Note that it may be tempting to group
2997 memory tags based on conflicting alias sets instead of
2998 equivalence. That would be wrong because alias sets are not
2999 necessarily transitive (as demonstrated by the libstdc++ test
3000 23_containers/vector/cons/4.cc). Given three alias sets A, B, C
3001 such that conflicts (A, B) == true and conflicts (A, C) == true,
3002 it does not necessarily follow that conflicts (B, C) == true. */
3003 for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
3005 struct alias_map_d *curr = ai->pointers[i];
3006 tree curr_tag = symbol_mem_tag (curr->var);
3007 if (tag_set == curr->set)
3014 /* If VAR cannot alias with any of the existing memory tags, create a new
3015 tag for PTR and add it to the POINTERS array. */
3016 if (tag == NULL_TREE)
3018 struct alias_map_d *alias_map;
3020 /* If PTR did not have a symbol tag already, create a new SMT.*
3021 artificial variable representing the memory location
3022 pointed-to by PTR. */
3023 tag = symbol_mem_tag (ptr);
3024 if (tag == NULL_TREE)
3025 tag = create_memory_tag (tag_type, true);
3027 /* Add PTR to the POINTERS array. Note that we are not interested in
3028 PTR's alias set. Instead, we cache the alias set for the memory that
3030 alias_map = XCNEW (struct alias_map_d);
3031 alias_map->var = ptr;
3032 alias_map->set = tag_set;
3033 ai->pointers[ai->num_pointers++] = alias_map;
3036 /* If the pointed-to type is volatile, so is the tag. */
3037 TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
3039 /* Make sure that the symbol tag has the same alias set as the
3041 gcc_assert (tag_set == get_alias_set (tag));
3047 /* Create GLOBAL_VAR, an artificial global variable to act as a
3048 representative of all the variables that may be clobbered by function
3052 create_global_var (void)
3054 tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
3056 DECL_ARTIFICIAL (global_var) = 1;
3057 TREE_READONLY (global_var) = 0;
3058 DECL_EXTERNAL (global_var) = 1;
3059 TREE_STATIC (global_var) = 1;
3060 TREE_USED (global_var) = 1;
3061 DECL_CONTEXT (global_var) = NULL_TREE;
3062 TREE_THIS_VOLATILE (global_var) = 0;
3063 TREE_ADDRESSABLE (global_var) = 0;
3065 create_var_ann (global_var);
3066 mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
3067 add_referenced_var (global_var);
3068 mark_sym_for_renaming (global_var);
3069 cfun->gimple_df->global_var = global_var;
3073 /* Dump alias statistics on FILE. */
3076 dump_alias_stats (FILE *file)
3078 const char *funcname
3079 = lang_hooks.decl_printable_name (current_function_decl, 2);
3080 fprintf (file, "\nAlias statistics for %s\n\n", funcname);
3081 fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
3082 fprintf (file, "Total alias mayalias results:\t%u\n",
3083 alias_stats.alias_mayalias);
3084 fprintf (file, "Total alias noalias results:\t%u\n",
3085 alias_stats.alias_noalias);
3086 fprintf (file, "Total simple queries:\t%u\n",
3087 alias_stats.simple_queries);
3088 fprintf (file, "Total simple resolved:\t%u\n",
3089 alias_stats.simple_resolved);
3090 fprintf (file, "Total TBAA queries:\t%u\n",
3091 alias_stats.tbaa_queries);
3092 fprintf (file, "Total TBAA resolved:\t%u\n",
3093 alias_stats.tbaa_resolved);
3094 fprintf (file, "Total non-addressable structure type queries:\t%u\n",
3095 alias_stats.structnoaddress_queries);
3096 fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
3097 alias_stats.structnoaddress_resolved);
3101 /* Dump alias information on FILE. */
3104 dump_alias_info (FILE *file)
3107 const char *funcname
3108 = lang_hooks.decl_printable_name (current_function_decl, 2);
3109 referenced_var_iterator rvi;
3112 fprintf (file, "\nAlias information for %s\n\n", funcname);
3114 dump_memory_partitions (file);
3116 fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
3118 fprintf (file, "Aliased symbols\n\n");
3120 FOR_EACH_REFERENCED_VAR (var, rvi)
3122 if (may_be_aliased (var))
3123 dump_variable (file, var);
3126 fprintf (file, "\nDereferenced pointers\n\n");
3128 FOR_EACH_REFERENCED_VAR (var, rvi)
3129 if (symbol_mem_tag (var))
3130 dump_variable (file, var);
3132 fprintf (file, "\nSymbol memory tags\n\n");
3134 FOR_EACH_REFERENCED_VAR (var, rvi)
3136 if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
3137 dump_variable (file, var);
3140 fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
3142 fprintf (file, "SSA_NAME pointers\n\n");
3143 for (i = 1; i < num_ssa_names; i++)
3145 tree ptr = ssa_name (i);
3146 struct ptr_info_def *pi;
3148 if (ptr == NULL_TREE)
3151 pi = SSA_NAME_PTR_INFO (ptr);
3152 if (!SSA_NAME_IN_FREE_LIST (ptr)
3154 && pi->name_mem_tag)
3155 dump_points_to_info_for (file, ptr);
3158 fprintf (file, "\nName memory tags\n\n");
3160 FOR_EACH_REFERENCED_VAR (var, rvi)
3162 if (TREE_CODE (var) == NAME_MEMORY_TAG)
3163 dump_variable (file, var);
3166 fprintf (file, "\n");
3170 /* Dump alias information on stderr. */
3173 debug_alias_info (void)
3175 dump_alias_info (stderr);
3179 /* Return the alias information associated with pointer T. It creates a
3180 new instance if none existed. */
3182 struct ptr_info_def *
3183 get_ptr_info (tree t)
3185 struct ptr_info_def *pi;
3187 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
3189 pi = SSA_NAME_PTR_INFO (t);
3192 pi = GGC_CNEW (struct ptr_info_def);
3193 SSA_NAME_PTR_INFO (t) = pi;
3200 /* Dump points-to information for SSA_NAME PTR into FILE. */
3203 dump_points_to_info_for (FILE *file, tree ptr)
3205 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3207 print_generic_expr (file, ptr, dump_flags);
3211 if (pi->name_mem_tag)
3213 fprintf (file, ", name memory tag: ");
3214 print_generic_expr (file, pi->name_mem_tag, dump_flags);
3217 if (pi->is_dereferenced)
3218 fprintf (file, ", is dereferenced (R=%ld, W=%ld)",
3219 get_mem_sym_stats_for (ptr)->num_direct_reads,
3220 get_mem_sym_stats_for (ptr)->num_direct_writes);
3222 if (pi->value_escapes_p)
3223 fprintf (file, ", its value escapes");
3225 if (pi->pt_anything)
3226 fprintf (file, ", points-to anything");
3229 fprintf (file, ", points-to NULL");
3233 fprintf (file, ", points-to vars: ");
3234 dump_decl_set (file, pi->pt_vars);
3238 fprintf (file, "\n");
3242 /* Dump points-to information for VAR into stderr. */
3245 debug_points_to_info_for (tree var)
3247 dump_points_to_info_for (stderr, var);
3251 /* Dump points-to information into FILE. NOTE: This function is slow, as
3252 it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
3255 dump_points_to_info (FILE *file)
3258 block_stmt_iterator si;
3261 lang_hooks.decl_printable_name (current_function_decl, 2);
3262 referenced_var_iterator rvi;
3265 fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
3267 /* First dump points-to information for the default definitions of
3268 pointer variables. This is necessary because default definitions are
3269 not part of the code. */
3270 FOR_EACH_REFERENCED_VAR (var, rvi)
3272 if (POINTER_TYPE_P (TREE_TYPE (var)))
3274 tree def = gimple_default_def (cfun, var);
3276 dump_points_to_info_for (file, def);
3280 /* Dump points-to information for every pointer defined in the program. */
3285 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3287 tree ptr = PHI_RESULT (phi);
3288 if (POINTER_TYPE_P (TREE_TYPE (ptr)))
3289 dump_points_to_info_for (file, ptr);
3292 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3294 tree stmt = bsi_stmt (si);
3296 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3297 if (TREE_CODE (def) == SSA_NAME
3298 && POINTER_TYPE_P (TREE_TYPE (def)))
3299 dump_points_to_info_for (file, def);
3303 fprintf (file, "\n");
3307 /* Dump points-to info pointed to by PTO into STDERR. */
3310 debug_points_to_info (void)
3312 dump_points_to_info (stderr);
3315 /* Dump to FILE the list of variables that may be aliasing VAR. */
3318 dump_may_aliases_for (FILE *file, tree var)
3322 aliases = MTAG_ALIASES (var);
3329 fprintf (file, "{ ");
3330 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
3332 al = referenced_var (i);
3333 print_generic_expr (file, al, dump_flags);
3334 fprintf (file, " ");
3336 fprintf (file, "}");
3341 /* Dump to stderr the list of variables that may be aliasing VAR. */
3344 debug_may_aliases_for (tree var)
3346 dump_may_aliases_for (stderr, var);
3350 /* Return true if VAR may be aliased. */
3353 may_be_aliased (tree var)
3356 if (TREE_ADDRESSABLE (var))
3359 /* Globally visible variables can have their addresses taken by other
3360 translation units. */
3362 && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
3364 else if (!MTAG_P (var)
3365 && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
3368 /* Automatic variables can't have their addresses escape any other
3369 way. This must be after the check for global variables, as
3370 extern declarations do not have TREE_STATIC set. */
3371 if (!TREE_STATIC (var))
3374 /* If we're in unit-at-a-time mode, then we must have seen all
3375 occurrences of address-of operators, and so we can trust
3376 TREE_ADDRESSABLE. Otherwise we can only be sure the variable
3377 isn't addressable if it's local to the current function. */
3378 if (flag_unit_at_a_time)
3381 if (decl_function_context (var) == current_function_decl)
3387 /* The following is based on code in add_stmt_operand to ensure that the
3388 same defs/uses/vdefs/vuses will be found after replacing a reference
3389 to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
3390 is the address of var. Return a memtag for the ptr, after adding the
3391 proper may_aliases to it (which are the aliases of var, if it has any,
3395 add_may_alias_for_new_tag (tree tag, tree var)
3397 bitmap aliases = NULL;
3400 aliases = may_aliases (var);
3402 /* Case 1: |aliases| == 1 */
3403 if (aliases && bitmap_count_bits (aliases) == 1)
3405 tree ali = referenced_var (bitmap_first_set_bit (aliases));
3406 if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
3410 /* Case 2: |aliases| == 0 */
3411 if (aliases == NULL)
3412 add_may_alias (tag, var);
3415 /* Case 3: |aliases| > 1 */
3416 union_alias_set_into (tag, aliases);
3421 /* Create a new symbol tag for PTR. Construct the may-alias list of this type
3422 tag so that it has the aliasing of VAR, or of the relevant subvars of VAR
3423 according to the location accessed by EXPR.
3425 Note, the set of aliases represented by the new symbol tag are not marked
3429 new_type_alias (tree ptr, tree var, tree expr)
3431 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
3434 tree ali = NULL_TREE;
3435 HOST_WIDE_INT offset, size, maxsize;
3437 VEC (tree, heap) *overlaps = NULL;
3441 gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
3442 gcc_assert (!MTAG_P (var));
3444 ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
3447 tag = create_memory_tag (tag_type, true);
3448 set_symbol_mem_tag (ptr, tag);
3450 /* Add VAR to the may-alias set of PTR's new symbol tag. If VAR has
3451 subvars, add the subvars to the tag instead of the actual var. */
3452 if (var_can_have_subvars (ref)
3453 && (svars = get_subvars_for_var (ref)))
3455 for (sv = svars; sv; sv = sv->next)
3459 if (overlap_subvar (offset, maxsize, sv->var, &exact))
3460 VEC_safe_push (tree, heap, overlaps, sv->var);
3462 gcc_assert (overlaps != NULL);
3464 else if (var_can_have_subvars (var)
3465 && (svars = get_subvars_for_var (var)))
3467 /* If the REF is not a direct access to VAR (e.g., it is a dereference
3468 of a pointer), we should scan the virtual operands of REF the same
3469 way as tree-ssa-operands do. At the moment, this is somewhat
3470 difficult, so we just give up and add all the subvars of VAR.
3471 On mem-ssa branch, the scanning for virtual operands have been
3472 split from the rest of tree-ssa-operands, so it should be much
3473 easier to fix this problem correctly once mem-ssa is merged. */
3474 for (sv = svars; sv; sv = sv->next)
3475 VEC_safe_push (tree, heap, overlaps, sv->var);
3477 gcc_assert (overlaps != NULL);
3480 ali = add_may_alias_for_new_tag (tag, var);
3482 len = VEC_length (tree, overlaps);
3485 if (dump_file && (dump_flags & TDF_DETAILS))
3486 fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len);
3489 ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0));
3495 for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++)
3497 ali = add_may_alias_for_new_tag (tag, sv_var);
3501 /* Can happen only if 'Case 1' of add_may_alias_for_new_tag
3502 took place. Since more than one svar was found, we add
3503 'ali' as one of the may_aliases of the new tag. */
3504 add_may_alias (tag, ali);
3509 VEC_free (tree, heap, overlaps);
3512 set_symbol_mem_tag (ptr, ali);
3513 TREE_READONLY (tag) = TREE_READONLY (var);
3514 MTAG_GLOBAL (tag) = is_global_var (var);
3517 /* This represents the used range of a variable. */
3519 typedef struct used_part
3521 HOST_WIDE_INT minused;
3522 HOST_WIDE_INT maxused;
3523 /* True if we have an explicit use/def of some portion of this variable,
3524 even if it is all of it. i.e. a.b = 5 or temp = a.b. */
3526 /* True if we have an implicit use/def of some portion of this
3527 variable. Implicit uses occur when we can't tell what part we
3528 are referencing, and have to make conservative assumptions. */
3530 /* True if the structure is only written to or taken its address. */
3534 /* An array of used_part structures, indexed by variable uid. */
3536 static htab_t used_portions;
3538 struct used_part_map
3544 /* Return true if the uid in the two used part maps are equal. */
3547 used_part_map_eq (const void *va, const void *vb)
3549 const struct used_part_map *a = (const struct used_part_map *) va;
3550 const struct used_part_map *b = (const struct used_part_map *) vb;
3551 return (a->uid == b->uid);
3554 /* Hash a from uid in a used_part_map. */
3557 used_part_map_hash (const void *item)
3559 return ((const struct used_part_map *)item)->uid;
3562 /* Free a used part map element. */
3565 free_used_part_map (void *item)
3567 free (((struct used_part_map *)item)->to);
3571 /* Lookup a used_part structure for a UID. */
3574 up_lookup (unsigned int uid)
3576 struct used_part_map *h, in;
3578 h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid);
3584 /* Insert the pair UID, TO into the used part hashtable. */
3587 up_insert (unsigned int uid, used_part_t to)
3589 struct used_part_map *h;
3592 h = XNEW (struct used_part_map);
3595 loc = htab_find_slot_with_hash (used_portions, h,
3599 *(struct used_part_map **) loc = h;
3603 /* Given a variable uid, UID, get or create the entry in the used portions
3604 table for the variable. */
3607 get_or_create_used_part_for (size_t uid)
3610 if ((up = up_lookup (uid)) == NULL)
3612 up = XCNEW (struct used_part);
3613 up->minused = INT_MAX;
3615 up->explicit_uses = false;
3616 up->implicit_uses = false;
3617 up->write_only = true;
3624 /* Create and return a structure sub-variable for field type FIELD at
3625 offset OFFSET, with size SIZE, of variable VAR. If ALIAS_SET not
3626 -1 this field is non-addressable and we should use this alias set
3630 create_sft (tree var, tree field, unsigned HOST_WIDE_INT offset,
3631 unsigned HOST_WIDE_INT size, alias_set_type alias_set)
3633 tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT");
3635 /* We need to copy the various flags from VAR to SUBVAR, so that
3636 they are is_global_var iff the original variable was. */
3637 DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
3638 MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var);
3639 TREE_PUBLIC (subvar) = TREE_PUBLIC (var);
3640 TREE_STATIC (subvar) = TREE_STATIC (var);
3641 TREE_READONLY (subvar) = TREE_READONLY (var);
3642 TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var);
3644 /* Add the new variable to REFERENCED_VARS. */
3645 set_symbol_mem_tag (subvar, NULL);
3646 add_referenced_var (subvar);
3647 SFT_PARENT_VAR (subvar) = var;
3648 SFT_OFFSET (subvar) = offset;
3649 SFT_SIZE (subvar) = size;
3650 SFT_ALIAS_SET (subvar) = alias_set;
3655 /* Given an aggregate VAR, create the subvariables that represent its
3659 create_overlap_variables_for (tree var)
3661 VEC(fieldoff_s,heap) *fieldstack = NULL;
3663 size_t uid = DECL_UID (var);
3665 up = up_lookup (uid);
3670 push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL,
3672 if (VEC_length (fieldoff_s, fieldstack) != 0)
3676 bool notokay = false;
3679 HOST_WIDE_INT lastfooffset = -1;
3680 HOST_WIDE_INT lastfosize = -1;
3681 tree lastfotype = NULL_TREE;
3683 /* Not all fields have DECL_SIZE set, and those that don't, we don't
3684 know their size, and thus, can't handle.
3685 The same is true of fields with DECL_SIZE that is not an integer
3686 constant (such as variable sized fields).
3687 Fields with offsets which are not constant will have an offset < 0
3688 We *could* handle fields that are constant sized arrays, but
3689 currently don't. Doing so would require some extra changes to
3690 tree-ssa-operands.c. */
3692 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
3695 || TREE_CODE (fo->size) != INTEGER_CST
3704 /* The current heuristic we use is as follows:
3705 If the variable has no used portions in this function, no
3706 structure vars are created for it.
3708 If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
3709 we always create structure vars for them.
3710 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3711 some explicit uses, we create structure vars for them.
3712 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3713 no explicit uses, we do not create structure vars for them.
3716 if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS
3717 && !up->explicit_uses)
3719 if (dump_file && (dump_flags & TDF_DETAILS))
3721 fprintf (dump_file, "Variable ");
3722 print_generic_expr (dump_file, var, 0);
3723 fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
3728 /* Bail out, if we can't create overlap variables. */
3731 VEC_free (fieldoff_s, heap, fieldstack);
3735 /* Otherwise, create the variables. */
3736 subvars = lookup_subvars_for_var (var);
3738 sort_fieldstack (fieldstack);
3740 for (i = VEC_length (fieldoff_s, fieldstack);
3741 VEC_iterate (fieldoff_s, fieldstack, --i, fo);)
3744 HOST_WIDE_INT fosize;
3747 fosize = TREE_INT_CST_LOW (fo->size);
3748 currfotype = fo->type;
3750 /* If this field isn't in the used portion,
3751 or it has the exact same offset and size as the last
3754 if (((fo->offset <= up->minused
3755 && fo->offset + fosize <= up->minused)
3756 || fo->offset >= up->maxused)
3757 || (fo->offset == lastfooffset
3758 && fosize == lastfosize
3759 && currfotype == lastfotype))
3761 sv = GGC_NEW (struct subvar);
3762 sv->next = *subvars;
3764 create_sft (var, fo->type, fo->offset, fosize, fo->alias_set);
3768 fprintf (dump_file, "structure field tag %s created for var %s",
3769 get_name (sv->var), get_name (var));
3770 fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
3771 SFT_OFFSET (sv->var));
3772 fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
3773 SFT_SIZE (sv->var));
3774 fprintf (dump_file, "\n");
3777 lastfotype = currfotype;
3778 lastfooffset = fo->offset;
3779 lastfosize = fosize;
3783 /* Once we have created subvars, the original is no longer call
3784 clobbered on its own. Its call clobbered status depends
3785 completely on the call clobbered status of the subvars.
3787 add_referenced_var in the above loop will take care of
3788 marking subvars of global variables as call clobbered for us
3789 to start, since they are global as well. */
3790 clear_call_clobbered (var);
3793 VEC_free (fieldoff_s, heap, fieldstack);
3797 /* Find the conservative answer to the question of what portions of what
3798 structures are used by this statement. We assume that if we have a
3799 component ref with a known size + offset, that we only need that part
3800 of the structure. For unknown cases, or cases where we do something
3801 to the whole structure, we assume we need to create fields for the
3802 entire structure. */
3805 find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p)
3807 switch (TREE_CODE (*tp))
3809 case GIMPLE_MODIFY_STMT:
3810 /* Recurse manually here to track whether the use is in the
3811 LHS of an assignment. */
3812 find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 0), walk_subtrees, tp);
3813 return find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 1),
3814 walk_subtrees, NULL);
3820 HOST_WIDE_INT bitsize;
3821 HOST_WIDE_INT bitmaxsize;
3822 HOST_WIDE_INT bitpos;
3824 ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize);
3826 && var_can_have_subvars (ref)
3827 && bitmaxsize != -1)
3829 size_t uid = DECL_UID (ref);
3832 up = get_or_create_used_part_for (uid);
3834 if (bitpos <= up->minused)
3835 up->minused = bitpos;
3836 if ((bitpos + bitmaxsize >= up->maxused))
3837 up->maxused = bitpos + bitmaxsize;
3839 if (bitsize == bitmaxsize)
3840 up->explicit_uses = true;
3842 up->implicit_uses = true;
3844 up->write_only = false;
3845 up_insert (uid, up);
3852 /* This is here to make sure we mark the entire base variable as used
3853 when you take its address. Because our used portion analysis is
3854 simple, we aren't looking at casts or pointer arithmetic to see what
3855 happens when you take the address. */
3858 tree var = get_base_address (TREE_OPERAND (*tp, 0));
3863 && var_can_have_subvars (var)
3864 && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3867 size_t uid = DECL_UID (var);
3869 up = get_or_create_used_part_for (uid);
3872 up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
3873 up->implicit_uses = true;
3875 up->write_only = false;
3877 up_insert (uid, up);
3886 int nargs = call_expr_nargs (*tp);
3887 for (i = 0; i < nargs; i++)
3889 tree *arg = &CALL_EXPR_ARG (*tp, i);
3890 if (TREE_CODE (*arg) != ADDR_EXPR)
3891 find_used_portions (arg, walk_subtrees, NULL);
3902 && var_can_have_subvars (var)
3903 && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3906 size_t uid = DECL_UID (var);
3908 up = get_or_create_used_part_for (uid);
3911 up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
3912 up->implicit_uses = true;
3914 up_insert (uid, up);
3928 /* Create structure field variables for structures used in this function. */
3931 create_structure_vars (void)
3934 safe_referenced_var_iterator rvi;
3935 VEC (tree, heap) *varvec = NULL;
3938 used_portions = htab_create (10, used_part_map_hash, used_part_map_eq,
3939 free_used_part_map);
3943 block_stmt_iterator bsi;
3944 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3946 walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
3951 FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi)
3953 /* The C++ FE creates vars without DECL_SIZE set, for some reason. */
3956 && var_can_have_subvars (var)
3958 && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3959 create_overlap_variables_for (var);
3961 htab_delete (used_portions);
3962 VEC_free (tree, heap, varvec);
3964 /* Update SSA operands of statements mentioning variables we split. */
3965 if (gimple_in_ssa_p (cfun))
3968 block_stmt_iterator bsi;
3969 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3971 tree stmt = bsi_stmt (bsi);
3972 bool update = false;
3976 if (STORED_SYMS (stmt))
3977 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
3979 tree sym = referenced_var_lookup (i);
3980 if (get_subvars_for_var (sym))
3987 if (LOADED_SYMS (stmt) && !update)
3988 EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
3990 tree sym = referenced_var_lookup (i);
3991 if (get_subvars_for_var (sym))
3998 if (stmt_ann (stmt)->addresses_taken && !update)
3999 EXECUTE_IF_SET_IN_BITMAP (stmt_ann (stmt)->addresses_taken,
4002 tree sym = referenced_var_lookup (i);
4003 if (get_subvars_for_var (sym))
4015 return TODO_rebuild_alias;
4019 gate_structure_vars (void)
4021 return flag_tree_salias != 0;
4024 struct tree_opt_pass pass_create_structure_vars =
4026 "salias", /* name */
4027 gate_structure_vars, /* gate */
4028 create_structure_vars, /* execute */
4031 0, /* static_pass_number */
4033 PROP_cfg, /* properties_required */
4034 0, /* properties_provided */
4035 0, /* properties_destroyed */
4036 0, /* todo_flags_start */
4037 TODO_dump_func, /* todo_flags_finish */
4041 /* Reset the call_clobbered flags on our referenced vars. In
4042 theory, this only needs to be done for globals. */
4045 reset_cc_flags (void)
4048 referenced_var_iterator rvi;
4050 FOR_EACH_REFERENCED_VAR (var, rvi)
4051 var_ann (var)->call_clobbered = false;
4055 struct tree_opt_pass pass_reset_cc_flags =
4059 reset_cc_flags, /* execute */
4062 0, /* static_pass_number */
4064 PROP_referenced_vars |PROP_cfg, /* properties_required */
4065 0, /* properties_provided */
4066 0, /* properties_destroyed */
4067 0, /* todo_flags_start */
4068 0, /* todo_flags_finish */