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 GCC][13/13]Distribute loop with loop versioning under runtime alias check

This is the main patch rewriting loop distribution in order to handle hmmer.
It improves loop distribution by versioning loop under runtime alias check conditions.
As described in comments, the patch basically implements distribution in the following

     1) Seed partitions with specific type statements.  For now we support
	two types seed statements: statement defining variable used outside
	of loop; statement storing to memory.
     2) Build reduced dependence graph (RDG) for loop to be distributed.
	The vertices (RDG:V) model all statements in the loop and the edges
	(RDG:E) model flow and control dependencies between statements.
     3) Apart from RDG, compute data dependencies between memory references.
     4) Starting from seed statement, build up partition by adding depended
	statements according to RDG's dependence information.  Partition is
	classified as parallel type if it can be executed paralleled; or as
	sequential type if it can't.  Parallel type partition is further
	classified as different builtin kinds if it can be implemented as
	builtin function calls.
     5) Build partition dependence graph (PG) based on data dependencies.
	The vertices (PG:V) model all partitions and the edges (PG:E) model
	all data dependencies between every partitions pair.  In general,
	data dependence is either compilation time known or unknown.  In C
	family languages, there exists quite amount compilation time unknown
	dependencies because of possible alias relation of data references.
	We categorize PG's edge to two types: "true" edge that represents
	compilation time known data dependencies; "alias" edge for all other
	data dependencies.
     6) Traverse subgraph of PG as if all "alias" edges don't exist.  Merge
	partitions in each strong connected component (SCC) correspondingly.
	Build new PG for merged partitions.
     7) Traverse PG again and this time with both "true" and "alias" edges
	included.  We try to break SCCs by removing some edges.  Because
	SCCs by "true" edges are all fused in step 6), we can break SCCs
	by removing some "alias" edges.  It's NP-hard to choose optimal
	edge set, fortunately simple approximation is good enough for us
	given the small problem scale.
     8) Collect all data dependencies of the removed "alias" edges.  Create
	runtime alias checks for collected data dependencies.
     9) Version loop under the condition of runtime alias checks.  Given
	loop distribution generally introduces additional overhead, it is
	only useful if vectorization is achieved in distributed loop.  We
	version loop with internal function call IFN_LOOP_DIST_ALIAS.  If
	no distributed loop can be vectorized, we simply remove distributed
	loops and recover to the original one.

Also, there are some more to improve in the future (which isn't difficult I think):
     1) We only distribute innermost loops now.  This pass should handle loop
	nests in the future.
     2) We only fuse partitions in SCC now.  A better fusion algorithm is
	desired to minimize loop overhead, maximize parallelism and maximize

Bootstrap and test on x86_64 and AArch64.  Is it OK?

2017-06-07  Bin Cheng  <>

	* tree-loop-distribution.c: Add general explanantion on the pass.
	(pg_add_dependence_edges): New parameter.  handle alias data
	dependence specially and record it in the parameter if asked.
	(struct pg_vdata, pg_edata, pg_edge_callback_data): New structs.
	(init_partition_graph_vertices, add_partition_graph_edge): New.
	(pg_skip_alias_edge, free_partition_graph_edata_cb): New.
	(free_partition_graph_vdata, build_partition_graph): New.
	(sort_partitions_by_post_order, merge_dep_scc_partitions): New.
	(pg_collect_alias_ddrs, break_alias_scc_partitions): New.
	(data_ref_segment_size, latch_dominated_by_data_ref): New.
	(compute_alias_check_pairs, version_loop_by_alias_check): New.
	(version_for_distribution_p, finalize_partitions): New.
	(distribute_loop): Handle alias data dependence specially.  Factor
	out loop fustion code as functions.

Attachment: 0013-loop-distribution-20170607.txt
Description: 0013-loop-distribution-20170607.txt

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