From 499be8ef6be39e70ee2de807ac4ddd81b5827c0a Mon Sep 17 00:00:00 2001 From: dberlin Date: Thu, 19 Oct 2006 23:05:53 +0000 Subject: [PATCH] 2006-10-19 Daniel Berlin Fix PR tree-optimization/28778 Fix PR tree-optimization/29156 Fix PR tree-optimization/29415 * tree.h (DECL_PTA_ARTIFICIAL): New macro. (tree_decl_with_vis): Add artificial_pta_var flag. * tree-ssa-alias.c (is_escape_site): Remove alias info argument, pushed into callers. * tree-ssa-structalias.c (nonlocal_for_type): New variable. (nonlocal_all): Ditto. (struct variable_info): Add directly_dereferenced member. (var_escaped_vars): New variable. (escaped_vars_tree): Ditto. (escaped_vars_id): Ditto. (nonlocal_vars_id): Ditto. (new_var_info): Set directly_dereferenced. (graph_size): New variable (build_constraint_graph): Use graph_size. (solve_graph): Don't process constraints that cannot change the solution, don't try to propagate an empty solution to our successors. (process_constraint): Set directly_dereferenced. (could_have_pointers): New function. (get_constraint_for_component_ref): Don't process STRING_CST. (nonlocal_lookup): New function. (nonlocal_insert): Ditto. (create_nonlocal_var): Ditto. (get_nonlocal_id_for_type): Ditto. (get_constraint_for): Allow results vector to be empty in the case of string constants. Handle results of calls properly. (update_alias_info): Update alias info stats on number and type of calls. (find_func_aliases): Use could_have_pointers. (make_constraint_from_escaped): Renamed from make_constraint_to_anything, and changed to make constraints from escape variable. (make_constraint_to_escaped): New function. (find_global_initializers): Ditto. (create_variable_info_for): Make constraint from escaped to any global variable, and from any global variable to the set of escaped vars. (intra_create_variable_infos): Deal with escaped instead of pointing to anything. (set_uids_in_ptset): Do type pruning on directly dereferenced variables. (find_what_p_points_to): Adjust call to set_uids_with_ptset. (init_base_vars): Fix comment, and initialize escaped_vars. (need_to_solve): Removed. (find_escape_constraints): New function. (expand_nonlocal_solutions): Ditto. (compute_points_to_sets): Call find_escape_constraints and expand_nonlocal_solutions. (delete_points_to_sets): Don't fall off the end of the graph. (init_alias_heapvars): Initialize nonlocal_for_type and nonlocal_all. (delete_alias_heapvars): Free nonlocal_for_type and null out nonlocal_all. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@117891 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 60 ++ gcc/testsuite/gcc.c-torture/execute/pr28778.c | 33 ++ gcc/testsuite/gcc.c-torture/execute/pr29156.c | 32 ++ gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c | 2 +- gcc/tree-ssa-alias.c | 11 +- gcc/tree-ssa-operands.c | 3 + gcc/tree-ssa-structalias.c | 773 +++++++++++++++++++++----- gcc/tree-ssa-structalias.h | 2 +- gcc/tree.h | 7 +- 9 files changed, 763 insertions(+), 160 deletions(-) create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr28778.c create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr29156.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7f0267afe02..835baa1e262 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,63 @@ +2006-10-19 Daniel Berlin + + Fix PR tree-optimization/28778 + Fix PR tree-optimization/29156 + Fix PR tree-optimization/29415 + * tree.h (DECL_PTA_ARTIFICIAL): New macro. + (tree_decl_with_vis): Add artificial_pta_var flag. + * tree-ssa-alias.c (is_escape_site): Remove alias info argument, + pushed into callers. + * tree-ssa-structalias.c (nonlocal_for_type): New variable. + (nonlocal_all): Ditto. + (struct variable_info): Add directly_dereferenced member. + (var_escaped_vars): New variable. + (escaped_vars_tree): Ditto. + (escaped_vars_id): Ditto. + (nonlocal_vars_id): Ditto. + (new_var_info): Set directly_dereferenced. + (graph_size): New variable + (build_constraint_graph): Use graph_size. + (solve_graph): Don't process constraints that cannot change the + solution, don't try to propagate an empty solution to our + successors. + (process_constraint): Set directly_dereferenced. + (could_have_pointers): New function. + (get_constraint_for_component_ref): Don't process STRING_CST. + (nonlocal_lookup): New function. + (nonlocal_insert): Ditto. + (create_nonlocal_var): Ditto. + (get_nonlocal_id_for_type): Ditto. + (get_constraint_for): Allow results vector to be empty in the case + of string constants. + Handle results of calls properly. + (update_alias_info): Update alias info stats on number and type of + calls. + (find_func_aliases): Use could_have_pointers. + (make_constraint_from_escaped): Renamed from + make_constraint_to_anything, and changed to make constraints from + escape variable. + (make_constraint_to_escaped): New function. + (find_global_initializers): Ditto. + (create_variable_info_for): Make constraint from escaped to any + global variable, and from any global variable to the set of + escaped vars. + (intra_create_variable_infos): Deal with escaped instead of + pointing to anything. + (set_uids_in_ptset): Do type pruning on directly dereferenced + variables. + (find_what_p_points_to): Adjust call to set_uids_with_ptset. + (init_base_vars): Fix comment, and initialize escaped_vars. + (need_to_solve): Removed. + (find_escape_constraints): New function. + (expand_nonlocal_solutions): Ditto. + (compute_points_to_sets): Call find_escape_constraints and + expand_nonlocal_solutions. + (delete_points_to_sets): Don't fall off the end of the graph. + (init_alias_heapvars): Initialize nonlocal_for_type and + nonlocal_all. + (delete_alias_heapvars): Free nonlocal_for_type and null out + nonlocal_all. + 2006-10-19 Eric Botcazou * fold-const.c (add_double): Rename to add_double_with_sign. diff --git a/gcc/testsuite/gcc.c-torture/execute/pr28778.c b/gcc/testsuite/gcc.c-torture/execute/pr28778.c new file mode 100644 index 00000000000..f96a66cd30b --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr28778.c @@ -0,0 +1,33 @@ +extern void abort(void); +typedef long GLint; +void aglChoosePixelFormat (const GLint *); + +void +find (const int *alistp) +{ + const int *blist; + int list[32]; + if (alistp) + blist = alistp; + else + { + list[3] = 42; + blist = list; + } + aglChoosePixelFormat ((GLint *) blist); +} + +void +aglChoosePixelFormat (const GLint * a) +{ + int *b = (int *) a; + if (b[3] != 42) + abort (); +} + +int +main (void) +{ + find (0); + return 0; +} diff --git a/gcc/testsuite/gcc.c-torture/execute/pr29156.c b/gcc/testsuite/gcc.c-torture/execute/pr29156.c new file mode 100644 index 00000000000..20f5f9979c5 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr29156.c @@ -0,0 +1,32 @@ +extern void abort(void); +struct test1 +{ + int a; + int b; +}; +struct test2 +{ + float d; + struct test1 sub; +}; + +int global; + +int bla(struct test1 *xa, struct test2 *xb) +{ + global = 1; + xb->sub.a = 1; + xa->a = 8; + return xb->sub.a; +} + +int main(void) +{ + struct test2 pom; + + if (bla (&pom.sub, &pom) != 8) + abort (); + + return 0; +} + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c b/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c index 4cebcbb670a..4a64d2490f4 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pta-fp.c @@ -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 "alias1"} } */ +/* { dg-final { scan-tree-dump-times "{ sin cos }" 1 "alias1"} } */ /* { dg-final { cleanup-tree-dump "alias1" } } */ diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index d3c5700c873..cf317de81fd 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -2103,24 +2103,17 @@ set_pt_anything (tree ptr) 3- STMT is an assignment to a non-local variable, or 4- STMT is a return statement. - AI points to the alias information collected so far. - Return the type of escape site found, if we found one, or NO_ESCAPE if none. */ enum escape_type -is_escape_site (tree stmt, struct alias_info *ai) +is_escape_site (tree stmt) { tree call = get_call_expr_in (stmt); if (call != NULL_TREE) { - ai->num_calls_found++; - if (!TREE_SIDE_EFFECTS (call)) - { - ai->num_pure_const_calls_found++; - return ESCAPE_TO_PURE_CONST; - } + return ESCAPE_TO_PURE_CONST; return ESCAPE_TO_CALL; } diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index 0e931ca74a9..0efbe0f3ae2 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -1053,6 +1053,9 @@ access_can_touch_variable (tree ref, tree alias, HOST_WIDE_INT offset, if (alias == global_var) return true; + if (TREE_CODE (alias) == VAR_DECL && DECL_PTA_ARTIFICIAL (alias)) + return true; + /* If ALIAS is an SFT, it can't be touched if the offset and size of the access is not overlapping with the SFT offset and size. This is only true if we are accessing through a pointer diff --git a/gcc/tree-ssa-structalias.c b/gcc/tree-ssa-structalias.c index 9be67cadb03..b1f125a8679 100644 --- a/gcc/tree-ssa-structalias.c +++ b/gcc/tree-ssa-structalias.c @@ -162,7 +162,17 @@ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA worth the pain or slowdown. */ static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) - htab_t heapvar_for_stmt; +htab_t heapvar_for_stmt; + + +/* Represents nonlocals. */ +static GTY ((if_marked ("tree_map_marked_p"), param_is (struct tree_map))) +htab_t nonlocal_for_type; + +/* If strict aliasing is off, we only use one variable to represent + the nonlocal types. */ +static GTY (()) tree nonlocal_all; + static bool use_field_sensitive = true; static int in_ipa_mode = 0; static bitmap_obstack predbitmap_obstack; @@ -223,6 +233,12 @@ struct variable_info /* True if this variable is the target of a dereference. Needed for variable substitution. */ unsigned int indirect_target:1; + + /* True if the variable is directly the target of a dereference. + This is used to track which variables are *actually* dereferenced + so we can prune their points to listed. This is equivalent to the + indirect_target flag when no merging of variables happens. */ + unsigned int directly_dereferenced:1; /* True if this is a variable created by the constraint analysis, such as heap variables and constraints we had to break up. */ @@ -312,6 +328,15 @@ static varinfo_t var_integer; static tree integer_tree; static unsigned int integer_id; +/* Variable that represents escaped variables. This is used to give + incoming pointer variables a better set than ANYTHING. */ +static varinfo_t var_escaped_vars; +static tree escaped_vars_tree; +static unsigned int escaped_vars_id; + +/* Variable that represents non-local variables before we expand it to + one for each type. */ +static unsigned int nonlocal_vars_id; /* Lookup a heap var for FROM, and return it if we find one. */ @@ -342,7 +367,7 @@ heapvar_insert (tree from, tree to) h->to = to; loc = htab_find_slot_with_hash (heapvar_for_stmt, h, h->hash, INSERT); *(struct tree_map **) loc = h; -} +} /* Return a new variable info structure consisting for a variable named NAME, and using constraint graph node NODE. */ @@ -358,6 +383,7 @@ new_var_info (tree t, unsigned int id, const char *name, unsigned int node) ret->node = node; ret->address_taken = false; ret->indirect_target = false; + ret->directly_dereferenced = false; ret->is_artificial_var = false; ret->is_heap_var = false; ret->is_special_var = false; @@ -466,6 +492,7 @@ struct constraint_graph typedef struct constraint_graph *constraint_graph_t; static constraint_graph_t graph; +static int graph_size; /* Create a new constraint consisting of LHS and RHS expressions. */ @@ -1181,10 +1208,11 @@ build_constraint_graph (void) constraint_t c; graph = XNEW (struct constraint_graph); - graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, VEC_length (varinfo_t, varmap) + 1); - graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, VEC_length (varinfo_t, varmap) + 1); - graph->zero_weight_succs = XCNEWVEC (bitmap, VEC_length (varinfo_t, varmap) + 1); - graph->zero_weight_preds = XCNEWVEC (bitmap, VEC_length (varinfo_t, varmap) + 1); + graph_size = VEC_length (varinfo_t, varmap) + 1; + graph->succs = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size); + graph->preds = XCNEWVEC (VEC(constraint_edge_t,heap) *, graph_size); + graph->zero_weight_succs = XCNEWVEC (bitmap, graph_size); + graph->zero_weight_preds = XCNEWVEC (bitmap, graph_size); for (i = 0; VEC_iterate (constraint_t, constraints, i, c); i++) { @@ -2027,54 +2055,70 @@ solve_graph (constraint_graph_t graph) bitmap_iterator bi; VEC(constraint_t,heap) *complex = get_varinfo (i)->complex; VEC(constraint_edge_t,heap) *succs; + bool solution_empty; RESET_BIT (changed, i); changed_count--; - /* Process the complex constraints */ solution = get_varinfo (i)->solution; + solution_empty = bitmap_empty_p (solution); + + /* Process the complex constraints */ for (j = 0; VEC_iterate (constraint_t, complex, j, c); j++) - do_complex_constraint (graph, c, solution); + { + /* The only complex constraint that can change our + solution to non-empty, given an empty solution, + is a constraint where the lhs side is receiving + some set from elsewhere. */ + if (!solution_empty || c->lhs.type != DEREF) + do_complex_constraint (graph, c, solution); + } - /* Propagate solution to all successors. */ - succs = graph->succs[i]; - - EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i], 0, j, bi) + solution_empty = bitmap_empty_p (solution); + + if (!solution_empty) { - bitmap tmp = get_varinfo (j)->solution; - bool flag = false; - - flag = set_union_with_increment (tmp, solution, 0); + /* Propagate solution to all successors. */ + succs = graph->succs[i]; - if (flag) + EXECUTE_IF_IN_NONNULL_BITMAP (graph->zero_weight_succs[i], + 0, j, bi) { - get_varinfo (j)->solution = tmp; - if (!TEST_BIT (changed, j)) + bitmap tmp = get_varinfo (j)->solution; + bool flag = false; + + flag = set_union_with_increment (tmp, solution, 0); + + if (flag) { - SET_BIT (changed, j); - changed_count++; + get_varinfo (j)->solution = tmp; + if (!TEST_BIT (changed, j)) + { + SET_BIT (changed, j); + changed_count++; + } } } - } - for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++) - { - bitmap tmp = get_varinfo (e->dest)->solution; - bool flag = false; - unsigned int k; - bitmap weights = e->weights; - bitmap_iterator bi; + for (j = 0; VEC_iterate (constraint_edge_t, succs, j, e); j++) + { + bitmap tmp = get_varinfo (e->dest)->solution; + bool flag = false; + unsigned int k; + bitmap weights = e->weights; + bitmap_iterator bi; - gcc_assert (weights && !bitmap_empty_p (weights)); - EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi) - flag |= set_union_with_increment (tmp, solution, k); + gcc_assert (weights && !bitmap_empty_p (weights)); + EXECUTE_IF_SET_IN_BITMAP (weights, 0, k, bi) + flag |= set_union_with_increment (tmp, solution, k); - if (flag) - { - get_varinfo (e->dest)->solution = tmp; - if (!TEST_BIT (changed, e->dest)) + if (flag) { - SET_BIT (changed, e->dest); - changed_count++; + get_varinfo (e->dest)->solution = tmp; + if (!TEST_BIT (changed, e->dest)) + { + SET_BIT (changed, e->dest); + changed_count++; + } } } } @@ -2248,6 +2292,11 @@ process_constraint (constraint_t t) gcc_assert (rhs.var < VEC_length (varinfo_t, varmap)); gcc_assert (lhs.var < VEC_length (varinfo_t, varmap)); + if (lhs.type == DEREF) + get_varinfo (lhs.var)->directly_dereferenced = true; + if (rhs.type == DEREF) + get_varinfo (rhs.var)->directly_dereferenced = true; + /* ANYTHING == ANYTHING is pointless. */ if (lhs.var == anything_id && rhs.var == anything_id) return; @@ -2297,6 +2346,19 @@ process_constraint (constraint_t t) } } +/* Return true if T is a variable of a type that could contain + pointers. */ + +static bool +could_have_pointers (tree t) +{ + tree type = TREE_TYPE (t); + + if (POINTER_TYPE_P (type) || AGGREGATE_TYPE_P (type) + || TREE_CODE (type) == COMPLEX_TYPE) + return true; + return false; +} /* Return the position, in bits, of FIELD_DECL from the beginning of its structure. */ @@ -2364,6 +2426,12 @@ get_constraint_for_component_ref (tree t, VEC(ce_s, heap) **results) } t = get_ref_base_and_extent (t, &bitpos, &bitsize, &bitmaxsize); + + /* String constants's are readonly, so there is nothing to really do + here. */ + if (TREE_CODE (t) == STRING_CST) + return; + get_constraint_for (t, results); result = VEC_last (ce_s, *results); result->offset = bitpos; @@ -2448,6 +2516,105 @@ do_deref (VEC (ce_s, heap) **constraints) } } +/* Lookup a nonlocal variable for type FROM, and return it if we find + one. */ + +static tree +nonlocal_lookup (tree from) +{ + struct tree_map *h, in; + in.from = from; + + h = htab_find_with_hash (nonlocal_for_type, &in, + htab_hash_pointer (from)); + if (h) + return h->to; + return NULL_TREE; +} + +/* Insert a mapping FROM->TO in the nonlocal variable for type + hashtable. */ + +static void +nonlocal_insert (tree from, tree to) +{ + struct tree_map *h; + void **loc; + + h = ggc_alloc (sizeof (struct tree_map)); + h->hash = htab_hash_pointer (from); + h->from = from; + h->to = to; + loc = htab_find_slot_with_hash (nonlocal_for_type, h, h->hash, + INSERT); + *(struct tree_map **) loc = h; +} + +/* Create a nonlocal variable of TYPE to represent nonlocals we can + alias. */ + +static tree +create_nonlocal_var (tree type) +{ + tree nonlocal = create_tmp_var_raw (type, "NONLOCAL"); + + if (referenced_vars) + add_referenced_var (nonlocal); + + DECL_PTA_ARTIFICIAL (nonlocal) = 1; + DECL_EXTERNAL (nonlocal) = 1; + nonlocal_insert (type, nonlocal); + return nonlocal; +} + +/* Get or create a nonlocal variable for TYPE, and return its + variable info id. */ + +static unsigned int +get_nonlocal_id_for_type (tree type) +{ + tree nonlocal; + unsigned int nonlocal_id; + varinfo_t nonlocal_vi; + + /* For strict aliasing, we have one variable per type. For + non-strict aliasing, we only need one variable. */ + if (flag_strict_aliasing != 0) + { + nonlocal = nonlocal_lookup (type); + } + else + { + if (!nonlocal_all) + { + nonlocal = create_nonlocal_var (void_type_node); + nonlocal_all = nonlocal; + } + else + nonlocal = nonlocal_all; + } + + if (nonlocal && lookup_id_for_tree (nonlocal, &nonlocal_id)) + return nonlocal_id; + + if (!nonlocal) + { + gcc_assert (flag_strict_aliasing != 0); + nonlocal = create_nonlocal_var (type); + } + + /* Create variable info for the nonlocal var if it does not + exist. */ + nonlocal_id = create_variable_info_for (nonlocal, + get_name (nonlocal)); + nonlocal_vi = get_varinfo (nonlocal_id); + nonlocal_vi->is_artificial_var = 1; + nonlocal_vi->is_heap_var = 1; + nonlocal_vi->is_unknown_size_var = 1; + nonlocal_vi->directly_dereferenced = true; + + return nonlocal_id; +} /* Given a tree T, return the constraint expression for it. */ @@ -2507,6 +2674,9 @@ get_constraint_for (tree t, VEC (ce_s, heap) **results) varinfo_t origvar; struct constraint_expr tmp; + if (VEC_length (ce_s, *results) == 0) + return; + gcc_assert (VEC_length (ce_s, *results) == 1); origrhs = VEC_last (ce_s, *results); tmp = *origrhs; @@ -2549,7 +2719,6 @@ get_constraint_for (tree t, VEC (ce_s, heap) **results) } break; case CALL_EXPR: - /* XXX: In interprocedural mode, if we didn't have the body, we would need to do *each pointer argument = &ANYTHING added. */ @@ -2578,7 +2747,16 @@ get_constraint_for (tree t, VEC (ce_s, heap) **results) VEC_safe_push (ce_s, heap, *results, &temp); return; } - /* FALLTHRU */ + else + { + temp.var = escaped_vars_id; + temp.type = SCALAR; + temp.offset = 0; + VEC_safe_push (ce_s, heap, *results, &temp); + return; + } + break; + default: { temp.type = ADDRESSOF; @@ -2974,9 +3152,17 @@ update_alias_info (tree stmt, struct alias_info *ai) bitmap addr_taken; use_operand_p use_p; ssa_op_iter iter; - enum escape_type stmt_escape_type = is_escape_site (stmt, ai); + enum escape_type stmt_escape_type = is_escape_site (stmt); tree op; + if (stmt_escape_type == ESCAPE_TO_CALL + || stmt_escape_type == ESCAPE_TO_PURE_CONST) + { + ai->num_calls_found++; + if (stmt_escape_type == ESCAPE_TO_PURE_CONST) + ai->num_pure_const_calls_found++; + } + /* Mark all the variables whose address are taken by the statement. */ addr_taken = addresses_taken (stmt); if (addr_taken) @@ -3257,8 +3443,7 @@ find_func_aliases (tree origt) /* Only care about pointers and structures containing pointers. */ - if (POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (t))) - || TREE_CODE (TREE_TYPE (PHI_RESULT (t))) == COMPLEX_TYPE) + if (could_have_pointers (PHI_RESULT (t))) { int i; unsigned int j; @@ -3407,9 +3592,7 @@ find_func_aliases (tree origt) { /* 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)) - || TREE_CODE (TREE_TYPE (lhsop)) == COMPLEX_TYPE + if (could_have_pointers (lhsop) || TREE_CODE (rhsop) == CALL_EXPR) { get_constraint_for (lhsop, &lhsc); @@ -3712,8 +3895,9 @@ push_fields_onto_fieldstack (tree type, VEC(fieldoff_s,heap) **fieldstack, return count; } +/* Create a constraint from ESCAPED_VARS variable to VI. */ static void -make_constraint_to_anything (varinfo_t vi) +make_constraint_from_escaped (varinfo_t vi) { struct constraint_expr lhs, rhs; @@ -3721,9 +3905,24 @@ make_constraint_to_anything (varinfo_t vi) lhs.offset = 0; lhs.type = SCALAR; - rhs.var = anything_id; - rhs.offset =0 ; - rhs.type = ADDRESSOF; + rhs.var = escaped_vars_id; + rhs.offset = 0; + rhs.type = SCALAR; + process_constraint (new_constraint (lhs, rhs)); +} + +/* Create a constraint to the ESCAPED_VARS variable from constraint + expression RHS. */ + +static void +make_constraint_to_escaped (struct constraint_expr rhs) +{ + struct constraint_expr lhs; + + lhs.var = escaped_vars_id; + lhs.offset = 0; + lhs.type = SCALAR; + process_constraint (new_constraint (lhs, rhs)); } @@ -3876,6 +4075,55 @@ check_for_overlaps (VEC (fieldoff_s,heap) *fieldstack) } return false; } + +/* This function is called through walk_tree to walk global + initializers looking for constraints we need to add to the + constraint list. */ + +static tree +find_global_initializers (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, + void *viv) +{ + varinfo_t vi = (varinfo_t)viv; + tree t = *tp; + + switch (TREE_CODE (t)) + { + /* Dereferences and addressofs are the only important things + here, and i don't even remember if dereferences are legal + here in initializers. */ + case INDIRECT_REF: + case ADDR_EXPR: + { + struct constraint_expr *c; + size_t i; + + VEC(ce_s, heap) *rhsc = NULL; + get_constraint_for (t, &rhsc); + for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) + { + struct constraint_expr lhs; + + lhs.var = vi->id; + lhs.type = SCALAR; + lhs.offset = 0; + process_constraint (new_constraint (lhs, *c)); + } + + VEC_free (ce_s, heap, rhsc); + } + break; + case VAR_DECL: + /* We might not have walked this because we skip + DECL_EXTERNALs during the initial scan. */ + add_referenced_var (t); + break; + default: + break; + } + return NULL_TREE; +} + /* Create a varinfo structure for NAME and DECL, and add it to VARMAP. This will also create any varinfo structures necessary for fields of DECL. */ @@ -3933,7 +4181,27 @@ create_variable_info_for (tree decl, const char *name) insert_id_for_tree (vi->decl, index); VEC_safe_push (varinfo_t, heap, varmap, vi); if (is_global && (!flag_whole_program || !in_ipa_mode)) - make_constraint_to_anything (vi); + { + make_constraint_from_escaped (vi); + + /* If the variable can't be aliased, there is no point in + putting it in the set of nonlocal vars. */ + if (may_be_aliased (vi->decl)) + { + struct constraint_expr rhs; + rhs.var = index; + rhs.type = ADDRESSOF; + rhs.offset = 0; + make_constraint_to_escaped (rhs); + } + + if (TREE_CODE (decl) != FUNCTION_DECL && DECL_INITIAL (decl)) + { + walk_tree_without_duplicates (&DECL_INITIAL (decl), + find_global_initializers, + (void *)vi); + } + } stats.total_vars++; if (use_field_sensitive @@ -4013,8 +4281,21 @@ create_variable_info_for (tree decl, const char *name) insert_into_field_list (vi, newvi); VEC_safe_push (varinfo_t, heap, varmap, newvi); if (is_global && (!flag_whole_program || !in_ipa_mode)) - make_constraint_to_anything (newvi); - + { + /* If the variable can't be aliased, there is no point in + putting it in the set of nonlocal vars. */ + if (may_be_aliased (vi->decl)) + { + struct constraint_expr rhs; + + rhs.var = newindex; + rhs.type = ADDRESSOF; + rhs.offset = 0; + make_constraint_to_escaped (rhs); + } + make_constraint_from_escaped (newvi); + } + stats.total_vars++; } VEC_free (fieldoff_s, heap, fieldstack); @@ -4047,7 +4328,6 @@ debug_solution_for_var (unsigned int var) dump_solution_for_var (stdout, var); } - /* Create varinfo structures for all of the variables in the function for intraprocedural mode. */ @@ -4055,17 +4335,20 @@ static void intra_create_variable_infos (void) { tree t; - - /* For each incoming argument arg, ARG = &ANYTHING or a dummy variable if - flag_argument_noalias > 2. */ + struct constraint_expr lhs, rhs; + tree nonlocal; + varinfo_t nonlocal_vi; + /* For each incoming pointer argument arg, ARG = ESCAPED_VARS or a + dummy variable if flag_argument_noalias > 2. */ for (t = DECL_ARGUMENTS (current_function_decl); t; t = TREE_CHAIN (t)) { - struct constraint_expr lhs; varinfo_t p; + unsigned int arg_id; + + if (!could_have_pointers (t)) + continue; - lhs.offset = 0; - lhs.type = SCALAR; - lhs.var = create_variable_info_for (t, alias_get_name (t)); + arg_id = get_id_for_tree (t); /* With flag_argument_noalias greater than two means that the incoming argument cannot alias anything except for itself so create a HEAP @@ -4074,9 +4357,13 @@ intra_create_variable_infos (void) && flag_argument_noalias > 2) { varinfo_t vi; - struct constraint_expr rhs; tree heapvar = heapvar_lookup (t); unsigned int id; + + lhs.offset = 0; + lhs.type = SCALAR; + lhs.var = get_id_for_tree (t); + if (heapvar == NULL_TREE) { heapvar = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (t)), @@ -4086,8 +4373,7 @@ intra_create_variable_infos (void) add_referenced_var (heapvar); heapvar_insert (t, heapvar); } - id = create_variable_info_for (heapvar, - alias_get_name (heapvar)); + id = get_id_for_tree (heapvar); vi = get_varinfo (id); vi->is_artificial_var = 1; vi->is_heap_var = 1; @@ -4102,25 +4388,54 @@ intra_create_variable_infos (void) } } else - for (p = get_varinfo (lhs.var); p; p = p->next) - make_constraint_to_anything (p); - } + { + for (p = get_varinfo (arg_id); p; p = p->next) + make_constraint_from_escaped (p); + } + } + nonlocal = create_tmp_var_raw (void_type_node, "NONLOCAL_ALL"); + + DECL_EXTERNAL (nonlocal) = 1; + + /* Create variable info for the nonlocal var if it does not + exist. */ + nonlocal_vars_id = create_variable_info_for (nonlocal, + get_name (nonlocal)); + nonlocal_vi = get_varinfo (nonlocal_vars_id); + nonlocal_vi->is_artificial_var = 1; + nonlocal_vi->is_heap_var = 1; + nonlocal_vi->is_unknown_size_var = 1; + nonlocal_vi->directly_dereferenced = true; + + rhs.var = nonlocal_vars_id; + rhs.type = ADDRESSOF; + rhs.offset = 0; + + lhs.var = escaped_vars_id; + lhs.type = SCALAR; + lhs.offset = 0; + + process_constraint (new_constraint (lhs, rhs)); } /* Set bits in INTO corresponding to the variable uids in solution set - FROM */ + FROM, which came from variable PTR. + For variables that are actually dereferenced, we also use type + based alias analysis to prune the points-to sets. */ static void -set_uids_in_ptset (bitmap into, bitmap from) +set_uids_in_ptset (tree ptr, bitmap into, bitmap from) { unsigned int i; bitmap_iterator bi; subvar_t sv; + unsigned HOST_WIDE_INT ptr_alias_set = get_alias_set (TREE_TYPE (ptr)); EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi) { varinfo_t vi = get_varinfo (i); - + unsigned HOST_WIDE_INT var_alias_set; + /* The only artificial variables that are allowed in a may-alias set are heap variables. */ if (vi->is_artificial_var && !vi->is_heap_var) @@ -4137,18 +4452,32 @@ set_uids_in_ptset (bitmap into, bitmap from) || TREE_CODE (vi->decl) == PARM_DECL) { if (var_can_have_subvars (vi->decl) - && get_subvars_for_var (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); if (sft) - bitmap_set_bit (into, DECL_UID (sft)); + { + var_alias_set = get_alias_set (sft); + if (!vi->directly_dereferenced + || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) + 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)); + /* Otherwise, just add VI->DECL to the alias set. + Don't type prune artificial vars. */ + if (vi->is_artificial_var) + bitmap_set_bit (into, DECL_UID (vi->decl)); + else + { + var_alias_set = get_alias_set (vi->decl); + if (!vi->directly_dereferenced + || alias_sets_conflict_p (ptr_alias_set, var_alias_set)) + bitmap_set_bit (into, DECL_UID (vi->decl)); + } } } } @@ -4179,7 +4508,7 @@ find_what_p_points_to (tree p) if (lookup_id_for_tree (lookup_p, &id)) { varinfo_t vi = get_varinfo (id); - + if (vi->is_artificial_var) return false; @@ -4233,7 +4562,7 @@ find_what_p_points_to (tree p) if (!pi->pt_vars) pi->pt_vars = BITMAP_GGC_ALLOC (); - set_uids_in_ptset (pi->pt_vars, vi->solution); + set_uids_in_ptset (vi->decl, pi->pt_vars, vi->solution); if (bitmap_empty_p (pi->pt_vars)) pi->pt_vars = NULL; @@ -4375,8 +4704,8 @@ init_base_vars (void) integer_id = 3; VEC_safe_push (varinfo_t, heap, varmap, var_integer); - /* *INTEGER = ANYTHING, because we don't know where a dereference of a random - integer will point to. */ + /* INTEGER = ANYTHING, because we don't know where a dereference of + a random integer will point to. */ lhs.type = SCALAR; lhs.var = integer_id; lhs.offset = 0; @@ -4384,46 +4713,31 @@ init_base_vars (void) rhs.var = anything_id; rhs.offset = 0; process_constraint (new_constraint (lhs, rhs)); + + /* Create the ESCAPED_VARS variable used to represent variables that + escape this function. */ + escaped_vars_tree = create_tmp_var_raw (void_type_node, "ESCAPED_VARS"); + var_escaped_vars = new_var_info (escaped_vars_tree, 4, "ESCAPED_VARS", 4); + insert_id_for_tree (escaped_vars_tree, 4); + var_escaped_vars->is_artificial_var = 1; + var_escaped_vars->size = ~0; + var_escaped_vars->fullsize = ~0; + var_escaped_vars->offset = 0; + var_escaped_vars->next = NULL; + escaped_vars_id = 4; + VEC_safe_push (varinfo_t, heap, varmap, var_escaped_vars); + + /* ESCAPED_VARS = *ESCAPED_VARS */ + lhs.type = SCALAR; + lhs.var = escaped_vars_id; + lhs.offset = 0; + rhs.type = DEREF; + rhs.var = escaped_vars_id; + rhs.offset = 0; + process_constraint (new_constraint (lhs, rhs)); + } -/* Return true if we actually need to solve the constraint graph in order to - get our points-to sets. This is false when, for example, no addresses are - taken other than special vars, or all points-to sets with members already - contain the anything variable and there are no predecessors for other - sets. */ - -static bool -need_to_solve (void) -{ - int i; - varinfo_t v; - bool found_address_taken = false; - bool found_non_anything = false; - - for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++) - { - if (v->is_special_var) - continue; - - if (v->address_taken) - found_address_taken = true; - - if (v->solution - && !bitmap_empty_p (v->solution) - && !bitmap_bit_p (v->solution, anything_id)) - found_non_anything = true; - else if (bitmap_empty_p (v->solution) - && (VEC_length (constraint_edge_t, graph->preds[v->id]) != 0 - || (graph->zero_weight_preds[v->id] && !bitmap_empty_p (graph->zero_weight_preds[v->id])))) - found_non_anything = true; - - if (found_address_taken && found_non_anything) - return true; - } - - return false; -} - /* Initialize things necessary to perform PTA */ static void @@ -4447,7 +4761,160 @@ init_alias_vars (void) init_base_vars (); } +/* Given a statement STMT, generate necessary constraints to + escaped_vars for the escaping variables. */ + +static void +find_escape_constraints (tree stmt) +{ + enum escape_type stmt_escape_type = is_escape_site (stmt); + tree rhs; + VEC(ce_s, heap) *rhsc = NULL; + struct constraint_expr *c; + size_t i; + + if (stmt_escape_type == NO_ESCAPE) + return; + + if (TREE_CODE (stmt) == RETURN_EXPR) + { + /* Returns are either bare, with an embedded MODIFY_EXPR, or + just a plain old expression. */ + if (!TREE_OPERAND (stmt, 0)) + return; + if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR) + rhs = TREE_OPERAND (TREE_OPERAND (stmt, 0), 1); + else + rhs = TREE_OPERAND (stmt, 0); + + get_constraint_for (rhs, &rhsc); + for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) + make_constraint_to_escaped (*c); + VEC_free (ce_s, heap, rhsc); + return; + } + else if (TREE_CODE (stmt) == ASM_EXPR) + { + /* Whatever the inputs of the ASM are, escape. */ + tree arg; + + for (arg = ASM_INPUTS (stmt); arg; arg = TREE_CHAIN (arg)) + { + rhsc = NULL; + get_constraint_for (TREE_VALUE (arg), &rhsc); + for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) + make_constraint_to_escaped (*c); + VEC_free (ce_s, heap, rhsc); + } + return; + } + else if (TREE_CODE (stmt) == CALL_EXPR + || (TREE_CODE (stmt) == MODIFY_EXPR + && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)) + { + /* Calls cause all of the arguments passed in to escape. */ + tree arg; + + if (TREE_CODE (stmt) == MODIFY_EXPR) + stmt = TREE_OPERAND (stmt, 1); + for (arg = TREE_OPERAND (stmt, 1); arg; arg = TREE_CHAIN (arg)) + { + if (POINTER_TYPE_P (TREE_TYPE (TREE_VALUE (arg)))) + { + rhsc = NULL; + get_constraint_for (TREE_VALUE (arg), &rhsc); + for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) + make_constraint_to_escaped (*c); + VEC_free (ce_s, heap, rhsc); + } + } + return; + } + else + { + gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); + } + + gcc_assert (stmt_escape_type == ESCAPE_BAD_CAST + || stmt_escape_type == ESCAPE_STORED_IN_GLOBAL + || stmt_escape_type == ESCAPE_UNKNOWN); + rhs = TREE_OPERAND (stmt, 1); + + /* Look through casts for the real escaping variable. + Constants don't really escape, so ignore them. + Otherwise, whatever escapes must be on our RHS. */ + if (TREE_CODE (rhs) == NOP_EXPR + || TREE_CODE (rhs) == CONVERT_EXPR + || TREE_CODE (rhs) == NON_LVALUE_EXPR) + { + get_constraint_for (TREE_OPERAND (rhs, 0), &rhsc); + } + else if (CONSTANT_CLASS_P (rhs)) + return; + else + { + get_constraint_for (rhs, &rhsc); + } + for (i = 0; VEC_iterate (ce_s, rhsc, i, c); i++) + make_constraint_to_escaped (*c); + VEC_free (ce_s, heap, rhsc); +} + +/* Expand the solutions that have nonlocal_id in them to include one + variable for each type that is pointed to by nonlocal and + dereferenced. */ + +static void +expand_nonlocal_solutions (void) +{ + int i; + varinfo_t v; + bitmap new_nonlocal_solution = BITMAP_ALLOC (&ptabitmap_obstack); + /* We could do this faster by only checking non-collapsed nodes, + unless the node was collapsed to one we would normally ignore in the + rest of the loop. Logic already seems complicated enough, and + it wasn't a measurable speedup on any testcases i had. */ + for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++) + { + /* Where the solution for our variable is, since it may have + been collapsed to another varinfo. */ + varinfo_t solv = v; + + if (v->is_special_var + || v->id == nonlocal_vars_id + || v->id == escaped_vars_id + || !POINTER_TYPE_P (TREE_TYPE (v->decl))) + continue; + + if (v->node != v->id) + solv = get_varinfo (v->node); + if (bitmap_bit_p (solv->solution, nonlocal_vars_id)) + { + unsigned int new_nonlocal_id; + tree pttype = TREE_TYPE (TREE_TYPE (v->decl)); + + new_nonlocal_id = get_nonlocal_id_for_type (pttype); + bitmap_set_bit (new_nonlocal_solution, new_nonlocal_id); + } + } + + if (!bitmap_empty_p (new_nonlocal_solution)) + { + + for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++) + { + if (v->node != v->id) + continue; + if (bitmap_bit_p (v->solution, nonlocal_vars_id)) + { + bitmap_clear_bit (v->solution, nonlocal_vars_id); + bitmap_ior_into (v->solution, new_nonlocal_solution); + } + } + } +} + /* Create points-to sets for the current function. See the comments at the start of the file for an algorithmic overview. */ @@ -4484,11 +4951,13 @@ compute_points_to_sets (struct alias_info *ai) for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) { tree stmt = bsi_stmt (bsi); + find_func_aliases (stmt); - /* Update various related attributes like escaped - addresses, pointer dereferences for loads and stores. - This is used when creating name tags and alias - sets. */ + find_escape_constraints (stmt); + /* 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 (stmt, ai); } } @@ -4501,21 +4970,20 @@ compute_points_to_sets (struct alias_info *ai) dump_constraints (dump_file); } - if (1 || need_to_solve ()) - { - if (dump_file) - fprintf (dump_file, - "\nCollapsing static cycles and doing variable " - "substitution:\n"); + if (dump_file) + fprintf (dump_file, + "\nCollapsing static cycles and doing variable " + "substitution:\n"); - find_and_collapse_graph_cycles (graph, false); - perform_var_substitution (graph); + find_and_collapse_graph_cycles (graph, false); + perform_var_substitution (graph); - if (dump_file) - fprintf (dump_file, "\nSolving graph:\n"); + if (dump_file) + fprintf (dump_file, "\nSolving graph:\n"); - solve_graph (graph); - } + solve_graph (graph); + + expand_nonlocal_solutions (); if (dump_file) dump_sa_points_to_info (dump_file); @@ -4533,7 +5001,7 @@ delete_points_to_sets (void) { varinfo_t v; int i; - + htab_delete (id_for_tree); bitmap_obstack_release (&ptabitmap_obstack); bitmap_obstack_release (&predbitmap_obstack); @@ -4541,6 +5009,10 @@ delete_points_to_sets (void) for (i = 0; VEC_iterate (varinfo_t, varmap, i, v); i++) { + /* Nonlocal vars may add more varinfos. */ + if (i >= graph_size) + break; + VEC_free (constraint_edge_t, heap, graph->succs[i]); VEC_free (constraint_edge_t, heap, graph->preds[i]); VEC_free (constraint_t, heap, v->complex); @@ -4590,7 +5062,7 @@ ipa_pta_execute (void) { varinfo_t fi = get_varinfo (varid); for (; fi; fi = fi->next) - make_constraint_to_anything (fi); + make_constraint_from_escaped (fi); } } } @@ -4644,21 +5116,20 @@ ipa_pta_execute (void) dump_constraints (dump_file); } - if (need_to_solve ()) - { - if (dump_file) - fprintf (dump_file, - "\nCollapsing static cycles and doing variable " - "substitution:\n"); + if (dump_file) + fprintf (dump_file, + "\nCollapsing static cycles and doing variable " + "substitution:\n"); - find_and_collapse_graph_cycles (graph, false); - perform_var_substitution (graph); + find_and_collapse_graph_cycles (graph, false); + perform_var_substitution (graph); - if (dump_file) - fprintf (dump_file, "\nSolving graph:\n"); + if (dump_file) + fprintf (dump_file, "\nSolving graph:\n"); - solve_graph (graph); - } + solve_graph (graph); + + expand_nonlocal_solutions (); if (dump_file) dump_sa_points_to_info (dump_file); @@ -4689,13 +5160,19 @@ struct tree_opt_pass pass_ipa_pta = void init_alias_heapvars (void) { - heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, NULL); + heapvar_for_stmt = htab_create_ggc (11, tree_map_hash, tree_map_eq, + NULL); + nonlocal_for_type = htab_create_ggc (11, tree_map_hash, tree_map_eq, + NULL); + nonlocal_all = NULL_TREE; } void delete_alias_heapvars (void) { - htab_delete (heapvar_for_stmt); + nonlocal_all = NULL_TREE; + htab_delete (heapvar_for_stmt); + htab_delete (nonlocal_for_type); } diff --git a/gcc/tree-ssa-structalias.h b/gcc/tree-ssa-structalias.h index 5283202e9f8..165e5c1b1ae 100644 --- a/gcc/tree-ssa-structalias.h +++ b/gcc/tree-ssa-structalias.h @@ -81,7 +81,7 @@ struct alias_info #define NUM_REFERENCES_SET(ANN, VAL) (ANN)->common.aux = (void*) ((void *)(VAL)) /* In tree-ssa-alias.c. */ -enum escape_type is_escape_site (tree, struct alias_info *); +enum escape_type is_escape_site (tree); /* In tree-ssa-structalias.c. */ extern void compute_points_to_sets (struct alias_info *); diff --git a/gcc/tree.h b/gcc/tree.h index e6a861ca24a..dddd3863248 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -2858,6 +2858,10 @@ extern void decl_restrict_base_insert (tree, tree); multiple translation units should be merged. */ #define DECL_ONE_ONLY(NODE) (DECL_WITH_VIS_CHECK (NODE)->decl_with_vis.one_only) +/* Internal to points-to analysis and operand scanning. Indicates + that this DECL is an artificial points-to variable. */ +#define DECL_PTA_ARTIFICIAL(NODE) (VAR_DECL_CHECK (NODE)->decl_with_vis.artificial_pta_var) + struct tree_decl_with_vis GTY(()) { struct tree_decl_with_rtl common; @@ -2875,6 +2879,7 @@ struct tree_decl_with_vis GTY(()) unsigned based_on_restrict_p : 1; /* Used by C++. Might become a generic decl flag. */ unsigned shadowed_for_var_p : 1; + unsigned artificial_pta_var : 1; /* Don't belong to VAR_DECL exclusively. */ unsigned in_system_header_flag : 1; @@ -2889,7 +2894,7 @@ struct tree_decl_with_vis GTY(()) /* Belongs to VAR_DECL exclusively. */ ENUM_BITFIELD(tls_model) tls_model : 3; - /* 11 unused bits. */ + /* 10 unused bits. */ }; /* In a VAR_DECL that's static, -- 2.11.4.GIT