1 /* Alias analysis for trees.
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
24 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
34 #include "langhooks.h"
37 #include "diagnostic.h"
38 #include "tree-dump.h"
39 #include "tree-gimple.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
42 #include "tree-pass.h"
43 #include "tree-ssa-structalias.h"
46 #include "ipa-type-escape.h"
50 #include "pointer-set.h"
52 /* Structure to map a variable to its alias set. */
55 /* Variable and its alias set. */
61 /* Data structures used for computing memory partitions. */
65 /* Symbol or memory tag. */
68 /* Number of virtual operators needed to represent references to VAR. */
72 typedef struct mp_info_def *mp_info_t;
74 DEF_VEC_ALLOC_P(mp_info_t, heap);
76 /* Counters used to display statistics on alias analysis. */
79 unsigned int alias_queries;
80 unsigned int alias_mayalias;
81 unsigned int alias_noalias;
82 unsigned int simple_queries;
83 unsigned int simple_resolved;
84 unsigned int tbaa_queries;
85 unsigned int tbaa_resolved;
86 unsigned int structnoaddress_queries;
87 unsigned int structnoaddress_resolved;
91 /* Local variables. */
92 static struct alias_stats_d alias_stats;
93 static bitmap_obstack alias_bitmap_obstack;
95 /* Local functions. */
96 static void compute_flow_insensitive_aliasing (struct alias_info *);
97 static void finalize_ref_all_pointers (struct alias_info *);
98 static void dump_alias_stats (FILE *);
99 static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool);
100 static tree create_memory_tag (tree type, bool is_type_tag);
101 static tree get_smt_for (tree, struct alias_info *);
102 static tree get_nmt_for (tree);
103 static void add_may_alias (tree, tree);
104 static struct alias_info *init_alias_info (void);
105 static void delete_alias_info (struct alias_info *);
106 static void compute_flow_sensitive_aliasing (struct alias_info *);
107 static void setup_pointers_and_addressables (struct alias_info *);
108 static void create_global_var (void);
109 static void maybe_create_global_var (struct alias_info *ai);
110 static void set_pt_anything (tree ptr);
112 void dump_mp_info (FILE *, VEC(mp_info_t,heap) *mp_info_t);
113 void debug_mp_info (VEC(mp_info_t,heap) *mp_info_t);
115 /* Global declarations. */
117 /* Mark variable VAR as being non-addressable. */
120 mark_non_addressable (tree var)
124 if (!TREE_ADDRESSABLE (var))
127 mpt = memory_partition (var);
130 var_ann (var)->call_clobbered = false;
132 bitmap_clear_bit (gimple_call_clobbered_vars (cfun), DECL_UID (var));
133 TREE_ADDRESSABLE (var) = 0;
137 bitmap_clear_bit (MPT_SYMBOLS (mpt), DECL_UID (var));
138 set_memory_partition (var, NULL_TREE);
143 /* qsort comparison function to sort type/name tags by DECL_UID. */
146 sort_tags_by_id (const void *pa, const void *pb)
148 tree a = *(tree *)pa;
149 tree b = *(tree *)pb;
151 return DECL_UID (a) - DECL_UID (b);
154 /* Initialize WORKLIST to contain those memory tags that are marked call
155 clobbered. Initialized WORKLIST2 to contain the reasons these
156 memory tags escaped. */
159 init_transitive_clobber_worklist (VEC (tree, heap) **worklist,
160 VEC (int, heap) **worklist2)
162 referenced_var_iterator rvi;
165 FOR_EACH_REFERENCED_VAR (curr, rvi)
167 if (MTAG_P (curr) && is_call_clobbered (curr))
169 VEC_safe_push (tree, heap, *worklist, curr);
170 VEC_safe_push (int, heap, *worklist2, var_ann (curr)->escape_mask);
175 /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
176 ALIAS is not already marked call clobbered, and is a memory
180 add_to_worklist (tree alias, VEC (tree, heap) **worklist,
181 VEC (int, heap) **worklist2,
184 if (MTAG_P (alias) && !is_call_clobbered (alias))
186 VEC_safe_push (tree, heap, *worklist, alias);
187 VEC_safe_push (int, heap, *worklist2, reason);
191 /* Mark aliases of TAG as call clobbered, and place any tags on the
192 alias list that were not already call clobbered on WORKLIST. */
195 mark_aliases_call_clobbered (tree tag, VEC (tree, heap) **worklist,
196 VEC (int, heap) **worklist2)
202 var_ann_t ta = var_ann (tag);
206 aliases = may_aliases (tag);
210 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
212 entry = referenced_var (i);
213 if (!unmodifiable_var_p (entry))
215 add_to_worklist (entry, worklist, worklist2, ta->escape_mask);
216 mark_call_clobbered (entry, ta->escape_mask);
221 /* Tags containing global vars need to be marked as global.
222 Tags containing call clobbered vars need to be marked as call
226 compute_tag_properties (void)
228 referenced_var_iterator rvi;
231 VEC (tree, heap) *taglist = NULL;
233 FOR_EACH_REFERENCED_VAR (tag, rvi)
235 if (!MTAG_P (tag) || TREE_CODE (tag) == STRUCT_FIELD_TAG)
237 VEC_safe_push (tree, heap, taglist, tag);
240 /* We sort the taglist by DECL_UID, for two reasons.
241 1. To get a sequential ordering to make the bitmap accesses
243 2. Because of the way we compute aliases, it's more likely that
244 an earlier tag is included in a later tag, and this will reduce
245 the number of iterations.
247 If we had a real tag graph, we would just topo-order it and be
249 qsort (VEC_address (tree, taglist),
250 VEC_length (tree, taglist),
254 /* Go through each tag not marked as global, and if it aliases
255 global vars, mark it global.
257 If the tag contains call clobbered vars, mark it call
260 This loop iterates because tags may appear in the may-aliases
261 list of other tags when we group. */
268 for (k = 0; VEC_iterate (tree, taglist, k, tag); k++)
274 bool tagcc = is_call_clobbered (tag);
275 bool tagglobal = MTAG_GLOBAL (tag);
277 if (tagcc && tagglobal)
280 ma = may_aliases (tag);
284 EXECUTE_IF_SET_IN_BITMAP (ma, 0, i, bi)
286 entry = referenced_var (i);
287 /* Call clobbered entries cause the tag to be marked
289 if (!tagcc && is_call_clobbered (entry))
291 mark_call_clobbered (tag, var_ann (entry)->escape_mask);
296 /* Global vars cause the tag to be marked global. */
297 if (!tagglobal && is_global_var (entry))
299 MTAG_GLOBAL (tag) = true;
304 /* Early exit once both global and cc are set, since the
305 loop can't do any more than that. */
306 if (tagcc && tagglobal)
311 VEC_free (tree, heap, taglist);
314 /* Set up the initial variable clobbers and globalness.
315 When this function completes, only tags whose aliases need to be
316 clobbered will be set clobbered. Tags clobbered because they
317 contain call clobbered vars are handled in compute_tag_properties. */
320 set_initial_properties (struct alias_info *ai)
323 referenced_var_iterator rvi;
327 FOR_EACH_REFERENCED_VAR (var, rvi)
329 if (is_global_var (var)
330 && (!var_can_have_subvars (var)
331 || get_subvars_for_var (var) == NULL))
333 if (!unmodifiable_var_p (var))
334 mark_call_clobbered (var, ESCAPE_IS_GLOBAL);
336 else if (TREE_CODE (var) == PARM_DECL
337 && gimple_default_def (cfun, var)
338 && POINTER_TYPE_P (TREE_TYPE (var)))
340 tree def = gimple_default_def (cfun, var);
341 get_ptr_info (def)->value_escapes_p = 1;
342 get_ptr_info (def)->escape_mask |= ESCAPE_IS_PARM;
346 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
348 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
349 tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
351 if (pi->value_escapes_p)
353 /* If PTR escapes then its associated memory tags and
354 pointed-to variables are call-clobbered. */
355 if (pi->name_mem_tag)
356 mark_call_clobbered (pi->name_mem_tag, pi->escape_mask);
359 mark_call_clobbered (tag, pi->escape_mask);
365 EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
366 if (!unmodifiable_var_p (referenced_var (j)))
367 mark_call_clobbered (referenced_var (j), pi->escape_mask);
371 /* If the name tag is call clobbered, so is the symbol tag
372 associated with the base VAR_DECL. */
375 && is_call_clobbered (pi->name_mem_tag))
376 mark_call_clobbered (tag, pi->escape_mask);
378 /* Name tags and symbol tags that we don't know where they point
379 to, might point to global memory, and thus, are clobbered.
381 FIXME: This is not quite right. They should only be
382 clobbered if value_escapes_p is true, regardless of whether
383 they point to global memory or not.
384 So removing this code and fixing all the bugs would be nice.
385 It is the cause of a bunch of clobbering. */
386 if ((pi->pt_global_mem || pi->pt_anything)
387 && pi->is_dereferenced && pi->name_mem_tag)
389 mark_call_clobbered (pi->name_mem_tag, ESCAPE_IS_GLOBAL);
390 MTAG_GLOBAL (pi->name_mem_tag) = true;
393 if ((pi->pt_global_mem || pi->pt_anything)
394 && pi->is_dereferenced
397 mark_call_clobbered (tag, ESCAPE_IS_GLOBAL);
398 MTAG_GLOBAL (tag) = true;
403 /* Compute which variables need to be marked call clobbered because
404 their tag is call clobbered, and which tags need to be marked
405 global because they contain global variables. */
408 compute_call_clobbered (struct alias_info *ai)
410 VEC (tree, heap) *worklist = NULL;
411 VEC(int,heap) *worklist2 = NULL;
413 set_initial_properties (ai);
414 init_transitive_clobber_worklist (&worklist, &worklist2);
415 while (VEC_length (tree, worklist) != 0)
417 tree curr = VEC_pop (tree, worklist);
418 int reason = VEC_pop (int, worklist2);
420 mark_call_clobbered (curr, reason);
421 mark_aliases_call_clobbered (curr, &worklist, &worklist2);
423 VEC_free (tree, heap, worklist);
424 VEC_free (int, heap, worklist2);
425 compute_tag_properties ();
428 /* Dump the MP_INFO array to FILE. */
431 dump_mp_info (FILE *file, VEC(mp_info_t,heap) *mp_info)
436 for (i = 0; VEC_iterate (mp_info_t, mp_info, i, mp_p); i++)
438 fprintf (file, "%6lu\t", mp_p->num_vops);
439 if (mp_p->var == NULL_TREE)
441 fprintf (file, "CALL-CLOBBERED SYMBOLS: ");
442 dump_decl_set (file, gimple_call_clobbered_vars (cfun));
445 dump_variable (file, mp_p->var);
450 /* Dump the MP_INFO array to stderr. */
453 debug_mp_info (VEC(mp_info_t,heap) *mp_info)
455 dump_mp_info (stderr, mp_info);
459 /* Comparison function for qsort used in sort_mp_info. */
462 mp_info_cmp (const void *p, const void *q)
464 mp_info_t e1 = *((const mp_info_t *) p);
465 mp_info_t e2 = *((const mp_info_t *) q);
467 /* We want to sort in decreasing order. */
468 if (e1->num_vops < e2->num_vops)
470 else if (e1->num_vops > e2->num_vops)
477 /* Sort the array of reference counts used to compute memory partitions.
478 Elements are sorted in descending order of virtual operators needed. */
481 sort_mp_info (VEC(mp_info_t,heap) *list)
483 unsigned num = VEC_length (mp_info_t, list);
490 if (VEC_index (mp_info_t, list, 0)->num_vops
491 < VEC_index (mp_info_t, list, 1)->num_vops)
493 /* Swap elements if they are in the wrong order. */
494 mp_info_t tmp = VEC_index (mp_info_t, list, 0);
495 VEC_replace (mp_info_t, list, 0, VEC_index (mp_info_t, list, 1));
496 VEC_replace (mp_info_t, list, 1, tmp);
502 /* There are 3 or more elements, call qsort. */
503 qsort (VEC_address (mp_info_t, list), VEC_length (mp_info_t, list),
504 sizeof (mp_info_t), mp_info_cmp);
508 /* Create a new partition to hold all the symbols aliased with
509 MP_P->VAR. If MP_P->VAR is NULL, it partitions the call-clobbered
510 variables. Only symbols that are not already in another partition
511 are added to the new partition created for MP_P->VAR. */
514 create_partition_for (mp_info_t mp_p)
521 if (mp_p->num_vops <= (long) MAX_ALIASED_VOPS)
524 if (mp_p->var == NULL_TREE)
529 /* Since the partitions we create for call-clobbered variables
530 will also be marked call-clobbered, make a copy of the
531 original set to avoid confusing the iterator. */
532 tmp = BITMAP_ALLOC (NULL);
533 bitmap_copy (tmp, gimple_call_clobbered_vars (cfun));
535 /* Process call-clobbered symbols when no MP_P->VAR is given. */
537 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
539 tree sym = referenced_var (i);
540 if (memory_partition (sym) == NULL_TREE)
542 if (mpt == NULL_TREE)
544 mpt = get_mpt_for (sym);
548 mark_sym_for_renaming (mpt);
549 mark_sym_for_renaming (sym);
550 set_memory_partition (sym, mpt);
555 /* If we have already grouped enough, stop. */
556 if (mp_p->num_vops <= (long) MAX_ALIASED_VOPS)
564 aliases = may_aliases (mp_p->var);
565 gcc_assert (!bitmap_empty_p (aliases));
568 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
570 sym = referenced_var (i);
571 /* Only set the memory partition for aliased symbol SYM if
572 SYM does not belong to another partition. */
573 if (memory_partition (sym) == NULL_TREE)
575 if (mpt == NULL_TREE)
577 mpt = get_mpt_for (mp_p->var);
581 mark_sym_for_renaming (mpt);
582 mark_sym_for_renaming (sym);
583 set_memory_partition (sym, mpt);
588 /* If we have already grouped enough, stop. */
589 if (mp_p->num_vops <= (long) MAX_ALIASED_VOPS)
594 mark_call_clobbered (mpt, ESCAPE_UNKNOWN);
599 /* Rewrite the alias set for TAG to use the newly created partitions.
600 If TAG is NULL, rewrite the set of call-clobbered variables.
601 NEW_ALIASES is a scratch bitmap to build the new set of aliases for
605 rewrite_alias_set_for (tree tag, bitmap new_aliases)
611 if (tag == NULL_TREE)
613 /* Do not rewrite CALL_CLOBBERED_VARS. If a symbol S is taken
614 out of this set, the optimizers will no longer consider S as
615 call-clobbered, and that may lead to wrong transformations
616 (e.g., pass_tail_calls explicitly examines all the symbols in
617 the function to determine if it should enable tail-call
623 /* Create a new alias set for TAG with the new partitions. */
625 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag), 0, i, bi)
627 sym = referenced_var (i);
628 mpt = memory_partition (sym);
630 bitmap_set_bit (new_aliases, DECL_UID (mpt));
632 bitmap_set_bit (new_aliases, DECL_UID (sym));
635 /* Rebuild the may-alias array for TAG. */
636 bitmap_copy (MTAG_ALIASES (tag), new_aliases);
641 /* Compute memory partitions.
643 The partitioning is straightforward:
645 1- All the memory tags and call-clobbered that cause virtual
646 operators are collected into the MP_INFO table together with the
647 number of virtual operands that would be needed to represent all
648 the members in the alias set.
650 2- MP_INFO is sorted in decreasing order of virtual operators.
652 3- For every memory tag T in MP_INFO, a new partition MP is created.
654 4- All the symbols S in T's alias set are examined. If S is not
655 already in another partition then S is added to partition MP.
657 6- The estimate of VOPS is updated, if it falls below
658 MAX_ALIASED_VOPS, we stop. */
661 compute_memory_partitions (void)
663 referenced_var_iterator rvi;
666 struct mp_info_def mp;
668 VEC(mp_info_t,heap) *mp_info;
669 long max_num_vops = 0;
672 timevar_push (TV_MEMORY_PARTITIONING);
677 /* Add reference counts for all the call-clobbered variables. */
678 if (!bitmap_empty_p (gimple_call_clobbered_vars (cfun)))
681 mp.num_vops = bitmap_count_bits (gimple_call_clobbered_vars (cfun));
682 max_num_vops = mp.num_vops;
683 mp_p = xcalloc (1, sizeof (*mp_p));
685 VEC_safe_push (mp_info_t, heap, mp_info, mp_p);
688 /* Add reference counts for all the symbol tags. */
689 FOR_EACH_REFERENCED_VAR (var, rvi)
691 if (TREE_CODE (var) != SYMBOL_MEMORY_TAG
692 && TREE_CODE (var) != NAME_MEMORY_TAG)
695 /* Each reference to VAR will produce as many VOPs as elements
696 exist in its alias set. */
698 if (!may_aliases (var))
701 mp.num_vops = bitmap_count_bits (may_aliases (var));
703 /* No point grouping singleton alias sets. */
704 if (mp.num_vops <= 1)
707 mp_p = xcalloc (1, sizeof (*mp_p));
709 VEC_safe_push (mp_info_t, heap, mp_info, mp_p);
711 if (mp.num_vops > max_num_vops)
712 max_num_vops = mp.num_vops;
717 fprintf (dump_file, "\n%s: Maximum number of VOPS needed per statement: "
718 "%ld\n", get_name (current_function_decl), max_num_vops);
721 /* No partitions required if we are below the threshold. */
722 if (max_num_vops <= (long) MAX_ALIASED_VOPS)
725 /* Sort the MP_INFO array in order of decreasing number of
727 sort_mp_info (mp_info);
731 fprintf (dump_file, "\nVOPS generated by pointer dereferences "
732 "before partitioning:\n");
733 dump_mp_info (dump_file, mp_info);
736 /* Now that we have all the VOP generating tags in the MP_INFO array
737 sorted by decreasing number of VOPS, create memory partitions and
738 group aliased symbols into those partitions. */
739 for (i = 0; VEC_iterate (mp_info_t, mp_info, i, mp_p); i++)
741 /* Stop processing if we are already below the threshold. */
742 if (mp_p->num_vops <= (long) MAX_ALIASED_VOPS)
745 create_partition_for (mp_p);
748 /* After partitions have been created, rewrite alias sets to use
749 them instead of the original symbols. This way, if the alias set
750 was computed as { a b c d e f }, and the subset { b e f } was
751 grouped into partition MPT.3, then the new alias set for the tag
752 will be { a c d MPT.3 }. */
753 new_aliases = BITMAP_ALLOC (NULL);
755 for (i = 0; VEC_iterate (mp_info_t, mp_info, i, mp_p); i++)
757 rewrite_alias_set_for (mp_p->var, new_aliases);
758 bitmap_clear (new_aliases);
761 BITMAP_FREE (new_aliases);
765 fprintf (dump_file, "\nVOPS generated by pointer dereferences "
766 "after partitioning:\n");
767 dump_mp_info (dump_file, mp_info);
771 /* Free allocated memory. */
772 for (i = 0; VEC_iterate (mp_info_t, mp_info, i, mp_p); i++)
774 VEC_free (mp_info_t, heap, mp_info);
776 timevar_pop (TV_MEMORY_PARTITIONING);
779 /* This function computes the value of the is_aliased bit for
780 variables. is_aliased is true for any variable that is in an
784 compute_is_aliased (void)
786 referenced_var_iterator rvi;
788 bitmap aliased_vars = BITMAP_ALLOC (NULL);
792 /* Add is_aliased for all vars pointed to by the symbol tags. */
793 FOR_EACH_REFERENCED_VAR (tag, rvi)
796 if (TREE_CODE (tag) != SYMBOL_MEMORY_TAG
797 && TREE_CODE (tag) != NAME_MEMORY_TAG)
799 aliases = MTAG_ALIASES (tag);
803 bitmap_ior_into (aliased_vars, aliases);
806 EXECUTE_IF_SET_IN_BITMAP (aliased_vars, 0, i, bi)
808 tree var = referenced_var (i);
810 var_ann (var)->is_aliased = true;
813 BITMAP_FREE (aliased_vars);
817 /* Compute may-alias information for every variable referenced in function
820 Alias analysis proceeds in 3 main phases:
822 1- Points-to and escape analysis.
824 This phase walks the use-def chains in the SSA web looking for three
827 * Assignments of the form P_i = &VAR
828 * Assignments of the form P_i = malloc()
829 * Pointers and ADDR_EXPR that escape the current function.
831 The concept of 'escaping' is the same one used in the Java world. When
832 a pointer or an ADDR_EXPR escapes, it means that it has been exposed
833 outside of the current function. So, assignment to global variables,
834 function arguments and returning a pointer are all escape sites, as are
835 conversions between pointers and integers.
837 This is where we are currently limited. Since not everything is renamed
838 into SSA, we lose track of escape properties when a pointer is stashed
839 inside a field in a structure, for instance. In those cases, we are
840 assuming that the pointer does escape.
842 We use escape analysis to determine whether a variable is
843 call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable
844 is call-clobbered. If a pointer P_i escapes, then all the variables
845 pointed-to by P_i (and its memory tag) also escape.
847 2- Compute flow-sensitive aliases
849 We have two classes of memory tags. Memory tags associated with the
850 pointed-to data type of the pointers in the program. These tags are
851 called "symbol memory tag" (SMT). The other class are those associated
852 with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
853 when adding operands for an INDIRECT_REF *P_i, we will first check
854 whether P_i has a name tag, if it does we use it, because that will have
855 more precise aliasing information. Otherwise, we use the standard symbol
858 In this phase, we go through all the pointers we found in points-to
859 analysis and create alias sets for the name memory tags associated with
860 each pointer P_i. If P_i escapes, we mark call-clobbered the variables
861 it points to and its tag.
864 3- Compute flow-insensitive aliases
866 This pass will compare the alias set of every symbol memory tag and
867 every addressable variable found in the program. Given a symbol
868 memory tag SMT and an addressable variable V. If the alias sets of
869 SMT and V conflict (as computed by may_alias_p), then V is marked
870 as an alias tag and added to the alias set of SMT.
872 For instance, consider the following function:
888 After aliasing analysis has finished, the symbol memory tag for pointer
889 'p' will have two aliases, namely variables 'a' and 'b'. Every time
890 pointer 'p' is dereferenced, we want to mark the operation as a
891 potential reference to 'a' and 'b'.
901 # p_1 = PHI <p_4(1), p_6(2)>;
916 In certain cases, the list of may aliases for a pointer may grow too
917 large. This may cause an explosion in the number of virtual operands
918 inserted in the code. Resulting in increased memory consumption and
921 When the number of virtual operands needed to represent aliased
922 loads and stores grows too large (configurable with @option{--param
923 max-aliased-vops}), alias sets are grouped to avoid severe
924 compile-time slow downs and memory consumption. See group_aliases. */
927 compute_may_aliases (void)
929 struct alias_info *ai;
931 memset (&alias_stats, 0, sizeof (alias_stats));
933 /* Initialize aliasing information. */
934 ai = init_alias_info ();
936 /* For each pointer P_i, determine the sets of variables that P_i may
937 point-to. For every addressable variable V, determine whether the
938 address of V escapes the current function, making V call-clobbered
939 (i.e., whether &V is stored in a global variable or if its passed as a
940 function call argument). */
941 compute_points_to_sets (ai);
943 /* Collect all pointers and addressable variables, compute alias sets,
944 create memory tags for pointers and promote variables whose address is
945 not needed anymore. */
946 setup_pointers_and_addressables (ai);
948 /* Compute type-based flow-insensitive aliasing for all the type
950 compute_flow_insensitive_aliasing (ai);
952 /* Compute flow-sensitive, points-to based aliasing for all the name
954 compute_flow_sensitive_aliasing (ai);
956 /* Compute call clobbering information. */
957 compute_call_clobbered (ai);
959 /* If the program makes no reference to global variables, but it
960 contains a mixture of pure and non-pure functions, then we need
961 to create use-def and def-def links between these functions to
962 avoid invalid transformations on them. */
963 maybe_create_global_var (ai);
965 /* If the program contains ref-all pointers, finalize may-alias information
966 for them. This pass needs to be run after call-clobbering information
967 has been computed. */
968 if (ai->ref_all_symbol_mem_tag)
969 finalize_ref_all_pointers (ai);
971 /* Compute memory partitions for every memory variable. */
972 compute_memory_partitions ();
974 /* Debugging dumps. */
977 dump_referenced_vars (dump_file);
978 if (dump_flags & TDF_STATS)
979 dump_alias_stats (dump_file);
980 dump_points_to_info (dump_file);
981 dump_alias_info (dump_file);
984 /* Set up is_aliased flags. */
985 compute_is_aliased ();
987 /* Deallocate memory used by aliasing data structures. */
988 delete_alias_info (ai);
991 block_stmt_iterator bsi;
995 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
997 update_stmt_if_modified (bsi_stmt (bsi));
1005 struct tree_opt_pass pass_may_alias =
1009 compute_may_aliases, /* execute */
1012 0, /* static_pass_number */
1013 TV_TREE_MAY_ALIAS, /* tv_id */
1014 PROP_cfg | PROP_ssa, /* properties_required */
1015 PROP_alias, /* properties_provided */
1016 0, /* properties_destroyed */
1017 0, /* todo_flags_start */
1018 TODO_dump_func | TODO_update_ssa
1019 | TODO_ggc_collect | TODO_verify_ssa
1020 | TODO_verify_stmts, /* todo_flags_finish */
1025 /* Data structure used to count the number of dereferences to PTR
1026 inside an expression. */
1034 /* Helper for count_uses_and_derefs. Called by walk_tree to look for
1035 (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
1038 count_ptr_derefs (tree *tp, int *walk_subtrees, void *data)
1040 struct count_ptr_d *count_p = (struct count_ptr_d *) data;
1042 /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld,
1043 pointer 'ptr' is *not* dereferenced, it is simply used to compute
1044 the address of 'fld' as 'ptr + offsetof(fld)'. */
1045 if (TREE_CODE (*tp) == ADDR_EXPR)
1051 if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
1058 /* Count the number of direct and indirect uses for pointer PTR in
1059 statement STMT. The two counts are stored in *NUM_USES_P and
1060 *NUM_DEREFS_P respectively. *IS_STORE_P is set to 'true' if at
1061 least one of those dereferences is a store operation. */
1064 count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
1065 unsigned *num_derefs_p, bool *is_store)
1074 /* Find out the total number of uses of PTR in STMT. */
1075 FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
1079 /* Now count the number of indirect references to PTR. This is
1080 truly awful, but we don't have much choice. There are no parent
1081 pointers inside INDIRECT_REFs, so an expression like
1082 '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
1083 find all the indirect and direct uses of x_1 inside. The only
1084 shortcut we can take is the fact that GIMPLE only allows
1085 INDIRECT_REFs inside the expressions below. */
1086 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1087 || (TREE_CODE (stmt) == RETURN_EXPR
1088 && TREE_CODE (TREE_OPERAND (stmt, 0)) == GIMPLE_MODIFY_STMT)
1089 || TREE_CODE (stmt) == ASM_EXPR
1090 || TREE_CODE (stmt) == CALL_EXPR)
1094 if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
1096 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1097 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1099 else if (TREE_CODE (stmt) == RETURN_EXPR)
1101 tree e = TREE_OPERAND (stmt, 0);
1102 lhs = GIMPLE_STMT_OPERAND (e, 0);
1103 rhs = GIMPLE_STMT_OPERAND (e, 1);
1105 else if (TREE_CODE (stmt) == ASM_EXPR)
1107 lhs = ASM_OUTPUTS (stmt);
1108 rhs = ASM_INPUTS (stmt);
1116 if (lhs && (TREE_CODE (lhs) == TREE_LIST
1117 || EXPR_P (lhs) || GIMPLE_STMT_P (lhs)))
1119 struct count_ptr_d count;
1122 walk_tree (&lhs, count_ptr_derefs, &count, NULL);
1124 *num_derefs_p = count.count;
1127 if (rhs && (TREE_CODE (rhs) == TREE_LIST
1128 || EXPR_P (rhs) || GIMPLE_STMT_P (rhs)))
1130 struct count_ptr_d count;
1133 walk_tree (&rhs, count_ptr_derefs, &count, NULL);
1134 *num_derefs_p += count.count;
1138 gcc_assert (*num_uses_p >= *num_derefs_p);
1141 /* Initialize the data structures used for alias analysis. */
1143 static struct alias_info *
1144 init_alias_info (void)
1146 struct alias_info *ai;
1147 referenced_var_iterator rvi;
1150 ai = XCNEW (struct alias_info);
1151 ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
1152 sbitmap_zero (ai->ssa_names_visited);
1153 ai->processed_ptrs = VEC_alloc (tree, heap, 50);
1154 ai->written_vars = pointer_set_create ();
1155 ai->dereferenced_ptrs_store = pointer_set_create ();
1156 ai->dereferenced_ptrs_load = pointer_set_create ();
1158 /* If aliases have been computed before, clear existing information. */
1159 if (gimple_aliases_computed_p (cfun))
1163 bitmap_obstack_release (&alias_bitmap_obstack);
1165 /* Similarly, clear the set of addressable variables. In this
1166 case, we can just clear the set because addressability is
1167 only computed here. */
1168 bitmap_clear (gimple_addressable_vars (cfun));
1170 /* Clear flow-insensitive alias information from each symbol. */
1171 FOR_EACH_REFERENCED_VAR (var, rvi)
1173 var_ann_t ann = var_ann (var);
1175 ann->is_aliased = 0;
1178 MTAG_ALIASES (var) = NULL;
1180 /* Since we are about to re-discover call-clobbered
1181 variables, clear the call-clobbered flag. Variables that
1182 are intrinsically call-clobbered (globals, local statics,
1183 etc) will not be marked by the aliasing code, so we can't
1184 remove them from CALL_CLOBBERED_VARS.
1186 NB: STRUCT_FIELDS are still call clobbered if they are for
1187 a global variable, so we *don't* clear their call clobberedness
1188 just because they are tags, though we will clear it if they
1189 aren't for global variables. */
1190 if (TREE_CODE (var) == NAME_MEMORY_TAG
1191 || TREE_CODE (var) == SYMBOL_MEMORY_TAG
1192 || !is_global_var (var))
1193 clear_call_clobbered (var);
1196 /* Clear flow-sensitive points-to information from each SSA name. */
1197 for (i = 1; i < num_ssa_names; i++)
1199 tree name = ssa_name (i);
1201 if (!name || !POINTER_TYPE_P (TREE_TYPE (name)))
1204 if (SSA_NAME_PTR_INFO (name))
1206 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name);
1208 /* Clear all the flags but keep the name tag to
1209 avoid creating new temporaries unnecessarily. If
1210 this pointer is found to point to a subset or
1211 superset of its former points-to set, then a new
1212 tag will need to be created in create_name_tags. */
1213 pi->pt_anything = 0;
1215 pi->value_escapes_p = 0;
1216 pi->is_dereferenced = 0;
1218 bitmap_clear (pi->pt_vars);
1224 /* If this is the first time we compute aliasing information,
1225 every non-register symbol will need to be put into SSA form
1226 (the initial SSA form only operates on GIMPLE registers). */
1227 FOR_EACH_REFERENCED_VAR (var, rvi)
1228 if (!is_gimple_reg (var))
1229 mark_sym_for_renaming (var);
1232 /* Next time, we will need to reset alias information. */
1233 cfun->gimple_df->aliases_computed_p = true;
1234 bitmap_obstack_initialize (&alias_bitmap_obstack);
1240 /* Deallocate memory used by alias analysis. */
1243 delete_alias_info (struct alias_info *ai)
1247 sbitmap_free (ai->ssa_names_visited);
1249 VEC_free (tree, heap, ai->processed_ptrs);
1251 for (i = 0; i < ai->num_addressable_vars; i++)
1252 free (ai->addressable_vars[i]);
1253 free (ai->addressable_vars);
1255 for (i = 0; i < ai->num_pointers; i++)
1256 free (ai->pointers[i]);
1257 free (ai->pointers);
1259 pointer_set_destroy (ai->written_vars);
1260 pointer_set_destroy (ai->dereferenced_ptrs_store);
1261 pointer_set_destroy (ai->dereferenced_ptrs_load);
1264 delete_points_to_sets ();
1267 /* Used for hashing to identify pointer infos with identical
1270 eq_ptr_info (const void *p1, const void *p2)
1272 const struct ptr_info_def *n1 = (const struct ptr_info_def *) p1;
1273 const struct ptr_info_def *n2 = (const struct ptr_info_def *) p2;
1274 return bitmap_equal_p (n1->pt_vars, n2->pt_vars);
1278 ptr_info_hash (const void *p)
1280 const struct ptr_info_def *n = (const struct ptr_info_def *) p;
1281 return bitmap_hash (n->pt_vars);
1284 /* Create name tags for all the pointers that have been dereferenced.
1285 We only create a name tag for a pointer P if P is found to point to
1286 a set of variables (so that we can alias them to *P) or if it is
1287 the result of a call to malloc (which means that P cannot point to
1288 anything else nor alias any other variable).
1290 If two pointers P and Q point to the same set of variables, they
1291 are assigned the same name tag. */
1294 create_name_tags (void)
1297 VEC (tree, heap) *with_ptvars = NULL;
1301 /* Collect the list of pointers with a non-empty points to set. */
1302 for (i = 1; i < num_ssa_names; i++)
1304 tree ptr = ssa_name (i);
1305 struct ptr_info_def *pi;
1308 || !POINTER_TYPE_P (TREE_TYPE (ptr))
1309 || !SSA_NAME_PTR_INFO (ptr))
1312 pi = SSA_NAME_PTR_INFO (ptr);
1314 if (pi->pt_anything || !pi->is_dereferenced)
1316 /* No name tags for pointers that have not been
1317 dereferenced or point to an arbitrary location. */
1318 pi->name_mem_tag = NULL_TREE;
1322 /* Set pt_anything on the pointers without pt_vars filled in so
1323 that they are assigned a symbol tag. */
1324 if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
1325 VEC_safe_push (tree, heap, with_ptvars, ptr);
1327 set_pt_anything (ptr);
1330 /* If we didn't find any pointers with pt_vars set, we're done. */
1334 ptr_hash = htab_create (10, ptr_info_hash, eq_ptr_info, NULL);
1335 /* Now go through the pointers with pt_vars, and find a name tag
1336 with the same pt_vars as this pointer, or create one if one
1338 for (i = 0; VEC_iterate (tree, with_ptvars, i, ptr); i++)
1340 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
1341 tree old_name_tag = pi->name_mem_tag;
1342 struct ptr_info_def **slot;
1344 /* If PTR points to a set of variables, check if we don't
1345 have another pointer Q with the same points-to set before
1346 creating a tag. If so, use Q's tag instead of creating a
1349 This is important for not creating unnecessary symbols
1350 and also for copy propagation. If we ever need to
1351 propagate PTR into Q or vice-versa, we would run into
1352 problems if they both had different name tags because
1353 they would have different SSA version numbers (which
1354 would force us to take the name tags in and out of SSA). */
1356 slot = (struct ptr_info_def **) htab_find_slot (ptr_hash, pi, INSERT);
1358 pi->name_mem_tag = (*slot)->name_mem_tag;
1362 /* If we didn't find a pointer with the same points-to set
1363 as PTR, create a new name tag if needed. */
1364 if (pi->name_mem_tag == NULL_TREE)
1365 pi->name_mem_tag = get_nmt_for (ptr);
1368 /* If the new name tag computed for PTR is different than
1369 the old name tag that it used to have, then the old tag
1370 needs to be removed from the IL, so we mark it for
1372 if (old_name_tag && old_name_tag != pi->name_mem_tag)
1373 mark_sym_for_renaming (old_name_tag);
1375 TREE_THIS_VOLATILE (pi->name_mem_tag)
1376 |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
1378 /* Mark the new name tag for renaming. */
1379 mark_sym_for_renaming (pi->name_mem_tag);
1381 htab_delete (ptr_hash);
1383 VEC_free (tree, heap, with_ptvars);
1386 /* Union the alias set SET into the may-aliases for TAG */
1389 union_alias_set_into (tree tag, bitmap set)
1391 bitmap ma = MTAG_ALIASES (tag);
1393 if (bitmap_empty_p (set))
1397 ma = MTAG_ALIASES (tag) = BITMAP_ALLOC (&alias_bitmap_obstack);
1398 bitmap_ior_into (ma, set);
1402 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
1403 the name memory tag (NMT) associated with P_i. If P_i escapes, then its
1404 name tag and the variables it points-to are call-clobbered. Finally, if
1405 P_i escapes and we could not determine where it points to, then all the
1406 variables in the same alias set as *P_i are marked call-clobbered. This
1407 is necessary because we must assume that P_i may take the address of any
1408 variable in the same alias set. */
1411 compute_flow_sensitive_aliasing (struct alias_info *ai)
1418 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
1420 if (!find_what_p_points_to (ptr))
1421 set_pt_anything (ptr);
1424 create_name_tags ();
1426 for (i = 0; VEC_iterate (tree, ai->processed_ptrs, i, ptr); i++)
1428 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
1429 tree tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
1431 /* Set up aliasing information for PTR's name memory tag (if it has
1432 one). Note that only pointers that have been dereferenced will
1433 have a name memory tag. */
1434 if (pi->name_mem_tag && pi->pt_vars)
1436 if (!bitmap_empty_p (pi->pt_vars))
1438 union_alias_set_into (pi->name_mem_tag, pi->pt_vars);
1439 union_alias_set_into (tag, pi->pt_vars);
1440 bitmap_clear_bit (MTAG_ALIASES (tag), DECL_UID (tag));
1442 /* It may be the case that this the tag uid was the only
1443 bit we had set in the aliases list, and in this case,
1444 we don't want to keep an empty bitmap, as this
1445 asserts in tree-ssa-operands.c . */
1446 if (bitmap_empty_p (MTAG_ALIASES (tag)))
1447 BITMAP_FREE (MTAG_ALIASES (tag));
1454 /* Return TRUE if at least one symbol in TAG2's alias set is also
1455 present in TAG1's alias set. */
1458 have_common_aliases_p (bitmap tag1aliases, bitmap tag2aliases)
1461 /* This is the old behavior of have_common_aliases_p, which is to
1462 return false if both sets are empty, or one set is and the other
1464 if ((tag1aliases == NULL && tag2aliases != NULL)
1465 || (tag2aliases == NULL && tag1aliases != NULL)
1466 || (tag1aliases == NULL && tag2aliases == NULL))
1469 return bitmap_intersect_p (tag1aliases, tag2aliases);
1472 /* Compute type-based alias sets. Traverse all the pointers and
1473 addressable variables found in setup_pointers_and_addressables.
1475 For every pointer P in AI->POINTERS and addressable variable V in
1476 AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
1477 memory tag (SMT) if their alias sets conflict. V is then marked as
1478 an aliased symbol so that the operand scanner knows that statements
1479 containing V have aliased operands. */
1482 compute_flow_insensitive_aliasing (struct alias_info *ai)
1486 /* For every pointer P, determine which addressable variables may alias
1487 with P's symbol memory tag. */
1488 for (i = 0; i < ai->num_pointers; i++)
1491 struct alias_map_d *p_map = ai->pointers[i];
1492 tree tag = symbol_mem_tag (p_map->var);
1495 /* Call-clobbering information is not finalized yet at this point. */
1496 if (PTR_IS_REF_ALL (p_map->var))
1499 for (j = 0; j < ai->num_addressable_vars; j++)
1501 struct alias_map_d *v_map;
1503 bool tag_stored_p, var_stored_p;
1505 v_map = ai->addressable_vars[j];
1507 v_ann = var_ann (var);
1509 /* Skip memory tags and variables that have never been
1510 written to. We also need to check if the variables are
1511 call-clobbered because they may be overwritten by
1513 tag_stored_p = pointer_set_contains (ai->written_vars, tag)
1514 || is_call_clobbered (tag);
1515 var_stored_p = pointer_set_contains (ai->written_vars, var)
1516 || is_call_clobbered (var);
1517 if (!tag_stored_p && !var_stored_p)
1520 if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false))
1522 /* We should never have a var with subvars here, because
1523 they shouldn't get into the set of addressable vars */
1524 gcc_assert (!var_can_have_subvars (var)
1525 || get_subvars_for_var (var) == NULL);
1527 /* Add VAR to TAG's may-aliases set. */
1528 add_may_alias (tag, var);
1533 /* Since this analysis is based exclusively on symbols, it fails to
1534 handle cases where two pointers P and Q have different memory
1535 tags with conflicting alias set numbers but no aliased symbols in
1538 For example, suppose that we have two memory tags SMT.1 and SMT.2
1541 may-aliases (SMT.1) = { a }
1542 may-aliases (SMT.2) = { b }
1544 and the alias set number of SMT.1 conflicts with that of SMT.2.
1545 Since they don't have symbols in common, loads and stores from
1546 SMT.1 and SMT.2 will seem independent of each other, which will
1547 lead to the optimizers making invalid transformations (see
1548 testsuite/gcc.c-torture/execute/pr15262-[12].c).
1550 To avoid this problem, we do a final traversal of AI->POINTERS
1551 looking for pairs of pointers that have no aliased symbols in
1552 common and yet have conflicting alias set numbers. */
1553 for (i = 0; i < ai->num_pointers; i++)
1556 struct alias_map_d *p_map1 = ai->pointers[i];
1557 tree tag1 = symbol_mem_tag (p_map1->var);
1558 bitmap may_aliases1 = MTAG_ALIASES (tag1);
1560 if (PTR_IS_REF_ALL (p_map1->var))
1563 for (j = i + 1; j < ai->num_pointers; j++)
1565 struct alias_map_d *p_map2 = ai->pointers[j];
1566 tree tag2 = symbol_mem_tag (p_map2->var);
1567 bitmap may_aliases2 = may_aliases (tag2);
1569 if (PTR_IS_REF_ALL (p_map2->var))
1572 /* If the pointers may not point to each other, do nothing. */
1573 if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true))
1576 /* The two pointers may alias each other. If they already have
1577 symbols in common, do nothing. */
1578 if (have_common_aliases_p (may_aliases1, may_aliases2))
1581 if (may_aliases2 && !bitmap_empty_p (may_aliases2))
1583 union_alias_set_into (tag1, may_aliases2);
1587 /* Since TAG2 does not have any aliases of its own, add
1588 TAG2 itself to the alias set of TAG1. */
1589 add_may_alias (tag1, tag2);
1597 /* Finalize may-alias information for ref-all pointers. Traverse all
1598 the addressable variables found in setup_pointers_and_addressables.
1600 If flow-sensitive alias analysis has attached a name memory tag to
1601 a ref-all pointer, we will use it for the dereferences because that
1602 will have more precise aliasing information. But if there is no
1603 name tag, we will use a special symbol tag that aliases all the
1604 call-clobbered addressable variables. */
1607 finalize_ref_all_pointers (struct alias_info *ai)
1611 /* First add the real call-clobbered variables. */
1612 for (i = 0; i < ai->num_addressable_vars; i++)
1614 tree var = ai->addressable_vars[i]->var;
1615 if (is_call_clobbered (var))
1616 add_may_alias (ai->ref_all_symbol_mem_tag, var);
1619 /* Then add the call-clobbered pointer memory tags. See
1620 compute_flow_insensitive_aliasing for the rationale. */
1621 for (i = 0; i < ai->num_pointers; i++)
1623 tree ptr = ai->pointers[i]->var, tag;
1624 if (PTR_IS_REF_ALL (ptr))
1626 tag = symbol_mem_tag (ptr);
1627 if (is_call_clobbered (tag))
1628 add_may_alias (ai->ref_all_symbol_mem_tag, tag);
1634 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */
1637 create_alias_map_for (tree var, struct alias_info *ai)
1639 struct alias_map_d *alias_map;
1640 alias_map = XCNEW (struct alias_map_d);
1641 alias_map->var = var;
1642 alias_map->set = get_alias_set (var);
1643 ai->addressable_vars[ai->num_addressable_vars++] = alias_map;
1647 /* Create memory tags for all the dereferenced pointers and build the
1648 ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
1649 sets. Based on the address escape and points-to information collected
1650 earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
1651 variables whose address is not needed anymore. */
1654 setup_pointers_and_addressables (struct alias_info *ai)
1656 size_t num_addressable_vars, num_pointers;
1657 referenced_var_iterator rvi;
1659 VEC (tree, heap) *varvec = NULL;
1660 safe_referenced_var_iterator srvi;
1662 /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
1663 num_addressable_vars = num_pointers = 0;
1665 FOR_EACH_REFERENCED_VAR (var, rvi)
1667 if (may_be_aliased (var))
1668 num_addressable_vars++;
1670 if (POINTER_TYPE_P (TREE_TYPE (var)))
1672 /* Since we don't keep track of volatile variables, assume that
1673 these pointers are used in indirect store operations. */
1674 if (TREE_THIS_VOLATILE (var))
1675 pointer_set_insert (ai->dereferenced_ptrs_store, var);
1681 /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
1682 always going to be slightly bigger than we actually need them
1683 because some TREE_ADDRESSABLE variables will be marked
1684 non-addressable below and only pointers with unique symbol tags are
1685 going to be added to POINTERS. */
1686 ai->addressable_vars = XCNEWVEC (struct alias_map_d *, num_addressable_vars);
1687 ai->pointers = XCNEWVEC (struct alias_map_d *, num_pointers);
1688 ai->num_addressable_vars = 0;
1689 ai->num_pointers = 0;
1691 FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, srvi)
1695 /* Name memory tags already have flow-sensitive aliasing
1696 information, so they need not be processed by
1697 compute_flow_insensitive_aliasing. Similarly, symbol memory
1698 tags are already accounted for when we process their
1701 Structure fields, on the other hand, have to have some of this
1702 information processed for them, but it's pointless to mark them
1703 non-addressable (since they are fake variables anyway). */
1704 if (MTAG_P (var) && TREE_CODE (var) != STRUCT_FIELD_TAG)
1707 /* Remove the ADDRESSABLE flag from every addressable variable whose
1708 address is not needed anymore. This is caused by the propagation
1709 of ADDR_EXPR constants into INDIRECT_REF expressions and the
1710 removal of dead pointer assignments done by the early scalar
1712 if (TREE_ADDRESSABLE (var))
1714 if (!bitmap_bit_p (gimple_addressable_vars (cfun), DECL_UID (var))
1715 && TREE_CODE (var) != RESULT_DECL
1716 && !is_global_var (var))
1718 bool okay_to_mark = true;
1720 /* Since VAR is now a regular GIMPLE register, we will need
1721 to rename VAR into SSA afterwards. */
1722 mark_sym_for_renaming (var);
1724 /* If VAR can have sub-variables, and any of its
1725 sub-variables has its address taken, then we cannot
1726 remove the addressable flag from VAR. */
1727 if (var_can_have_subvars (var)
1728 && (svars = get_subvars_for_var (var)))
1732 for (sv = svars; sv; sv = sv->next)
1734 if (bitmap_bit_p (gimple_addressable_vars (cfun),
1735 DECL_UID (sv->var)))
1736 okay_to_mark = false;
1737 mark_sym_for_renaming (sv->var);
1741 /* The address of VAR is not needed, remove the
1742 addressable bit, so that it can be optimized as a
1743 regular variable. */
1746 /* The memory partition holding VAR will no longer
1747 contain VAR, and statements referencing it will need
1749 if (memory_partition (var))
1750 mark_sym_for_renaming (memory_partition (var));
1752 mark_non_addressable (var);
1757 /* Global variables and addressable locals may be aliased. Create an
1758 entry in ADDRESSABLE_VARS for VAR. */
1759 if (may_be_aliased (var))
1761 if (!var_can_have_subvars (var)
1762 || get_subvars_for_var (var) == NULL)
1763 create_alias_map_for (var, ai);
1765 mark_sym_for_renaming (var);
1768 /* Add pointer variables that have been dereferenced to the POINTERS
1769 array and create a symbol memory tag for them. */
1770 if (POINTER_TYPE_P (TREE_TYPE (var)))
1772 if ((pointer_set_contains (ai->dereferenced_ptrs_store, var)
1773 || pointer_set_contains (ai->dereferenced_ptrs_load, var)))
1778 /* If pointer VAR still doesn't have a memory tag
1779 associated with it, create it now or re-use an
1781 tag = get_smt_for (var, ai);
1782 t_ann = var_ann (tag);
1784 /* The symbol tag will need to be renamed into SSA
1785 afterwards. Note that we cannot do this inside
1786 get_smt_for because aliasing may run multiple times
1787 and we only create symbol tags the first time. */
1788 mark_sym_for_renaming (tag);
1790 /* Similarly, if pointer VAR used to have another type
1791 tag, we will need to process it in the renamer to
1792 remove the stale virtual operands. */
1793 old_tag = symbol_mem_tag (var);
1795 mark_sym_for_renaming (old_tag);
1797 /* Associate the tag with pointer VAR. */
1798 set_symbol_mem_tag (var, tag);
1800 /* If pointer VAR has been used in a store operation,
1801 then its memory tag must be marked as written-to. */
1802 if (pointer_set_contains (ai->dereferenced_ptrs_store, var))
1803 pointer_set_insert (ai->written_vars, tag);
1807 /* The pointer has not been dereferenced. If it had a
1808 symbol memory tag, remove it and mark the old tag for
1809 renaming to remove it out of the IL. */
1810 tree tag = symbol_mem_tag (var);
1813 mark_sym_for_renaming (tag);
1814 set_symbol_mem_tag (var, NULL_TREE);
1820 VEC_free (tree, heap, varvec);
1824 /* Determine whether to use .GLOBAL_VAR to model call clobbering
1825 semantics. If the function makes no references to global
1826 variables and contains at least one call to a non-pure function,
1827 then we need to mark the side-effects of the call using .GLOBAL_VAR
1828 to represent all possible global memory referenced by the callee. */
1831 maybe_create_global_var (struct alias_info *ai)
1833 /* No need to create it, if we have one already. */
1834 if (gimple_global_var (cfun) == NULL_TREE)
1836 /* Create .GLOBAL_VAR if there are no call-clobbered
1837 variables and the program contains a mixture of pure/const
1838 and regular function calls. This is to avoid the problem
1839 described in PR 20115:
1842 int func_pure (void) { return X; }
1843 int func_non_pure (int a) { X += a; }
1846 int a = func_pure ();
1852 Since foo() has no call-clobbered variables, there is
1853 no relationship between the calls to func_pure and
1854 func_non_pure. Since func_pure has no side-effects, value
1855 numbering optimizations elide the second call to func_pure.
1856 So, if we have some pure/const and some regular calls in the
1857 program we create .GLOBAL_VAR to avoid missing these
1859 if (bitmap_count_bits (gimple_call_clobbered_vars (cfun)) == 0
1860 && ai->num_calls_found > 0
1861 && ai->num_pure_const_calls_found > 0
1862 && ai->num_calls_found > ai->num_pure_const_calls_found)
1863 create_global_var ();
1868 /* Return TRUE if pointer PTR may point to variable VAR.
1870 MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
1871 This is needed because when checking for type conflicts we are
1872 interested in the alias set of the memory location pointed-to by
1873 PTR. The alias set of PTR itself is irrelevant.
1875 VAR_ALIAS_SET is the alias set for VAR. */
1878 may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
1879 tree var, HOST_WIDE_INT var_alias_set,
1880 bool alias_set_only)
1884 alias_stats.alias_queries++;
1885 alias_stats.simple_queries++;
1887 /* By convention, a variable cannot alias itself. */
1888 mem = symbol_mem_tag (ptr);
1891 alias_stats.alias_noalias++;
1892 alias_stats.simple_resolved++;
1896 /* If -fargument-noalias-global is > 2, pointer arguments may
1897 not point to anything else. */
1898 if (flag_argument_noalias > 2 && TREE_CODE (ptr) == PARM_DECL)
1900 alias_stats.alias_noalias++;
1901 alias_stats.simple_resolved++;
1905 /* If -fargument-noalias-global is > 1, pointer arguments may
1906 not point to global variables. */
1907 if (flag_argument_noalias > 1 && is_global_var (var)
1908 && TREE_CODE (ptr) == PARM_DECL)
1910 alias_stats.alias_noalias++;
1911 alias_stats.simple_resolved++;
1915 /* If either MEM or VAR is a read-only global and the other one
1916 isn't, then PTR cannot point to VAR. */
1917 if ((unmodifiable_var_p (mem) && !unmodifiable_var_p (var))
1918 || (unmodifiable_var_p (var) && !unmodifiable_var_p (mem)))
1920 alias_stats.alias_noalias++;
1921 alias_stats.simple_resolved++;
1925 gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
1927 alias_stats.tbaa_queries++;
1929 /* If the alias sets don't conflict then MEM cannot alias VAR. */
1930 if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
1932 alias_stats.alias_noalias++;
1933 alias_stats.tbaa_resolved++;
1937 /* If VAR is a record or union type, PTR cannot point into VAR
1938 unless there is some explicit address operation in the
1939 program that can reference a field of the type pointed-to by PTR.
1940 This also assumes that the types of both VAR and PTR are
1941 contained within the compilation unit, and that there is no fancy
1942 addressing arithmetic associated with any of the types
1944 if (mem_alias_set != 0 && var_alias_set != 0)
1946 tree ptr_type = TREE_TYPE (ptr);
1947 tree var_type = TREE_TYPE (var);
1949 /* The star count is -1 if the type at the end of the pointer_to
1950 chain is not a record or union type. */
1951 if ((!alias_set_only) &&
1952 ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
1954 int ptr_star_count = 0;
1956 /* ipa_type_escape_star_count_of_interesting_type is a
1957 little too restrictive for the pointer type, need to
1958 allow pointers to primitive types as long as those types
1959 cannot be pointers to everything. */
1960 while (POINTER_TYPE_P (ptr_type))
1962 /* Strip the *s off. */
1963 ptr_type = TREE_TYPE (ptr_type);
1967 /* There does not appear to be a better test to see if the
1968 pointer type was one of the pointer to everything
1970 if (ptr_star_count > 0)
1972 alias_stats.structnoaddress_queries++;
1973 if (ipa_type_escape_field_does_not_clobber_p (var_type,
1976 alias_stats.structnoaddress_resolved++;
1977 alias_stats.alias_noalias++;
1981 else if (ptr_star_count == 0)
1983 /* If PTR_TYPE was not really a pointer to type, it cannot
1985 alias_stats.structnoaddress_queries++;
1986 alias_stats.structnoaddress_resolved++;
1987 alias_stats.alias_noalias++;
1993 alias_stats.alias_mayalias++;
1998 /* Add ALIAS to the set of variables that may alias VAR. */
2001 add_may_alias (tree var, tree alias)
2004 /* Don't allow self-referential aliases. */
2005 gcc_assert (var != alias);
2007 /* ALIAS must be addressable if it's being added to an alias set. */
2009 TREE_ADDRESSABLE (alias) = 1;
2011 gcc_assert (may_be_aliased (alias));
2014 /* VAR must be a symbol or a name tag. */
2015 gcc_assert (TREE_CODE (var) == SYMBOL_MEMORY_TAG
2016 || TREE_CODE (var) == NAME_MEMORY_TAG);
2018 if (MTAG_ALIASES (var) == NULL)
2019 MTAG_ALIASES (var) = BITMAP_ALLOC (&alias_bitmap_obstack);
2021 bitmap_set_bit (MTAG_ALIASES (var), DECL_UID (alias));
2025 /* Mark pointer PTR as pointing to an arbitrary memory location. */
2028 set_pt_anything (tree ptr)
2030 struct ptr_info_def *pi = get_ptr_info (ptr);
2032 pi->pt_anything = 1;
2035 /* The pointer used to have a name tag, but we now found it pointing
2036 to an arbitrary location. The name tag needs to be renamed and
2037 disassociated from PTR. */
2038 if (pi->name_mem_tag)
2040 mark_sym_for_renaming (pi->name_mem_tag);
2041 pi->name_mem_tag = NULL_TREE;
2046 /* Return true if STMT is an "escape" site from the current function. Escape
2047 sites those statements which might expose the address of a variable
2048 outside the current function. STMT is an escape site iff:
2050 1- STMT is a function call, or
2051 2- STMT is an __asm__ expression, or
2052 3- STMT is an assignment to a non-local variable, or
2053 4- STMT is a return statement.
2055 Return the type of escape site found, if we found one, or NO_ESCAPE
2059 is_escape_site (tree stmt)
2061 tree call = get_call_expr_in (stmt);
2062 if (call != NULL_TREE)
2064 if (!TREE_SIDE_EFFECTS (call))
2065 return ESCAPE_TO_PURE_CONST;
2067 return ESCAPE_TO_CALL;
2069 else if (TREE_CODE (stmt) == ASM_EXPR)
2070 return ESCAPE_TO_ASM;
2071 else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
2073 tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
2075 /* Get to the base of _REF nodes. */
2076 if (TREE_CODE (lhs) != SSA_NAME)
2077 lhs = get_base_address (lhs);
2079 /* If we couldn't recognize the LHS of the assignment, assume that it
2080 is a non-local store. */
2081 if (lhs == NULL_TREE)
2082 return ESCAPE_UNKNOWN;
2084 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == NOP_EXPR
2085 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == CONVERT_EXPR
2086 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == VIEW_CONVERT_EXPR)
2089 = TREE_TYPE (TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt, 1), 0));
2090 tree to = TREE_TYPE (GIMPLE_STMT_OPERAND (stmt, 1));
2092 /* If the RHS is a conversion between a pointer and an integer, the
2093 pointer escapes since we can't track the integer. */
2094 if (POINTER_TYPE_P (from) && !POINTER_TYPE_P (to))
2095 return ESCAPE_BAD_CAST;
2097 /* Same if the RHS is a conversion between a regular pointer and a
2098 ref-all pointer since we can't track the SMT of the former. */
2099 if (POINTER_TYPE_P (from) && !TYPE_REF_CAN_ALIAS_ALL (from)
2100 && POINTER_TYPE_P (to) && TYPE_REF_CAN_ALIAS_ALL (to))
2101 return ESCAPE_BAD_CAST;
2104 /* If the LHS is an SSA name, it can't possibly represent a non-local
2106 if (TREE_CODE (lhs) == SSA_NAME)
2109 /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
2110 local variables we cannot be sure if it will escape, because we
2111 don't have information about objects not in SSA form. Need to
2112 implement something along the lines of
2114 J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
2115 Midkiff, ``Escape analysis for java,'' in Proceedings of the
2116 Conference on Object-Oriented Programming Systems, Languages, and
2117 Applications (OOPSLA), pp. 1-19, 1999. */
2118 return ESCAPE_STORED_IN_GLOBAL;
2120 else if (TREE_CODE (stmt) == RETURN_EXPR)
2121 return ESCAPE_TO_RETURN;
2126 /* Create a new memory tag of type TYPE.
2127 Does NOT push it into the current binding. */
2130 create_tag_raw (enum tree_code code, tree type, const char *prefix)
2134 tmp_var = build_decl (code, create_tmp_var_name (prefix), type);
2136 /* Make the variable writable. */
2137 TREE_READONLY (tmp_var) = 0;
2139 /* It doesn't start out global. */
2140 MTAG_GLOBAL (tmp_var) = 0;
2141 TREE_STATIC (tmp_var) = 0;
2142 TREE_USED (tmp_var) = 1;
2147 /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
2148 is considered to represent all the pointers whose pointed-to types are
2149 in the same alias set class. Otherwise, the tag represents a single
2150 SSA_NAME pointer variable. */
2153 create_memory_tag (tree type, bool is_type_tag)
2155 tree tag = create_tag_raw (is_type_tag ? SYMBOL_MEMORY_TAG : NAME_MEMORY_TAG,
2156 type, (is_type_tag) ? "SMT" : "NMT");
2158 /* By default, memory tags are local variables. Alias analysis will
2159 determine whether they should be considered globals. */
2160 DECL_CONTEXT (tag) = current_function_decl;
2162 /* Memory tags are by definition addressable. */
2163 TREE_ADDRESSABLE (tag) = 1;
2165 set_symbol_mem_tag (tag, NULL_TREE);
2167 /* Add the tag to the symbol table. */
2168 add_referenced_var (tag);
2174 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
2175 This is used if P_i has been found to point to a specific set of
2176 variables or to a non-aliased memory location like the address returned
2177 by malloc functions. */
2180 get_nmt_for (tree ptr)
2182 struct ptr_info_def *pi = get_ptr_info (ptr);
2183 tree tag = pi->name_mem_tag;
2185 if (tag == NULL_TREE)
2186 tag = create_memory_tag (TREE_TYPE (TREE_TYPE (ptr)), false);
2191 /* Return the symbol memory tag associated to pointer PTR. A memory
2192 tag is an artificial variable that represents the memory location
2193 pointed-to by PTR. It is used to model the effects of pointer
2194 de-references on addressable variables.
2196 AI points to the data gathered during alias analysis. This
2197 function populates the array AI->POINTERS. */
2200 get_smt_for (tree ptr, struct alias_info *ai)
2204 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2205 HOST_WIDE_INT tag_set = get_alias_set (tag_type);
2207 /* We use a unique memory tag for all the ref-all pointers. */
2208 if (PTR_IS_REF_ALL (ptr))
2210 if (!ai->ref_all_symbol_mem_tag)
2211 ai->ref_all_symbol_mem_tag = create_memory_tag (void_type_node, true);
2212 return ai->ref_all_symbol_mem_tag;
2215 /* To avoid creating unnecessary memory tags, only create one memory tag
2216 per alias set class. Note that it may be tempting to group
2217 memory tags based on conflicting alias sets instead of
2218 equivalence. That would be wrong because alias sets are not
2219 necessarily transitive (as demonstrated by the libstdc++ test
2220 23_containers/vector/cons/4.cc). Given three alias sets A, B, C
2221 such that conflicts (A, B) == true and conflicts (A, C) == true,
2222 it does not necessarily follow that conflicts (B, C) == true. */
2223 for (i = 0, tag = NULL_TREE; i < ai->num_pointers; i++)
2225 struct alias_map_d *curr = ai->pointers[i];
2226 tree curr_tag = symbol_mem_tag (curr->var);
2227 if (tag_set == curr->set)
2234 /* If VAR cannot alias with any of the existing memory tags, create a new
2235 tag for PTR and add it to the POINTERS array. */
2236 if (tag == NULL_TREE)
2238 struct alias_map_d *alias_map;
2240 /* If PTR did not have a symbol tag already, create a new SMT.*
2241 artificial variable representing the memory location
2242 pointed-to by PTR. */
2243 tag = symbol_mem_tag (ptr);
2244 if (tag == NULL_TREE)
2245 tag = create_memory_tag (tag_type, true);
2247 /* Add PTR to the POINTERS array. Note that we are not interested in
2248 PTR's alias set. Instead, we cache the alias set for the memory that
2250 alias_map = XCNEW (struct alias_map_d);
2251 alias_map->var = ptr;
2252 alias_map->set = tag_set;
2253 ai->pointers[ai->num_pointers++] = alias_map;
2256 /* If the pointed-to type is volatile, so is the tag. */
2257 TREE_THIS_VOLATILE (tag) |= TREE_THIS_VOLATILE (tag_type);
2259 /* Make sure that the symbol tag has the same alias set as the
2261 gcc_assert (tag_set == get_alias_set (tag));
2267 /* Create GLOBAL_VAR, an artificial global variable to act as a
2268 representative of all the variables that may be clobbered by function
2272 create_global_var (void)
2274 tree global_var = build_decl (VAR_DECL, get_identifier (".GLOBAL_VAR"),
2276 DECL_ARTIFICIAL (global_var) = 1;
2277 TREE_READONLY (global_var) = 0;
2278 DECL_EXTERNAL (global_var) = 1;
2279 TREE_STATIC (global_var) = 1;
2280 TREE_USED (global_var) = 1;
2281 DECL_CONTEXT (global_var) = NULL_TREE;
2282 TREE_THIS_VOLATILE (global_var) = 0;
2283 TREE_ADDRESSABLE (global_var) = 0;
2285 create_var_ann (global_var);
2286 mark_call_clobbered (global_var, ESCAPE_UNKNOWN);
2287 add_referenced_var (global_var);
2288 mark_sym_for_renaming (global_var);
2289 cfun->gimple_df->global_var = global_var;
2293 /* Dump alias statistics on FILE. */
2296 dump_alias_stats (FILE *file)
2298 const char *funcname
2299 = lang_hooks.decl_printable_name (current_function_decl, 2);
2300 fprintf (file, "\nAlias statistics for %s\n\n", funcname);
2301 fprintf (file, "Total alias queries:\t%u\n", alias_stats.alias_queries);
2302 fprintf (file, "Total alias mayalias results:\t%u\n",
2303 alias_stats.alias_mayalias);
2304 fprintf (file, "Total alias noalias results:\t%u\n",
2305 alias_stats.alias_noalias);
2306 fprintf (file, "Total simple queries:\t%u\n",
2307 alias_stats.simple_queries);
2308 fprintf (file, "Total simple resolved:\t%u\n",
2309 alias_stats.simple_resolved);
2310 fprintf (file, "Total TBAA queries:\t%u\n",
2311 alias_stats.tbaa_queries);
2312 fprintf (file, "Total TBAA resolved:\t%u\n",
2313 alias_stats.tbaa_resolved);
2314 fprintf (file, "Total non-addressable structure type queries:\t%u\n",
2315 alias_stats.structnoaddress_queries);
2316 fprintf (file, "Total non-addressable structure type resolved:\t%u\n",
2317 alias_stats.structnoaddress_resolved);
2321 /* Dump alias information on FILE. */
2324 dump_alias_info (FILE *file)
2327 const char *funcname
2328 = lang_hooks.decl_printable_name (current_function_decl, 2);
2329 referenced_var_iterator rvi;
2332 fprintf (file, "\nFlow-insensitive alias information for %s\n\n", funcname);
2334 fprintf (file, "Aliased symbols\n\n");
2336 FOR_EACH_REFERENCED_VAR (var, rvi)
2338 if (may_be_aliased (var))
2339 dump_variable (file, var);
2342 fprintf (file, "\nDereferenced pointers\n\n");
2344 FOR_EACH_REFERENCED_VAR (var, rvi)
2345 if (symbol_mem_tag (var))
2346 dump_variable (file, var);
2348 fprintf (file, "\nSymbol memory tags\n\n");
2350 FOR_EACH_REFERENCED_VAR (var, rvi)
2352 if (TREE_CODE (var) == SYMBOL_MEMORY_TAG)
2353 dump_variable (file, var);
2356 fprintf (file, "\n\nFlow-sensitive alias information for %s\n\n", funcname);
2358 fprintf (file, "SSA_NAME pointers\n\n");
2359 for (i = 1; i < num_ssa_names; i++)
2361 tree ptr = ssa_name (i);
2362 struct ptr_info_def *pi;
2364 if (ptr == NULL_TREE)
2367 pi = SSA_NAME_PTR_INFO (ptr);
2368 if (!SSA_NAME_IN_FREE_LIST (ptr)
2370 && pi->name_mem_tag)
2371 dump_points_to_info_for (file, ptr);
2374 fprintf (file, "\nName memory tags\n\n");
2376 FOR_EACH_REFERENCED_VAR (var, rvi)
2378 if (TREE_CODE (var) == NAME_MEMORY_TAG)
2379 dump_variable (file, var);
2382 dump_memory_partitions (file);
2384 fprintf (file, "\n");
2388 /* Dump alias information on stderr. */
2391 debug_alias_info (void)
2393 dump_alias_info (stderr);
2397 /* Return the alias information associated with pointer T. It creates a
2398 new instance if none existed. */
2400 struct ptr_info_def *
2401 get_ptr_info (tree t)
2403 struct ptr_info_def *pi;
2405 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t)));
2407 pi = SSA_NAME_PTR_INFO (t);
2410 pi = GGC_CNEW (struct ptr_info_def);
2411 SSA_NAME_PTR_INFO (t) = pi;
2418 /* Dump points-to information for SSA_NAME PTR into FILE. */
2421 dump_points_to_info_for (FILE *file, tree ptr)
2423 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
2425 print_generic_expr (file, ptr, dump_flags);
2429 if (pi->name_mem_tag)
2431 fprintf (file, ", name memory tag: ");
2432 print_generic_expr (file, pi->name_mem_tag, dump_flags);
2435 if (pi->is_dereferenced)
2436 fprintf (file, ", is dereferenced");
2438 if (pi->value_escapes_p)
2439 fprintf (file, ", its value escapes");
2441 if (pi->pt_anything)
2442 fprintf (file, ", points-to anything");
2445 fprintf (file, ", points-to NULL");
2449 fprintf (file, ", points-to vars: ");
2450 dump_decl_set (file, pi->pt_vars);
2454 fprintf (file, "\n");
2458 /* Dump points-to information for VAR into stderr. */
2461 debug_points_to_info_for (tree var)
2463 dump_points_to_info_for (stderr, var);
2467 /* Dump points-to information into FILE. NOTE: This function is slow, as
2468 it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
2471 dump_points_to_info (FILE *file)
2474 block_stmt_iterator si;
2477 lang_hooks.decl_printable_name (current_function_decl, 2);
2478 referenced_var_iterator rvi;
2481 fprintf (file, "\n\nPointed-to sets for pointers in %s\n\n", fname);
2483 /* First dump points-to information for the default definitions of
2484 pointer variables. This is necessary because default definitions are
2485 not part of the code. */
2486 FOR_EACH_REFERENCED_VAR (var, rvi)
2488 if (POINTER_TYPE_P (TREE_TYPE (var)))
2490 tree def = gimple_default_def (cfun, var);
2492 dump_points_to_info_for (file, def);
2496 /* Dump points-to information for every pointer defined in the program. */
2501 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2503 tree ptr = PHI_RESULT (phi);
2504 if (POINTER_TYPE_P (TREE_TYPE (ptr)))
2505 dump_points_to_info_for (file, ptr);
2508 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2510 tree stmt = bsi_stmt (si);
2512 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
2513 if (POINTER_TYPE_P (TREE_TYPE (def)))
2514 dump_points_to_info_for (file, def);
2518 fprintf (file, "\n");
2522 /* Dump points-to info pointed to by PTO into STDERR. */
2525 debug_points_to_info (void)
2527 dump_points_to_info (stderr);
2530 /* Dump to FILE the list of variables that may be aliasing VAR. */
2533 dump_may_aliases_for (FILE *file, tree var)
2537 aliases = MTAG_ALIASES (var);
2544 fprintf (file, "{ ");
2545 EXECUTE_IF_SET_IN_BITMAP (aliases, 0, i, bi)
2547 al = referenced_var (i);
2548 print_generic_expr (file, al, dump_flags);
2549 fprintf (file, " ");
2551 fprintf (file, "}");
2556 /* Dump to stderr the list of variables that may be aliasing VAR. */
2559 debug_may_aliases_for (tree var)
2561 dump_may_aliases_for (stderr, var);
2565 /* Return true if VAR may be aliased. */
2568 may_be_aliased (tree var)
2571 if (TREE_ADDRESSABLE (var))
2574 /* Globally visible variables can have their addresses taken by other
2575 translation units. */
2577 && (MTAG_GLOBAL (var) || TREE_PUBLIC (var)))
2579 else if (!MTAG_P (var)
2580 && (DECL_EXTERNAL (var) || TREE_PUBLIC (var)))
2583 /* Automatic variables can't have their addresses escape any other
2584 way. This must be after the check for global variables, as
2585 extern declarations do not have TREE_STATIC set. */
2586 if (!TREE_STATIC (var))
2589 /* If we're in unit-at-a-time mode, then we must have seen all
2590 occurrences of address-of operators, and so we can trust
2591 TREE_ADDRESSABLE. Otherwise we can only be sure the variable
2592 isn't addressable if it's local to the current function. */
2593 if (flag_unit_at_a_time)
2596 if (decl_function_context (var) == current_function_decl)
2603 /* Given two symbols return TRUE if one is in the alias set of the
2607 is_aliased_with (tree tag, tree sym)
2613 aliases = MTAG_ALIASES (tag);
2615 if (aliases == NULL)
2618 return bitmap_bit_p (aliases, DECL_UID (sym));
2622 gcc_assert (MTAG_P (sym));
2623 aliases = MTAG_ALIASES (sym);
2625 if (aliases == NULL)
2628 return bitmap_bit_p (aliases, DECL_UID (tag));
2634 /* The following is based on code in add_stmt_operand to ensure that the
2635 same defs/uses/vdefs/vuses will be found after replacing a reference
2636 to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
2637 is the address of var. Return a memtag for the ptr, after adding the
2638 proper may_aliases to it (which are the aliases of var, if it has any,
2642 add_may_alias_for_new_tag (tree tag, tree var)
2644 bitmap aliases = NULL;
2647 aliases = may_aliases (var);
2649 /* Case 1: |aliases| == 1 */
2650 if (aliases && bitmap_count_bits (aliases) == 1)
2652 tree ali = referenced_var (bitmap_first_set_bit (aliases));
2653 if (TREE_CODE (ali) == SYMBOL_MEMORY_TAG)
2657 /* Case 2: |aliases| == 0 */
2658 if (aliases == NULL)
2659 add_may_alias (tag, var);
2662 /* Case 3: |aliases| > 1 */
2663 union_alias_set_into (tag, aliases);
2668 /* Create a new symbol tag for PTR. Construct the may-alias list of this type
2669 tag so that it has the aliasing of VAR, or of the relevant subvars of VAR
2670 according to the location accessed by EXPR.
2672 Note, the set of aliases represented by the new symbol tag are not marked
2676 new_type_alias (tree ptr, tree var, tree expr)
2678 tree tag_type = TREE_TYPE (TREE_TYPE (ptr));
2681 tree ali = NULL_TREE;
2682 HOST_WIDE_INT offset, size, maxsize;
2684 VEC (tree, heap) *overlaps = NULL;
2688 gcc_assert (symbol_mem_tag (ptr) == NULL_TREE);
2689 gcc_assert (!MTAG_P (var));
2691 ref = get_ref_base_and_extent (expr, &offset, &size, &maxsize);
2694 tag = create_memory_tag (tag_type, true);
2695 set_symbol_mem_tag (ptr, tag);
2697 /* Add VAR to the may-alias set of PTR's new symbol tag. If VAR has
2698 subvars, add the subvars to the tag instead of the actual var. */
2699 if (var_can_have_subvars (ref)
2700 && (svars = get_subvars_for_var (ref)))
2702 for (sv = svars; sv; sv = sv->next)
2706 if (overlap_subvar (offset, maxsize, sv->var, &exact))
2707 VEC_safe_push (tree, heap, overlaps, sv->var);
2709 gcc_assert (overlaps != NULL);
2711 else if (var_can_have_subvars (var)
2712 && (svars = get_subvars_for_var (var)))
2714 /* If the REF is not a direct access to VAR (e.g., it is a dereference
2715 of a pointer), we should scan the virtual operands of REF the same
2716 way as tree-ssa-operands do. At the moment, this is somewhat
2717 difficult, so we just give up and add all the subvars of VAR.
2718 On mem-ssa branch, the scanning for virtual operands have been
2719 split from the rest of tree-ssa-operands, so it should be much
2720 easier to fix this problem correctly once mem-ssa is merged. */
2721 for (sv = svars; sv; sv = sv->next)
2722 VEC_safe_push (tree, heap, overlaps, sv->var);
2724 gcc_assert (overlaps != NULL);
2727 ali = add_may_alias_for_new_tag (tag, var);
2729 len = VEC_length (tree, overlaps);
2732 if (dump_file && (dump_flags & TDF_DETAILS))
2733 fprintf (dump_file, "\nnumber of overlapping subvars = %u\n", len);
2736 ali = add_may_alias_for_new_tag (tag, VEC_index (tree, overlaps, 0));
2742 for (k = 0; VEC_iterate (tree, overlaps, k, sv_var); k++)
2744 ali = add_may_alias_for_new_tag (tag, sv_var);
2748 /* Can happen only if 'Case 1' of add_may_alias_for_new_tag
2749 took place. Since more than one svar was found, we add
2750 'ali' as one of the may_aliases of the new tag. */
2751 add_may_alias (tag, ali);
2756 VEC_free (tree, heap, overlaps);
2759 set_symbol_mem_tag (ptr, ali);
2760 TREE_READONLY (tag) = TREE_READONLY (var);
2761 MTAG_GLOBAL (tag) = is_global_var (var);
2764 /* This represents the used range of a variable. */
2766 typedef struct used_part
2768 HOST_WIDE_INT minused;
2769 HOST_WIDE_INT maxused;
2770 /* True if we have an explicit use/def of some portion of this variable,
2771 even if it is all of it. i.e. a.b = 5 or temp = a.b. */
2773 /* True if we have an implicit use/def of some portion of this
2774 variable. Implicit uses occur when we can't tell what part we
2775 are referencing, and have to make conservative assumptions. */
2777 /* True if the structure is only written to or taken its address. */
2781 /* An array of used_part structures, indexed by variable uid. */
2783 static htab_t used_portions;
2785 struct used_part_map
2791 /* Return true if the uid in the two used part maps are equal. */
2794 used_part_map_eq (const void *va, const void *vb)
2796 const struct used_part_map *a = (const struct used_part_map *) va;
2797 const struct used_part_map *b = (const struct used_part_map *) vb;
2798 return (a->uid == b->uid);
2801 /* Hash a from uid in a used_part_map. */
2804 used_part_map_hash (const void *item)
2806 return ((const struct used_part_map *)item)->uid;
2809 /* Free a used part map element. */
2812 free_used_part_map (void *item)
2814 free (((struct used_part_map *)item)->to);
2818 /* Lookup a used_part structure for a UID. */
2821 up_lookup (unsigned int uid)
2823 struct used_part_map *h, in;
2825 h = (struct used_part_map *) htab_find_with_hash (used_portions, &in, uid);
2831 /* Insert the pair UID, TO into the used part hashtable. */
2834 up_insert (unsigned int uid, used_part_t to)
2836 struct used_part_map *h;
2839 h = XNEW (struct used_part_map);
2842 loc = htab_find_slot_with_hash (used_portions, h,
2846 *(struct used_part_map **) loc = h;
2850 /* Given a variable uid, UID, get or create the entry in the used portions
2851 table for the variable. */
2854 get_or_create_used_part_for (size_t uid)
2857 if ((up = up_lookup (uid)) == NULL)
2859 up = XCNEW (struct used_part);
2860 up->minused = INT_MAX;
2862 up->explicit_uses = false;
2863 up->implicit_uses = false;
2864 up->write_only = true;
2871 /* Create and return a structure sub-variable for field type FIELD at
2872 offset OFFSET, with size SIZE, of variable VAR. */
2875 create_sft (tree var, tree field, unsigned HOST_WIDE_INT offset,
2876 unsigned HOST_WIDE_INT size)
2878 tree subvar = create_tag_raw (STRUCT_FIELD_TAG, field, "SFT");
2880 /* We need to copy the various flags from VAR to SUBVAR, so that
2881 they are is_global_var iff the original variable was. */
2882 DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
2883 MTAG_GLOBAL (subvar) = DECL_EXTERNAL (var);
2884 TREE_PUBLIC (subvar) = TREE_PUBLIC (var);
2885 TREE_STATIC (subvar) = TREE_STATIC (var);
2886 TREE_READONLY (subvar) = TREE_READONLY (var);
2887 TREE_ADDRESSABLE (subvar) = TREE_ADDRESSABLE (var);
2889 /* Add the new variable to REFERENCED_VARS. */
2890 set_symbol_mem_tag (subvar, NULL);
2891 add_referenced_var (subvar);
2892 SFT_PARENT_VAR (subvar) = var;
2893 SFT_OFFSET (subvar) = offset;
2894 SFT_SIZE (subvar) = size;
2899 /* Given an aggregate VAR, create the subvariables that represent its
2903 create_overlap_variables_for (tree var)
2905 VEC(fieldoff_s,heap) *fieldstack = NULL;
2907 size_t uid = DECL_UID (var);
2909 up = up_lookup (uid);
2914 push_fields_onto_fieldstack (TREE_TYPE (var), &fieldstack, 0, NULL);
2915 if (VEC_length (fieldoff_s, fieldstack) != 0)
2919 bool notokay = false;
2922 HOST_WIDE_INT lastfooffset = -1;
2923 HOST_WIDE_INT lastfosize = -1;
2924 tree lastfotype = NULL_TREE;
2926 /* Not all fields have DECL_SIZE set, and those that don't, we don't
2927 know their size, and thus, can't handle.
2928 The same is true of fields with DECL_SIZE that is not an integer
2929 constant (such as variable sized fields).
2930 Fields with offsets which are not constant will have an offset < 0
2931 We *could* handle fields that are constant sized arrays, but
2932 currently don't. Doing so would require some extra changes to
2933 tree-ssa-operands.c. */
2935 for (i = 0; VEC_iterate (fieldoff_s, fieldstack, i, fo); i++)
2938 || TREE_CODE (fo->size) != INTEGER_CST
2947 /* The current heuristic we use is as follows:
2948 If the variable has no used portions in this function, no
2949 structure vars are created for it.
2951 If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
2952 we always create structure vars for them.
2953 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
2954 some explicit uses, we create structure vars for them.
2955 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
2956 no explicit uses, we do not create structure vars for them.
2959 if (fieldcount >= SALIAS_MAX_IMPLICIT_FIELDS
2960 && !up->explicit_uses)
2962 if (dump_file && (dump_flags & TDF_DETAILS))
2964 fprintf (dump_file, "Variable ");
2965 print_generic_expr (dump_file, var, 0);
2966 fprintf (dump_file, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
2971 /* Bail out, if we can't create overlap variables. */
2974 VEC_free (fieldoff_s, heap, fieldstack);
2978 /* Otherwise, create the variables. */
2979 subvars = lookup_subvars_for_var (var);
2981 sort_fieldstack (fieldstack);
2983 for (i = VEC_length (fieldoff_s, fieldstack);
2984 VEC_iterate (fieldoff_s, fieldstack, --i, fo);)
2987 HOST_WIDE_INT fosize;
2990 fosize = TREE_INT_CST_LOW (fo->size);
2991 currfotype = fo->type;
2993 /* If this field isn't in the used portion,
2994 or it has the exact same offset and size as the last
2997 if (((fo->offset <= up->minused
2998 && fo->offset + fosize <= up->minused)
2999 || fo->offset >= up->maxused)
3000 || (fo->offset == lastfooffset
3001 && fosize == lastfosize
3002 && currfotype == lastfotype))
3004 sv = GGC_NEW (struct subvar);
3005 sv->next = *subvars;
3006 sv->var = create_sft (var, fo->type, fo->offset, fosize);
3010 fprintf (dump_file, "structure field tag %s created for var %s",
3011 get_name (sv->var), get_name (var));
3012 fprintf (dump_file, " offset " HOST_WIDE_INT_PRINT_DEC,
3013 SFT_OFFSET (sv->var));
3014 fprintf (dump_file, " size " HOST_WIDE_INT_PRINT_DEC,
3015 SFT_SIZE (sv->var));
3016 fprintf (dump_file, "\n");
3019 lastfotype = currfotype;
3020 lastfooffset = fo->offset;
3021 lastfosize = fosize;
3025 /* Once we have created subvars, the original is no longer call
3026 clobbered on its own. Its call clobbered status depends
3027 completely on the call clobbered status of the subvars.
3029 add_referenced_var in the above loop will take care of
3030 marking subvars of global variables as call clobbered for us
3031 to start, since they are global as well. */
3032 clear_call_clobbered (var);
3035 VEC_free (fieldoff_s, heap, fieldstack);
3039 /* Find the conservative answer to the question of what portions of what
3040 structures are used by this statement. We assume that if we have a
3041 component ref with a known size + offset, that we only need that part
3042 of the structure. For unknown cases, or cases where we do something
3043 to the whole structure, we assume we need to create fields for the
3044 entire structure. */
3047 find_used_portions (tree *tp, int *walk_subtrees, void *lhs_p)
3049 switch (TREE_CODE (*tp))
3051 case GIMPLE_MODIFY_STMT:
3052 /* Recurse manually here to track whether the use is in the
3053 LHS of an assignment. */
3054 find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 0), walk_subtrees, tp);
3055 return find_used_portions (&GIMPLE_STMT_OPERAND (*tp, 1),
3056 walk_subtrees, NULL);
3062 HOST_WIDE_INT bitsize;
3063 HOST_WIDE_INT bitmaxsize;
3064 HOST_WIDE_INT bitpos;
3066 ref = get_ref_base_and_extent (*tp, &bitpos, &bitsize, &bitmaxsize);
3068 && var_can_have_subvars (ref)
3069 && bitmaxsize != -1)
3071 size_t uid = DECL_UID (ref);
3074 up = get_or_create_used_part_for (uid);
3076 if (bitpos <= up->minused)
3077 up->minused = bitpos;
3078 if ((bitpos + bitmaxsize >= up->maxused))
3079 up->maxused = bitpos + bitmaxsize;
3081 if (bitsize == bitmaxsize)
3082 up->explicit_uses = true;
3084 up->implicit_uses = true;
3086 up->write_only = false;
3087 up_insert (uid, up);
3094 /* This is here to make sure we mark the entire base variable as used
3095 when you take its address. Because our used portion analysis is
3096 simple, we aren't looking at casts or pointer arithmetic to see what
3097 happens when you take the address. */
3100 tree var = get_base_address (TREE_OPERAND (*tp, 0));
3105 && var_can_have_subvars (var)
3106 && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3109 size_t uid = DECL_UID (var);
3111 up = get_or_create_used_part_for (uid);
3114 up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
3115 up->implicit_uses = true;
3117 up->write_only = false;
3119 up_insert (uid, up);
3128 for (arg = &TREE_OPERAND (*tp, 1); *arg; arg = &TREE_CHAIN (*arg))
3130 if (TREE_CODE (TREE_VALUE (*arg)) != ADDR_EXPR)
3131 find_used_portions (&TREE_VALUE (*arg), walk_subtrees, NULL);
3142 && var_can_have_subvars (var)
3143 && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3146 size_t uid = DECL_UID (var);
3148 up = get_or_create_used_part_for (uid);
3151 up->maxused = TREE_INT_CST_LOW (DECL_SIZE (var));
3152 up->implicit_uses = true;
3154 up_insert (uid, up);
3168 /* Create structure field variables for structures used in this function. */
3171 create_structure_vars (void)
3174 safe_referenced_var_iterator rvi;
3175 VEC (tree, heap) *varvec = NULL;
3178 used_portions = htab_create (10, used_part_map_hash, used_part_map_eq,
3179 free_used_part_map);
3183 block_stmt_iterator bsi;
3184 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3186 walk_tree_without_duplicates (bsi_stmt_ptr (bsi),
3191 FOR_EACH_REFERENCED_VAR_SAFE (var, varvec, rvi)
3193 /* The C++ FE creates vars without DECL_SIZE set, for some reason. */
3196 && var_can_have_subvars (var)
3198 && TREE_CODE (DECL_SIZE (var)) == INTEGER_CST)
3199 create_overlap_variables_for (var);
3201 htab_delete (used_portions);
3202 VEC_free (tree, heap, varvec);
3204 /* Update SSA operands of statements mentioning variables we split. */
3205 if (gimple_in_ssa_p (cfun))
3208 block_stmt_iterator bsi;
3209 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
3211 tree stmt = bsi_stmt (bsi);
3212 bool update = false;
3216 if (STORED_SYMS (stmt))
3217 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt), 0, i, bi)
3219 tree sym = referenced_var_lookup (i);
3220 if (get_subvars_for_var (sym))
3227 if (LOADED_SYMS (stmt) && !update)
3228 EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt), 0, i, bi)
3230 tree sym = referenced_var_lookup (i);
3231 if (get_subvars_for_var (sym))
3238 if (stmt_ann (stmt)->addresses_taken && !update)
3239 EXECUTE_IF_SET_IN_BITMAP (stmt_ann (stmt)->addresses_taken,
3242 tree sym = referenced_var_lookup (i);
3243 if (get_subvars_for_var (sym))
3259 gate_structure_vars (void)
3261 return flag_tree_salias != 0;
3264 struct tree_opt_pass pass_create_structure_vars =
3266 "salias", /* name */
3267 gate_structure_vars, /* gate */
3268 create_structure_vars, /* execute */
3271 0, /* static_pass_number */
3273 PROP_cfg, /* properties_required */
3274 0, /* properties_provided */
3275 0, /* properties_destroyed */
3276 0, /* todo_flags_start */
3277 TODO_dump_func, /* todo_flags_finish */
3281 /* Reset the call_clobbered flags on our referenced vars. In
3282 theory, this only needs to be done for globals. */
3285 reset_cc_flags (void)
3288 referenced_var_iterator rvi;
3290 FOR_EACH_REFERENCED_VAR (var, rvi)
3291 var_ann (var)->call_clobbered = false;
3295 struct tree_opt_pass pass_reset_cc_flags =
3299 reset_cc_flags, /* execute */
3302 0, /* static_pass_number */
3304 PROP_referenced_vars |PROP_cfg, /* properties_required */
3305 0, /* properties_provided */
3306 0, /* properties_destroyed */
3307 0, /* todo_flags_start */
3308 0, /* todo_flags_finish */