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 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 /* Broad overview of how aliasing works:
54 First we compute points-to sets, which is done in
55 tree-ssa-structalias.c
57 During points-to set constraint finding, a bunch of little bits of
58 information is collected.
59 This is not done because it is necessary for points-to, but because
60 points-to has to walk every statement anyway. The function performing
61 this collecting is update_alias_info.
63 Bits update_alias_info collects include:
64 1. Directly escaping variables and variables whose value escapes
65 (using is_escape_site). This is the set of variables and values that
66 escape prior to transitive closure of the clobbers.
67 2. The set of variables dereferenced on the LHS (into
68 dereferenced_ptr_stores)
69 3. The set of variables dereferenced on the RHS (into
70 dereferenced_ptr_loads)
71 4. The set of all pointers we saw.
72 5. The number of loads and stores for each variable
73 6. The number of statements touching memory
74 7. The set of address taken variables.
77 #1 is computed by a combination of is_escape_site, and counting the
78 number of uses/deref operators. This function properly accounts for
79 situations like &ptr->field, which is *not* a dereference.
81 After points-to sets are computed, the sets themselves still
82 contain points-to specific variables, such as a variable that says
83 the pointer points to anything, a variable that says the pointer
84 points to readonly memory, etc.
86 These are eliminated in a later phase, as we will see.
88 The rest of the phases are located in tree-ssa-alias.c
90 The next phase after points-to set computation is called
91 "setup_pointers_and_addressables"
93 This pass does 3 main things:
95 1. All variables that can have TREE_ADDRESSABLE removed safely (IE
96 non-globals whose address is not taken), have TREE_ADDRESSABLE
98 2. All variables that may be aliased (which is the set of addressable
99 variables and globals) at all, are marked for renaming, and have
100 symbol memory tags created for them.
101 3. All variables which are stored into have their SMT's added to
105 After this function is run, all variables that will ever have an
106 SMT, have one, though its aliases are not filled in.
108 The next phase is to compute flow-insensitive aliasing, which in
109 our case, is a misnomer. it is really computing aliasing that
110 requires no transitive closure to be correct. In particular, it
111 uses stack vs non-stack, TBAA, etc, to determine whether two
112 symbols could *ever* alias . This phase works by going through all
113 the pointers we collected during update_alias_info, and for every
114 addressable variable in the program, seeing if they alias. If so,
115 the addressable variable is added to the symbol memory tag for the
118 As part of this, we handle symbol memory tags that conflict but
119 have no aliases in common, by forcing them to have a symbol in
120 common (through unioning alias sets or adding one as an alias of
121 the other), or by adding one as an alias of another. The case of
122 conflicts with no aliases in common occurs mainly due to aliasing
123 we cannot see. In particular, it generally means we have a load
124 through a pointer whose value came from outside the function.
125 Without an addressable symbol to point to, they would get the wrong
128 After flow insensitive aliasing is computed, we compute name tags
129 (called compute_flow_sensitive_info). We walk each pointer we
130 collected and see if it has a usable points-to set. If so, we
131 generate a name tag using that pointer, and make an alias bitmap for
132 it. Name tags are shared between all things with the same alias
133 bitmap. The alias bitmap will be translated from what points-to
134 computed. In particular, the "anything" variable in points-to will be
135 transformed into a pruned set of SMT's and their aliases that
136 compute_flow_insensitive_aliasing computed.
137 Note that since 4.3, every pointer that points-to computed a solution for
138 will get a name tag (whereas before 4.3, only those whose set did
139 *not* include the anything variable would). At the point where name
140 tags are all assigned, symbol memory tags are dead, and could be
141 deleted, *except* on global variables. Global variables still use
142 symbol memory tags as of right now.
144 After name tags are computed, the set of clobbered variables is
145 transitively closed. In particular, we compute the set of clobbered
146 variables based on the initial set of clobbers, plus the aliases of
147 pointers which either escape, or have their value escape.
149 After this, maybe_create_global_var is run, which handles a corner
150 case where we have no call clobbered variables, but have pure and
153 Staring at this function, I now remember it is a hack for the fact
154 that we do not mark all globals in the program as call clobbered for a
155 function unless they are actually used in that function. Instead, we
156 only mark the set that is actually clobbered. As a result, you can
157 end up with situations where you have no call clobbered vars set.
159 After maybe_create_global_var, we set pointers with the REF_ALL flag
160 to have alias sets that include all clobbered
161 memory tags and variables.
163 After this, memory partitioning is computed (by the function
164 compute_memory_partitions) and alias sets are reworked accordingly.
166 Lastly, we delete partitions with no symbols, and clean up after
169 /* Structure to map a variable to its alias set. */
172 /* Variable and its alias set. */
178 /* Counters used to display statistics on alias analysis. */
181 unsigned int alias_queries
;
182 unsigned int alias_mayalias
;
183 unsigned int alias_noalias
;
184 unsigned int simple_queries
;
185 unsigned int simple_resolved
;
186 unsigned int tbaa_queries
;
187 unsigned int tbaa_resolved
;
188 unsigned int structnoaddress_queries
;
189 unsigned int structnoaddress_resolved
;
193 /* Local variables. */
194 static struct alias_stats_d alias_stats
;
195 static bitmap_obstack alias_bitmap_obstack
;
197 /* Local functions. */
198 static void compute_flow_insensitive_aliasing (struct alias_info
*);
199 static void finalize_ref_all_pointers (struct alias_info
*);
200 static void dump_alias_stats (FILE *);
201 static bool may_alias_p (tree
, HOST_WIDE_INT
, tree
, HOST_WIDE_INT
, bool);
202 static tree
create_memory_tag (tree type
, bool is_type_tag
);
203 static tree
get_smt_for (tree
, struct alias_info
*);
204 static tree
get_nmt_for (tree
);
205 static void add_may_alias (tree
, tree
);
206 static struct alias_info
*init_alias_info (void);
207 static void delete_alias_info (struct alias_info
*);
208 static void compute_flow_sensitive_aliasing (struct alias_info
*);
209 static void setup_pointers_and_addressables (struct alias_info
*);
210 static void create_global_var (void);
211 static void maybe_create_global_var (void);
212 static void set_pt_anything (tree
);
214 void debug_mp_info (VEC(mem_sym_stats_t
,heap
) *);
218 /* Return memory reference stats for symbol VAR. Create a new slot in
219 cfun->gimple_df->mem_sym_stats if needed. */
221 static struct mem_sym_stats_d
*
222 get_mem_sym_stats_for (tree var
)
225 struct mem_sym_stats_d
*stats
;
226 struct pointer_map_t
*map
= gimple_mem_ref_stats (cfun
)->mem_sym_stats
;
230 slot
= pointer_map_insert (map
, var
);
233 stats
= XCNEW (struct mem_sym_stats_d
);
235 *slot
= (void *) stats
;
238 stats
= (struct mem_sym_stats_d
*) *slot
;
244 /* Set MPT to be the memory partition associated with symbol SYM. */
247 set_memory_partition (tree sym
, tree mpt
)
249 #if defined ENABLE_CHECKING
251 gcc_assert (TREE_CODE (mpt
) == MEMORY_PARTITION_TAG
252 && !is_gimple_reg (sym
));
255 var_ann (sym
)->mpt
= mpt
;
258 if (MPT_SYMBOLS (mpt
) == NULL
)
259 MPT_SYMBOLS (mpt
) = BITMAP_ALLOC (&alias_bitmap_obstack
);
261 bitmap_set_bit (MPT_SYMBOLS (mpt
), DECL_UID (sym
));
263 /* MPT inherits the call-clobbering attributes from SYM. */
264 if (is_call_clobbered (sym
))
266 MTAG_GLOBAL (mpt
) = 1;
267 mark_call_clobbered (mpt
, ESCAPE_IS_GLOBAL
);
273 /* Mark variable VAR as being non-addressable. */
276 mark_non_addressable (tree var
)
280 if (!TREE_ADDRESSABLE (var
))
283 mpt
= memory_partition (var
);
286 var_ann (var
)->call_clobbered
= false;
288 bitmap_clear_bit (gimple_call_clobbered_vars (cfun
), DECL_UID (var
));
289 TREE_ADDRESSABLE (var
) = 0;
293 /* Note that it's possible for a symbol to have an associated
294 MPT and the MPT have a NULL empty set. During
295 init_alias_info, all MPTs get their sets cleared out, but the
296 symbols still point to the old MPTs that used to hold them.
297 This is done so that compute_memory_partitions can now which
298 symbols are losing or changing partitions and mark them for
300 if (MPT_SYMBOLS (mpt
))
301 bitmap_clear_bit (MPT_SYMBOLS (mpt
), DECL_UID (var
));
302 set_memory_partition (var
, NULL_TREE
);
307 /* qsort comparison function to sort type/name tags by DECL_UID. */
310 sort_tags_by_id (const void *pa
, const void *pb
)
312 tree a
= *(tree
*)pa
;
313 tree b
= *(tree
*)pb
;
315 return DECL_UID (a
) - DECL_UID (b
);
318 /* Initialize WORKLIST to contain those memory tags that are marked call
319 clobbered. Initialized WORKLIST2 to contain the reasons these
320 memory tags escaped. */
323 init_transitive_clobber_worklist (VEC (tree
, heap
) **worklist
,
324 VEC (int, heap
) **worklist2
)
326 referenced_var_iterator rvi
;
329 FOR_EACH_REFERENCED_VAR (curr
, rvi
)
331 if (MTAG_P (curr
) && is_call_clobbered (curr
))
333 VEC_safe_push (tree
, heap
, *worklist
, curr
);
334 VEC_safe_push (int, heap
, *worklist2
, var_ann (curr
)->escape_mask
);
339 /* Add ALIAS to WORKLIST (and the reason for escaping REASON to WORKLIST2) if
340 ALIAS is not already marked call clobbered, and is a memory
344 add_to_worklist (tree alias
, VEC (tree
, heap
) **worklist
,
345 VEC (int, heap
) **worklist2
,
348 if (MTAG_P (alias
) && !is_call_clobbered (alias
))
350 VEC_safe_push (tree
, heap
, *worklist
, alias
);
351 VEC_safe_push (int, heap
, *worklist2
, reason
);
355 /* Mark aliases of TAG as call clobbered, and place any tags on the
356 alias list that were not already call clobbered on WORKLIST. */
359 mark_aliases_call_clobbered (tree tag
, VEC (tree
, heap
) **worklist
,
360 VEC (int, heap
) **worklist2
)
366 var_ann_t ta
= var_ann (tag
);
370 aliases
= may_aliases (tag
);
374 EXECUTE_IF_SET_IN_BITMAP (aliases
, 0, i
, bi
)
376 entry
= referenced_var (i
);
377 if (!unmodifiable_var_p (entry
))
379 add_to_worklist (entry
, worklist
, worklist2
, ta
->escape_mask
);
380 mark_call_clobbered (entry
, ta
->escape_mask
);
385 /* Tags containing global vars need to be marked as global.
386 Tags containing call clobbered vars need to be marked as call
390 compute_tag_properties (void)
392 referenced_var_iterator rvi
;
395 VEC (tree
, heap
) *taglist
= NULL
;
397 FOR_EACH_REFERENCED_VAR (tag
, rvi
)
399 if (!MTAG_P (tag
) || TREE_CODE (tag
) == STRUCT_FIELD_TAG
)
401 VEC_safe_push (tree
, heap
, taglist
, tag
);
404 /* We sort the taglist by DECL_UID, for two reasons.
405 1. To get a sequential ordering to make the bitmap accesses
407 2. Because of the way we compute aliases, it's more likely that
408 an earlier tag is included in a later tag, and this will reduce
409 the number of iterations.
411 If we had a real tag graph, we would just topo-order it and be
413 qsort (VEC_address (tree
, taglist
),
414 VEC_length (tree
, taglist
),
418 /* Go through each tag not marked as global, and if it aliases
419 global vars, mark it global.
421 If the tag contains call clobbered vars, mark it call
424 This loop iterates because tags may appear in the may-aliases
425 list of other tags when we group. */
432 for (k
= 0; VEC_iterate (tree
, taglist
, k
, tag
); k
++)
438 bool tagcc
= is_call_clobbered (tag
);
439 bool tagglobal
= MTAG_GLOBAL (tag
);
441 if (tagcc
&& tagglobal
)
444 ma
= may_aliases (tag
);
448 EXECUTE_IF_SET_IN_BITMAP (ma
, 0, i
, bi
)
450 entry
= referenced_var (i
);
451 /* Call clobbered entries cause the tag to be marked
453 if (!tagcc
&& is_call_clobbered (entry
))
455 mark_call_clobbered (tag
, var_ann (entry
)->escape_mask
);
460 /* Global vars cause the tag to be marked global. */
461 if (!tagglobal
&& is_global_var (entry
))
463 MTAG_GLOBAL (tag
) = true;
468 /* Early exit once both global and cc are set, since the
469 loop can't do any more than that. */
470 if (tagcc
&& tagglobal
)
475 VEC_free (tree
, heap
, taglist
);
478 /* Set up the initial variable clobbers and globalness.
479 When this function completes, only tags whose aliases need to be
480 clobbered will be set clobbered. Tags clobbered because they
481 contain call clobbered vars are handled in compute_tag_properties. */
484 set_initial_properties (struct alias_info
*ai
)
487 referenced_var_iterator rvi
;
491 FOR_EACH_REFERENCED_VAR (var
, rvi
)
493 if (is_global_var (var
)
494 && (!var_can_have_subvars (var
)
495 || get_subvars_for_var (var
) == NULL
))
497 if (!unmodifiable_var_p (var
))
498 mark_call_clobbered (var
, ESCAPE_IS_GLOBAL
);
500 else if (TREE_CODE (var
) == PARM_DECL
501 && gimple_default_def (cfun
, var
)
502 && POINTER_TYPE_P (TREE_TYPE (var
)))
504 tree def
= gimple_default_def (cfun
, var
);
505 get_ptr_info (def
)->value_escapes_p
= 1;
506 get_ptr_info (def
)->escape_mask
|= ESCAPE_IS_PARM
;
510 for (i
= 0; VEC_iterate (tree
, ai
->processed_ptrs
, i
, ptr
); i
++)
512 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
513 tree tag
= symbol_mem_tag (SSA_NAME_VAR (ptr
));
515 if (pi
->value_escapes_p
)
517 /* If PTR escapes then its associated memory tags and
518 pointed-to variables are call-clobbered. */
519 if (pi
->name_mem_tag
)
520 mark_call_clobbered (pi
->name_mem_tag
, pi
->escape_mask
);
523 mark_call_clobbered (tag
, pi
->escape_mask
);
529 EXECUTE_IF_SET_IN_BITMAP (pi
->pt_vars
, 0, j
, bi
)
530 if (!unmodifiable_var_p (referenced_var (j
)))
531 mark_call_clobbered (referenced_var (j
), pi
->escape_mask
);
535 /* If the name tag is call clobbered, so is the symbol tag
536 associated with the base VAR_DECL. */
539 && is_call_clobbered (pi
->name_mem_tag
))
540 mark_call_clobbered (tag
, pi
->escape_mask
);
542 /* Name tags and symbol tags that we don't know where they point
543 to, might point to global memory, and thus, are clobbered.
545 FIXME: This is not quite right. They should only be
546 clobbered if value_escapes_p is true, regardless of whether
547 they point to global memory or not.
548 So removing this code and fixing all the bugs would be nice.
549 It is the cause of a bunch of clobbering. */
550 if ((pi
->pt_global_mem
|| pi
->pt_anything
)
551 && pi
->is_dereferenced
&& pi
->name_mem_tag
)
553 mark_call_clobbered (pi
->name_mem_tag
, ESCAPE_IS_GLOBAL
);
554 MTAG_GLOBAL (pi
->name_mem_tag
) = true;
557 if ((pi
->pt_global_mem
|| pi
->pt_anything
)
558 && pi
->is_dereferenced
561 mark_call_clobbered (tag
, ESCAPE_IS_GLOBAL
);
562 MTAG_GLOBAL (tag
) = true;
567 /* Compute which variables need to be marked call clobbered because
568 their tag is call clobbered, and which tags need to be marked
569 global because they contain global variables. */
572 compute_call_clobbered (struct alias_info
*ai
)
574 VEC (tree
, heap
) *worklist
= NULL
;
575 VEC(int,heap
) *worklist2
= NULL
;
577 set_initial_properties (ai
);
578 init_transitive_clobber_worklist (&worklist
, &worklist2
);
579 while (VEC_length (tree
, worklist
) != 0)
581 tree curr
= VEC_pop (tree
, worklist
);
582 int reason
= VEC_pop (int, worklist2
);
584 mark_call_clobbered (curr
, reason
);
585 mark_aliases_call_clobbered (curr
, &worklist
, &worklist2
);
587 VEC_free (tree
, heap
, worklist
);
588 VEC_free (int, heap
, worklist2
);
589 compute_tag_properties ();
593 /* Dump memory partition information to FILE. */
596 dump_memory_partitions (FILE *file
)
602 fprintf (file
, "\nMemory partitions\n\n");
603 for (i
= 0, npart
= 0, nsyms
= 0;
604 VEC_iterate (tree
, gimple_ssa_operands (cfun
)->mpt_table
, i
, mpt
);
609 bitmap syms
= MPT_SYMBOLS (mpt
);
610 unsigned long n
= (syms
) ? bitmap_count_bits (syms
) : 0;
612 fprintf (file
, "#%u: ", i
);
613 print_generic_expr (file
, mpt
, 0);
614 fprintf (file
, ": %lu elements: ", n
);
615 dump_decl_set (file
, syms
);
621 fprintf (file
, "\n%u memory partitions holding %lu symbols\n", npart
, nsyms
);
625 /* Dump memory partition information to stderr. */
628 debug_memory_partitions (void)
630 dump_memory_partitions (stderr
);
634 /* Return true if memory partitioning is required given the memory
635 reference estimates in STATS. */
638 need_to_partition_p (struct mem_ref_stats_d
*stats
)
640 long num_vops
= stats
->num_vuses
+ stats
->num_vdefs
;
641 long avg_vops
= CEIL (num_vops
, stats
->num_mem_stmts
);
642 return (num_vops
> (long) MAX_ALIASED_VOPS
643 && avg_vops
> (long) AVG_ALIASED_VOPS
);
647 /* Count the actual number of virtual operators in CFUN. Note that
648 this is only meaningful after virtual operands have been populated,
649 so it should be invoked at the end of compute_may_aliases.
651 The number of virtual operators are stored in *NUM_VDEFS_P and
652 *NUM_VUSES_P, the number of partitioned symbols in
653 *NUM_PARTITIONED_P and the number of unpartitioned symbols in
654 *NUM_UNPARTITIONED_P.
656 If any of these pointers is NULL the corresponding count is not
660 count_mem_refs (long *num_vuses_p
, long *num_vdefs_p
,
661 long *num_partitioned_p
, long *num_unpartitioned_p
)
663 block_stmt_iterator bsi
;
665 long num_vdefs
, num_vuses
, num_partitioned
, num_unpartitioned
;
666 referenced_var_iterator rvi
;
669 num_vuses
= num_vdefs
= num_partitioned
= num_unpartitioned
= 0;
671 if (num_vuses_p
|| num_vdefs_p
)
673 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
675 tree stmt
= bsi_stmt (bsi
);
676 if (stmt_references_memory_p (stmt
))
678 num_vuses
+= NUM_SSA_OPERANDS (stmt
, SSA_OP_VUSE
);
679 num_vdefs
+= NUM_SSA_OPERANDS (stmt
, SSA_OP_VDEF
);
683 if (num_partitioned_p
|| num_unpartitioned_p
)
684 FOR_EACH_REFERENCED_VAR (sym
, rvi
)
686 if (is_gimple_reg (sym
))
689 if (memory_partition (sym
))
696 *num_vdefs_p
= num_vdefs
;
699 *num_vuses_p
= num_vuses
;
701 if (num_partitioned_p
)
702 *num_partitioned_p
= num_partitioned
;
704 if (num_unpartitioned_p
)
705 *num_unpartitioned_p
= num_unpartitioned
;
709 /* Dump memory reference stats for function CFUN to FILE. */
712 dump_mem_ref_stats (FILE *file
)
714 long actual_num_vuses
, actual_num_vdefs
;
715 long num_partitioned
, num_unpartitioned
;
716 struct mem_ref_stats_d
*stats
;
718 stats
= gimple_mem_ref_stats (cfun
);
720 count_mem_refs (&actual_num_vuses
, &actual_num_vdefs
, &num_partitioned
,
723 fprintf (file
, "\nMemory reference statistics for %s\n\n",
724 lang_hooks
.decl_printable_name (current_function_decl
, 2));
726 fprintf (file
, "Number of memory statements: %ld\n",
727 stats
->num_mem_stmts
);
728 fprintf (file
, "Number of call sites: %ld\n",
729 stats
->num_call_sites
);
730 fprintf (file
, "Number of pure/const call sites: %ld\n",
731 stats
->num_pure_const_call_sites
);
732 fprintf (file
, "Number of asm sites: %ld\n",
733 stats
->num_asm_sites
);
734 fprintf (file
, "Estimated number of loads: %ld (%ld/stmt)\n",
736 (stats
->num_mem_stmts
)
737 ? CEIL (stats
->num_vuses
, stats
->num_mem_stmts
)
739 fprintf (file
, "Actual number of loads: %ld (%ld/stmt)\n",
741 (stats
->num_mem_stmts
)
742 ? CEIL (actual_num_vuses
, stats
->num_mem_stmts
)
745 if (actual_num_vuses
> stats
->num_vuses
+ (stats
->num_vuses
/ 25))
746 fprintf (file
, "\t(warning: estimation is lower by more than 25%%)\n");
748 fprintf (file
, "Estimated number of stores: %ld (%ld/stmt)\n",
750 (stats
->num_mem_stmts
)
751 ? CEIL (stats
->num_vdefs
, stats
->num_mem_stmts
)
753 fprintf (file
, "Actual number of stores: %ld (%ld/stmt)\n",
755 (stats
->num_mem_stmts
)
756 ? CEIL (actual_num_vdefs
, stats
->num_mem_stmts
)
759 if (actual_num_vdefs
> stats
->num_vdefs
+ (stats
->num_vdefs
/ 25))
760 fprintf (file
, "\t(warning: estimation is lower by more than 25%%)\n");
762 fprintf (file
, "Partitioning thresholds: MAX = %d AVG = %d "
763 "(%sNEED TO PARTITION)\n", MAX_ALIASED_VOPS
, AVG_ALIASED_VOPS
,
764 stats
->num_mem_stmts
&& need_to_partition_p (stats
) ? "" : "NO ");
765 fprintf (file
, "Number of partitioned symbols: %ld\n", num_partitioned
);
766 fprintf (file
, "Number of unpartitioned symbols: %ld\n", num_unpartitioned
);
770 /* Dump memory reference stats for function FN to stderr. */
773 debug_mem_ref_stats (void)
775 dump_mem_ref_stats (stderr
);
779 /* Dump memory reference stats for variable VAR to FILE. */
782 dump_mem_sym_stats (FILE *file
, tree var
)
784 mem_sym_stats_t stats
= mem_sym_stats (cfun
, var
);
789 fprintf (file
, "read frequency: %6ld, write frequency: %6ld, "
790 "direct reads: %3ld, direct writes: %3ld, "
791 "indirect reads: %4ld, indirect writes: %4ld, symbol: ",
792 stats
->frequency_reads
, stats
->frequency_writes
,
793 stats
->num_direct_reads
, stats
->num_direct_writes
,
794 stats
->num_indirect_reads
, stats
->num_indirect_writes
);
795 print_generic_expr (file
, stats
->var
, 0);
796 fprintf (file
, ", tags: ");
797 dump_decl_set (file
, stats
->parent_tags
);
801 /* Dump memory reference stats for variable VAR to stderr. */
804 debug_mem_sym_stats (tree var
)
806 dump_mem_sym_stats (stderr
, var
);
810 /* Dump memory reference stats for all memory symbols to FILE. */
813 dump_all_mem_sym_stats (FILE *file
)
815 referenced_var_iterator rvi
;
818 FOR_EACH_REFERENCED_VAR (sym
, rvi
)
820 if (is_gimple_reg (sym
))
823 dump_mem_sym_stats (file
, sym
);
828 /* Dump memory reference stats for all memory symbols to stderr. */
831 debug_all_mem_sym_stats (void)
833 dump_all_mem_sym_stats (stderr
);
837 /* Dump the MP_INFO array to FILE. */
840 dump_mp_info (FILE *file
, VEC(mem_sym_stats_t
,heap
) *mp_info
)
843 mem_sym_stats_t mp_p
;
845 for (i
= 0; VEC_iterate (mem_sym_stats_t
, mp_info
, i
, mp_p
); i
++)
846 if (!mp_p
->partitioned_p
)
847 dump_mem_sym_stats (file
, mp_p
->var
);
851 /* Dump the MP_INFO array to stderr. */
854 debug_mp_info (VEC(mem_sym_stats_t
,heap
) *mp_info
)
856 dump_mp_info (stderr
, mp_info
);
860 /* Update memory reference stats for symbol VAR in statement STMT.
861 NUM_DIRECT_READS and NUM_DIRECT_WRITES specify the number of times
862 that VAR is read/written in STMT (indirect reads/writes are not
863 recorded by this function, see compute_memory_partitions). */
866 update_mem_sym_stats_from_stmt (tree var
, tree stmt
, long num_direct_reads
,
867 long num_direct_writes
)
869 mem_sym_stats_t stats
;
871 gcc_assert (num_direct_reads
>= 0 && num_direct_writes
>= 0);
873 stats
= get_mem_sym_stats_for (var
);
875 stats
->num_direct_reads
+= num_direct_reads
;
876 stats
->frequency_reads
+= ((long) bb_for_stmt (stmt
)->frequency
879 stats
->num_direct_writes
+= num_direct_writes
;
880 stats
->frequency_writes
+= ((long) bb_for_stmt (stmt
)->frequency
881 * num_direct_writes
);
885 /* The list is sorted by increasing partitioning score (PSCORE).
886 This score is computed such that symbols with high scores are
887 those that are least likely to be partitioned. Given a symbol
888 MP->VAR, PSCORE(S) is the result of the following weighted sum
890 PSCORE(S) = FW * 64 + FR * 32
897 FW Execution frequency of writes to S
898 FR Execution frequency of reads from S
899 DW Number of direct writes to S
900 DR Number of direct reads from S
901 IW Number of indirect writes to S
902 IR Number of indirect reads from S
903 NO_ALIAS State of the NO_ALIAS* flags
905 The basic idea here is that symbols that are frequently
906 written-to in hot paths of the code are the last to be considered
910 pscore (mem_sym_stats_t mp
)
912 return mp
->frequency_writes
* 64 + mp
->frequency_reads
* 32
913 + mp
->num_direct_writes
* 16 + mp
->num_direct_reads
* 8
914 + mp
->num_indirect_writes
* 4 + mp
->num_indirect_reads
* 2
915 + var_ann (mp
->var
)->noalias_state
;
919 /* Given two MP_INFO entries MP1 and MP2, return -1 if MP1->VAR should
920 be partitioned before MP2->VAR, 0 if they are the same or 1 if
921 MP1->VAR should be partitioned after MP2->VAR. */
924 compare_mp_info_entries (mem_sym_stats_t mp1
, mem_sym_stats_t mp2
)
926 long pscore1
= pscore (mp1
);
927 long pscore2
= pscore (mp2
);
929 if (pscore1
< pscore2
)
931 else if (pscore1
> pscore2
)
938 /* Comparison routine for qsort. The list is sorted by increasing
939 partitioning score (PSCORE). This score is computed such that
940 symbols with high scores are those that are least likely to be
944 mp_info_cmp (const void *p
, const void *q
)
946 mem_sym_stats_t e1
= *((const mem_sym_stats_t
*) p
);
947 mem_sym_stats_t e2
= *((const mem_sym_stats_t
*) q
);
948 return compare_mp_info_entries (e1
, e2
);
952 /* Sort the array of reference counts used to compute memory partitions.
953 Elements are sorted in ascending order of execution frequency and
954 descending order of virtual operators needed. */
957 sort_mp_info (VEC(mem_sym_stats_t
,heap
) *list
)
959 unsigned num
= VEC_length (mem_sym_stats_t
, list
);
966 if (compare_mp_info_entries (VEC_index (mem_sym_stats_t
, list
, 0),
967 VEC_index (mem_sym_stats_t
, list
, 1)) > 0)
969 /* Swap elements if they are in the wrong order. */
970 mem_sym_stats_t tmp
= VEC_index (mem_sym_stats_t
, list
, 0);
971 VEC_replace (mem_sym_stats_t
, list
, 0,
972 VEC_index (mem_sym_stats_t
, list
, 1));
973 VEC_replace (mem_sym_stats_t
, list
, 1, tmp
);
979 /* There are 3 or more elements, call qsort. */
980 qsort (VEC_address (mem_sym_stats_t
, list
),
981 VEC_length (mem_sym_stats_t
, list
),
982 sizeof (mem_sym_stats_t
),
987 /* Return the memory partition tag (MPT) associated with memory
991 get_mpt_for (tree sym
)
995 /* Don't create a new tag unnecessarily. */
996 mpt
= memory_partition (sym
);
997 if (mpt
== NULL_TREE
)
999 mpt
= create_tag_raw (MEMORY_PARTITION_TAG
, TREE_TYPE (sym
), "MPT");
1000 TREE_ADDRESSABLE (mpt
) = 0;
1001 add_referenced_var (mpt
);
1002 VEC_safe_push (tree
, heap
, gimple_ssa_operands (cfun
)->mpt_table
, mpt
);
1003 gcc_assert (MPT_SYMBOLS (mpt
) == NULL
);
1004 set_memory_partition (sym
, mpt
);
1011 /* Add MP_P->VAR to a memory partition and return the partition. */
1014 find_partition_for (mem_sym_stats_t mp_p
)
1017 VEC(tree
,heap
) *mpt_table
;
1020 mpt_table
= gimple_ssa_operands (cfun
)->mpt_table
;
1023 /* Find an existing partition for MP_P->VAR. */
1024 for (i
= 0; VEC_iterate (tree
, mpt_table
, i
, mpt
); i
++)
1026 mem_sym_stats_t mpt_stats
;
1028 /* If MPT does not have any symbols yet, use it. */
1029 if (MPT_SYMBOLS (mpt
) == NULL
)
1032 /* Otherwise, see if MPT has common parent tags with MP_P->VAR,
1033 but avoid grouping clobbered variables with non-clobbered
1034 variables (otherwise, this tends to creates a single memory
1035 partition because other call-clobbered variables may have
1036 common parent tags with non-clobbered ones). */
1037 mpt_stats
= get_mem_sym_stats_for (mpt
);
1038 if (mp_p
->parent_tags
1039 && mpt_stats
->parent_tags
1040 && is_call_clobbered (mpt
) == is_call_clobbered (mp_p
->var
)
1041 && bitmap_intersect_p (mpt_stats
->parent_tags
, mp_p
->parent_tags
))
1044 /* If no common parent tags are found, see if both MPT and
1045 MP_P->VAR are call-clobbered. */
1046 if (is_call_clobbered (mpt
) && is_call_clobbered (mp_p
->var
))
1050 if (mpt
== NULL_TREE
)
1051 mpt
= get_mpt_for (mp_p
->var
);
1053 set_memory_partition (mp_p
->var
, mpt
);
1055 mp_p
->partitioned_p
= true;
1057 mark_sym_for_renaming (mp_p
->var
);
1058 mark_sym_for_renaming (mpt
);
1064 /* Rewrite the alias set for TAG to use the newly created partitions.
1065 If TAG is NULL, rewrite the set of call-clobbered variables.
1066 NEW_ALIASES is a scratch bitmap to build the new set of aliases for
1070 rewrite_alias_set_for (tree tag
, bitmap new_aliases
)
1076 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag
), 0, i
, bi
)
1078 sym
= referenced_var (i
);
1079 mpt
= memory_partition (sym
);
1081 bitmap_set_bit (new_aliases
, DECL_UID (mpt
));
1083 bitmap_set_bit (new_aliases
, DECL_UID (sym
));
1086 /* Rebuild the may-alias array for TAG. */
1087 bitmap_copy (MTAG_ALIASES (tag
), new_aliases
);
1091 /* Determine how many virtual operands can be saved by partitioning
1092 MP_P->VAR into MPT. When a symbol S is thrown inside a partition
1093 P, every virtual operand that used to reference S will now
1094 reference P. Whether it reduces the number of virtual operands
1097 1- Direct references to S are never saved. Instead of the virtual
1098 operand to S, we will now have a virtual operand to P.
1100 2- Indirect references to S are reduced only for those memory tags
1101 holding S that already had other symbols partitioned into P.
1102 For instance, if a memory tag T has the alias set { a b S c },
1103 the first time we partition S into P, the alias set will become
1104 { a b P c }, so no virtual operands will be saved. However, if
1105 we now partition symbol 'c' into P, then the alias set for T
1106 will become { a b P }, so we will be saving one virtual operand
1107 for every indirect reference to 'c'.
1109 3- Is S is call-clobbered, we save as many virtual operands as
1110 call/asm sites exist in the code, but only if other
1111 call-clobbered symbols have been grouped into P. The first
1112 call-clobbered symbol that we group does not produce any
1115 MEM_REF_STATS points to CFUN's memory reference information. */
1118 estimate_vop_reduction (struct mem_ref_stats_d
*mem_ref_stats
,
1119 mem_sym_stats_t mp_p
, tree mpt
)
1123 mem_sym_stats_t mpt_stats
;
1125 /* We should only get symbols with indirect references here. */
1126 gcc_assert (mp_p
->num_indirect_reads
> 0 || mp_p
->num_indirect_writes
> 0);
1128 /* Note that the only statistics we keep for MPT is the set of
1129 parent tags to know which memory tags have had alias members
1130 partitioned, and the indicator has_call_clobbered_vars.
1131 Reference counts are not important for MPT. */
1132 mpt_stats
= get_mem_sym_stats_for (mpt
);
1134 /* Traverse all the parent tags for MP_P->VAR. For every tag T, if
1135 partition P is already grouping aliases of T, then reduce the
1136 number of virtual operands by the number of direct references
1138 if (mp_p
->parent_tags
)
1140 if (mpt_stats
->parent_tags
== NULL
)
1141 mpt_stats
->parent_tags
= BITMAP_ALLOC (&alias_bitmap_obstack
);
1143 EXECUTE_IF_SET_IN_BITMAP (mp_p
->parent_tags
, 0, i
, bi
)
1145 if (bitmap_bit_p (mpt_stats
->parent_tags
, i
))
1147 /* Partition MPT is already partitioning symbols in the
1148 alias set for TAG. This means that we are now saving
1149 1 virtual operand for every direct reference to TAG. */
1150 tree tag
= referenced_var (i
);
1151 mem_sym_stats_t tag_stats
= mem_sym_stats (cfun
, tag
);
1152 mem_ref_stats
->num_vuses
-= tag_stats
->num_direct_reads
;
1153 mem_ref_stats
->num_vdefs
-= tag_stats
->num_direct_writes
;
1157 /* This is the first symbol in tag I's alias set that is
1158 being grouped under MPT. We will not save any
1159 virtual operands this time, but record that MPT is
1160 grouping a symbol from TAG's alias set so that the
1161 next time we get the savings. */
1162 bitmap_set_bit (mpt_stats
->parent_tags
, i
);
1167 /* If MP_P->VAR is call-clobbered, and MPT is already grouping
1168 call-clobbered symbols, then we will save as many virtual
1169 operands as asm/call sites there are. */
1170 if (is_call_clobbered (mp_p
->var
))
1172 if (mpt_stats
->has_call_clobbered_vars
)
1173 mem_ref_stats
->num_vdefs
-= mem_ref_stats
->num_call_sites
1174 + mem_ref_stats
->num_asm_sites
;
1176 mpt_stats
->has_call_clobbered_vars
= true;
1181 /* Helper for compute_memory_partitions. Transfer reference counts
1182 from pointers to their pointed-to sets. Counters for pointers were
1183 computed by update_alias_info. MEM_REF_STATS points to CFUN's
1184 memory reference information. */
1187 update_reference_counts (struct mem_ref_stats_d
*mem_ref_stats
)
1191 mem_sym_stats_t sym_stats
;
1193 for (i
= 1; i
< num_ssa_names
; i
++)
1196 struct ptr_info_def
*pi
;
1200 && POINTER_TYPE_P (TREE_TYPE (ptr
))
1201 && (pi
= SSA_NAME_PTR_INFO (ptr
)) != NULL
1202 && pi
->is_dereferenced
)
1207 mem_sym_stats_t ptr_stats
, tag_stats
;
1209 /* If PTR has flow-sensitive points-to information, use
1210 PTR's name tag, otherwise use the symbol tag associated
1211 with PTR's symbol. */
1212 if (pi
->name_mem_tag
)
1213 tag
= pi
->name_mem_tag
;
1215 tag
= symbol_mem_tag (SSA_NAME_VAR (ptr
));
1217 ptr_stats
= get_mem_sym_stats_for (ptr
);
1218 tag_stats
= get_mem_sym_stats_for (tag
);
1220 /* TAG has as many direct references as dereferences we
1221 found for its parent pointer. */
1222 tag_stats
->num_direct_reads
+= ptr_stats
->num_direct_reads
;
1223 tag_stats
->num_direct_writes
+= ptr_stats
->num_direct_writes
;
1225 /* All the dereferences of pointer PTR are considered direct
1226 references to PTR's memory tag (TAG). In turn,
1227 references to TAG will become virtual operands for every
1228 symbol in TAG's alias set. So, for every symbol ALIAS in
1229 TAG's alias set, add as many indirect references to ALIAS
1230 as direct references there are for TAG. */
1231 if (MTAG_ALIASES (tag
))
1232 EXECUTE_IF_SET_IN_BITMAP (MTAG_ALIASES (tag
), 0, j
, bj
)
1234 tree alias
= referenced_var (j
);
1235 sym_stats
= get_mem_sym_stats_for (alias
);
1237 /* All the direct references to TAG are indirect references
1239 sym_stats
->num_indirect_reads
+= ptr_stats
->num_direct_reads
;
1240 sym_stats
->num_indirect_writes
+= ptr_stats
->num_direct_writes
;
1241 sym_stats
->frequency_reads
+= ptr_stats
->frequency_reads
;
1242 sym_stats
->frequency_writes
+= ptr_stats
->frequency_writes
;
1244 /* Indicate that TAG is one of ALIAS's parent tags. */
1245 if (sym_stats
->parent_tags
== NULL
)
1246 sym_stats
->parent_tags
= BITMAP_ALLOC (&alias_bitmap_obstack
);
1247 bitmap_set_bit (sym_stats
->parent_tags
, DECL_UID (tag
));
1252 /* Call-clobbered symbols are indirectly written at every
1254 EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun
), 0, i
, bi
)
1256 tree sym
= referenced_var (i
);
1257 sym_stats
= get_mem_sym_stats_for (sym
);
1258 sym_stats
->num_indirect_writes
+= mem_ref_stats
->num_call_sites
1259 + mem_ref_stats
->num_asm_sites
;
1262 /* Addressable symbols are indirectly written at some ASM sites.
1263 Since only ASM sites that clobber memory actually affect
1264 addressable symbols, this is an over-estimation. */
1265 EXECUTE_IF_SET_IN_BITMAP (gimple_addressable_vars (cfun
), 0, i
, bi
)
1267 tree sym
= referenced_var (i
);
1268 sym_stats
= get_mem_sym_stats_for (sym
);
1269 sym_stats
->num_indirect_writes
+= mem_ref_stats
->num_asm_sites
;
1274 /* Helper for compute_memory_partitions. Add all memory symbols to
1275 *MP_INFO_P and compute the initial estimate for the total number of
1276 virtual operands needed. MEM_REF_STATS points to CFUN's memory
1277 reference information. On exit, *TAGS_P will contain the list of
1278 memory tags whose alias set need to be rewritten after
1282 build_mp_info (struct mem_ref_stats_d
*mem_ref_stats
,
1283 VEC(mem_sym_stats_t
,heap
) **mp_info_p
,
1284 VEC(tree
,heap
) **tags_p
)
1287 referenced_var_iterator rvi
;
1289 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1291 mem_sym_stats_t sym_stats
;
1294 /* We are only interested in memory symbols other than MPTs. */
1295 if (is_gimple_reg (var
) || TREE_CODE (var
) == MEMORY_PARTITION_TAG
)
1298 /* Collect memory tags into the TAGS array so that we can
1299 rewrite their alias sets after partitioning. */
1300 if (MTAG_P (var
) && MTAG_ALIASES (var
))
1301 VEC_safe_push (tree
, heap
, *tags_p
, var
);
1303 /* Since we are going to re-compute partitions, any symbols that
1304 used to belong to a partition must be detached from it and
1305 marked for renaming. */
1306 if ((old_mpt
= memory_partition (var
)) != NULL
)
1308 mark_sym_for_renaming (old_mpt
);
1309 set_memory_partition (var
, NULL_TREE
);
1310 mark_sym_for_renaming (var
);
1313 sym_stats
= get_mem_sym_stats_for (var
);
1315 /* Add VAR's reference info to MP_INFO. Note that the only
1316 symbols that make sense to partition are those that have
1317 indirect references. If a symbol S is always directly
1318 referenced, partitioning it will not reduce the number of
1319 virtual operators. The only symbols that are profitable to
1320 partition are those that belong to alias sets and/or are
1322 if (sym_stats
->num_indirect_reads
> 0
1323 || sym_stats
->num_indirect_writes
> 0)
1324 VEC_safe_push (mem_sym_stats_t
, heap
, *mp_info_p
, sym_stats
);
1326 /* Update the number of estimated VOPS. Note that direct
1327 references to memory tags are always counted as indirect
1328 references to their alias set members, so if a memory tag has
1329 aliases, do not count its direct references to avoid double
1331 if (!MTAG_P (var
) || !MTAG_ALIASES (var
))
1333 mem_ref_stats
->num_vuses
+= sym_stats
->num_direct_reads
;
1334 mem_ref_stats
->num_vdefs
+= sym_stats
->num_direct_writes
;
1337 mem_ref_stats
->num_vuses
+= sym_stats
->num_indirect_reads
;
1338 mem_ref_stats
->num_vdefs
+= sym_stats
->num_indirect_writes
;
1343 /* Compute memory partitions. A memory partition (MPT) is an
1344 arbitrary grouping of memory symbols, such that references to one
1345 member of the group is considered a reference to all the members of
1348 As opposed to alias sets in memory tags, the grouping into
1349 partitions is completely arbitrary and only done to reduce the
1350 number of virtual operands. The only rule that needs to be
1351 observed when creating memory partitions is that given two memory
1352 partitions MPT.i and MPT.j, they must not contain symbols in
1355 Memory partitions are used when putting the program into Memory-SSA
1356 form. In particular, in Memory-SSA PHI nodes are not computed for
1357 individual memory symbols. They are computed for memory
1358 partitions. This reduces the amount of PHI nodes in the SSA graph
1359 at the expense of precision (i.e., it makes unrelated stores affect
1362 However, it is possible to increase precision by changing this
1363 partitioning scheme. For instance, if the partitioning scheme is
1364 such that get_mpt_for is the identity function (that is,
1365 get_mpt_for (s) = s), this will result in ultimate precision at the
1366 expense of huge SSA webs.
1368 At the other extreme, a partitioning scheme that groups all the
1369 symbols in the same set results in minimal SSA webs and almost
1370 total loss of precision.
1372 There partitioning heuristic uses three parameters to decide the
1373 order in which symbols are processed. The list of symbols is
1374 sorted so that symbols that are more likely to be partitioned are
1375 near the top of the list:
1377 - Execution frequency. If a memory references is in a frequently
1378 executed code path, grouping it into a partition may block useful
1379 transformations and cause sub-optimal code generation. So, the
1380 partition heuristic tries to avoid grouping symbols with high
1381 execution frequency scores. Execution frequency is taken
1382 directly from the basic blocks where every reference is made (see
1383 update_mem_sym_stats_from_stmt), which in turn uses the
1384 profile guided machinery, so if the program is compiled with PGO
1385 enabled, more accurate partitioning decisions will be made.
1387 - Number of references. Symbols with few references in the code,
1388 are partitioned before symbols with many references.
1390 - NO_ALIAS attributes. Symbols with any of the NO_ALIAS*
1391 attributes are partitioned after symbols marked MAY_ALIAS.
1393 Once the list is sorted, the partitioning proceeds as follows:
1395 1- For every symbol S in MP_INFO, create a new memory partition MP,
1396 if necessary. To avoid memory partitions that contain symbols
1397 from non-conflicting alias sets, memory partitions are
1398 associated to the memory tag that holds S in its alias set. So,
1399 when looking for a memory partition for S, the memory partition
1400 associated with one of the memory tags holding S is chosen. If
1401 none exists, a new one is created.
1403 2- Add S to memory partition MP.
1405 3- Reduce by 1 the number of VOPS for every memory tag holding S.
1407 4- If the total number of VOPS is less than MAX_ALIASED_VOPS or the
1408 average number of VOPS per statement is less than
1409 AVG_ALIASED_VOPS, stop. Otherwise, go to the next symbol in the
1413 compute_memory_partitions (void)
1417 mem_sym_stats_t mp_p
;
1418 VEC(mem_sym_stats_t
,heap
) *mp_info
;
1420 VEC(tree
,heap
) *tags
;
1421 struct mem_ref_stats_d
*mem_ref_stats
;
1422 int prev_max_aliased_vops
;
1424 mem_ref_stats
= gimple_mem_ref_stats (cfun
);
1425 gcc_assert (mem_ref_stats
->num_vuses
== 0 && mem_ref_stats
->num_vdefs
== 0);
1427 if (mem_ref_stats
->num_mem_stmts
== 0)
1430 timevar_push (TV_MEMORY_PARTITIONING
);
1434 prev_max_aliased_vops
= MAX_ALIASED_VOPS
;
1436 /* Since we clearly cannot lower the number of virtual operators
1437 below the total number of memory statements in the function, we
1438 may need to adjust MAX_ALIASED_VOPS beforehand. */
1439 if (MAX_ALIASED_VOPS
< mem_ref_stats
->num_mem_stmts
)
1440 MAX_ALIASED_VOPS
= mem_ref_stats
->num_mem_stmts
;
1442 /* Update reference stats for all the pointed-to variables and
1444 update_reference_counts (mem_ref_stats
);
1446 /* Add all the memory symbols to MP_INFO. */
1447 build_mp_info (mem_ref_stats
, &mp_info
, &tags
);
1449 /* No partitions required if we are below the threshold. */
1450 if (!need_to_partition_p (mem_ref_stats
))
1453 fprintf (dump_file
, "\nMemory partitioning NOT NEEDED for %s\n",
1454 get_name (current_function_decl
));
1458 /* Sort the MP_INFO array so that symbols that should be partitioned
1459 first are near the top of the list. */
1460 sort_mp_info (mp_info
);
1464 fprintf (dump_file
, "\nMemory partitioning NEEDED for %s\n\n",
1465 get_name (current_function_decl
));
1466 fprintf (dump_file
, "Memory symbol references before partitioning:\n");
1467 dump_mp_info (dump_file
, mp_info
);
1470 /* Create partitions for variables in MP_INFO until we have enough
1471 to lower the total number of VOPS below MAX_ALIASED_VOPS or if
1472 the average number of VOPS per statement is below
1473 AVG_ALIASED_VOPS. */
1474 for (i
= 0; VEC_iterate (mem_sym_stats_t
, mp_info
, i
, mp_p
); i
++)
1478 /* If we are below the threshold, stop. */
1479 if (!need_to_partition_p (mem_ref_stats
))
1482 mpt
= find_partition_for (mp_p
);
1483 estimate_vop_reduction (mem_ref_stats
, mp_p
, mpt
);
1486 /* After partitions have been created, rewrite alias sets to use
1487 them instead of the original symbols. This way, if the alias set
1488 was computed as { a b c d e f }, and the subset { b e f } was
1489 grouped into partition MPT.3, then the new alias set for the tag
1490 will be { a c d MPT.3 }.
1492 Note that this is not strictly necessary. The operand scanner
1493 will always check if a symbol belongs to a partition when adding
1494 virtual operands. However, by reducing the size of the alias
1495 sets to be scanned, the work needed inside the operand scanner is
1496 significantly reduced. */
1497 new_aliases
= BITMAP_ALLOC (NULL
);
1499 for (i
= 0; VEC_iterate (tree
, tags
, i
, tag
); i
++)
1501 rewrite_alias_set_for (tag
, new_aliases
);
1502 bitmap_clear (new_aliases
);
1505 BITMAP_FREE (new_aliases
);
1509 fprintf (dump_file
, "\nMemory symbol references after partitioning:\n");
1510 dump_mp_info (dump_file
, mp_info
);
1514 /* Free allocated memory. */
1515 VEC_free (mem_sym_stats_t
, heap
, mp_info
);
1516 VEC_free (tree
, heap
, tags
);
1518 MAX_ALIASED_VOPS
= prev_max_aliased_vops
;
1520 timevar_pop (TV_MEMORY_PARTITIONING
);
1524 /* Compute may-alias information for every variable referenced in function
1527 Alias analysis proceeds in 3 main phases:
1529 1- Points-to and escape analysis.
1531 This phase walks the use-def chains in the SSA web looking for three
1534 * Assignments of the form P_i = &VAR
1535 * Assignments of the form P_i = malloc()
1536 * Pointers and ADDR_EXPR that escape the current function.
1538 The concept of 'escaping' is the same one used in the Java world. When
1539 a pointer or an ADDR_EXPR escapes, it means that it has been exposed
1540 outside of the current function. So, assignment to global variables,
1541 function arguments and returning a pointer are all escape sites, as are
1542 conversions between pointers and integers.
1544 This is where we are currently limited. Since not everything is renamed
1545 into SSA, we lose track of escape properties when a pointer is stashed
1546 inside a field in a structure, for instance. In those cases, we are
1547 assuming that the pointer does escape.
1549 We use escape analysis to determine whether a variable is
1550 call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable
1551 is call-clobbered. If a pointer P_i escapes, then all the variables
1552 pointed-to by P_i (and its memory tag) also escape.
1554 2- Compute flow-sensitive aliases
1556 We have two classes of memory tags. Memory tags associated with the
1557 pointed-to data type of the pointers in the program. These tags are
1558 called "symbol memory tag" (SMT). The other class are those associated
1559 with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
1560 when adding operands for an INDIRECT_REF *P_i, we will first check
1561 whether P_i has a name tag, if it does we use it, because that will have
1562 more precise aliasing information. Otherwise, we use the standard symbol
1565 In this phase, we go through all the pointers we found in points-to
1566 analysis and create alias sets for the name memory tags associated with
1567 each pointer P_i. If P_i escapes, we mark call-clobbered the variables
1568 it points to and its tag.
1571 3- Compute flow-insensitive aliases
1573 This pass will compare the alias set of every symbol memory tag and
1574 every addressable variable found in the program. Given a symbol
1575 memory tag SMT and an addressable variable V. If the alias sets of
1576 SMT and V conflict (as computed by may_alias_p), then V is marked
1577 as an alias tag and added to the alias set of SMT.
1579 For instance, consider the following function:
1595 After aliasing analysis has finished, the symbol memory tag for pointer
1596 'p' will have two aliases, namely variables 'a' and 'b'. Every time
1597 pointer 'p' is dereferenced, we want to mark the operation as a
1598 potential reference to 'a' and 'b'.
1608 # p_1 = PHI <p_4(1), p_6(2)>;
1623 In certain cases, the list of may aliases for a pointer may grow too
1624 large. This may cause an explosion in the number of virtual operands
1625 inserted in the code. Resulting in increased memory consumption and
1628 When the number of virtual operands needed to represent aliased
1629 loads and stores grows too large (configurable with option --param
1630 max-aliased-vops and --param avg-aliased-vops), alias sets are
1631 grouped to avoid severe compile-time slow downs and memory
1632 consumption. See compute_memory_partitions. */
1635 compute_may_aliases (void)
1637 struct alias_info
*ai
;
1639 memset (&alias_stats
, 0, sizeof (alias_stats
));
1641 /* Initialize aliasing information. */
1642 ai
= init_alias_info ();
1644 /* For each pointer P_i, determine the sets of variables that P_i may
1645 point-to. For every addressable variable V, determine whether the
1646 address of V escapes the current function, making V call-clobbered
1647 (i.e., whether &V is stored in a global variable or if its passed as a
1648 function call argument). */
1649 compute_points_to_sets (ai
);
1651 /* Collect all pointers and addressable variables, compute alias sets,
1652 create memory tags for pointers and promote variables whose address is
1653 not needed anymore. */
1654 setup_pointers_and_addressables (ai
);
1656 /* Compute type-based flow-insensitive aliasing for all the type
1658 compute_flow_insensitive_aliasing (ai
);
1660 /* Compute flow-sensitive, points-to based aliasing for all the name
1662 compute_flow_sensitive_aliasing (ai
);
1664 /* Compute call clobbering information. */
1665 compute_call_clobbered (ai
);
1667 /* If the program makes no reference to global variables, but it
1668 contains a mixture of pure and non-pure functions, then we need
1669 to create use-def and def-def links between these functions to
1670 avoid invalid transformations on them. */
1671 maybe_create_global_var ();
1673 /* If the program contains ref-all pointers, finalize may-alias information
1674 for them. This pass needs to be run after call-clobbering information
1675 has been computed. */
1676 if (ai
->ref_all_symbol_mem_tag
)
1677 finalize_ref_all_pointers (ai
);
1679 /* Compute memory partitions for every memory variable. */
1680 compute_memory_partitions ();
1682 /* Remove partitions with no symbols. Partitions may end up with an
1683 empty MPT_SYMBOLS set if a previous round of alias analysis
1684 needed to partition more symbols. Since we don't need those
1685 partitions anymore, remove them to free up the space. */
1689 VEC(tree
,heap
) *mpt_table
;
1691 mpt_table
= gimple_ssa_operands (cfun
)->mpt_table
;
1693 while (i
< VEC_length (tree
, mpt_table
))
1695 mpt
= VEC_index (tree
, mpt_table
, i
);
1696 if (MPT_SYMBOLS (mpt
) == NULL
)
1697 VEC_unordered_remove (tree
, mpt_table
, i
);
1703 /* Populate all virtual operands and newly promoted register operands. */
1705 block_stmt_iterator bsi
;
1708 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
1709 update_stmt_if_modified (bsi_stmt (bsi
));
1712 /* Debugging dumps. */
1715 dump_mem_ref_stats (dump_file
);
1716 dump_alias_info (dump_file
);
1717 dump_points_to_info (dump_file
);
1719 if (dump_flags
& TDF_STATS
)
1720 dump_alias_stats (dump_file
);
1722 if (dump_flags
& TDF_DETAILS
)
1723 dump_referenced_vars (dump_file
);
1726 /* Report strict aliasing violations. */
1727 strict_aliasing_warning_backend ();
1729 /* Deallocate memory used by aliasing data structures. */
1730 delete_alias_info (ai
);
1736 struct tree_opt_pass pass_may_alias
=
1740 compute_may_aliases
, /* execute */
1743 0, /* static_pass_number */
1744 TV_TREE_MAY_ALIAS
, /* tv_id */
1745 PROP_cfg
| PROP_ssa
, /* properties_required */
1746 PROP_alias
, /* properties_provided */
1747 0, /* properties_destroyed */
1748 0, /* todo_flags_start */
1753 | TODO_verify_stmts
, /* todo_flags_finish */
1758 /* Data structure used to count the number of dereferences to PTR
1759 inside an expression. */
1767 /* Helper for count_uses_and_derefs. Called by walk_tree to look for
1768 (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
1771 count_ptr_derefs (tree
*tp
, int *walk_subtrees
, void *data
)
1773 struct count_ptr_d
*count_p
= (struct count_ptr_d
*) data
;
1775 /* Do not walk inside ADDR_EXPR nodes. In the expression &ptr->fld,
1776 pointer 'ptr' is *not* dereferenced, it is simply used to compute
1777 the address of 'fld' as 'ptr + offsetof(fld)'. */
1778 if (TREE_CODE (*tp
) == ADDR_EXPR
)
1784 if (INDIRECT_REF_P (*tp
) && TREE_OPERAND (*tp
, 0) == count_p
->ptr
)
1791 /* Count the number of direct and indirect uses for pointer PTR in
1792 statement STMT. The number of direct uses is stored in
1793 *NUM_USES_P. Indirect references are counted separately depending
1794 on whether they are store or load operations. The counts are
1795 stored in *NUM_STORES_P and *NUM_LOADS_P. */
1798 count_uses_and_derefs (tree ptr
, tree stmt
, unsigned *num_uses_p
,
1799 unsigned *num_loads_p
, unsigned *num_stores_p
)
1808 /* Find out the total number of uses of PTR in STMT. */
1809 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
1813 /* Now count the number of indirect references to PTR. This is
1814 truly awful, but we don't have much choice. There are no parent
1815 pointers inside INDIRECT_REFs, so an expression like
1816 '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
1817 find all the indirect and direct uses of x_1 inside. The only
1818 shortcut we can take is the fact that GIMPLE only allows
1819 INDIRECT_REFs inside the expressions below. */
1820 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
1821 || (TREE_CODE (stmt
) == RETURN_EXPR
1822 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == GIMPLE_MODIFY_STMT
)
1823 || TREE_CODE (stmt
) == ASM_EXPR
1824 || TREE_CODE (stmt
) == CALL_EXPR
)
1828 if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
1830 lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
1831 rhs
= GIMPLE_STMT_OPERAND (stmt
, 1);
1833 else if (TREE_CODE (stmt
) == RETURN_EXPR
)
1835 tree e
= TREE_OPERAND (stmt
, 0);
1836 lhs
= GIMPLE_STMT_OPERAND (e
, 0);
1837 rhs
= GIMPLE_STMT_OPERAND (e
, 1);
1839 else if (TREE_CODE (stmt
) == ASM_EXPR
)
1841 lhs
= ASM_OUTPUTS (stmt
);
1842 rhs
= ASM_INPUTS (stmt
);
1851 && (TREE_CODE (lhs
) == TREE_LIST
1853 || GIMPLE_STMT_P (lhs
)))
1855 struct count_ptr_d count
;
1858 walk_tree (&lhs
, count_ptr_derefs
, &count
, NULL
);
1859 *num_stores_p
= count
.count
;
1863 && (TREE_CODE (rhs
) == TREE_LIST
1865 || GIMPLE_STMT_P (rhs
)))
1867 struct count_ptr_d count
;
1870 walk_tree (&rhs
, count_ptr_derefs
, &count
, NULL
);
1871 *num_loads_p
= count
.count
;
1875 gcc_assert (*num_uses_p
>= *num_loads_p
+ *num_stores_p
);
1879 /* Helper for delete_mem_ref_stats. Free all the slots in the
1880 mem_sym_stats map. */
1883 delete_mem_sym_stats (void *key ATTRIBUTE_UNUSED
, void **value
,
1884 void *data ATTRIBUTE_UNUSED
)
1892 /* Remove memory references stats for function FN. */
1895 delete_mem_ref_stats (struct function
*fn
)
1897 if (gimple_mem_ref_stats (fn
)->mem_sym_stats
)
1899 pointer_map_traverse (gimple_mem_ref_stats (fn
)->mem_sym_stats
,
1900 delete_mem_sym_stats
, NULL
);
1901 pointer_map_destroy (gimple_mem_ref_stats (fn
)->mem_sym_stats
);
1904 gimple_mem_ref_stats (fn
)->mem_sym_stats
= NULL
;
1908 /* Initialize memory reference stats. */
1911 init_mem_ref_stats (void)
1913 struct mem_ref_stats_d
*mem_ref_stats
= gimple_mem_ref_stats (cfun
);
1915 if (mem_ref_stats
->mem_sym_stats
)
1916 delete_mem_ref_stats (cfun
);
1918 memset (mem_ref_stats
, 0, sizeof (struct mem_ref_stats_d
));
1919 mem_ref_stats
->mem_sym_stats
= pointer_map_create ();
1923 /* Initialize the data structures used for alias analysis. */
1925 static struct alias_info
*
1926 init_alias_info (void)
1928 struct alias_info
*ai
;
1929 referenced_var_iterator rvi
;
1932 ai
= XCNEW (struct alias_info
);
1933 ai
->ssa_names_visited
= sbitmap_alloc (num_ssa_names
);
1934 sbitmap_zero (ai
->ssa_names_visited
);
1935 ai
->processed_ptrs
= VEC_alloc (tree
, heap
, 50);
1936 ai
->written_vars
= pointer_set_create ();
1937 ai
->dereferenced_ptrs_store
= pointer_set_create ();
1938 ai
->dereferenced_ptrs_load
= pointer_set_create ();
1940 /* Clear out all memory reference stats. */
1941 init_mem_ref_stats ();
1943 /* If aliases have been computed before, clear existing information. */
1944 if (gimple_aliases_computed_p (cfun
))
1948 bitmap_obstack_release (&alias_bitmap_obstack
);
1950 /* Similarly, clear the set of addressable variables. In this
1951 case, we can just clear the set because addressability is
1952 only computed here. */
1953 bitmap_clear (gimple_addressable_vars (cfun
));
1955 /* Clear flow-insensitive alias information from each symbol. */
1956 FOR_EACH_REFERENCED_VAR (var
, rvi
)
1958 if (is_gimple_reg (var
))
1962 MTAG_ALIASES (var
) = NULL
;
1964 /* Memory partition information will be computed from scratch. */
1965 if (TREE_CODE (var
) == MEMORY_PARTITION_TAG
)
1966 MPT_SYMBOLS (var
) = NULL
;
1968 /* Since we are about to re-discover call-clobbered
1969 variables, clear the call-clobbered flag. Variables that
1970 are intrinsically call-clobbered (globals, local statics,
1971 etc) will not be marked by the aliasing code, so we can't
1972 remove them from CALL_CLOBBERED_VARS.
1974 NB: STRUCT_FIELDS are still call clobbered if they are
1975 for a global variable, so we *don't* clear their call
1976 clobberedness just because they are tags, though we will
1977 clear it if they aren't for global variables. */
1978 if (TREE_CODE (var
) == NAME_MEMORY_TAG
1979 || TREE_CODE (var
) == SYMBOL_MEMORY_TAG
1980 || TREE_CODE (var
) == MEMORY_PARTITION_TAG
1981 || !is_global_var (var
))
1982 clear_call_clobbered (var
);
1985 /* Clear flow-sensitive points-to information from each SSA name. */
1986 for (i
= 1; i
< num_ssa_names
; i
++)
1988 tree name
= ssa_name (i
);
1990 if (!name
|| !POINTER_TYPE_P (TREE_TYPE (name
)))
1993 if (SSA_NAME_PTR_INFO (name
))
1995 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (name
);
1997 /* Clear all the flags but keep the name tag to
1998 avoid creating new temporaries unnecessarily. If
1999 this pointer is found to point to a subset or
2000 superset of its former points-to set, then a new
2001 tag will need to be created in create_name_tags. */
2002 pi
->pt_anything
= 0;
2004 pi
->value_escapes_p
= 0;
2005 pi
->is_dereferenced
= 0;
2007 bitmap_clear (pi
->pt_vars
);
2013 /* If this is the first time we compute aliasing information,
2014 every non-register symbol will need to be put into SSA form
2015 (the initial SSA form only operates on GIMPLE registers). */
2016 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2017 if (!is_gimple_reg (var
))
2018 mark_sym_for_renaming (var
);
2021 /* Next time, we will need to reset alias information. */
2022 cfun
->gimple_df
->aliases_computed_p
= true;
2023 bitmap_obstack_initialize (&alias_bitmap_obstack
);
2029 /* Deallocate memory used by alias analysis. */
2032 delete_alias_info (struct alias_info
*ai
)
2036 sbitmap_free (ai
->ssa_names_visited
);
2038 VEC_free (tree
, heap
, ai
->processed_ptrs
);
2040 for (i
= 0; i
< ai
->num_addressable_vars
; i
++)
2041 free (ai
->addressable_vars
[i
]);
2042 free (ai
->addressable_vars
);
2044 for (i
= 0; i
< ai
->num_pointers
; i
++)
2045 free (ai
->pointers
[i
]);
2046 free (ai
->pointers
);
2048 pointer_set_destroy (ai
->written_vars
);
2049 pointer_set_destroy (ai
->dereferenced_ptrs_store
);
2050 pointer_set_destroy (ai
->dereferenced_ptrs_load
);
2053 delete_points_to_sets ();
2057 /* Used for hashing to identify pointer infos with identical
2061 eq_ptr_info (const void *p1
, const void *p2
)
2063 const struct ptr_info_def
*n1
= (const struct ptr_info_def
*) p1
;
2064 const struct ptr_info_def
*n2
= (const struct ptr_info_def
*) p2
;
2065 return bitmap_equal_p (n1
->pt_vars
, n2
->pt_vars
);
2069 ptr_info_hash (const void *p
)
2071 const struct ptr_info_def
*n
= (const struct ptr_info_def
*) p
;
2072 return bitmap_hash (n
->pt_vars
);
2076 /* Create name tags for all the pointers that have been dereferenced.
2077 We only create a name tag for a pointer P if P is found to point to
2078 a set of variables (so that we can alias them to *P) or if it is
2079 the result of a call to malloc (which means that P cannot point to
2080 anything else nor alias any other variable).
2082 If two pointers P and Q point to the same set of variables, they
2083 are assigned the same name tag. */
2086 create_name_tags (void)
2089 VEC (tree
, heap
) *with_ptvars
= NULL
;
2093 /* Collect the list of pointers with a non-empty points to set. */
2094 for (i
= 1; i
< num_ssa_names
; i
++)
2096 tree ptr
= ssa_name (i
);
2097 struct ptr_info_def
*pi
;
2100 || !POINTER_TYPE_P (TREE_TYPE (ptr
))
2101 || !SSA_NAME_PTR_INFO (ptr
))
2104 pi
= SSA_NAME_PTR_INFO (ptr
);
2106 if (pi
->pt_anything
|| !pi
->is_dereferenced
)
2108 /* No name tags for pointers that have not been
2109 dereferenced or point to an arbitrary location. */
2110 pi
->name_mem_tag
= NULL_TREE
;
2114 /* Set pt_anything on the pointers without pt_vars filled in so
2115 that they are assigned a symbol tag. */
2116 if (pi
->pt_vars
&& !bitmap_empty_p (pi
->pt_vars
))
2117 VEC_safe_push (tree
, heap
, with_ptvars
, ptr
);
2119 set_pt_anything (ptr
);
2122 /* If we didn't find any pointers with pt_vars set, we're done. */
2126 ptr_hash
= htab_create (10, ptr_info_hash
, eq_ptr_info
, NULL
);
2128 /* Now go through the pointers with pt_vars, and find a name tag
2129 with the same pt_vars as this pointer, or create one if one
2131 for (i
= 0; VEC_iterate (tree
, with_ptvars
, i
, ptr
); i
++)
2133 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
2134 tree old_name_tag
= pi
->name_mem_tag
;
2135 struct ptr_info_def
**slot
;
2137 /* If PTR points to a set of variables, check if we don't
2138 have another pointer Q with the same points-to set before
2139 creating a tag. If so, use Q's tag instead of creating a
2142 This is important for not creating unnecessary symbols
2143 and also for copy propagation. If we ever need to
2144 propagate PTR into Q or vice-versa, we would run into
2145 problems if they both had different name tags because
2146 they would have different SSA version numbers (which
2147 would force us to take the name tags in and out of SSA). */
2148 slot
= (struct ptr_info_def
**) htab_find_slot (ptr_hash
, pi
, INSERT
);
2150 pi
->name_mem_tag
= (*slot
)->name_mem_tag
;
2154 /* If we didn't find a pointer with the same points-to set
2155 as PTR, create a new name tag if needed. */
2156 if (pi
->name_mem_tag
== NULL_TREE
)
2157 pi
->name_mem_tag
= get_nmt_for (ptr
);
2160 /* If the new name tag computed for PTR is different than
2161 the old name tag that it used to have, then the old tag
2162 needs to be removed from the IL, so we mark it for
2164 if (old_name_tag
&& old_name_tag
!= pi
->name_mem_tag
)
2165 mark_sym_for_renaming (old_name_tag
);
2167 TREE_THIS_VOLATILE (pi
->name_mem_tag
)
2168 |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr
)));
2170 /* Mark the new name tag for renaming. */
2171 mark_sym_for_renaming (pi
->name_mem_tag
);
2174 htab_delete (ptr_hash
);
2176 VEC_free (tree
, heap
, with_ptvars
);
2180 /* Union the alias set SET into the may-aliases for TAG. */
2183 union_alias_set_into (tree tag
, bitmap set
)
2185 bitmap ma
= MTAG_ALIASES (tag
);
2187 if (bitmap_empty_p (set
))
2191 ma
= MTAG_ALIASES (tag
) = BITMAP_ALLOC (&alias_bitmap_obstack
);
2192 bitmap_ior_into (ma
, set
);
2196 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
2197 the name memory tag (NMT) associated with P_i. If P_i escapes, then its
2198 name tag and the variables it points-to are call-clobbered. Finally, if
2199 P_i escapes and we could not determine where it points to, then all the
2200 variables in the same alias set as *P_i are marked call-clobbered. This
2201 is necessary because we must assume that P_i may take the address of any
2202 variable in the same alias set. */
2205 compute_flow_sensitive_aliasing (struct alias_info
*ai
)
2212 for (i
= 0; VEC_iterate (tree
, ai
->processed_ptrs
, i
, ptr
); i
++)
2214 if (!find_what_p_points_to (ptr
))
2215 set_pt_anything (ptr
);
2218 create_name_tags ();
2220 for (i
= 0; VEC_iterate (tree
, ai
->processed_ptrs
, i
, ptr
); i
++)
2222 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
2223 tree tag
= symbol_mem_tag (SSA_NAME_VAR (ptr
));
2225 /* Set up aliasing information for PTR's name memory tag (if it has
2226 one). Note that only pointers that have been dereferenced will
2227 have a name memory tag. */
2228 if (pi
->name_mem_tag
&& pi
->pt_vars
)
2230 if (!bitmap_empty_p (pi
->pt_vars
))
2232 union_alias_set_into (pi
->name_mem_tag
, pi
->pt_vars
);
2233 union_alias_set_into (tag
, pi
->pt_vars
);
2234 bitmap_clear_bit (MTAG_ALIASES (tag
), DECL_UID (tag
));
2236 /* It may be the case that this the tag uid was the only
2237 bit we had set in the aliases list, and in this case,
2238 we don't want to keep an empty bitmap, as this
2239 asserts in tree-ssa-operands.c . */
2240 if (bitmap_empty_p (MTAG_ALIASES (tag
)))
2241 BITMAP_FREE (MTAG_ALIASES (tag
));
2248 /* Return TRUE if at least one symbol in TAG2's alias set is also
2249 present in TAG1's alias set. */
2252 have_common_aliases_p (bitmap tag1aliases
, bitmap tag2aliases
)
2255 /* This is the old behavior of have_common_aliases_p, which is to
2256 return false if both sets are empty, or one set is and the other
2258 if ((tag1aliases
== NULL
&& tag2aliases
!= NULL
)
2259 || (tag2aliases
== NULL
&& tag1aliases
!= NULL
)
2260 || (tag1aliases
== NULL
&& tag2aliases
== NULL
))
2263 return bitmap_intersect_p (tag1aliases
, tag2aliases
);
2266 /* Compute type-based alias sets. Traverse all the pointers and
2267 addressable variables found in setup_pointers_and_addressables.
2269 For every pointer P in AI->POINTERS and addressable variable V in
2270 AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's symbol
2271 memory tag (SMT) if their alias sets conflict. V is then marked as
2272 an aliased symbol so that the operand scanner knows that statements
2273 containing V have aliased operands. */
2276 compute_flow_insensitive_aliasing (struct alias_info
*ai
)
2280 /* For every pointer P, determine which addressable variables may alias
2281 with P's symbol memory tag. */
2282 for (i
= 0; i
< ai
->num_pointers
; i
++)
2285 struct alias_map_d
*p_map
= ai
->pointers
[i
];
2286 tree tag
= symbol_mem_tag (p_map
->var
);
2289 /* Call-clobbering information is not finalized yet at this point. */
2290 if (PTR_IS_REF_ALL (p_map
->var
))
2293 for (j
= 0; j
< ai
->num_addressable_vars
; j
++)
2295 struct alias_map_d
*v_map
;
2297 bool tag_stored_p
, var_stored_p
;
2299 v_map
= ai
->addressable_vars
[j
];
2301 v_ann
= var_ann (var
);
2303 /* Skip memory tags and variables that have never been
2304 written to. We also need to check if the variables are
2305 call-clobbered because they may be overwritten by
2307 tag_stored_p
= pointer_set_contains (ai
->written_vars
, tag
)
2308 || is_call_clobbered (tag
);
2309 var_stored_p
= pointer_set_contains (ai
->written_vars
, var
)
2310 || is_call_clobbered (var
);
2311 if (!tag_stored_p
&& !var_stored_p
)
2314 if (may_alias_p (p_map
->var
, p_map
->set
, var
, v_map
->set
, false))
2316 /* We should never have a var with subvars here, because
2317 they shouldn't get into the set of addressable vars */
2318 gcc_assert (!var_can_have_subvars (var
)
2319 || get_subvars_for_var (var
) == NULL
);
2321 /* Add VAR to TAG's may-aliases set. */
2322 add_may_alias (tag
, var
);
2327 /* Since this analysis is based exclusively on symbols, it fails to
2328 handle cases where two pointers P and Q have different memory
2329 tags with conflicting alias set numbers but no aliased symbols in
2332 For example, suppose that we have two memory tags SMT.1 and SMT.2
2335 may-aliases (SMT.1) = { a }
2336 may-aliases (SMT.2) = { b }
2338 and the alias set number of SMT.1 conflicts with that of SMT.2.
2339 Since they don't have symbols in common, loads and stores from
2340 SMT.1 and SMT.2 will seem independent of each other, which will
2341 lead to the optimizers making invalid transformations (see
2342 testsuite/gcc.c-torture/execute/pr15262-[12].c).
2344 To avoid this problem, we do a final traversal of AI->POINTERS
2345 looking for pairs of pointers that have no aliased symbols in
2346 common and yet have conflicting alias set numbers. */
2347 for (i
= 0; i
< ai
->num_pointers
; i
++)
2350 struct alias_map_d
*p_map1
= ai
->pointers
[i
];
2351 tree tag1
= symbol_mem_tag (p_map1
->var
);
2352 bitmap may_aliases1
= MTAG_ALIASES (tag1
);
2354 if (PTR_IS_REF_ALL (p_map1
->var
))
2357 for (j
= i
+ 1; j
< ai
->num_pointers
; j
++)
2359 struct alias_map_d
*p_map2
= ai
->pointers
[j
];
2360 tree tag2
= symbol_mem_tag (p_map2
->var
);
2361 bitmap may_aliases2
= may_aliases (tag2
);
2363 if (PTR_IS_REF_ALL (p_map2
->var
))
2366 /* If the pointers may not point to each other, do nothing. */
2367 if (!may_alias_p (p_map1
->var
, p_map1
->set
, tag2
, p_map2
->set
, true))
2370 /* The two pointers may alias each other. If they already have
2371 symbols in common, do nothing. */
2372 if (have_common_aliases_p (may_aliases1
, may_aliases2
))
2375 if (may_aliases2
&& !bitmap_empty_p (may_aliases2
))
2377 union_alias_set_into (tag1
, may_aliases2
);
2381 /* Since TAG2 does not have any aliases of its own, add
2382 TAG2 itself to the alias set of TAG1. */
2383 add_may_alias (tag1
, tag2
);
2391 /* Finalize may-alias information for ref-all pointers. Traverse all
2392 the addressable variables found in setup_pointers_and_addressables.
2394 If flow-sensitive alias analysis has attached a name memory tag to
2395 a ref-all pointer, we will use it for the dereferences because that
2396 will have more precise aliasing information. But if there is no
2397 name tag, we will use a special symbol tag that aliases all the
2398 call-clobbered addressable variables. */
2401 finalize_ref_all_pointers (struct alias_info
*ai
)
2405 /* First add the real call-clobbered variables. */
2406 for (i
= 0; i
< ai
->num_addressable_vars
; i
++)
2408 tree var
= ai
->addressable_vars
[i
]->var
;
2409 if (is_call_clobbered (var
))
2410 add_may_alias (ai
->ref_all_symbol_mem_tag
, var
);
2413 /* Then add the call-clobbered pointer memory tags. See
2414 compute_flow_insensitive_aliasing for the rationale. */
2415 for (i
= 0; i
< ai
->num_pointers
; i
++)
2417 tree ptr
= ai
->pointers
[i
]->var
, tag
;
2418 /* Avoid adding to self and clean up. */
2419 if (PTR_IS_REF_ALL (ptr
))
2421 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
2422 if (pi
->is_dereferenced
)
2423 pi
->pt_anything
= 0;
2426 tag
= symbol_mem_tag (ptr
);
2427 if (is_call_clobbered (tag
))
2428 add_may_alias (ai
->ref_all_symbol_mem_tag
, tag
);
2434 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */
2437 create_alias_map_for (tree var
, struct alias_info
*ai
)
2439 struct alias_map_d
*alias_map
;
2440 alias_map
= XCNEW (struct alias_map_d
);
2441 alias_map
->var
= var
;
2442 alias_map
->set
= get_alias_set (var
);
2443 ai
->addressable_vars
[ai
->num_addressable_vars
++] = alias_map
;
2447 /* Create memory tags for all the dereferenced pointers and build the
2448 ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
2449 sets. Based on the address escape and points-to information collected
2450 earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
2451 variables whose address is not needed anymore. */
2454 setup_pointers_and_addressables (struct alias_info
*ai
)
2456 size_t num_addressable_vars
, num_pointers
;
2457 referenced_var_iterator rvi
;
2459 VEC (tree
, heap
) *varvec
= NULL
;
2460 safe_referenced_var_iterator srvi
;
2462 /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
2463 num_addressable_vars
= num_pointers
= 0;
2465 FOR_EACH_REFERENCED_VAR (var
, rvi
)
2467 if (may_be_aliased (var
))
2468 num_addressable_vars
++;
2470 if (POINTER_TYPE_P (TREE_TYPE (var
)))
2472 /* Since we don't keep track of volatile variables, assume that
2473 these pointers are used in indirect store operations. */
2474 if (TREE_THIS_VOLATILE (var
))
2475 pointer_set_insert (ai
->dereferenced_ptrs_store
, var
);
2481 /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
2482 always going to be slightly bigger than we actually need them
2483 because some TREE_ADDRESSABLE variables will be marked
2484 non-addressable below and only pointers with unique symbol tags are
2485 going to be added to POINTERS. */
2486 ai
->addressable_vars
= XCNEWVEC (struct alias_map_d
*, num_addressable_vars
);
2487 ai
->pointers
= XCNEWVEC (struct alias_map_d
*, num_pointers
);
2488 ai
->num_addressable_vars
= 0;
2489 ai
->num_pointers
= 0;
2491 FOR_EACH_REFERENCED_VAR_SAFE (var
, varvec
, srvi
)
2495 /* Name memory tags already have flow-sensitive aliasing
2496 information, so they need not be processed by
2497 compute_flow_insensitive_aliasing. Similarly, symbol memory
2498 tags are already accounted for when we process their
2501 Structure fields, on the other hand, have to have some of this
2502 information processed for them, but it's pointless to mark them
2503 non-addressable (since they are fake variables anyway). */
2504 if (MTAG_P (var
) && TREE_CODE (var
) != STRUCT_FIELD_TAG
)
2507 /* Remove the ADDRESSABLE flag from every addressable variable whose
2508 address is not needed anymore. This is caused by the propagation
2509 of ADDR_EXPR constants into INDIRECT_REF expressions and the
2510 removal of dead pointer assignments done by the early scalar
2512 if (TREE_ADDRESSABLE (var
))
2514 if (!bitmap_bit_p (gimple_addressable_vars (cfun
), DECL_UID (var
))
2515 && TREE_CODE (var
) != RESULT_DECL
2516 && !is_global_var (var
))
2518 bool okay_to_mark
= true;
2520 /* Since VAR is now a regular GIMPLE register, we will need
2521 to rename VAR into SSA afterwards. */
2522 mark_sym_for_renaming (var
);
2524 /* If VAR can have sub-variables, and any of its
2525 sub-variables has its address taken, then we cannot
2526 remove the addressable flag from VAR. */
2527 if (var_can_have_subvars (var
)
2528 && (svars
= get_subvars_for_var (var
)))
2532 for (sv
= svars
; sv
; sv
= sv
->next
)
2534 if (bitmap_bit_p (gimple_addressable_vars (cfun
),
2535 DECL_UID (sv
->var
)))
2536 okay_to_mark
= false;
2537 mark_sym_for_renaming (sv
->var
);
2541 /* The address of VAR is not needed, remove the
2542 addressable bit, so that it can be optimized as a
2543 regular variable. */
2546 /* The memory partition holding VAR will no longer
2547 contain VAR, and statements referencing it will need
2549 if (memory_partition (var
))
2550 mark_sym_for_renaming (memory_partition (var
));
2552 mark_non_addressable (var
);
2557 /* Global variables and addressable locals may be aliased. Create an
2558 entry in ADDRESSABLE_VARS for VAR. */
2559 if (may_be_aliased (var
))
2561 if (!var_can_have_subvars (var
)
2562 || get_subvars_for_var (var
) == NULL
)
2563 create_alias_map_for (var
, ai
);
2565 mark_sym_for_renaming (var
);
2568 /* Add pointer variables that have been dereferenced to the POINTERS
2569 array and create a symbol memory tag for them. */
2570 if (POINTER_TYPE_P (TREE_TYPE (var
)))
2572 if ((pointer_set_contains (ai
->dereferenced_ptrs_store
, var
)
2573 || pointer_set_contains (ai
->dereferenced_ptrs_load
, var
)))
2578 /* If pointer VAR still doesn't have a memory tag
2579 associated with it, create it now or re-use an
2581 tag
= get_smt_for (var
, ai
);
2582 t_ann
= var_ann (tag
);
2584 /* The symbol tag will need to be renamed into SSA
2585 afterwards. Note that we cannot do this inside
2586 get_smt_for because aliasing may run multiple times
2587 and we only create symbol tags the first time. */
2588 mark_sym_for_renaming (tag
);
2590 /* Similarly, if pointer VAR used to have another type
2591 tag, we will need to process it in the renamer to
2592 remove the stale virtual operands. */
2593 old_tag
= symbol_mem_tag (var
);
2595 mark_sym_for_renaming (old_tag
);
2597 /* Associate the tag with pointer VAR. */
2598 set_symbol_mem_tag (var
, tag
);
2600 /* If pointer VAR has been used in a store operation,
2601 then its memory tag must be marked as written-to. */
2602 if (pointer_set_contains (ai
->dereferenced_ptrs_store
, var
))
2603 pointer_set_insert (ai
->written_vars
, tag
);
2607 /* The pointer has not been dereferenced. If it had a
2608 symbol memory tag, remove it and mark the old tag for
2609 renaming to remove it out of the IL. */
2610 tree tag
= symbol_mem_tag (var
);
2613 mark_sym_for_renaming (tag
);
2614 set_symbol_mem_tag (var
, NULL_TREE
);
2620 VEC_free (tree
, heap
, varvec
);
2624 /* Determine whether to use .GLOBAL_VAR to model call clobbering
2625 semantics. If the function makes no references to global
2626 variables and contains at least one call to a non-pure function,
2627 then we need to mark the side-effects of the call using .GLOBAL_VAR
2628 to represent all possible global memory referenced by the callee. */
2631 maybe_create_global_var (void)
2633 /* No need to create it, if we have one already. */
2634 if (gimple_global_var (cfun
) == NULL_TREE
)
2636 struct mem_ref_stats_d
*stats
= gimple_mem_ref_stats (cfun
);
2638 /* Create .GLOBAL_VAR if there are no call-clobbered
2639 variables and the program contains a mixture of pure/const
2640 and regular function calls. This is to avoid the problem
2641 described in PR 20115:
2644 int func_pure (void) { return X; }
2645 int func_non_pure (int a) { X += a; }
2648 int a = func_pure ();
2654 Since foo() has no call-clobbered variables, there is
2655 no relationship between the calls to func_pure and
2656 func_non_pure. Since func_pure has no side-effects, value
2657 numbering optimizations elide the second call to func_pure.
2658 So, if we have some pure/const and some regular calls in the
2659 program we create .GLOBAL_VAR to avoid missing these
2661 if (bitmap_count_bits (gimple_call_clobbered_vars (cfun
)) == 0
2662 && stats
->num_call_sites
> 0
2663 && stats
->num_pure_const_call_sites
> 0
2664 && stats
->num_call_sites
> stats
->num_pure_const_call_sites
)
2665 create_global_var ();
2670 /* Return TRUE if pointer PTR may point to variable VAR.
2672 MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
2673 This is needed because when checking for type conflicts we are
2674 interested in the alias set of the memory location pointed-to by
2675 PTR. The alias set of PTR itself is irrelevant.
2677 VAR_ALIAS_SET is the alias set for VAR. */
2680 may_alias_p (tree ptr
, HOST_WIDE_INT mem_alias_set
,
2681 tree var
, HOST_WIDE_INT var_alias_set
,
2682 bool alias_set_only
)
2686 alias_stats
.alias_queries
++;
2687 alias_stats
.simple_queries
++;
2689 /* By convention, a variable cannot alias itself. */
2690 mem
= symbol_mem_tag (ptr
);
2693 alias_stats
.alias_noalias
++;
2694 alias_stats
.simple_resolved
++;
2698 /* If -fargument-noalias-global is > 2, pointer arguments may
2699 not point to anything else. */
2700 if (flag_argument_noalias
> 2 && TREE_CODE (ptr
) == PARM_DECL
)
2702 alias_stats
.alias_noalias
++;
2703 alias_stats
.simple_resolved
++;
2707 /* If -fargument-noalias-global is > 1, pointer arguments may
2708 not point to global variables. */
2709 if (flag_argument_noalias
> 1 && is_global_var (var
)
2710 && TREE_CODE (ptr
) == PARM_DECL
)
2712 alias_stats
.alias_noalias
++;
2713 alias_stats
.simple_resolved
++;
2717 /* If either MEM or VAR is a read-only global and the other one
2718 isn't, then PTR cannot point to VAR. */
2719 if ((unmodifiable_var_p (mem
) && !unmodifiable_var_p (var
))
2720 || (unmodifiable_var_p (var
) && !unmodifiable_var_p (mem
)))
2722 alias_stats
.alias_noalias
++;
2723 alias_stats
.simple_resolved
++;
2727 gcc_assert (TREE_CODE (mem
) == SYMBOL_MEMORY_TAG
);
2729 if (!DECL_NO_TBAA_P (ptr
))
2731 alias_stats
.tbaa_queries
++;
2733 /* If the alias sets don't conflict then MEM cannot alias VAR. */
2734 if (!alias_sets_conflict_p (mem_alias_set
, var_alias_set
))
2736 alias_stats
.alias_noalias
++;
2737 alias_stats
.tbaa_resolved
++;
2741 /* If VAR is a record or union type, PTR cannot point into VAR
2742 unless there is some explicit address operation in the
2743 program that can reference a field of the type pointed-to by
2744 PTR. This also assumes that the types of both VAR and PTR
2745 are contained within the compilation unit, and that there is
2746 no fancy addressing arithmetic associated with any of the
2748 if (mem_alias_set
!= 0 && var_alias_set
!= 0)
2750 tree ptr_type
= TREE_TYPE (ptr
);
2751 tree var_type
= TREE_TYPE (var
);
2753 /* The star count is -1 if the type at the end of the
2754 pointer_to chain is not a record or union type. */
2755 if ((!alias_set_only
) &&
2756 ipa_type_escape_star_count_of_interesting_type (var_type
) >= 0)
2758 int ptr_star_count
= 0;
2760 /* ipa_type_escape_star_count_of_interesting_type is a
2761 little too restrictive for the pointer type, need to
2762 allow pointers to primitive types as long as those
2763 types cannot be pointers to everything. */
2764 while (POINTER_TYPE_P (ptr_type
))
2766 /* Strip the *s off. */
2767 ptr_type
= TREE_TYPE (ptr_type
);
2771 /* There does not appear to be a better test to see if
2772 the pointer type was one of the pointer to everything
2774 if (ptr_star_count
> 0)
2776 alias_stats
.structnoaddress_queries
++;
2777 if (ipa_type_escape_field_does_not_clobber_p (var_type
,
2780 alias_stats
.structnoaddress_resolved
++;
2781 alias_stats
.alias_noalias
++;
2785 else if (ptr_star_count
== 0)
2787 /* If PTR_TYPE was not really a pointer to type, it cannot
2789 alias_stats
.structnoaddress_queries
++;
2790 alias_stats
.structnoaddress_resolved
++;
2791 alias_stats
.alias_noalias
++;
2798 alias_stats
.alias_mayalias
++;
2803 /* Add ALIAS to the set of variables that may alias VAR. */
2806 add_may_alias (tree var
, tree alias
)
2808 /* Don't allow self-referential aliases. */
2809 gcc_assert (var
!= alias
);
2811 /* ALIAS must be addressable if it's being added to an alias set. */
2813 TREE_ADDRESSABLE (alias
) = 1;
2815 gcc_assert (may_be_aliased (alias
));
2818 /* VAR must be a symbol or a name tag. */
2819 gcc_assert (TREE_CODE (var
) == SYMBOL_MEMORY_TAG
2820 || TREE_CODE (var
) == NAME_MEMORY_TAG
);
2822 if (MTAG_ALIASES (var
) == NULL
)
2823 MTAG_ALIASES (var
) = BITMAP_ALLOC (&alias_bitmap_obstack
);
2825 bitmap_set_bit (MTAG_ALIASES (var
), DECL_UID (alias
));
2829 /* Mark pointer PTR as pointing to an arbitrary memory location. */
2832 set_pt_anything (tree ptr
)
2834 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
2836 pi
->pt_anything
= 1;
2839 /* The pointer used to have a name tag, but we now found it pointing
2840 to an arbitrary location. The name tag needs to be renamed and
2841 disassociated from PTR. */
2842 if (pi
->name_mem_tag
)
2844 mark_sym_for_renaming (pi
->name_mem_tag
);
2845 pi
->name_mem_tag
= NULL_TREE
;
2850 /* Return true if STMT is an "escape" site from the current function. Escape
2851 sites those statements which might expose the address of a variable
2852 outside the current function. STMT is an escape site iff:
2854 1- STMT is a function call, or
2855 2- STMT is an __asm__ expression, or
2856 3- STMT is an assignment to a non-local variable, or
2857 4- STMT is a return statement.
2859 Return the type of escape site found, if we found one, or NO_ESCAPE
2863 is_escape_site (tree stmt
)
2865 tree call
= get_call_expr_in (stmt
);
2866 if (call
!= NULL_TREE
)
2868 if (!TREE_SIDE_EFFECTS (call
))
2869 return ESCAPE_TO_PURE_CONST
;
2871 return ESCAPE_TO_CALL
;
2873 else if (TREE_CODE (stmt
) == ASM_EXPR
)
2874 return ESCAPE_TO_ASM
;
2875 else if (TREE_CODE (stmt
) == GIMPLE_MODIFY_STMT
)
2877 tree lhs
= GIMPLE_STMT_OPERAND (stmt
, 0);
2879 /* Get to the base of _REF nodes. */
2880 if (TREE_CODE (lhs
) != SSA_NAME
)
2881 lhs
= get_base_address (lhs
);
2883 /* If we couldn't recognize the LHS of the assignment, assume that it
2884 is a non-local store. */
2885 if (lhs
== NULL_TREE
)
2886 return ESCAPE_UNKNOWN
;
2888 if (TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == NOP_EXPR
2889 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == CONVERT_EXPR
2890 || TREE_CODE (GIMPLE_STMT_OPERAND (stmt
, 1)) == VIEW_CONVERT_EXPR
)
2893 = TREE_TYPE (TREE_OPERAND (GIMPLE_STMT_OPERAND (stmt
, 1), 0));
2894 tree to
= TREE_TYPE (GIMPLE_STMT_OPERAND (stmt
, 1));
2896 /* If the RHS is a conversion between a pointer and an integer, the
2897 pointer escapes since we can't track the integer. */
2898 if (POINTER_TYPE_P (from
) && !POINTER_TYPE_P (to
))
2899 return ESCAPE_BAD_CAST
;
2901 /* Same if the RHS is a conversion between a regular pointer and a
2902 ref-all pointer since we can't track the SMT of the former. */
2903 if (POINTER_TYPE_P (from
) && !TYPE_REF_CAN_ALIAS_ALL (from
)
2904 && POINTER_TYPE_P (to
) && TYPE_REF_CAN_ALIAS_ALL (to
))
2905 return ESCAPE_BAD_CAST
;
2908 /* If the LHS is an SSA name, it can't possibly represent a non-local
2910 if (TREE_CODE (lhs
) == SSA_NAME
)
2913 /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
2914 local variables we cannot be sure if it will escape, because we
2915 don't have information about objects not in SSA form. Need to
2916 implement something along the lines of
2918 J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
2919 Midkiff, ``Escape analysis for java,'' in Proceedings of the
2920 Conference on Object-Oriented Programming Systems, Languages, and
2921 Applications (OOPSLA), pp. 1-19, 1999. */
2922 return ESCAPE_STORED_IN_GLOBAL
;
2924 else if (TREE_CODE (stmt
) == RETURN_EXPR
)
2925 return ESCAPE_TO_RETURN
;
2930 /* Create a new memory tag of type TYPE.
2931 Does NOT push it into the current binding. */
2934 create_tag_raw (enum tree_code code
, tree type
, const char *prefix
)
2938 tmp_var
= build_decl (code
, create_tmp_var_name (prefix
), type
);
2940 /* Make the variable writable. */
2941 TREE_READONLY (tmp_var
) = 0;
2943 /* It doesn't start out global. */
2944 MTAG_GLOBAL (tmp_var
) = 0;
2945 TREE_STATIC (tmp_var
) = 0;
2946 TREE_USED (tmp_var
) = 1;
2951 /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
2952 is considered to represent all the pointers whose pointed-to types are
2953 in the same alias set class. Otherwise, the tag represents a single
2954 SSA_NAME pointer variable. */
2957 create_memory_tag (tree type
, bool is_type_tag
)
2959 tree tag
= create_tag_raw (is_type_tag
? SYMBOL_MEMORY_TAG
: NAME_MEMORY_TAG
,
2960 type
, (is_type_tag
) ? "SMT" : "NMT");
2962 /* By default, memory tags are local variables. Alias analysis will
2963 determine whether they should be considered globals. */
2964 DECL_CONTEXT (tag
) = current_function_decl
;
2966 /* Memory tags are by definition addressable. */
2967 TREE_ADDRESSABLE (tag
) = 1;
2969 set_symbol_mem_tag (tag
, NULL_TREE
);
2971 /* Add the tag to the symbol table. */
2972 add_referenced_var (tag
);
2978 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
2979 This is used if P_i has been found to point to a specific set of
2980 variables or to a non-aliased memory location like the address returned
2981 by malloc functions. */
2984 get_nmt_for (tree ptr
)
2986 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
2987 tree tag
= pi
->name_mem_tag
;
2989 if (tag
== NULL_TREE
)
2990 tag
= create_memory_tag (TREE_TYPE (TREE_TYPE (ptr
)), false);
2995 /* Return the symbol memory tag associated to pointer PTR. A memory
2996 tag is an artificial variable that represents the memory location
2997 pointed-to by PTR. It is used to model the effects of pointer
2998 de-references on addressable variables.
3000 AI points to the data gathered during alias analysis. This
3001 function populates the array AI->POINTERS. */
3004 get_smt_for (tree ptr
, struct alias_info
*ai
)
3008 tree tag_type
= TREE_TYPE (TREE_TYPE (ptr
));
3009 HOST_WIDE_INT tag_set
= get_alias_set (tag_type
);
3011 /* We use a unique memory tag for all the ref-all pointers. */
3012 if (PTR_IS_REF_ALL (ptr
))
3014 if (!ai
->ref_all_symbol_mem_tag
)
3015 ai
->ref_all_symbol_mem_tag
= create_memory_tag (void_type_node
, true);
3016 return ai
->ref_all_symbol_mem_tag
;
3019 /* To avoid creating unnecessary memory tags, only create one memory tag
3020 per alias set class. Note that it may be tempting to group
3021 memory tags based on conflicting alias sets instead of
3022 equivalence. That would be wrong because alias sets are not
3023 necessarily transitive (as demonstrated by the libstdc++ test
3024 23_containers/vector/cons/4.cc). Given three alias sets A, B, C
3025 such that conflicts (A, B) == true and conflicts (A, C) == true,
3026 it does not necessarily follow that conflicts (B, C) == true. */
3027 for (i
= 0, tag
= NULL_TREE
; i
< ai
->num_pointers
; i
++)
3029 struct alias_map_d
*curr
= ai
->pointers
[i
];
3030 tree curr_tag
= symbol_mem_tag (curr
->var
);
3031 if (tag_set
== curr
->set
)
3038 /* If VAR cannot alias with any of the existing memory tags, create a new
3039 tag for PTR and add it to the POINTERS array. */
3040 if (tag
== NULL_TREE
)
3042 struct alias_map_d
*alias_map
;
3044 /* If PTR did not have a symbol tag already, create a new SMT.*
3045 artificial variable representing the memory location
3046 pointed-to by PTR. */
3047 tag
= symbol_mem_tag (ptr
);
3048 if (tag
== NULL_TREE
)
3049 tag
= create_memory_tag (tag_type
, true);
3051 /* Add PTR to the POINTERS array. Note that we are not interested in
3052 PTR's alias set. Instead, we cache the alias set for the memory that
3054 alias_map
= XCNEW (struct alias_map_d
);
3055 alias_map
->var
= ptr
;
3056 alias_map
->set
= tag_set
;
3057 ai
->pointers
[ai
->num_pointers
++] = alias_map
;
3060 /* If the pointed-to type is volatile, so is the tag. */
3061 TREE_THIS_VOLATILE (tag
) |= TREE_THIS_VOLATILE (tag_type
);
3063 /* Make sure that the symbol tag has the same alias set as the
3065 gcc_assert (tag_set
== get_alias_set (tag
));
3071 /* Create GLOBAL_VAR, an artificial global variable to act as a
3072 representative of all the variables that may be clobbered by function
3076 create_global_var (void)
3078 tree global_var
= build_decl (VAR_DECL
, get_identifier (".GLOBAL_VAR"),
3080 DECL_ARTIFICIAL (global_var
) = 1;
3081 TREE_READONLY (global_var
) = 0;
3082 DECL_EXTERNAL (global_var
) = 1;
3083 TREE_STATIC (global_var
) = 1;
3084 TREE_USED (global_var
) = 1;
3085 DECL_CONTEXT (global_var
) = NULL_TREE
;
3086 TREE_THIS_VOLATILE (global_var
) = 0;
3087 TREE_ADDRESSABLE (global_var
) = 0;
3089 create_var_ann (global_var
);
3090 mark_call_clobbered (global_var
, ESCAPE_UNKNOWN
);
3091 add_referenced_var (global_var
);
3092 mark_sym_for_renaming (global_var
);
3093 cfun
->gimple_df
->global_var
= global_var
;
3097 /* Dump alias statistics on FILE. */
3100 dump_alias_stats (FILE *file
)
3102 const char *funcname
3103 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
3104 fprintf (file
, "\nAlias statistics for %s\n\n", funcname
);
3105 fprintf (file
, "Total alias queries:\t%u\n", alias_stats
.alias_queries
);
3106 fprintf (file
, "Total alias mayalias results:\t%u\n",
3107 alias_stats
.alias_mayalias
);
3108 fprintf (file
, "Total alias noalias results:\t%u\n",
3109 alias_stats
.alias_noalias
);
3110 fprintf (file
, "Total simple queries:\t%u\n",
3111 alias_stats
.simple_queries
);
3112 fprintf (file
, "Total simple resolved:\t%u\n",
3113 alias_stats
.simple_resolved
);
3114 fprintf (file
, "Total TBAA queries:\t%u\n",
3115 alias_stats
.tbaa_queries
);
3116 fprintf (file
, "Total TBAA resolved:\t%u\n",
3117 alias_stats
.tbaa_resolved
);
3118 fprintf (file
, "Total non-addressable structure type queries:\t%u\n",
3119 alias_stats
.structnoaddress_queries
);
3120 fprintf (file
, "Total non-addressable structure type resolved:\t%u\n",
3121 alias_stats
.structnoaddress_resolved
);
3125 /* Dump alias information on FILE. */
3128 dump_alias_info (FILE *file
)
3131 const char *funcname
3132 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
3133 referenced_var_iterator rvi
;
3136 fprintf (file
, "\nAlias information for %s\n\n", funcname
);
3138 dump_memory_partitions (file
);
3140 fprintf (file
, "\nFlow-insensitive alias information for %s\n\n", funcname
);
3142 fprintf (file
, "Aliased symbols\n\n");
3144 FOR_EACH_REFERENCED_VAR (var
, rvi
)
3146 if (may_be_aliased (var
))
3147 dump_variable (file
, var
);
3150 fprintf (file
, "\nDereferenced pointers\n\n");
3152 FOR_EACH_REFERENCED_VAR (var
, rvi
)
3153 if (symbol_mem_tag (var
))
3154 dump_variable (file
, var
);
3156 fprintf (file
, "\nSymbol memory tags\n\n");
3158 FOR_EACH_REFERENCED_VAR (var
, rvi
)
3160 if (TREE_CODE (var
) == SYMBOL_MEMORY_TAG
)
3161 dump_variable (file
, var
);
3164 fprintf (file
, "\n\nFlow-sensitive alias information for %s\n\n", funcname
);
3166 fprintf (file
, "SSA_NAME pointers\n\n");
3167 for (i
= 1; i
< num_ssa_names
; i
++)
3169 tree ptr
= ssa_name (i
);
3170 struct ptr_info_def
*pi
;
3172 if (ptr
== NULL_TREE
)
3175 pi
= SSA_NAME_PTR_INFO (ptr
);
3176 if (!SSA_NAME_IN_FREE_LIST (ptr
)
3178 && pi
->name_mem_tag
)
3179 dump_points_to_info_for (file
, ptr
);
3182 fprintf (file
, "\nName memory tags\n\n");
3184 FOR_EACH_REFERENCED_VAR (var
, rvi
)
3186 if (TREE_CODE (var
) == NAME_MEMORY_TAG
)
3187 dump_variable (file
, var
);
3190 fprintf (file
, "\n");
3194 /* Dump alias information on stderr. */
3197 debug_alias_info (void)
3199 dump_alias_info (stderr
);
3203 /* Return the alias information associated with pointer T. It creates a
3204 new instance if none existed. */
3206 struct ptr_info_def
*
3207 get_ptr_info (tree t
)
3209 struct ptr_info_def
*pi
;
3211 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t
)));
3213 pi
= SSA_NAME_PTR_INFO (t
);
3216 pi
= GGC_CNEW (struct ptr_info_def
);
3217 SSA_NAME_PTR_INFO (t
) = pi
;
3224 /* Dump points-to information for SSA_NAME PTR into FILE. */
3227 dump_points_to_info_for (FILE *file
, tree ptr
)
3229 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
3231 print_generic_expr (file
, ptr
, dump_flags
);
3235 if (pi
->name_mem_tag
)
3237 fprintf (file
, ", name memory tag: ");
3238 print_generic_expr (file
, pi
->name_mem_tag
, dump_flags
);
3241 if (pi
->is_dereferenced
)
3242 fprintf (file
, ", is dereferenced (R=%ld, W=%ld)",
3243 get_mem_sym_stats_for (ptr
)->num_direct_reads
,
3244 get_mem_sym_stats_for (ptr
)->num_direct_writes
);
3246 if (pi
->value_escapes_p
)
3247 fprintf (file
, ", its value escapes");
3249 if (pi
->pt_anything
)
3250 fprintf (file
, ", points-to anything");
3253 fprintf (file
, ", points-to NULL");
3257 fprintf (file
, ", points-to vars: ");
3258 dump_decl_set (file
, pi
->pt_vars
);
3262 fprintf (file
, "\n");
3266 /* Dump points-to information for VAR into stderr. */
3269 debug_points_to_info_for (tree var
)
3271 dump_points_to_info_for (stderr
, var
);
3275 /* Dump points-to information into FILE. NOTE: This function is slow, as
3276 it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
3279 dump_points_to_info (FILE *file
)
3282 block_stmt_iterator si
;
3285 lang_hooks
.decl_printable_name (current_function_decl
, 2);
3286 referenced_var_iterator rvi
;
3289 fprintf (file
, "\n\nPointed-to sets for pointers in %s\n\n", fname
);
3291 /* First dump points-to information for the default definitions of
3292 pointer variables. This is necessary because default definitions are
3293 not part of the code. */
3294 FOR_EACH_REFERENCED_VAR (var
, rvi
)
3296 if (POINTER_TYPE_P (TREE_TYPE (var
)))
3298 tree def
= gimple_default_def (cfun
, var
);
3300 dump_points_to_info_for (file
, def
);
3304 /* Dump points-to information for every pointer defined in the program. */
3309 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
3311 tree ptr
= PHI_RESULT (phi
);
3312 if (POINTER_TYPE_P (TREE_TYPE (ptr
)))
3313 dump_points_to_info_for (file
, ptr
);
3316 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
3318 tree stmt
= bsi_stmt (si
);
3320 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
3321 if (TREE_CODE (def
) == SSA_NAME
3322 && POINTER_TYPE_P (TREE_TYPE (def
)))
3323 dump_points_to_info_for (file
, def
);
3327 fprintf (file
, "\n");
3331 /* Dump points-to info pointed to by PTO into STDERR. */
3334 debug_points_to_info (void)
3336 dump_points_to_info (stderr
);
3339 /* Dump to FILE the list of variables that may be aliasing VAR. */
3342 dump_may_aliases_for (FILE *file
, tree var
)
3346 aliases
= MTAG_ALIASES (var
);
3353 fprintf (file
, "{ ");
3354 EXECUTE_IF_SET_IN_BITMAP (aliases
, 0, i
, bi
)
3356 al
= referenced_var (i
);
3357 print_generic_expr (file
, al
, dump_flags
);
3358 fprintf (file
, " ");
3360 fprintf (file
, "}");
3365 /* Dump to stderr the list of variables that may be aliasing VAR. */
3368 debug_may_aliases_for (tree var
)
3370 dump_may_aliases_for (stderr
, var
);
3374 /* Return true if VAR may be aliased. */
3377 may_be_aliased (tree var
)
3380 if (TREE_ADDRESSABLE (var
))
3383 /* Globally visible variables can have their addresses taken by other
3384 translation units. */
3386 && (MTAG_GLOBAL (var
) || TREE_PUBLIC (var
)))
3388 else if (!MTAG_P (var
)
3389 && (DECL_EXTERNAL (var
) || TREE_PUBLIC (var
)))
3392 /* Automatic variables can't have their addresses escape any other
3393 way. This must be after the check for global variables, as
3394 extern declarations do not have TREE_STATIC set. */
3395 if (!TREE_STATIC (var
))
3398 /* If we're in unit-at-a-time mode, then we must have seen all
3399 occurrences of address-of operators, and so we can trust
3400 TREE_ADDRESSABLE. Otherwise we can only be sure the variable
3401 isn't addressable if it's local to the current function. */
3402 if (flag_unit_at_a_time
)
3405 if (decl_function_context (var
) == current_function_decl
)
3411 /* The following is based on code in add_stmt_operand to ensure that the
3412 same defs/uses/vdefs/vuses will be found after replacing a reference
3413 to var (or ARRAY_REF to var) with an INDIRECT_REF to ptr whose value
3414 is the address of var. Return a memtag for the ptr, after adding the
3415 proper may_aliases to it (which are the aliases of var, if it has any,
3419 add_may_alias_for_new_tag (tree tag
, tree var
)
3421 bitmap aliases
= NULL
;
3424 aliases
= may_aliases (var
);
3426 /* Case 1: |aliases| == 1 */
3427 if (aliases
&& bitmap_count_bits (aliases
) == 1)
3429 tree ali
= referenced_var (bitmap_first_set_bit (aliases
));
3430 if (TREE_CODE (ali
) == SYMBOL_MEMORY_TAG
)
3434 /* Case 2: |aliases| == 0 */
3435 if (aliases
== NULL
)
3436 add_may_alias (tag
, var
);
3439 /* Case 3: |aliases| > 1 */
3440 union_alias_set_into (tag
, aliases
);
3445 /* Create a new symbol tag for PTR. Construct the may-alias list of this type
3446 tag so that it has the aliasing of VAR, or of the relevant subvars of VAR
3447 according to the location accessed by EXPR.
3449 Note, the set of aliases represented by the new symbol tag are not marked
3453 new_type_alias (tree ptr
, tree var
, tree expr
)
3455 tree tag_type
= TREE_TYPE (TREE_TYPE (ptr
));
3458 tree ali
= NULL_TREE
;
3459 HOST_WIDE_INT offset
, size
, maxsize
;
3461 VEC (tree
, heap
) *overlaps
= NULL
;
3465 gcc_assert (symbol_mem_tag (ptr
) == NULL_TREE
);
3466 gcc_assert (!MTAG_P (var
));
3468 ref
= get_ref_base_and_extent (expr
, &offset
, &size
, &maxsize
);
3471 tag
= create_memory_tag (tag_type
, true);
3472 set_symbol_mem_tag (ptr
, tag
);
3474 /* Add VAR to the may-alias set of PTR's new symbol tag. If VAR has
3475 subvars, add the subvars to the tag instead of the actual var. */
3476 if (var_can_have_subvars (ref
)
3477 && (svars
= get_subvars_for_var (ref
)))
3479 for (sv
= svars
; sv
; sv
= sv
->next
)
3483 if (overlap_subvar (offset
, maxsize
, sv
->var
, &exact
))
3484 VEC_safe_push (tree
, heap
, overlaps
, sv
->var
);
3486 gcc_assert (overlaps
!= NULL
);
3488 else if (var_can_have_subvars (var
)
3489 && (svars
= get_subvars_for_var (var
)))
3491 /* If the REF is not a direct access to VAR (e.g., it is a dereference
3492 of a pointer), we should scan the virtual operands of REF the same
3493 way as tree-ssa-operands do. At the moment, this is somewhat
3494 difficult, so we just give up and add all the subvars of VAR.
3495 On mem-ssa branch, the scanning for virtual operands have been
3496 split from the rest of tree-ssa-operands, so it should be much
3497 easier to fix this problem correctly once mem-ssa is merged. */
3498 for (sv
= svars
; sv
; sv
= sv
->next
)
3499 VEC_safe_push (tree
, heap
, overlaps
, sv
->var
);
3501 gcc_assert (overlaps
!= NULL
);
3504 ali
= add_may_alias_for_new_tag (tag
, var
);
3506 len
= VEC_length (tree
, overlaps
);
3509 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3510 fprintf (dump_file
, "\nnumber of overlapping subvars = %u\n", len
);
3513 ali
= add_may_alias_for_new_tag (tag
, VEC_index (tree
, overlaps
, 0));
3519 for (k
= 0; VEC_iterate (tree
, overlaps
, k
, sv_var
); k
++)
3521 ali
= add_may_alias_for_new_tag (tag
, sv_var
);
3525 /* Can happen only if 'Case 1' of add_may_alias_for_new_tag
3526 took place. Since more than one svar was found, we add
3527 'ali' as one of the may_aliases of the new tag. */
3528 add_may_alias (tag
, ali
);
3533 VEC_free (tree
, heap
, overlaps
);
3536 set_symbol_mem_tag (ptr
, ali
);
3537 TREE_READONLY (tag
) = TREE_READONLY (var
);
3538 MTAG_GLOBAL (tag
) = is_global_var (var
);
3541 /* This represents the used range of a variable. */
3543 typedef struct used_part
3545 HOST_WIDE_INT minused
;
3546 HOST_WIDE_INT maxused
;
3547 /* True if we have an explicit use/def of some portion of this variable,
3548 even if it is all of it. i.e. a.b = 5 or temp = a.b. */
3550 /* True if we have an implicit use/def of some portion of this
3551 variable. Implicit uses occur when we can't tell what part we
3552 are referencing, and have to make conservative assumptions. */
3554 /* True if the structure is only written to or taken its address. */
3558 /* An array of used_part structures, indexed by variable uid. */
3560 static htab_t used_portions
;
3562 struct used_part_map
3568 /* Return true if the uid in the two used part maps are equal. */
3571 used_part_map_eq (const void *va
, const void *vb
)
3573 const struct used_part_map
*a
= (const struct used_part_map
*) va
;
3574 const struct used_part_map
*b
= (const struct used_part_map
*) vb
;
3575 return (a
->uid
== b
->uid
);
3578 /* Hash a from uid in a used_part_map. */
3581 used_part_map_hash (const void *item
)
3583 return ((const struct used_part_map
*)item
)->uid
;
3586 /* Free a used part map element. */
3589 free_used_part_map (void *item
)
3591 free (((struct used_part_map
*)item
)->to
);
3595 /* Lookup a used_part structure for a UID. */
3598 up_lookup (unsigned int uid
)
3600 struct used_part_map
*h
, in
;
3602 h
= (struct used_part_map
*) htab_find_with_hash (used_portions
, &in
, uid
);
3608 /* Insert the pair UID, TO into the used part hashtable. */
3611 up_insert (unsigned int uid
, used_part_t to
)
3613 struct used_part_map
*h
;
3616 h
= XNEW (struct used_part_map
);
3619 loc
= htab_find_slot_with_hash (used_portions
, h
,
3623 *(struct used_part_map
**) loc
= h
;
3627 /* Given a variable uid, UID, get or create the entry in the used portions
3628 table for the variable. */
3631 get_or_create_used_part_for (size_t uid
)
3634 if ((up
= up_lookup (uid
)) == NULL
)
3636 up
= XCNEW (struct used_part
);
3637 up
->minused
= INT_MAX
;
3639 up
->explicit_uses
= false;
3640 up
->implicit_uses
= false;
3641 up
->write_only
= true;
3648 /* Create and return a structure sub-variable for field type FIELD at
3649 offset OFFSET, with size SIZE, of variable VAR. If ALIAS_SET not
3650 -1 this field is non-addressable and we should use this alias set
3654 create_sft (tree var
, tree field
, unsigned HOST_WIDE_INT offset
,
3655 unsigned HOST_WIDE_INT size
, HOST_WIDE_INT alias_set
)
3657 tree subvar
= create_tag_raw (STRUCT_FIELD_TAG
, field
, "SFT");
3659 /* We need to copy the various flags from VAR to SUBVAR, so that
3660 they are is_global_var iff the original variable was. */
3661 DECL_CONTEXT (subvar
) = DECL_CONTEXT (var
);
3662 MTAG_GLOBAL (subvar
) = DECL_EXTERNAL (var
);
3663 TREE_PUBLIC (subvar
) = TREE_PUBLIC (var
);
3664 TREE_STATIC (subvar
) = TREE_STATIC (var
);
3665 TREE_READONLY (subvar
) = TREE_READONLY (var
);
3666 TREE_ADDRESSABLE (subvar
) = TREE_ADDRESSABLE (var
);
3668 /* Add the new variable to REFERENCED_VARS. */
3669 set_symbol_mem_tag (subvar
, NULL
);
3670 add_referenced_var (subvar
);
3671 SFT_PARENT_VAR (subvar
) = var
;
3672 SFT_OFFSET (subvar
) = offset
;
3673 SFT_SIZE (subvar
) = size
;
3674 SFT_ALIAS_SET (subvar
) = alias_set
;
3679 /* Given an aggregate VAR, create the subvariables that represent its
3683 create_overlap_variables_for (tree var
)
3685 VEC(fieldoff_s
,heap
) *fieldstack
= NULL
;
3687 size_t uid
= DECL_UID (var
);
3689 up
= up_lookup (uid
);
3694 push_fields_onto_fieldstack (TREE_TYPE (var
), &fieldstack
, 0, NULL
,
3696 if (VEC_length (fieldoff_s
, fieldstack
) != 0)
3700 bool notokay
= false;
3703 HOST_WIDE_INT lastfooffset
= -1;
3704 HOST_WIDE_INT lastfosize
= -1;
3705 tree lastfotype
= NULL_TREE
;
3707 /* Not all fields have DECL_SIZE set, and those that don't, we don't
3708 know their size, and thus, can't handle.
3709 The same is true of fields with DECL_SIZE that is not an integer
3710 constant (such as variable sized fields).
3711 Fields with offsets which are not constant will have an offset < 0
3712 We *could* handle fields that are constant sized arrays, but
3713 currently don't. Doing so would require some extra changes to
3714 tree-ssa-operands.c. */
3716 for (i
= 0; VEC_iterate (fieldoff_s
, fieldstack
, i
, fo
); i
++)
3719 || TREE_CODE (fo
->size
) != INTEGER_CST
3728 /* The current heuristic we use is as follows:
3729 If the variable has no used portions in this function, no
3730 structure vars are created for it.
3732 If the variable has less than SALIAS_MAX_IMPLICIT_FIELDS,
3733 we always create structure vars for them.
3734 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3735 some explicit uses, we create structure vars for them.
3736 If the variable has more than SALIAS_MAX_IMPLICIT_FIELDS, and
3737 no explicit uses, we do not create structure vars for them.
3740 if (fieldcount
>= SALIAS_MAX_IMPLICIT_FIELDS
3741 && !up
->explicit_uses
)
3743 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3745 fprintf (dump_file
, "Variable ");
3746 print_generic_expr (dump_file
, var
, 0);
3747 fprintf (dump_file
, " has no explicit uses in this function, and is > SALIAS_MAX_IMPLICIT_FIELDS, so skipping\n");
3752 /* Bail out, if we can't create overlap variables. */
3755 VEC_free (fieldoff_s
, heap
, fieldstack
);
3759 /* Otherwise, create the variables. */
3760 subvars
= lookup_subvars_for_var (var
);
3762 sort_fieldstack (fieldstack
);
3764 for (i
= VEC_length (fieldoff_s
, fieldstack
);
3765 VEC_iterate (fieldoff_s
, fieldstack
, --i
, fo
);)
3768 HOST_WIDE_INT fosize
;
3771 fosize
= TREE_INT_CST_LOW (fo
->size
);
3772 currfotype
= fo
->type
;
3774 /* If this field isn't in the used portion,
3775 or it has the exact same offset and size as the last
3778 if (((fo
->offset
<= up
->minused
3779 && fo
->offset
+ fosize
<= up
->minused
)
3780 || fo
->offset
>= up
->maxused
)
3781 || (fo
->offset
== lastfooffset
3782 && fosize
== lastfosize
3783 && currfotype
== lastfotype
))
3785 sv
= GGC_NEW (struct subvar
);
3786 sv
->next
= *subvars
;
3788 create_sft (var
, fo
->type
, fo
->offset
, fosize
, fo
->alias_set
);
3792 fprintf (dump_file
, "structure field tag %s created for var %s",
3793 get_name (sv
->var
), get_name (var
));
3794 fprintf (dump_file
, " offset " HOST_WIDE_INT_PRINT_DEC
,
3795 SFT_OFFSET (sv
->var
));
3796 fprintf (dump_file
, " size " HOST_WIDE_INT_PRINT_DEC
,
3797 SFT_SIZE (sv
->var
));
3798 fprintf (dump_file
, "\n");
3801 lastfotype
= currfotype
;
3802 lastfooffset
= fo
->offset
;
3803 lastfosize
= fosize
;
3807 /* Once we have created subvars, the original is no longer call
3808 clobbered on its own. Its call clobbered status depends
3809 completely on the call clobbered status of the subvars.
3811 add_referenced_var in the above loop will take care of
3812 marking subvars of global variables as call clobbered for us
3813 to start, since they are global as well. */
3814 clear_call_clobbered (var
);
3817 VEC_free (fieldoff_s
, heap
, fieldstack
);
3821 /* Find the conservative answer to the question of what portions of what
3822 structures are used by this statement. We assume that if we have a
3823 component ref with a known size + offset, that we only need that part
3824 of the structure. For unknown cases, or cases where we do something
3825 to the whole structure, we assume we need to create fields for the
3826 entire structure. */
3829 find_used_portions (tree
*tp
, int *walk_subtrees
, void *lhs_p
)
3831 switch (TREE_CODE (*tp
))
3833 case GIMPLE_MODIFY_STMT
:
3834 /* Recurse manually here to track whether the use is in the
3835 LHS of an assignment. */
3836 find_used_portions (&GIMPLE_STMT_OPERAND (*tp
, 0), walk_subtrees
, tp
);
3837 return find_used_portions (&GIMPLE_STMT_OPERAND (*tp
, 1),
3838 walk_subtrees
, NULL
);
3844 HOST_WIDE_INT bitsize
;
3845 HOST_WIDE_INT bitmaxsize
;
3846 HOST_WIDE_INT bitpos
;
3848 ref
= get_ref_base_and_extent (*tp
, &bitpos
, &bitsize
, &bitmaxsize
);
3850 && var_can_have_subvars (ref
)
3851 && bitmaxsize
!= -1)
3853 size_t uid
= DECL_UID (ref
);
3856 up
= get_or_create_used_part_for (uid
);
3858 if (bitpos
<= up
->minused
)
3859 up
->minused
= bitpos
;
3860 if ((bitpos
+ bitmaxsize
>= up
->maxused
))
3861 up
->maxused
= bitpos
+ bitmaxsize
;
3863 if (bitsize
== bitmaxsize
)
3864 up
->explicit_uses
= true;
3866 up
->implicit_uses
= true;
3868 up
->write_only
= false;
3869 up_insert (uid
, up
);
3876 /* This is here to make sure we mark the entire base variable as used
3877 when you take its address. Because our used portion analysis is
3878 simple, we aren't looking at casts or pointer arithmetic to see what
3879 happens when you take the address. */
3882 tree var
= get_base_address (TREE_OPERAND (*tp
, 0));
3887 && var_can_have_subvars (var
)
3888 && TREE_CODE (DECL_SIZE (var
)) == INTEGER_CST
)
3891 size_t uid
= DECL_UID (var
);
3893 up
= get_or_create_used_part_for (uid
);
3896 up
->maxused
= TREE_INT_CST_LOW (DECL_SIZE (var
));
3897 up
->implicit_uses
= true;
3899 up
->write_only
= false;
3901 up_insert (uid
, up
);
3910 int nargs
= call_expr_nargs (*tp
);
3911 for (i
= 0; i
< nargs
; i
++)
3913 tree
*arg
= &CALL_EXPR_ARG (*tp
, i
);
3914 if (TREE_CODE (*arg
) != ADDR_EXPR
)
3915 find_used_portions (arg
, walk_subtrees
, NULL
);
3926 && var_can_have_subvars (var
)
3927 && TREE_CODE (DECL_SIZE (var
)) == INTEGER_CST
)
3930 size_t uid
= DECL_UID (var
);
3932 up
= get_or_create_used_part_for (uid
);
3935 up
->maxused
= TREE_INT_CST_LOW (DECL_SIZE (var
));
3936 up
->implicit_uses
= true;
3938 up_insert (uid
, up
);
3952 /* Create structure field variables for structures used in this function. */
3955 create_structure_vars (void)
3958 safe_referenced_var_iterator rvi
;
3959 VEC (tree
, heap
) *varvec
= NULL
;
3962 used_portions
= htab_create (10, used_part_map_hash
, used_part_map_eq
,
3963 free_used_part_map
);
3967 block_stmt_iterator bsi
;
3968 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3970 walk_tree_without_duplicates (bsi_stmt_ptr (bsi
),
3975 FOR_EACH_REFERENCED_VAR_SAFE (var
, varvec
, rvi
)
3977 /* The C++ FE creates vars without DECL_SIZE set, for some reason. */
3980 && var_can_have_subvars (var
)
3982 && TREE_CODE (DECL_SIZE (var
)) == INTEGER_CST
)
3983 create_overlap_variables_for (var
);
3985 htab_delete (used_portions
);
3986 VEC_free (tree
, heap
, varvec
);
3988 /* Update SSA operands of statements mentioning variables we split. */
3989 if (gimple_in_ssa_p (cfun
))
3992 block_stmt_iterator bsi
;
3993 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
3995 tree stmt
= bsi_stmt (bsi
);
3996 bool update
= false;
4000 if (STORED_SYMS (stmt
))
4001 EXECUTE_IF_SET_IN_BITMAP (STORED_SYMS (stmt
), 0, i
, bi
)
4003 tree sym
= referenced_var_lookup (i
);
4004 if (get_subvars_for_var (sym
))
4011 if (LOADED_SYMS (stmt
) && !update
)
4012 EXECUTE_IF_SET_IN_BITMAP (LOADED_SYMS (stmt
), 0, i
, bi
)
4014 tree sym
= referenced_var_lookup (i
);
4015 if (get_subvars_for_var (sym
))
4022 if (stmt_ann (stmt
)->addresses_taken
&& !update
)
4023 EXECUTE_IF_SET_IN_BITMAP (stmt_ann (stmt
)->addresses_taken
,
4026 tree sym
= referenced_var_lookup (i
);
4027 if (get_subvars_for_var (sym
))
4043 gate_structure_vars (void)
4045 return flag_tree_salias
!= 0;
4048 struct tree_opt_pass pass_create_structure_vars
=
4050 "salias", /* name */
4051 gate_structure_vars
, /* gate */
4052 create_structure_vars
, /* execute */
4055 0, /* static_pass_number */
4057 PROP_cfg
, /* properties_required */
4058 0, /* properties_provided */
4059 0, /* properties_destroyed */
4060 0, /* todo_flags_start */
4061 TODO_dump_func
, /* todo_flags_finish */
4065 /* Reset the call_clobbered flags on our referenced vars. In
4066 theory, this only needs to be done for globals. */
4069 reset_cc_flags (void)
4072 referenced_var_iterator rvi
;
4074 FOR_EACH_REFERENCED_VAR (var
, rvi
)
4075 var_ann (var
)->call_clobbered
= false;
4079 struct tree_opt_pass pass_reset_cc_flags
=
4083 reset_cc_flags
, /* execute */
4086 0, /* static_pass_number */
4088 PROP_referenced_vars
|PROP_cfg
, /* properties_required */
4089 0, /* properties_provided */
4090 0, /* properties_destroyed */
4091 0, /* todo_flags_start */
4092 0, /* todo_flags_finish */