Fix PR tree-optimization/28778, 29156, and 29415

["Daniel Berlin" <dberlin at dberlin dot org>]

This large patch fixes three P1 regressions, 28778, 29156, 29415.

The basic issue in all three is that previously, we had no way to
describe accesses to nonlocal memory.   When we had no addressable
variables, we generated no conflicting vuses, even if we were
dereferencing pointers or passing them to other functions.

As our aliasing has gotten better, it eventually got to the point
during 4.2 that we could eliminate all local aliases, and be left with
nothing to say things aliased.  It was still possible to construct
these cases with 4.x, it's just *much much* harder.
Sadly, there is no smaller, less risky, and correct fix i can think of
for this problem that will not cause either massive compile time
explosion, or massive performance loss (I tried some before making
this statement).

To fix these regressions, I changed points-to to compute results even
in the presence of escaping variables, by computing a conservatively
correct set of nonlocal-variables.

This actually makes points-to results used roughly 90-99% of the time
for aliasing, instead of 2-5% of the time, since there are no more
anything variables in most  points-to results (they are in fact, rare
now, but still possible).

However, in order to represent dereferences of non-local variables, we
in fact, need to create a set of non-local variables that they can
alias with.   We could simply create one, but this would force every
variable that escapes or touches escaping memory to conflict with each
other, even if TBAA would say they can't.

To work around this, we create one variable per type that accesses
non-local memory (we could do one per alias set instead with a little
work), and then use TBAA pruning in find_what_p_points_to eliminate
those nonlocal variables we can't really point-to because of TBAA
rules.
In order to make this correct, we only type-prune variables that are
actually dereferenced.

An interesting side-effect of this patch, is that most if not all of
the current clobbering and SMT code can be eliminated.
The only cases that should use SMT results anymore are the very rare
case of us pointing to anything (which can be fixed), and for passes
that don't copy flow-sensitive info.

I imagine removing these two pieces of code would be a significant
speedup, but as this patch is complex enough already, I have left this
to 4.3.

I stole a bit in decl_with_vis to note which variables are artificial
PTA generated vars, because timings done showed that on large
testcases, we took about a 10% compile time hit if i used a bitmap of
uids and tested it instead.  This is likely because the path that
would test this bitmap in tree-ssa-operands.c is pretty well used, and
the bitmap could get large.

Otherwise, Richard Guenther tells me there is a small runtime
performance hit from this patch (not surprising, since we were doing
illegal optimizations before), and that it fixes two currently failing
tests in DLV.

This test was bootstrapped and regtested on i686-darwin and x86-64-linux-gnu.

It will cause three loadpre failures, interestingly enough due to
*better* aliasing info .  This is a  shortcoming of the load value
numbering and redundancy identification currently used in PRE, and i'm
working on fixing it.

I left them failing for now, if we would rather have them xfailed,
that is fine too.


Committed to mainline
--Dan

2006-10-19  Daniel Berlin  <dberlin@dberlin.org>

	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.