This is the mail archive of the gcc-patches@gcc.gnu.org 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]: Remove weighted edges in points-to solver


As part of my patches to speed up and reduce memory usage of the
points-to analyzer, this patch removes the need for weighted edges,
which was probably the only ugly part of this points-to solver, and
cost us a lot of memory for almost no gain.

In some theoretical world, it's better to have weighted edges than it
is to reprocess weighted constraints over and over (it trades edges
for iterations of the solver).  In the real world, it's better to be
able to represent all your edges using one bit a piece, and reprocess
the constraints (especially since when we added 4 million weighted
edges, at 8-32 bytes a piece, instead of 1 bit a piece, we spent more
time futzing with them than we would have just reprocessing the
constraints)

:)

Bootstrapped and regtested on i686-pc-darwin

Committed to mainline.

2006-11-22 Daniel Berlin <dberlin@dberlin.org>

	* tree-ssa-structalias.c: Remove edge weights in favor of just
	processing them as complex constraints.
	(struct constraint_graph): Remove weighted succs and preds. Rename
	nonweighted succs and preds.
	(constraint_edge): Removed.
	(constraint_edge_t): Ditto.
	(constraint_edge_pool): Ditto.
	(new_constraint_edge): Ditto.
	(constraint_edge_equal): Ditto.
	(constraint_edge_less): Ditto.
	(constraint_edge_vec_find): Ditto.
	(erase_self_graph_edge): Ditto.
	(add_graph_edge): Removed.
	(get_graph_weights): Ditto.
	(allocate_graph_weights): Ditto.	(
	(valid_weighted_graph_edge): Ditto
	(bitmap_other_than_zero_bit_set): Ditto.
	(int_add_graph_edge): Renamed to add_graph_edge.
	(clear_edges_for_node): Remove support for weighted edges.
	(merge_graph_nodes): Ditto.
	(valid_graph_edge): Ditto.
	(build_constraint_graph): Ditto.
	(scc_visit): Ditto.
	(collapse_nodes): Ditto.
	(process_unification_queue): Ditto.
	(topo_visit): Ditto.
	(do_ds_constraint): Ditto.
	(perform_var_subsitution): Ditto.
	(solve_graph): Ditto.
	(init_alias_vars): Ditto.
	(delete_points_to_sets): Ditto.
	(do_complex_constraint): Support offsetted copies here.

Attachment: edgeweighting.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]