[stage 2 projects] Enable new points-to solver
Diego Novillo
dnovillo@redhat.com
Fri Jul 8 22:12:00 GMT 2005
This patch finally enables the new points-to solver by making it
part of the alias machinery. Up until now, we were only using it
in few cases, and we were not transferring all of the
information.
The main changes in the patch are:
- Points-to information is not built separately anymore. It's
fully integrated in pass_may_alias.
- The dreadful points-to analysis using use-def chains is gone.
The new solver is much more flexible and intuitive to use (it
does need some cosmetic TLC, though).
- Pointers pointing to malloc are represented by unique HEAP.x
variables that are created by the PT solver. These HEAP.x
variables are then exported into the may-alias sets of the
corresponding name tags. Pointers that may point into the same
heap space will receive the same HEAP variable.
- Pointer arithmetic used to confuse the new solver. If it saw
PTR + OFFSET, it would create one ANYTHING constraint for
OFFSET, which would then be transferred into the pointer as
"points-to anything" attribute.
This is no longer the case. We now have an ANYOFFSET
constraint which is similar to the ANYTHING constraint, except
that it specifies that the pointer can point anywhere a
specific object, not anywhere in memory.
For instance,
int a[10], *p;
for (i = 0, p = &a; i < 10; i++, p++)
p_1 = PHI <...>
*p_1 = ...
The solution for p_1 will be { ANYOFFSET a }, meaning that p_1
can point anywhere inside a. This is in contrast to:
p_1 = (pred) ? foo() : &a;
which yields { ANYTHING a }, meaning that p_1 could be pointing
anywhere in memory.
Another wrinkle in ANYOFFSET is when the solution includes an
aggregate variable with sub-variables. In those cases, all the
sub-variables of the aggregate are added to the final alias
set.
- Another bug in the points-to solver was with structures that
could have sub-variables but for which we didn't create SFTs
for all the fields. Some passes (SRA in this case) were adding
uses for fields that didn't have SFTs associated with them, so
we ICEd while solving the constraints. Fixed by not using the
SFTs and using the fields directly.
- The function merge_alias_info cannot be merging flow sensitive
alias information. This is because we call it from two
different contexts, one is from pointer assignments (during
copy propagation). In those cases, it would be OK for the
pointers to share flow-sensitive information.
But we also call this function when propagating equivalences
created by EQ_EXPR predicates. In those cases, the two
pointers are not always the same, they are only the same in one
of the sub-graphs dominated by the predicate (VRP, DOM).
The flow-insensitive information is always OK to merge, though.
The one real problem I have now is with the fix for PR 21356.
That patch together with this one causes bootstrap failures
everywhere. Somehow, DCE ends up garbling up dominance
information and we ICE in calc_dfs_tree. I am still not sure
what's going on, but undoing the patch for 21356 lets me finish
bootstrap and tests on all the architectures. I'm working on a
new fix for 21356 now.
Mark, this means that it may take me a little longer to commit
this patch. I hope this is OK with you.
Diego.
* Makefile.in (tree-ssa-alias.o): Depend on tree-ssa-structalias.h
* tree-cfg.c (CHECK_OP): Only test for is_gimple_val.
* tree-dfa.c (dump_subvars_for): New.
(debug_subvars_for): New.
(dump_variable): Show subvariables if VAR has them.
* tree-flow-inline.h (get_subvar_at): New.
(overlap_subvar): Change offset and size to unsigned HOST_WIDE_INT.
* tree-flow.h (struct ptr_info_def): Remove field pt_malloc.
Update all users.
(struct subvar): Change fields offset and size to unsigned
HOST_WIDE_INT.
(dump_subvars_for): Declare.
(debug_subvars_for): Declare.
(get_subvar_at): Declare.
(okay_component_ref_for_subvars): Change 2nd and 3rd argument
to unsigned HOST_WIDE_INT *.
(overlap_subvar): Likewise.
* tree-gimple.c (is_gimple_reg): Always return false for
SFTs and memory tags.
* tree-pass.h (pass_build_pta, pass_del_pta): Remove.
Update all callers.
* tree-ssa-alias.c: Include tree-ssa-structalias.h.
(compute_may_aliases): Call compute_points_to_sets.
(collect_points_to_info_for): Remove.
(compute_points_to_and_addr_escape): Remove.
(delete_alias_info): Call delete_points_to_sets.
(compute_flow_sensitive_aliasing): If the call to
find_what_p_points_to returns false, call set_pt_anything.
(add_may_alias): Set TREE_ADDRESSABLE when adding a new alias.
(set_pt_anything): Clear pi->pt_vars.
(set_pt_malloc): Remove.
(merge_pointed_to_info): Remove.
(add_pointed_to_expr): Remove.
(add_pointed_to_var): Remove.
(collect_points_to_info_r): Remove.
(is_escape_site): Make extern.
(create_sft): New.
(create_overlap_variables_for): Call it.
* tree-ssa-copy.c (merge_alias_info): Never merge
flow-sensitive alias information.
* tree-ssa-operands.c (get_expr_operands): Adjust variables
offset and size to be unsigned HOST_WIDE_INT.
(add_to_addressable_set): Rename from note_addressable.
Set TREE_ADDRESSABLE as the variables are added to the set.
Update all users.
* tree-ssa-operands.h (add_to_addressable_set): Declare.
* tree-ssa-structalias.c: Include tree-ssa-structalias.h last.
(struct variable_info): Add bitfield is_heap_var.
(var_anyoffset, anyoffset_tree, anyoffset_id): Declare.
(new_var_info): Initialize is_heap_var.
(get_constraint_for): Add HEAP variables to the symbol table.
Mark them with is_heap_var.
(update_alias_info): New. Taken mostly from the old
compute_points_to_and_addr_escape.
(handle_ptr_arith): New.
(find_func_aliases): Call update_alias_info.
Call handle_ptr_info for tcc_binary expressions.
Call mark_stmt_modified.
(create_variable_info_for): If DECL has subvars, do not create
variables for its subvars. Always add all the fields.
(set_uids_in_ptset): If the solution includes ANYOFFSET and
SFTs, then add all the SFTs of the structure.
If VI->DECL is an aggregate with subvariables, add the SFT at
VI->OFFSET.
(find_what_p_points_to): If VI is an artificial variable,
translate to bitfields in SSA_NAME_PTR_INFO.
If the solution is empty, set pi->pt_vars to NULL
(init_base_vars): Create ANYOFFSET.
(compute_points_to_sets): Rename from create_alias_vars.
Make extern.
(pass_build_pta): Remove.
(delete_points_to_sets): Rename from delete_alias_vars.
(pass_del_pta): Remove.
* tree-ssa-structalias.h (struct alias_info): Move from
tree-ssa-alias.h.
(NUM_REFERENCES, NUM_REFERENCES_CLEAR, NUM_REFERENCES_INC,
NUM_REFERENCES_SET): Likewise.
(compute_points_to_sets, delete_points_to_sets): Declare.
testsuite/ChangeLog
* gcc.dg/tree-ssa/pta-fp.c: Use -fdump-tree-alias1.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1519
diff -d -u -p -r1.1519 Makefile.in
--- Makefile.in 7 Jul 2005 12:37:16 -0000 1.1519
+++ Makefile.in 8 Jul 2005 20:31:08 -0000
@@ -1894,7 +1894,7 @@ tree-ssa-alias.o : tree-ssa-alias.c $(TR
$(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h $(FLAGS_H) \
function.h $(TIMEVAR_H) convert.h $(TM_H) coretypes.h langhooks.h \
$(TREE_DUMP_H) tree-pass.h $(PARAMS_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
- hard-reg-set.h $(TREE_GIMPLE_H) vec.h
+ hard-reg-set.h $(TREE_GIMPLE_H) vec.h tree-ssa-structalias.h
tree-ssa-reassoc.o : tree-ssa-reassoc.c $(TREE_FLOW_H) $(CONFIG_H) \
$(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) errors.h $(TIMEVAR_H) \
$(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) tree-iterator.h\
Index: passes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/passes.c,v
retrieving revision 2.97
diff -d -u -p -r2.97 passes.c
--- passes.c 5 Jul 2005 16:20:08 -0000 2.97
+++ passes.c 8 Jul 2005 20:31:08 -0000
@@ -471,10 +471,8 @@ init_optimization_passes (void)
NEXT_PASS (pass_referenced_vars);
NEXT_PASS (pass_create_structure_vars);
NEXT_PASS (pass_build_ssa);
- NEXT_PASS (pass_build_pta);
NEXT_PASS (pass_may_alias);
NEXT_PASS (pass_return_slot);
- NEXT_PASS (pass_del_pta);
NEXT_PASS (pass_rename_ssa_copies);
NEXT_PASS (pass_early_warn_uninitialized);
@@ -490,9 +488,7 @@ init_optimization_passes (void)
NEXT_PASS (pass_dominator);
NEXT_PASS (pass_phiopt);
- NEXT_PASS (pass_build_pta);
NEXT_PASS (pass_may_alias);
- NEXT_PASS (pass_del_pta);
NEXT_PASS (pass_tail_recursion);
NEXT_PASS (pass_profile);
NEXT_PASS (pass_ch);
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.208
diff -d -u -p -r2.208 tree-cfg.c
--- tree-cfg.c 3 Jul 2005 21:08:01 -0000 2.208
+++ tree-cfg.c 8 Jul 2005 20:31:09 -0000
@@ -3078,12 +3078,9 @@ verify_expr (tree *tp, int *walk_subtree
if (TYPE_P (t))
*walk_subtrees = 0;
- /* Check operand N for being valid GIMPLE and give error MSG if not.
- We check for constants explicitly since they are not considered
- gimple invariants if they overflowed. */
+ /* Check operand N for being valid GIMPLE and give error MSG if not. */
#define CHECK_OP(N, MSG) \
- do { if (!CONSTANT_CLASS_P (TREE_OPERAND (t, N)) \
- && !is_gimple_val (TREE_OPERAND (t, N))) \
+ do { if (!is_gimple_val (TREE_OPERAND (t, N))) \
{ error (MSG); return TREE_OPERAND (t, N); }} while (0)
switch (TREE_CODE (t))
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dfa.c,v
retrieving revision 2.58
diff -d -u -p -r2.58 tree-dfa.c
--- tree-dfa.c 30 Jun 2005 22:18:28 -0000 2.58
+++ tree-dfa.c 8 Jul 2005 20:31:09 -0000
@@ -254,6 +254,37 @@ debug_referenced_vars (void)
}
+/* Dump sub-variables for VAR to FILE. */
+
+void
+dump_subvars_for (FILE *file, tree var)
+{
+ subvar_t sv = get_subvars_for_var (var);
+
+ if (!sv)
+ return;
+
+ fprintf (file, "{ ");
+
+ for (; sv; sv = sv->next)
+ {
+ print_generic_expr (file, sv->var, dump_flags);
+ fprintf (file, " ");
+ }
+
+ fprintf (file, "}");
+}
+
+
+/* Dumb sub-variables for VAR to stderr. */
+
+void
+debug_subvars_for (tree var)
+{
+ dump_subvars_for (stderr, var);
+}
+
+
/* Dump variable VAR and its may-aliases to FILE. */
void
@@ -316,6 +347,12 @@ dump_variable (FILE *file, tree var)
dump_may_aliases_for (file, var);
}
+ if (get_subvars_for_var (var))
+ {
+ fprintf (file, ", sub-vars: ");
+ dump_subvars_for (file, var);
+ }
+
fprintf (file, "\n");
}
@@ -741,8 +778,8 @@ find_new_referenced_vars (tree *stmt_p)
size, in bits, of REF inside the return value. */
tree
-okay_component_ref_for_subvars (tree ref, HOST_WIDE_INT *poffset,
- HOST_WIDE_INT *psize)
+okay_component_ref_for_subvars (tree ref, unsigned HOST_WIDE_INT *poffset,
+ unsigned HOST_WIDE_INT *psize)
{
tree result = NULL;
HOST_WIDE_INT bitsize;
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.51
diff -d -u -p -r2.51 tree-flow-inline.h
--- tree-flow-inline.h 30 Jun 2005 22:18:30 -0000 2.51
+++ tree-flow-inline.h 8 Jul 2005 20:31:09 -0000
@@ -1444,6 +1444,20 @@ get_subvars_for_var (tree var)
return subvars;
}
+/* Return the subvariable of VAR at offset OFFSET. */
+
+static inline tree
+get_subvar_at (tree var, unsigned HOST_WIDE_INT offset)
+{
+ subvar_t sv;
+
+ for (sv = get_subvars_for_var (var); sv; sv = sv->next)
+ if (sv->offset == offset)
+ return sv->var;
+
+ return NULL_TREE;
+}
+
/* Return true if V is a tree that we can have subvars for.
Normally, this is any aggregate type, however, due to implementation
limitations ATM, we exclude array types as well. */
@@ -1461,7 +1475,7 @@ var_can_have_subvars (tree v)
*EXACT will be set to true upon return. */
static inline bool
-overlap_subvar (HOST_WIDE_INT offset, HOST_WIDE_INT size,
+overlap_subvar (unsigned HOST_WIDE_INT offset, unsigned HOST_WIDE_INT size,
subvar_t sv, bool *exact)
{
/* There are three possible cases of overlap.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.123
diff -d -u -p -r2.123 tree-flow.h
--- tree-flow.h 7 Jul 2005 05:40:21 -0000 2.123
+++ tree-flow.h 8 Jul 2005 20:31:09 -0000
@@ -71,9 +71,6 @@ struct ptr_info_def GTY(())
is pointing to. */
unsigned int pt_anything : 1;
- /* Nonzero if this pointer is the result of a call to malloc. */
- unsigned int pt_malloc : 1;
-
/* Nonzero if the value of this pointer escapes the current function. */
unsigned int value_escapes_p : 1;
@@ -160,19 +157,22 @@ enum mem_tag_kind {
/* This variable represents a structure field. */
STRUCT_FIELD
};
+
struct subvar;
typedef struct subvar *subvar_t;
/* This structure represents a fake sub-variable for a structure field. */
-
struct subvar GTY(())
{
- /* Fake variable name */
+ /* Fake variable. */
tree var;
+
/* Offset inside structure. */
- HOST_WIDE_INT offset;
- /* Size of field. */
- HOST_WIDE_INT size;
+ unsigned HOST_WIDE_INT offset;
+
+ /* Size of the field. */
+ unsigned HOST_WIDE_INT size;
+
/* Next subvar for this structure. */
subvar_t next;
};
@@ -552,6 +552,8 @@ extern void debug_referenced_vars (void)
extern void dump_referenced_vars (FILE *);
extern void dump_variable (FILE *, tree);
extern void debug_variable (tree);
+extern void dump_subvars_for (FILE *, tree);
+extern void debug_subvars_for (tree);
extern tree get_virtual_var (tree);
extern void add_referenced_tmp_var (tree);
extern void mark_new_vars_to_rename (tree);
@@ -578,11 +580,13 @@ extern void add_type_alias (tree, tree);
extern void new_type_alias (tree, tree);
extern void count_uses_and_derefs (tree, tree, unsigned *, unsigned *, bool *);
static inline subvar_t get_subvars_for_var (tree);
+static inline tree get_subvar_at (tree, unsigned HOST_WIDE_INT);
static inline bool ref_contains_array_ref (tree);
-extern tree okay_component_ref_for_subvars (tree, HOST_WIDE_INT *,
- HOST_WIDE_INT *);
+extern tree okay_component_ref_for_subvars (tree, unsigned HOST_WIDE_INT *,
+ unsigned HOST_WIDE_INT *);
static inline bool var_can_have_subvars (tree);
-static inline bool overlap_subvar (HOST_WIDE_INT, HOST_WIDE_INT,
+static inline bool overlap_subvar (unsigned HOST_WIDE_INT,
+ unsigned HOST_WIDE_INT,
subvar_t, bool *);
/* Call-back function for walk_use_def_chains(). At each reaching
Index: tree-gimple.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-gimple.c,v
retrieving revision 2.40
diff -d -u -p -r2.40 tree-gimple.c
--- tree-gimple.c 25 Jun 2005 02:01:22 -0000 2.40
+++ tree-gimple.c 8 Jul 2005 20:31:09 -0000
@@ -268,6 +268,8 @@ is_gimple_reg_type (tree type)
bool
is_gimple_reg (tree t)
{
+ var_ann_t ann;
+
if (TREE_CODE (t) == SSA_NAME)
t = SSA_NAME_VAR (t);
@@ -305,9 +307,16 @@ is_gimple_reg (tree t)
if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE)
return DECL_COMPLEX_GIMPLE_REG_P (t);
+ /* Some compiler temporaries are created to be used exclusively in
+ virtual operands (currently memory tags and sub-variables).
+ These variables should never be considered GIMPLE registers. */
+ if (DECL_ARTIFICIAL (t) && (ann = var_ann (t)) != NULL)
+ return ann->mem_tag_kind == NOT_A_TAG;
+
return true;
}
+
/* Returns true if T is a GIMPLE formal temporary variable. */
bool
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.47
diff -d -u -p -r2.47 tree-pass.h
--- tree-pass.h 5 Jul 2005 16:20:25 -0000 2.47
+++ tree-pass.h 8 Jul 2005 20:31:09 -0000
@@ -276,8 +276,6 @@ extern struct tree_opt_pass pass_store_c
extern struct tree_opt_pass pass_store_copy_prop;
extern struct tree_opt_pass pass_vrp;
extern struct tree_opt_pass pass_create_structure_vars;
-extern struct tree_opt_pass pass_build_pta;
-extern struct tree_opt_pass pass_del_pta;
extern struct tree_opt_pass pass_uncprop;
extern struct tree_opt_pass pass_return_slot;
extern struct tree_opt_pass pass_reassoc;
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.100
diff -d -u -p -r2.100 tree-ssa-alias.c
--- tree-ssa-alias.c 1 Jul 2005 03:55:22 -0000 2.100
+++ tree-ssa-alias.c 8 Jul 2005 20:31:10 -0000
@@ -40,19 +40,12 @@ Boston, MA 02110-1301, USA. */
#include "tree-flow.h"
#include "tree-inline.h"
#include "tree-pass.h"
+#include "tree-ssa-structalias.h"
#include "convert.h"
#include "params.h"
#include "vec.h"
#include "bitmap.h"
-/* Keep track of how many times each pointer has been dereferenced in
- the program using the aux variable. This is used by the alias
- grouping heuristic in compute_flow_insensitive_aliasing. */
-#define NUM_REFERENCES(ANN) ((size_t)((ANN)->common.aux))
-#define NUM_REFERENCES_CLEAR(ANN) ((ANN)->common.aux) = 0
-#define NUM_REFERENCES_INC(ANN) (ANN)->common.aux = (void*) (((size_t)((ANN)->common.aux)) + 1)
-#define NUM_REFERENCES_SET(ANN, VAL) (ANN)->common.aux = (void*) ((void *)(VAL))
-
/* Obstack used to hold grouping bitmaps and other temporary bitmaps used by
aliasing */
static bitmap_obstack alias_obstack;
@@ -83,51 +76,6 @@ struct alias_map_d
};
-/* Alias information used by compute_may_aliases and its helpers. */
-struct alias_info
-{
- /* SSA names visited while collecting points-to information. If bit I
- is set, it means that SSA variable with version I has already been
- visited. */
- sbitmap ssa_names_visited;
-
- /* Array of SSA_NAME pointers processed by the points-to collector. */
- varray_type processed_ptrs;
-
- /* Variables whose address is still needed. */
- bitmap addresses_needed;
-
- /* ADDRESSABLE_VARS contains all the global variables and locals that
- have had their address taken. */
- struct alias_map_d **addressable_vars;
- size_t num_addressable_vars;
-
- /* POINTERS contains all the _DECL pointers with unique memory tags
- that have been referenced in the program. */
- struct alias_map_d **pointers;
- size_t num_pointers;
-
- /* Number of function calls found in the program. */
- size_t num_calls_found;
-
- /* Number of const/pure function calls found in the program. */
- size_t num_pure_const_calls_found;
-
- /* Total number of virtual operands that will be needed to represent
- all the aliases of all the pointers found in the program. */
- long total_alias_vops;
-
- /* Variables that have been written to. */
- bitmap written_vars;
-
- /* Pointers that have been used in an indirect store operation. */
- bitmap dereferenced_ptrs_store;
-
- /* Pointers that have been used in an indirect load operation. */
- bitmap dereferenced_ptrs_load;
-};
-
-
/* Counters used to display statistics on alias analysis. */
struct alias_stats_d
{
@@ -155,18 +103,12 @@ static void add_may_alias (tree, tree);
static void replace_may_alias (tree, size_t, tree);
static struct alias_info *init_alias_info (void);
static void delete_alias_info (struct alias_info *);
-static void compute_points_to_and_addr_escape (struct alias_info *);
static void compute_flow_sensitive_aliasing (struct alias_info *);
static void setup_pointers_and_addressables (struct alias_info *);
-static bool collect_points_to_info_r (tree, tree, void *);
-static bool is_escape_site (tree, struct alias_info *);
-static void add_pointed_to_var (struct alias_info *, tree, tree);
static void create_global_var (void);
-static void collect_points_to_info_for (struct alias_info *, tree);
static void maybe_create_global_var (struct alias_info *ai);
static void group_aliases (struct alias_info *);
static void set_pt_anything (tree ptr);
-static void set_pt_malloc (tree ptr);
/* Global declarations. */
@@ -315,7 +257,7 @@ compute_may_aliases (void)
address of V escapes the current function, making V call-clobbered
(i.e., whether &V is stored in a global variable or if its passed as a
function call argument). */
- compute_points_to_and_addr_escape (ai);
+ compute_points_to_sets (ai);
/* Collect all pointers and addressable variables, compute alias sets,
create memory tags for pointers and promote variables whose address is
@@ -506,7 +448,6 @@ init_alias_info (void)
ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
sbitmap_zero (ai->ssa_names_visited);
VARRAY_TREE_INIT (ai->processed_ptrs, 50, "processed_ptrs");
- ai->addresses_needed = BITMAP_ALLOC (&alias_obstack);
ai->written_vars = BITMAP_ALLOC (&alias_obstack);
ai->dereferenced_ptrs_store = BITMAP_ALLOC (&alias_obstack);
ai->dereferenced_ptrs_load = BITMAP_ALLOC (&alias_obstack);
@@ -564,7 +505,6 @@ init_alias_info (void)
superset of its former points-to set, then a new
tag will need to be created in create_name_tags. */
pi->pt_anything = 0;
- pi->pt_malloc = 0;
pi->pt_null = 0;
pi->value_escapes_p = 0;
pi->is_dereferenced = 0;
@@ -592,7 +532,6 @@ delete_alias_info (struct alias_info *ai
sbitmap_free (ai->ssa_names_visited);
ai->processed_ptrs = NULL;
- BITMAP_FREE (ai->addresses_needed);
for (i = 0; i < ai->num_addressable_vars; i++)
free (ai->addressable_vars[i]);
@@ -613,171 +552,9 @@ delete_alias_info (struct alias_info *ai
BITMAP_FREE (ai->dereferenced_ptrs_store);
BITMAP_FREE (ai->dereferenced_ptrs_load);
bitmap_obstack_release (&alias_obstack);
-
free (ai);
-}
-
-
-/* Walk use-def chains for pointer PTR to determine what variables is PTR
- pointing to. */
-
-static void
-collect_points_to_info_for (struct alias_info *ai, tree ptr)
-{
- gcc_assert (POINTER_TYPE_P (TREE_TYPE (ptr)));
-
- if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)))
- {
- SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (ptr));
- walk_use_def_chains (ptr, collect_points_to_info_r, ai, true);
- VARRAY_PUSH_TREE (ai->processed_ptrs, ptr);
- }
-}
-
-/* Traverse use-def links for all the pointers in the program to collect
- address escape and points-to information.
-
- This is loosely based on the same idea described in R. Hasti and S.
- Horwitz, ``Using static single assignment form to improve
- flow-insensitive pointer analysis,'' in SIGPLAN Conference on
- Programming Language Design and Implementation, pp. 97-105, 1998. */
-
-static void
-compute_points_to_and_addr_escape (struct alias_info *ai)
-{
- basic_block bb;
- unsigned i;
- tree op;
- ssa_op_iter iter;
-
- timevar_push (TV_TREE_PTA);
-
- FOR_EACH_BB (bb)
- {
- block_stmt_iterator si;
-
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- {
- bitmap addr_taken;
- tree stmt = bsi_stmt (si);
- bool stmt_escapes_p = is_escape_site (stmt, ai);
- bitmap_iterator bi;
-
- /* Mark all the variables whose address are taken by the
- statement. Note that this will miss all the addresses taken
- in PHI nodes (those are discovered while following the use-def
- chains). */
- addr_taken = addresses_taken (stmt);
- if (addr_taken)
- EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
- {
- tree var = referenced_var (i);
- bitmap_set_bit (ai->addresses_needed, DECL_UID (var));
- if (stmt_escapes_p)
- mark_call_clobbered (var);
- }
-
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
- {
- tree var = SSA_NAME_VAR (op);
- var_ann_t v_ann = var_ann (var);
- struct ptr_info_def *pi;
- bool is_store;
- unsigned num_uses, num_derefs;
-
- /* If the operand's variable may be aliased, keep track
- of how many times we've referenced it. This is used
- for alias grouping in compute_flow_sensitive_aliasing.
- Note that we don't need to grow AI->NUM_REFERENCES
- because we are processing regular variables, not
- memory tags (the array's initial size is set to
- NUM_REFERENCED_VARS). */
- if (may_be_aliased (var))
- NUM_REFERENCES_INC (v_ann);
-
- if (!POINTER_TYPE_P (TREE_TYPE (op)))
- continue;
-
- collect_points_to_info_for (ai, op);
-
- pi = SSA_NAME_PTR_INFO (op);
- count_uses_and_derefs (op, stmt, &num_uses, &num_derefs,
- &is_store);
-
- if (num_derefs > 0)
- {
- /* Mark OP as dereferenced. In a subsequent pass,
- dereferenced pointers that point to a set of
- variables will be assigned a name tag to alias
- all the variables OP points to. */
- pi->is_dereferenced = 1;
-
- /* Keep track of how many time we've dereferenced each
- pointer. */
- NUM_REFERENCES_INC (v_ann);
-
- /* If this is a store operation, mark OP as being
- dereferenced to store, otherwise mark it as being
- dereferenced to load. */
- if (is_store)
- bitmap_set_bit (ai->dereferenced_ptrs_store,
- DECL_UID (var));
- else
- bitmap_set_bit (ai->dereferenced_ptrs_load,
- DECL_UID (var));
- }
-
- if (stmt_escapes_p && num_derefs < num_uses)
- {
- /* If STMT is an escape point and STMT contains at
- least one direct use of OP, then the value of OP
- escapes and so the pointed-to variables need to
- be marked call-clobbered. */
- pi->value_escapes_p = 1;
-
- /* If the statement makes a function call, assume
- that pointer OP will be dereferenced in a store
- operation inside the called function. */
- if (get_call_expr_in (stmt))
- {
- bitmap_set_bit (ai->dereferenced_ptrs_store,
- DECL_UID (var));
- pi->is_dereferenced = 1;
- }
- }
- }
-
- /* Update reference counter for definitions to any
- potentially aliased variable. This is used in the alias
- grouping heuristics. */
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
- {
- tree var = SSA_NAME_VAR (op);
- var_ann_t ann = var_ann (var);
- bitmap_set_bit (ai->written_vars, DECL_UID (var));
- if (may_be_aliased (var))
- NUM_REFERENCES_INC (ann);
-
- if (POINTER_TYPE_P (TREE_TYPE (op)))
- collect_points_to_info_for (ai, op);
- }
- /* Mark variables in V_MAY_DEF operands as being written to. */
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
- {
- tree var = DECL_P (op) ? op : SSA_NAME_VAR (op);
- bitmap_set_bit (ai->written_vars, DECL_UID (var));
- }
-
- /* After promoting variables and computing aliasing we will
- need to re-scan most statements. FIXME: Try to minimize the
- number of statements re-scanned. It's not really necessary to
- re-scan *all* statements. */
- mark_stmt_modified (stmt);
- }
- }
-
- timevar_pop (TV_TREE_PTA);
+ delete_points_to_sets ();
}
@@ -863,16 +640,10 @@ create_name_tags (void)
if (old_name_tag && old_name_tag != pi->name_mem_tag)
mark_sym_for_renaming (old_name_tag);
}
- else if (pi->pt_malloc)
- {
- /* Otherwise, create a unique name tag for this pointer. */
- pi->name_mem_tag = get_nmt_for (ptr);
- }
else
{
- /* Only pointers that may point to malloc or other variables
- may receive a name tag. If the pointer does not point to
- a known spot, we should use type tags. */
+ /* If the pointer does not point to a known spot, we should
+ use type tags. */
set_pt_anything (ptr);
continue;
}
@@ -902,11 +673,8 @@ compute_flow_sensitive_aliasing (struct
for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
{
tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
- if (pi->pt_anything || pi->pt_vars == NULL)
- {
- find_what_p_points_to (ptr);
- }
+ if (!find_what_p_points_to (ptr))
+ set_pt_anything (ptr);
}
create_name_tags ();
@@ -931,9 +699,7 @@ compute_flow_sensitive_aliasing (struct
if (pi->pt_vars)
EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, j, bi)
- {
- mark_call_clobbered (referenced_var (j));
- }
+ mark_call_clobbered (referenced_var (j));
}
/* Set up aliasing information for PTR's name memory tag (if it has
@@ -1009,9 +775,9 @@ compute_flow_insensitive_aliasing (struc
So we first check the call_clobbered status of the
tag and variable before querying the bitmap. */
tag_stored_p = is_call_clobbered (tag)
- || bitmap_bit_p (ai->written_vars, DECL_UID (tag));
+ || bitmap_bit_p (ai->written_vars, DECL_UID (tag));
var_stored_p = is_call_clobbered (var)
- || bitmap_bit_p (ai->written_vars, DECL_UID (var));
+ || bitmap_bit_p (ai->written_vars, DECL_UID (var));
if (!tag_stored_p && !var_stored_p)
continue;
@@ -1126,7 +892,7 @@ compute_flow_insensitive_aliasing (struc
}
if (dump_file)
- fprintf (dump_file, "%s: Total number of aliased vops: %ld\n",
+ fprintf (dump_file, "\n%s: Total number of aliased vops: %ld\n",
get_name (current_function_decl),
ai->total_alias_vops);
@@ -1458,9 +1224,9 @@ setup_pointers_and_addressables (struct
of ADDR_EXPR constants into INDIRECT_REF expressions and the
removal of dead pointer assignments done by the early scalar
cleanup passes. */
- if (TREE_ADDRESSABLE (var) && v_ann->mem_tag_kind != STRUCT_FIELD)
+ if (TREE_ADDRESSABLE (var))
{
- if (!bitmap_bit_p (ai->addresses_needed, DECL_UID (var))
+ if (!bitmap_bit_p (addressable_vars, DECL_UID (var))
&& TREE_CODE (var) != RESULT_DECL
&& !is_global_var (var))
{
@@ -1470,6 +1236,9 @@ setup_pointers_and_addressables (struct
to rename VAR into SSA afterwards. */
mark_sym_for_renaming (var);
+ /* If VAR can have sub-variables, and any of its
+ sub-variables has its address taken, then we cannot
+ remove the addressable flag from VAR. */
if (var_can_have_subvars (var)
&& (svars = get_subvars_for_var (var)))
{
@@ -1477,8 +1246,7 @@ setup_pointers_and_addressables (struct
for (sv = svars; sv; sv = sv->next)
{
- if (bitmap_bit_p (ai->addresses_needed,
- DECL_UID (sv->var)))
+ if (bitmap_bit_p (addressable_vars, DECL_UID (sv->var)))
okay_to_mark = false;
mark_sym_for_renaming (sv->var);
}
@@ -1490,22 +1258,6 @@ setup_pointers_and_addressables (struct
if (okay_to_mark)
mark_non_addressable (var);
}
- else
- {
- /* Add the variable to the set of addressables. Mostly
- used when scanning operands for ASM_EXPRs that
- clobber memory. In those cases, we need to clobber
- all call-clobbered variables and all addressables. */
- bitmap_set_bit (addressable_vars, DECL_UID (var));
- if (var_can_have_subvars (var)
- && (svars = get_subvars_for_var (var)))
- {
- subvar_t sv;
- for (sv = svars; sv; sv = sv->next)
- bitmap_set_bit (addressable_vars, DECL_UID (sv->var));
- }
-
- }
}
/* Global variables and addressable locals may be aliased. Create an
@@ -1562,10 +1314,9 @@ setup_pointers_and_addressables (struct
references of TAG. Since TAG can be associated with
several pointers, add the dereferences of VAR to the
TAG. */
-
NUM_REFERENCES_SET (t_ann,
- NUM_REFERENCES (t_ann) +
- NUM_REFERENCES (v_ann));
+ NUM_REFERENCES (t_ann)
+ + NUM_REFERENCES (v_ann));
}
else
{
@@ -1783,8 +1534,16 @@ add_may_alias (tree var, tree alias)
var_ann_t v_ann = get_var_ann (var);
var_ann_t a_ann = get_var_ann (alias);
+ /* Don't allow self-referential aliases. */
gcc_assert (var != alias);
+ /* ALIAS must be addressable if it's being added to an alias set. */
+#if 1
+ TREE_ADDRESSABLE (alias) = 1;
+#else
+ gcc_assert (may_be_aliased (alias));
+#endif
+
if (v_ann->may_aliases == NULL)
VARRAY_TREE_INIT (v_ann->may_aliases, 2, "aliases");
@@ -1836,7 +1595,7 @@ set_pt_anything (tree ptr)
struct ptr_info_def *pi = get_ptr_info (ptr);
pi->pt_anything = 1;
- pi->pt_malloc = 0;
+ pi->pt_vars = NULL;
/* The pointer used to have a name tag, but we now found it pointing
to an arbitrary location. The name tag needs to be renamed and
@@ -1849,341 +1608,6 @@ set_pt_anything (tree ptr)
}
-/* Mark pointer PTR as pointing to a malloc'd memory area. */
-
-static void
-set_pt_malloc (tree ptr)
-{
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
-
- /* If the pointer has already been found to point to arbitrary
- memory locations, it is unsafe to mark it as pointing to malloc. */
- if (pi->pt_anything)
- return;
-
- pi->pt_malloc = 1;
-}
-
-
-/* Given two different pointers DEST and ORIG. Merge the points-to
- information in ORIG into DEST. AI contains all the alias
- information collected up to this point. */
-
-static void
-merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig)
-{
- struct ptr_info_def *dest_pi, *orig_pi;
-
- gcc_assert (dest != orig);
-
- /* Make sure we have points-to information for ORIG. */
- collect_points_to_info_for (ai, orig);
-
- dest_pi = get_ptr_info (dest);
- orig_pi = SSA_NAME_PTR_INFO (orig);
-
- if (orig_pi)
- {
- gcc_assert (orig_pi != dest_pi);
-
- /* Notice that we never merge PT_MALLOC. This attribute is only
- true if the pointer is the result of a malloc() call.
- Otherwise, we can end up in this situation:
-
- P_i = malloc ();
- ...
- P_j = P_i + X;
-
- P_j would be marked as PT_MALLOC, however we currently do not
- handle cases of more than one pointer pointing to the same
- malloc'd area.
-
- FIXME: If the merging comes from an expression that preserves
- the PT_MALLOC attribute (copy assignment, address
- arithmetic), we ought to merge PT_MALLOC, but then both
- pointers would end up getting different name tags because
- create_name_tags is not smart enough to determine that the
- two come from the same malloc call. Copy propagation before
- aliasing should cure this. */
- dest_pi->pt_malloc = 0;
- if (orig_pi->pt_malloc || orig_pi->pt_anything)
- set_pt_anything (dest);
-
- dest_pi->pt_null |= orig_pi->pt_null;
-
- if (!dest_pi->pt_anything
- && orig_pi->pt_vars
- && !bitmap_empty_p (orig_pi->pt_vars))
- {
- if (dest_pi->pt_vars == NULL)
- {
- dest_pi->pt_vars = BITMAP_GGC_ALLOC ();
- bitmap_copy (dest_pi->pt_vars, orig_pi->pt_vars);
- }
- else
- bitmap_ior_into (dest_pi->pt_vars, orig_pi->pt_vars);
- }
- }
- else
- set_pt_anything (dest);
-}
-
-
-/* Add EXPR to the list of expressions pointed-to by PTR. */
-
-static void
-add_pointed_to_expr (struct alias_info *ai, tree ptr, tree expr)
-{
- if (TREE_CODE (expr) == WITH_SIZE_EXPR)
- expr = TREE_OPERAND (expr, 0);
-
- get_ptr_info (ptr);
-
- if (TREE_CODE (expr) == CALL_EXPR
- && (call_expr_flags (expr) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA)))
- {
- /* If EXPR is a malloc-like call, then the area pointed to PTR
- is guaranteed to not alias with anything else. */
- set_pt_malloc (ptr);
- }
- else if (TREE_CODE (expr) == ADDR_EXPR)
- {
- /* Found P_i = ADDR_EXPR */
- add_pointed_to_var (ai, ptr, expr);
- }
- else if (TREE_CODE (expr) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (expr)))
- {
- /* Found P_i = Q_j. */
- merge_pointed_to_info (ai, ptr, expr);
- }
- else if (TREE_CODE (expr) == PLUS_EXPR || TREE_CODE (expr) == MINUS_EXPR)
- {
- /* Found P_i = PLUS_EXPR or P_i = MINUS_EXPR */
- tree op0 = TREE_OPERAND (expr, 0);
- tree op1 = TREE_OPERAND (expr, 1);
-
- /* Both operands may be of pointer type. FIXME: Shouldn't
- we just expect PTR + OFFSET always? */
- if (POINTER_TYPE_P (TREE_TYPE (op0))
- && TREE_CODE (op0) != INTEGER_CST)
- {
- if (TREE_CODE (op0) == SSA_NAME)
- merge_pointed_to_info (ai, ptr, op0);
- else if (TREE_CODE (op0) == ADDR_EXPR)
- add_pointed_to_var (ai, ptr, op0);
- else
- set_pt_anything (ptr);
- }
-
- if (POINTER_TYPE_P (TREE_TYPE (op1))
- && TREE_CODE (op1) != INTEGER_CST)
- {
- if (TREE_CODE (op1) == SSA_NAME)
- merge_pointed_to_info (ai, ptr, op1);
- else if (TREE_CODE (op1) == ADDR_EXPR)
- add_pointed_to_var (ai, ptr, op1);
- else
- set_pt_anything (ptr);
- }
-
- /* Neither operand is a pointer? VAR can be pointing anywhere.
- FIXME: Shouldn't we asserting here? If we get here, we found
- PTR = INT_CST + INT_CST, which should not be a valid pointer
- expression. */
- if (!(POINTER_TYPE_P (TREE_TYPE (op0))
- && TREE_CODE (op0) != INTEGER_CST)
- && !(POINTER_TYPE_P (TREE_TYPE (op1))
- && TREE_CODE (op1) != INTEGER_CST))
- set_pt_anything (ptr);
- }
- else if (integer_zerop (expr))
- {
- /* EXPR is the NULL pointer. Mark PTR as pointing to NULL. */
- SSA_NAME_PTR_INFO (ptr)->pt_null = 1;
- }
- else
- {
- /* If we can't recognize the expression, assume that PTR may
- point anywhere. */
- set_pt_anything (ptr);
- }
-}
-
-
-/* If VALUE is of the form &DECL, add DECL to the set of variables
- pointed-to by PTR. Otherwise, add VALUE as a pointed-to expression by
- PTR. AI points to the collected alias information. */
-
-static void
-add_pointed_to_var (struct alias_info *ai, tree ptr, tree value)
-{
- struct ptr_info_def *pi = get_ptr_info (ptr);
- tree pt_var = NULL_TREE;
- HOST_WIDE_INT offset, size;
- tree addrop;
- size_t uid;
- tree ref;
- subvar_t svars;
-
- gcc_assert (TREE_CODE (value) == ADDR_EXPR);
-
- addrop = TREE_OPERAND (value, 0);
- if (REFERENCE_CLASS_P (addrop))
- pt_var = get_base_address (addrop);
- else
- pt_var = addrop;
-
- /* If this is a component_ref, see if we can get a smaller number of
- variables to take the address of. */
- if (TREE_CODE (addrop) == COMPONENT_REF
- && (ref = okay_component_ref_for_subvars (addrop, &offset ,&size)))
- {
- subvar_t sv;
- svars = get_subvars_for_var (ref);
-
- uid = DECL_UID (pt_var);
-
- if (pi->pt_vars == NULL)
- pi->pt_vars = BITMAP_GGC_ALLOC ();
- /* If the variable is a global, mark the pointer as pointing to
- global memory (which will make its tag a global variable). */
- if (is_global_var (pt_var))
- pi->pt_global_mem = 1;
-
- for (sv = svars; sv; sv = sv->next)
- {
- if (overlap_subvar (offset, size, sv, NULL))
- {
- bitmap_set_bit (pi->pt_vars, DECL_UID (sv->var));
- bitmap_set_bit (ai->addresses_needed, DECL_UID (sv->var));
- }
- }
- }
- else if (pt_var && SSA_VAR_P (pt_var))
- {
-
- uid = DECL_UID (pt_var);
-
- if (pi->pt_vars == NULL)
- pi->pt_vars = BITMAP_GGC_ALLOC ();
-
- /* If this is an aggregate, we may have subvariables for it that need
- to be pointed to. */
- if (var_can_have_subvars (pt_var)
- && (svars = get_subvars_for_var (pt_var)))
- {
- subvar_t sv;
- for (sv = svars; sv; sv = sv->next)
- {
- uid = DECL_UID (sv->var);
- bitmap_set_bit (ai->addresses_needed, uid);
- bitmap_set_bit (pi->pt_vars, uid);
- }
- }
- else
- {
- bitmap_set_bit (ai->addresses_needed, uid);
- bitmap_set_bit (pi->pt_vars, uid);
- }
-
- /* If the variable is a global, mark the pointer as pointing to
- global memory (which will make its tag a global variable). */
- if (is_global_var (pt_var))
- pi->pt_global_mem = 1;
- }
-}
-
-
-/* Callback for walk_use_def_chains to gather points-to information from the
- SSA web.
-
- VAR is an SSA variable or a GIMPLE expression.
-
- STMT is the statement that generates the SSA variable or, if STMT is a
- PHI_NODE, VAR is one of the PHI arguments.
-
- DATA is a pointer to a structure of type ALIAS_INFO. */
-
-static bool
-collect_points_to_info_r (tree var, tree stmt, void *data)
-{
- struct alias_info *ai = (struct alias_info *) data;
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Visiting use-def links for ");
- print_generic_expr (dump_file, var, dump_flags);
- fprintf (dump_file, "\n");
- }
-
- switch (TREE_CODE (stmt))
- {
- case RETURN_EXPR:
- gcc_assert (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR);
- stmt = TREE_OPERAND (stmt, 0);
- /* FALLTHRU */
-
- case MODIFY_EXPR:
- {
- tree rhs = TREE_OPERAND (stmt, 1);
- STRIP_NOPS (rhs);
- add_pointed_to_expr (ai, var, rhs);
- break;
- }
-
- case ASM_EXPR:
- /* Pointers defined by __asm__ statements can point anywhere. */
- set_pt_anything (var);
- break;
-
- case NOP_EXPR:
- if (IS_EMPTY_STMT (stmt))
- {
- tree decl = SSA_NAME_VAR (var);
-
- if (TREE_CODE (decl) == PARM_DECL)
- add_pointed_to_expr (ai, var, decl);
- else if (DECL_INITIAL (decl))
- add_pointed_to_expr (ai, var, DECL_INITIAL (decl));
- else
- add_pointed_to_expr (ai, var, decl);
- }
- break;
-
- case PHI_NODE:
- {
- /* It STMT is a PHI node, then VAR is one of its arguments. The
- variable that we are analyzing is the LHS of the PHI node. */
- tree lhs = PHI_RESULT (stmt);
-
- switch (TREE_CODE (var))
- {
- case ADDR_EXPR:
- add_pointed_to_var (ai, lhs, var);
- break;
-
- case SSA_NAME:
- /* Avoid unnecessary merges. */
- if (lhs != var)
- merge_pointed_to_info (ai, lhs, var);
- break;
-
- default:
- gcc_assert (is_gimple_min_invariant (var));
- add_pointed_to_expr (ai, lhs, var);
- break;
- }
- break;
- }
-
- default:
- gcc_unreachable ();
- }
-
- return false;
-}
-
-
/* Return true if STMT is an "escape" site from the current function. Escape
sites those statements which might expose the address of a variable
outside the current function. STMT is an escape site iff:
@@ -2195,7 +1619,7 @@ collect_points_to_info_r (tree var, tree
AI points to the alias information collected so far. */
-static bool
+bool
is_escape_site (tree stmt, struct alias_info *ai)
{
tree call = get_call_expr_in (stmt);
@@ -2271,9 +1695,7 @@ create_memory_tag (tree type, bool is_ty
determine whether they should be considered globals. */
DECL_CONTEXT (tag) = current_function_decl;
- /* Memory tags are by definition addressable. This also prevents
- is_gimple_ref frome confusing memory tags with optimizable
- variables. */
+ /* Memory tags are by definition addressable. */
TREE_ADDRESSABLE (tag) = 1;
ann = get_var_ann (tag);
@@ -2304,7 +1726,6 @@ get_nmt_for (tree ptr)
/* If PTR is a PARM_DECL, it points to a global variable or malloc,
then its name tag should be considered a global variable. */
if (TREE_CODE (SSA_NAME_VAR (ptr)) == PARM_DECL
- || pi->pt_malloc
|| pi->pt_global_mem)
mark_call_clobbered (tag);
@@ -2560,9 +1981,6 @@ dump_points_to_info_for (FILE *file, tre
if (pi->pt_anything)
fprintf (file, ", points-to anything");
- if (pi->pt_malloc)
- fprintf (file, ", points-to malloc");
-
if (pi->pt_null)
fprintf (file, ", points-to NULL");
@@ -2978,6 +2396,33 @@ get_or_create_used_part_for (size_t uid)
}
+/* Create and return a structure sub-variable for field FIELD of
+ variable VAR. */
+
+static tree
+create_sft (tree var, tree field)
+{
+ var_ann_t ann;
+ tree subvar = create_tmp_var_raw (TREE_TYPE (field), "SFT");
+
+ /* We need to copy the various flags from VAR to SUBVAR, so that
+ they are is_global_var iff the original variable was. */
+ DECL_CONTEXT (subvar) = DECL_CONTEXT (var);
+ DECL_EXTERNAL (subvar) = DECL_EXTERNAL (var);
+ TREE_PUBLIC (subvar) = TREE_PUBLIC (var);
+ TREE_STATIC (subvar) = TREE_STATIC (var);
+ TREE_READONLY (subvar) = TREE_READONLY (var);
+
+ /* Add the new variable to REFERENCED_VARS. */
+ ann = get_var_ann (subvar);
+ ann->mem_tag_kind = STRUCT_FIELD;
+ ann->type_mem_tag = NULL;
+ add_referenced_tmp_var (subvar);
+
+ return subvar;
+}
+
+
/* Given an aggregate VAR, create the subvariables that represent its
fields. */
@@ -3067,7 +2512,6 @@ create_overlap_variables_for (tree var)
{
subvar_t sv;
HOST_WIDE_INT fosize;
- var_ann_t ann;
tree currfotype;
fosize = TREE_INT_CST_LOW (DECL_SIZE (fo->field));
@@ -3088,7 +2532,8 @@ create_overlap_variables_for (tree var)
sv->offset = fo->offset;
sv->size = fosize;
sv->next = *subvars;
- sv->var = create_tmp_var_raw (TREE_TYPE (fo->field), "SFT");
+ sv->var = create_sft (var, fo->field);
+
if (dump_file)
{
fprintf (dump_file, "structure field tag %s created for var %s",
@@ -3100,25 +2545,6 @@ create_overlap_variables_for (tree var)
fprintf (dump_file, "\n");
}
- /* We need to copy the various flags from var to sv->var, so that
- they are is_global_var iff the original variable was. */
-
- DECL_EXTERNAL (sv->var) = DECL_EXTERNAL (var);
- TREE_PUBLIC (sv->var) = TREE_PUBLIC (var);
- TREE_STATIC (sv->var) = TREE_STATIC (var);
- TREE_READONLY (sv->var) = TREE_READONLY (var);
-
- /* Like other memory tags, these need to be marked addressable to
- keep is_gimple_reg from thinking they are real. */
- TREE_ADDRESSABLE (sv->var) = 1;
-
- DECL_CONTEXT (sv->var) = DECL_CONTEXT (var);
-
- ann = get_var_ann (sv->var);
- ann->mem_tag_kind = STRUCT_FIELD;
- ann->type_mem_tag = NULL;
- add_referenced_tmp_var (sv->var);
-
lastfotype = currfotype;
lastfooffset = fo->offset;
lastfosize = fosize;
Index: tree-ssa-copy.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-copy.c,v
retrieving revision 2.36
diff -d -u -p -r2.36 tree-ssa-copy.c
--- tree-ssa-copy.c 30 Jun 2005 00:51:05 -0000 2.36
+++ tree-ssa-copy.c 8 Jul 2005 20:31:10 -0000
@@ -188,7 +188,9 @@ merge_alias_info (tree orig, tree new)
#endif
/* Synchronize the type tags. If both pointers had a tag and they
- are different, then something has gone wrong. */
+ are different, then something has gone wrong. Type tags can
+ always be merged because they are flow insensitive, all the SSA
+ names of the same base DECL share the same type tag. */
if (new_ann->type_mem_tag == NULL_TREE)
new_ann->type_mem_tag = orig_ann->type_mem_tag;
else if (orig_ann->type_mem_tag == NULL_TREE)
@@ -196,32 +198,41 @@ merge_alias_info (tree orig, tree new)
else
gcc_assert (new_ann->type_mem_tag == orig_ann->type_mem_tag);
- /* Synchronize the name tags. If NEW did not have a name tag, get
- it from ORIG. This happens when NEW is a compiler generated
- temporary which still hasn't had its points-to information filled
- in. */
- if (SSA_NAME_PTR_INFO (orig))
+ /* Check that flow-sensitive information is compatible. Notice that
+ we may not merge flow-sensitive information here. This function
+ is called when propagating equivalences dictated by the IL, like
+ a copy operation P_i = Q_j, and from equivalences dictated by
+ control-flow, like if (P_i == Q_j).
+
+ In the former case, P_i and Q_j are equivalent in every block
+ dominated by the assignment, so their flow-sensitive information
+ is always the same. However, in the latter case, the pointers
+ P_i and Q_j are only equivalent in one of the sub-graphs out of
+ the predicate, so their flow-sensitive information is not the
+ same in every block dominated by the predicate.
+
+ Since we cannot distinguish one case from another in this
+ function, we can only make sure that if P_i and Q_j have
+ flow-sensitive information, they should be compatible. */
+ if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (new))
{
struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig);
struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new);
- if (new_ptr_info == NULL)
- duplicate_ssa_name_ptr_info (new, orig_ptr_info);
- else if (orig_ptr_info->name_mem_tag
- && new_ptr_info->name_mem_tag
- && orig_ptr_info->pt_vars
- && new_ptr_info->pt_vars)
- {
- /* Note that pointer NEW may actually have a different set
- of pointed-to variables. However, since NEW is being
- copy-propagated into ORIG, it must always be true that
- the pointed-to set for pointer NEW is the same, or a
- subset, of the pointed-to set for pointer ORIG. If this
- isn't the case, we shouldn't have been able to do the
- propagation of NEW into ORIG. */
- gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars,
- orig_ptr_info->pt_vars));
- }
+ /* Note that pointer NEW and ORIG may actually have different
+ pointed-to variables (e.g., PR 18291 represented in
+ testsuite/gcc.c-torture/compile/pr18291.c). However, since
+ NEW is being copy-propagated into ORIG, it must always be
+ true that the pointed-to set for pointer NEW is the same, or
+ a subset, of the pointed-to set for pointer ORIG. If this
+ isn't the case, we shouldn't have been able to do the
+ propagation of NEW into ORIG. */
+ if (orig_ptr_info->name_mem_tag
+ && new_ptr_info->name_mem_tag
+ && orig_ptr_info->pt_vars
+ && new_ptr_info->pt_vars)
+ gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars,
+ orig_ptr_info->pt_vars));
}
}
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.92
diff -d -u -p -r2.92 tree-ssa-operands.c
--- tree-ssa-operands.c 30 Jun 2005 22:18:34 -0000 2.92
+++ tree-ssa-operands.c 8 Jul 2005 20:31:10 -0000
@@ -32,7 +32,6 @@ Boston, MA 02110-1301, USA. */
#include "ggc.h"
#include "timevar.h"
#include "toplev.h"
-
#include "langhooks.h"
/* This file contains the code required to manage the operands cache of the
@@ -148,7 +147,6 @@ static bool ops_active = false;
static GTY (()) struct ssa_operand_memory_d *operand_memory = NULL;
static unsigned operand_memory_index;
-static void note_addressable (tree, stmt_ann_t);
static void get_expr_operands (tree, tree *, int);
static void get_asm_expr_operands (tree);
static void get_indirect_ref_operands (tree, tree, int);
@@ -1310,7 +1308,7 @@ get_expr_operands (tree stmt, tree *expr
case IMAGPART_EXPR:
{
tree ref;
- HOST_WIDE_INT offset, size;
+ unsigned HOST_WIDE_INT offset, size;
/* This component ref becomes an access to all of the subvariables
it can touch, if we can determine that, but *NOT* the real one.
If we can't determine which fields we could touch, the recursion
@@ -1515,8 +1513,8 @@ get_asm_expr_operands (tree stmt)
if (!allows_reg && allows_mem)
{
tree t = get_base_address (TREE_VALUE (link));
- if (t && DECL_P (t))
- note_addressable (t, s_ann);
+ if (t && DECL_P (t) && s_ann)
+ add_to_addressable_set (t, &s_ann->addresses_taken);
}
get_expr_operands (stmt, &TREE_VALUE (link), opf_is_def);
@@ -1534,8 +1532,8 @@ get_asm_expr_operands (tree stmt)
if (!allows_reg && allows_mem)
{
tree t = get_base_address (TREE_VALUE (link));
- if (t && DECL_P (t))
- note_addressable (t, s_ann);
+ if (t && DECL_P (t) && s_ann)
+ add_to_addressable_set (t, &s_ann->addresses_taken);
}
get_expr_operands (stmt, &TREE_VALUE (link), 0);
@@ -1688,7 +1686,10 @@ get_tmr_operands (tree stmt, tree expr,
flags &= ~opf_kill_def;
if (TMR_SYMBOL (expr))
- note_addressable (TMR_SYMBOL (expr), stmt_ann (stmt));
+ {
+ stmt_ann_t ann = stmt_ann (stmt);
+ add_to_addressable_set (TMR_SYMBOL (expr), &ann->addresses_taken);
+ }
if (tag)
add_stmt_operand (&tag, stmt_ann (stmt), flags);
@@ -1757,9 +1758,9 @@ add_stmt_operand (tree *var_p, stmt_ann_
/* If the operand is an ADDR_EXPR, add its operand to the list of
variables that have had their address taken in this statement. */
- if (TREE_CODE (var) == ADDR_EXPR)
+ if (TREE_CODE (var) == ADDR_EXPR && s_ann)
{
- note_addressable (TREE_OPERAND (var, 0), s_ann);
+ add_to_addressable_set (TREE_OPERAND (var, 0), &s_ann->addresses_taken);
return;
}
@@ -1910,40 +1911,51 @@ add_stmt_operand (tree *var_p, stmt_ann_
}
-/* Record that VAR had its address taken in the statement with annotations
- S_ANN. */
+/* Add the base address of REF to the set *ADDRESSES_TAKEN. If
+ *ADDRESSES_TAKEN is NULL, a new set is created. REF may be
+ a single variable whose address has been taken or any other valid
+ GIMPLE memory reference (structure reference, array, etc). If the
+ base address of REF is a decl that has sub-variables, also add all
+ of its sub-variables. */
-static void
-note_addressable (tree var, stmt_ann_t s_ann)
+void
+add_to_addressable_set (tree ref, bitmap *addresses_taken)
{
+ tree var;
subvar_t svars;
- if (!s_ann)
- return;
-
+ gcc_assert (addresses_taken);
+
/* Note that it is *NOT OKAY* to use the target of a COMPONENT_REF
- as the only thing we take the address of.
- See PR 21407 and the ensuing mailing list discussion. */
-
- var = get_base_address (var);
+ as the only thing we take the address of. If VAR is a structure,
+ taking the address of a field means that the whole structure may
+ be referenced using pointer arithmetic. See PR 21407 and the
+ ensuing mailing list discussion. */
+ var = get_base_address (ref);
if (var && SSA_VAR_P (var))
{
- if (s_ann->addresses_taken == NULL)
- s_ann->addresses_taken = BITMAP_GGC_ALLOC ();
+ if (*addresses_taken == NULL)
+ *addresses_taken = BITMAP_GGC_ALLOC ();
-
if (var_can_have_subvars (var)
&& (svars = get_subvars_for_var (var)))
{
subvar_t sv;
for (sv = svars; sv; sv = sv->next)
- bitmap_set_bit (s_ann->addresses_taken, DECL_UID (sv->var));
+ {
+ bitmap_set_bit (*addresses_taken, DECL_UID (sv->var));
+ TREE_ADDRESSABLE (sv->var) = 1;
+ }
}
else
- bitmap_set_bit (s_ann->addresses_taken, DECL_UID (var));
+ {
+ bitmap_set_bit (*addresses_taken, DECL_UID (var));
+ TREE_ADDRESSABLE (var) = 1;
+ }
}
}
+
/* Add clobbering definitions for .GLOBAL_VAR or for each of the call
clobbered variables in the function. */
Index: tree-ssa-operands.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.h,v
retrieving revision 2.19
diff -d -u -p -r2.19 tree-ssa-operands.h
--- tree-ssa-operands.h 27 Jun 2005 23:33:02 -0000 2.19
+++ tree-ssa-operands.h 8 Jul 2005 20:31:10 -0000
@@ -170,6 +170,8 @@ extern bool ssa_ro_call_cache_valid;
extern bool ssa_operands_active (void);
+extern void add_to_addressable_set (tree, bitmap *);
+
enum ssa_op_iter_type {
ssa_op_iter_none = 0,
ssa_op_iter_tree,
Index: tree-ssa-structalias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-structalias.c,v
retrieving revision 2.13
diff -d -u -p -r2.13 tree-ssa-structalias.c
--- tree-ssa-structalias.c 6 Jul 2005 16:49:57 -0000 2.13
+++ tree-ssa-structalias.c 8 Jul 2005 20:31:11 -0000
@@ -26,7 +26,6 @@ Foundation, Inc., 51 Franklin Street, Fi
#include "ggc.h"
#include "obstack.h"
#include "bitmap.h"
-#include "tree-ssa-structalias.h"
#include "flags.h"
#include "rtl.h"
#include "tm_p.h"
@@ -49,6 +48,7 @@ Foundation, Inc., 51 Franklin Street, Fi
#include "timevar.h"
#include "alloc-pool.h"
#include "splay-tree.h"
+#include "tree-ssa-structalias.h"
/* The idea behind this analyzer is to generate set constraints from the
program, then solve the resulting constraints in order to generate the
@@ -223,6 +223,9 @@ struct variable_info
/* True for variables that have unions somewhere in them. */
unsigned int has_union:1;
+ /* True if this is a heap variable. */
+ unsigned int is_heap_var:1;
+
/* Points-to set for this variable. */
bitmap solution;
@@ -270,6 +273,12 @@ static varinfo_t var_integer;
static tree integer_tree;
static unsigned int integer_id;
+/* Variable that represents arbitrary offsets into an object. Used to
+ represent pointer arithmetic, which may not legally escape the
+ bounds of an object. */
+static varinfo_t var_anyoffset;
+static tree anyoffset_tree;
+static unsigned int anyoffset_id;
/* Return a new variable info structure consisting for a variable
named NAME, and using constraint graph node NODE. */
@@ -286,6 +295,7 @@ new_var_info (tree t, unsigned int id, c
ret->address_taken = false;
ret->indirect_target = false;
ret->is_artificial_var = false;
+ ret->is_heap_var = false;
ret->is_unknown_size_var = false;
ret->solution = BITMAP_ALLOC (&ptabitmap_obstack);
bitmap_clear (ret->solution);
@@ -941,8 +951,11 @@ build_constraint_graph (void)
constraint_t c;
graph = ggc_alloc (sizeof (struct constraint_graph));
- graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->succs));
- graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap) * sizeof (*graph->preds));
+ graph->succs = ggc_alloc_cleared (VEC_length (varinfo_t, varmap)
+ * sizeof (*graph->succs));
+ graph->preds = ggc_alloc_cleared (VEC_length (varinfo_t, varmap)
+ * sizeof (*graph->preds));
+
for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++)
{
struct constraint_expr lhs = c->lhs;
@@ -983,6 +996,8 @@ build_constraint_graph (void)
}
}
}
+
+
/* Changed variables on the last iteration. */
static unsigned int changed_count;
static sbitmap changed;
@@ -2137,11 +2152,18 @@ get_constraint_for (tree t)
&ANYTHING added. */
if (call_expr_flags (t) & (ECF_MALLOC | ECF_MAY_BE_ALLOCA))
{
- tree heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
+ varinfo_t vi;
+ tree heapvar;
+
+ heapvar = create_tmp_var_raw (ptr_type_node, "HEAP");
+ DECL_EXTERNAL (heapvar) = 1;
+ add_referenced_tmp_var (heapvar);
temp.var = create_variable_info_for (heapvar,
alias_get_name (heapvar));
- get_varinfo (temp.var)->is_artificial_var = 1;
+ vi = get_varinfo (temp.var);
+ vi->is_artificial_var = 1;
+ vi->is_heap_var = 1;
temp.type = ADDRESSOF;
temp.offset = 0;
return temp;
@@ -2191,9 +2213,11 @@ get_constraint_for (tree t)
/* Cast from non-pointer to pointers are bad news for us.
Anything else, we see through */
- if (!(POINTER_TYPE_P (TREE_TYPE (t)) &&
- ! POINTER_TYPE_P (TREE_TYPE (op))))
+ if (!(POINTER_TYPE_P (TREE_TYPE (t))
+ && ! POINTER_TYPE_P (TREE_TYPE (op))))
return get_constraint_for (op);
+
+ /* FALLTHRU */
}
default:
{
@@ -2467,81 +2491,300 @@ ref_contains_indirect_ref (tree ref)
}
-/* Tree walker that is the heart of the aliasing infrastructure.
- TP is a pointer to the current tree.
- WALK_SUBTREES specifies whether to continue traversing subtrees or
- not.
- Returns NULL_TREE when we should stop.
-
- This function is the main part of the constraint builder. It
- walks the trees, calling the appropriate building functions
- to process various statements. */
+/* Update related alias information kept in AI. This is used when
+ building name tags, alias sets and deciding grouping heuristics.
+ STMT is the statement to process. This function also updates
+ ADDRESSABLE_VARS. */
static void
-find_func_aliases (tree t)
+update_alias_info (tree stmt, struct alias_info *ai)
+{
+ bitmap addr_taken;
+ use_operand_p use_p;
+ def_operand_p def_p;
+ ssa_op_iter iter;
+ bool stmt_escapes_p = is_escape_site (stmt, ai);
+
+ /* Mark all the variables whose address are taken by the statement. */
+ addr_taken = addresses_taken (stmt);
+ if (addr_taken)
+ {
+ bitmap_ior_into (addressable_vars, addr_taken);
+
+ /* If STMT is an escape point, all the addresses taken by it are
+ call-clobbered. */
+ if (stmt_escapes_p)
+ {
+ bitmap_iterator bi;
+ unsigned i;
+
+ EXECUTE_IF_SET_IN_BITMAP (addr_taken, 0, i, bi)
+ mark_call_clobbered (referenced_var (i));
+ }
+ }
+
+ /* Process each operand use. If an operand may be aliased, keep
+ track of how many times it's being used. For pointers, determine
+ whether they are dereferenced by the statement, or whether their
+ value escapes, etc. */
+ FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
+ {
+ tree op, var;
+ var_ann_t v_ann;
+ struct ptr_info_def *pi;
+ bool is_store;
+ unsigned num_uses, num_derefs;
+
+ op = USE_FROM_PTR (use_p);
+
+ /* If STMT is a PHI node, OP may be an ADDR_EXPR. If so, add it
+ to the set of addressable variables. */
+ if (TREE_CODE (op) == ADDR_EXPR)
+ {
+ gcc_assert (TREE_CODE (stmt) == PHI_NODE);
+
+ /* PHI nodes don't have annotations for pinning the set
+ of addresses taken, so we collect them here.
+
+ FIXME, should we allow PHI nodes to have annotations
+ so that they can be treated like regular statements?
+ Currently, they are treated as second-class
+ statements. */
+ add_to_addressable_set (TREE_OPERAND (op, 0), &addressable_vars);
+ continue;
+ }
+
+ /* Ignore constants. */
+ if (TREE_CODE (op) != SSA_NAME)
+ continue;
+
+ var = SSA_NAME_VAR (op);
+ v_ann = var_ann (var);
+
+ /* If the operand's variable may be aliased, keep track of how
+ many times we've referenced it. This is used for alias
+ grouping in compute_flow_insensitive_aliasing. */
+ if (may_be_aliased (var))
+ NUM_REFERENCES_INC (v_ann);
+
+ /* We are only interested in pointers. */
+ if (!POINTER_TYPE_P (TREE_TYPE (op)))
+ continue;
+
+ pi = get_ptr_info (op);
+
+ /* Add OP to AI->PROCESSED_PTRS, if it's not there already. */
+ if (!TEST_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op)))
+ {
+ SET_BIT (ai->ssa_names_visited, SSA_NAME_VERSION (op));
+ VARRAY_PUSH_TREE (ai->processed_ptrs, op);
+ }
+
+ /* If STMT is a PHI node, then it will not have pointer
+ dereferences and it will not be an escape point. */
+ if (TREE_CODE (stmt) == PHI_NODE)
+ continue;
+
+ /* Determine whether OP is a dereferenced pointer, and if STMT
+ is an escape point, whether OP escapes. */
+ count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
+
+ if (num_derefs > 0)
+ {
+ /* Mark OP as dereferenced. In a subsequent pass,
+ dereferenced pointers that point to a set of
+ variables will be assigned a name tag to alias
+ all the variables OP points to. */
+ pi->is_dereferenced = 1;
+
+ /* Keep track of how many time we've dereferenced each
+ pointer. */
+ NUM_REFERENCES_INC (v_ann);
+
+ /* If this is a store operation, mark OP as being
+ dereferenced to store, otherwise mark it as being
+ dereferenced to load. */
+ if (is_store)
+ bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
+ else
+ bitmap_set_bit (ai->dereferenced_ptrs_load, DECL_UID (var));
+ }
+
+ if (stmt_escapes_p && num_derefs < num_uses)
+ {
+ /* If STMT is an escape point and STMT contains at
+ least one direct use of OP, then the value of OP
+ escapes and so the pointed-to variables need to
+ be marked call-clobbered. */
+ pi->value_escapes_p = 1;
+
+ /* If the statement makes a function call, assume
+ that pointer OP will be dereferenced in a store
+ operation inside the called function. */
+ if (get_call_expr_in (stmt))
+ {
+ bitmap_set_bit (ai->dereferenced_ptrs_store, DECL_UID (var));
+ pi->is_dereferenced = 1;
+ }
+ }
+ }
+
+ /* Update reference counter for definitions to any potentially
+ aliased variable. This is used in the alias grouping heuristics. */
+ FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, iter, SSA_OP_ALL_DEFS)
+ {
+ tree op = DEF_FROM_PTR (def_p);
+ tree var = SSA_NAME_VAR (op);
+ var_ann_t ann = var_ann (var);
+ bitmap_set_bit (ai->written_vars, DECL_UID (var));
+ if (may_be_aliased (var))
+ NUM_REFERENCES_INC (ann);
+ }
+}
+
+
+/* Handle pointer arithmetic EXPR when creating aliasing constraints.
+ Expressions of the type PTR + CST can be handled in two ways:
+
+ 1- If the constraint for PTR is ADDRESSOF for a non-structure
+ variable, then we can use it directly because adding or
+ subtracting a constant may not alter the original ADDRESSOF
+ constraing (i.e., pointer arithmetic may not legally go outside
+ an object's boundaries).
+
+ 2- If the constraint for PTR is ADDRESSOF for a structure variable,
+ then if CST is a compile-time constant that can be used as an
+ offset, we can determine which sub-variable will be pointed-to
+ by the expression.
+
+ Return true if the expression is handled. For any other kind of
+ expression, return false so that each operand can be added as a
+ separate constraint by the caller. */
+
+static bool
+handle_ptr_arith (struct constraint_expr lhs, tree expr)
+{
+ tree op0, op1;
+ struct constraint_expr base, offset;
+
+ if (TREE_CODE (expr) != PLUS_EXPR)
+ return false;
+
+ op0 = TREE_OPERAND (expr, 0);
+ op1 = TREE_OPERAND (expr, 1);
+
+ base = get_constraint_for (op0);
+
+ offset.var = anyoffset_id;
+ offset.type = ADDRESSOF;
+ offset.offset = 0;
+
+ process_constraint (new_constraint (lhs, base));
+ process_constraint (new_constraint (lhs, offset));
+
+ return true;
+}
+
+
+/* Walk statement T setting up aliasing constraints according to the
+ references found in T. This function is the main part of the
+ constraint builder. AI points to auxiliary alias information used
+ when building alias sets and computing alias grouping heuristics. */
+
+static void
+find_func_aliases (tree t, struct alias_info *ai)
{
struct constraint_expr lhs, rhs;
- switch (TREE_CODE (t))
- {
- case PHI_NODE:
- {
- int i;
- /* Only care about pointers and structures containing
- pointers. */
- if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
- || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
- {
- lhs = get_constraint_for (PHI_RESULT (t));
- for (i = 0; i < PHI_NUM_ARGS (t); i++)
- {
- rhs = get_constraint_for (PHI_ARG_DEF (t, i));
- process_constraint (new_constraint (lhs, rhs));
- }
- }
- }
- break;
+ /* Update various related attributes like escaped addresses, pointer
+ dereferences for loads and stores. This is used when creating
+ name tags and alias sets. */
+ update_alias_info (t, ai);
- case MODIFY_EXPR:
- {
- tree lhsop = TREE_OPERAND (t, 0);
- tree rhsop = TREE_OPERAND (t, 1);
- int i;
+ /* Now build constraints expressions. */
+ if (TREE_CODE (t) == PHI_NODE)
+ {
+ /* Only care about pointers and structures containing
+ pointers. */
+ if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t)))
+ || AGGREGATE_TYPE_P (TREE_TYPE (PHI_RESULT (t))))
+ {
+ int i;
- if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
- && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
- {
- do_structure_copy (lhsop, rhsop);
- }
- else
- {
- /* Only care about operations with pointers, structures
- containing pointers, dereferences, and call
- expressions. */
- if (POINTER_TYPE_P (TREE_TYPE (lhsop))
- || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
- || ref_contains_indirect_ref (lhsop)
- || TREE_CODE (rhsop) == CALL_EXPR)
- {
- lhs = get_constraint_for (lhsop);
- switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
- {
- /* RHS that consist of unary operations,
- exceptional types, or bare decls/constants, get
- handled directly by get_constraint_for. */
+ lhs = get_constraint_for (PHI_RESULT (t));
+ for (i = 0; i < PHI_NUM_ARGS (t); i++)
+ {
+ rhs = get_constraint_for (PHI_ARG_DEF (t, i));
+ process_constraint (new_constraint (lhs, rhs));
+ }
+ }
+ }
+ else if (TREE_CODE (t) == MODIFY_EXPR)
+ {
+ tree lhsop = TREE_OPERAND (t, 0);
+ tree rhsop = TREE_OPERAND (t, 1);
+ int i;
+
+ if (AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
+ && AGGREGATE_TYPE_P (TREE_TYPE (rhsop)))
+ {
+ do_structure_copy (lhsop, rhsop);
+ }
+ else
+ {
+ /* Only care about operations with pointers, structures
+ containing pointers, dereferences, and call expressions. */
+ if (POINTER_TYPE_P (TREE_TYPE (lhsop))
+ || AGGREGATE_TYPE_P (TREE_TYPE (lhsop))
+ || ref_contains_indirect_ref (lhsop)
+ || TREE_CODE (rhsop) == CALL_EXPR)
+ {
+ lhs = get_constraint_for (lhsop);
+ switch (TREE_CODE_CLASS (TREE_CODE (rhsop)))
+ {
+ /* RHS that consist of unary operations,
+ exceptional types, or bare decls/constants, get
+ handled directly by get_constraint_for. */
case tcc_reference:
case tcc_declaration:
case tcc_constant:
case tcc_exceptional:
case tcc_expression:
case tcc_unary:
- {
- rhs = get_constraint_for (rhsop);
- process_constraint (new_constraint (lhs, rhs));
- }
+ {
+ rhs = get_constraint_for (rhsop);
+ process_constraint (new_constraint (lhs, rhs));
+
+ /* When taking the address of an aggregate
+ type, from the LHS we can access any field
+ of the RHS. */
+ if (rhs.type == ADDRESSOF
+ && rhs.var > anything_id
+ && AGGREGATE_TYPE_P (TREE_TYPE (TREE_TYPE (rhsop))))
+ {
+ rhs.var = anyoffset_id;
+ rhs.type = ADDRESSOF;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
+ }
+ }
break;
- /* Otherwise, walk each operand. */
+ case tcc_binary:
+ {
+ /* For pointer arithmetic of the form
+ PTR + CST, we can simply use PTR's
+ constraint because pointer arithmetic is
+ not allowed to go out of bounds. */
+ if (handle_ptr_arith (lhs, rhsop))
+ break;
+ }
+ /* FALLTHRU */
+
+ /* Otherwise, walk each operand. Notice that we
+ can't use the operand interface because we need
+ to process expressions other than simple operands
+ (e.g. INDIRECT_REF, ADDR_EXPR, CALL_EXPR). */
default:
for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (rhsop)); i++)
{
@@ -2549,15 +2792,16 @@ find_func_aliases (tree t)
rhs = get_constraint_for (op);
process_constraint (new_constraint (lhs, rhs));
}
- }
- }
- }
- }
- break;
-
- default:
- break;
+ }
+ }
+ }
}
+
+ /* After promoting variables and computing aliasing we will
+ need to re-scan most statements. FIXME: Try to minimize the
+ number of statements re-scanned. It's not really necessary to
+ re-scan *all* statements. */
+ mark_stmt_modified (t);
}
@@ -2718,12 +2962,12 @@ create_variable_info_for (tree decl, con
tree decltype = TREE_TYPE (decl);
bool notokay = false;
bool hasunion;
- subvar_t svars;
bool is_global = DECL_P (decl) ? is_global_var (decl) : false;
VEC (fieldoff_s,heap) *fieldstack = NULL;
- hasunion = TREE_CODE (decltype) == UNION_TYPE || TREE_CODE (decltype) == QUAL_UNION_TYPE;
+ hasunion = TREE_CODE (decltype) == UNION_TYPE
+ || TREE_CODE (decltype) == QUAL_UNION_TYPE;
if (var_can_have_subvars (decl) && use_field_sensitive && !hasunion)
{
push_fields_onto_fieldstack (decltype, &fieldstack, 0, &hasunion);
@@ -2733,62 +2977,6 @@ create_variable_info_for (tree decl, con
notokay = true;
}
}
-
- /* If this variable already has subvars, just create the variables for the
- subvars and we are done.
- NOTE: This assumes things haven't generated uses of previously
- unused structure fields. */
- if (use_field_sensitive
- && !notokay
- && var_can_have_subvars (decl)
- && var_ann (decl)
- && (svars = get_subvars_for_var (decl)))
- {
- subvar_t sv;
- varinfo_t base = NULL;
- unsigned int firstindex = index;
-
- for (sv = svars; sv; sv = sv->next)
- {
- /* For debugging purposes, this will print the names of the
- fields as "<var>.<offset>.<size>"
- This is only for debugging purposes. */
-#define PRINT_LONG_NAMES
-#ifdef PRINT_LONG_NAMES
- char *tempname;
- const char *newname;
-
- asprintf (&tempname,
- "%s." HOST_WIDE_INT_PRINT_DEC "." HOST_WIDE_INT_PRINT_DEC,
- alias_get_name (decl), sv->offset, sv->size);
- newname = ggc_strdup (tempname);
- free (tempname);
- vi = new_var_info (sv->var, index, newname, index);
-#else
- vi = new_var_info (sv->var, index, alias_get_name (sv->var), index);
-#endif
- vi->decl = sv->var;
- vi->fullsize = TREE_INT_CST_LOW (TYPE_SIZE (decltype));
- vi->size = sv->size;
- vi->offset = sv->offset;
- if (!base)
- {
- base = vi;
- insert_id_for_tree (decl, index);
- }
- else
- {
- insert_into_field_list (base, vi);
- }
- insert_id_for_tree (sv->var, index);
- VEC_safe_push (varinfo_t, gc, varmap, vi);
- if (is_global)
- make_constraint_to_anything (vi);
- index++;
-
- }
- return firstindex;
- }
/* If the variable doesn't have subvars, we may end up needing to
@@ -2935,7 +3123,6 @@ intra_create_variable_infos (void)
lhs.type = SCALAR;
lhs.var = create_variable_info_for (t, alias_get_name (t));
- get_varinfo (lhs.var)->is_artificial_var = true;
rhs.var = anything_id;
rhs.type = ADDRESSOF;
rhs.offset = 0;
@@ -2958,30 +3145,67 @@ set_uids_in_ptset (bitmap into, bitmap f
{
unsigned int i;
bitmap_iterator bi;
+ bool found_anyoffset = false;
+ subvar_t sv;
EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
{
varinfo_t vi = get_varinfo (i);
+
+ /* If we find ANYOFFSET in the solution and the solution
+ includes SFTs for some structure, then all the SFTs in that
+ structure will need to be added to the alias set. */
+ if (vi->id == anyoffset_id)
+ {
+ found_anyoffset = true;
+ continue;
+ }
+
+ /* The only artificial variables that are allowed in a may-alias
+ set are heap variables. */
+ if (vi->is_artificial_var && !vi->is_heap_var)
+ continue;
- /* Variables containing unions may need to be converted to their
- SFT's, because SFT's can have unions and we cannot. */
if (vi->has_union && get_subvars_for_var (vi->decl) != NULL)
{
- subvar_t svars = get_subvars_for_var (vi->decl);
- subvar_t sv;
- for (sv = svars; sv; sv = sv->next)
+ /* Variables containing unions may need to be converted to
+ their SFT's, because SFT's can have unions and we cannot. */
+ for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
bitmap_set_bit (into, DECL_UID (sv->var));
}
- /* We may end up with labels in the points-to set because people
- take their address, and they are _DECL's. */
else if (TREE_CODE (vi->decl) == VAR_DECL
- || TREE_CODE (vi->decl) == PARM_DECL)
- bitmap_set_bit (into, DECL_UID (vi->decl));
-
-
+ || TREE_CODE (vi->decl) == PARM_DECL)
+ {
+ if (found_anyoffset
+ && var_can_have_subvars (vi->decl)
+ && get_subvars_for_var (vi->decl))
+ {
+ /* If ANYOFFSET is in the solution set and VI->DECL is
+ an aggregate variable with sub-variables, then any of
+ the SFTs inside VI->DECL may have been accessed. Add
+ all the sub-vars for VI->DECL. */
+ for (sv = get_subvars_for_var (vi->decl); sv; sv = sv->next)
+ bitmap_set_bit (into, DECL_UID (sv->var));
+ }
+ else if (var_can_have_subvars (vi->decl)
+ && get_subvars_for_var (vi->decl))
+ {
+ /* If VI->DECL is an aggregate for which we created
+ SFTs, add the SFT corresponding to VI->OFFSET. */
+ tree sft = get_subvar_at (vi->decl, vi->offset);
+ bitmap_set_bit (into, DECL_UID (sft));
+ }
+ else
+ {
+ /* Otherwise, just add VI->DECL to the alias set. */
+ bitmap_set_bit (into, DECL_UID (vi->decl));
+ }
+ }
}
}
-static int have_alias_info = false;
+
+
+static bool have_alias_info = false;
/* Given a pointer variable P, fill in its points-to set, or return
false if we can't. */
@@ -2990,8 +3214,10 @@ bool
find_what_p_points_to (tree p)
{
unsigned int id = 0;
+
if (!have_alias_info)
return false;
+
if (lookup_id_for_tree (p, &id))
{
varinfo_t vi = get_varinfo (id);
@@ -2999,14 +3225,15 @@ find_what_p_points_to (tree p)
if (vi->is_artificial_var)
return false;
- /* See if this is a field or a structure */
+ /* See if this is a field or a structure. */
if (vi->size != vi->fullsize)
{
+ /* Nothing currently asks about structure fields directly,
+ but when they do, we need code here to hand back the
+ points-to set. */
if (!var_can_have_subvars (vi->decl)
|| get_subvars_for_var (vi->decl) == NULL)
return false;
- /* Nothing currently asks about structure fields directly, but when
- they do, we need code here to hand back the points-to set. */
}
else
{
@@ -3018,21 +3245,45 @@ find_what_p_points_to (tree p)
variable. */
vi = get_varinfo (vi->node);
- /* Make sure there aren't any artificial vars in the points to set.
- XXX: Note that we need to translate our heap variables to
- something. */
+ /* Translate artificial variables into SSA_NAME_PTR_INFO
+ attributes. */
EXECUTE_IF_SET_IN_BITMAP (vi->solution, 0, i, bi)
{
- if (get_varinfo (i)->is_artificial_var)
- return false;
+ varinfo_t vi = get_varinfo (i);
+
+ if (vi->is_artificial_var)
+ {
+ /* FIXME. READONLY should be handled better so that
+ flow insensitive aliasing can disregard writeable
+ aliases. */
+ if (vi->id == nothing_id)
+ pi->pt_null = 1;
+ else if (vi->id == anything_id)
+ pi->pt_anything = 1;
+ else if (vi->id == readonly_id)
+ pi->pt_anything = 1;
+ else if (vi->id == integer_id)
+ pi->pt_anything = 1;
+ else if (vi->is_heap_var)
+ pi->pt_global_mem = 1;
+ }
}
- pi->pt_anything = false;
+
+ if (pi->pt_anything)
+ return false;
+
if (!pi->pt_vars)
pi->pt_vars = BITMAP_GGC_ALLOC ();
+
set_uids_in_ptset (pi->pt_vars, vi->solution);
+
+ if (bitmap_empty_p (pi->pt_vars))
+ pi->pt_vars = NULL;
+
return true;
}
}
+
return false;
}
@@ -3053,7 +3304,7 @@ dump_sa_points_to_info (FILE *outfile)
{
unsigned int i;
- fprintf (outfile, "\nPoints-to information\n\n");
+ fprintf (outfile, "\nPoints-to sets\n\n");
if (dump_flags & TDF_STATS)
{
@@ -3124,6 +3375,7 @@ init_base_vars (void)
rhs.var = anything_id;
rhs.offset = 0;
var_anything->address_taken = true;
+
/* This specifically does not use process_constraint because
process_constraint ignores all anything = anything constraints, since all
but this one are redundant. */
@@ -3177,17 +3429,44 @@ init_base_vars (void)
rhs.var = anything_id;
rhs.offset = 0;
process_constraint (new_constraint (lhs, rhs));
+
+ /* Create the ANYOFFSET variable, used to represent an arbitrary offset
+ inside an object. This is similar to ANYTHING, but less drastic.
+ It means that the pointer can point anywhere inside an object,
+ but not outside of it. */
+ anyoffset_tree = create_tmp_var_raw (void_type_node, "ANYOFFSET");
+ anyoffset_id = 4;
+ var_anyoffset = new_var_info (anyoffset_tree, anyoffset_id, "ANYOFFSET",
+ anyoffset_id);
+ insert_id_for_tree (anyoffset_tree, anyoffset_id);
+ var_anyoffset->is_artificial_var = 1;
+ var_anyoffset->size = ~0;
+ var_anyoffset->offset = 0;
+ var_anyoffset->next = NULL;
+ var_anyoffset->fullsize = ~0;
+ VEC_safe_push (varinfo_t, gc, varmap, var_anyoffset);
+
+ /* ANYOFFSET points to ANYOFFSET. */
+ lhs.type = SCALAR;
+ lhs.var = anyoffset_id;
+ lhs.offset = 0;
+ rhs.type = ADDRESSOF;
+ rhs.var = anyoffset_id;
+ rhs.offset = 0;
+ process_constraint (new_constraint (lhs, rhs));
}
/* Create points-to sets for the current function. See the comments
at the start of the file for an algorithmic overview. */
-static void
-create_alias_vars (void)
+void
+compute_points_to_sets (struct alias_info *ai)
{
basic_block bb;
-
+
+ timevar_push (TV_TREE_PTA);
+
init_alias_vars ();
constraint_pool = create_alloc_pool ("Constraint pool",
@@ -3201,7 +3480,7 @@ create_alias_vars (void)
varmap = VEC_alloc (varinfo_t, gc, 8);
id_for_tree = htab_create (10, tree_id_hash, tree_id_eq, free);
memset (&stats, 0, sizeof (stats));
-
+
init_base_vars ();
intra_create_variable_infos ();
@@ -3214,28 +3493,29 @@ create_alias_vars (void)
for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
if (is_gimple_reg (PHI_RESULT (phi)))
- find_func_aliases (phi);
+ find_func_aliases (phi, ai);
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- find_func_aliases (bsi_stmt (bsi));
+ find_func_aliases (bsi_stmt (bsi), ai);
}
build_constraint_graph ();
if (dump_file)
{
- fprintf (dump_file, "Constraints:\n");
+ fprintf (dump_file, "Points-to analysis\n\nConstraints:\n\n");
dump_constraints (dump_file);
}
if (dump_file)
- fprintf (dump_file, "Collapsing static cycles and doing variable substitution:\n");
+ fprintf (dump_file, "\nCollapsing static cycles and doing variable "
+ "substitution:\n");
find_and_collapse_graph_cycles (graph, false);
perform_var_substitution (graph);
if (dump_file)
- fprintf (dump_file, "Solving graph:\n");
+ fprintf (dump_file, "\nSolving graph:\n");
solve_graph (graph);
@@ -3243,30 +3523,15 @@ create_alias_vars (void)
dump_sa_points_to_info (dump_file);
have_alias_info = true;
+
+ timevar_pop (TV_TREE_PTA);
}
-struct tree_opt_pass pass_build_pta =
-{
- "pta", /* name */
- NULL, /* gate */
- create_alias_vars, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_PTA, /* tv_id */
- PROP_cfg, /* properties_required */
- PROP_pta, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 0 /* letter */
-};
-
/* Delete created points-to sets. */
-static void
-delete_alias_vars (void)
+void
+delete_points_to_sets (void)
{
htab_delete (id_for_tree);
free_alloc_pool (variable_info_pool);
@@ -3275,20 +3540,3 @@ delete_alias_vars (void)
bitmap_obstack_release (&ptabitmap_obstack);
have_alias_info = false;
}
-
-struct tree_opt_pass pass_del_pta =
-{
- NULL, /* name */
- NULL, /* gate */
- delete_alias_vars, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_PTA, /* tv_id */
- PROP_pta, /* properties_required */
- 0, /* properties_provided */
- PROP_pta, /* properties_destroyed */
- 0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 0 /* letter */
-};
Index: tree-ssa-structalias.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-structalias.h,v
retrieving revision 2.3
diff -d -u -p -r2.3 tree-ssa-structalias.h
--- tree-ssa-structalias.h 25 Jun 2005 02:01:47 -0000 2.3
+++ tree-ssa-structalias.h 8 Jul 2005 20:31:11 -0000
@@ -25,6 +25,66 @@ Foundation, Inc., 51 Franklin Street, Fi
struct constraint;
typedef struct constraint *constraint_t;
+/* Alias information used by compute_may_aliases and its helpers. */
+struct alias_info
+{
+ /* SSA names visited while collecting points-to information. If bit I
+ is set, it means that SSA variable with version I has already been
+ visited. */
+ sbitmap ssa_names_visited;
+
+ /* Array of SSA_NAME pointers processed by the points-to collector. */
+ varray_type processed_ptrs;
+
+ /* ADDRESSABLE_VARS contains all the global variables and locals that
+ have had their address taken. */
+ struct alias_map_d **addressable_vars;
+ size_t num_addressable_vars;
+
+ /* POINTERS contains all the _DECL pointers with unique memory tags
+ that have been referenced in the program. */
+ struct alias_map_d **pointers;
+ size_t num_pointers;
+
+ /* Number of function calls found in the program. */
+ size_t num_calls_found;
+
+ /* Number of const/pure function calls found in the program. */
+ size_t num_pure_const_calls_found;
+
+ /* Array of counters to keep track of how many times each pointer has
+ been dereferenced in the program. This is used by the alias grouping
+ heuristic in compute_flow_insensitive_aliasing. */
+ varray_type num_references;
+
+ /* Total number of virtual operands that will be needed to represent
+ all the aliases of all the pointers found in the program. */
+ long total_alias_vops;
+
+ /* Variables that have been written to. */
+ bitmap written_vars;
+
+ /* Pointers that have been used in an indirect store operation. */
+ bitmap dereferenced_ptrs_store;
+
+ /* Pointers that have been used in an indirect load operation. */
+ bitmap dereferenced_ptrs_load;
+};
+
+/* Keep track of how many times each pointer has been dereferenced in
+ the program using the aux variable. This is used by the alias
+ grouping heuristic in compute_flow_insensitive_aliasing. */
+#define NUM_REFERENCES(ANN) ((size_t)((ANN)->common.aux))
+#define NUM_REFERENCES_CLEAR(ANN) ((ANN)->common.aux) = 0
+#define NUM_REFERENCES_INC(ANN) (ANN)->common.aux = (void*) (((size_t)((ANN)->common.aux)) + 1)
+#define NUM_REFERENCES_SET(ANN, VAL) (ANN)->common.aux = (void*) ((void *)(VAL))
+
+/* In tree-ssa-alias.c. */
+bool is_escape_site (tree, struct alias_info *);
+
+/* In tree-ssa-structalias.c. */
+extern void compute_points_to_sets (struct alias_info *);
+extern void delete_points_to_sets (void);
extern void dump_constraint (FILE *, constraint_t);
extern void dump_constraints (FILE *);
extern void debug_constraint (constraint_t);
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.103
diff -d -u -p -r2.103 tree-ssa.c
--- tree-ssa.c 3 Jul 2005 21:08:01 -0000 2.103
+++ tree-ssa.c 8 Jul 2005 20:31:11 -0000
@@ -467,10 +467,9 @@ verify_flow_sensitive_alias_info (void)
}
if (pi->name_mem_tag
- && !pi->pt_malloc
&& (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
{
- error ("pointers with a memory tag, should have points-to sets or point to malloc");
+ error ("pointers with a memory tag, should have points-to sets");
goto err;
}
Index: testsuite/gcc.dg/tree-ssa/pta-fp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c,v
retrieving revision 1.1
diff -d -u -p -r1.1 pta-fp.c
--- testsuite/gcc.dg/tree-ssa/pta-fp.c 5 Jul 2005 15:31:17 -0000 1.1
+++ testsuite/gcc.dg/tree-ssa/pta-fp.c 8 Jul 2005 20:31:13 -0000
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-pta1" } */
+/* { dg-options "-O2 -fdump-tree-alias1" } */
extern double cos (double);
extern double sin (double);
double f(double a)
@@ -22,5 +22,5 @@ double f(double a)
}
/* The points-to set of the final function pointer should be "sin cos" */
-/* { dg-final { scan-tree-dump-times "sin cos" 1 "pta1"} } */
-/* { dg-final { cleanup-tree-dump "pta1" } } */
+/* { dg-final { scan-tree-dump-times "sin cos" 1 "alias1"} } */
+/* { dg-final { cleanup-tree-dump "alias1" } } */
More information about the Gcc-patches
mailing list