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 dump_alias_stats (FILE *);
200 static bool may_alias_p (tree, alias_set_type, tree, alias_set_type, bool);
201 static tree create_memory_tag (tree type, bool is_type_tag);
202 static tree get_smt_for (tree, struct alias_info *);
203 static tree get_nmt_for (tree);
204 static void add_may_alias (tree, tree);
205 static struct alias_info *init_alias_info (void);
206 static void delete_alias_info (struct alias_info *);
207 static void compute_flow_sensitive_aliasing (struct alias_info *);
208 static void setup_pointers_and_addressables (struct alias_info *);
209 static void create_global_var (void);
210 static void maybe_create_global_var (void);
211 static void set_pt_anything (tree);
213 void debug_mp_info (VEC(mem_sym_stats_t,heap) *);
215 static alloc_pool mem_sym_stats_pool;
217 /* Return memory reference stats for symbol VAR. Create a new slot in
218 cfun->gimple_df->mem_sym_stats if needed. */
220 static struct mem_sym_stats_d *
221 get_mem_sym_stats_for (tree var)
224 struct mem_sym_stats_d *stats;
225 struct pointer_map_t *map = gimple_mem_ref_stats (cfun)->mem_sym_stats;
229 slot = pointer_map_insert (map, var);
232 stats = pool_alloc (mem_sym_stats_pool);
233 memset (stats, 0, sizeof (*stats));
235 *slot = (void *) stats;
238 stats = (struct mem_sym_stats_d *) *slot;
244 /* Return memory reference statistics for variable VAR in function FN.
245 This is computed by alias analysis, but it is not kept
246 incrementally up-to-date. So, these stats are only accurate if
247 pass_may_alias has been run recently. If no alias information
248 exists, this function returns NULL. */
250 static mem_sym_stats_t
251 mem_sym_stats (struct function *fn, tree var)
254 struct pointer_map_t *stats_map = gimple_mem_ref_stats (fn)->mem_sym_stats;
256 if (stats_map == NULL)
259 slot = pointer_map_contains (stats_map, var);
263 return (mem_sym_stats_t) *slot;
267 /* Set MPT to be the memory partition associated with symbol SYM. */
270 set_memory_partition (tree sym, tree mpt)
272 #if defined ENABLE_CHECKING
274 gcc_assert (TREE_CODE (mpt) == MEMORY_PARTITION_TAG
275 && !is_gimple_reg (sym));
278 var_ann (sym)->mpt = mpt;
281 if (MPT_SYMBOLS (mpt) == NULL)
282 MPT_SYMBOLS (mpt) = BITMAP_ALLOC (&alias_bitmap_obstack);
284 bitmap_set_bit (MPT_SYMBOLS (mpt), DECL_UID (sym));
286 /* MPT inherits the call-clobbering attributes from SYM. */
287 if (is_call_clobbered (sym))
289 MTAG_GLOBAL (mpt) = 1;
290 mark_call_clobbered (mpt, ESCAPE_IS_GLOBAL);
296 /* Mark variable VAR as being non-addressable. */
299 mark_non_addressable (tree var)
303 if (!TREE_ADDRESSABLE (var))
306 mpt = memory_partition (var);
309 var_ann (var)->call_clobbered = false;
311 bitmap_clear_bit (gimple_call_clobbered_vars (cfun), DECL_UID (var));
312 TREE_ADDRESSABLE (var) = 0;
316 /* Note that it's possible for a symbol to have an associated
317 MPT and the MPT have a NULL empty set. During
318 init_alias_info, all MPTs get their sets cleared out, but the
319 symbols still point to the old MPTs that used to hold them.
320 This is done so that compute_memory_partitions can now which
321 symbols are losing or changing partitions and mark them for
323 if (MPT_SYMBOLS (mpt))
324 bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var));
325 set_memory_partition (var, NULL_TREE);
330 /* qsort comparison function to sort type/name tags by DECL_UID. */
333 sort_tags_by_id (const void *pa, const void *pb)
335 const_tree const a = *(const_tree const *)pa;
336 const_tree const b = *(const_tree const *)pb;
338 return DECL_UID (a) - DECL_UID (b);
341 /* Initialize WORKLIST to contain those memory tags that are marked call
342 clobbered. Initialized WORKLIST2 to contain the reasons these
343 memory tags escaped. */
346 init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
347 VEC (int, heap) **worklist2,
350 referenced_var_iterator rvi;
353 FOR_EACH_REFERENCED_VAR (curr, rvi)
355 if (MTAG_P (curr) && is_call_clobbered (curr))
357 VEC_safe_push (tree, heap, *worklist, curr);
358 VEC_safe_push (int, heap, *worklist2,
359 var_ann (curr)->escape_mask);
360 bitmap_set_bit (on_worklist, DECL_UID (curr));
365 /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
366 ALIAS is not already marked call clobbered, and is a memory
370 add_to_worklist (tree alias, VEC (tree, heap) **worklist,
371 VEC (int, heap) **worklist2, int reason,
374 if (MTAG_P (alias) && !is_call_clobbered (alias)
375 && !bitmap_bit_p (on_worklist, DECL_UID (alias)))
377 VEC_safe_push (tree, heap, *worklist, alias);
378 VEC_safe_push (int, heap, *worklist2, reason);
379 bitmap_set_bit (on_worklist, DECL_UID (alias));
383 /* Mark aliases of TAG as call clobbered, and place any tags on the
384 alias list that were not already call clobbered on WORKLIST. */
387 mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
388 VEC (int, heap) **worklist2, bitmap on_worklist)
394 var_ann_t ta = var_ann (tag);
398 aliases = may_aliases (tag);
402 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
404 entry = referenced_var (i);
405 /* If you clobber one part of a structure, you
406 clobber the entire thing. While this does not make
407 the world a particularly nice place, it is necessary
408 in order to allow C/C++ tricks that involve
409 pointer arithmetic to work. */
410 if (!unmodifiable_var_p (entry))
412 add_to_worklist (entry, worklist, worklist2, ta->escape_mask,
414 mark_call_clobbered (entry, ta->escape_mask);
419 /* Tags containing global vars need to be marked as global.
420 Tags containing call clobbered vars need to be marked as call
424 compute_tag_properties (void)
426 referenced_var_iterator rvi;
429 VEC (tree, heap) *taglist = NULL;
431 FOR_EACH_REFERENCED_VAR (tag, rvi)
435 VEC_safe_push (tree, heap, taglist, tag);
438 /* We sort the taglist by DECL_UID, for two reasons.
439 1. To get a sequential ordering to make the bitmap accesses
441 2. Because of the way we compute aliases, it's more likely that
442 an earlier tag is included in a later tag, and this will reduce
443 the number of iterations.
445 If we had a real tag graph, we would just topo-order it and be
447 qsort (VEC_address (tree, taglist),
448 VEC_length (tree, taglist),
452 /* Go through each tag not marked as global, and if it aliases
453 global vars, mark it global.
455 If the tag contains call clobbered vars, mark it call
458 This loop iterates because tags may appear in the may-aliases
459 list of other tags when we group. */
466 for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
472 bool tagcc = is_call_clobbered (tag);
473 bool tagglobal = MTAG_GLOBAL (tag);
475 if (tagcc && tagglobal)
478 ma = may_aliases (tag);
482 EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi)
484 entry = referenced_var (i);
485 /* Call clobbered entries cause the tag to be marked
487 if (!tagcc && is_call_clobbered (entry))
489 mark_call_clobbered (tag, var_ann (entry)->escape_mask);
494 /* Global vars cause the tag to be marked global. */
495 if (!tagglobal && is_global_var (entry))
497 MTAG_GLOBAL (tag) = true;
502 /* Early exit once both global and cc are set, since the
503 loop can't do any more than that. */
504 if (tagcc && tagglobal)
509 VEC_free (tree, heap, taglist);
512 /* Set up the initial variable clobbers and globalness.
513 When this function completes, only tags whose aliases need to be
514 clobbered will be set clobbered. Tags clobbered because they
515 contain call clobbered vars are handled in compute_tag_properties. */
518 set_initial_properties (struct alias_info *ai)
521 referenced_var_iterator rvi;
524 bool any_pt_anything = false;
525 enum escape_type pt_anything_mask = 0;
527 FOR_EACH_REFERENCED_VAR (var, rvi)
529 if (is_global_var (var))
531 if (!unmodifiable_var_p (var))
532 mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
534 else if (TREE_CODE (var) == PARM_DECL
535 && gimple_default_def (cfun, var)
536 && POINTER_TYPE_P (TREE_TYPE (var)))
538 tree def = gimple_default_def (cfun, var);
539 get_ptr_info (def)->value_escapes_p = 1;
540 get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
544 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
546 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
547 tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
549 /* A pointer that only escapes via a function return does not
550 add to the call clobber or call used solution.
551 To exclude ESCAPE_TO_PURE_CONST we would need to track
552 call used variables separately or compute those properly
553 in the operand scanner. */
554 if (pi->value_escapes_p
555 && pi->escape_mask & ~ESCAPE_TO_RETURN)
557 /* If PTR escapes then its associated memory tags and
558 pointed-to variables are call-clobbered. */
559 if (pi->name_mem_tag)
560 mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
563 mark_call_clobbered (tag, pi->escape_mask);
565 /* Defer to points-to analysis if possible, otherwise
566 clobber all addressable variables. Parameters cannot
567 point to local memory though.
568 ??? Properly tracking which pointers point to non-local
569 memory only would make a big difference here. */
570 if (!clobber_what_p_points_to (ptr)
571 && !(pi->escape_mask & ESCAPE_IS_PARM))
573 any_pt_anything = true;
574 pt_anything_mask |= pi->escape_mask;
578 /* If the name tag is call clobbered, so is the symbol tag
579 associated with the base VAR_DECL. */
582 && is_call_clobbered (pi->name_mem_tag))
583 mark_call_clobbered (tag, pi->escape_mask);
585 /* Name tags and symbol tags that we don't know where they point
586 to, might point to global memory, and thus, are clobbered.
588 FIXME: This is not quite right. They should only be
589 clobbered if value_escapes_p is true, regardless of whether
590 they point to global memory or not.
591 So removing this code and fixing all the bugs would be nice.
592 It is the cause of a bunch of clobbering. */
593 if ((pi->pt_global_mem || pi->pt_anything)
594 && pi->is_dereferenced && pi->name_mem_tag)
596 mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
597 MTAG_GLOBAL (pi->name_mem_tag) = true;
600 if ((pi->pt_global_mem || pi->pt_anything)
601 && pi->is_dereferenced
604 mark_call_clobbered (tag, ESCAPE_IS_GLOBAL);
605 MTAG_GLOBAL (tag) = true;
609 /* If a pt_anything pointer escaped we need to mark all addressable
610 variables call clobbered. */
616 EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, j, bi)
618 tree var = referenced_var (j);
619 if (!unmodifiable_var_p (var))
620 mark_call_clobbered (var, pt_anything_mask);
625 /* Compute which variables need to be marked call clobbered because
626 their tag is call clobbered, and which tags need to be marked
627 global because they contain global variables. */
630 compute_call_clobbered (struct alias_info *ai)
632 VEC (tree, heap) *worklist = NULL;
633 VEC (int,heap) *worklist2 = NULL;
636 timevar_push (TV_CALL_CLOBBER);
637 on_worklist = BITMAP_ALLOC (NULL);
639 set_initial_properties (ai);
640 init_transitive_clobber_worklist (&worklist, &worklist2, on_worklist);
641 while (VEC_length (tree, worklist) != 0)
643 tree curr = VEC_pop (tree, worklist);
644 int reason = VEC_pop (int, worklist2);
646 bitmap_clear_bit (on_worklist, DECL_UID (curr));
647 mark_call_clobbered (curr, reason);
648 mark_aliases_call_clobbered (curr, &worklist, &worklist2, on_worklist);
650 VEC_free (tree, heap, worklist);
651 VEC_free (int, heap, worklist2);
652 BITMAP_FREE (on_worklist);
653 compute_tag_properties ();
654 timevar_pop (TV_CALL_CLOBBER);
658 /* Dump memory partition information to FILE. */
661 dump_memory_partitions (FILE *file)
667 fprintf (file, "\nMemory partitions\n\n");
668 for (i = 0, npart = 0, nsyms = 0;
669 VEC_iterate (tree, gimple_ssa_operands (cfun)->mpt_table, i, mpt);
674 bitmap syms = MPT_SYMBOLS (mpt);
675 unsigned long n = (syms) ? bitmap_count_bits (syms) : 0;
677 fprintf (file, "#%u: ", i);
678 print_generic_expr (file, mpt, 0);
679 fprintf (file, ": %lu elements: ", n);
680 dump_decl_set (file, syms);
686 fprintf (file, "\n%u memory partitions holding %lu symbols\n", npart, nsyms);
690 /* Dump memory partition information to stderr. */
693 debug_memory_partitions (void)
695 dump_memory_partitions (stderr);
699 /* Return true if memory partitioning is required given the memory
700 reference estimates in STATS. */
703 need_to_partition_p (struct mem_ref_stats_d *stats)
705 long num_vops = stats->num_vuses + stats->num_vdefs;
706 long avg_vops = CEIL (num_vops, stats->num_mem_stmts);
707 return (num_vops > (long) MAX_ALIASED_VOPS
708 && avg_vops > (long) AVG_ALIASED_VOPS);
712 /* Count the actual number of virtual operators in CFUN. Note that
713 this is only meaningful after virtual operands have been populated,
714 so it should be invoked at the end of compute_may_aliases.
716 The number of virtual operators are stored in *NUM_VDEFS_P and
717 *NUM_VUSES_P, the number of partitioned symbols in
718 *NUM_PARTITIONED_P and the number of unpartitioned symbols in
719 *NUM_UNPARTITIONED_P.
721 If any of these pointers is NULL the corresponding count is not
725 count_mem_refs (long *num_vuses_p, long *num_vdefs_p,
726 long *num_partitioned_p, long *num_unpartitioned_p)
728 block_stmt_iterator bsi;
730 long num_vdefs, num_vuses, num_partitioned, num_unpartitioned;
731 referenced_var_iterator rvi;
734 num_vuses = num_vdefs = num_partitioned = num_unpartitioned = 0;
736 if (num_vuses_p || num_vdefs_p)
738 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
740 tree stmt = bsi_stmt (bsi);
741 if (stmt_references_memory_p (stmt))
743 num_vuses += NUM_SSA_OPERANDS (stmt, SSA_OP_VUSE);
744 num_vdefs += NUM_SSA_OPERANDS (stmt, SSA_OP_VDEF);
748 if (num_partitioned_p || num_unpartitioned_p)
749 FOR_EACH_REFERENCED_VAR (sym, rvi)
751 if (is_gimple_reg (sym))
754 if (memory_partition (sym))
761 *num_vdefs_p = num_vdefs;
764 *num_vuses_p = num_vuses;
766 if (num_partitioned_p)
767 *num_partitioned_p = num_partitioned;
769 if (num_unpartitioned_p)
770 *num_unpartitioned_p = num_unpartitioned;
774 /* The list is sorted by increasing partitioning score (PSCORE).
775 This score is computed such that symbols with high scores are
776 those that are least likely to be partitioned. Given a symbol
777 MP->VAR, PSCORE(S) is the result of the following weighted sum
779 PSCORE(S) = FW * 64 + FR * 32
786 FW Execution frequency of writes to S
787 FR Execution frequency of reads from S
788 DW Number of direct writes to S
789 DR Number of direct reads from S
790 IW Number of indirect writes to S
791 IR Number of indirect reads from S
792 NO_ALIAS State of the NO_ALIAS* flags
794 The basic idea here is that symbols that are frequently
795 written-to in hot paths of the code are the last to be considered
799 mem_sym_score (mem_sym_stats_t mp)
801 return mp->frequency_writes * 64 + mp->frequency_reads * 32
802 + mp->num_direct_writes * 16 + mp->num_direct_reads * 8
803 + mp->num_indirect_writes * 4 + mp->num_indirect_reads * 2
804 + var_ann (mp->var)->noalias_state;
808 /* Dump memory reference stats for function CFUN to FILE. */
811 dump_mem_ref_stats (FILE *file)
813 long actual_num_vuses, actual_num_vdefs;
814 long num_partitioned, num_unpartitioned;
815 struct mem_ref_stats_d *stats;
817 stats = gimple_mem_ref_stats (cfun);
819 count_mem_refs (&actual_num_vuses, &actual_num_vdefs, &num_partitioned,
822 fprintf (file, "\nMemory reference statistics for %s\n\n",
823 lang_hooks.decl_printable_name (current_function_decl, 2));
825 fprintf (file, "Number of memory statements: %ld\n",
826 stats->num_mem_stmts);
827 fprintf (file, "Number of call sites: %ld\n",
828 stats->num_call_sites);
829 fprintf (file, "Number of pure/const call sites: %ld\n",
830 stats->num_pure_const_call_sites);
831 fprintf (file, "Number of asm sites: %ld\n",
832 stats->num_asm_sites);
833 fprintf (file, "Estimated number of loads: %ld (%ld/stmt)\n",
835 (stats->num_mem_stmts)
836 ? CEIL (stats->num_vuses, stats->num_mem_stmts)
838 fprintf (file, "Actual number of loads: %ld (%ld/stmt)\n",
840 (stats->num_mem_stmts)
841 ? CEIL (actual_num_vuses, stats->num_mem_stmts)
844 if (actual_num_vuses > stats->num_vuses + (stats->num_vuses / 25))
845 fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
847 fprintf (file, "Estimated number of stores: %ld (%ld/stmt)\n",
849 (stats->num_mem_stmts)
850 ? CEIL (stats->num_vdefs, stats->num_mem_stmts)
852 fprintf (file, "Actual number of stores: %ld (%ld/stmt)\n",
854 (stats->num_mem_stmts)
855 ? CEIL (actual_num_vdefs, stats->num_mem_stmts)
858 if (actual_num_vdefs > stats->num_vdefs + (stats->num_vdefs / 25))
859 fprintf (file, "\t(warning: estimation is lower by more than 25%%)\n");
861 fprintf (file, "Partitioning thresholds: MAX = %d AVG = %d "
862 "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS, AVG_ALIASED_VOPS,
863 stats->num_mem_stmts && need_to_partition_p (stats) ? "" : "NO ");
864 fprintf (file, "Number of partitioned symbols: %ld\n", num_partitioned);
865 fprintf (file, "Number of unpartitioned symbols: %ld\n", num_unpartitioned);
869 /* Dump memory reference stats for function FN to stderr. */
872 debug_mem_ref_stats (void)
874 dump_mem_ref_stats (stderr);
878 /* Dump memory reference stats for variable VAR to FILE. */
881 dump_mem_sym_stats (FILE *file, tree var)
883 mem_sym_stats_t stats = mem_sym_stats (cfun, var);
888 fprintf (file, "read frequency: %6ld, write frequency: %6ld, "
889 "direct reads: %3ld, direct writes: %3ld, "
890 "indirect reads: %4ld, indirect writes: %4ld, symbol: ",
891 stats->frequency_reads, stats->frequency_writes,
892 stats->num_direct_reads, stats->num_direct_writes,
893 stats->num_indirect_reads, stats->num_indirect_writes);
894 print_generic_expr (file, stats->var, 0);
895 fprintf (file, ", tags: ");
896 dump_decl_set (file, stats->parent_tags);
900 /* Dump memory reference stats for variable VAR to stderr. */
903 debug_mem_sym_stats (tree var)
905 dump_mem_sym_stats (stderr, var);
908 /* Dump memory reference stats for variable VAR to FILE. For use
909 of tree-dfa.c:dump_variable. */
912 dump_mem_sym_stats_for_var (FILE *file, tree var)
914 mem_sym_stats_t stats = mem_sym_stats (cfun, var);
919 fprintf (file, ", score: %ld", mem_sym_score (stats));
920 fprintf (file, ", direct reads: %ld", stats->num_direct_reads);
921 fprintf (file, ", direct writes: %ld", stats->num_direct_writes);
922 fprintf (file, ", indirect reads: %ld", stats->num_indirect_reads);
923 fprintf (file, ", indirect writes: %ld", stats->num_indirect_writes);
926 /* Dump memory reference stats for all memory symbols to FILE. */
929 dump_all_mem_sym_stats (FILE *file)
931 referenced_var_iterator rvi;
934 FOR_EACH_REFERENCED_VAR (sym, rvi)
936 if (is_gimple_reg (sym))
939 dump_mem_sym_stats (file, sym);
944 /* Dump memory reference stats for all memory symbols to stderr. */
947 debug_all_mem_sym_stats (void)
949 dump_all_mem_sym_stats (stderr);
953 /* Dump the MP_INFO array to FILE. */
956 dump_mp_info (FILE *file, VEC(mem_sym_stats_t,heap) *mp_info)
959 mem_sym_stats_t mp_p;
961 for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
962 if (!mp_p->partitioned_p)
963 dump_mem_sym_stats (file, mp_p->var);
967 /* Dump the MP_INFO array to stderr. */
970 debug_mp_info (VEC(mem_sym_stats_t,heap) *mp_info)
972 dump_mp_info (stderr, mp_info);
976 /* Update memory reference stats for symbol VAR in statement STMT.
977 NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times
978 that VAR is read/written in STMT (indirect reads/writes are not
979 recorded by this function, see compute_memory_partitions). */
982 update_mem_sym_stats_from_stmt (tree var, tree stmt, long num_direct_reads,
983 long num_direct_writes)
985 mem_sym_stats_t stats;
987 gcc_assert (num_direct_reads >= 0 && num_direct_writes >= 0);
989 stats = get_mem_sym_stats_for (var);
991 stats->num_direct_reads += num_direct_reads;
992 stats->frequency_reads += ((long) bb_for_stmt (stmt)->frequency
995 stats->num_direct_writes += num_direct_writes;
996 stats->frequency_writes += ((long) bb_for_stmt (stmt)->frequency
997 * num_direct_writes);
1001 /* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should
1002 be partitioned before MP2->VAR, 0 if they are the same or 1 if
1003 MP1->VAR should be partitioned after MP2->VAR. */
1006 compare_mp_info_entries (mem_sym_stats_t mp1, mem_sym_stats_t mp2)
1008 long pscore1 = mem_sym_score (mp1);
1009 long pscore2 = mem_sym_score (mp2);
1011 if (pscore1 < pscore2)
1013 else if (pscore1 > pscore2)
1016 return DECL_UID (mp1->var) - DECL_UID (mp2->var);
1020 /* Comparison routine for qsort. The list is sorted by increasing
1021 partitioning score (PSCORE). This score is computed such that
1022 symbols with high scores are those that are least likely to be
1026 mp_info_cmp (const void *p, const void *q)
1028 mem_sym_stats_t e1 = *((const mem_sym_stats_t *) p);
1029 mem_sym_stats_t e2 = *((const mem_sym_stats_t *) q);
1030 return compare_mp_info_entries (e1, e2);
1034 /* Sort the array of reference counts used to compute memory partitions.
1035 Elements are sorted in ascending order of execution frequency and
1036 descending order of virtual operators needed. */
1039 sort_mp_info (VEC(mem_sym_stats_t,heap) *list)
1041 unsigned num = VEC_length (mem_sym_stats_t, list);
1048 if (compare_mp_info_entries (VEC_index (mem_sym_stats_t, list, 0),
1049 VEC_index (mem_sym_stats_t, list, 1)) > 0)
1051 /* Swap elements if they are in the wrong order. */
1052 mem_sym_stats_t tmp = VEC_index (mem_sym_stats_t, list, 0);
1053 VEC_replace (mem_sym_stats_t, list, 0,
1054 VEC_index (mem_sym_stats_t, list, 1));
1055 VEC_replace (mem_sym_stats_t, list, 1, tmp);
1061 /* There are 3 or more elements, call qsort. */
1062 qsort (VEC_address (mem_sym_stats_t, list),
1063 VEC_length (mem_sym_stats_t, list),
1064 sizeof (mem_sym_stats_t),
1069 /* Return the memory partition tag (MPT) associated with memory
1073 get_mpt_for (tree sym)
1077 /* Don't create a new tag unnecessarily. */
1078 mpt = memory_partition (sym);
1079 if (mpt == NULL_TREE)
1081 mpt = create_tag_raw (MEMORY_PARTITION_TAG, TREE_TYPE (sym), "MPT");
1082 TREE_ADDRESSABLE (mpt) = 0;
1083 add_referenced_var (mpt);
1084 VEC_safe_push (tree, heap, gimple_ssa_operands (cfun)->mpt_table, mpt);
1085 gcc_assert (MPT_SYMBOLS (mpt) == NULL);
1086 set_memory_partition (sym, mpt);
1093 /* Add MP_P->VAR to a memory partition and return the partition. */
1096 find_partition_for (mem_sym_stats_t mp_p)
1099 VEC(tree,heap) *mpt_table;
1102 mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1105 /* Find an existing partition for MP_P->VAR. */
1106 for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
1108 mem_sym_stats_t mpt_stats;
1110 /* If MPT does not have any symbols yet, use it. */
1111 if (MPT_SYMBOLS (mpt) == NULL)
1114 /* Otherwise, see if MPT has common parent tags with MP_P->VAR,
1115 but avoid grouping clobbered variables with non-clobbered
1116 variables (otherwise, this tends to creates a single memory
1117 partition because other call-clobbered variables may have
1118 common parent tags with non-clobbered ones). */
1119 mpt_stats = get_mem_sym_stats_for (mpt);
1120 if (mp_p->parent_tags
1121 && mpt_stats->parent_tags
1122 && is_call_clobbered (mpt) == is_call_clobbered (mp_p->var)
1123 && bitmap_intersect_p (mpt_stats->parent_tags, mp_p->parent_tags))
1126 /* If no common parent tags are found, see if both MPT and
1127 MP_P->VAR are call-clobbered. */
1128 if (is_call_clobbered (mpt) && is_call_clobbered (mp_p->var))
1132 if (mpt == NULL_TREE)
1133 mpt = get_mpt_for (mp_p->var);
1135 set_memory_partition (mp_p->var, mpt);
1137 mp_p->partitioned_p = true;
1139 mark_sym_for_renaming (mp_p->var);
1140 mark_sym_for_renaming (mpt);
1146 /* Rewrite the alias set for TAG to use the newly created partitions.
1147 If TAG is NULL, rewrite the set of call-clobbered variables.
1148 NEW_ALIASES is a scratch bitmap to build the new set of aliases for
1152 rewrite_alias_set_for (tree tag, bitmap new_aliases)
1158 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
1160 sym = referenced_var (i);
1161 mpt = memory_partition (sym);
1163 bitmap_set_bit (new_aliases, DECL_UID (mpt));
1165 bitmap_set_bit (new_aliases, DECL_UID (sym));
1168 /* Rebuild the may-alias array for TAG. */
1169 bitmap_copy (MTAG_ALIASES (tag), new_aliases);
1173 /* Determine how many virtual operands can be saved by partitioning
1174 MP_P->VAR into MPT. When a symbol S is thrown inside a partition
1175 P, every virtual operand that used to reference S will now
1176 reference P. Whether it reduces the number of virtual operands
1179 1- Direct references to S are never saved. Instead of the virtual
1180 operand to S, we will now have a virtual operand to P.
1182 2- Indirect references to S are reduced only for those memory tags
1183 holding S that already had other symbols partitioned into P.
1184 For instance, if a memory tag T has the alias set { a b S c },
1185 the first time we partition S into P, the alias set will become
1186 { a b P c }, so no virtual operands will be saved. However, if
1187 we now partition symbol 'c' into P, then the alias set for T
1188 will become { a b P }, so we will be saving one virtual operand
1189 for every indirect reference to 'c'.
1191 3- Is S is call-clobbered, we save as many virtual operands as
1192 call/asm sites exist in the code, but only if other
1193 call-clobbered symbols have been grouped into P. The first
1194 call-clobbered symbol that we group does not produce any
1197 MEM_REF_STATS points to CFUN's memory reference information. */
1200 estimate_vop_reduction (struct mem_ref_stats_d *mem_ref_stats,
1201 mem_sym_stats_t mp_p, tree mpt)
1205 mem_sym_stats_t mpt_stats;
1207 /* We should only get symbols with indirect references here. */
1208 gcc_assert (mp_p->num_indirect_reads > 0 || mp_p->num_indirect_writes > 0);
1210 /* Note that the only statistics we keep for MPT is the set of
1211 parent tags to know which memory tags have had alias members
1212 partitioned, and the indicator has_call_clobbered_vars.
1213 Reference counts are not important for MPT. */
1214 mpt_stats = get_mem_sym_stats_for (mpt);
1216 /* Traverse all the parent tags for MP_P->VAR. For every tag T, if
1217 partition P is already grouping aliases of T, then reduce the
1218 number of virtual operands by the number of direct references
1220 if (mp_p->parent_tags)
1222 if (mpt_stats->parent_tags == NULL)
1223 mpt_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1225 EXECUTE_IF_SET_IN_BITMAP (mp_p->parent_tags, 0, i, bi)
1227 if (bitmap_bit_p (mpt_stats->parent_tags, i))
1229 /* Partition MPT is already partitioning symbols in the
1230 alias set for TAG. This means that we are now saving
1231 1 virtual operand for every direct reference to TAG. */
1232 tree tag = referenced_var (i);
1233 mem_sym_stats_t tag_stats = mem_sym_stats (cfun, tag);
1234 mem_ref_stats->num_vuses -= tag_stats->num_direct_reads;
1235 mem_ref_stats->num_vdefs -= tag_stats->num_direct_writes;
1239 /* This is the first symbol in tag I's alias set that is
1240 being grouped under MPT. We will not save any
1241 virtual operands this time, but record that MPT is
1242 grouping a symbol from TAG's alias set so that the
1243 next time we get the savings. */
1244 bitmap_set_bit (mpt_stats->parent_tags, i);
1249 /* If MP_P->VAR is call-clobbered, and MPT is already grouping
1250 call-clobbered symbols, then we will save as many virtual
1251 operands as asm/call sites there are. */
1252 if (is_call_clobbered (mp_p->var))
1254 if (mpt_stats->has_call_clobbered_vars)
1255 mem_ref_stats->num_vdefs -= mem_ref_stats->num_call_sites
1256 + mem_ref_stats->num_asm_sites;
1258 mpt_stats->has_call_clobbered_vars = true;
1263 /* Helper for compute_memory_partitions. Transfer reference counts
1264 from pointers to their pointed-to sets. Counters for pointers were
1265 computed by update_alias_info. MEM_REF_STATS points to CFUN's
1266 memory reference information. */
1269 update_reference_counts (struct mem_ref_stats_d *mem_ref_stats)
1273 mem_sym_stats_t sym_stats;
1275 for (i = 1; i < num_ssa_names; i++)
1278 struct ptr_info_def *pi;
1282 && POINTER_TYPE_P (TREE_TYPE (ptr))
1283 && (pi = SSA_NAME_PTR_INFO (ptr)) != NULL
1284 && pi->is_dereferenced)
1289 mem_sym_stats_t ptr_stats, tag_stats;
1291 /* If PTR has flow-sensitive points-to information, use
1292 PTR's name tag, otherwise use the symbol tag associated
1293 with PTR's symbol. */
1294 if (pi->name_mem_tag)
1295 tag = pi->name_mem_tag;
1297 tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
1299 ptr_stats = get_mem_sym_stats_for (ptr);
1300 tag_stats = get_mem_sym_stats_for (tag);
1302 /* TAG has as many direct references as dereferences we
1303 found for its parent pointer. */
1304 tag_stats->num_direct_reads += ptr_stats->num_direct_reads;
1305 tag_stats->num_direct_writes += ptr_stats->num_direct_writes;
1307 /* All the dereferences of pointer PTR are considered direct
1308 references to PTR's memory tag (TAG). In turn,
1309 references to TAG will become virtual operands for every
1310 symbol in TAG's alias set. So, for every symbol ALIAS in
1311 TAG's alias set, add as many indirect references to ALIAS
1312 as direct references there are for TAG. */
1313 if (MTAG_ALIASES (tag))
1314 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, j, bj)
1316 tree alias = referenced_var (j);
1317 sym_stats = get_mem_sym_stats_for (alias);
1319 /* All the direct references to TAG are indirect references
1321 sym_stats->num_indirect_reads += ptr_stats->num_direct_reads;
1322 sym_stats->num_indirect_writes += ptr_stats->num_direct_writes;
1323 sym_stats->frequency_reads += ptr_stats->frequency_reads;
1324 sym_stats->frequency_writes += ptr_stats->frequency_writes;
1326 /* Indicate that TAG is one of ALIAS's parent tags. */
1327 if (sym_stats->parent_tags == NULL)
1328 sym_stats->parent_tags = BITMAP_ALLOC (&alias_bitmap_obstack);
1329 bitmap_set_bit (sym_stats->parent_tags, DECL_UID (tag));
1334 /* Call-clobbered symbols are indirectly written at every
1336 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
1338 tree sym = referenced_var (i);
1339 sym_stats = get_mem_sym_stats_for (sym);
1340 sym_stats->num_indirect_writes += mem_ref_stats->num_call_sites
1341 + mem_ref_stats->num_asm_sites;
1344 /* Addressable symbols are indirectly written at some ASM sites.
1345 Since only ASM sites that clobber memory actually affect
1346 addressable symbols, this is an over-estimation. */
1347 EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun), 0, i, bi)
1349 tree sym = referenced_var (i);
1350 sym_stats = get_mem_sym_stats_for (sym);
1351 sym_stats->num_indirect_writes += mem_ref_stats->num_asm_sites;
1356 /* Helper for compute_memory_partitions. Add all memory symbols to
1357 *MP_INFO_P and compute the initial estimate for the total number of
1358 virtual operands needed. MEM_REF_STATS points to CFUN's memory
1359 reference information. On exit, *TAGS_P will contain the list of
1360 memory tags whose alias set need to be rewritten after
1364 build_mp_info (struct mem_ref_stats_d *mem_ref_stats,
1365 VEC(mem_sym_stats_t,heap) **mp_info_p,
1366 VEC(tree,heap) **tags_p)
1369 referenced_var_iterator rvi;
1371 FOR_EACH_REFERENCED_VAR (var, rvi)
1373 mem_sym_stats_t sym_stats;
1376 /* We are only interested in memory symbols other than MPTs. */
1377 if (is_gimple_reg (var) || TREE_CODE (var) == MEMORY_PARTITION_TAG)
1380 /* Collect memory tags into the TAGS array so that we can
1381 rewrite their alias sets after partitioning. */
1382 if (MTAG_P (var) && MTAG_ALIASES (var))
1383 VEC_safe_push (tree, heap, *tags_p, var);
1385 /* Since we are going to re-compute partitions, any symbols that
1386 used to belong to a partition must be detached from it and
1387 marked for renaming. */
1388 if ((old_mpt = memory_partition (var)) != NULL)
1390 mark_sym_for_renaming (old_mpt);
1391 set_memory_partition (var, NULL_TREE);
1392 mark_sym_for_renaming (var);
1395 sym_stats = get_mem_sym_stats_for (var);
1397 /* Add VAR's reference info to MP_INFO. Note that the only
1398 symbols that make sense to partition are those that have
1399 indirect references. If a symbol S is always directly
1400 referenced, partitioning it will not reduce the number of
1401 virtual operators. The only symbols that are profitable to
1402 partition are those that belong to alias sets and/or are
1404 if (sym_stats->num_indirect_reads > 0
1405 || sym_stats->num_indirect_writes > 0)
1406 VEC_safe_push (mem_sym_stats_t, heap, *mp_info_p, sym_stats);
1408 /* Update the number of estimated VOPS. Note that direct
1409 references to memory tags are always counted as indirect
1410 references to their alias set members, so if a memory tag has
1411 aliases, do not count its direct references to avoid double
1413 if (!MTAG_P (var) || !MTAG_ALIASES (var))
1415 mem_ref_stats->num_vuses += sym_stats->num_direct_reads;
1416 mem_ref_stats->num_vdefs += sym_stats->num_direct_writes;
1419 mem_ref_stats->num_vuses += sym_stats->num_indirect_reads;
1420 mem_ref_stats->num_vdefs += sym_stats->num_indirect_writes;
1425 /* Compute memory partitions. A memory partition (MPT) is an
1426 arbitrary grouping of memory symbols, such that references to one
1427 member of the group is considered a reference to all the members of
1430 As opposed to alias sets in memory tags, the grouping into
1431 partitions is completely arbitrary and only done to reduce the
1432 number of virtual operands. The only rule that needs to be
1433 observed when creating memory partitions is that given two memory
1434 partitions MPT.i and MPT.j, they must not contain symbols in
1437 Memory partitions are used when putting the program into Memory-SSA
1438 form. In particular, in Memory-SSA PHI nodes are not computed for
1439 individual memory symbols. They are computed for memory
1440 partitions. This reduces the amount of PHI nodes in the SSA graph
1441 at the expense of precision (i.e., it makes unrelated stores affect
1444 However, it is possible to increase precision by changing this
1445 partitioning scheme. For instance, if the partitioning scheme is
1446 such that get_mpt_for is the identity function (that is,
1447 get_mpt_for (s) = s), this will result in ultimate precision at the
1448 expense of huge SSA webs.
1450 At the other extreme, a partitioning scheme that groups all the
1451 symbols in the same set results in minimal SSA webs and almost
1452 total loss of precision.
1454 There partitioning heuristic uses three parameters to decide the
1455 order in which symbols are processed. The list of symbols is
1456 sorted so that symbols that are more likely to be partitioned are
1457 near the top of the list:
1459 - Execution frequency. If a memory references is in a frequently
1460 executed code path, grouping it into a partition may block useful
1461 transformations and cause sub-optimal code generation. So, the
1462 partition heuristic tries to avoid grouping symbols with high
1463 execution frequency scores. Execution frequency is taken
1464 directly from the basic blocks where every reference is made (see
1465 update_mem_sym_stats_from_stmt), which in turn uses the
1466 profile guided machinery, so if the program is compiled with PGO
1467 enabled, more accurate partitioning decisions will be made.
1469 - Number of references. Symbols with few references in the code,
1470 are partitioned before symbols with many references.
1472 - NO_ALIAS attributes. Symbols with any of the NO_ALIAS*
1473 attributes are partitioned after symbols marked MAY_ALIAS.
1475 Once the list is sorted, the partitioning proceeds as follows:
1477 1- For every symbol S in MP_INFO, create a new memory partition MP,
1478 if necessary. To avoid memory partitions that contain symbols
1479 from non-conflicting alias sets, memory partitions are
1480 associated to the memory tag that holds S in its alias set. So,
1481 when looking for a memory partition for S, the memory partition
1482 associated with one of the memory tags holding S is chosen. If
1483 none exists, a new one is created.
1485 2- Add S to memory partition MP.
1487 3- Reduce by 1 the number of VOPS for every memory tag holding S.
1489 4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the
1490 average number of VOPS per statement is less than
1491 AVG_ALIASED_VOPS, stop. Otherwise, go to the next symbol in the
1495 compute_memory_partitions (void)
1499 mem_sym_stats_t mp_p;
1500 VEC(mem_sym_stats_t,heap) *mp_info;
1502 VEC(tree,heap) *tags;
1503 struct mem_ref_stats_d *mem_ref_stats;
1504 int prev_max_aliased_vops;
1506 mem_ref_stats = gimple_mem_ref_stats (cfun);
1507 gcc_assert (mem_ref_stats->num_vuses == 0 && mem_ref_stats->num_vdefs == 0);
1509 if (mem_ref_stats->num_mem_stmts == 0)
1512 timevar_push (TV_MEMORY_PARTITIONING);
1516 prev_max_aliased_vops = MAX_ALIASED_VOPS;
1518 /* Since we clearly cannot lower the number of virtual operators
1519 below the total number of memory statements in the function, we
1520 may need to adjust MAX_ALIASED_VOPS beforehand. */
1521 if (MAX_ALIASED_VOPS < mem_ref_stats->num_mem_stmts)
1522 MAX_ALIASED_VOPS = mem_ref_stats->num_mem_stmts;
1524 /* Update reference stats for all the pointed-to variables and
1526 update_reference_counts (mem_ref_stats);
1528 /* Add all the memory symbols to MP_INFO. */
1529 build_mp_info (mem_ref_stats, &mp_info, &tags);
1531 /* No partitions required if we are below the threshold. */
1532 if (!need_to_partition_p (mem_ref_stats))
1535 fprintf (dump_file, "\nMemory partitioning NOT NEEDED for %s\n",
1536 get_name (current_function_decl));
1540 /* Sort the MP_INFO array so that symbols that should be partitioned
1541 first are near the top of the list. */
1542 sort_mp_info (mp_info);
1546 fprintf (dump_file, "\nMemory partitioning NEEDED for %s\n\n",
1547 get_name (current_function_decl));
1548 fprintf (dump_file, "Memory symbol references before partitioning:\n");
1549 dump_mp_info (dump_file, mp_info);
1552 /* Create partitions for variables in MP_INFO until we have enough
1553 to lower the total number of VOPS below MAX_ALIASED_VOPS or if
1554 the average number of VOPS per statement is below
1555 AVG_ALIASED_VOPS. */
1556 for (i = 0; VEC_iterate (mem_sym_stats_t, mp_info, i, mp_p); i++)
1560 /* If we are below the threshold, stop. */
1561 if (!need_to_partition_p (mem_ref_stats))
1564 mpt = find_partition_for (mp_p);
1565 estimate_vop_reduction (mem_ref_stats, mp_p, mpt);
1568 /* After partitions have been created, rewrite alias sets to use
1569 them instead of the original symbols. This way, if the alias set
1570 was computed as { a b c d e f }, and the subset { b e f } was
1571 grouped into partition MPT.3, then the new alias set for the tag
1572 will be { a c d MPT.3 }.
1574 Note that this is not strictly necessary. The operand scanner
1575 will always check if a symbol belongs to a partition when adding
1576 virtual operands. However, by reducing the size of the alias
1577 sets to be scanned, the work needed inside the operand scanner is
1578 significantly reduced. */
1579 new_aliases = BITMAP_ALLOC (&alias_bitmap_obstack);
1581 for (i = 0; VEC_iterate (tree, tags, i, tag); i++)
1583 rewrite_alias_set_for (tag, new_aliases);
1584 bitmap_clear (new_aliases);
1587 BITMAP_FREE (new_aliases);
1591 fprintf (dump_file, "\nMemory symbol references after partitioning:\n");
1592 dump_mp_info (dump_file, mp_info);
1596 /* Free allocated memory. */
1597 VEC_free (mem_sym_stats_t, heap, mp_info);
1598 VEC_free (tree, heap, tags);
1600 MAX_ALIASED_VOPS = prev_max_aliased_vops;
1602 timevar_pop (TV_MEMORY_PARTITIONING);
1606 /* Compute may-alias information for every variable referenced in function
1609 Alias analysis proceeds in 3 main phases:
1611 1- Points-to and escape analysis.
1613 This phase walks the use-def chains in the SSA web looking for three
1616 * Assignments of the form P_i = &VAR
1617 * Assignments of the form P_i = malloc()
1618 * Pointers and ADDR_EXPR that escape the current function.
1620 The concept of 'escaping' is the same one used in the Java world. When
1621 a pointer or an ADDR_EXPR escapes, it means that it has been exposed
1622 outside of the current function. So, assignment to global variables,
1623 function arguments and returning a pointer are all escape sites, as are
1624 conversions between pointers and integers.
1626 This is where we are currently limited. Since not everything is renamed
1627 into SSA, we lose track of escape properties when a pointer is stashed
1628 inside a field in a structure, for instance. In those cases, we are
1629 assuming that the pointer does escape.
1631 We use escape analysis to determine whether a variable is
1632 call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable
1633 is call-clobbered. If a pointer P_i escapes, then all the variables
1634 pointed-to by P_i (and its memory tag) also escape.
1636 2- Compute flow-sensitive aliases
1638 We have two classes of memory tags. Memory tags associated with the
1639 pointed-to data type of the pointers in the program. These tags are
1640 called "symbol memory tag" (SMT). The other class are those associated
1641 with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
1642 when adding operands for an INDIRECT_REF *P_i, we will first check
1643 whether P_i has a name tag, if it does we use it, because that will have
1644 more precise aliasing information. Otherwise, we use the standard symbol
1647 In this phase, we go through all the pointers we found in points-to
1648 analysis and create alias sets for the name memory tags associated with
1649 each pointer P_i. If P_i escapes, we mark call-clobbered the variables
1650 it points to and its tag.
1653 3- Compute flow-insensitive aliases
1655 This pass will compare the alias set of every symbol memory tag and
1656 every addressable variable found in the program. Given a symbol
1657 memory tag SMT and an addressable variable V. If the alias sets of
1658 SMT and V conflict (as computed by may_alias_p), then V is marked
1659 as an alias tag and added to the alias set of SMT.
1661 For instance, consider the following function:
1677 After aliasing analysis has finished, the symbol memory tag for pointer
1678 'p' will have two aliases, namely variables 'a' and 'b'. Every time
1679 pointer 'p' is dereferenced, we want to mark the operation as a
1680 potential reference to 'a' and 'b'.
1690 # p_1 = PHI <p_4(1), p_6(2)>;
1705 In certain cases, the list of may aliases for a pointer may grow too
1706 large. This may cause an explosion in the number of virtual operands
1707 inserted in the code. Resulting in increased memory consumption and
1710 When the number of virtual operands needed to represent aliased
1711 loads and stores grows too large (configurable with option --param
1712 max-aliased-vops and --param avg-aliased-vops), alias sets are
1713 grouped to avoid severe compile-time slow downs and memory
1714 consumption. See compute_memory_partitions. */
1717 compute_may_aliases (void)
1719 struct alias_info *ai;
1721 timevar_push (TV_TREE_MAY_ALIAS);
1723 memset (&alias_stats, 0, sizeof (alias_stats));
1725 /* Initialize aliasing information. */
1726 ai = init_alias_info ();
1728 /* For each pointer P_i, determine the sets of variables that P_i may
1729 point-to. For every addressable variable V, determine whether the
1730 address of V escapes the current function, making V call-clobbered
1731 (i.e., whether &V is stored in a global variable or if its passed as a
1732 function call argument). */
1733 compute_points_to_sets (ai);
1735 /* Collect all pointers and addressable variables, compute alias sets,
1736 create memory tags for pointers and promote variables whose address is
1737 not needed anymore. */
1738 setup_pointers_and_addressables (ai);
1740 /* Compute type-based flow-insensitive aliasing for all the type
1742 compute_flow_insensitive_aliasing (ai);
1744 /* Compute flow-sensitive, points-to based aliasing for all the name
1746 compute_flow_sensitive_aliasing (ai);
1748 /* Compute call clobbering information. */
1749 compute_call_clobbered (ai);
1751 /* If the program makes no reference to global variables, but it
1752 contains a mixture of pure and non-pure functions, then we need
1753 to create use-def and def-def links between these functions to
1754 avoid invalid transformations on them. */
1755 maybe_create_global_var ();
1757 /* Compute memory partitions for every memory variable. */
1758 compute_memory_partitions ();
1760 /* Remove partitions with no symbols. Partitions may end up with an
1761 empty MPT_SYMBOLS set if a previous round of alias analysis
1762 needed to partition more symbols. Since we don't need those
1763 partitions anymore, remove them to free up the space. */
1767 VEC(tree,heap) *mpt_table;
1769 mpt_table = gimple_ssa_operands (cfun)->mpt_table;
1771 while (i < VEC_length (tree, mpt_table))
1773 mpt = VEC_index (tree, mpt_table, i);
1774 if (MPT_SYMBOLS (mpt) == NULL)
1775 VEC_unordered_remove (tree, mpt_table, i);
1781 /* Populate all virtual operands and newly promoted register operands. */
1783 block_stmt_iterator bsi;
1786 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1787 update_stmt_if_modified (bsi_stmt (bsi));
1790 /* Debugging dumps. */
1793 dump_mem_ref_stats (dump_file);
1794 dump_alias_info (dump_file);
1795 dump_points_to_info (dump_file);
1797 if (dump_flags & TDF_STATS)
1798 dump_alias_stats (dump_file);
1800 if (dump_flags & TDF_DETAILS)
1801 dump_referenced_vars (dump_file);
1804 /* Report strict aliasing violations. */
1805 strict_aliasing_warning_backend ();
1807 /* Deallocate memory used by aliasing data structures. */
1808 delete_alias_info (ai);
1810 if (need_ssa_update_p ())
1811 update_ssa (TODO_update_ssa);
1813 timevar_pop (TV_TREE_MAY_ALIAS);
1818 /* Data structure used to count the number of dereferences to PTR
1819 inside an expression. */
1827 /* Helper for count_uses_and_derefs. Called by walk_tree to look for
1828 (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
1831 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
1833 struct count_ptr_d *count_p = (struct count_ptr_d *) data;
1835 /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld,
1836 pointer 'ptr' is *not* dereferenced, it is simply used to compute
1837 the address of 'fld' as 'ptr + offsetof(fld)'. */
1838 if (TREE_CODE (*tp) == ADDR_EXPR)
1844 if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
1851 /* Count the number of direct and indirect uses for pointer PTR in
1852 statement STMT. The number of direct uses is stored in
1853 *NUM_USES_P. Indirect references are counted separately depending
1854 on whether they are store or load operations. The counts are
1855 stored in *NUM_STORES_P and *NUM_LOADS_P. */
1858 count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
1859 unsigned *num_loads_p, unsigned *num_stores_p)
1868 /* Find out the total number of uses of PTR in STMT. */
1869 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1873 /* Now count the number of indirect references to PTR. This is
1874 truly awful, but we don't have much choice. There are no parent
1875 pointers inside INDIRECT_REFs, so an expression like
1876 '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
1877 find all the indirect and direct uses of x_1 inside. The only
1878 shortcut we can take is the fact that GIMPLE only allows
1879 INDIRECT_REFs inside the expressions below. */
1880 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1881 || (TREE_CODE (stmt) == RETURN_EXPR
1882 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1883 || TREE_CODE (stmt) == ASM_EXPR
1884 || TREE_CODE (stmt) == CALL_EXPR)
1888 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1890 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1891 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1893 else if (TREE_CODE (stmt) == RETURN_EXPR)
1895 tree e = TREE_OPERAND (stmt, 0);
1896 lhs = GIMPLE_STMT_OPERAND (e, 0);
1897 rhs = GIMPLE_STMT_OPERAND (e, 1);
1899 else if (TREE_CODE (stmt) == ASM_EXPR)
1901 lhs = ASM_OUTPUTS (stmt);
1902 rhs = ASM_INPUTS (stmt);
1911 && (TREE_CODE (lhs) == TREE_LIST
1913 || GIMPLE_STMT_P (lhs)))
1915 struct count_ptr_d count;
1918 walk_tree (&lhs, count_ptr_derefs, &count, NULL);
1919 *num_stores_p = count.count;
1923 && (TREE_CODE (rhs) == TREE_LIST
1925 || GIMPLE_STMT_P (rhs)))
1927 struct count_ptr_d count;
1930 walk_tree (&rhs, count_ptr_derefs, &count, NULL);
1931 *num_loads_p = count.count;
1935 gcc_assert (*num_uses_p >= *num_loads_p + *num_stores_p);
1938 /* Remove memory references stats for function FN. */
1941 delete_mem_ref_stats (struct function *fn)
1943 if (gimple_mem_ref_stats (fn)->mem_sym_stats)
1945 free_alloc_pool (mem_sym_stats_pool);
1946 pointer_map_destroy (gimple_mem_ref_stats (fn)->mem_sym_stats);
1948 gimple_mem_ref_stats (fn)->mem_sym_stats = NULL;
1952 /* Initialize memory reference stats. */
1955 init_mem_ref_stats (void)
1957 struct mem_ref_stats_d *mem_ref_stats = gimple_mem_ref_stats (cfun);
1959 mem_sym_stats_pool = create_alloc_pool ("Mem sym stats",
1960 sizeof (struct mem_sym_stats_d),
1962 memset (mem_ref_stats, 0, sizeof (struct mem_ref_stats_d));
1963 mem_ref_stats->mem_sym_stats = pointer_map_create ();
1967 /* Helper for init_alias_info. Reset existing aliasing information. */
1970 reset_alias_info (void)
1972 referenced_var_iterator rvi;
1975 bitmap active_nmts, all_nmts;
1977 /* Clear the set of addressable variables. We do not need to clear
1978 the TREE_ADDRESSABLE bit on every symbol because we are going to
1979 re-compute addressability here. */
1980 bitmap_clear (gimple_addressable_vars (cfun));
1982 active_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
1983 all_nmts = BITMAP_ALLOC (&alias_bitmap_obstack);
1985 /* Clear flow-insensitive alias information from each symbol. */
1986 FOR_EACH_REFERENCED_VAR (var, rvi)
1988 if (is_gimple_reg (var))
1992 MTAG_ALIASES (var) = NULL;
1994 /* Memory partition information will be computed from scratch. */
1995 if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
1996 MPT_SYMBOLS (var) = NULL;
1998 /* Collect all the name tags to determine if we have any
1999 orphaned that need to be removed from the IL. A name tag
2000 will be orphaned if it is not associated with any active SSA
2002 if (TREE_CODE (var) == NAME_MEMORY_TAG)
2003 bitmap_set_bit (all_nmts, DECL_UID (var));
2005 /* Since we are about to re-discover call-clobbered
2006 variables, clear the call-clobbered flag. Variables that
2007 are intrinsically call-clobbered (globals, local statics,
2008 etc) will not be marked by the aliasing code, so we can't
2009 remove them from CALL_CLOBBERED_VARS.
2011 NB: STRUCT_FIELDS are still call clobbered if they are for a
2012 global variable, so we *don't* clear their call clobberedness
2013 just because they are tags, though we will clear it if they
2014 aren't for global variables. */
2015 if (TREE_CODE (var) == NAME_MEMORY_TAG
2016 || TREE_CODE (var) == SYMBOL_MEMORY_TAG
2017 || TREE_CODE (var) == MEMORY_PARTITION_TAG
2018 || !is_global_var (var))
2019 clear_call_clobbered (var);
2022 /* Clear flow-sensitive points-to information from each SSA name. */
2023 for (i = 1; i < num_ssa_names; i++)
2025 tree name = ssa_name (i);
2027 if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
2030 if (SSA_NAME_PTR_INFO (name))
2032 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
2034 /* Clear all the flags but keep the name tag to
2035 avoid creating new temporaries unnecessarily. If
2036 this pointer is found to point to a subset or
2037 superset of its former points-to set, then a new
2038 tag will need to be created in create_name_tags. */
2039 pi->pt_anything = 0;
2041 pi->value_escapes_p = 0;
2042 pi->is_dereferenced = 0;
2044 bitmap_clear (pi->pt_vars);
2046 /* Add NAME's name tag to the set of active tags. */
2047 if (pi->name_mem_tag)
2048 bitmap_set_bit (active_nmts, DECL_UID (pi->name_mem_tag));
2052 /* Name memory tags that are no longer associated with an SSA name
2053 are considered stale and should be removed from the IL. All the
2054 name tags that are in the set ALL_NMTS but not in ACTIVE_NMTS are
2055 considered stale and marked for renaming. */
2056 bitmap_and_compl_into (all_nmts, active_nmts);
2057 mark_set_for_renaming (all_nmts);
2059 BITMAP_FREE (all_nmts);
2060 BITMAP_FREE (active_nmts);
2064 /* Initialize the data structures used for alias analysis. */
2066 static struct alias_info *
2067 init_alias_info (void)
2069 struct alias_info *ai;
2070 referenced_var_iterator rvi;
2073 ai = XCNEW (struct alias_info);
2074 ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
2075 sbitmap_zero (ai->ssa_names_visited);
2076 ai->processed_ptrs = VEC_alloc (tree, heap, 50);
2077 ai->written_vars = pointer_set_create ();
2078 ai->dereferenced_ptrs_store = pointer_set_create ();
2079 ai->dereferenced_ptrs_load = pointer_set_create ();
2081 /* Clear out all memory reference stats. */
2082 init_mem_ref_stats ();
2084 /* If aliases have been computed before, clear existing information. */
2085 if (gimple_aliases_computed_p (cfun))
2086 reset_alias_info ();
2089 /* If this is the first time we compute aliasing information,
2090 every non-register symbol will need to be put into SSA form
2091 (the initial SSA form only operates on GIMPLE registers). */
2092 FOR_EACH_REFERENCED_VAR (var, rvi)
2093 if (!is_gimple_reg (var))
2094 mark_sym_for_renaming (var);
2097 /* Next time, we will need to reset alias information. */
2098 cfun->gimple_df->aliases_computed_p = true;
2099 if (alias_bitmap_obstack.elements != NULL)
2100 bitmap_obstack_release (&alias_bitmap_obstack);
2101 bitmap_obstack_initialize (&alias_bitmap_obstack);
2107 /* Deallocate memory used by alias analysis. */
2110 delete_alias_info (struct alias_info *ai)
2114 sbitmap_free (ai->ssa_names_visited);
2116 VEC_free (tree, heap, ai->processed_ptrs);
2118 for (i = 0; i < ai->num_addressable_vars; i++)
2119 free (ai->addressable_vars[i]);
2120 free (ai->addressable_vars);
2122 for (i = 0; i < ai->num_pointers; i++)
2123 free (ai->pointers[i]);
2124 free (ai->pointers);
2126 pointer_set_destroy (ai->written_vars);
2127 pointer_set_destroy (ai->dereferenced_ptrs_store);
2128 pointer_set_destroy (ai->dereferenced_ptrs_load);
2131 delete_mem_ref_stats (cfun);
2132 delete_points_to_sets ();
2136 /* Used for hashing to identify pointer infos with identical
2140 eq_ptr_info (const void *p1, const void *p2)
2142 const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
2143 const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
2144 return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
2148 ptr_info_hash (const void *p)
2150 const struct ptr_info_def *n = (const struct ptr_info_def *) p;
2151 return bitmap_hash (n->pt_vars);
2155 /* Create name tags for all the pointers that have been dereferenced.
2156 We only create a name tag for a pointer P if P is found to point to
2157 a set of variables (so that we can alias them to *P) or if it is
2158 the result of a call to malloc (which means that P cannot point to
2159 anything else nor alias any other variable).
2161 If two pointers P and Q point to the same set of variables, they
2162 are assigned the same name tag. */
2165 create_name_tags (void)
2168 VEC (tree, heap) *with_ptvars = NULL;
2172 /* Collect the list of pointers with a non-empty points to set. */
2173 for (i = 1; i < num_ssa_names; i++)
2175 tree ptr = ssa_name (i);
2176 struct ptr_info_def *pi;
2179 || !POINTER_TYPE_P (TREE_TYPE (ptr))
2180 || !SSA_NAME_PTR_INFO (ptr))
2183 pi = SSA_NAME_PTR_INFO (ptr);
2185 if (pi->pt_anything || !pi->is_dereferenced)
2187 /* No name tags for pointers that have not been
2188 dereferenced or point to an arbitrary location. */
2189 pi->name_mem_tag = NULL_TREE;
2193 /* Set pt_anything on the pointers without pt_vars filled in so
2194 that they are assigned a symbol tag. */
2195 if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
2196 VEC_safe_push (tree, heap, with_ptvars, ptr);
2198 set_pt_anything (ptr);
2201 /* If we didn't find any pointers with pt_vars set, we're done. */
2205 ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
2207 /* Now go through the pointers with pt_vars, and find a name tag
2208 with the same pt_vars as this pointer, or create one if one
2210 for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
2212 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2213 tree old_name_tag = pi->name_mem_tag;
2214 struct ptr_info_def **slot;
2216 /* If PTR points to a set of variables, check if we don't
2217 have another pointer Q with the same points-to set before
2218 creating a tag. If so, use Q's tag instead of creating a
2221 This is important for not creating unnecessary symbols
2222 and also for copy propagation. If we ever need to
2223 propagate PTR into Q or vice-versa, we would run into
2224 problems if they both had different name tags because
2225 they would have different SSA version numbers (which
2226 would force us to take the name tags in and out of SSA). */
2227 slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
2229 pi->name_mem_tag = (*slot)->name_mem_tag;
2234 /* If we didn't find a pointer with the same points-to set
2235 as PTR, create a new name tag if needed. */
2236 if (pi->name_mem_tag == NULL_TREE)
2237 pi->name_mem_tag = get_nmt_for (ptr);
2240 /* If the new name tag computed for PTR is different than
2241 the old name tag that it used to have, then the old tag
2242 needs to be removed from the IL, so we mark it for
2244 if (old_name_tag && old_name_tag != pi->name_mem_tag)
2245 mark_sym_for_renaming (old_name_tag);
2247 /* Inherit volatility from the pointed-to type. */
2248 TREE_THIS_VOLATILE (pi->name_mem_tag)
2249 |= TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
2251 /* Mark the new name tag for renaming. */
2252 mark_sym_for_renaming (pi->name_mem_tag);
2255 htab_delete (ptr_hash);
2257 VEC_free (tree, heap, with_ptvars);
2261 /* Union the alias set SET into the may-aliases for TAG. */
2264 union_alias_set_into (tree tag, bitmap set)
2266 bitmap ma = MTAG_ALIASES (tag);
2268 if (bitmap_empty_p (set))
2272 ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack);
2273 bitmap_ior_into (ma, set);
2277 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
2278 the name memory tag (NMT) associated with P_i. If P_i escapes, then its
2279 name tag and the variables it points-to are call-clobbered. Finally, if
2280 P_i escapes and we could not determine where it points to, then all the
2281 variables in the same alias set as *P_i are marked call-clobbered. This
2282 is necessary because we must assume that P_i may take the address of any
2283 variable in the same alias set. */
2286 compute_flow_sensitive_aliasing (struct alias_info *ai)
2291 timevar_push (TV_FLOW_SENSITIVE);
2294 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2296 if (!find_what_p_points_to (ptr))
2297 set_pt_anything (ptr);
2300 create_name_tags ();
2302 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
2304 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2306 /* Set up aliasing information for PTR's name memory tag (if it has
2307 one). Note that only pointers that have been dereferenced will
2308 have a name memory tag. */
2309 if (pi->name_mem_tag && pi->pt_vars)
2311 if (!bitmap_empty_p (pi->pt_vars))
2312 union_alias_set_into (pi->name_mem_tag, pi->pt_vars);
2315 timevar_pop (TV_FLOW_SENSITIVE);
2319 /* Return TRUE if at least one symbol in TAG2's alias set is also
2320 present in TAG1's alias set. */
2323 have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases)
2326 /* This is the old behavior of have_common_aliases_p, which is to
2327 return false if both sets are empty, or one set is and the other
2329 if (tag1aliases == NULL || tag2aliases == NULL)
2332 return bitmap_intersect_p (tag1aliases, tag2aliases);
2335 /* Compute type-based alias sets. Traverse all the pointers and
2336 addressable variables found in setup_pointers_and_addressables.
2338 For every pointer P in AI->POINTERS and addressable variable V in
2339 AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
2340 memory tag (SMT) if their alias sets conflict. V is then marked as
2341 an aliased symbol so that the operand scanner knows that statements
2342 containing V have aliased operands. */
2345 compute_flow_insensitive_aliasing (struct alias_info *ai)
2349 timevar_push (TV_FLOW_INSENSITIVE);
2350 /* For every pointer P, determine which addressable variables may alias
2351 with P's symbol memory tag. */
2352 for (i = 0; i < ai->num_pointers; i++)
2355 struct alias_map_d *p_map = ai->pointers[i];
2356 tree tag = symbol_mem_tag (p_map->var);
2359 for (j = 0; j < ai->num_addressable_vars; j++)
2361 struct alias_map_d *v_map;
2363 bool tag_stored_p, var_stored_p;
2365 v_map = ai->addressable_vars[j];
2367 v_ann = var_ann (var);
2369 /* Skip memory tags and variables that have never been
2370 written to. We also need to check if the variables are
2371 call-clobbered because they may be overwritten by
2373 tag_stored_p = pointer_set_contains (ai->written_vars, tag)
2374 || is_call_clobbered (tag);
2375 var_stored_p = pointer_set_contains (ai->written_vars, var)
2376 || is_call_clobbered (var);
2377 if (!tag_stored_p && !var_stored_p)
2380 if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
2382 /* Add VAR to TAG's may-aliases set. */
2383 add_may_alias (tag, var);
2388 /* Since this analysis is based exclusively on symbols, it fails to
2389 handle cases where two pointers P and Q have different memory
2390 tags with conflicting alias set numbers but no aliased symbols in
2393 For example, suppose that we have two memory tags SMT.1 and SMT.2
2396 may-aliases (SMT.1) = { a }
2397 may-aliases (SMT.2) = { b }
2399 and the alias set number of SMT.1 conflicts with that of SMT.2.
2400 Since they don't have symbols in common, loads and stores from
2401 SMT.1 and SMT.2 will seem independent of each other, which will
2402 lead to the optimizers making invalid transformations (see
2403 testsuite/gcc.c-torture/execute/pr15262-[12].c).
2405 To avoid this problem, we do a final traversal of AI->POINTERS
2406 looking for pairs of pointers that have no aliased symbols in
2407 common and yet have conflicting alias set numbers. */
2408 for (i = 0; i < ai->num_pointers; i++)
2411 struct alias_map_d *p_map1 = ai->pointers[i];
2412 tree tag1 = symbol_mem_tag (p_map1->var);
2413 bitmap may_aliases1 = MTAG_ALIASES (tag1);
2415 for (j = 0; j < ai->num_pointers; j++)
2417 struct alias_map_d *p_map2 = ai->pointers[j];
2418 tree tag2 = symbol_mem_tag (p_map2->var);
2419 bitmap may_aliases2 = may_aliases (tag2);
2421 /* By convention tags don't alias themselves. */
2425 /* If the pointers may not point to each other, do nothing. */
2426 if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
2429 /* The two pointers may alias each other. If they already have
2430 symbols in common, do nothing. */
2431 if (have_common_aliases_p (may_aliases1, may_aliases2))
2434 add_may_alias (tag1, tag2);
2437 timevar_pop (TV_FLOW_INSENSITIVE);
2441 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */
2444 create_alias_map_for (tree var, struct alias_info *ai)
2446 struct alias_map_d *alias_map;
2447 alias_map = XCNEW (struct alias_map_d);
2448 alias_map->var = var;
2449 alias_map->set = get_alias_set (var);
2450 ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
2454 /* Create memory tags for all the dereferenced pointers and build the
2455 ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
2456 sets. Based on the address escape and points-to information collected
2457 earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
2458 variables whose address is not needed anymore. */
2461 setup_pointers_and_addressables (struct alias_info *ai)
2463 size_t num_addressable_vars, num_pointers;
2464 referenced_var_iterator rvi;
2466 VEC (tree, heap) *varvec = NULL;
2467 safe_referenced_var_iterator srvi;
2469 /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
2470 num_addressable_vars = num_pointers = 0;
2472 FOR_EACH_REFERENCED_VAR (var, rvi)
2474 if (may_be_aliased (var))
2475 num_addressable_vars++;
2477 if (POINTER_TYPE_P (TREE_TYPE (var)))
2479 /* Since we don't keep track of volatile variables, assume that
2480 these pointers are used in indirect store operations. */
2481 if (TREE_THIS_VOLATILE (var))
2482 pointer_set_insert (ai->dereferenced_ptrs_store, var);
2488 /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
2489 always going to be slightly bigger than we actually need them
2490 because some TREE_ADDRESSABLE variables will be marked
2491 non-addressable below and only pointers with unique symbol tags are
2492 going to be added to POINTERS. */
2493 ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
2494 ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
2495 ai->num_addressable_vars = 0;
2496 ai->num_pointers = 0;
2498 FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
2500 /* Name memory tags already have flow-sensitive aliasing
2501 information, so they need not be processed by
2502 compute_flow_insensitive_aliasing. Similarly, symbol memory
2503 tags are already accounted for when we process their
2506 Structure fields, on the other hand, have to have some of this
2507 information processed for them, but it's pointless to mark them
2508 non-addressable (since they are fake variables anyway). */
2512 /* Remove the ADDRESSABLE flag from every addressable variable whose
2513 address is not needed anymore. This is caused by the propagation
2514 of ADDR_EXPR constants into INDIRECT_REF expressions and the
2515 removal of dead pointer assignments done by the early scalar
2517 if (TREE_ADDRESSABLE (var))
2519 if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var))
2520 && TREE_CODE (var) != RESULT_DECL
2521 && !is_global_var (var))
2523 bool okay_to_mark = true;
2525 /* Since VAR is now a regular GIMPLE register, we will need
2526 to rename VAR into SSA afterwards. */
2527 mark_sym_for_renaming (var);
2529 /* The address of VAR is not needed, remove the
2530 addressable bit, so that it can be optimized as a
2531 regular variable. */
2534 /* The memory partition holding VAR will no longer
2535 contain VAR, and statements referencing it will need
2537 if (memory_partition (var))
2538 mark_sym_for_renaming (memory_partition (var));
2540 mark_non_addressable (var);
2545 /* Global variables and addressable locals may be aliased. Create an
2546 entry in ADDRESSABLE_VARS for VAR. */
2547 if (may_be_aliased (var))
2549 create_alias_map_for (var, ai);
2550 mark_sym_for_renaming (var);
2553 /* Add pointer variables that have been dereferenced to the POINTERS
2554 array and create a symbol memory tag for them. */
2555 if (POINTER_TYPE_P (TREE_TYPE (var)))
2557 if ((pointer_set_contains (ai->dereferenced_ptrs_store, var)
2558 || pointer_set_contains (ai->dereferenced_ptrs_load, var)))
2563 /* If pointer VAR still doesn't have a memory tag
2564 associated with it, create it now or re-use an
2566 tag = get_smt_for (var, ai);
2567 t_ann = var_ann (tag);
2569 /* The symbol tag will need to be renamed into SSA
2570 afterwards. Note that we cannot do this inside
2571 get_smt_for because aliasing may run multiple times
2572 and we only create symbol tags the first time. */
2573 mark_sym_for_renaming (tag);
2575 /* Similarly, if pointer VAR used to have another type
2576 tag, we will need to process it in the renamer to
2577 remove the stale virtual operands. */
2578 old_tag = symbol_mem_tag (var);
2580 mark_sym_for_renaming (old_tag);
2582 /* Associate the tag with pointer VAR. */
2583 set_symbol_mem_tag (var, tag);
2585 /* If pointer VAR has been used in a store operation,
2586 then its memory tag must be marked as written-to. */
2587 if (pointer_set_contains (ai->dereferenced_ptrs_store, var))
2588 pointer_set_insert (ai->written_vars, tag);
2592 /* The pointer has not been dereferenced. If it had a
2593 symbol memory tag, remove it and mark the old tag for
2594 renaming to remove it out of the IL. */
2595 tree tag = symbol_mem_tag (var);
2598 mark_sym_for_renaming (tag);
2599 set_symbol_mem_tag (var, NULL_TREE);
2605 VEC_free (tree, heap, varvec);
2609 /* Determine whether to use .GLOBAL_VAR to model call clobbering
2610 semantics. If the function makes no references to global
2611 variables and contains at least one call to a non-pure function,
2612 then we need to mark the side-effects of the call using .GLOBAL_VAR
2613 to represent all possible global memory referenced by the callee. */
2616 maybe_create_global_var (void)
2618 /* No need to create it, if we have one already. */
2619 if (gimple_global_var (cfun) == NULL_TREE)
2621 struct mem_ref_stats_d *stats = gimple_mem_ref_stats (cfun);
2623 /* Create .GLOBAL_VAR if there are no call-clobbered
2624 variables and the program contains a mixture of pure/const
2625 and regular function calls. This is to avoid the problem
2626 described in PR 20115:
2629 int func_pure (void) { return X; }
2630 int func_non_pure (int a) { X += a; }
2633 int a = func_pure ();
2639 Since foo() has no call-clobbered variables, there is
2640 no relationship between the calls to func_pure and
2641 func_non_pure. Since func_pure has no side-effects, value
2642 numbering optimizations elide the second call to func_pure.
2643 So, if we have some pure/const and some regular calls in the
2644 program we create .GLOBAL_VAR to avoid missing these
2646 if (bitmap_empty_p (gimple_call_clobbered_vars (cfun))
2647 && stats->num_call_sites > 0
2648 && stats->num_pure_const_call_sites > 0
2649 && stats->num_call_sites > stats->num_pure_const_call_sites)
2650 create_global_var ();
2655 /* Return TRUE if pointer PTR may point to variable VAR.
2657 MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
2658 This is needed because when checking for type conflicts we are
2659 interested in the alias set of the memory location pointed-to by
2660 PTR. The alias set of PTR itself is irrelevant.
2662 VAR_ALIAS_SET is the alias set for VAR. */
2665 may_alias_p (tree ptr, alias_set_type mem_alias_set,
2666 tree var, alias_set_type var_alias_set,
2667 bool alias_set_only)
2671 alias_stats.alias_queries++;
2672 alias_stats.simple_queries++;
2674 /* By convention, a variable cannot alias itself. */
2675 mem = symbol_mem_tag (ptr);
2678 alias_stats.alias_noalias++;
2679 alias_stats.simple_resolved++;
2683 /* If -fargument-noalias-global is > 2, pointer arguments may
2684 not point to anything else. */
2685 if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
2687 alias_stats.alias_noalias++;
2688 alias_stats.simple_resolved++;
2692 /* If -fargument-noalias-global is > 1, pointer arguments may
2693 not point to global variables. */
2694 if (flag_argument_noalias > 1 && is_global_var (var)
2695 && TREE_CODE (ptr) == PARM_DECL)
2697 alias_stats.alias_noalias++;
2698 alias_stats.simple_resolved++;
2702 /* If either MEM or VAR is a read-only global and the other one
2703 isn't, then PTR cannot point to VAR. */
2704 if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
2705 || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
2707 alias_stats.alias_noalias++;
2708 alias_stats.simple_resolved++;
2712 /* If the pointed to memory has alias set zero, or the pointer
2713 is ref-all, or the pointer decl is marked that no TBAA is to
2714 be applied, the MEM can alias VAR. */
2715 if (mem_alias_set == 0
2716 || DECL_POINTER_ALIAS_SET (ptr) == 0
2717 || TYPE_REF_CAN_ALIAS_ALL (TREE_TYPE (ptr))
2718 || DECL_NO_TBAA_P (ptr))
2720 alias_stats.alias_mayalias++;
2721 alias_stats.simple_resolved++;
2725 gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
2727 alias_stats.tbaa_queries++;
2729 /* If the alias sets don't conflict then MEM cannot alias VAR. */
2730 if (mem_alias_set != var_alias_set
2731 && !alias_set_subset_of (mem_alias_set, var_alias_set))
2733 alias_stats.alias_noalias++;
2734 alias_stats.tbaa_resolved++;
2738 /* If VAR is a record or union type, PTR cannot point into VAR
2739 unless there is some explicit address operation in the
2740 program that can reference a field of the type pointed-to by
2741 PTR. This also assumes that the types of both VAR and PTR
2742 are contained within the compilation unit, and that there is
2743 no fancy addressing arithmetic associated with any of the
2745 if (mem_alias_set != 0 && var_alias_set != 0)
2747 tree ptr_type = TREE_TYPE (ptr);
2748 tree var_type = TREE_TYPE (var);
2750 /* The star count is -1 if the type at the end of the
2751 pointer_to chain is not a record or union type. */
2753 && ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
2755 int ptr_star_count = 0;
2757 /* ipa_type_escape_star_count_of_interesting_type is a
2758 little too restrictive for the pointer type, need to
2759 allow pointers to primitive types as long as those
2760 types cannot be pointers to everything. */
2761 while (POINTER_TYPE_P (ptr_type))
2763 /* Strip the *s off. */
2764 ptr_type = TREE_TYPE (ptr_type);
2768 /* There does not appear to be a better test to see if
2769 the pointer type was one of the pointer to everything
2771 if (ptr_star_count > 0)
2773 alias_stats.structnoaddress_queries++;
2774 if (ipa_type_escape_field_does_not_clobber_p (var_type,
2777 alias_stats.structnoaddress_resolved++;
2778 alias_stats.alias_noalias++;
2782 else if (ptr_star_count == 0)
2784 /* If PTR_TYPE was not really a pointer to type, it cannot
2786 alias_stats.structnoaddress_queries++;
2787 alias_stats.structnoaddress_resolved++;
2788 alias_stats.alias_noalias++;
2794 alias_stats.alias_mayalias++;
2799 /* Add ALIAS to the set of variables that may alias VAR. */
2802 add_may_alias (tree var, tree alias)
2804 /* Don't allow self-referential aliases. */
2805 gcc_assert (var != alias);
2807 /* ALIAS must be addressable if it's being added to an alias set. */
2809 TREE_ADDRESSABLE (alias) = 1;
2811 gcc_assert (may_be_aliased (alias));
2814 /* VAR must be a symbol or a name tag. */
2815 gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG
2816 || TREE_CODE (var) == NAME_MEMORY_TAG);
2818 if (MTAG_ALIASES (var) == NULL)
2819 MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack);
2821 bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias));
2825 /* Mark pointer PTR as pointing to an arbitrary memory location. */
2828 set_pt_anything (tree ptr)
2830 struct ptr_info_def *pi = get_ptr_info (ptr);
2832 pi->pt_anything = 1;
2835 /* The pointer used to have a name tag, but we now found it pointing
2836 to an arbitrary location. The name tag needs to be renamed and
2837 disassociated from PTR. */
2838 if (pi->name_mem_tag)
2840 mark_sym_for_renaming (pi->name_mem_tag);
2841 pi->name_mem_tag = NULL_TREE;
2846 /* Return true if STMT is an "escape" site from the current function. Escape
2847 sites those statements which might expose the address of a variable
2848 outside the current function. STMT is an escape site iff:
2850 1- STMT is a function call, or
2851 2- STMT is an __asm__ expression, or
2852 3- STMT is an assignment to a non-local variable, or
2853 4- STMT is a return statement.
2855 Return the type of escape site found, if we found one, or NO_ESCAPE
2859 is_escape_site (tree stmt)
2861 tree call = get_call_expr_in (stmt);
2862 if (call != NULL_TREE)
2864 if (!TREE_SIDE_EFFECTS (call))
2865 return ESCAPE_TO_PURE_CONST;
2867 return ESCAPE_TO_CALL;
2869 else if (TREE_CODE (stmt) == ASM_EXPR)
2870 return ESCAPE_TO_ASM;
2871 else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2873 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
2875 /* Get to the base of _REF nodes. */
2876 if (TREE_CODE (lhs) != SSA_NAME)
2877 lhs = get_base_address (lhs);
2879 /* If we couldn't recognize the LHS of the assignment, assume that it
2880 is a non-local store. */
2881 if (lhs == NULL_TREE)
2882 return ESCAPE_UNKNOWN;
2884 if (CONVERT_EXPR_P (GIMPLE_STMT_OPERAND (stmt, 1))
2885 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
2888 = TREE_TYPE (TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0));
2889 tree to = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 1));
2891 /* If the RHS is a conversion between a pointer and an integer, the
2892 pointer escapes since we can't track the integer. */
2893 if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
2894 return ESCAPE_BAD_CAST;
2897 /* If the LHS is an SSA name, it can't possibly represent a non-local
2899 if (TREE_CODE (lhs) == SSA_NAME)
2902 /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
2903 local variables we cannot be sure if it will escape, because we
2904 don't have information about objects not in SSA form. Need to
2905 implement something along the lines of
2907 J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
2908 Midkiff, ``Escape analysis for java,'' in Proceedings of the
2909 Conference on Object-Oriented Programming Systems, Languages, and
2910 Applications (OOPSLA), pp. 1-19, 1999. */
2911 return ESCAPE_STORED_IN_GLOBAL;
2913 else if (TREE_CODE (stmt) == RETURN_EXPR)
2914 return ESCAPE_TO_RETURN;
2919 /* Create a new memory tag of type TYPE.
2920 Does NOT push it into the current binding. */
2923 create_tag_raw (enum tree_code code, tree type, const char *prefix)
2927 tmp_var = build_decl (code, create_tmp_var_name (prefix), type);
2929 /* Make the variable writable. */
2930 TREE_READONLY (tmp_var) = 0;
2932 /* It doesn't start out global. */
2933 MTAG_GLOBAL (tmp_var) = 0;
2934 TREE_STATIC (tmp_var) = 0;
2935 TREE_USED (tmp_var) = 1;
2940 /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
2941 is considered to represent all the pointers whose pointed-to types are
2942 in the same alias set class. Otherwise, the tag represents a single
2943 SSA_NAME pointer variable. */
2946 create_memory_tag (tree type, bool is_type_tag)
2948 tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
2949 type, (is_type_tag) ? "SMT" : "NMT");
2951 /* By default, memory tags are local variables. Alias analysis will
2952 determine whether they should be considered globals. */
2953 DECL_CONTEXT (tag) = current_function_decl;
2955 /* Memory tags are by definition addressable. */
2956 TREE_ADDRESSABLE (tag) = 1;
2958 set_symbol_mem_tag (tag, NULL_TREE);
2960 /* Add the tag to the symbol table. */
2961 add_referenced_var (tag);
2967 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
2968 This is used if P_i has been found to point to a specific set of
2969 variables or to a non-aliased memory location like the address returned
2970 by malloc functions. */
2973 get_nmt_for (tree ptr)
2975 struct ptr_info_def *pi = get_ptr_info (ptr);
2976 tree tag = pi->name_mem_tag;
2978 if (tag == NULL_TREE)
2979 tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
2984 /* Return the symbol memory tag associated to pointer PTR. A memory
2985 tag is an artificial variable that represents the memory location
2986 pointed-to by PTR. It is used to model the effects of pointer
2987 de-references on addressable variables.
2989 AI points to the data gathered during alias analysis. This
2990 function populates the array AI->POINTERS. */
2993 get_smt_for (tree ptr, struct alias_info *ai)
2997 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2998 alias_set_type tag_set = get_alias_set (tag_type);
3000 /* To avoid creating unnecessary memory tags, only create one memory tag
3001 per alias set class. Note that it may be tempting to group
3002 memory tags based on conflicting alias sets instead of
3003 equivalence. That would be wrong because alias sets are not
3004 necessarily transitive (as demonstrated by the libstdc++ test
3005 23_containers/vector/cons/4.cc). Given three alias sets A, B, C
3006 such that conflicts (A, B) == true and conflicts (A, C) == true,
3007 it does not necessarily follow that conflicts (B, C) == true. */
3008 for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
3010 struct alias_map_d *curr = ai->pointers[i];
3011 tree curr_tag = symbol_mem_tag (curr->var);
3012 if (tag_set == curr->set)
3019 /* If VAR cannot alias with any of the existing memory tags, create a new
3020 tag for PTR and add it to the POINTERS array. */
3021 if (tag == NULL_TREE)
3023 struct alias_map_d *alias_map;
3025 /* If PTR did not have a symbol tag already, create a new SMT.*
3026 artificial variable representing the memory location
3027 pointed-to by PTR. */
3028 tag = symbol_mem_tag (ptr);
3029 if (tag == NULL_TREE)
3030 tag = create_memory_tag (tag_type, true);
3032 /* Add PTR to the POINTERS array. Note that we are not interested in
3033 PTR's alias set. Instead, we cache the alias set for the memory that
3035 alias_map = XCNEW (struct alias_map_d);
3036 alias_map->var = ptr;
3037 alias_map->set = tag_set;
3038 ai->pointers[ai->num_pointers++] = alias_map;
3041 /* If the pointed-to type is volatile, so is the tag. */
3042 TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
3044 /* Make sure that the symbol tag has the same alias set as the
3045 pointed-to type or at least accesses through the pointer will
3046 alias that set. The latter can happen after the vectorizer
3047 created pointers of vector type. */
3048 gcc_assert (tag_set == get_alias_set (tag)
3049 || alias_set_subset_of (tag_set, get_alias_set (tag)));
3055 /* Create GLOBAL_VAR, an artificial global variable to act as a
3056 representative of all the variables that may be clobbered by function
3060 create_global_var (void)
3062 tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
3064 DECL_ARTIFICIAL (global_var) = 1;
3065 TREE_READONLY (global_var) = 0;
3066 DECL_EXTERNAL (global_var) = 1;
3067 TREE_STATIC (global_var) = 1;
3068 TREE_USED (global_var) = 1;
3069 DECL_CONTEXT (global_var) = NULL_TREE;
3070 TREE_THIS_VOLATILE (global_var) = 0;
3071 TREE_ADDRESSABLE (global_var) = 0;
3073 create_var_ann (global_var);
3074 mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
3075 add_referenced_var (global_var);
3076 mark_sym_for_renaming (global_var);
3077 cfun->gimple_df->global_var = global_var;
3081 /* Dump alias statistics on FILE. */
3084 dump_alias_stats (FILE *file)
3086 const char *funcname
3087 = lang_hooks.decl_printable_name (current_function_decl, 2);
3088 fprintf (file, "\nAlias statistics for %s\n\n", funcname);
3089 fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
3090 fprintf (file, "Total alias mayalias results:\t%u\n",
3091 alias_stats.alias_mayalias);
3092 fprintf (file, "Total alias noalias results:\t%u\n",
3093 alias_stats.alias_noalias);
3094 fprintf (file, "Total simple queries:\t%u\n",
3095 alias_stats.simple_queries);
3096 fprintf (file, "Total simple resolved:\t%u\n",
3097 alias_stats.simple_resolved);
3098 fprintf (file, "Total TBAA queries:\t%u\n",
3099 alias_stats.tbaa_queries);
3100 fprintf (file, "Total TBAA resolved:\t%u\n",
3101 alias_stats.tbaa_resolved);
3102 fprintf (file, "Total non-addressable structure type queries:\t%u\n",
3103 alias_stats.structnoaddress_queries);
3104 fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
3105 alias_stats.structnoaddress_resolved);
3109 /* Dump alias information on FILE. */
3112 dump_alias_info (FILE *file)
3115 const char *funcname
3116 = lang_hooks.decl_printable_name (current_function_decl, 2);
3117 referenced_var_iterator rvi;
3120 fprintf (file, "\nAlias information for %s\n\n", funcname);
3122 dump_memory_partitions (file);
3124 fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
3126 fprintf (file, "Aliased symbols\n\n");
3128 FOR_EACH_REFERENCED_VAR (var, rvi)
3130 if (may_be_aliased (var))
3131 dump_variable (file, var);
3134 fprintf (file, "\nDereferenced pointers\n\n");
3136 FOR_EACH_REFERENCED_VAR (var, rvi)
3137 if (symbol_mem_tag (var))
3138 dump_variable (file, var);
3140 fprintf (file, "\nSymbol memory tags\n\n");
3142 FOR_EACH_REFERENCED_VAR (var, rvi)
3144 if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
3145 dump_variable (file, var);
3148 fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
3150 fprintf (file, "SSA_NAME pointers\n\n");
3151 for (i = 1; i < num_ssa_names; i++)
3153 tree ptr = ssa_name (i);
3154 struct ptr_info_def *pi;
3156 if (ptr == NULL_TREE)
3159 pi = SSA_NAME_PTR_INFO (ptr);
3160 if (!SSA_NAME_IN_FREE_LIST (ptr)
3162 && pi->name_mem_tag)
3163 dump_points_to_info_for (file, ptr);
3166 fprintf (file, "\nName memory tags\n\n");
3168 FOR_EACH_REFERENCED_VAR (var, rvi)
3170 if (TREE_CODE (var) == NAME_MEMORY_TAG)
3171 dump_variable (file, var);
3174 fprintf (file, "\n");
3178 /* Dump alias information on stderr. */
3181 debug_alias_info (void)
3183 dump_alias_info (stderr);
3187 /* Return the alias information associated with pointer T. It creates a
3188 new instance if none existed. */
3190 struct ptr_info_def *
3191 get_ptr_info (tree t)
3193 struct ptr_info_def *pi;
3195 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
3197 pi = SSA_NAME_PTR_INFO (t);
3200 pi = GGC_CNEW (struct ptr_info_def);
3201 SSA_NAME_PTR_INFO (t) = pi;
3208 /* Dump points-to information for SSA_NAME PTR into FILE. */
3211 dump_points_to_info_for (FILE *file, tree ptr)
3213 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
3215 print_generic_expr (file, ptr, dump_flags);
3219 if (pi->name_mem_tag)
3221 fprintf (file, ", name memory tag: ");
3222 print_generic_expr (file, pi->name_mem_tag, dump_flags);
3225 if (pi->is_dereferenced)
3226 fprintf (file, ", is dereferenced");
3228 if (pi->value_escapes_p)
3229 fprintf (file, ", its value escapes");
3231 if (pi->pt_anything)
3232 fprintf (file, ", points-to anything");
3235 fprintf (file, ", points-to NULL");
3239 fprintf (file, ", points-to vars: ");
3240 dump_decl_set (file, pi->pt_vars);
3244 fprintf (file, "\n");
3248 /* Dump points-to information for VAR into stderr. */
3251 debug_points_to_info_for (tree var)
3253 dump_points_to_info_for (stderr, var);
3257 /* Dump points-to information into FILE. NOTE: This function is slow, as
3258 it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
3261 dump_points_to_info (FILE *file)
3264 block_stmt_iterator si;
3267 lang_hooks.decl_printable_name (current_function_decl, 2);
3268 referenced_var_iterator rvi;
3271 fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
3273 /* First dump points-to information for the default definitions of
3274 pointer variables. This is necessary because default definitions are
3275 not part of the code. */
3276 FOR_EACH_REFERENCED_VAR (var, rvi)
3278 if (POINTER_TYPE_P (TREE_TYPE (var)))
3280 tree def = gimple_default_def (cfun, var);
3282 dump_points_to_info_for (file, def);
3286 /* Dump points-to information for every pointer defined in the program. */
3291 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3293 tree ptr = PHI_RESULT (phi);
3294 if (POINTER_TYPE_P (TREE_TYPE (ptr)))
3295 dump_points_to_info_for (file, ptr);
3298 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3300 tree stmt = bsi_stmt (si);
3302 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
3303 if (TREE_CODE (def) == SSA_NAME
3304 && POINTER_TYPE_P (TREE_TYPE (def)))
3305 dump_points_to_info_for (file, def);
3309 fprintf (file, "\n");
3313 /* Dump points-to info pointed to by PTO into STDERR. */
3316 debug_points_to_info (void)
3318 dump_points_to_info (stderr);
3321 /* Dump to FILE the list of variables that may be aliasing VAR. */
3324 dump_may_aliases_for (FILE *file, tree var)
3328 aliases = MTAG_ALIASES (var);
3335 fprintf (file, "{ ");
3336 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
3338 al = referenced_var (i);
3339 print_generic_expr (file, al, dump_flags);
3340 fprintf (file, " ");
3342 fprintf (file, "}");
3347 /* Dump to stderr the list of variables that may be aliasing VAR. */
3350 debug_may_aliases_for (tree var)
3352 dump_may_aliases_for (stderr, var);
3356 /* Return true if VAR may be aliased. */
3359 may_be_aliased (tree var)
3362 if (TREE_ADDRESSABLE (var))
3365 /* Globally visible variables can have their addresses taken by other
3366 translation units. */
3368 && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
3370 else if (!MTAG_P (var)
3371 && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
3374 /* Automatic variables can't have their addresses escape any other
3375 way. This must be after the check for global variables, as
3376 extern declarations do not have TREE_STATIC set. */
3377 if (!TREE_STATIC (var))
3380 /* If we're in unit-at-a-time mode, then we must have seen all
3381 occurrences of address-of operators, and so we can trust
3382 TREE_ADDRESSABLE. Otherwise we can only be sure the variable
3383 isn't addressable if it's local to the current function. */
3384 if (flag_unit_at_a_time)
3387 if (decl_function_context (var) == current_function_decl)
3393 /* The following is based on code in add_stmt_operand to ensure that the
3394 same defs/uses/vdefs/vuses will be found after replacing a reference
3395 to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
3396 is the address of var. Return a memtag for the ptr, after adding the
3397 proper may_aliases to it (which are the aliases of var, if it has any,
3401 add_may_alias_for_new_tag (tree tag, tree var)
3403 bitmap aliases = NULL;
3406 aliases = may_aliases (var);
3408 /* Case 1: |aliases| == 1 */
3410 && bitmap_single_bit_set_p (aliases))
3412 tree ali = referenced_var (bitmap_first_set_bit (aliases));
3413 if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
3417 /* Case 2: |aliases| == 0 */
3418 if (aliases == NULL)
3419 add_may_alias (tag, var);
3422 /* Case 3: |aliases| > 1 */
3423 union_alias_set_into (tag, aliases);
3428 /* Create a new symbol tag for PTR. Construct the may-alias list of
3429 this type tag so that it has the aliasing of VAR according to the
3430 location accessed by EXPR.
3432 Note, the set of aliases represented by the new symbol tag are not
3433 marked for renaming. */
3436 new_type_alias (tree ptr, tree var, tree expr)
3438 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
3440 tree ali = NULL_TREE;
3441 HOST_WIDE_INT offset, size, maxsize;
3444 gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
3445 gcc_assert (!MTAG_P (var));
3447 ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
3450 tag = create_memory_tag (tag_type, true);
3451 set_symbol_mem_tag (ptr, tag);
3453 ali = add_may_alias_for_new_tag (tag, var);
3455 set_symbol_mem_tag (ptr, ali);
3456 MTAG_GLOBAL (tag) = is_global_var (var);
3460 /* Reset the call_clobbered flags on our referenced vars. In
3461 theory, this only needs to be done for globals. */
3464 reset_cc_flags (void)
3467 referenced_var_iterator rvi;
3469 FOR_EACH_REFERENCED_VAR (var, rvi)
3470 var_ann (var)->call_clobbered = false;
3474 struct gimple_opt_pass pass_reset_cc_flags =
3480 reset_cc_flags, /* execute */
3483 0, /* static_pass_number */
3485 PROP_referenced_vars |PROP_cfg, /* properties_required */
3486 0, /* properties_provided */
3487 0, /* properties_destroyed */
3488 0, /* todo_flags_start */
3489 0 /* todo_flags_finish */
3494 /* A dummy pass to cause aliases to be computed via TODO_rebuild_alias. */
3496 struct gimple_opt_pass pass_build_alias =
3505 0, /* static_pass_number */
3507 PROP_cfg | PROP_ssa, /* properties_required */
3508 PROP_alias, /* properties_provided */
3509 0, /* properties_destroyed */
3510 0, /* todo_flags_start */
3511 TODO_rebuild_alias | TODO_dump_func /* todo_flags_finish */