1 /* Alias analysis for trees.
2 Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, 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"
46 /* 'true' after aliases have been computed (see compute_may_aliases). */
47 bool aliases_computed_p
;
49 /* Structure to map a variable to its alias set and keep track of the
50 virtual operands that will be needed to represent it. */
53 /* Variable and its alias set. */
57 /* Total number of virtual operands that will be needed to represent
58 all the aliases of VAR. */
59 long total_alias_vops
;
61 /* Nonzero if the aliases for this memory tag have been grouped
62 already. Used in group_aliases. */
63 unsigned int grouped_p
: 1;
65 /* Set of variables aliased with VAR. This is the exact same
66 information contained in VAR_ANN (VAR)->MAY_ALIASES, but in
67 bitmap form to speed up alias grouping. */
72 /* Alias information used by compute_may_aliases and its helpers. */
75 /* SSA names visited while collecting points-to information. If bit I
76 is set, it means that SSA variable with version I has already been
78 sbitmap ssa_names_visited
;
80 /* Array of SSA_NAME pointers processed by the points-to collector. */
81 varray_type processed_ptrs
;
83 /* Variables whose address is still needed. */
84 bitmap addresses_needed
;
86 /* ADDRESSABLE_VARS contains all the global variables and locals that
87 have had their address taken. */
88 struct alias_map_d
**addressable_vars
;
89 size_t num_addressable_vars
;
91 /* POINTERS contains all the _DECL pointers with unique memory tags
92 that have been referenced in the program. */
93 struct alias_map_d
**pointers
;
96 /* Number of function calls found in the program. */
97 size_t num_calls_found
;
99 /* Number of const/pure function calls found in the program. */
100 size_t num_pure_const_calls_found
;
102 /* Array of counters to keep track of how many times each pointer has
103 been dereferenced in the program. This is used by the alias grouping
104 heuristic in compute_flow_insensitive_aliasing. */
105 varray_type num_references
;
107 /* Total number of virtual operands that will be needed to represent
108 all the aliases of all the pointers found in the program. */
109 long total_alias_vops
;
111 /* Variables that have been written to. */
114 /* Pointers that have been used in an indirect store operation. */
115 bitmap dereferenced_ptrs_store
;
117 /* Pointers that have been used in an indirect load operation. */
118 bitmap dereferenced_ptrs_load
;
122 /* Counters used to display statistics on alias analysis. */
125 unsigned int alias_queries
;
126 unsigned int alias_mayalias
;
127 unsigned int alias_noalias
;
128 unsigned int simple_queries
;
129 unsigned int simple_resolved
;
130 unsigned int tbaa_queries
;
131 unsigned int tbaa_resolved
;
135 /* Local variables. */
136 static struct alias_stats_d alias_stats
;
138 /* Local functions. */
139 static void compute_flow_insensitive_aliasing (struct alias_info
*);
140 static void dump_alias_stats (FILE *);
141 static bool may_alias_p (tree
, HOST_WIDE_INT
, tree
, HOST_WIDE_INT
);
142 static tree
create_memory_tag (tree type
, bool is_type_tag
);
143 static tree
get_tmt_for (tree
, struct alias_info
*);
144 static tree
get_nmt_for (tree
);
145 static void add_may_alias (tree
, tree
);
146 static void replace_may_alias (tree
, size_t, tree
);
147 static struct alias_info
*init_alias_info (void);
148 static void delete_alias_info (struct alias_info
*);
149 static void compute_points_to_and_addr_escape (struct alias_info
*);
150 static void compute_flow_sensitive_aliasing (struct alias_info
*);
151 static void setup_pointers_and_addressables (struct alias_info
*);
152 static bool collect_points_to_info_r (tree
, tree
, void *);
153 static bool is_escape_site (tree
, struct alias_info
*);
154 static void add_pointed_to_var (struct alias_info
*, tree
, tree
);
155 static void create_global_var (void);
156 static void collect_points_to_info_for (struct alias_info
*, tree
);
157 static void maybe_create_global_var (struct alias_info
*ai
);
158 static void group_aliases (struct alias_info
*);
159 static void set_pt_anything (tree ptr
);
160 static void set_pt_malloc (tree ptr
);
162 /* Global declarations. */
164 /* Call clobbered variables in the function. If bit I is set, then
165 REFERENCED_VARS (I) is call-clobbered. */
166 bitmap call_clobbered_vars
;
168 /* Addressable variables in the function. If bit I is set, then
169 REFERENCED_VARS (I) has had its address taken. Note that
170 CALL_CLOBBERED_VARS and ADDRESSABLE_VARS are not related. An
171 addressable variable is not necessarily call-clobbered (e.g., a
172 local addressable whose address does not escape) and not all
173 call-clobbered variables are addressable (e.g., a local static
175 bitmap addressable_vars
;
177 /* When the program has too many call-clobbered variables and call-sites,
178 this variable is used to represent the clobbering effects of function
179 calls. In these cases, all the call clobbered variables in the program
180 are forced to alias this variable. This reduces compile times by not
181 having to keep track of too many V_MAY_DEF expressions at call sites. */
185 /* Compute may-alias information for every variable referenced in function
188 Alias analysis proceeds in 3 main phases:
190 1- Points-to and escape analysis.
192 This phase walks the use-def chains in the SSA web looking for three
195 * Assignments of the form P_i = &VAR
196 * Assignments of the form P_i = malloc()
197 * Pointers and ADDR_EXPR that escape the current function.
199 The concept of 'escaping' is the same one used in the Java world. When
200 a pointer or an ADDR_EXPR escapes, it means that it has been exposed
201 outside of the current function. So, assignment to global variables,
202 function arguments and returning a pointer are all escape sites, as are
203 conversions between pointers and integers.
205 This is where we are currently limited. Since not everything is renamed
206 into SSA, we lose track of escape properties when a pointer is stashed
207 inside a field in a structure, for instance. In those cases, we are
208 assuming that the pointer does escape.
210 We use escape analysis to determine whether a variable is
211 call-clobbered. Simply put, if an ADDR_EXPR escapes, then the variable
212 is call-clobbered. If a pointer P_i escapes, then all the variables
213 pointed-to by P_i (and its memory tag) also escape.
215 2- Compute flow-sensitive aliases
217 We have two classes of memory tags. Memory tags associated with the
218 pointed-to data type of the pointers in the program. These tags are
219 called "type memory tag" (TMT). The other class are those associated
220 with SSA_NAMEs, called "name memory tag" (NMT). The basic idea is that
221 when adding operands for an INDIRECT_REF *P_i, we will first check
222 whether P_i has a name tag, if it does we use it, because that will have
223 more precise aliasing information. Otherwise, we use the standard type
226 In this phase, we go through all the pointers we found in points-to
227 analysis and create alias sets for the name memory tags associated with
228 each pointer P_i. If P_i escapes, we mark call-clobbered the variables
229 it points to and its tag.
232 3- Compute flow-insensitive aliases
234 This pass will compare the alias set of every type memory tag and every
235 addressable variable found in the program. Given a type memory tag TMT
236 and an addressable variable V. If the alias sets of TMT and V conflict
237 (as computed by may_alias_p), then V is marked as an alias tag and added
238 to the alias set of TMT.
240 For instance, consider the following function:
256 After aliasing analysis has finished, the type memory tag for pointer
257 'p' will have two aliases, namely variables 'a' and 'b'. Every time
258 pointer 'p' is dereferenced, we want to mark the operation as a
259 potential reference to 'a' and 'b'.
269 # p_1 = PHI <p_4(1), p_6(2)>;
271 # a_7 = V_MAY_DEF <a_3>;
272 # b_8 = V_MAY_DEF <b_5>;
275 # a_9 = V_MAY_DEF <a_7>
284 In certain cases, the list of may aliases for a pointer may grow too
285 large. This may cause an explosion in the number of virtual operands
286 inserted in the code. Resulting in increased memory consumption and
289 When the number of virtual operands needed to represent aliased
290 loads and stores grows too large (configurable with @option{--param
291 max-aliased-vops}), alias sets are grouped to avoid severe
292 compile-time slow downs and memory consumption. See group_aliases. */
295 compute_may_aliases (void)
297 struct alias_info
*ai
;
299 memset (&alias_stats
, 0, sizeof (alias_stats
));
301 /* Initialize aliasing information. */
302 ai
= init_alias_info ();
304 /* For each pointer P_i, determine the sets of variables that P_i may
305 point-to. For every addressable variable V, determine whether the
306 address of V escapes the current function, making V call-clobbered
307 (i.e., whether &V is stored in a global variable or if its passed as a
308 function call argument). */
309 compute_points_to_and_addr_escape (ai
);
311 /* Collect all pointers and addressable variables, compute alias sets,
312 create memory tags for pointers and promote variables whose address is
313 not needed anymore. */
314 setup_pointers_and_addressables (ai
);
316 /* Compute flow-sensitive, points-to based aliasing for all the name
317 memory tags. Note that this pass needs to be done before flow
318 insensitive analysis because it uses the points-to information
319 gathered before to mark call-clobbered type tags. */
320 compute_flow_sensitive_aliasing (ai
);
322 /* Compute type-based flow-insensitive aliasing for all the type
324 compute_flow_insensitive_aliasing (ai
);
326 /* If the program has too many call-clobbered variables and/or function
327 calls, create .GLOBAL_VAR and use it to model call-clobbering
328 semantics at call sites. This reduces the number of virtual operands
329 considerably, improving compile times at the expense of lost
330 aliasing precision. */
331 maybe_create_global_var (ai
);
333 /* Debugging dumps. */
336 dump_referenced_vars (dump_file
);
337 if (dump_flags
& TDF_STATS
)
338 dump_alias_stats (dump_file
);
339 dump_points_to_info (dump_file
);
340 dump_alias_info (dump_file
);
343 /* Deallocate memory used by aliasing data structures. */
344 delete_alias_info (ai
);
347 struct tree_opt_pass pass_may_alias
=
351 compute_may_aliases
, /* execute */
354 0, /* static_pass_number */
355 TV_TREE_MAY_ALIAS
, /* tv_id */
356 PROP_cfg
| PROP_ssa
, /* properties_required */
357 PROP_alias
, /* properties_provided */
358 0, /* properties_destroyed */
359 0, /* todo_flags_start */
360 TODO_dump_func
| TODO_rename_vars
361 | TODO_ggc_collect
| TODO_verify_ssa
362 | TODO_verify_stmts
, /* todo_flags_finish */
367 /* Data structure used to count the number of dereferences to PTR
368 inside an expression. */
376 /* Helper for count_uses_and_derefs. Called by walk_tree to look for
377 (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA. */
380 count_ptr_derefs (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
, void *data
)
382 struct count_ptr_d
*count_p
= (struct count_ptr_d
*) data
;
384 if (INDIRECT_REF_P (*tp
) && TREE_OPERAND (*tp
, 0) == count_p
->ptr
)
391 /* Count the number of direct and indirect uses for pointer PTR in
392 statement STMT. The two counts are stored in *NUM_USES_P and
393 *NUM_DEREFS_P respectively. *IS_STORE_P is set to 'true' if at
394 least one of those dereferences is a store operation. */
397 count_uses_and_derefs (tree ptr
, tree stmt
, unsigned *num_uses_p
,
398 unsigned *num_derefs_p
, bool *is_store
)
407 /* Find out the total number of uses of PTR in STMT. */
408 FOR_EACH_SSA_TREE_OPERAND (use
, stmt
, i
, SSA_OP_USE
)
412 /* Now count the number of indirect references to PTR. This is
413 truly awful, but we don't have much choice. There are no parent
414 pointers inside INDIRECT_REFs, so an expression like
415 '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
416 find all the indirect and direct uses of x_1 inside. The only
417 shortcut we can take is the fact that GIMPLE only allows
418 INDIRECT_REFs inside the expressions below. */
419 if (TREE_CODE (stmt
) == MODIFY_EXPR
420 || (TREE_CODE (stmt
) == RETURN_EXPR
421 && TREE_CODE (TREE_OPERAND (stmt
, 0)) == MODIFY_EXPR
)
422 || TREE_CODE (stmt
) == ASM_EXPR
423 || TREE_CODE (stmt
) == CALL_EXPR
)
427 if (TREE_CODE (stmt
) == MODIFY_EXPR
)
429 lhs
= TREE_OPERAND (stmt
, 0);
430 rhs
= TREE_OPERAND (stmt
, 1);
432 else if (TREE_CODE (stmt
) == RETURN_EXPR
)
434 tree e
= TREE_OPERAND (stmt
, 0);
435 lhs
= TREE_OPERAND (e
, 0);
436 rhs
= TREE_OPERAND (e
, 1);
438 else if (TREE_CODE (stmt
) == ASM_EXPR
)
440 lhs
= ASM_OUTPUTS (stmt
);
441 rhs
= ASM_INPUTS (stmt
);
449 if (lhs
&& (TREE_CODE (lhs
) == TREE_LIST
|| EXPR_P (lhs
)))
451 struct count_ptr_d count
;
454 walk_tree (&lhs
, count_ptr_derefs
, &count
, NULL
);
456 *num_derefs_p
= count
.count
;
459 if (rhs
&& (TREE_CODE (rhs
) == TREE_LIST
|| EXPR_P (rhs
)))
461 struct count_ptr_d count
;
464 walk_tree (&rhs
, count_ptr_derefs
, &count
, NULL
);
465 *num_derefs_p
+= count
.count
;
469 gcc_assert (*num_uses_p
>= *num_derefs_p
);
473 /* Initialize the data structures used for alias analysis. */
475 static struct alias_info
*
476 init_alias_info (void)
478 struct alias_info
*ai
;
480 ai
= xcalloc (1, sizeof (struct alias_info
));
481 ai
->ssa_names_visited
= sbitmap_alloc (num_ssa_names
);
482 sbitmap_zero (ai
->ssa_names_visited
);
483 VARRAY_TREE_INIT (ai
->processed_ptrs
, 50, "processed_ptrs");
484 ai
->addresses_needed
= BITMAP_ALLOC (NULL
);
485 VARRAY_UINT_INIT (ai
->num_references
, num_referenced_vars
, "num_references");
486 ai
->written_vars
= BITMAP_ALLOC (NULL
);
487 ai
->dereferenced_ptrs_store
= BITMAP_ALLOC (NULL
);
488 ai
->dereferenced_ptrs_load
= BITMAP_ALLOC (NULL
);
490 /* If aliases have been computed before, clear existing information. */
491 if (aliases_computed_p
)
496 /* Make sure that every statement has a valid set of operands.
497 If a statement needs to be scanned for operands while we
498 compute aliases, it may get erroneous operands because all
499 the alias relations are not built at that point.
500 FIXME: This code will become obsolete when operands are not
504 block_stmt_iterator si
;
505 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
506 get_stmt_operands (bsi_stmt (si
));
509 /* Similarly, clear the set of addressable variables. In this
510 case, we can just clear the set because addressability is
511 only computed here. */
512 bitmap_clear (addressable_vars
);
514 /* Clear flow-insensitive alias information from each symbol. */
515 for (i
= 0; i
< num_referenced_vars
; i
++)
517 tree var
= referenced_var (i
);
518 var_ann_t ann
= var_ann (var
);
520 ann
->is_alias_tag
= 0;
521 ann
->may_aliases
= NULL
;
523 /* Since we are about to re-discover call-clobbered
524 variables, clear the call-clobbered flag. Variables that
525 are intrinsically call-clobbered (globals, local statics,
526 etc) will not be marked by the aliasing code, so we can't
527 remove them from CALL_CLOBBERED_VARS. */
528 if (ann
->mem_tag_kind
!= NOT_A_TAG
|| !is_global_var (var
))
529 clear_call_clobbered (var
);
532 /* Clear flow-sensitive points-to information from each SSA name. */
533 for (i
= 1; i
< num_ssa_names
; i
++)
535 tree name
= ssa_name (i
);
537 if (!name
|| !POINTER_TYPE_P (TREE_TYPE (name
)))
540 if (SSA_NAME_PTR_INFO (name
))
542 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (name
);
544 /* Clear all the flags but keep the name tag to
545 avoid creating new temporaries unnecessarily. If
546 this pointer is found to point to a subset or
547 superset of its former points-to set, then a new
548 tag will need to be created in create_name_tags. */
552 pi
->value_escapes_p
= 0;
553 pi
->is_dereferenced
= 0;
555 bitmap_clear (pi
->pt_vars
);
560 /* Next time, we will need to reset alias information. */
561 aliases_computed_p
= true;
567 /* Deallocate memory used by alias analysis. */
570 delete_alias_info (struct alias_info
*ai
)
574 sbitmap_free (ai
->ssa_names_visited
);
575 ai
->processed_ptrs
= NULL
;
576 BITMAP_FREE (ai
->addresses_needed
);
578 for (i
= 0; i
< ai
->num_addressable_vars
; i
++)
580 sbitmap_free (ai
->addressable_vars
[i
]->may_aliases
);
581 free (ai
->addressable_vars
[i
]);
583 free (ai
->addressable_vars
);
585 for (i
= 0; i
< ai
->num_pointers
; i
++)
587 sbitmap_free (ai
->pointers
[i
]->may_aliases
);
588 free (ai
->pointers
[i
]);
592 ai
->num_references
= NULL
;
593 BITMAP_FREE (ai
->written_vars
);
594 BITMAP_FREE (ai
->dereferenced_ptrs_store
);
595 BITMAP_FREE (ai
->dereferenced_ptrs_load
);
601 /* Walk use-def chains for pointer PTR to determine what variables is PTR
605 collect_points_to_info_for (struct alias_info
*ai
, tree ptr
)
607 gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr
)));
609 if (!TEST_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (ptr
)))
611 SET_BIT (ai
->ssa_names_visited
, SSA_NAME_VERSION (ptr
));
612 walk_use_def_chains (ptr
, collect_points_to_info_r
, ai
, true);
613 VARRAY_PUSH_TREE (ai
->processed_ptrs
, ptr
);
618 /* Traverse use-def links for all the pointers in the program to collect
619 address escape and points-to information.
621 This is loosely based on the same idea described in R. Hasti and S.
622 Horwitz, ``Using static single assignment form to improve
623 flow-insensitive pointer analysis,'' in SIGPLAN Conference on
624 Programming Language Design and Implementation, pp. 97-105, 1998. */
627 compute_points_to_and_addr_escape (struct alias_info
*ai
)
634 timevar_push (TV_TREE_PTA
);
638 bb_ann_t block_ann
= bb_ann (bb
);
639 block_stmt_iterator si
;
641 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
644 tree stmt
= bsi_stmt (si
);
645 bool stmt_escapes_p
= is_escape_site (stmt
, ai
);
648 /* Mark all the variables whose address are taken by the
649 statement. Note that this will miss all the addresses taken
650 in PHI nodes (those are discovered while following the use-def
652 get_stmt_operands (stmt
);
653 addr_taken
= addresses_taken (stmt
);
655 EXECUTE_IF_SET_IN_BITMAP (addr_taken
, 0, i
, bi
)
657 tree var
= referenced_var (i
);
658 bitmap_set_bit (ai
->addresses_needed
, var_ann (var
)->uid
);
660 mark_call_clobbered (var
);
664 block_ann
->has_escape_site
= 1;
666 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
668 var_ann_t v_ann
= var_ann (SSA_NAME_VAR (op
));
669 struct ptr_info_def
*pi
;
671 unsigned num_uses
, num_derefs
;
673 /* If the operand's variable may be aliased, keep track
674 of how many times we've referenced it. This is used
675 for alias grouping in compute_flow_sensitive_aliasing.
676 Note that we don't need to grow AI->NUM_REFERENCES
677 because we are processing regular variables, not
678 memory tags (the array's initial size is set to
679 NUM_REFERENCED_VARS). */
680 if (may_be_aliased (SSA_NAME_VAR (op
)))
681 (VARRAY_UINT (ai
->num_references
, v_ann
->uid
))++;
683 if (!POINTER_TYPE_P (TREE_TYPE (op
)))
686 collect_points_to_info_for (ai
, op
);
688 pi
= SSA_NAME_PTR_INFO (op
);
689 count_uses_and_derefs (op
, stmt
, &num_uses
, &num_derefs
,
694 /* Mark OP as dereferenced. In a subsequent pass,
695 dereferenced pointers that point to a set of
696 variables will be assigned a name tag to alias
697 all the variables OP points to. */
698 pi
->is_dereferenced
= 1;
700 /* Keep track of how many time we've dereferenced each
701 pointer. Again, we don't need to grow
702 AI->NUM_REFERENCES because we're processing
703 existing program variables. */
704 (VARRAY_UINT (ai
->num_references
, v_ann
->uid
))++;
706 /* If this is a store operation, mark OP as being
707 dereferenced to store, otherwise mark it as being
708 dereferenced to load. */
710 bitmap_set_bit (ai
->dereferenced_ptrs_store
, v_ann
->uid
);
712 bitmap_set_bit (ai
->dereferenced_ptrs_load
, v_ann
->uid
);
715 if (stmt_escapes_p
&& num_derefs
< num_uses
)
717 /* If STMT is an escape point and STMT contains at
718 least one direct use of OP, then the value of OP
719 escapes and so the pointed-to variables need to
720 be marked call-clobbered. */
721 pi
->value_escapes_p
= 1;
723 /* If the statement makes a function call, assume
724 that pointer OP will be dereferenced in a store
725 operation inside the called function. */
726 if (get_call_expr_in (stmt
))
728 bitmap_set_bit (ai
->dereferenced_ptrs_store
, v_ann
->uid
);
729 pi
->is_dereferenced
= 1;
734 /* Update reference counter for definitions to any
735 potentially aliased variable. This is used in the alias
736 grouping heuristics. */
737 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
739 tree var
= SSA_NAME_VAR (op
);
740 var_ann_t ann
= var_ann (var
);
741 bitmap_set_bit (ai
->written_vars
, ann
->uid
);
742 if (may_be_aliased (var
))
743 (VARRAY_UINT (ai
->num_references
, ann
->uid
))++;
745 if (POINTER_TYPE_P (TREE_TYPE (op
)))
746 collect_points_to_info_for (ai
, op
);
749 /* Mark variables in V_MAY_DEF operands as being written to. */
750 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
752 tree var
= SSA_NAME_VAR (op
);
753 var_ann_t ann
= var_ann (var
);
754 bitmap_set_bit (ai
->written_vars
, ann
->uid
);
757 /* After promoting variables and computing aliasing we will
758 need to re-scan most statements. FIXME: Try to minimize the
759 number of statements re-scanned. It's not really necessary to
760 re-scan *all* statements. */
765 timevar_pop (TV_TREE_PTA
);
769 /* Create name tags for all the pointers that have been dereferenced.
770 We only create a name tag for a pointer P if P is found to point to
771 a set of variables (so that we can alias them to *P) or if it is
772 the result of a call to malloc (which means that P cannot point to
773 anything else nor alias any other variable).
775 If two pointers P and Q point to the same set of variables, they
776 are assigned the same name tag. */
779 create_name_tags (struct alias_info
*ai
)
783 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ai
->processed_ptrs
); i
++)
785 tree ptr
= VARRAY_TREE (ai
->processed_ptrs
, i
);
786 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
788 if (pi
->pt_anything
|| !pi
->is_dereferenced
)
790 /* No name tags for pointers that have not been
791 dereferenced or point to an arbitrary location. */
792 pi
->name_mem_tag
= NULL_TREE
;
796 if (pi
->pt_vars
&& !bitmap_empty_p (pi
->pt_vars
))
799 tree old_name_tag
= pi
->name_mem_tag
;
801 /* If PTR points to a set of variables, check if we don't
802 have another pointer Q with the same points-to set before
803 creating a tag. If so, use Q's tag instead of creating a
806 This is important for not creating unnecessary symbols
807 and also for copy propagation. If we ever need to
808 propagate PTR into Q or vice-versa, we would run into
809 problems if they both had different name tags because
810 they would have different SSA version numbers (which
811 would force us to take the name tags in and out of SSA). */
812 for (j
= 0; j
< i
; j
++)
814 tree q
= VARRAY_TREE (ai
->processed_ptrs
, j
);
815 struct ptr_info_def
*qi
= SSA_NAME_PTR_INFO (q
);
820 && bitmap_equal_p (pi
->pt_vars
, qi
->pt_vars
))
822 pi
->name_mem_tag
= qi
->name_mem_tag
;
827 /* If we didn't find a pointer with the same points-to set
828 as PTR, create a new name tag if needed. */
829 if (pi
->name_mem_tag
== NULL_TREE
)
830 pi
->name_mem_tag
= get_nmt_for (ptr
);
832 /* If the new name tag computed for PTR is different than
833 the old name tag that it used to have, then the old tag
834 needs to be removed from the IL, so we mark it for
836 if (old_name_tag
&& old_name_tag
!= pi
->name_mem_tag
)
837 bitmap_set_bit (vars_to_rename
, var_ann (old_name_tag
)->uid
);
839 else if (pi
->pt_malloc
)
841 /* Otherwise, create a unique name tag for this pointer. */
842 pi
->name_mem_tag
= get_nmt_for (ptr
);
846 /* Only pointers that may point to malloc or other variables
847 may receive a name tag. If the pointer does not point to
848 a known spot, we should use type tags. */
849 set_pt_anything (ptr
);
853 TREE_THIS_VOLATILE (pi
->name_mem_tag
)
854 |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr
)));
856 /* Mark the new name tag for renaming. */
857 bitmap_set_bit (vars_to_rename
, var_ann (pi
->name_mem_tag
)->uid
);
863 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
864 the name memory tag (NMT) associated with P_i. If P_i escapes, then its
865 name tag and the variables it points-to are call-clobbered. Finally, if
866 P_i escapes and we could not determine where it points to, then all the
867 variables in the same alias set as *P_i are marked call-clobbered. This
868 is necessary because we must assume that P_i may take the address of any
869 variable in the same alias set. */
872 compute_flow_sensitive_aliasing (struct alias_info
*ai
)
876 create_name_tags (ai
);
878 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ai
->processed_ptrs
); i
++)
881 tree ptr
= VARRAY_TREE (ai
->processed_ptrs
, i
);
882 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
883 var_ann_t v_ann
= var_ann (SSA_NAME_VAR (ptr
));
886 if (pi
->value_escapes_p
|| pi
->pt_anything
)
888 /* If PTR escapes or may point to anything, then its associated
889 memory tags and pointed-to variables are call-clobbered. */
890 if (pi
->name_mem_tag
)
891 mark_call_clobbered (pi
->name_mem_tag
);
893 if (v_ann
->type_mem_tag
)
894 mark_call_clobbered (v_ann
->type_mem_tag
);
897 EXECUTE_IF_SET_IN_BITMAP (pi
->pt_vars
, 0, j
, bi
)
899 mark_call_clobbered (referenced_var (j
));
903 /* Set up aliasing information for PTR's name memory tag (if it has
904 one). Note that only pointers that have been dereferenced will
905 have a name memory tag. */
906 if (pi
->name_mem_tag
&& pi
->pt_vars
)
907 EXECUTE_IF_SET_IN_BITMAP (pi
->pt_vars
, 0, j
, bi
)
909 add_may_alias (pi
->name_mem_tag
, referenced_var (j
));
910 add_may_alias (v_ann
->type_mem_tag
, referenced_var (j
));
913 /* If the name tag is call clobbered, so is the type tag
914 associated with the base VAR_DECL. */
916 && v_ann
->type_mem_tag
917 && is_call_clobbered (pi
->name_mem_tag
))
918 mark_call_clobbered (v_ann
->type_mem_tag
);
923 /* Compute type-based alias sets. Traverse all the pointers and
924 addressable variables found in setup_pointers_and_addressables.
926 For every pointer P in AI->POINTERS and addressable variable V in
927 AI->ADDRESSABLE_VARS, add V to the may-alias sets of P's type
928 memory tag (TMT) if their alias sets conflict. V is then marked as
929 an alias tag so that the operand scanner knows that statements
930 containing V have aliased operands. */
933 compute_flow_insensitive_aliasing (struct alias_info
*ai
)
937 /* Initialize counter for the total number of virtual operands that
938 aliasing will introduce. When AI->TOTAL_ALIAS_VOPS goes beyond the
939 threshold set by --params max-alias-vops, we enable alias
941 ai
->total_alias_vops
= 0;
943 /* For every pointer P, determine which addressable variables may alias
944 with P's type memory tag. */
945 for (i
= 0; i
< ai
->num_pointers
; i
++)
948 struct alias_map_d
*p_map
= ai
->pointers
[i
];
949 tree tag
= var_ann (p_map
->var
)->type_mem_tag
;
950 var_ann_t tag_ann
= var_ann (tag
);
952 p_map
->total_alias_vops
= 0;
953 p_map
->may_aliases
= sbitmap_alloc (num_referenced_vars
);
954 sbitmap_zero (p_map
->may_aliases
);
956 for (j
= 0; j
< ai
->num_addressable_vars
; j
++)
958 struct alias_map_d
*v_map
;
961 bool tag_stored_p
, var_stored_p
;
963 v_map
= ai
->addressable_vars
[j
];
965 v_ann
= var_ann (var
);
967 /* Skip memory tags and variables that have never been
968 written to. We also need to check if the variables are
969 call-clobbered because they may be overwritten by
972 Note this is effectively random accessing elements in
973 the sparse bitset, which can be highly inefficient.
974 So we first check the call_clobbered status of the
975 tag and variable before querying the bitmap. */
976 tag_stored_p
= is_call_clobbered (tag
)
977 || bitmap_bit_p (ai
->written_vars
, tag_ann
->uid
);
978 var_stored_p
= is_call_clobbered (var
)
979 || bitmap_bit_p (ai
->written_vars
, v_ann
->uid
);
980 if (!tag_stored_p
&& !var_stored_p
)
983 if (may_alias_p (p_map
->var
, p_map
->set
, var
, v_map
->set
))
985 size_t num_tag_refs
, num_var_refs
;
987 num_tag_refs
= VARRAY_UINT (ai
->num_references
, tag_ann
->uid
);
988 num_var_refs
= VARRAY_UINT (ai
->num_references
, v_ann
->uid
);
990 /* Add VAR to TAG's may-aliases set. */
991 add_may_alias (tag
, var
);
993 /* Update the total number of virtual operands due to
994 aliasing. Since we are adding one more alias to TAG's
995 may-aliases set, the total number of virtual operands due
996 to aliasing will be increased by the number of references
997 made to VAR and TAG (every reference to TAG will also
998 count as a reference to VAR). */
999 ai
->total_alias_vops
+= (num_var_refs
+ num_tag_refs
);
1000 p_map
->total_alias_vops
+= (num_var_refs
+ num_tag_refs
);
1002 /* Update the bitmap used to represent TAG's alias set
1003 in case we need to group aliases. */
1004 SET_BIT (p_map
->may_aliases
, var_ann (var
)->uid
);
1009 /* Since this analysis is based exclusively on symbols, it fails to
1010 handle cases where two pointers P and Q have different memory
1011 tags with conflicting alias set numbers but no aliased symbols in
1014 For example, suppose that we have two memory tags TMT.1 and TMT.2
1017 may-aliases (TMT.1) = { a }
1018 may-aliases (TMT.2) = { b }
1020 and the alias set number of TMT.1 conflicts with that of TMT.2.
1021 Since they don't have symbols in common, loads and stores from
1022 TMT.1 and TMT.2 will seem independent of each other, which will
1023 lead to the optimizers making invalid transformations (see
1024 testsuite/gcc.c-torture/execute/pr15262-[12].c).
1026 To avoid this problem, we do a final traversal of AI->POINTERS
1027 looking for pairs of pointers that have no aliased symbols in
1028 common and yet have conflicting alias set numbers. */
1029 for (i
= 0; i
< ai
->num_pointers
; i
++)
1032 struct alias_map_d
*p_map1
= ai
->pointers
[i
];
1033 tree tag1
= var_ann (p_map1
->var
)->type_mem_tag
;
1034 sbitmap may_aliases1
= p_map1
->may_aliases
;
1036 for (j
= i
+ 1; j
< ai
->num_pointers
; j
++)
1038 struct alias_map_d
*p_map2
= ai
->pointers
[j
];
1039 tree tag2
= var_ann (p_map2
->var
)->type_mem_tag
;
1040 sbitmap may_aliases2
= p_map2
->may_aliases
;
1042 /* If the pointers may not point to each other, do nothing. */
1043 if (!may_alias_p (p_map1
->var
, p_map1
->set
, p_map2
->var
, p_map2
->set
))
1046 /* The two pointers may alias each other. If they already have
1047 symbols in common, do nothing. */
1048 if (sbitmap_any_common_bits (may_aliases1
, may_aliases2
))
1051 if (sbitmap_first_set_bit (may_aliases2
) >= 0)
1055 /* Add all the aliases for TAG2 into TAG1's alias set.
1056 FIXME, update grouping heuristic counters. */
1057 EXECUTE_IF_SET_IN_SBITMAP (may_aliases2
, 0, k
,
1058 add_may_alias (tag1
, referenced_var (k
)));
1059 sbitmap_a_or_b (may_aliases1
, may_aliases1
, may_aliases2
);
1063 /* Since TAG2 does not have any aliases of its own, add
1064 TAG2 itself to the alias set of TAG1. */
1065 add_may_alias (tag1
, tag2
);
1066 SET_BIT (may_aliases1
, var_ann (tag2
)->uid
);
1072 fprintf (dump_file
, "%s: Total number of aliased vops: %ld\n",
1073 get_name (current_function_decl
),
1074 ai
->total_alias_vops
);
1076 /* Determine if we need to enable alias grouping. */
1077 if (ai
->total_alias_vops
>= MAX_ALIASED_VOPS
)
1082 /* Comparison function for qsort used in group_aliases. */
1085 total_alias_vops_cmp (const void *p
, const void *q
)
1087 const struct alias_map_d
**p1
= (const struct alias_map_d
**)p
;
1088 const struct alias_map_d
**p2
= (const struct alias_map_d
**)q
;
1089 long n1
= (*p1
)->total_alias_vops
;
1090 long n2
= (*p2
)->total_alias_vops
;
1092 /* We want to sort in descending order. */
1093 return (n1
> n2
? -1 : (n1
== n2
) ? 0 : 1);
1096 /* Group all the aliases for TAG to make TAG represent all the
1097 variables in its alias set. Update the total number
1098 of virtual operands due to aliasing (AI->TOTAL_ALIAS_VOPS). This
1099 function will make TAG be the unique alias tag for all the
1100 variables in its may-aliases. So, given:
1102 may-aliases(TAG) = { V1, V2, V3 }
1104 This function will group the variables into:
1106 may-aliases(V1) = { TAG }
1107 may-aliases(V2) = { TAG }
1108 may-aliases(V2) = { TAG } */
1111 group_aliases_into (tree tag
, sbitmap tag_aliases
, struct alias_info
*ai
)
1114 var_ann_t tag_ann
= var_ann (tag
);
1115 size_t num_tag_refs
= VARRAY_UINT (ai
->num_references
, tag_ann
->uid
);
1117 EXECUTE_IF_SET_IN_SBITMAP (tag_aliases
, 0, i
,
1119 tree var
= referenced_var (i
);
1120 var_ann_t ann
= var_ann (var
);
1122 /* Make TAG the unique alias of VAR. */
1123 ann
->is_alias_tag
= 0;
1124 ann
->may_aliases
= NULL
;
1126 /* Note that VAR and TAG may be the same if the function has no
1127 addressable variables (see the discussion at the end of
1128 setup_pointers_and_addressables). */
1130 add_may_alias (var
, tag
);
1132 /* Reduce total number of virtual operands contributed
1133 by TAG on behalf of VAR. Notice that the references to VAR
1134 itself won't be removed. We will merely replace them with
1135 references to TAG. */
1136 ai
->total_alias_vops
-= num_tag_refs
;
1139 /* We have reduced the number of virtual operands that TAG makes on
1140 behalf of all the variables formerly aliased with it. However,
1141 we have also "removed" all the virtual operands for TAG itself,
1142 so we add them back. */
1143 ai
->total_alias_vops
+= num_tag_refs
;
1145 /* TAG no longer has any aliases. */
1146 tag_ann
->may_aliases
= NULL
;
1150 /* Group may-aliases sets to reduce the number of virtual operands due
1153 1- Sort the list of pointers in decreasing number of contributed
1156 2- Take the first entry in AI->POINTERS and revert the role of
1157 the memory tag and its aliases. Usually, whenever an aliased
1158 variable Vi is found to alias with a memory tag T, we add Vi
1159 to the may-aliases set for T. Meaning that after alias
1160 analysis, we will have:
1162 may-aliases(T) = { V1, V2, V3, ..., Vn }
1164 This means that every statement that references T, will get 'n'
1165 virtual operands for each of the Vi tags. But, when alias
1166 grouping is enabled, we make T an alias tag and add it to the
1167 alias set of all the Vi variables:
1169 may-aliases(V1) = { T }
1170 may-aliases(V2) = { T }
1172 may-aliases(Vn) = { T }
1174 This has two effects: (a) statements referencing T will only get
1175 a single virtual operand, and, (b) all the variables Vi will now
1176 appear to alias each other. So, we lose alias precision to
1177 improve compile time. But, in theory, a program with such a high
1178 level of aliasing should not be very optimizable in the first
1181 3- Since variables may be in the alias set of more than one
1182 memory tag, the grouping done in step (2) needs to be extended
1183 to all the memory tags that have a non-empty intersection with
1184 the may-aliases set of tag T. For instance, if we originally
1185 had these may-aliases sets:
1187 may-aliases(T) = { V1, V2, V3 }
1188 may-aliases(R) = { V2, V4 }
1190 In step (2) we would have reverted the aliases for T as:
1192 may-aliases(V1) = { T }
1193 may-aliases(V2) = { T }
1194 may-aliases(V3) = { T }
1196 But note that now V2 is no longer aliased with R. We could
1197 add R to may-aliases(V2), but we are in the process of
1198 grouping aliases to reduce virtual operands so what we do is
1199 add V4 to the grouping to obtain:
1201 may-aliases(V1) = { T }
1202 may-aliases(V2) = { T }
1203 may-aliases(V3) = { T }
1204 may-aliases(V4) = { T }
1206 4- If the total number of virtual operands due to aliasing is
1207 still above the threshold set by max-alias-vops, go back to (2). */
1210 group_aliases (struct alias_info
*ai
)
1214 /* Sort the POINTERS array in descending order of contributed
1215 virtual operands. */
1216 qsort (ai
->pointers
, ai
->num_pointers
, sizeof (struct alias_map_d
*),
1217 total_alias_vops_cmp
);
1219 /* For every pointer in AI->POINTERS, reverse the roles of its tag
1220 and the tag's may-aliases set. */
1221 for (i
= 0; i
< ai
->num_pointers
; i
++)
1224 tree tag1
= var_ann (ai
->pointers
[i
]->var
)->type_mem_tag
;
1225 sbitmap tag1_aliases
= ai
->pointers
[i
]->may_aliases
;
1227 /* Skip tags that have been grouped already. */
1228 if (ai
->pointers
[i
]->grouped_p
)
1231 /* See if TAG1 had any aliases in common with other type tags.
1232 If we find a TAG2 with common aliases with TAG1, add TAG2's
1233 aliases into TAG1. */
1234 for (j
= i
+ 1; j
< ai
->num_pointers
; j
++)
1236 sbitmap tag2_aliases
= ai
->pointers
[j
]->may_aliases
;
1238 if (sbitmap_any_common_bits (tag1_aliases
, tag2_aliases
))
1240 tree tag2
= var_ann (ai
->pointers
[j
]->var
)->type_mem_tag
;
1242 sbitmap_a_or_b (tag1_aliases
, tag1_aliases
, tag2_aliases
);
1244 /* TAG2 does not need its aliases anymore. */
1245 sbitmap_zero (tag2_aliases
);
1246 var_ann (tag2
)->may_aliases
= NULL
;
1248 /* TAG1 is the unique alias of TAG2. */
1249 add_may_alias (tag2
, tag1
);
1251 ai
->pointers
[j
]->grouped_p
= true;
1255 /* Now group all the aliases we collected into TAG1. */
1256 group_aliases_into (tag1
, tag1_aliases
, ai
);
1258 /* If we've reduced total number of virtual operands below the
1260 if (ai
->total_alias_vops
< MAX_ALIASED_VOPS
)
1264 /* Finally, all the variables that have been grouped cannot be in
1265 the may-alias set of name memory tags. Suppose that we have
1266 grouped the aliases in this code so that may-aliases(a) = TMT.20
1270 # a_9 = V_MAY_DEF <a_8>
1272 ... Several modifications to TMT.20 ...
1276 Since p_5 points to 'a', the optimizers will try to propagate 0
1277 into p_5->field, but that is wrong because there have been
1278 modifications to 'TMT.20' in between. To prevent this we have to
1279 replace 'a' with 'TMT.20' in the name tag of p_5. */
1280 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ai
->processed_ptrs
); i
++)
1283 tree ptr
= VARRAY_TREE (ai
->processed_ptrs
, i
);
1284 tree name_tag
= SSA_NAME_PTR_INFO (ptr
)->name_mem_tag
;
1285 varray_type aliases
;
1287 if (name_tag
== NULL_TREE
)
1290 aliases
= var_ann (name_tag
)->may_aliases
;
1291 for (j
= 0; aliases
&& j
< VARRAY_ACTIVE_SIZE (aliases
); j
++)
1293 tree alias
= VARRAY_TREE (aliases
, j
);
1294 var_ann_t ann
= var_ann (alias
);
1296 if (ann
->mem_tag_kind
== NOT_A_TAG
&& ann
->may_aliases
)
1300 gcc_assert (VARRAY_ACTIVE_SIZE (ann
->may_aliases
) == 1);
1302 new_alias
= VARRAY_TREE (ann
->may_aliases
, 0);
1303 replace_may_alias (name_tag
, j
, new_alias
);
1310 "%s: Total number of aliased vops after grouping: %ld%s\n",
1311 get_name (current_function_decl
),
1312 ai
->total_alias_vops
,
1313 (ai
->total_alias_vops
< 0) ? " (negative values are OK)" : "");
1317 /* Create a new alias set entry for VAR in AI->ADDRESSABLE_VARS. */
1320 create_alias_map_for (tree var
, struct alias_info
*ai
)
1322 struct alias_map_d
*alias_map
;
1323 alias_map
= xcalloc (1, sizeof (*alias_map
));
1324 alias_map
->var
= var
;
1325 alias_map
->set
= get_alias_set (var
);
1326 ai
->addressable_vars
[ai
->num_addressable_vars
++] = alias_map
;
1330 /* Create memory tags for all the dereferenced pointers and build the
1331 ADDRESSABLE_VARS and POINTERS arrays used for building the may-alias
1332 sets. Based on the address escape and points-to information collected
1333 earlier, this pass will also clear the TREE_ADDRESSABLE flag from those
1334 variables whose address is not needed anymore. */
1337 setup_pointers_and_addressables (struct alias_info
*ai
)
1339 size_t i
, n_vars
, num_addressable_vars
, num_pointers
;
1341 /* Size up the arrays ADDRESSABLE_VARS and POINTERS. */
1342 num_addressable_vars
= num_pointers
= 0;
1343 for (i
= 0; i
< num_referenced_vars
; i
++)
1345 tree var
= referenced_var (i
);
1347 if (may_be_aliased (var
))
1348 num_addressable_vars
++;
1350 if (POINTER_TYPE_P (TREE_TYPE (var
)))
1352 /* Since we don't keep track of volatile variables, assume that
1353 these pointers are used in indirect store operations. */
1354 if (TREE_THIS_VOLATILE (var
))
1355 bitmap_set_bit (ai
->dereferenced_ptrs_store
, var_ann (var
)->uid
);
1361 /* Create ADDRESSABLE_VARS and POINTERS. Note that these arrays are
1362 always going to be slightly bigger than we actually need them
1363 because some TREE_ADDRESSABLE variables will be marked
1364 non-addressable below and only pointers with unique type tags are
1365 going to be added to POINTERS. */
1366 ai
->addressable_vars
= xcalloc (num_addressable_vars
,
1367 sizeof (struct alias_map_d
*));
1368 ai
->pointers
= xcalloc (num_pointers
, sizeof (struct alias_map_d
*));
1369 ai
->num_addressable_vars
= 0;
1370 ai
->num_pointers
= 0;
1372 /* Since we will be creating type memory tags within this loop, cache the
1373 value of NUM_REFERENCED_VARS to avoid processing the additional tags
1375 n_vars
= num_referenced_vars
;
1377 for (i
= 0; i
< n_vars
; i
++)
1379 tree var
= referenced_var (i
);
1380 var_ann_t v_ann
= var_ann (var
);
1382 /* Name memory tags already have flow-sensitive aliasing
1383 information, so they need not be processed by
1384 compute_flow_insensitive_aliasing. Similarly, type memory
1385 tags are already accounted for when we process their
1386 associated pointer. */
1387 if (v_ann
->mem_tag_kind
!= NOT_A_TAG
)
1390 /* Remove the ADDRESSABLE flag from every addressable variable whose
1391 address is not needed anymore. This is caused by the propagation
1392 of ADDR_EXPR constants into INDIRECT_REF expressions and the
1393 removal of dead pointer assignments done by the early scalar
1395 if (TREE_ADDRESSABLE (var
))
1397 if (!bitmap_bit_p (ai
->addresses_needed
, v_ann
->uid
)
1398 && TREE_CODE (var
) != RESULT_DECL
1399 && !is_global_var (var
))
1401 /* The address of VAR is not needed, remove the
1402 addressable bit, so that it can be optimized as a
1403 regular variable. */
1404 mark_non_addressable (var
);
1406 /* Since VAR is now a regular GIMPLE register, we will need
1407 to rename VAR into SSA afterwards. */
1408 bitmap_set_bit (vars_to_rename
, v_ann
->uid
);
1412 /* Add the variable to the set of addressables. Mostly
1413 used when scanning operands for ASM_EXPRs that
1414 clobber memory. In those cases, we need to clobber
1415 all call-clobbered variables and all addressables. */
1416 bitmap_set_bit (addressable_vars
, v_ann
->uid
);
1420 /* Global variables and addressable locals may be aliased. Create an
1421 entry in ADDRESSABLE_VARS for VAR. */
1422 if (may_be_aliased (var
))
1424 create_alias_map_for (var
, ai
);
1425 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1428 /* Add pointer variables that have been dereferenced to the POINTERS
1429 array and create a type memory tag for them. */
1430 if (POINTER_TYPE_P (TREE_TYPE (var
)))
1432 if ((bitmap_bit_p (ai
->dereferenced_ptrs_store
, v_ann
->uid
)
1433 || bitmap_bit_p (ai
->dereferenced_ptrs_load
, v_ann
->uid
)))
1438 /* If pointer VAR still doesn't have a memory tag
1439 associated with it, create it now or re-use an
1441 tag
= get_tmt_for (var
, ai
);
1442 t_ann
= var_ann (tag
);
1444 /* The type tag will need to be renamed into SSA
1445 afterwards. Note that we cannot do this inside
1446 get_tmt_for because aliasing may run multiple times
1447 and we only create type tags the first time. */
1448 bitmap_set_bit (vars_to_rename
, t_ann
->uid
);
1450 /* Associate the tag with pointer VAR. */
1451 v_ann
->type_mem_tag
= tag
;
1453 /* If pointer VAR has been used in a store operation,
1454 then its memory tag must be marked as written-to. */
1455 if (bitmap_bit_p (ai
->dereferenced_ptrs_store
, v_ann
->uid
))
1456 bitmap_set_bit (ai
->written_vars
, t_ann
->uid
);
1458 /* If pointer VAR is a global variable or a PARM_DECL,
1459 then its memory tag should be considered a global
1461 if (TREE_CODE (var
) == PARM_DECL
|| is_global_var (var
))
1462 mark_call_clobbered (tag
);
1464 /* All the dereferences of pointer VAR count as
1465 references of TAG. Since TAG can be associated with
1466 several pointers, add the dereferences of VAR to the
1467 TAG. We may need to grow AI->NUM_REFERENCES because
1468 we have been adding name and type tags. */
1469 if (t_ann
->uid
>= VARRAY_SIZE (ai
->num_references
))
1470 VARRAY_GROW (ai
->num_references
, t_ann
->uid
+ 10);
1472 VARRAY_UINT (ai
->num_references
, t_ann
->uid
)
1473 += VARRAY_UINT (ai
->num_references
, v_ann
->uid
);
1477 /* The pointer has not been dereferenced. If it had a
1478 type memory tag, remove it and mark the old tag for
1479 renaming to remove it out of the IL. */
1480 var_ann_t ann
= var_ann (var
);
1481 tree tag
= ann
->type_mem_tag
;
1484 bitmap_set_bit (vars_to_rename
, var_ann (tag
)->uid
);
1485 ann
->type_mem_tag
= NULL_TREE
;
1493 /* Determine whether to use .GLOBAL_VAR to model call clobbering semantics. At
1494 every call site, we need to emit V_MAY_DEF expressions to represent the
1495 clobbering effects of the call for variables whose address escapes the
1498 One approach is to group all call-clobbered variables into a single
1499 representative that is used as an alias of every call-clobbered variable
1500 (.GLOBAL_VAR). This works well, but it ties the optimizer hands because
1501 references to any call clobbered variable is a reference to .GLOBAL_VAR.
1503 The second approach is to emit a clobbering V_MAY_DEF for every
1504 call-clobbered variable at call sites. This is the preferred way in terms
1505 of optimization opportunities but it may create too many V_MAY_DEF operands
1506 if there are many call clobbered variables and function calls in the
1509 To decide whether or not to use .GLOBAL_VAR we multiply the number of
1510 function calls found by the number of call-clobbered variables. If that
1511 product is beyond a certain threshold, as determined by the parameterized
1512 values shown below, we use .GLOBAL_VAR.
1514 FIXME. This heuristic should be improved. One idea is to use several
1515 .GLOBAL_VARs of different types instead of a single one. The thresholds
1516 have been derived from a typical bootstrap cycle, including all target
1517 libraries. Compile times were found increase by ~1% compared to using
1521 maybe_create_global_var (struct alias_info
*ai
)
1523 unsigned i
, n_clobbered
;
1526 /* No need to create it, if we have one already. */
1527 if (global_var
== NULL_TREE
)
1529 /* Count all the call-clobbered variables. */
1531 EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars
, 0, i
, bi
)
1536 /* If the number of virtual operands that would be needed to
1537 model all the call-clobbered variables is larger than
1538 GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR.
1540 Also create .GLOBAL_VAR if there are no call-clobbered
1541 variables and the program contains a mixture of pure/const
1542 and regular function calls. This is to avoid the problem
1543 described in PR 20115:
1546 int func_pure (void) { return X; }
1547 int func_non_pure (int a) { X += a; }
1550 int a = func_pure ();
1556 Since foo() has no call-clobbered variables, there is
1557 no relationship between the calls to func_pure and
1558 func_non_pure. Since func_pure has no side-effects, value
1559 numbering optimizations elide the second call to func_pure.
1560 So, if we have some pure/const and some regular calls in the
1561 program we create .GLOBAL_VAR to avoid missing these
1563 if (ai
->num_calls_found
* n_clobbered
>= (size_t) GLOBAL_VAR_THRESHOLD
1564 || (n_clobbered
== 0
1565 && ai
->num_calls_found
> 0
1566 && ai
->num_pure_const_calls_found
> 0
1567 && ai
->num_calls_found
> ai
->num_pure_const_calls_found
))
1568 create_global_var ();
1571 /* Mark all call-clobbered symbols for renaming. Since the initial
1572 rewrite into SSA ignored all call sites, we may need to rename
1573 .GLOBAL_VAR and the call-clobbered variables. */
1574 EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars
, 0, i
, bi
)
1576 tree var
= referenced_var (i
);
1578 /* If the function has calls to clobbering functions and
1579 .GLOBAL_VAR has been created, make it an alias for all
1580 call-clobbered variables. */
1581 if (global_var
&& var
!= global_var
)
1582 add_may_alias (var
, global_var
);
1584 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1589 /* Return TRUE if pointer PTR may point to variable VAR.
1591 MEM_ALIAS_SET is the alias set for the memory location pointed-to by PTR
1592 This is needed because when checking for type conflicts we are
1593 interested in the alias set of the memory location pointed-to by
1594 PTR. The alias set of PTR itself is irrelevant.
1596 VAR_ALIAS_SET is the alias set for VAR. */
1599 may_alias_p (tree ptr
, HOST_WIDE_INT mem_alias_set
,
1600 tree var
, HOST_WIDE_INT var_alias_set
)
1605 alias_stats
.alias_queries
++;
1606 alias_stats
.simple_queries
++;
1608 /* By convention, a variable cannot alias itself. */
1609 mem
= var_ann (ptr
)->type_mem_tag
;
1612 alias_stats
.alias_noalias
++;
1613 alias_stats
.simple_resolved
++;
1617 m_ann
= var_ann (mem
);
1619 gcc_assert (m_ann
->mem_tag_kind
== TYPE_TAG
);
1621 alias_stats
.tbaa_queries
++;
1623 /* If VAR is a pointer with the same alias set as PTR, then dereferencing
1624 PTR can't possibly affect VAR. Note, that we are specifically testing
1625 for PTR's alias set here, not its pointed-to type. We also can't
1626 do this check with relaxed aliasing enabled. */
1627 if (POINTER_TYPE_P (TREE_TYPE (var
))
1628 && var_alias_set
!= 0
1629 && mem_alias_set
!= 0)
1631 HOST_WIDE_INT ptr_alias_set
= get_alias_set (ptr
);
1632 if (ptr_alias_set
== var_alias_set
)
1634 alias_stats
.alias_noalias
++;
1635 alias_stats
.tbaa_resolved
++;
1640 /* If the alias sets don't conflict then MEM cannot alias VAR. */
1641 if (!alias_sets_conflict_p (mem_alias_set
, var_alias_set
))
1643 alias_stats
.alias_noalias
++;
1644 alias_stats
.tbaa_resolved
++;
1648 alias_stats
.alias_mayalias
++;
1653 /* Add ALIAS to the set of variables that may alias VAR. */
1656 add_may_alias (tree var
, tree alias
)
1659 var_ann_t v_ann
= get_var_ann (var
);
1660 var_ann_t a_ann
= get_var_ann (alias
);
1662 gcc_assert (var
!= alias
);
1664 if (v_ann
->may_aliases
== NULL
)
1665 VARRAY_TREE_INIT (v_ann
->may_aliases
, 2, "aliases");
1667 /* Avoid adding duplicates. */
1668 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (v_ann
->may_aliases
); i
++)
1669 if (alias
== VARRAY_TREE (v_ann
->may_aliases
, i
))
1672 /* If VAR is a call-clobbered variable, so is its new ALIAS.
1673 FIXME, call-clobbering should only depend on whether an address
1674 escapes. It should be independent of aliasing. */
1675 if (is_call_clobbered (var
))
1676 mark_call_clobbered (alias
);
1678 /* Likewise. If ALIAS is call-clobbered, so is VAR. */
1679 else if (is_call_clobbered (alias
))
1680 mark_call_clobbered (var
);
1682 VARRAY_PUSH_TREE (v_ann
->may_aliases
, alias
);
1683 a_ann
->is_alias_tag
= 1;
1687 /* Replace alias I in the alias sets of VAR with NEW_ALIAS. */
1690 replace_may_alias (tree var
, size_t i
, tree new_alias
)
1692 var_ann_t v_ann
= var_ann (var
);
1693 VARRAY_TREE (v_ann
->may_aliases
, i
) = new_alias
;
1695 /* If VAR is a call-clobbered variable, so is NEW_ALIAS.
1696 FIXME, call-clobbering should only depend on whether an address
1697 escapes. It should be independent of aliasing. */
1698 if (is_call_clobbered (var
))
1699 mark_call_clobbered (new_alias
);
1701 /* Likewise. If NEW_ALIAS is call-clobbered, so is VAR. */
1702 else if (is_call_clobbered (new_alias
))
1703 mark_call_clobbered (var
);
1707 /* Mark pointer PTR as pointing to an arbitrary memory location. */
1710 set_pt_anything (tree ptr
)
1712 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
1714 pi
->pt_anything
= 1;
1717 /* The pointer used to have a name tag, but we now found it pointing
1718 to an arbitrary location. The name tag needs to be renamed and
1719 disassociated from PTR. */
1720 if (pi
->name_mem_tag
)
1722 bitmap_set_bit (vars_to_rename
, var_ann (pi
->name_mem_tag
)->uid
);
1723 pi
->name_mem_tag
= NULL_TREE
;
1728 /* Mark pointer PTR as pointing to a malloc'd memory area. */
1731 set_pt_malloc (tree ptr
)
1733 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
1735 /* If the pointer has already been found to point to arbitrary
1736 memory locations, it is unsafe to mark it as pointing to malloc. */
1737 if (pi
->pt_anything
)
1744 /* Given two different pointers DEST and ORIG. Merge the points-to
1745 information in ORIG into DEST. AI contains all the alias
1746 information collected up to this point. */
1749 merge_pointed_to_info (struct alias_info
*ai
, tree dest
, tree orig
)
1751 struct ptr_info_def
*dest_pi
, *orig_pi
;
1753 gcc_assert (dest
!= orig
);
1755 /* Make sure we have points-to information for ORIG. */
1756 collect_points_to_info_for (ai
, orig
);
1758 dest_pi
= get_ptr_info (dest
);
1759 orig_pi
= SSA_NAME_PTR_INFO (orig
);
1763 gcc_assert (orig_pi
!= dest_pi
);
1765 /* Notice that we never merge PT_MALLOC. This attribute is only
1766 true if the pointer is the result of a malloc() call.
1767 Otherwise, we can end up in this situation:
1773 P_j would be marked as PT_MALLOC, however we currently do not
1774 handle cases of more than one pointer pointing to the same
1777 FIXME: If the merging comes from an expression that preserves
1778 the PT_MALLOC attribute (copy assignment, address
1779 arithmetic), we ought to merge PT_MALLOC, but then both
1780 pointers would end up getting different name tags because
1781 create_name_tags is not smart enough to determine that the
1782 two come from the same malloc call. Copy propagation before
1783 aliasing should cure this. */
1784 dest_pi
->pt_malloc
= 0;
1785 if (orig_pi
->pt_malloc
|| orig_pi
->pt_anything
)
1786 set_pt_anything (dest
);
1788 dest_pi
->pt_null
|= orig_pi
->pt_null
;
1790 if (!dest_pi
->pt_anything
1792 && !bitmap_empty_p (orig_pi
->pt_vars
))
1794 if (dest_pi
->pt_vars
== NULL
)
1796 dest_pi
->pt_vars
= BITMAP_GGC_ALLOC ();
1797 bitmap_copy (dest_pi
->pt_vars
, orig_pi
->pt_vars
);
1800 bitmap_ior_into (dest_pi
->pt_vars
, orig_pi
->pt_vars
);
1804 set_pt_anything (dest
);
1808 /* Add EXPR to the list of expressions pointed-to by PTR. */
1811 add_pointed_to_expr (struct alias_info
*ai
, tree ptr
, tree expr
)
1813 if (TREE_CODE (expr
) == WITH_SIZE_EXPR
)
1814 expr
= TREE_OPERAND (expr
, 0);
1818 if (TREE_CODE (expr
) == CALL_EXPR
1819 && (call_expr_flags (expr
) & (ECF_MALLOC
| ECF_MAY_BE_ALLOCA
)))
1821 /* If EXPR is a malloc-like call, then the area pointed to PTR
1822 is guaranteed to not alias with anything else. */
1823 set_pt_malloc (ptr
);
1825 else if (TREE_CODE (expr
) == ADDR_EXPR
)
1827 /* Found P_i = ADDR_EXPR */
1828 add_pointed_to_var (ai
, ptr
, expr
);
1830 else if (TREE_CODE (expr
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (expr
)))
1832 /* Found P_i = Q_j. */
1833 merge_pointed_to_info (ai
, ptr
, expr
);
1835 else if (TREE_CODE (expr
) == PLUS_EXPR
|| TREE_CODE (expr
) == MINUS_EXPR
)
1837 /* Found P_i = PLUS_EXPR or P_i = MINUS_EXPR */
1838 tree op0
= TREE_OPERAND (expr
, 0);
1839 tree op1
= TREE_OPERAND (expr
, 1);
1841 /* Both operands may be of pointer type. FIXME: Shouldn't
1842 we just expect PTR + OFFSET always? */
1843 if (POINTER_TYPE_P (TREE_TYPE (op0
))
1844 && TREE_CODE (op0
) != INTEGER_CST
)
1846 if (TREE_CODE (op0
) == SSA_NAME
)
1847 merge_pointed_to_info (ai
, ptr
, op0
);
1848 else if (TREE_CODE (op0
) == ADDR_EXPR
)
1849 add_pointed_to_var (ai
, ptr
, op0
);
1851 set_pt_anything (ptr
);
1854 if (POINTER_TYPE_P (TREE_TYPE (op1
))
1855 && TREE_CODE (op1
) != INTEGER_CST
)
1857 if (TREE_CODE (op1
) == SSA_NAME
)
1858 merge_pointed_to_info (ai
, ptr
, op1
);
1859 else if (TREE_CODE (op1
) == ADDR_EXPR
)
1860 add_pointed_to_var (ai
, ptr
, op1
);
1862 set_pt_anything (ptr
);
1865 /* Neither operand is a pointer? VAR can be pointing anywhere.
1866 FIXME: Shouldn't we abort here? If we get here, we found
1867 PTR = INT_CST + INT_CST, which should not be a valid pointer
1869 if (!(POINTER_TYPE_P (TREE_TYPE (op0
))
1870 && TREE_CODE (op0
) != INTEGER_CST
)
1871 && !(POINTER_TYPE_P (TREE_TYPE (op1
))
1872 && TREE_CODE (op1
) != INTEGER_CST
))
1873 set_pt_anything (ptr
);
1875 else if (integer_zerop (expr
))
1877 /* EXPR is the NULL pointer. Mark PTR as pointing to NULL. */
1878 SSA_NAME_PTR_INFO (ptr
)->pt_null
= 1;
1882 /* If we can't recognize the expression, assume that PTR may
1884 set_pt_anything (ptr
);
1889 /* If VALUE is of the form &DECL, add DECL to the set of variables
1890 pointed-to by PTR. Otherwise, add VALUE as a pointed-to expression by
1891 PTR. AI points to the collected alias information. */
1894 add_pointed_to_var (struct alias_info
*ai
, tree ptr
, tree value
)
1896 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
1900 gcc_assert (TREE_CODE (value
) == ADDR_EXPR
);
1902 pt_var
= TREE_OPERAND (value
, 0);
1903 if (REFERENCE_CLASS_P (pt_var
))
1904 pt_var
= get_base_address (pt_var
);
1906 if (pt_var
&& SSA_VAR_P (pt_var
))
1908 uid
= var_ann (pt_var
)->uid
;
1909 bitmap_set_bit (ai
->addresses_needed
, uid
);
1911 if (pi
->pt_vars
== NULL
)
1912 pi
->pt_vars
= BITMAP_GGC_ALLOC ();
1913 bitmap_set_bit (pi
->pt_vars
, uid
);
1915 /* If the variable is a global, mark the pointer as pointing to
1916 global memory (which will make its tag a global variable). */
1917 if (is_global_var (pt_var
))
1918 pi
->pt_global_mem
= 1;
1923 /* Callback for walk_use_def_chains to gather points-to information from the
1926 VAR is an SSA variable or a GIMPLE expression.
1928 STMT is the statement that generates the SSA variable or, if STMT is a
1929 PHI_NODE, VAR is one of the PHI arguments.
1931 DATA is a pointer to a structure of type ALIAS_INFO. */
1934 collect_points_to_info_r (tree var
, tree stmt
, void *data
)
1936 struct alias_info
*ai
= (struct alias_info
*) data
;
1938 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1940 fprintf (dump_file
, "Visiting use-def links for ");
1941 print_generic_expr (dump_file
, var
, dump_flags
);
1942 fprintf (dump_file
, "\n");
1945 switch (TREE_CODE (stmt
))
1948 if (TREE_CODE (TREE_OPERAND (stmt
, 0)) != MODIFY_EXPR
)
1950 stmt
= TREE_OPERAND (stmt
, 0);
1955 tree rhs
= TREE_OPERAND (stmt
, 1);
1957 add_pointed_to_expr (ai
, var
, rhs
);
1962 /* Pointers defined by __asm__ statements can point anywhere. */
1963 set_pt_anything (var
);
1967 if (IS_EMPTY_STMT (stmt
))
1969 tree decl
= SSA_NAME_VAR (var
);
1971 if (TREE_CODE (decl
) == PARM_DECL
)
1972 add_pointed_to_expr (ai
, var
, decl
);
1973 else if (DECL_INITIAL (decl
))
1974 add_pointed_to_expr (ai
, var
, DECL_INITIAL (decl
));
1976 add_pointed_to_expr (ai
, var
, decl
);
1982 /* It STMT is a PHI node, then VAR is one of its arguments. The
1983 variable that we are analyzing is the LHS of the PHI node. */
1984 tree lhs
= PHI_RESULT (stmt
);
1986 switch (TREE_CODE (var
))
1989 add_pointed_to_var (ai
, lhs
, var
);
1993 /* Avoid unnecessary merges. */
1995 merge_pointed_to_info (ai
, lhs
, var
);
1999 gcc_assert (is_gimple_min_invariant (var
));
2000 add_pointed_to_expr (ai
, lhs
, var
);
2014 /* Return true if STMT is an "escape" site from the current function. Escape
2015 sites those statements which might expose the address of a variable
2016 outside the current function. STMT is an escape site iff:
2018 1- STMT is a function call, or
2019 2- STMT is an __asm__ expression, or
2020 3- STMT is an assignment to a non-local variable, or
2021 4- STMT is a return statement.
2023 AI points to the alias information collected so far. */
2026 is_escape_site (tree stmt
, struct alias_info
*ai
)
2028 tree call
= get_call_expr_in (stmt
);
2029 if (call
!= NULL_TREE
)
2031 ai
->num_calls_found
++;
2033 if (!TREE_SIDE_EFFECTS (call
))
2034 ai
->num_pure_const_calls_found
++;
2038 else if (TREE_CODE (stmt
) == ASM_EXPR
)
2040 else if (TREE_CODE (stmt
) == MODIFY_EXPR
)
2042 tree lhs
= TREE_OPERAND (stmt
, 0);
2044 /* Get to the base of _REF nodes. */
2045 if (TREE_CODE (lhs
) != SSA_NAME
)
2046 lhs
= get_base_address (lhs
);
2048 /* If we couldn't recognize the LHS of the assignment, assume that it
2049 is a non-local store. */
2050 if (lhs
== NULL_TREE
)
2053 /* If the RHS is a conversion between a pointer and an integer, the
2054 pointer escapes since we can't track the integer. */
2055 if ((TREE_CODE (TREE_OPERAND (stmt
, 1)) == NOP_EXPR
2056 || TREE_CODE (TREE_OPERAND (stmt
, 1)) == CONVERT_EXPR
2057 || TREE_CODE (TREE_OPERAND (stmt
, 1)) == VIEW_CONVERT_EXPR
)
2058 && POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND
2059 (TREE_OPERAND (stmt
, 1), 0)))
2060 && !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt
, 1))))
2063 /* If the LHS is an SSA name, it can't possibly represent a non-local
2065 if (TREE_CODE (lhs
) == SSA_NAME
)
2068 /* FIXME: LHS is not an SSA_NAME. Even if it's an assignment to a
2069 local variables we cannot be sure if it will escape, because we
2070 don't have information about objects not in SSA form. Need to
2071 implement something along the lines of
2073 J.-D. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P.
2074 Midkiff, ``Escape analysis for java,'' in Proceedings of the
2075 Conference on Object-Oriented Programming Systems, Languages, and
2076 Applications (OOPSLA), pp. 1-19, 1999. */
2079 else if (TREE_CODE (stmt
) == RETURN_EXPR
)
2086 /* Create a new memory tag of type TYPE. If IS_TYPE_TAG is true, the tag
2087 is considered to represent all the pointers whose pointed-to types are
2088 in the same alias set class. Otherwise, the tag represents a single
2089 SSA_NAME pointer variable. */
2092 create_memory_tag (tree type
, bool is_type_tag
)
2095 tree tag
= create_tmp_var_raw (type
, (is_type_tag
) ? "TMT" : "NMT");
2097 /* By default, memory tags are local variables. Alias analysis will
2098 determine whether they should be considered globals. */
2099 DECL_CONTEXT (tag
) = current_function_decl
;
2101 /* Memory tags are by definition addressable. This also prevents
2102 is_gimple_ref frome confusing memory tags with optimizable
2104 TREE_ADDRESSABLE (tag
) = 1;
2106 ann
= get_var_ann (tag
);
2107 ann
->mem_tag_kind
= (is_type_tag
) ? TYPE_TAG
: NAME_TAG
;
2108 ann
->type_mem_tag
= NULL_TREE
;
2110 /* Add the tag to the symbol table. */
2111 add_referenced_tmp_var (tag
);
2117 /* Create a name memory tag to represent a specific SSA_NAME pointer P_i.
2118 This is used if P_i has been found to point to a specific set of
2119 variables or to a non-aliased memory location like the address returned
2120 by malloc functions. */
2123 get_nmt_for (tree ptr
)
2125 struct ptr_info_def
*pi
= get_ptr_info (ptr
);
2126 tree tag
= pi
->name_mem_tag
;
2128 if (tag
== NULL_TREE
)
2129 tag
= create_memory_tag (TREE_TYPE (TREE_TYPE (ptr
)), false);
2131 /* If PTR is a PARM_DECL, it points to a global variable or malloc,
2132 then its name tag should be considered a global variable. */
2133 if (TREE_CODE (SSA_NAME_VAR (ptr
)) == PARM_DECL
2135 || pi
->pt_global_mem
)
2136 mark_call_clobbered (tag
);
2142 /* Return the type memory tag associated to pointer PTR. A memory tag is an
2143 artificial variable that represents the memory location pointed-to by
2144 PTR. It is used to model the effects of pointer de-references on
2145 addressable variables.
2147 AI points to the data gathered during alias analysis. This function
2148 populates the array AI->POINTERS. */
2151 get_tmt_for (tree ptr
, struct alias_info
*ai
)
2155 tree tag_type
= TREE_TYPE (TREE_TYPE (ptr
));
2156 HOST_WIDE_INT tag_set
= get_alias_set (tag_type
);
2158 /* To avoid creating unnecessary memory tags, only create one memory tag
2159 per alias set class. Note that it may be tempting to group
2160 memory tags based on conflicting alias sets instead of
2161 equivalence. That would be wrong because alias sets are not
2162 necessarily transitive (as demonstrated by the libstdc++ test
2163 23_containers/vector/cons/4.cc). Given three alias sets A, B, C
2164 such that conflicts (A, B) == true and conflicts (A, C) == true,
2165 it does not necessarily follow that conflicts (B, C) == true. */
2166 for (i
= 0, tag
= NULL_TREE
; i
< ai
->num_pointers
; i
++)
2168 struct alias_map_d
*curr
= ai
->pointers
[i
];
2169 if (tag_set
== curr
->set
)
2171 tag
= var_ann (curr
->var
)->type_mem_tag
;
2176 /* If VAR cannot alias with any of the existing memory tags, create a new
2177 tag for PTR and add it to the POINTERS array. */
2178 if (tag
== NULL_TREE
)
2180 struct alias_map_d
*alias_map
;
2182 /* If PTR did not have a type tag already, create a new TMT.*
2183 artificial variable representing the memory location
2184 pointed-to by PTR. */
2185 if (var_ann (ptr
)->type_mem_tag
== NULL_TREE
)
2186 tag
= create_memory_tag (tag_type
, true);
2188 tag
= var_ann (ptr
)->type_mem_tag
;
2190 /* Add PTR to the POINTERS array. Note that we are not interested in
2191 PTR's alias set. Instead, we cache the alias set for the memory that
2193 alias_map
= xcalloc (1, sizeof (*alias_map
));
2194 alias_map
->var
= ptr
;
2195 alias_map
->set
= tag_set
;
2196 ai
->pointers
[ai
->num_pointers
++] = alias_map
;
2199 /* If the pointed-to type is volatile, so is the tag. */
2200 TREE_THIS_VOLATILE (tag
) |= TREE_THIS_VOLATILE (tag_type
);
2202 /* Make sure that the type tag has the same alias set as the
2204 gcc_assert (tag_set
== get_alias_set (tag
));
2210 /* Create GLOBAL_VAR, an artificial global variable to act as a
2211 representative of all the variables that may be clobbered by function
2215 create_global_var (void)
2217 global_var
= build_decl (VAR_DECL
, get_identifier (".GLOBAL_VAR"),
2219 DECL_ARTIFICIAL (global_var
) = 1;
2220 TREE_READONLY (global_var
) = 0;
2221 DECL_EXTERNAL (global_var
) = 1;
2222 TREE_STATIC (global_var
) = 1;
2223 TREE_USED (global_var
) = 1;
2224 DECL_CONTEXT (global_var
) = NULL_TREE
;
2225 TREE_THIS_VOLATILE (global_var
) = 0;
2226 TREE_ADDRESSABLE (global_var
) = 0;
2228 add_referenced_tmp_var (global_var
);
2229 bitmap_set_bit (vars_to_rename
, var_ann (global_var
)->uid
);
2233 /* Dump alias statistics on FILE. */
2236 dump_alias_stats (FILE *file
)
2238 const char *funcname
2239 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2240 fprintf (file
, "\nAlias statistics for %s\n\n", funcname
);
2241 fprintf (file
, "Total alias queries:\t%u\n", alias_stats
.alias_queries
);
2242 fprintf (file
, "Total alias mayalias results:\t%u\n",
2243 alias_stats
.alias_mayalias
);
2244 fprintf (file
, "Total alias noalias results:\t%u\n",
2245 alias_stats
.alias_noalias
);
2246 fprintf (file
, "Total simple queries:\t%u\n",
2247 alias_stats
.simple_queries
);
2248 fprintf (file
, "Total simple resolved:\t%u\n",
2249 alias_stats
.simple_resolved
);
2250 fprintf (file
, "Total TBAA queries:\t%u\n",
2251 alias_stats
.tbaa_queries
);
2252 fprintf (file
, "Total TBAA resolved:\t%u\n",
2253 alias_stats
.tbaa_resolved
);
2257 /* Dump alias information on FILE. */
2260 dump_alias_info (FILE *file
)
2263 const char *funcname
2264 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
2266 fprintf (file
, "\nFlow-insensitive alias information for %s\n\n", funcname
);
2268 fprintf (file
, "Aliased symbols\n\n");
2269 for (i
= 0; i
< num_referenced_vars
; i
++)
2271 tree var
= referenced_var (i
);
2272 if (may_be_aliased (var
))
2273 dump_variable (file
, var
);
2276 fprintf (file
, "\nDereferenced pointers\n\n");
2277 for (i
= 0; i
< num_referenced_vars
; i
++)
2279 tree var
= referenced_var (i
);
2280 var_ann_t ann
= var_ann (var
);
2281 if (ann
->type_mem_tag
)
2282 dump_variable (file
, var
);
2285 fprintf (file
, "\nType memory tags\n\n");
2286 for (i
= 0; i
< num_referenced_vars
; i
++)
2288 tree var
= referenced_var (i
);
2289 var_ann_t ann
= var_ann (var
);
2290 if (ann
->mem_tag_kind
== TYPE_TAG
)
2291 dump_variable (file
, var
);
2294 fprintf (file
, "\n\nFlow-sensitive alias information for %s\n\n", funcname
);
2296 fprintf (file
, "SSA_NAME pointers\n\n");
2297 for (i
= 1; i
< num_ssa_names
; i
++)
2299 tree ptr
= ssa_name (i
);
2300 struct ptr_info_def
*pi
;
2302 if (ptr
== NULL_TREE
)
2305 pi
= SSA_NAME_PTR_INFO (ptr
);
2306 if (!SSA_NAME_IN_FREE_LIST (ptr
)
2308 && pi
->name_mem_tag
)
2309 dump_points_to_info_for (file
, ptr
);
2312 fprintf (file
, "\nName memory tags\n\n");
2313 for (i
= 0; i
< num_referenced_vars
; i
++)
2315 tree var
= referenced_var (i
);
2316 var_ann_t ann
= var_ann (var
);
2317 if (ann
->mem_tag_kind
== NAME_TAG
)
2318 dump_variable (file
, var
);
2321 fprintf (file
, "\n");
2325 /* Dump alias information on stderr. */
2328 debug_alias_info (void)
2330 dump_alias_info (stderr
);
2334 /* Return the alias information associated with pointer T. It creates a
2335 new instance if none existed. */
2337 struct ptr_info_def
*
2338 get_ptr_info (tree t
)
2340 struct ptr_info_def
*pi
;
2342 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t
)));
2344 pi
= SSA_NAME_PTR_INFO (t
);
2347 pi
= ggc_alloc (sizeof (*pi
));
2348 memset ((void *)pi
, 0, sizeof (*pi
));
2349 SSA_NAME_PTR_INFO (t
) = pi
;
2356 /* Dump points-to information for SSA_NAME PTR into FILE. */
2359 dump_points_to_info_for (FILE *file
, tree ptr
)
2361 struct ptr_info_def
*pi
= SSA_NAME_PTR_INFO (ptr
);
2363 print_generic_expr (file
, ptr
, dump_flags
);
2367 if (pi
->name_mem_tag
)
2369 fprintf (file
, ", name memory tag: ");
2370 print_generic_expr (file
, pi
->name_mem_tag
, dump_flags
);
2373 if (pi
->is_dereferenced
)
2374 fprintf (file
, ", is dereferenced");
2376 if (pi
->value_escapes_p
)
2377 fprintf (file
, ", its value escapes");
2379 if (pi
->pt_anything
)
2380 fprintf (file
, ", points-to anything");
2383 fprintf (file
, ", points-to malloc");
2386 fprintf (file
, ", points-to NULL");
2393 fprintf (file
, ", points-to vars: { ");
2394 EXECUTE_IF_SET_IN_BITMAP (pi
->pt_vars
, 0, ix
, bi
)
2396 print_generic_expr (file
, referenced_var (ix
), dump_flags
);
2397 fprintf (file
, " ");
2399 fprintf (file
, "}");
2403 fprintf (file
, "\n");
2407 /* Dump points-to information for VAR into stderr. */
2410 debug_points_to_info_for (tree var
)
2412 dump_points_to_info_for (stderr
, var
);
2416 /* Dump points-to information into FILE. NOTE: This function is slow, as
2417 it needs to traverse the whole CFG looking for pointer SSA_NAMEs. */
2420 dump_points_to_info (FILE *file
)
2423 block_stmt_iterator si
;
2427 lang_hooks
.decl_printable_name (current_function_decl
, 2);
2429 fprintf (file
, "\n\nPointed-to sets for pointers in %s\n\n", fname
);
2431 /* First dump points-to information for the default definitions of
2432 pointer variables. This is necessary because default definitions are
2433 not part of the code. */
2434 for (i
= 0; i
< num_referenced_vars
; i
++)
2436 tree var
= referenced_var (i
);
2437 if (POINTER_TYPE_P (TREE_TYPE (var
)))
2439 var_ann_t ann
= var_ann (var
);
2440 if (ann
->default_def
)
2441 dump_points_to_info_for (file
, ann
->default_def
);
2445 /* Dump points-to information for every pointer defined in the program. */
2450 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
2452 tree ptr
= PHI_RESULT (phi
);
2453 if (POINTER_TYPE_P (TREE_TYPE (ptr
)))
2454 dump_points_to_info_for (file
, ptr
);
2457 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
2459 tree stmt
= bsi_stmt (si
);
2461 FOR_EACH_SSA_TREE_OPERAND (def
, stmt
, iter
, SSA_OP_DEF
)
2462 if (POINTER_TYPE_P (TREE_TYPE (def
)))
2463 dump_points_to_info_for (file
, def
);
2467 fprintf (file
, "\n");
2471 /* Dump points-to info pointed by PTO into STDERR. */
2474 debug_points_to_info (void)
2476 dump_points_to_info (stderr
);
2479 /* Dump to FILE the list of variables that may be aliasing VAR. */
2482 dump_may_aliases_for (FILE *file
, tree var
)
2484 varray_type aliases
;
2486 if (TREE_CODE (var
) == SSA_NAME
)
2487 var
= SSA_NAME_VAR (var
);
2489 aliases
= var_ann (var
)->may_aliases
;
2493 fprintf (file
, "{ ");
2494 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (aliases
); i
++)
2496 print_generic_expr (file
, VARRAY_TREE (aliases
, i
), dump_flags
);
2497 fprintf (file
, " ");
2499 fprintf (file
, "}");
2504 /* Dump to stderr the list of variables that may be aliasing VAR. */
2507 debug_may_aliases_for (tree var
)
2509 dump_may_aliases_for (stderr
, var
);
2512 /* Return true if VAR may be aliased. */
2515 may_be_aliased (tree var
)
2518 if (TREE_ADDRESSABLE (var
))
2521 /* Globally visible variables can have their addresses taken by other
2522 translation units. */
2523 if (DECL_EXTERNAL (var
) || TREE_PUBLIC (var
))
2526 /* Automatic variables can't have their addresses escape any other way.
2527 This must be after the check for global variables, as extern declarations
2528 do not have TREE_STATIC set. */
2529 if (!TREE_STATIC (var
))
2532 /* If we're in unit-at-a-time mode, then we must have seen all occurrences
2533 of address-of operators, and so we can trust TREE_ADDRESSABLE. Otherwise
2534 we can only be sure the variable isn't addressable if it's local to the
2535 current function. */
2536 if (flag_unit_at_a_time
)
2538 if (decl_function_context (var
) == current_function_decl
)