This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH]: alias slowdown patch

Here ya go. This should fix your time and memory issues.

For cplusplus_grammar.ii i get:

tree PTA              :   1.76 ( 3%) usr   0.09 ( 1%) sys   2.03 (
2%) wall    3591 kB ( 1%) ggc
tree alias analysis   :   7.93 (12%) usr   1.26 ( 9%) sys   9.95
(11%) wall    3986 kB ( 1%) ggc

Note that the remaining "tree alias analysis" time is actually copying the bitmap sets from PTA to SSA_NAME_PTR_INFO, 5 times, for 100000 variables. We then take these bitmaps from SSA_NAME_PTR_INFO, and explicitly enumerate them into vectors in the form of add_may_alias.

This is a bit dumb.

The second worst part is that we know only about 30000 of them have
different points-to sets, but there is no way to explain this to what
is asking us.

While fixing the timing issue, i discovered serious memory usage
issues that occur if we try to compute the real points-to sets instead
of punting (which is what i've really done with this patch).
In fact, I got it to compute the complete points-to sets in 3 seconds,
using 50 meg of memory.
However, we then take these sets, and explicitly enumerate them into
these two places I mentioned above, and waste 800 meg of memory
keeping them around.

So for now, i have punted and we don't compute the points-to set for
global variables anymore to avoid this, but this is really a kludge
(if you were to say, move the large table into the function, you would
hit the same problem)

I want to move us to something other than sparse bitmaps for points-to
(BDD's), because they are about 100x more memory efficient (it is like
sharing all the same bits of the bitmaps for all the points-to sets at
once), but real overall memory savings will mean we are going to have
to stop explicitly enumerating *all* of our points-to sets into
bitmaps at once during alias analysis like we do now.
It is perfectly fine and fast to enumerate the set for one variable at
a time from the BDD (it's cached), as long as we stop trying to keep
the bitmaps around.

As our points-to sets get bigger (which is inveitable if we have to
handle codes like this, and move to interprocedural analysis), this is
only going to get worse and worse.

I can make it fast, but without changing the way we postprocess these
sets, i can't make it memory efficient.


(I will commit this patch to 4.2 branch and mainline once it finishes
bootstrap/regtesting. It already passed bootstrap once, though that
version had a few should-be-cosmetic differences than this one, just
to CYA :P )


2006-11-21 Daniel Berlin <>

	* tree-ssa-structalias.c: Update comments.
	(var_escaped_vars): Remove.
	(escaped_vars_tree): Remove.
	(escaped_vars_id): Remove.
	(constraint_expr_type): Add INCLUDES.
	(graph_size): Removed.
	(dump_constraint): Support INCLUDES.
	(build_constraint_graph): Ditto.
	(collapse_nodes): Add merge_solutions argument.
	Don't merge attributes.
	(process_unification_queue): Just use collapse_nodes.
	(perform_var_substitution): Update call to collapse_nodes.
	(get_constraint_exp_from_ssa_var): Use INCLUDES.
	(process_constraint): Fix non-field sensitive handling
	Handle includes.
	(get_constraint_for): Use INCLUDES.
	(make_constraint_from_escaped): Use nonlocal_vars_id.
	(make_constraint_to_escaped): Removed.
	(find_global_initializers): Removed.
	(create_variable_info_for): Do not make constraints to escaped
	vars anymore.
	(dump_solution_for_var): Don't print out the equivalent points-to
	sets, just use the name of the variable it shares it with.
	(intra_create_variable_infos): Use INCLUDES.
	Move initialization of nonlocal variable to init_base_vars.
	(init_base_vars): Init nonlocal variable here.
	Remove escaped_vars initialization.
	(find_escape_constraints): Removed.
	(delete_points_to_sets): Remove dead code.

Attachment: includes.diff.txt
Description: Text document

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]