| Message ID | VI1PR0802MB2176D6EF8010E74F69340CD1E7F70@VI1PR0802MB2176.eurprd08.prod.outlook.com |
|---|---|
| State | New |
| Headers | show |
Hi Bin, Thanks for posting the patch. I haven't looked in detail yet but have couple of quick questions. 1. Shouldn’t the run time alias check for versioning happen only when vectorisation is enabled? You seems to be using the IFN_LOOP_DIST_ALIAS when vectoring but seems to be versioning otherwise too. 2. As I understand, loop distribution will be mostly beneficial when enabling transformations succeeds. Like resulting loop being vectorized. I am wondering if we should only version when the loop’s control flow is simple that it can be vectorizable. I know that you are adding the internal function for this to some extend but for some cases we should be able to say while in loop distribution itself that the control flow will not result in loop being vectorized. Btw, did you run Spec2006 with this? Any notable changes ? Thanks, Kugan On 2 June 2017 at 21:51, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > This is the main patch of the change. It improves loop distribution by versioning loop under > runtime alias check conditions, as well as better partition fusion. As described in comments, > the patch basically implements distribution in the following steps: > > 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 dependences between statements. > 3) Apart from RDG, compute data dependences 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 parallelly; 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 dependences. > The vertices (PG:V) model all partitions and the edges (PG:E) model > all data dependences 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 > dependences because of possible alias relation of data references. > We categorize PG's edge to two types: "true" edge that represents > compilation time known data dependences; "alias" edge for all other > data dependences. > 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge > partitions in each strong connected commponent (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 dependences of the removed "alias" edges. Create > runtime alias checks for collected data dependences. > 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 shouldn't be difficult): > TODO: > 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 > > This patch also fixes couple of latent bugs in the original implementation. > > After this change, kernel loop in hmmer can be distributed and vectorized as a result. > This gives obvious performance improvement. There is still inefficient code generation > issue which I will try to fix in loop split. Apart from this, the next opportunity in hmmer > is to eliminate number of dead stores under proper alias information. > Bootstrap and test at O2/O3 on x86_64 and AArch64. is it OK? > > Thanks, > bin > 2017-05-31 Bin Cheng <bin.cheng@arm.com> > > * cfgloop.h (struct loop): New field ldist_alias_id. > * cfgloopmanip.c (lv_adjust_loop_entry_edge): Refine comment for > new internal function. > * internal-fn.c (expand_LOOP_DIST_ALIAS): New function. > * internal-fn.def (IFN_LOOP_DIST_ALIAS): New internal function. > * tree-loop-distribution.c: Add general explanantion on the pass. > Include header file. > (struct ddr_entry, struct ddr_entry_hasher): New structs. > (ddr_entry_hasher::hash, ddr_entry_hasher::equal): New functions. > (bb_top_order_index, bb_top_order_index_size): New static vars. > (bb_top_order_cmp): New function. > (stmts_from_loop): Get basic blocks in topological order. Don't > free data references. > (build_rdg): New parameter pointing to vector of data references. > Store data references in it. > (enum partition_type): New enum. > (enum partition_kind, struct partition): Add comments. New fields. > (partition_alloc, partition_free): Handle new fields of partition. > (enum fuse_type, fuse_message): New enum and varaible. > (partition_merge_into): New parameter. Update implementation wrto > new fields of partition. > (generate_loops_for_partition): Set ldist_alias_id information. > (record_ddr, get_ddr, possible_data_dep_cycle_p): New functions. > (build_rdg_partition_for_vertex): New parameter. Compute type info > for partition. > (classify_partition): New parameter. Only classify partition as > reduction if the reduction is not included by all partitions. > Retrieve cached ddr, rather than compute it on the fly. > (ref_base_address): Delete. > (similar_memory_accesses): Rename to ... > (share_memory_accesses): ... this. > (rdg_build_partitions): New parameter and update uses. > (pg_add_dependence_edges): New parameter. Store ddr in parameter > vector if it could be resolved by runtime alias check. > (rdg_compute_data_dependence): New function. > (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): Update uses. Break SCC and version loop > with runtime alias checks. > (pass_loop_distribution::execute): Compute topological order for > basic blocks. Update uses. > * tree-vectorizer.c (vect_loop_dist_alias_call): New. > (fold_loop_dist_alias_call): New. > (vectorize_loops): Fold IFN_LOOP_DIST_ALIAS call depending on > successful vectorization or not. > > gcc/testsuite/ChangeLog > 2017-05-31 Bin Cheng <bin.cheng@arm.com> > > * gcc.dg/tree-ssa/ldist-4.c: Adjust test string. > * gcc.dg/tree-ssa/ldist-12.c: Ditto. > * gcc.dg/tree-ssa/ldist-13.c: Ditto. > * gcc.dg/tree-ssa/ldist-14.c: Ditto.
On Mon, Jun 5, 2017 at 5:21 AM, Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> wrote: > Hi Bin, > > Thanks for posting the patch. I haven't looked in detail yet but have > couple of quick questions. > > 1. Shouldn’t the run time alias check for versioning happen only when > vectorisation is enabled? You seems to be using the > IFN_LOOP_DIST_ALIAS when vectoring but seems to be versioning > otherwise too. It's to keep behavior consistent when user explicitly specify the option at for example O2 optimization level. It shouldn't matter much since in most cases vectorizer is enabled along with distribution. One case it could be useful is in test cases, i.e, we can test distribution without depending on vectorization. > > 2. As I understand, loop distribution will be mostly beneficial when > enabling transformations succeeds. Like resulting loop being > vectorized. I am wondering if we should only version when the loop’s > control flow is simple that it can be vectorizable. I know that you > are adding the internal function for this to some extend but for some > cases we should be able to say while in loop distribution itself that > the control flow will not result in loop being vectorized. So far distribution is mainly for vectorization, though it could be beneficial to other parallelization optimization. OTOH, cost model on control flow graph only may not be enough, for example, we may still want to distribute case consisting of a vectorizable partition and a complicated CFG partition. One possible change is we may want to restrict the transformation to case with limited number partitions, which is more or less for compilation time concern. That being said, we don't have a cost model now. > > Btw, did you run Spec2006 with this? Any notable changes ? Hmmer. Thanks, bin > > Thanks, > Kugan > > > > > On 2 June 2017 at 21:51, Bin Cheng <Bin.Cheng@arm.com> wrote: >> Hi, >> This is the main patch of the change. It improves loop distribution by versioning loop under >> runtime alias check conditions, as well as better partition fusion. As described in comments, >> the patch basically implements distribution in the following steps: >> >> 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 dependences between statements. >> 3) Apart from RDG, compute data dependences 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 parallelly; 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 dependences. >> The vertices (PG:V) model all partitions and the edges (PG:E) model >> all data dependences 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 >> dependences because of possible alias relation of data references. >> We categorize PG's edge to two types: "true" edge that represents >> compilation time known data dependences; "alias" edge for all other >> data dependences. >> 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge >> partitions in each strong connected commponent (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 dependences of the removed "alias" edges. Create >> runtime alias checks for collected data dependences. >> 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 shouldn't be difficult): >> TODO: >> 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 >> >> This patch also fixes couple of latent bugs in the original implementation. >> >> After this change, kernel loop in hmmer can be distributed and vectorized as a result. >> This gives obvious performance improvement. There is still inefficient code generation >> issue which I will try to fix in loop split. Apart from this, the next opportunity in hmmer >> is to eliminate number of dead stores under proper alias information. >> Bootstrap and test at O2/O3 on x86_64 and AArch64. is it OK? >> >> Thanks, >> bin >> 2017-05-31 Bin Cheng <bin.cheng@arm.com> >> >> * cfgloop.h (struct loop): New field ldist_alias_id. >> * cfgloopmanip.c (lv_adjust_loop_entry_edge): Refine comment for >> new internal function. >> * internal-fn.c (expand_LOOP_DIST_ALIAS): New function. >> * internal-fn.def (IFN_LOOP_DIST_ALIAS): New internal function. >> * tree-loop-distribution.c: Add general explanantion on the pass. >> Include header file. >> (struct ddr_entry, struct ddr_entry_hasher): New structs. >> (ddr_entry_hasher::hash, ddr_entry_hasher::equal): New functions. >> (bb_top_order_index, bb_top_order_index_size): New static vars. >> (bb_top_order_cmp): New function. >> (stmts_from_loop): Get basic blocks in topological order. Don't >> free data references. >> (build_rdg): New parameter pointing to vector of data references. >> Store data references in it. >> (enum partition_type): New enum. >> (enum partition_kind, struct partition): Add comments. New fields. >> (partition_alloc, partition_free): Handle new fields of partition. >> (enum fuse_type, fuse_message): New enum and varaible. >> (partition_merge_into): New parameter. Update implementation wrto >> new fields of partition. >> (generate_loops_for_partition): Set ldist_alias_id information. >> (record_ddr, get_ddr, possible_data_dep_cycle_p): New functions. >> (build_rdg_partition_for_vertex): New parameter. Compute type info >> for partition. >> (classify_partition): New parameter. Only classify partition as >> reduction if the reduction is not included by all partitions. >> Retrieve cached ddr, rather than compute it on the fly. >> (ref_base_address): Delete. >> (similar_memory_accesses): Rename to ... >> (share_memory_accesses): ... this. >> (rdg_build_partitions): New parameter and update uses. >> (pg_add_dependence_edges): New parameter. Store ddr in parameter >> vector if it could be resolved by runtime alias check. >> (rdg_compute_data_dependence): New function. >> (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): Update uses. Break SCC and version loop >> with runtime alias checks. >> (pass_loop_distribution::execute): Compute topological order for >> basic blocks. Update uses. >> * tree-vectorizer.c (vect_loop_dist_alias_call): New. >> (fold_loop_dist_alias_call): New. >> (vectorize_loops): Fold IFN_LOOP_DIST_ALIAS call depending on >> successful vectorization or not. >> >> gcc/testsuite/ChangeLog >> 2017-05-31 Bin Cheng <bin.cheng@arm.com> >> >> * gcc.dg/tree-ssa/ldist-4.c: Adjust test string. >> * gcc.dg/tree-ssa/ldist-12.c: Ditto. >> * gcc.dg/tree-ssa/ldist-13.c: Ditto. >> * gcc.dg/tree-ssa/ldist-14.c: Ditto.
On Fri, Jun 2, 2017 at 1:51 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: > Hi, > This is the main patch of the change. It improves loop distribution by versioning loop under > runtime alias check conditions, as well as better partition fusion. As described in comments, > the patch basically implements distribution in the following steps: > > 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 dependences between statements. > 3) Apart from RDG, compute data dependences 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 parallelly; 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 dependences. > The vertices (PG:V) model all partitions and the edges (PG:E) model > all data dependences 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 > dependences because of possible alias relation of data references. > We categorize PG's edge to two types: "true" edge that represents > compilation time known data dependences; "alias" edge for all other > data dependences. > 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge > partitions in each strong connected commponent (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 dependences of the removed "alias" edges. Create > runtime alias checks for collected data dependences. > 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 shouldn't be difficult): > TODO: > 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 > > This patch also fixes couple of latent bugs in the original implementation. It would be nice to split this patch up, for example fixing the latent bugs first (so we can backport that part). You now compute _all_ dependences in the loop while I originally designed loop distribution to do less dependence computation by only computing dependences between datarefs in different partitions (and delaying that until after partition fusing required by things not requiring dependence info). Please do not remove this optimization. Richard. > After this change, kernel loop in hmmer can be distributed and vectorized as a result. > This gives obvious performance improvement. There is still inefficient code generation > issue which I will try to fix in loop split. Apart from this, the next opportunity in hmmer > is to eliminate number of dead stores under proper alias information. > Bootstrap and test at O2/O3 on x86_64 and AArch64. is it OK? > > Thanks, > bin > 2017-05-31 Bin Cheng <bin.cheng@arm.com> > > * cfgloop.h (struct loop): New field ldist_alias_id. > * cfgloopmanip.c (lv_adjust_loop_entry_edge): Refine comment for > new internal function. > * internal-fn.c (expand_LOOP_DIST_ALIAS): New function. > * internal-fn.def (IFN_LOOP_DIST_ALIAS): New internal function. > * tree-loop-distribution.c: Add general explanantion on the pass. > Include header file. > (struct ddr_entry, struct ddr_entry_hasher): New structs. > (ddr_entry_hasher::hash, ddr_entry_hasher::equal): New functions. > (bb_top_order_index, bb_top_order_index_size): New static vars. > (bb_top_order_cmp): New function. > (stmts_from_loop): Get basic blocks in topological order. Don't > free data references. > (build_rdg): New parameter pointing to vector of data references. > Store data references in it. > (enum partition_type): New enum. > (enum partition_kind, struct partition): Add comments. New fields. > (partition_alloc, partition_free): Handle new fields of partition. > (enum fuse_type, fuse_message): New enum and varaible. > (partition_merge_into): New parameter. Update implementation wrto > new fields of partition. > (generate_loops_for_partition): Set ldist_alias_id information. > (record_ddr, get_ddr, possible_data_dep_cycle_p): New functions. > (build_rdg_partition_for_vertex): New parameter. Compute type info > for partition. > (classify_partition): New parameter. Only classify partition as > reduction if the reduction is not included by all partitions. > Retrieve cached ddr, rather than compute it on the fly. > (ref_base_address): Delete. > (similar_memory_accesses): Rename to ... > (share_memory_accesses): ... this. > (rdg_build_partitions): New parameter and update uses. > (pg_add_dependence_edges): New parameter. Store ddr in parameter > vector if it could be resolved by runtime alias check. > (rdg_compute_data_dependence): New function. > (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): Update uses. Break SCC and version loop > with runtime alias checks. > (pass_loop_distribution::execute): Compute topological order for > basic blocks. Update uses. > * tree-vectorizer.c (vect_loop_dist_alias_call): New. > (fold_loop_dist_alias_call): New. > (vectorize_loops): Fold IFN_LOOP_DIST_ALIAS call depending on > successful vectorization or not. > > gcc/testsuite/ChangeLog > 2017-05-31 Bin Cheng <bin.cheng@arm.com> > > * gcc.dg/tree-ssa/ldist-4.c: Adjust test string. > * gcc.dg/tree-ssa/ldist-12.c: Ditto. > * gcc.dg/tree-ssa/ldist-13.c: Ditto. > * gcc.dg/tree-ssa/ldist-14.c: Ditto.
On Wed, Jun 7, 2017 at 11:03 AM, Richard Biener <richard.guenther@gmail.com> wrote: > On Fri, Jun 2, 2017 at 1:51 PM, Bin Cheng <Bin.Cheng@arm.com> wrote: >> Hi, >> This is the main patch of the change. It improves loop distribution by versioning loop under >> runtime alias check conditions, as well as better partition fusion. As described in comments, >> the patch basically implements distribution in the following steps: >> >> 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 dependences between statements. >> 3) Apart from RDG, compute data dependences 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 parallelly; 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 dependences. >> The vertices (PG:V) model all partitions and the edges (PG:E) model >> all data dependences 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 >> dependences because of possible alias relation of data references. >> We categorize PG's edge to two types: "true" edge that represents >> compilation time known data dependences; "alias" edge for all other >> data dependences. >> 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge >> partitions in each strong connected commponent (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 dependences of the removed "alias" edges. Create >> runtime alias checks for collected data dependences. >> 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 shouldn't be difficult): >> TODO: >> 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 >> >> This patch also fixes couple of latent bugs in the original implementation. > > It would be nice to split this patch up, for example fixing the latent > bugs first > (so we can backport that part). I only remember the major one in which topological order is needed when sorting statements, dominance order is not enough. I will try to split it as much as possible, but the change falls in a big chunk to some extend. > > You now compute _all_ dependences in the loop while I originally designed loop > distribution to do less dependence computation by only computing dependences > between datarefs in different partitions (and delaying that until > after partition fusing > required by things not requiring dependence info). > Please do not remove this optimization. Right, I did that and cache it in hash table because we need to query dependence for two references multiple times. I will restore the on-demand computing behavior. Thanks, bin > > Richard. > >> After this change, kernel loop in hmmer can be distributed and vectorized as a result. >> This gives obvious performance improvement. There is still inefficient code generation >> issue which I will try to fix in loop split. Apart from this, the next opportunity in hmmer >> is to eliminate number of dead stores under proper alias information. >> Bootstrap and test at O2/O3 on x86_64 and AArch64. is it OK? >> >> Thanks, >> bin >> 2017-05-31 Bin Cheng <bin.cheng@arm.com> >> >> * cfgloop.h (struct loop): New field ldist_alias_id. >> * cfgloopmanip.c (lv_adjust_loop_entry_edge): Refine comment for >> new internal function. >> * internal-fn.c (expand_LOOP_DIST_ALIAS): New function. >> * internal-fn.def (IFN_LOOP_DIST_ALIAS): New internal function. >> * tree-loop-distribution.c: Add general explanantion on the pass. >> Include header file. >> (struct ddr_entry, struct ddr_entry_hasher): New structs. >> (ddr_entry_hasher::hash, ddr_entry_hasher::equal): New functions. >> (bb_top_order_index, bb_top_order_index_size): New static vars. >> (bb_top_order_cmp): New function. >> (stmts_from_loop): Get basic blocks in topological order. Don't >> free data references. >> (build_rdg): New parameter pointing to vector of data references. >> Store data references in it. >> (enum partition_type): New enum. >> (enum partition_kind, struct partition): Add comments. New fields. >> (partition_alloc, partition_free): Handle new fields of partition. >> (enum fuse_type, fuse_message): New enum and varaible. >> (partition_merge_into): New parameter. Update implementation wrto >> new fields of partition. >> (generate_loops_for_partition): Set ldist_alias_id information. >> (record_ddr, get_ddr, possible_data_dep_cycle_p): New functions. >> (build_rdg_partition_for_vertex): New parameter. Compute type info >> for partition. >> (classify_partition): New parameter. Only classify partition as >> reduction if the reduction is not included by all partitions. >> Retrieve cached ddr, rather than compute it on the fly. >> (ref_base_address): Delete. >> (similar_memory_accesses): Rename to ... >> (share_memory_accesses): ... this. >> (rdg_build_partitions): New parameter and update uses. >> (pg_add_dependence_edges): New parameter. Store ddr in parameter >> vector if it could be resolved by runtime alias check. >> (rdg_compute_data_dependence): New function. >> (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): Update uses. Break SCC and version loop >> with runtime alias checks. >> (pass_loop_distribution::execute): Compute topological order for >> basic blocks. Update uses. >> * tree-vectorizer.c (vect_loop_dist_alias_call): New. >> (fold_loop_dist_alias_call): New. >> (vectorize_loops): Fold IFN_LOOP_DIST_ALIAS call depending on >> successful vectorization or not. >> >> gcc/testsuite/ChangeLog >> 2017-05-31 Bin Cheng <bin.cheng@arm.com> >> >> * gcc.dg/tree-ssa/ldist-4.c: Adjust test string. >> * gcc.dg/tree-ssa/ldist-12.c: Ditto. >> * gcc.dg/tree-ssa/ldist-13.c: Ditto. >> * gcc.dg/tree-ssa/ldist-14.c: Ditto.
Hi Bin, > + > +/* In reduced dependence graph RDG for loop distribution, return true if > + dependence between references DR1 and DR2 may create dependence cycle > + and such dependence cycle can't be resolved by runtime alias check. */ > + > +static bool > +possible_data_dep_cycle_p (struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, > + data_reference_p dr1, data_reference_p dr2) This name seems to be misleading a bit. It is basically dependence test ? Of course this can lead to a cycle but looks like possible_data_dep_p would be better. > +{ > + struct data_dependence_relation *ddr; > + > + /* Re-shuffle data-refs to be in topological order. */ > + if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) > + > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) > + std::swap (dr1, dr2); > + > + ddr = get_ddr (rdg, ddr_table, dr1, dr2); > + > + /* In case something goes wrong in data dependence analysis. */ > + if (ddr == NULL) > + return true; > + /* In case of no data dependence. */ > + else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) > + return false; > + /* Or the data dependence can be resolved by compilation time alias > + check. */ > + else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)), > + get_alias_set (DR_REF (dr2)))) > + return false; > + /* For unknown data dependence or known data dependence which can't be > + expressed in classic distance vector, we check if it can be resolved > + by runtime alias check. If yes, we still consider data dependence > + as won't introduce data dependence cycle. */ > + else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know > + || DDR_NUM_DIST_VECTS (ddr) == 0) You have already handled chrec_known above. Can you still have known data dependence which can't be expressed in classic distance vector ? > + return !runtime_alias_check_p (ddr, NULL, true); > + else if (DDR_NUM_DIST_VECTS (ddr) > 1) > + return true; > + else if (DDR_REVERSED_P (ddr) > + || lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) > + return false; > + > + return true; > +} > > /* Returns a partition with all the statements needed for computing > the vertex V of the RDG, also including the loop exit conditions. */ > > static partition * > -build_rdg_partition_for_vertex (struct graph *rdg, int v) > +build_rdg_partition_for_vertex (struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, int v) > { > partition *partition = partition_alloc (NULL, NULL); > auto_vec<int, 3> nodes; > - unsigned i; > + unsigned i, j; > int x; > + data_reference_p dr, dr1, dr2; > > graphds_dfs (rdg, &v, 1, &nodes, false, NULL); > > @@ -1005,8 +1262,43 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) > bitmap_set_bit (partition->stmts, x); > bitmap_set_bit (partition->loops, > loop_containing_stmt (RDG_STMT (rdg, x))->num); > + > + for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j) > + { > + /* Partition can only be executed sequentially if there is any > + unknown data reference. */ > + if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) > + || !DR_INIT (dr) || !DR_STEP (dr)) > + partition->type = PTYPE_SEQUENTIAL; > + > + if (DR_IS_READ (dr)) > + partition->reads.safe_push (dr); > + else > + partition->writes.safe_push (dr); > + } > } > > + if (partition->type == PTYPE_SEQUENTIAL) > + return partition; > + > + /* Further check if any data dependence prevents us from executing the > + partition parallelly. */ > + for (i = 0; partition->reads.iterate (i, &dr1); ++i) > + for (j = 0; partition->writes.iterate (j, &dr2); ++j) > + if (possible_data_dep_cycle_p (rdg, ddr_table, dr1, dr2)) > + { > + partition->type = PTYPE_SEQUENTIAL; > + return partition; > + } > + > + for (i = 0; partition->writes.iterate (i, &dr1); ++i) > + for (j = i + 1; partition->writes.iterate (j, &dr2); ++j) > + if (possible_data_dep_cycle_p (rdg, ddr_table, dr1, dr2)) > + { > + partition->type = PTYPE_SEQUENTIAL; > + return partition; > + } > + > return partition; > } > > @@ -1014,7 +1306,9 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) > For the moment we detect only the memset zero pattern. */ > > static void > -classify_partition (loop_p loop, struct graph *rdg, partition *partition) > +classify_partition (loop_p loop, struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, > + partition *partition, bitmap stmt_in_all_partitions) > { > bitmap_iterator bi; > unsigned i; > @@ -1022,6 +1316,7 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) > data_reference_p single_load, single_store; > bool volatiles_p = false; > bool plus_one = false; > + bool has_reduction = false; > > partition->kind = PKIND_NORMAL; > partition->main_dr = NULL; > @@ -1036,16 +1331,24 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) > if (gimple_has_volatile_ops (stmt)) > volatiles_p = true; > > - /* If the stmt has uses outside of the loop mark it as reduction. */ > + /* If the stmt is not included by all partitions and there is uses > + outside of the loop, then mark the partition as reduction. */ > if (stmt_has_scalar_dependences_outside_loop (loop, stmt)) > { > - partition->reduction_p = true; > - return; > + if (!bitmap_bit_p (stmt_in_all_partitions, i)) > + { > + partition->reduction_p = true; > + return; > + } > + has_reduction = true; > } > } > > /* Perform general partition disqualification for builtins. */ > if (volatiles_p > + /* Simple workaround to prevent classifying the partition as builtin > + if it contains any use outside of loop. */ > + || has_reduction > || !flag_tree_loop_distribute_patterns) > return; > > @@ -1143,44 +1446,27 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) > return; > /* Now check that if there is a dependence this dependence is > of a suitable form for memmove. */ > - vec<loop_p> loops = vNULL; > - ddr_p ddr; > - loops.safe_push (loop); > - ddr = initialize_data_dependence_relation (single_load, single_store, > - loops); > - compute_affine_dependence (ddr, loop); > + ddr_p ddr = get_ddr (rdg, ddr_table, single_load, single_store); > if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) > - { > - free_dependence_relation (ddr); > - loops.release (); > - return; > - } > + return; > + > if (DDR_ARE_DEPENDENT (ddr) != chrec_known) > { > if (DDR_NUM_DIST_VECTS (ddr) == 0) > - { > - free_dependence_relation (ddr); > - loops.release (); > - return; > - } > + return; > + > lambda_vector dist_v; > FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v) > { > int dist = dist_v[index_in_loop_nest (loop->num, > DDR_LOOP_NEST (ddr))]; > if (dist > 0 && !DDR_REVERSED_P (ddr)) > - { > - free_dependence_relation (ddr); > - loops.release (); > - return; > - } > + return; > } > partition->kind = PKIND_MEMMOVE; > } > else > partition->kind = PKIND_MEMCPY; > - free_dependence_relation (ddr); > - loops.release (); > partition->main_dr = single_store; > partition->secondary_dr = single_load; > partition->niter = nb_iter; > @@ -1188,30 +1474,16 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) > } > } > > -/* For a data reference REF, return the declaration of its base > - address or NULL_TREE if the base is not determined. */ > - > -static tree > -ref_base_address (data_reference_p dr) > -{ > - tree base_address = DR_BASE_ADDRESS (dr); > - if (base_address > - && TREE_CODE (base_address) == ADDR_EXPR) > - return TREE_OPERAND (base_address, 0); > - > - return base_address; > -} > - > -/* Returns true when PARTITION1 and PARTITION2 have similar memory > - accesses in RDG. */ > +/* Returns true when PARTITION1 and PARTITION2 share the same memory > + accesses in RDG. This is a simple data reuse cost model. */ > > static bool > -similar_memory_accesses (struct graph *rdg, partition *partition1, > - partition *partition2) > +share_memory_accesses (struct graph *rdg, > + partition *partition1, partition *partition2) > { > - unsigned i, j, k, l; > - bitmap_iterator bi, bj; > - data_reference_p ref1, ref2; > + unsigned i, j; > + data_reference_p dr1, dr2; > + bitmap_iterator bi; > > /* First check whether in the intersection of the two partitions are > any loads or stores. Common loads are the situation that happens > @@ -1221,24 +1493,69 @@ similar_memory_accesses (struct graph *rdg, partition *partition1, > || RDG_MEM_READS_STMT (rdg, i)) > return true; > > - /* Then check all data-references against each other. */ > - EXECUTE_IF_SET_IN_BITMAP (partition1->stmts, 0, i, bi) > - if (RDG_MEM_WRITE_STMT (rdg, i) > - || RDG_MEM_READS_STMT (rdg, i)) > - EXECUTE_IF_SET_IN_BITMAP (partition2->stmts, 0, j, bj) > - if (RDG_MEM_WRITE_STMT (rdg, j) > - || RDG_MEM_READS_STMT (rdg, j)) > - { > - FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, i), k, ref1) > - { > - tree base1 = ref_base_address (ref1); > - if (base1) > - FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, j), l, ref2) > - if (base1 == ref_base_address (ref2)) > - return true; > - } > - } > + for (i = 0; partition1->reads.iterate (i, &dr1); ++i) > + { > + if (!DR_BASE_ADDRESS (dr1) > + || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1)) > + continue; > + > + for (j = 0; partition2->reads.iterate (j, &dr2); ++j) > + { > + if (!DR_BASE_ADDRESS (dr2) > + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) > + continue; > + > + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) > + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) > + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) > + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) > + return true; > + } > + for (j = 0; partition2->writes.iterate (j, &dr2); ++j) > + { > + if (!DR_BASE_ADDRESS (dr2) > + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) > + continue; > + > + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) > + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) > + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) > + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) > + return true; > + } > + } > + > + for (i = 0; partition1->writes.iterate (i, &dr1); ++i) > + { > + if (!DR_BASE_ADDRESS (dr1) > + || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1)) > + continue; > + > + for (j = 0; partition2->reads.iterate (j, &dr2); ++j) > + { > + if (!DR_BASE_ADDRESS (dr2) > + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) > + continue; > > + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) > + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) > + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) > + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) > + return true; > + } > + for (j = 0; partition2->writes.iterate (j, &dr2); ++j) > + { > + if (!DR_BASE_ADDRESS (dr2) > + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) > + continue; > + > + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) > + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) > + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) > + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) > + return true; > + } > + } > return false; > } > > @@ -1248,8 +1565,10 @@ similar_memory_accesses (struct graph *rdg, partition *partition1, > > static void > rdg_build_partitions (struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, > vec<gimple *> starting_stmts, > - vec<partition *> *partitions) > + vec<partition *> *partitions, > + bitmap stmt_in_all_partitions) > { > auto_bitmap processed; > int i; > @@ -1261,20 +1580,22 @@ rdg_build_partitions (struct graph *rdg, > > if (dump_file && (dump_flags & TDF_DETAILS)) > fprintf (dump_file, > - "ldist asked to generate code for vertex %d\n", v); > + "LDist asked to generate code for vertex %d\n", v); > > /* If the vertex is already contained in another partition so > is the partition rooted at it. */ > if (bitmap_bit_p (processed, v)) > continue; > > - partition *partition = build_rdg_partition_for_vertex (rdg, v); > + partition *partition = build_rdg_partition_for_vertex (rdg, ddr_table, v); > bitmap_ior_into (processed, partition->stmts); > + bitmap_and_into (stmt_in_all_partitions, partition->stmts); > > if (dump_file && (dump_flags & TDF_DETAILS)) > { > - fprintf (dump_file, "ldist useful partition:\n"); > - dump_bitmap (dump_file, partition->stmts); > + fprintf (dump_file, "LDist creates useful %s partition:\n", > + partition->type == PTYPE_PARALLEL ? "parallel" : "sequent"); > + bitmap_print (dump_file, partition->stmts, " ", "\n"); > } > > partitions->safe_push (partition); > @@ -1365,12 +1686,15 @@ partition_contains_all_rw (struct graph *rdg, > } > > /* Compute partition dependence created by the data references in DRS1 > - and DRS2 and modify and return DIR according to that. */ > + and DRS2 and modify and return DIR according to that. If additional > + dependence is introduced by possible alias between data references, > + we record such data dependence relations in ALIAS_DDRS. */ > > static int > -pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir, > +pg_add_dependence_edges (struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, int dir, > vec<data_reference_p> drs1, > - vec<data_reference_p> drs2) > + vec<data_reference_p> drs2, vec<ddr_p> *alias_ddrs) > { > data_reference_p dr1, dr2; > > @@ -1380,26 +1704,40 @@ pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir, > for (int jj = 0; drs2.iterate (jj, &dr2); ++jj) > { > data_reference_p saved_dr1 = dr1; > - int this_dir = 1; > + int res, this_dir = 1; > ddr_p ddr; > - /* Re-shuffle data-refs to be in dominator order. */ > + /* Re-shuffle data-refs to be in topological order. */ > if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) > > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) > { > std::swap (dr1, dr2); > this_dir = -this_dir; > } > - ddr = initialize_data_dependence_relation (dr1, dr2, loops); > - compute_affine_dependence (ddr, loops[0]); > + ddr = get_ddr (rdg, ddr_table, dr1, dr2); > if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) > - this_dir = 2; > + { > + res = data_ref_compare_tree (DR_BASE_ADDRESS (dr1), > + DR_BASE_ADDRESS (dr2)); > + /* Be conservative. If data references are not well analyzed, or > + the two data references have the same base address and offset, > + add dependence and consider it alias to each other. In other > + words, the dependence can not be resolved by runtime alias > + check. */ > + if (!DR_BASE_ADDRESS (dr1) || !DR_OFFSET (dr1) || !DR_INIT (dr1) > + || !DR_BASE_ADDRESS (dr2) || !DR_OFFSET (dr2) || !DR_INIT (dr2) > + || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1)) > + || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2)) > + || res == 0) > + this_dir = 2; > + /* If it's possible to do runtime alias check, simply record the > + ddr. */ > + else if (alias_ddrs != NULL) > + alias_ddrs->safe_push (ddr); If alias_ddrs is not passed (i.e. NULL), shouldn't this_ddr = 2. May be add an assert for alias_ddrs ? > + } > else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) > { > if (DDR_REVERSED_P (ddr)) > - { > - std::swap (dr1, dr2); > - this_dir = -this_dir; > - } > + this_dir = -this_dir; > /* Known dependences can still be unordered througout the > iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ > if (DDR_NUM_DIST_VECTS (ddr) != 1) > @@ -1407,16 +1745,13 @@ pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir, > /* If the overlap is exact preserve stmt order. */ > else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) > ; > + /* Else as the distance vector is lexicographic positive > + swap the dependence direction. */ > else > - { > - /* Else as the distance vector is lexicographic positive > - swap the dependence direction. */ > - this_dir = -this_dir; > - } > + this_dir = -this_dir; > } > else > this_dir = 0; > - free_dependence_relation (ddr); > if (this_dir == 2) > return 2; > else if (dir == 0) > @@ -1439,6 +1774,663 @@ pgcmp (const void *v1_, const void *v2_) > return v2->post - v1->post; > } > > +/* Given loop nest LOOPS and its reduced dependence graph RDG for loop > + distribution, compute data dependence relations for all data refs in > + DATAREFS. Record dependence relation in DEPENDENCES and DDR_TABLE. */ > + > +static void > +rdg_compute_data_dependence (struct graph *rdg, vec<loop_p> loops, > + vec<data_reference_p> *datarefs, > + vec<ddr_p> *dependences, > + hash_table<ddr_entry_hasher> *ddr_table) > +{ > + int i, j; > + data_reference_p a, b; > + struct data_dependence_relation *ddr; > + > + FOR_EACH_VEC_ELT ((*datarefs), i, a) > + for (j = i + 1; datarefs->iterate (j, &b); j++) > + if (DR_IS_WRITE (a) || DR_IS_WRITE (b)) > + { > + ddr = initialize_data_dependence_relation (a, b, loops); > + compute_affine_dependence (ddr, loops[0]); > + dependences->safe_push (ddr); > + /* Record data dependence relation in hash table for later > + because it will be used multiple times. */ > + record_ddr (rdg, ddr_table, a, b, ddr); > + } > +} > + > +/* Data attached to vertices of partition dependence graph. */ > +struct pg_vdata > +{ > + /* ID of the corresponding partition. */ > + int id; > + /* The partition. */ > + struct partition *partition; > +}; > + > +/* Data attached to edges of partition dependence graph. */ > +struct pg_edata > +{ > + /* If the dependence edge can be resolved by runtime alias check, > + this vector contains data dependence relations for runtime alias > + check. On the other hand, if the dependence edge is introduced > + because of compilation time known data dependence, this vector > + is contains nothing. */ > + vec<ddr_p> alias_ddrs; > +}; > + > +/* Callback data for traversing edges in graph. */ > +struct pg_edge_callback_data > +{ > + /* Bitmap contains strong connected components should be merged. */ > + bitmap sccs_to_merge; > + /* Array constains component information for all vertices. */ > + int *vertices_component; > + /* Vector to record all data dependence relations which are needed > + to break strong connected components by runtime alias checks. */ > + vec<ddr_p> *alias_ddrs; > +}; > + > +/* Initialize vertice's data for partition dependence graph PG with > + PARTITIONS. */ > +static void > +init_partition_graph_vertices (struct graph *pg, > + vec<struct partition *> *partitions) > +{ > + int i; > + partition *partition; > + struct pg_vdata *data; > + > + for (i = 0; partitions->iterate (i, &partition); ++i) > + { > + data = new pg_vdata; > + pg->vertices[i].data = data; > + data->id = i; > + data->partition = partition; > + } > +} > + > +/* Add edge <I, J> to partition dependence graph PG. Attach vector of data > + dependence relations to the EDGE if DDRS isn't NULL. */ > + > +static void > +add_partition_graph_edge (struct graph *pg, int i, int j, vec<ddr_p> *ddrs) > +{ > + struct graph_edge *e = add_edge (pg, i, j); > + > + /* If the edge is attached with data dependence relations, it means this > + dependence edge can be resolved by runtime alias checks. */ > + if (ddrs != NULL) > + { > + struct pg_edata *data = new pg_edata; > + > + gcc_assert (ddrs->length () > 0); > + e->data = data; > + data->alias_ddrs = vNULL; > + data->alias_ddrs.safe_splice (*ddrs); > + } > +} > + > +/* Callback function for graph travesal algorithm. It returns true > + if edge E shouldn't be considered in graph when traversing it. */ > + > +static bool > +pg_skip_alias_edge (struct graph_edge *e) > +{ > + struct pg_edata *data = (struct pg_edata *)e->data; > + return (data != NULL && data->alias_ddrs.length () > 0); > +} > + > +/* Callback function freeing data attached to edge E of graph. */ > + > +static void > +free_partition_graph_edata_cb (struct graph *, struct graph_edge *e, void *) > +{ > + if (e->data != NULL) > + { > + struct pg_edata *data = (struct pg_edata *)e->data; > + data->alias_ddrs.release (); > + delete data; > + } > +} > + > +/* Free data attached to vertice of partition dependence graph PG. */ > + > +static void > +free_partition_graph_vdata (struct graph *pg) > +{ > + int i; > + struct pg_vdata *data; > + > + for (i = 0; i < pg->n_vertices; ++i) > + { > + data = (struct pg_vdata *)pg->vertices[i].data; > + delete data; > + } > +} > + > +/* Build and return partition dependence graph for PARTITIONS. RDG is > + reduced dependence graph for the loop to be distributed. DDR_TABLE > + is hash table contains all data dependence relations. ALIAS_DDRS is > + a data dependence relations vector for temporary use. If ALIAS_DDRS > + is NULL, dependence which can be resolved by runtime alias check will > + not be considered, vice versa. */ > + > +static struct graph * > +build_partition_graph (struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, > + vec<struct partition *> *partitions, > + vec<ddr_p> *alias_ddrs) Why do you pass alias_ddrs to this. alias_ddrs does not pass any data or return any. It can be defined in the function and used there. If you are using this to indicate runtime alias check should be considered, you can define a different bool for that ? > +{ > + int i, j; > + struct partition *partition1, *partition2; > + graph *pg = new_graph (partitions->length ()); > + > + init_partition_graph_vertices (pg, partitions); > + > + for (i = 0; partitions->iterate (i, &partition1); ++i) > + { > + for (j = i + 1; partitions->iterate (j, &partition2); ++j) > + { > + /* dependence direction - 0 is no dependence, -1 is back, > + 1 is forth, 2 is both (we can stop then, merging will occur). */ > + int dir = 0; > + > + /* If the first partition has reduction, add back edge; if the > + second partition has reduction, add forth edge. This makes > + sure that reduction partition will be sorted as the last one. */ > + if (partition_reduction_p (partition1)) > + dir = -1; > + else if (partition_reduction_p (partition2)) > + dir = 1; > + > + /* Cleanup the temporary vector. */ > + if (alias_ddrs != NULL) > + alias_ddrs->truncate (0); > + > + dir = pg_add_dependence_edges (rdg, ddr_table, dir, > + partition1->writes, > + partition2->reads, alias_ddrs); > + if (dir != 2) > + dir = pg_add_dependence_edges (rdg, ddr_table, dir, > + partition1->reads, > + partition2->writes, alias_ddrs); > + if (dir != 2) > + dir = pg_add_dependence_edges (rdg, ddr_table, dir, > + partition1->writes, > + partition2->writes, alias_ddrs); > + > + /* Add edge to partition graph if there exists dependence. There > + are two types of edges. One type edge is caused by compilation > + time know dependence, this type can not be resolved by runtime > + alias check. The other type can be resolved by runtime alias > + check. */ > + if (dir == 1 || dir == 2 > + || (alias_ddrs != NULL && alias_ddrs->length () > 0)) > + { > + /* Attach data dependence relations to edge that can be resolved > + by runtime alias check. */ > + bool alias_edge_p = (dir != 1 && dir != 2); > + add_partition_graph_edge (pg, i, j, > + (alias_edge_p) ? alias_ddrs : NULL); > + } > + if (dir == -1 || dir == 2 > + || (alias_ddrs != NULL && alias_ddrs->length () > 0)) > + { > + /* Attach data dependence relations to edge that can be resolved > + by runtime alias check. */ > + bool alias_edge_p = (dir != -1 && dir != 2); > + add_partition_graph_edge (pg, j, i, > + (alias_edge_p) ? alias_ddrs : NULL); > + } > + } > + } > + return pg; > +} > + > +/* Sort partitions in PG by post order and store them in PARTITIONS. */ > + > +static void > +sort_partitions_by_post_order (struct graph *pg, > + vec<struct partition *> *partitions) > +{ > + int i; > + struct pg_vdata *data; > + > + /* Now order the remaining nodes in postorder. */ > + qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp); > + partitions->truncate (0); > + for (i = 0; i < pg->n_vertices; ++i) > + { > + data = (struct pg_vdata *)pg->vertices[i].data; > + if (data->partition) > + partitions->safe_push (data->partition); > + } > +} > + > +/* Given reduced dependence graph RDG and data dependences in DDR_TABLE, > + merge strong connected components of PARTITIONS. ALIAS_DDRS is a data > + dependence relations vector for temporary use. If ALIAS_DDRS is NULL, > + dependence which can be resolved by runtime alias check will not be > + considered in building dependence graph for partitions, vice versa. */ > + > +static void > +merge_dep_scc_partitions (struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, > + vec<struct partition *> *partitions, > + vec<ddr_p> *alias_ddrs) > +{ > + struct partition *partition1, *partition2; > + struct pg_vdata *data; > + graph *pg = build_partition_graph (rdg, ddr_table, partitions, alias_ddrs); > + int i, j, num_sccs = graphds_scc (pg, NULL); > + > + /* Strong connected compoenent means dependence cycle, we cannot distribute > + them. So fuse them together. */ > + if ((unsigned) num_sccs < partitions->length ()) > + { > + for (i = 0; i < num_sccs; ++i) > + { > + for (j = 0; partitions->iterate (j, &partition1); ++j) > + if (pg->vertices[j].component == i) > + break; > + for (j = j + 1; partitions->iterate (j, &partition2); ++j) > + if (pg->vertices[j].component == i) > + { > + partition_merge_into (partition1, partition2, FUSE_SAME_SCC); > + (*partitions)[j] = NULL; > + partition_free (partition2); > + data = (struct pg_vdata *)pg->vertices[j].data; > + data->partition = NULL; > + } > + } > + sort_partitions_by_post_order (pg, partitions); > + } > + gcc_assert (partitions->length () == (unsigned)num_sccs); > + free_partition_graph_vdata (pg); > + free_graph (pg); > +} > + > +/* Callback function for traversing edge E in graph G. DATA is private > + callback data. */ > + > +static void > +pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data) > +{ > + int i, j, component; > + struct pg_edge_callback_data *cbdata; > + struct pg_edata *edata = (struct pg_edata *) e->data; > + > + /* If the edge doesn't have attached data dependence, it represents > + compilation time known dependences. This type dependence cannot > + be resolved by runtime alias check. */ > + if (edata == NULL || edata->alias_ddrs.length () == 0) > + return; > + > + cbdata = (struct pg_edge_callback_data *) data; > + i = e->src; > + j = e->dest; > + component = cbdata->vertices_component[i]; > + /* Vertices are topologically sorted according to compilation time > + known dependences, so we can break strong connected components > + by removing edges of the opposite direction, i.e, edges pointing > + from vertice with smaller post number to vertice with bigger post > + number. */ > + if (g->vertices[i].post < g->vertices[j].post > + /* We only need to remove edges connecting vertices in the same > + strong connected component to break it. */ > + && component == cbdata->vertices_component[j] > + /* Check if we want to break the strong connected component or not. */ > + && !bitmap_bit_p (cbdata->sccs_to_merge, component)) > + cbdata->alias_ddrs->safe_splice (edata->alias_ddrs); > +} > + > +/* This is the main function breaking strong conected components in > + PARTITIONS giving reduced depdendence graph RDG and data dependences > + in DDR_TABLE. Store data dependence relations for runtime alias > + check in ALIAS_DDRS. */ > + > +static void > +break_alias_scc_partitions (struct graph *rdg, > + hash_table<ddr_entry_hasher> *ddr_table, > + vec<struct partition *> *partitions, > + vec<ddr_p> *alias_ddrs) I am not sure I understand this. When you are in pg_add_dependence_edges, when you record alias_ddrs for runtime checking you set this_dur io 1. That means you have broken the dpendency there itself. Were you planning to keep this_dir = 2 and break the dependency here ? Thanks, Kugan > +{ > + int i, j, num_sccs, num_sccs_no_alias; > + /* Build partition dependence graph. */ > + graph *pg = build_partition_graph (rdg, ddr_table, partitions, alias_ddrs); > + > + alias_ddrs->truncate (0); > + /* Find strong connected components in the graph, with all dependence edges > + considered. */ > + num_sccs = graphds_scc (pg, NULL); > + /* All SCCs now can be broken by runtime alias checks because SCCs caused by > + compilation time known dependences are merged before this function. */ > + if ((unsigned) num_sccs < partitions->length ()) > + { > + struct pg_edge_callback_data cbdata; > + auto_bitmap sccs_to_merge; > + auto_vec<enum partition_type> scc_types; > + struct partition *partition, *first; > + > + /* If all paritions in a SCC has the same type, we can simply merge the > + SCC. This loop finds out such SCCS and record them in bitmap. */ > + bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs); > + for (i = 0; i < num_sccs; ++i) > + { > + for (j = 0; partitions->iterate (j, &first); ++j) > + if (pg->vertices[j].component == i) > + break; > + for (++j; partitions->iterate (j, &partition); ++j) > + { > + if (pg->vertices[j].component != i) > + continue; > + > + if (first->type != partition->type) > + { > + bitmap_clear_bit (sccs_to_merge, i); > + break; > + } > + } > + } > + > + /* Initialize callback data for traversing. */ > + cbdata.sccs_to_merge = sccs_to_merge; > + cbdata.alias_ddrs = alias_ddrs; > + cbdata.vertices_component = XNEWVEC (int, pg->n_vertices); > + /* Record the component information which will be corrupted by next > + graph scc finding call. */ > + for (i = 0; i < pg->n_vertices; ++i) > + cbdata.vertices_component[i] = pg->vertices[i].component; > + > + /* Collect data dependences for runtime alias checks to break SCCs. */ > + if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs) > + { > + /* Run SCC finding algorithm again, with alias dependence edges > + skipped. This is to topologically sort paritions according to > + compilation time known dependence. Note the topological order > + is stored in the form of pg's post order number. */ > + num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge); > + gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias); > + /* With topological order, we can construct two subgraphs L and R. > + L contains edge <x, y> where x < y in terms of post order, while > + R contains edge <x, y> where x > y. Edges for compilation time > + known dependence all fall in R, so we break SCCs by removing all > + (alias) edges of in subgraph L. */ > + for_each_edge (pg, pg_collect_alias_ddrs, &cbdata); > + } > + > + /* For SCC that doesn't need to be broken, merge it. */ > + for (i = 0; i < num_sccs; ++i) > + { > + if (!bitmap_bit_p (sccs_to_merge, i)) > + continue; > + > + for (j = 0; partitions->iterate (j, &first); ++j) > + if (cbdata.vertices_component[j] == i) > + break; > + for (++j; partitions->iterate (j, &partition); ++j) > + { > + struct pg_vdata *data; > + > + if (cbdata.vertices_component[j] != i) > + continue; > + > + partition_merge_into (first, partition, FUSE_SAME_SCC); > + (*partitions)[j] = NULL; > + partition_free (partition); > + data = (struct pg_vdata *)pg->vertices[j].data; > + gcc_assert (data->id == j); > + data->partition = NULL; > + } > + } > + } > + > + sort_partitions_by_post_order (pg, partitions); > + free_partition_graph_vdata (pg); > + for_each_edge (pg, free_partition_graph_edata_cb, NULL); > + free_graph (pg); > + > + if (dump_file && (dump_flags & TDF_DETAILS)) > + { > + fprintf (dump_file, "Possible alias data dependence to break:\n"); > + dump_data_dependence_relations (dump_file, *alias_ddrs); > + } > +} > + > +/* Compute and return an expression whose value is the segment length which > + will be accessed by DR in NITERS iterations. */ > + > +static tree > +data_ref_segment_size (struct data_reference *dr, tree niters) > +{ > + tree segment_length; > + > + if (integer_zerop (DR_STEP (dr))) > + segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))); > + else > + segment_length = size_binop (MULT_EXPR, > + fold_convert (sizetype, DR_STEP (dr)), > + fold_convert (sizetype, niters)); > + > + return segment_length; > +} > + > +/* Return true if LOOP's latch is dominated by statement for data reference > + DR. */ > + > +static inline bool > +latch_dominated_by_data_ref (struct loop *loop, data_reference *dr) > +{ > + return dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, > + gimple_bb (DR_STMT (dr))); > +} > + > +/* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's > + data dependence relations ALIAS_DDRS. */ > + > +static void > +compute_alias_check_pairs (struct loop *loop, vec<ddr_p> *alias_ddrs, > + vec<dr_with_seg_len_pair_t> *comp_alias_pairs) > +{ > + unsigned int i; > + unsigned HOST_WIDE_INT factor = 1; > + tree niters_plus_one, niters = number_of_latch_executions (loop); > + > + gcc_assert (niters != NULL_TREE && niters != chrec_dont_know); > + niters = fold_convert (sizetype, niters); > + niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node); > + > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, "Creating alias check pairs:\n"); > + > + /* Iterate all data dependence relations and compute alias check pairs. */ > + for (i = 0; i < alias_ddrs->length (); i++) > + { > + ddr_p ddr = (*alias_ddrs)[i]; > + struct data_reference *dr_a = DDR_A (ddr); > + struct data_reference *dr_b = DDR_B (ddr); > + tree seg_length_a, seg_length_b; > + int comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (dr_a), > + DR_BASE_ADDRESS (dr_b)); > + > + if (comp_res == 0) > + comp_res = data_ref_compare_tree (DR_OFFSET (dr_a), DR_OFFSET (dr_b)); > + gcc_assert (comp_res != 0); > + > + if (latch_dominated_by_data_ref (loop, dr_a)) > + seg_length_a = data_ref_segment_size (dr_a, niters_plus_one); > + else > + seg_length_a = data_ref_segment_size (dr_a, niters); > + > + if (latch_dominated_by_data_ref (loop, dr_b)) > + seg_length_b = data_ref_segment_size (dr_b, niters_plus_one); > + else > + seg_length_b = data_ref_segment_size (dr_b, niters); > + > + dr_with_seg_len_pair_t dr_with_seg_len_pair > + (dr_with_seg_len (dr_a, seg_length_a), > + dr_with_seg_len (dr_b, seg_length_b)); > + > + /* Canonicalize pairs by sorting the two DR members. */ > + if (comp_res > 0) > + std::swap (dr_with_seg_len_pair.first, dr_with_seg_len_pair.second); > + > + comp_alias_pairs->safe_push (dr_with_seg_len_pair); > + } > + > + if (tree_fits_uhwi_p (niters)) > + factor = tree_to_uhwi (niters); > + > + /* Prune alias check pairs. */ > + prune_runtime_alias_test_list (comp_alias_pairs, factor); > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, > + "Improved number of alias checks from %d to %d\n", > + alias_ddrs->length (), comp_alias_pairs->length ()); > +} > + > +/* Given data dependence relations in ALIAS_DDRS, generate runtime alias > + checks and version LOOP under condition of these runtime alias checks. */ > + > +static void > +version_loop_by_alias_check (struct loop *loop, vec<ddr_p> *alias_ddrs) > +{ > + unsigned then_prob, else_prob, then_scale, else_scale; > + basic_block cond_bb; > + struct loop *nloop; > + tree lhs, arg0, cond_expr = NULL_TREE; > + gimple_seq cond_stmts = NULL; > + gimple *stmt; > + auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs; > + > + /* Generate code for runtime alias checks if necessary. */ > + if (alias_ddrs->length () > 0) > + { > + compute_alias_check_pairs (loop, alias_ddrs, &comp_alias_pairs); > + create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr); > + cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts, > + is_gimple_condexpr, NULL_TREE); > + then_prob = 9 * REG_BR_PROB_BASE / 10; > + else_prob = REG_BR_PROB_BASE - then_prob; > + then_scale = 9 * REG_BR_PROB_BASE / 10; > + else_scale = REG_BR_PROB_BASE - then_scale; > + } > + else > + { > + cond_expr = boolean_true_node; > + /* Use REG_BR_PROB_BASE for both branches since only one branch > + will be kept in the end. */ > + then_prob = REG_BR_PROB_BASE; > + else_prob = REG_BR_PROB_BASE; > + then_scale = REG_BR_PROB_BASE; > + else_scale = REG_BR_PROB_BASE; > + } > + > + /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */ > + if (flag_tree_loop_vectorize) > + { > + /* Generate internal function call for loop distribution alias check. */ > + arg0 = build_int_cst (integer_type_node, loop->num); > + stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS, > + 2, arg0, cond_expr); > + lhs = make_ssa_name (boolean_type_node); > + gimple_call_set_lhs (stmt, lhs); > + gimple_seq_add_stmt (&cond_stmts, stmt); > + } > + else > + lhs = cond_expr; > + > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, > + "Version loop <%d> with runtime alias check\n", loop->num); > + > + initialize_original_copy_tables (); > + nloop = loop_version (loop, lhs, &cond_bb, then_prob, > + else_prob, then_scale, else_scale, true); > + free_original_copy_tables (); > + nloop->aux = (void *)nloop; > + /* Record the original loop number in newly generated loops. */ > + nloop->ldist_alias_id = loop->num; > + nloop->dont_vectorize = true; > + nloop->force_vectorize = false; > + > + if (cond_stmts) > + { > + gimple_stmt_iterator cond_gsi = gsi_last_bb (cond_bb); > + gsi_insert_seq_before (&cond_gsi, cond_stmts, GSI_SAME_STMT); > + } > + update_ssa (TODO_update_ssa); > +} > + > +/* Return true if loop versioning is needed to distrubute PARTITIONS. > + ALIAS_DDRS are data dependence relations for runtime alias check. */ > + > +static inline bool > +version_for_distribution_p (vec<struct partition *> *partitions, > + vec<ddr_p> *alias_ddrs) > +{ > + unsigned i; > + struct partition *partition; > + > + /* No need to version loop if we have only one partition. */ > + if (partitions->length () == 1) > + return false; > + > + /* Need to version loop if runtime alias check is necessary. */ > + if (alias_ddrs->length () > 0) > + return true; > + > + /* Don't version the loop with call to IFN_LOOP_DIST_ALIAS if > + vectorizer is not enable because no other pass can fold it. */ > + if (!flag_tree_loop_vectorize) > + return false; > + > + /* Don't version loop if any partition is builtin. */ > + for (i = 0; partitions->iterate (i, &partition); ++i) > + { > + if (partition->kind != PKIND_NORMAL) > + break; > + } > + return (i == partitions->length ()); > +} > + > +/* Fuse all partitions if necessary before finalizing distribution. */ > + > +static void > +finalize_partitions (vec<struct partition *> *partitions, > + vec<ddr_p> *alias_ddrs) > +{ > + unsigned i; > + struct partition *a, *partition; > + > + if (partitions->length () == 1 > + || alias_ddrs->length () > 0) > + return; > + > + a = (*partitions)[0]; > + if (a->kind != PKIND_NORMAL) > + return; > + > + for (i = 1; partitions->iterate (i, &partition); ++i) > + { > + /* Don't fuse if partition has different type or it is a builtin. */ > + if (partition->type != a->type > + || partition->kind != PKIND_NORMAL) > + return; > + } > + > + /* Fuse all partitions. */ > + for (i = 1; partitions->iterate (i, &partition); ++i) > + { > + partition_merge_into (a, partition, FUSE_FINALIZE); > + partition_free (partition); > + } > + partitions->truncate (1); > +} > + > /* Distributes the code from LOOP in such a way that producer > statements are placed before consumer statements. Tries to separate > only the statements from STMTS into separate loops. > @@ -1453,8 +2445,6 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > partition *partition; > bool any_builtin; > int i, nbp; > - graph *pg = NULL; > - int num_sccs = 1; > > *destroy_p = false; > *nb_calls = 0; > @@ -1462,7 +2452,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > if (!find_loop_nest (loop, &loop_nest)) > return 0; > > - rdg = build_rdg (loop_nest, cd); > + vec<data_reference_p> datarefs; > + datarefs.create (10); > + rdg = build_rdg (loop_nest, cd, &datarefs); > if (!rdg) > { > if (dump_file && (dump_flags & TDF_DETAILS)) > @@ -1470,19 +2462,35 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > "Loop %d not distributed: failed to build the RDG.\n", > loop->num); > > + free_data_refs (datarefs); > return 0; > } > > if (dump_file && (dump_flags & TDF_DETAILS)) > dump_rdg (dump_file, rdg); > > + auto_vec<ddr_p> alias_ddrs; > + vec<ddr_p> dependences; > + dependences.create (10); > + hash_table<ddr_entry_hasher> ddr_table (15); > + rdg_compute_data_dependence (rdg, loop_nest, &datarefs, > + &dependences, &ddr_table); > + > + /* We can't do runtime alias check if niter is unknown for loop. */ > + tree niters = number_of_latch_executions (loop); > + bool rt_alias_check_p = (niters != NULL_TREE && niters != chrec_dont_know); > + > + auto_bitmap stmt_in_all_partitions; > auto_vec<struct partition *, 3> partitions; > - rdg_build_partitions (rdg, stmts, &partitions); > + bitmap_set_range (stmt_in_all_partitions, 0, rdg->n_vertices); > + rdg_build_partitions (rdg, &ddr_table, stmts, > + &partitions, stmt_in_all_partitions); > > any_builtin = false; > FOR_EACH_VEC_ELT (partitions, i, partition) > { > - classify_partition (loop, rdg, partition); > + classify_partition (loop, rdg, &ddr_table, > + partition, stmt_in_all_partitions); > any_builtin |= partition_builtin_p (partition); > } > > @@ -1508,13 +2516,7 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > for (++i; partitions.iterate (i, &partition); ++i) > if (!partition_builtin_p (partition)) > { > - if (dump_file && (dump_flags & TDF_DETAILS)) > - { > - fprintf (dump_file, "fusing non-builtin partitions\n"); > - dump_bitmap (dump_file, into->stmts); > - dump_bitmap (dump_file, partition->stmts); > - } > - partition_merge_into (into, partition); > + partition_merge_into (into, partition, FUSE_NON_BUILTIN); > partitions.unordered_remove (i); > partition_free (partition); > i--; > @@ -1530,21 +2532,14 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > for (i = i + 1; partitions.iterate (i, &partition); ++i) > if (partition_reduction_p (partition)) > { > - if (dump_file && (dump_flags & TDF_DETAILS)) > - { > - fprintf (dump_file, "fusing partitions\n"); > - dump_bitmap (dump_file, into->stmts); > - dump_bitmap (dump_file, partition->stmts); > - fprintf (dump_file, "because they have reductions\n"); > - } > - partition_merge_into (into, partition); > + partition_merge_into (into, partition, FUSE_REDUCTION); > partitions.unordered_remove (i); > partition_free (partition); > i--; > } > > - /* Apply our simple cost model - fuse partitions with similar > - memory accesses. */ > + /* Apply our simple cost model - fuse partitions with shared memory > + accesses. */ > for (i = 0; partitions.iterate (i, &into); ++i) > { > bool changed = false; > @@ -1553,17 +2548,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > for (int j = i + 1; > partitions.iterate (j, &partition); ++j) > { > - if (similar_memory_accesses (rdg, into, partition)) > + if (share_memory_accesses (rdg, into, partition)) > { > - if (dump_file && (dump_flags & TDF_DETAILS)) > - { > - fprintf (dump_file, "fusing partitions\n"); > - dump_bitmap (dump_file, into->stmts); > - dump_bitmap (dump_file, partition->stmts); > - fprintf (dump_file, "because they have similar " > - "memory accesses\n"); > - } > - partition_merge_into (into, partition); > + partition_merge_into (into, partition, FUSE_SHARE_REF); > partitions.unordered_remove (j); > partition_free (partition); > j--; > @@ -1581,111 +2568,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > /* Build the partition dependency graph. */ > if (partitions.length () > 1) > { > - pg = new_graph (partitions.length ()); > - struct pgdata { > - struct partition *partition; > - vec<data_reference_p> writes; > - vec<data_reference_p> reads; > - }; > -#define PGDATA(i) ((pgdata *)(pg->vertices[i].data)) > - for (i = 0; partitions.iterate (i, &partition); ++i) > - { > - vertex *v = &pg->vertices[i]; > - pgdata *data = new pgdata; > - data_reference_p dr; > - /* FIXME - leaks. */ > - v->data = data; > - bitmap_iterator bi; > - unsigned j; > - data->partition = partition; > - data->reads = vNULL; > - data->writes = vNULL; > - EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, j, bi) > - for (int k = 0; RDG_DATAREFS (rdg, j).iterate (k, &dr); ++k) > - if (DR_IS_READ (dr)) > - data->reads.safe_push (dr); > - else > - data->writes.safe_push (dr); > - } > - struct partition *partition1, *partition2; > - for (i = 0; partitions.iterate (i, &partition1); ++i) > - for (int j = i + 1; partitions.iterate (j, &partition2); ++j) > - { > - /* dependence direction - 0 is no dependence, -1 is back, > - 1 is forth, 2 is both (we can stop then, merging will occur). */ > - int dir = 0; > - dir = pg_add_dependence_edges (rdg, loop_nest, dir, > - PGDATA(i)->writes, > - PGDATA(j)->reads); > - if (dir != 2) > - dir = pg_add_dependence_edges (rdg, loop_nest, dir, > - PGDATA(i)->reads, > - PGDATA(j)->writes); > - if (dir != 2) > - dir = pg_add_dependence_edges (rdg, loop_nest, dir, > - PGDATA(i)->writes, > - PGDATA(j)->writes); > - if (dir == 1 || dir == 2) > - add_edge (pg, i, j); > - if (dir == -1 || dir == 2) > - add_edge (pg, j, i); > - } > - > - /* Add edges to the reduction partition (if any) to force it last. */ > - unsigned j; > - for (j = 0; partitions.iterate (j, &partition); ++j) > - if (partition_reduction_p (partition)) > - break; > - if (j < partitions.length ()) > - { > - for (unsigned i = 0; partitions.iterate (i, &partition); ++i) > - if (i != j) > - add_edge (pg, i, j); > - } > - > - /* Compute partitions we cannot separate and fuse them. */ > - num_sccs = graphds_scc (pg, NULL); > - for (i = 0; i < num_sccs; ++i) > - { > - struct partition *first; > - int j; > - for (j = 0; partitions.iterate (j, &first); ++j) > - if (pg->vertices[j].component == i) > - break; > - for (j = j + 1; partitions.iterate (j, &partition); ++j) > - if (pg->vertices[j].component == i) > - { > - if (dump_file && (dump_flags & TDF_DETAILS)) > - { > - fprintf (dump_file, "fusing partitions\n"); > - dump_bitmap (dump_file, first->stmts); > - dump_bitmap (dump_file, partition->stmts); > - fprintf (dump_file, "because they are in the same " > - "dependence SCC\n"); > - } > - partition_merge_into (first, partition); > - partitions[j] = NULL; > - partition_free (partition); > - PGDATA (j)->partition = NULL; > - } > - } > - > - /* Now order the remaining nodes in postorder. */ > - qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp); > - partitions.truncate (0); > - for (i = 0; i < pg->n_vertices; ++i) > - { > - pgdata *data = PGDATA (i); > - if (data->partition) > - partitions.safe_push (data->partition); > - data->reads.release (); > - data->writes.release (); > - delete data; > - } > - gcc_assert (partitions.length () == (unsigned)num_sccs); > - free_graph (pg); > + merge_dep_scc_partitions (rdg, &ddr_table, &partitions, > + rt_alias_check_p ? NULL : &alias_ddrs); > + alias_ddrs.truncate (0); > + if (rt_alias_check_p && partitions.length () > 1) > + break_alias_scc_partitions (rdg, &ddr_table, &partitions, &alias_ddrs); > } > > + finalize_partitions (&partitions, &alias_ddrs); > + > nbp = partitions.length (); > if (nbp == 0 > || (nbp == 1 && !partition_builtin_p (partitions[0])) > @@ -1695,8 +2586,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > goto ldist_done; > } > > + if (version_for_distribution_p (&partitions, &alias_ddrs)) > + version_loop_by_alias_check (loop, &alias_ddrs); > + > if (dump_file && (dump_flags & TDF_DETAILS)) > - dump_rdg_partitions (dump_file, partitions); > + { > + fprintf (dump_file, > + "distribute loop <%d> into partitions:\n", loop->num); > + dump_rdg_partitions (dump_file, partitions); > + } > > FOR_EACH_VEC_ELT (partitions, i, partition) > { > @@ -1706,7 +2604,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, > } > > ldist_done: > - > + free_data_refs (datarefs); > + free_dependence_relations (dependences); > + ddr_table.empty (); > FOR_EACH_VEC_ELT (partitions, i, partition) > partition_free (partition); > > @@ -1758,6 +2658,22 @@ pass_loop_distribution::execute (function *fun) > control_dependences *cd = NULL; > auto_vec<loop_p> loops_to_be_destroyed; > > + /* Compute topological order for basic blocks. Topological order is > + needed because data dependence is computed for data references in > + lexicographical order */ > + if (bb_top_order_index == NULL) > + { > + int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); > + > + bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun)); > + bb_top_order_index_size > + = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, true); > + for (int i = 0; i < bb_top_order_index_size; i++) > + bb_top_order_index[rpo[i]] = i; > + > + free (rpo); > + } > + > FOR_ALL_BB_FN (bb, fun) > { > gimple_stmt_iterator gsi; > @@ -1767,6 +2683,9 @@ pass_loop_distribution::execute (function *fun) > gimple_set_uid (gsi_stmt (gsi), -1); > } > > + FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) > + loop->aux = NULL; > + > /* We can at the moment only distribute non-nested loops, thus restrict > walking to innermost loops. */ > FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) > @@ -1776,6 +2695,10 @@ pass_loop_distribution::execute (function *fun) > int num = loop->num; > unsigned int i; > > + /* Skip distributed loops. */ > + if (loop->aux != NULL) > + continue; > + > /* If the loop doesn't have a single exit we will fail anyway, > so do that early. */ > if (!single_exit (loop)) > @@ -1862,16 +2785,26 @@ out: > fprintf (dump_file, "Loop %d is the same.\n", num); > } > > + FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) > + loop->aux = NULL; > + > if (cd) > delete cd; > > + if (bb_top_order_index != NULL) > + { > + free (bb_top_order_index); > + bb_top_order_index = NULL; > + bb_top_order_index_size = 0; > + } > + > if (changed) > { > /* Destroy loop bodies that could not be reused. Do this late as we > otherwise can end up refering to stale data in control dependences. */ > unsigned i; > FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop) > - destroy_loop (loop); > + destroy_loop (loop); > > /* Cached scalar evolutions now may refer to wrong or non-existing > loops. */ > diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c > index 1bef2e4..0d83d33 100644 > --- a/gcc/tree-vectorizer.c > +++ b/gcc/tree-vectorizer.c > @@ -469,6 +469,63 @@ fold_loop_vectorized_call (gimple *g, tree value) > } > } > > +/* If LOOP has been versioned during loop distribution, return the internal > + call guarding it. */ > + > +static gimple * > +vect_loop_dist_alias_call (struct loop *loop) > +{ > + gimple_stmt_iterator gsi; > + gimple *g; > + basic_block bb = loop_preheader_edge (loop)->src; > + struct loop *outer_loop = bb->loop_father; > + > + /* Look upward in dominance tree. */ > + for (; bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && bb->loop_father == outer_loop; > + bb = get_immediate_dominator (CDI_DOMINATORS, bb)) > + { > + g = last_stmt (bb); > + if (g == NULL || gimple_code (g) != GIMPLE_COND) > + continue; > + > + gsi = gsi_for_stmt (g); > + gsi_prev (&gsi); > + if (gsi_end_p (gsi)) > + continue; > + > + g = gsi_stmt (gsi); > + /* The guarding internal function call must have the same distribution > + alias id. */ > + if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS) > + && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->ldist_alias_id)) > + return g; > + } > + return NULL; > +} > + > +/* Fold LOOP_DIST_ALIAS internal call stmt according to KEEP_P and update > + any immediate uses of it's LHS. Stmt is folded to its second argument > + if KEEP_P is true, otherwise to boolean_false_node. */ > + > +static void > +fold_loop_dist_alias_call (gimple *g, bool keep_p) > +{ > + tree lhs = gimple_call_lhs (g); > + use_operand_p use_p; > + imm_use_iterator iter; > + gimple *use_stmt; > + gimple_stmt_iterator gsi = gsi_for_stmt (g); > + tree folded_value = keep_p ? gimple_call_arg (g, 1) : boolean_false_node; > + > + update_call_from_tree (&gsi, folded_value); > + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) > + { > + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) > + SET_USE (use_p, folded_value); > + update_stmt (use_stmt); > + } > +} > + > /* Set the uids of all the statements in basic blocks inside loop > represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal > call guarding the loop which has been if converted. */ > @@ -595,7 +652,7 @@ vectorize_loops (void) > else > { > loop_vec_info loop_vinfo, orig_loop_vinfo; > - gimple *loop_vectorized_call; > + gimple *loop_vectorized_call, *loop_dist_alias_call; > try_vectorize: > if (!((flag_tree_loop_vectorize > && optimize_loop_nest_for_speed_p (loop)) > @@ -603,6 +660,7 @@ vectorize_loops (void) > continue; > orig_loop_vinfo = NULL; > loop_vectorized_call = vect_loop_vectorized_call (loop); > + loop_dist_alias_call = vect_loop_dist_alias_call (loop); > vectorize_epilogue: > vect_location = find_loop_location (loop); > if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION > @@ -710,6 +768,12 @@ vectorize_loops (void) > loop_vectorized_call = NULL; > ret |= TODO_cleanup_cfg; > } > + if (loop_dist_alias_call) > + { > + fold_loop_dist_alias_call (loop_dist_alias_call, true); > + loop_dist_alias_call = NULL; > + ret |= TODO_cleanup_cfg; > + } > > if (new_loop) > { > @@ -743,6 +807,15 @@ vectorize_loops (void) > { > fold_loop_vectorized_call (g, boolean_false_node); > ret |= TODO_cleanup_cfg; > + g = NULL; > + } > + else > + g = vect_loop_dist_alias_call (loop); > + > + if (g) > + { > + fold_loop_dist_alias_call (g, false); > + ret |= TODO_cleanup_cfg; > } > } > } > -- 1.9.1 >
On Thu, Jun 8, 2017 at 3:48 AM, kugan <kugan.vivekanandarajah@linaro.org> wrote: > Hi Bin, > >> + >> +/* In reduced dependence graph RDG for loop distribution, return true if >> + dependence between references DR1 and DR2 may create dependence cycle >> + and such dependence cycle can't be resolved by runtime alias check. >> */ >> + >> +static bool >> +possible_data_dep_cycle_p (struct graph *rdg, >> + hash_table<ddr_entry_hasher> *ddr_table, >> + data_reference_p dr1, data_reference_p dr2) > > > This name seems to be misleading a bit. It is basically dependence test ? Of > course this can lead to a cycle but looks like possible_data_dep_p would be > better. This tests dependence between statements in one partition. It indicates a must dependence cycle if the function returns true, I suppose data_dep_in_cycle_p should be better. > >> +{ >> + struct data_dependence_relation *ddr; >> + >> + /* Re-shuffle data-refs to be in topological order. */ >> + if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) >> + > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) >> + std::swap (dr1, dr2); >> + >> + ddr = get_ddr (rdg, ddr_table, dr1, dr2); >> + >> + /* In case something goes wrong in data dependence analysis. */ >> + if (ddr == NULL) >> + return true; >> + /* In case of no data dependence. */ >> + else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) >> + return false; >> + /* Or the data dependence can be resolved by compilation time alias >> + check. */ >> + else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)), >> + get_alias_set (DR_REF (dr2)))) >> + return false; >> + /* For unknown data dependence or known data dependence which can't be >> + expressed in classic distance vector, we check if it can be resolved >> + by runtime alias check. If yes, we still consider data dependence >> + as won't introduce data dependence cycle. */ >> + else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know >> + || DDR_NUM_DIST_VECTS (ddr) == 0) > > > You have already handled chrec_known above. Can you still have known data > dependence which can't be expressed in classic distance vector ? I don't know the very details in data dependence analyzer, only I tend to believe it's possible by code. Reading build_classic_dist_vector gives: if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE) return false; //... dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr)); if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr), dist_v, &init_b, &index_carry)) return false; Looks like we can have DDR_ARE_DEPENDENT (ddr) == NULL_TREE without classic distance vector. Or the code could be simplified vice versa. > >> (dr1) >> + || !DR_BASE_ADDRESS (dr2) || !DR_OFFSET (dr2) || !DR_INIT >> (dr2) >> + || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1)) >> + || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2)) >> + || res == 0) >> + this_dir = 2; >> + /* If it's possible to do runtime alias check, simply record >> the >> + ddr. */ >> + else if (alias_ddrs != NULL) >> + alias_ddrs->safe_push (ddr); > > > If alias_ddrs is not passed (i.e. NULL), shouldn't this_ddr = 2. May be add > an assert for alias_ddrs ? No, it's intended to ignore the dependence when alias_ddrs == NULL, I will add more comment for this. > >> +/* Build and return partition dependence graph for PARTITIONS. RDG is >> + reduced dependence graph for the loop to be distributed. DDR_TABLE >> + is hash table contains all data dependence relations. ALIAS_DDRS is >> + a data dependence relations vector for temporary use. If ALIAS_DDRS >> + is NULL, dependence which can be resolved by runtime alias check will >> + not be considered, vice versa. */ >> + >> +static struct graph * >> +build_partition_graph (struct graph *rdg, >> + hash_table<ddr_entry_hasher> *ddr_table, >> + vec<struct partition *> *partitions, >> + vec<ddr_p> *alias_ddrs) > > > Why do you pass alias_ddrs to this. alias_ddrs does not pass any data or > return any. It can be defined in the function and used there. If you are > using this to indicate runtime alias check should be considered, you can > define a different bool for that ? I need to pass vector at two end of function calling stack, so I tried to use vector pointer parameter for all related functions. Apparently this causes confusion for you, I will try the other way by using bool parameter in next version patch. > >> +{ >> + >> +static void >> +break_alias_scc_partitions (struct graph *rdg, >> + hash_table<ddr_entry_hasher> *ddr_table, >> + vec<struct partition *> *partitions, >> + vec<ddr_p> *alias_ddrs) > > > I am not sure I understand this. When you are in pg_add_dependence_edges, > when you record alias_ddrs for runtime checking you set this_dur io 1. That > means you have broken the dpendency there itself. Were you planning to keep No, it's not. And thanks for catching this, it's in actuality a mistake to set this_dir to 1 here. I will explicitly set this_dir to 0 for alias case. Setting it to 1 changes "alias" dependence into "true" dependence, which could corrupt distribution opportunities. > this_dir = 2 and break the dependency here ? The dependence is to be broken in this function. Thanks for reviewing, I am splitting patch into small ones and will address above comments. BTW, please remove long un-commented code piece when reviewing, I scrolled a lot to find where the comment is. Thanks, bin
From 51633dd096358b42672c42ab01a40cf3379c36d9 Mon Sep 17 00:00:00 2001 From: amker <amker@amker-laptop.(none)> Date: Mon, 29 May 2017 21:31:09 +0800 Subject: [PATCH 4/5] loop-distribution-20170526.txt --- gcc/cfgloop.h | 9 + gcc/cfgloopmanip.c | 3 +- gcc/internal-fn.c | 8 + gcc/internal-fn.def | 1 + gcc/testsuite/gcc.dg/tree-ssa/ldist-12.c | 3 +- gcc/testsuite/gcc.dg/tree-ssa/ldist-13.c | 5 +- gcc/testsuite/gcc.dg/tree-ssa/ldist-14.c | 5 +- gcc/testsuite/gcc.dg/tree-ssa/ldist-4.c | 4 +- gcc/tree-loop-distribution.c | 1429 ++++++++++++++++++++++++------ gcc/tree-vectorizer.c | 75 +- 10 files changed, 1282 insertions(+), 260 deletions(-) diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index a8bec1d..be4187a 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -225,6 +225,15 @@ struct GTY ((chain_next ("%h.next"))) loop { builtins. */ tree simduid; + /* For loops generated by distribution with runtime alias checks, this + is a unique identifier of the original distributed loop. Generally + it is the number of the original loop. IFN_LOOP_DIST_ALIAS builtin + uses this id as its first argument. Give a loop with an id, we can + look upward in dominance tree for the corresponding IFN_LOOP_DIST_ALIAS + buildin. Note this id has no meanling after IFN_LOOP_DIST_ALIAS is + folded and eliminated. */ + int ldist_alias_id; + /* Upper bound on number of iterations of a loop. */ struct nb_iter_bound *bounds; diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 3e34aad..b3e9d4c 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1647,7 +1647,8 @@ force_single_succ_latches (void) THEN_PROB is the probability of then branch of the condition. ELSE_PROB is the probability of else branch. Note that they may be both - REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED. */ + REG_BR_PROB_BASE when condition is IFN_LOOP_VECTORIZED or + IFN_LOOP_DIST_ALIAS. */ static basic_block lv_adjust_loop_entry_edge (basic_block first_head, basic_block second_head, diff --git a/gcc/internal-fn.c b/gcc/internal-fn.c index 75fe027..96e40cb 100644 --- a/gcc/internal-fn.c +++ b/gcc/internal-fn.c @@ -2250,6 +2250,14 @@ expand_LOOP_VECTORIZED (internal_fn, gcall *) gcc_unreachable (); } +/* This should get folded in tree-vectorizer.c. */ + +static void +expand_LOOP_DIST_ALIAS (internal_fn, gcall *) +{ + gcc_unreachable (); +} + /* Expand MASK_LOAD call STMT using optab OPTAB. */ static void diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def index e162d81..79c19fb 100644 --- a/gcc/internal-fn.def +++ b/gcc/internal-fn.def @@ -158,6 +158,7 @@ DEF_INTERNAL_FN (GOMP_SIMD_LAST_LANE, ECF_CONST | ECF_LEAF | ECF_NOTHROW, NULL) DEF_INTERNAL_FN (GOMP_SIMD_ORDERED_START, ECF_LEAF | ECF_NOTHROW, NULL) DEF_INTERNAL_FN (GOMP_SIMD_ORDERED_END, ECF_LEAF | ECF_NOTHROW, NULL) DEF_INTERNAL_FN (LOOP_VECTORIZED, ECF_NOVOPS | ECF_LEAF | ECF_NOTHROW, NULL) +DEF_INTERNAL_FN (LOOP_DIST_ALIAS, ECF_NOVOPS | ECF_LEAF | ECF_NOTHROW, NULL) DEF_INTERNAL_FN (ANNOTATE, ECF_CONST | ECF_LEAF | ECF_NOTHROW, NULL) DEF_INTERNAL_FN (UBSAN_NULL, ECF_LEAF | ECF_NOTHROW, ".R.") DEF_INTERNAL_FN (UBSAN_BOUNDS, ECF_LEAF | ECF_NOTHROW, NULL) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-12.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-12.c index 53551ca..625dd92 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ldist-12.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-12.c @@ -18,4 +18,5 @@ int foo (int * __restrict__ ia, return oya[22] + oyb[21]; } -/* { dg-final { scan-tree-dump-times "distributed: split to 2 loops" 1 "ldist" } } */ +/* Distributing the loop doesn't expose more parallelism. */ +/* { dg-final { scan-tree-dump-times "distributed: split to 2 loops" 0 "ldist" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-13.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-13.c index ba39d4d..8c9fd56 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ldist-13.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-13.c @@ -16,6 +16,5 @@ float foo (int n) return tmp; } -/* We should apply loop distribution. */ - -/* { dg-final { scan-tree-dump "Loop 1 distributed: split to 2 loops" "ldist" } } */ +/* Distributing the loop doesn't expose more parallelism. */ +/* { dg-final { scan-tree-dump-not "Loop 1 distributed: split to 2 loops" "ldist" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-14.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-14.c index 48c1040..fa4d1a8 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ldist-14.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-14.c @@ -21,6 +21,5 @@ float foo (int n) return tmp; } -/* We should apply loop distribution. */ - -/* { dg-final { scan-tree-dump "Loop 1 distributed: split to 2 loops" "ldist" } } */ +/* Distributing the loop doesn't expose more parallelism. */ +/* { dg-final { scan-tree-dump-not "Loop 1 distributed: split to 2 loops" "ldist" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-4.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-4.c index c36daf071..4def9b4 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ldist-4.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-4.c @@ -20,7 +20,5 @@ int loop1 (int k) return b[100-1][1]; } -/* The current cost model fuses the two partitions because they have - similar memory accesses. */ -/* { dg-final { scan-tree-dump "similar memory accesses" "ldist" } } */ +/* Distributing inner loop doesn't expose more parallelism. */ /* { dg-final { scan-tree-dump-times "distributed: split to 2 loops" 0 "ldist" } } */ diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index a60454b..05821b3 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -36,10 +36,58 @@ along with GCC; see the file COPYING3. If not see | D(I) = A(I-1)*E |ENDDO - This pass uses an RDG, Reduced Dependence Graph built on top of the - data dependence relations. The RDG is then topologically sorted to - obtain a map of information producers/consumers based on which it - generates the new loops. */ + Loop distribution is the dual of loop fusion. It separates statements + of a loop (or loop nest) into multiple loops (or loop nests) with the + same loop header. The major goal is to separate statements which may + be vectorized from those that can't. This pass implements distribution + in the following steps: + + 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 dependences between statements. + 3) Apart from RDG, compute data dependences 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 parallelly; 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 dependences. + The vertices (PG:V) model all partitions and the edges (PG:E) model + all data dependences 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 + dependences because of possible alias relation of data references. + We categorize PG's edge to two types: "true" edge that represents + compilation time known data dependences; "alias" edge for all other + data dependences. + 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge + partitions in each strong connected commponent (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 dependences of the removed "alias" edges. Create + runtime alias checks for collected data dependences. + 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. + + TODO: + 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 + data reuse. */ #include "config.h" #include "system.h" @@ -51,6 +99,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-pass.h" #include "ssa.h" #include "gimple-pretty-print.h" +#include "alias.h" #include "fold-const.h" #include "cfganal.h" #include "gimple-iterator.h" @@ -66,6 +115,43 @@ along with GCC; see the file COPYING3. If not see #include "tree-vectorizer.h" +/* Hashtable entry for data reference relation. */ +struct ddr_entry +{ + data_reference_p a; + data_reference_p b; + ddr_p ddr; + hashval_t hash; +}; + +/* Hashtable helpers. */ + +struct ddr_entry_hasher : delete_ptr_hash <ddr_entry> +{ + static inline hashval_t hash (const ddr_entry *); + static inline bool equal (const ddr_entry *, const ddr_entry *); +}; + +/* Hash function for data reference relation. */ + +inline hashval_t +ddr_entry_hasher::hash (const ddr_entry *entry) +{ + return entry->hash; +} + +/* Hash table equality function for data reference relation. */ + +inline bool +ddr_entry_hasher::equal (const ddr_entry *entry1, const ddr_entry *entry2) +{ + return (entry1->hash == entry2->hash + && DR_STMT (entry1->a) == DR_STMT (entry2->a) + && DR_STMT (entry1->b) == DR_STMT (entry2->b) + && operand_equal_p (DR_REF (entry1->a), DR_REF (entry2->a), 0) + && operand_equal_p (DR_REF (entry1->b), DR_REF (entry2->b), 0)); +} + /* A Reduced Dependence Graph (RDG) vertex representing a statement. */ struct rdg_vertex { @@ -373,16 +459,39 @@ create_rdg_vertices (struct graph *rdg, vec<gimple *> stmts, loop_p loop, return true; } -/* Initialize STMTS with all the statements of LOOP. The order in - which we discover statements is important as - generate_loops_for_partition is using the same traversal for - identifying statements in loop copies. */ +/* Array mapping basic block's index to its topological order. */ +static int *bb_top_order_index; +/* And size of the array. */ +static int bb_top_order_index_size; + +/* If X has a smaller topological sort number than Y, returns -1; + if greater, returns 1. */ + +static int +bb_top_order_cmp (const void *x, const void *y) +{ + basic_block bb1 = *(const basic_block *) x; + basic_block bb2 = *(const basic_block *) y; + + gcc_assert (bb1->index < bb_top_order_index_size + && bb2->index < bb_top_order_index_size); + gcc_assert (bb1 == bb2 + || bb_top_order_index[bb1->index] + != bb_top_order_index[bb2->index]); + + return (bb_top_order_index[bb1->index] - bb_top_order_index[bb2->index]); +} + +/* Initialize STMTS with all the statements of LOOP. We use topological + order to discover all statements. The order is important because + generate_loops_for_partition is using the same traversal for identifying + statements in loop copies. */ static void stmts_from_loop (struct loop *loop, vec<gimple *> *stmts) { unsigned int i; - basic_block *bbs = get_loop_body_in_dom_order (loop); + basic_block *bbs = get_loop_body_in_custom_order (loop, bb_top_order_cmp); for (i = 0; i < loop->num_nodes; i++) { @@ -423,7 +532,7 @@ free_rdg (struct graph *rdg) if (v->data) { gimple_set_uid (RDGV_STMT (v), -1); - free_data_refs (RDGV_DATAREFS (v)); + (RDGV_DATAREFS (v)).release (); free (v->data); } } @@ -436,19 +545,17 @@ free_rdg (struct graph *rdg) scalar dependence. */ static struct graph * -build_rdg (vec<loop_p> loop_nest, control_dependences *cd) +build_rdg (vec<loop_p> loop_nest, control_dependences *cd, + vec<data_reference_p> *datarefs) { struct graph *rdg; - vec<data_reference_p> datarefs; /* Create the RDG vertices from the stmts of the loop nest. */ auto_vec<gimple *, 10> stmts; stmts_from_loop (loop_nest[0], &stmts); rdg = new_graph (stmts.length ()); - datarefs.create (10); - if (!create_rdg_vertices (rdg, stmts, loop_nest[0], &datarefs)) + if (!create_rdg_vertices (rdg, stmts, loop_nest[0], datarefs)) { - datarefs.release (); free_rdg (rdg); return NULL; } @@ -458,28 +565,45 @@ build_rdg (vec<loop_p> loop_nest, control_dependences *cd) if (cd) create_rdg_cd_edges (rdg, cd, loop_nest[0]); - datarefs.release (); - return rdg; } - - +/* Builtin kind of distributed loop. */ enum partition_kind { PKIND_NORMAL, PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE }; +/* Type of distributed loop. */ +enum partition_type { + /* The distributed loop can be executed parallelly. */ + PTYPE_PARALLEL = 0, + /* The distributed loop has to be executed sequentially. */ + PTYPE_SEQUENTIAL +}; + +/* Partition for loop distribution. */ struct partition { + /* Statements of the partition. */ bitmap stmts; + /* Loops of the partition. */ bitmap loops; + /* True if the partition defines variable which is used outside of loop. */ bool reduction_p; + /* For builtin partition, true if it executes one iteration more than + number of loop (latch) iterations. */ bool plus_one; enum partition_kind kind; + enum partition_type type; /* data-references a kind != PKIND_NORMAL partition is about. */ data_reference_p main_dr; data_reference_p secondary_dr; + /* Number of loop (latch) iterations. */ tree niter; + /* Read data references in the partition. */ + vec<data_reference_p> reads; + /* Write data references in the partition. */ + vec<data_reference_p> writes; }; @@ -493,6 +617,8 @@ partition_alloc (bitmap stmts, bitmap loops) partition->loops = loops ? loops : BITMAP_ALLOC (NULL); partition->reduction_p = false; partition->kind = PKIND_NORMAL; + partition->reads = vNULL; + partition->writes = vNULL; return partition; } @@ -503,6 +629,8 @@ partition_free (partition *partition) { BITMAP_FREE (partition->stmts); BITMAP_FREE (partition->loops); + partition->reads.release (); + partition->writes.release (); free (partition); } @@ -522,15 +650,48 @@ partition_reduction_p (partition *partition) return partition->reduction_p; } +/* Partitions are fused because of different reasons. */ +enum fuse_type +{ + FUSE_NON_BUILTIN = 0, + FUSE_REDUCTION = 1, + FUSE_SHARE_REF = 2, + FUSE_SAME_SCC = 3, + FUSE_FINALIZE = 4 +}; + +/* Description on different fusing reason. */ +static const char *fuse_message[] = { + "they are non-builtins", + "they have reductions", + "they have shared memory refs", + "they are in the same dependence scc", + "there is no point to distribute loop"}; + /* Merge PARTITION into the partition DEST. */ static void -partition_merge_into (partition *dest, partition *partition) +partition_merge_into (partition *dest, partition *partition, enum fuse_type ft) { dest->kind = PKIND_NORMAL; + if (dest->type == PTYPE_PARALLEL) + dest->type = partition->type; + bitmap_ior_into (dest->stmts, partition->stmts); if (partition_reduction_p (partition)) dest->reduction_p = true; + + dest->reads.safe_splice (partition->reads); + dest->writes.safe_splice (partition->writes); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Fuse partitions because %s:\n", fuse_message[ft]); + fprintf (dump_file, " Part 1: "); + dump_bitmap (dump_file, dest->stmts); + fprintf (dump_file, " Part 2: "); + dump_bitmap (dump_file, partition->stmts); + } } @@ -618,8 +779,11 @@ generate_loops_for_partition (struct loop *loop, partition *partition, if (copy_p) { + int ldist_alias_id = loop->num; loop = copy_loop_before (loop); gcc_assert (loop != NULL); + loop->ldist_alias_id = ldist_alias_id; + loop->aux = (void *)loop; create_preheader (loop, CP_SIMPLE_PREHEADERS); create_bb_after_loop (loop); } @@ -986,17 +1150,110 @@ generate_code_for_partition (struct loop *loop, return false; } +/* Record data dependence relation in hashtable. */ + +static void +record_ddr (struct graph *rdg, hash_table<ddr_entry_hasher> *ddr_table, + data_reference_p a, data_reference_p b, + struct data_dependence_relation *ddr) +{ + struct ddr_entry ent, **slot; + + gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a)) + <= rdg_vertex_for_stmt (rdg, DR_STMT (b))); + ent.a = a; + ent.b = b; + ent.hash = iterative_hash_expr (DR_REF (a), 0); + ent.hash = iterative_hash_expr (DR_REF (b), ent.hash); + + slot = ddr_table->find_slot (&ent, INSERT); + if (*slot == NULL) + { + *slot = new ddr_entry (); + (*slot)->a = a; + (*slot)->b = b; + (*slot)->ddr = ddr; + (*slot)->hash = ent.hash; + } +} + +/* Given data references A and B in reduced dependence graph RDG, find + and return ddr from hash table DDR_TABLE. Return NULL if such ddr + doesn't exist. */ + +static data_dependence_relation * +get_ddr (struct graph *rdg, hash_table<ddr_entry_hasher> *ddr_table, + data_reference_p a, data_reference_p b) +{ + struct ddr_entry ent, **slot; + + gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a)) + <= rdg_vertex_for_stmt (rdg, DR_STMT (b))); + ent.a = a; + ent.b = b; + ent.hash = iterative_hash_expr (DR_REF (a), 0); + ent.hash = iterative_hash_expr (DR_REF (b), ent.hash); + slot = ddr_table->find_slot (&ent, NO_INSERT); + return slot != NULL ? (*slot)->ddr : NULL; +} + +/* In reduced dependence graph RDG for loop distribution, return true if + dependence between references DR1 and DR2 may create dependence cycle + and such dependence cycle can't be resolved by runtime alias check. */ + +static bool +possible_data_dep_cycle_p (struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, + data_reference_p dr1, data_reference_p dr2) +{ + struct data_dependence_relation *ddr; + + /* Re-shuffle data-refs to be in topological order. */ + if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) + > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) + std::swap (dr1, dr2); + + ddr = get_ddr (rdg, ddr_table, dr1, dr2); + + /* In case something goes wrong in data dependence analysis. */ + if (ddr == NULL) + return true; + /* In case of no data dependence. */ + else if (DDR_ARE_DEPENDENT (ddr) == chrec_known) + return false; + /* Or the data dependence can be resolved by compilation time alias + check. */ + else if (!alias_sets_conflict_p (get_alias_set (DR_REF (dr1)), + get_alias_set (DR_REF (dr2)))) + return false; + /* For unknown data dependence or known data dependence which can't be + expressed in classic distance vector, we check if it can be resolved + by runtime alias check. If yes, we still consider data dependence + as won't introduce data dependence cycle. */ + else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know + || DDR_NUM_DIST_VECTS (ddr) == 0) + return !runtime_alias_check_p (ddr, NULL, true); + else if (DDR_NUM_DIST_VECTS (ddr) > 1) + return true; + else if (DDR_REVERSED_P (ddr) + || lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) + return false; + + return true; +} /* Returns a partition with all the statements needed for computing the vertex V of the RDG, also including the loop exit conditions. */ static partition * -build_rdg_partition_for_vertex (struct graph *rdg, int v) +build_rdg_partition_for_vertex (struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, int v) { partition *partition = partition_alloc (NULL, NULL); auto_vec<int, 3> nodes; - unsigned i; + unsigned i, j; int x; + data_reference_p dr, dr1, dr2; graphds_dfs (rdg, &v, 1, &nodes, false, NULL); @@ -1005,8 +1262,43 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) bitmap_set_bit (partition->stmts, x); bitmap_set_bit (partition->loops, loop_containing_stmt (RDG_STMT (rdg, x))->num); + + for (j = 0; RDG_DATAREFS (rdg, x).iterate (j, &dr); ++j) + { + /* Partition can only be executed sequentially if there is any + unknown data reference. */ + if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) + || !DR_INIT (dr) || !DR_STEP (dr)) + partition->type = PTYPE_SEQUENTIAL; + + if (DR_IS_READ (dr)) + partition->reads.safe_push (dr); + else + partition->writes.safe_push (dr); + } } + if (partition->type == PTYPE_SEQUENTIAL) + return partition; + + /* Further check if any data dependence prevents us from executing the + partition parallelly. */ + for (i = 0; partition->reads.iterate (i, &dr1); ++i) + for (j = 0; partition->writes.iterate (j, &dr2); ++j) + if (possible_data_dep_cycle_p (rdg, ddr_table, dr1, dr2)) + { + partition->type = PTYPE_SEQUENTIAL; + return partition; + } + + for (i = 0; partition->writes.iterate (i, &dr1); ++i) + for (j = i + 1; partition->writes.iterate (j, &dr2); ++j) + if (possible_data_dep_cycle_p (rdg, ddr_table, dr1, dr2)) + { + partition->type = PTYPE_SEQUENTIAL; + return partition; + } + return partition; } @@ -1014,7 +1306,9 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) For the moment we detect only the memset zero pattern. */ static void -classify_partition (loop_p loop, struct graph *rdg, partition *partition) +classify_partition (loop_p loop, struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, + partition *partition, bitmap stmt_in_all_partitions) { bitmap_iterator bi; unsigned i; @@ -1022,6 +1316,7 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) data_reference_p single_load, single_store; bool volatiles_p = false; bool plus_one = false; + bool has_reduction = false; partition->kind = PKIND_NORMAL; partition->main_dr = NULL; @@ -1036,16 +1331,24 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) if (gimple_has_volatile_ops (stmt)) volatiles_p = true; - /* If the stmt has uses outside of the loop mark it as reduction. */ + /* If the stmt is not included by all partitions and there is uses + outside of the loop, then mark the partition as reduction. */ if (stmt_has_scalar_dependences_outside_loop (loop, stmt)) { - partition->reduction_p = true; - return; + if (!bitmap_bit_p (stmt_in_all_partitions, i)) + { + partition->reduction_p = true; + return; + } + has_reduction = true; } } /* Perform general partition disqualification for builtins. */ if (volatiles_p + /* Simple workaround to prevent classifying the partition as builtin + if it contains any use outside of loop. */ + || has_reduction || !flag_tree_loop_distribute_patterns) return; @@ -1143,44 +1446,27 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) return; /* Now check that if there is a dependence this dependence is of a suitable form for memmove. */ - vec<loop_p> loops = vNULL; - ddr_p ddr; - loops.safe_push (loop); - ddr = initialize_data_dependence_relation (single_load, single_store, - loops); - compute_affine_dependence (ddr, loop); + ddr_p ddr = get_ddr (rdg, ddr_table, single_load, single_store); if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - { - free_dependence_relation (ddr); - loops.release (); - return; - } + return; + if (DDR_ARE_DEPENDENT (ddr) != chrec_known) { if (DDR_NUM_DIST_VECTS (ddr) == 0) - { - free_dependence_relation (ddr); - loops.release (); - return; - } + return; + lambda_vector dist_v; FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v) { int dist = dist_v[index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr))]; if (dist > 0 && !DDR_REVERSED_P (ddr)) - { - free_dependence_relation (ddr); - loops.release (); - return; - } + return; } partition->kind = PKIND_MEMMOVE; } else partition->kind = PKIND_MEMCPY; - free_dependence_relation (ddr); - loops.release (); partition->main_dr = single_store; partition->secondary_dr = single_load; partition->niter = nb_iter; @@ -1188,30 +1474,16 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) } } -/* For a data reference REF, return the declaration of its base - address or NULL_TREE if the base is not determined. */ - -static tree -ref_base_address (data_reference_p dr) -{ - tree base_address = DR_BASE_ADDRESS (dr); - if (base_address - && TREE_CODE (base_address) == ADDR_EXPR) - return TREE_OPERAND (base_address, 0); - - return base_address; -} - -/* Returns true when PARTITION1 and PARTITION2 have similar memory - accesses in RDG. */ +/* Returns true when PARTITION1 and PARTITION2 share the same memory + accesses in RDG. This is a simple data reuse cost model. */ static bool -similar_memory_accesses (struct graph *rdg, partition *partition1, - partition *partition2) +share_memory_accesses (struct graph *rdg, + partition *partition1, partition *partition2) { - unsigned i, j, k, l; - bitmap_iterator bi, bj; - data_reference_p ref1, ref2; + unsigned i, j; + data_reference_p dr1, dr2; + bitmap_iterator bi; /* First check whether in the intersection of the two partitions are any loads or stores. Common loads are the situation that happens @@ -1221,24 +1493,69 @@ similar_memory_accesses (struct graph *rdg, partition *partition1, || RDG_MEM_READS_STMT (rdg, i)) return true; - /* Then check all data-references against each other. */ - EXECUTE_IF_SET_IN_BITMAP (partition1->stmts, 0, i, bi) - if (RDG_MEM_WRITE_STMT (rdg, i) - || RDG_MEM_READS_STMT (rdg, i)) - EXECUTE_IF_SET_IN_BITMAP (partition2->stmts, 0, j, bj) - if (RDG_MEM_WRITE_STMT (rdg, j) - || RDG_MEM_READS_STMT (rdg, j)) - { - FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, i), k, ref1) - { - tree base1 = ref_base_address (ref1); - if (base1) - FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg, j), l, ref2) - if (base1 == ref_base_address (ref2)) - return true; - } - } + for (i = 0; partition1->reads.iterate (i, &dr1); ++i) + { + if (!DR_BASE_ADDRESS (dr1) + || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1)) + continue; + + for (j = 0; partition2->reads.iterate (j, &dr2); ++j) + { + if (!DR_BASE_ADDRESS (dr2) + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) + continue; + + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) + return true; + } + for (j = 0; partition2->writes.iterate (j, &dr2); ++j) + { + if (!DR_BASE_ADDRESS (dr2) + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) + continue; + + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) + return true; + } + } + + for (i = 0; partition1->writes.iterate (i, &dr1); ++i) + { + if (!DR_BASE_ADDRESS (dr1) + || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1)) + continue; + + for (j = 0; partition2->reads.iterate (j, &dr2); ++j) + { + if (!DR_BASE_ADDRESS (dr2) + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) + continue; + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) + return true; + } + for (j = 0; partition2->writes.iterate (j, &dr2); ++j) + { + if (!DR_BASE_ADDRESS (dr2) + || !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2)) + continue; + + if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), 0) + && operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), 0) + && operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), 0) + && operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), 0)) + return true; + } + } return false; } @@ -1248,8 +1565,10 @@ similar_memory_accesses (struct graph *rdg, partition *partition1, static void rdg_build_partitions (struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, vec<gimple *> starting_stmts, - vec<partition *> *partitions) + vec<partition *> *partitions, + bitmap stmt_in_all_partitions) { auto_bitmap processed; int i; @@ -1261,20 +1580,22 @@ rdg_build_partitions (struct graph *rdg, if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, - "ldist asked to generate code for vertex %d\n", v); + "LDist asked to generate code for vertex %d\n", v); /* If the vertex is already contained in another partition so is the partition rooted at it. */ if (bitmap_bit_p (processed, v)) continue; - partition *partition = build_rdg_partition_for_vertex (rdg, v); + partition *partition = build_rdg_partition_for_vertex (rdg, ddr_table, v); bitmap_ior_into (processed, partition->stmts); + bitmap_and_into (stmt_in_all_partitions, partition->stmts); if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "ldist useful partition:\n"); - dump_bitmap (dump_file, partition->stmts); + fprintf (dump_file, "LDist creates useful %s partition:\n", + partition->type == PTYPE_PARALLEL ? "parallel" : "sequent"); + bitmap_print (dump_file, partition->stmts, " ", "\n"); } partitions->safe_push (partition); @@ -1365,12 +1686,15 @@ partition_contains_all_rw (struct graph *rdg, } /* Compute partition dependence created by the data references in DRS1 - and DRS2 and modify and return DIR according to that. */ + and DRS2 and modify and return DIR according to that. If additional + dependence is introduced by possible alias between data references, + we record such data dependence relations in ALIAS_DDRS. */ static int -pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir, +pg_add_dependence_edges (struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, int dir, vec<data_reference_p> drs1, - vec<data_reference_p> drs2) + vec<data_reference_p> drs2, vec<ddr_p> *alias_ddrs) { data_reference_p dr1, dr2; @@ -1380,26 +1704,40 @@ pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir, for (int jj = 0; drs2.iterate (jj, &dr2); ++jj) { data_reference_p saved_dr1 = dr1; - int this_dir = 1; + int res, this_dir = 1; ddr_p ddr; - /* Re-shuffle data-refs to be in dominator order. */ + /* Re-shuffle data-refs to be in topological order. */ if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1)) > rdg_vertex_for_stmt (rdg, DR_STMT (dr2))) { std::swap (dr1, dr2); this_dir = -this_dir; } - ddr = initialize_data_dependence_relation (dr1, dr2, loops); - compute_affine_dependence (ddr, loops[0]); + ddr = get_ddr (rdg, ddr_table, dr1, dr2); if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - this_dir = 2; + { + res = data_ref_compare_tree (DR_BASE_ADDRESS (dr1), + DR_BASE_ADDRESS (dr2)); + /* Be conservative. If data references are not well analyzed, or + the two data references have the same base address and offset, + add dependence and consider it alias to each other. In other + words, the dependence can not be resolved by runtime alias + check. */ + if (!DR_BASE_ADDRESS (dr1) || !DR_OFFSET (dr1) || !DR_INIT (dr1) + || !DR_BASE_ADDRESS (dr2) || !DR_OFFSET (dr2) || !DR_INIT (dr2) + || !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1)) + || !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2)) + || res == 0) + this_dir = 2; + /* If it's possible to do runtime alias check, simply record the + ddr. */ + else if (alias_ddrs != NULL) + alias_ddrs->safe_push (ddr); + } else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) { if (DDR_REVERSED_P (ddr)) - { - std::swap (dr1, dr2); - this_dir = -this_dir; - } + this_dir = -this_dir; /* Known dependences can still be unordered througout the iteration space, see gcc.dg/tree-ssa/ldist-16.c. */ if (DDR_NUM_DIST_VECTS (ddr) != 1) @@ -1407,16 +1745,13 @@ pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir, /* If the overlap is exact preserve stmt order. */ else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) ; + /* Else as the distance vector is lexicographic positive + swap the dependence direction. */ else - { - /* Else as the distance vector is lexicographic positive - swap the dependence direction. */ - this_dir = -this_dir; - } + this_dir = -this_dir; } else this_dir = 0; - free_dependence_relation (ddr); if (this_dir == 2) return 2; else if (dir == 0) @@ -1439,6 +1774,663 @@ pgcmp (const void *v1_, const void *v2_) return v2->post - v1->post; } +/* Given loop nest LOOPS and its reduced dependence graph RDG for loop + distribution, compute data dependence relations for all data refs in + DATAREFS. Record dependence relation in DEPENDENCES and DDR_TABLE. */ + +static void +rdg_compute_data_dependence (struct graph *rdg, vec<loop_p> loops, + vec<data_reference_p> *datarefs, + vec<ddr_p> *dependences, + hash_table<ddr_entry_hasher> *ddr_table) +{ + int i, j; + data_reference_p a, b; + struct data_dependence_relation *ddr; + + FOR_EACH_VEC_ELT ((*datarefs), i, a) + for (j = i + 1; datarefs->iterate (j, &b); j++) + if (DR_IS_WRITE (a) || DR_IS_WRITE (b)) + { + ddr = initialize_data_dependence_relation (a, b, loops); + compute_affine_dependence (ddr, loops[0]); + dependences->safe_push (ddr); + /* Record data dependence relation in hash table for later + because it will be used multiple times. */ + record_ddr (rdg, ddr_table, a, b, ddr); + } +} + +/* Data attached to vertices of partition dependence graph. */ +struct pg_vdata +{ + /* ID of the corresponding partition. */ + int id; + /* The partition. */ + struct partition *partition; +}; + +/* Data attached to edges of partition dependence graph. */ +struct pg_edata +{ + /* If the dependence edge can be resolved by runtime alias check, + this vector contains data dependence relations for runtime alias + check. On the other hand, if the dependence edge is introduced + because of compilation time known data dependence, this vector + is contains nothing. */ + vec<ddr_p> alias_ddrs; +}; + +/* Callback data for traversing edges in graph. */ +struct pg_edge_callback_data +{ + /* Bitmap contains strong connected components should be merged. */ + bitmap sccs_to_merge; + /* Array constains component information for all vertices. */ + int *vertices_component; + /* Vector to record all data dependence relations which are needed + to break strong connected components by runtime alias checks. */ + vec<ddr_p> *alias_ddrs; +}; + +/* Initialize vertice's data for partition dependence graph PG with + PARTITIONS. */ +static void +init_partition_graph_vertices (struct graph *pg, + vec<struct partition *> *partitions) +{ + int i; + partition *partition; + struct pg_vdata *data; + + for (i = 0; partitions->iterate (i, &partition); ++i) + { + data = new pg_vdata; + pg->vertices[i].data = data; + data->id = i; + data->partition = partition; + } +} + +/* Add edge <I, J> to partition dependence graph PG. Attach vector of data + dependence relations to the EDGE if DDRS isn't NULL. */ + +static void +add_partition_graph_edge (struct graph *pg, int i, int j, vec<ddr_p> *ddrs) +{ + struct graph_edge *e = add_edge (pg, i, j); + + /* If the edge is attached with data dependence relations, it means this + dependence edge can be resolved by runtime alias checks. */ + if (ddrs != NULL) + { + struct pg_edata *data = new pg_edata; + + gcc_assert (ddrs->length () > 0); + e->data = data; + data->alias_ddrs = vNULL; + data->alias_ddrs.safe_splice (*ddrs); + } +} + +/* Callback function for graph travesal algorithm. It returns true + if edge E shouldn't be considered in graph when traversing it. */ + +static bool +pg_skip_alias_edge (struct graph_edge *e) +{ + struct pg_edata *data = (struct pg_edata *)e->data; + return (data != NULL && data->alias_ddrs.length () > 0); +} + +/* Callback function freeing data attached to edge E of graph. */ + +static void +free_partition_graph_edata_cb (struct graph *, struct graph_edge *e, void *) +{ + if (e->data != NULL) + { + struct pg_edata *data = (struct pg_edata *)e->data; + data->alias_ddrs.release (); + delete data; + } +} + +/* Free data attached to vertice of partition dependence graph PG. */ + +static void +free_partition_graph_vdata (struct graph *pg) +{ + int i; + struct pg_vdata *data; + + for (i = 0; i < pg->n_vertices; ++i) + { + data = (struct pg_vdata *)pg->vertices[i].data; + delete data; + } +} + +/* Build and return partition dependence graph for PARTITIONS. RDG is + reduced dependence graph for the loop to be distributed. DDR_TABLE + is hash table contains all data dependence relations. ALIAS_DDRS is + a data dependence relations vector for temporary use. If ALIAS_DDRS + is NULL, dependence which can be resolved by runtime alias check will + not be considered, vice versa. */ + +static struct graph * +build_partition_graph (struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, + vec<struct partition *> *partitions, + vec<ddr_p> *alias_ddrs) +{ + int i, j; + struct partition *partition1, *partition2; + graph *pg = new_graph (partitions->length ()); + + init_partition_graph_vertices (pg, partitions); + + for (i = 0; partitions->iterate (i, &partition1); ++i) + { + for (j = i + 1; partitions->iterate (j, &partition2); ++j) + { + /* dependence direction - 0 is no dependence, -1 is back, + 1 is forth, 2 is both (we can stop then, merging will occur). */ + int dir = 0; + + /* If the first partition has reduction, add back edge; if the + second partition has reduction, add forth edge. This makes + sure that reduction partition will be sorted as the last one. */ + if (partition_reduction_p (partition1)) + dir = -1; + else if (partition_reduction_p (partition2)) + dir = 1; + + /* Cleanup the temporary vector. */ + if (alias_ddrs != NULL) + alias_ddrs->truncate (0); + + dir = pg_add_dependence_edges (rdg, ddr_table, dir, + partition1->writes, + partition2->reads, alias_ddrs); + if (dir != 2) + dir = pg_add_dependence_edges (rdg, ddr_table, dir, + partition1->reads, + partition2->writes, alias_ddrs); + if (dir != 2) + dir = pg_add_dependence_edges (rdg, ddr_table, dir, + partition1->writes, + partition2->writes, alias_ddrs); + + /* Add edge to partition graph if there exists dependence. There + are two types of edges. One type edge is caused by compilation + time know dependence, this type can not be resolved by runtime + alias check. The other type can be resolved by runtime alias + check. */ + if (dir == 1 || dir == 2 + || (alias_ddrs != NULL && alias_ddrs->length () > 0)) + { + /* Attach data dependence relations to edge that can be resolved + by runtime alias check. */ + bool alias_edge_p = (dir != 1 && dir != 2); + add_partition_graph_edge (pg, i, j, + (alias_edge_p) ? alias_ddrs : NULL); + } + if (dir == -1 || dir == 2 + || (alias_ddrs != NULL && alias_ddrs->length () > 0)) + { + /* Attach data dependence relations to edge that can be resolved + by runtime alias check. */ + bool alias_edge_p = (dir != -1 && dir != 2); + add_partition_graph_edge (pg, j, i, + (alias_edge_p) ? alias_ddrs : NULL); + } + } + } + return pg; +} + +/* Sort partitions in PG by post order and store them in PARTITIONS. */ + +static void +sort_partitions_by_post_order (struct graph *pg, + vec<struct partition *> *partitions) +{ + int i; + struct pg_vdata *data; + + /* Now order the remaining nodes in postorder. */ + qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp); + partitions->truncate (0); + for (i = 0; i < pg->n_vertices; ++i) + { + data = (struct pg_vdata *)pg->vertices[i].data; + if (data->partition) + partitions->safe_push (data->partition); + } +} + +/* Given reduced dependence graph RDG and data dependences in DDR_TABLE, + merge strong connected components of PARTITIONS. ALIAS_DDRS is a data + dependence relations vector for temporary use. If ALIAS_DDRS is NULL, + dependence which can be resolved by runtime alias check will not be + considered in building dependence graph for partitions, vice versa. */ + +static void +merge_dep_scc_partitions (struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, + vec<struct partition *> *partitions, + vec<ddr_p> *alias_ddrs) +{ + struct partition *partition1, *partition2; + struct pg_vdata *data; + graph *pg = build_partition_graph (rdg, ddr_table, partitions, alias_ddrs); + int i, j, num_sccs = graphds_scc (pg, NULL); + + /* Strong connected compoenent means dependence cycle, we cannot distribute + them. So fuse them together. */ + if ((unsigned) num_sccs < partitions->length ()) + { + for (i = 0; i < num_sccs; ++i) + { + for (j = 0; partitions->iterate (j, &partition1); ++j) + if (pg->vertices[j].component == i) + break; + for (j = j + 1; partitions->iterate (j, &partition2); ++j) + if (pg->vertices[j].component == i) + { + partition_merge_into (partition1, partition2, FUSE_SAME_SCC); + (*partitions)[j] = NULL; + partition_free (partition2); + data = (struct pg_vdata *)pg->vertices[j].data; + data->partition = NULL; + } + } + sort_partitions_by_post_order (pg, partitions); + } + gcc_assert (partitions->length () == (unsigned)num_sccs); + free_partition_graph_vdata (pg); + free_graph (pg); +} + +/* Callback function for traversing edge E in graph G. DATA is private + callback data. */ + +static void +pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data) +{ + int i, j, component; + struct pg_edge_callback_data *cbdata; + struct pg_edata *edata = (struct pg_edata *) e->data; + + /* If the edge doesn't have attached data dependence, it represents + compilation time known dependences. This type dependence cannot + be resolved by runtime alias check. */ + if (edata == NULL || edata->alias_ddrs.length () == 0) + return; + + cbdata = (struct pg_edge_callback_data *) data; + i = e->src; + j = e->dest; + component = cbdata->vertices_component[i]; + /* Vertices are topologically sorted according to compilation time + known dependences, so we can break strong connected components + by removing edges of the opposite direction, i.e, edges pointing + from vertice with smaller post number to vertice with bigger post + number. */ + if (g->vertices[i].post < g->vertices[j].post + /* We only need to remove edges connecting vertices in the same + strong connected component to break it. */ + && component == cbdata->vertices_component[j] + /* Check if we want to break the strong connected component or not. */ + && !bitmap_bit_p (cbdata->sccs_to_merge, component)) + cbdata->alias_ddrs->safe_splice (edata->alias_ddrs); +} + +/* This is the main function breaking strong conected components in + PARTITIONS giving reduced depdendence graph RDG and data dependences + in DDR_TABLE. Store data dependence relations for runtime alias + check in ALIAS_DDRS. */ + +static void +break_alias_scc_partitions (struct graph *rdg, + hash_table<ddr_entry_hasher> *ddr_table, + vec<struct partition *> *partitions, + vec<ddr_p> *alias_ddrs) +{ + int i, j, num_sccs, num_sccs_no_alias; + /* Build partition dependence graph. */ + graph *pg = build_partition_graph (rdg, ddr_table, partitions, alias_ddrs); + + alias_ddrs->truncate (0); + /* Find strong connected components in the graph, with all dependence edges + considered. */ + num_sccs = graphds_scc (pg, NULL); + /* All SCCs now can be broken by runtime alias checks because SCCs caused by + compilation time known dependences are merged before this function. */ + if ((unsigned) num_sccs < partitions->length ()) + { + struct pg_edge_callback_data cbdata; + auto_bitmap sccs_to_merge; + auto_vec<enum partition_type> scc_types; + struct partition *partition, *first; + + /* If all paritions in a SCC has the same type, we can simply merge the + SCC. This loop finds out such SCCS and record them in bitmap. */ + bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs); + for (i = 0; i < num_sccs; ++i) + { + for (j = 0; partitions->iterate (j, &first); ++j) + if (pg->vertices[j].component == i) + break; + for (++j; partitions->iterate (j, &partition); ++j) + { + if (pg->vertices[j].component != i) + continue; + + if (first->type != partition->type) + { + bitmap_clear_bit (sccs_to_merge, i); + break; + } + } + } + + /* Initialize callback data for traversing. */ + cbdata.sccs_to_merge = sccs_to_merge; + cbdata.alias_ddrs = alias_ddrs; + cbdata.vertices_component = XNEWVEC (int, pg->n_vertices); + /* Record the component information which will be corrupted by next + graph scc finding call. */ + for (i = 0; i < pg->n_vertices; ++i) + cbdata.vertices_component[i] = pg->vertices[i].component; + + /* Collect data dependences for runtime alias checks to break SCCs. */ + if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs) + { + /* Run SCC finding algorithm again, with alias dependence edges + skipped. This is to topologically sort paritions according to + compilation time known dependence. Note the topological order + is stored in the form of pg's post order number. */ + num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge); + gcc_assert (partitions->length () == (unsigned) num_sccs_no_alias); + /* With topological order, we can construct two subgraphs L and R. + L contains edge <x, y> where x < y in terms of post order, while + R contains edge <x, y> where x > y. Edges for compilation time + known dependence all fall in R, so we break SCCs by removing all + (alias) edges of in subgraph L. */ + for_each_edge (pg, pg_collect_alias_ddrs, &cbdata); + } + + /* For SCC that doesn't need to be broken, merge it. */ + for (i = 0; i < num_sccs; ++i) + { + if (!bitmap_bit_p (sccs_to_merge, i)) + continue; + + for (j = 0; partitions->iterate (j, &first); ++j) + if (cbdata.vertices_component[j] == i) + break; + for (++j; partitions->iterate (j, &partition); ++j) + { + struct pg_vdata *data; + + if (cbdata.vertices_component[j] != i) + continue; + + partition_merge_into (first, partition, FUSE_SAME_SCC); + (*partitions)[j] = NULL; + partition_free (partition); + data = (struct pg_vdata *)pg->vertices[j].data; + gcc_assert (data->id == j); + data->partition = NULL; + } + } + } + + sort_partitions_by_post_order (pg, partitions); + free_partition_graph_vdata (pg); + for_each_edge (pg, free_partition_graph_edata_cb, NULL); + free_graph (pg); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Possible alias data dependence to break:\n"); + dump_data_dependence_relations (dump_file, *alias_ddrs); + } +} + +/* Compute and return an expression whose value is the segment length which + will be accessed by DR in NITERS iterations. */ + +static tree +data_ref_segment_size (struct data_reference *dr, tree niters) +{ + tree segment_length; + + if (integer_zerop (DR_STEP (dr))) + segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))); + else + segment_length = size_binop (MULT_EXPR, + fold_convert (sizetype, DR_STEP (dr)), + fold_convert (sizetype, niters)); + + return segment_length; +} + +/* Return true if LOOP's latch is dominated by statement for data reference + DR. */ + +static inline bool +latch_dominated_by_data_ref (struct loop *loop, data_reference *dr) +{ + return dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, + gimple_bb (DR_STMT (dr))); +} + +/* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's + data dependence relations ALIAS_DDRS. */ + +static void +compute_alias_check_pairs (struct loop *loop, vec<ddr_p> *alias_ddrs, + vec<dr_with_seg_len_pair_t> *comp_alias_pairs) +{ + unsigned int i; + unsigned HOST_WIDE_INT factor = 1; + tree niters_plus_one, niters = number_of_latch_executions (loop); + + gcc_assert (niters != NULL_TREE && niters != chrec_dont_know); + niters = fold_convert (sizetype, niters); + niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "Creating alias check pairs:\n"); + + /* Iterate all data dependence relations and compute alias check pairs. */ + for (i = 0; i < alias_ddrs->length (); i++) + { + ddr_p ddr = (*alias_ddrs)[i]; + struct data_reference *dr_a = DDR_A (ddr); + struct data_reference *dr_b = DDR_B (ddr); + tree seg_length_a, seg_length_b; + int comp_res = data_ref_compare_tree (DR_BASE_ADDRESS (dr_a), + DR_BASE_ADDRESS (dr_b)); + + if (comp_res == 0) + comp_res = data_ref_compare_tree (DR_OFFSET (dr_a), DR_OFFSET (dr_b)); + gcc_assert (comp_res != 0); + + if (latch_dominated_by_data_ref (loop, dr_a)) + seg_length_a = data_ref_segment_size (dr_a, niters_plus_one); + else + seg_length_a = data_ref_segment_size (dr_a, niters); + + if (latch_dominated_by_data_ref (loop, dr_b)) + seg_length_b = data_ref_segment_size (dr_b, niters_plus_one); + else + seg_length_b = data_ref_segment_size (dr_b, niters); + + dr_with_seg_len_pair_t dr_with_seg_len_pair + (dr_with_seg_len (dr_a, seg_length_a), + dr_with_seg_len (dr_b, seg_length_b)); + + /* Canonicalize pairs by sorting the two DR members. */ + if (comp_res > 0) + std::swap (dr_with_seg_len_pair.first, dr_with_seg_len_pair.second); + + comp_alias_pairs->safe_push (dr_with_seg_len_pair); + } + + if (tree_fits_uhwi_p (niters)) + factor = tree_to_uhwi (niters); + + /* Prune alias check pairs. */ + prune_runtime_alias_test_list (comp_alias_pairs, factor); + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Improved number of alias checks from %d to %d\n", + alias_ddrs->length (), comp_alias_pairs->length ()); +} + +/* Given data dependence relations in ALIAS_DDRS, generate runtime alias + checks and version LOOP under condition of these runtime alias checks. */ + +static void +version_loop_by_alias_check (struct loop *loop, vec<ddr_p> *alias_ddrs) +{ + unsigned then_prob, else_prob, then_scale, else_scale; + basic_block cond_bb; + struct loop *nloop; + tree lhs, arg0, cond_expr = NULL_TREE; + gimple_seq cond_stmts = NULL; + gimple *stmt; + auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs; + + /* Generate code for runtime alias checks if necessary. */ + if (alias_ddrs->length () > 0) + { + compute_alias_check_pairs (loop, alias_ddrs, &comp_alias_pairs); + create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr); + cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts, + is_gimple_condexpr, NULL_TREE); + then_prob = 9 * REG_BR_PROB_BASE / 10; + else_prob = REG_BR_PROB_BASE - then_prob; + then_scale = 9 * REG_BR_PROB_BASE / 10; + else_scale = REG_BR_PROB_BASE - then_scale; + } + else + { + cond_expr = boolean_true_node; + /* Use REG_BR_PROB_BASE for both branches since only one branch + will be kept in the end. */ + then_prob = REG_BR_PROB_BASE; + else_prob = REG_BR_PROB_BASE; + then_scale = REG_BR_PROB_BASE; + else_scale = REG_BR_PROB_BASE; + } + + /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */ + if (flag_tree_loop_vectorize) + { + /* Generate internal function call for loop distribution alias check. */ + arg0 = build_int_cst (integer_type_node, loop->num); + stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS, + 2, arg0, cond_expr); + lhs = make_ssa_name (boolean_type_node); + gimple_call_set_lhs (stmt, lhs); + gimple_seq_add_stmt (&cond_stmts, stmt); + } + else + lhs = cond_expr; + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Version loop <%d> with runtime alias check\n", loop->num); + + initialize_original_copy_tables (); + nloop = loop_version (loop, lhs, &cond_bb, then_prob, + else_prob, then_scale, else_scale, true); + free_original_copy_tables (); + nloop->aux = (void *)nloop; + /* Record the original loop number in newly generated loops. */ + nloop->ldist_alias_id = loop->num; + nloop->dont_vectorize = true; + nloop->force_vectorize = false; + + if (cond_stmts) + { + gimple_stmt_iterator cond_gsi = gsi_last_bb (cond_bb); + gsi_insert_seq_before (&cond_gsi, cond_stmts, GSI_SAME_STMT); + } + update_ssa (TODO_update_ssa); +} + +/* Return true if loop versioning is needed to distrubute PARTITIONS. + ALIAS_DDRS are data dependence relations for runtime alias check. */ + +static inline bool +version_for_distribution_p (vec<struct partition *> *partitions, + vec<ddr_p> *alias_ddrs) +{ + unsigned i; + struct partition *partition; + + /* No need to version loop if we have only one partition. */ + if (partitions->length () == 1) + return false; + + /* Need to version loop if runtime alias check is necessary. */ + if (alias_ddrs->length () > 0) + return true; + + /* Don't version the loop with call to IFN_LOOP_DIST_ALIAS if + vectorizer is not enable because no other pass can fold it. */ + if (!flag_tree_loop_vectorize) + return false; + + /* Don't version loop if any partition is builtin. */ + for (i = 0; partitions->iterate (i, &partition); ++i) + { + if (partition->kind != PKIND_NORMAL) + break; + } + return (i == partitions->length ()); +} + +/* Fuse all partitions if necessary before finalizing distribution. */ + +static void +finalize_partitions (vec<struct partition *> *partitions, + vec<ddr_p> *alias_ddrs) +{ + unsigned i; + struct partition *a, *partition; + + if (partitions->length () == 1 + || alias_ddrs->length () > 0) + return; + + a = (*partitions)[0]; + if (a->kind != PKIND_NORMAL) + return; + + for (i = 1; partitions->iterate (i, &partition); ++i) + { + /* Don't fuse if partition has different type or it is a builtin. */ + if (partition->type != a->type + || partition->kind != PKIND_NORMAL) + return; + } + + /* Fuse all partitions. */ + for (i = 1; partitions->iterate (i, &partition); ++i) + { + partition_merge_into (a, partition, FUSE_FINALIZE); + partition_free (partition); + } + partitions->truncate (1); +} + /* Distributes the code from LOOP in such a way that producer statements are placed before consumer statements. Tries to separate only the statements from STMTS into separate loops. @@ -1453,8 +2445,6 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, partition *partition; bool any_builtin; int i, nbp; - graph *pg = NULL; - int num_sccs = 1; *destroy_p = false; *nb_calls = 0; @@ -1462,7 +2452,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, if (!find_loop_nest (loop, &loop_nest)) return 0; - rdg = build_rdg (loop_nest, cd); + vec<data_reference_p> datarefs; + datarefs.create (10); + rdg = build_rdg (loop_nest, cd, &datarefs); if (!rdg) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1470,19 +2462,35 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, "Loop %d not distributed: failed to build the RDG.\n", loop->num); + free_data_refs (datarefs); return 0; } if (dump_file && (dump_flags & TDF_DETAILS)) dump_rdg (dump_file, rdg); + auto_vec<ddr_p> alias_ddrs; + vec<ddr_p> dependences; + dependences.create (10); + hash_table<ddr_entry_hasher> ddr_table (15); + rdg_compute_data_dependence (rdg, loop_nest, &datarefs, + &dependences, &ddr_table); + + /* We can't do runtime alias check if niter is unknown for loop. */ + tree niters = number_of_latch_executions (loop); + bool rt_alias_check_p = (niters != NULL_TREE && niters != chrec_dont_know); + + auto_bitmap stmt_in_all_partitions; auto_vec<struct partition *, 3> partitions; - rdg_build_partitions (rdg, stmts, &partitions); + bitmap_set_range (stmt_in_all_partitions, 0, rdg->n_vertices); + rdg_build_partitions (rdg, &ddr_table, stmts, + &partitions, stmt_in_all_partitions); any_builtin = false; FOR_EACH_VEC_ELT (partitions, i, partition) { - classify_partition (loop, rdg, partition); + classify_partition (loop, rdg, &ddr_table, + partition, stmt_in_all_partitions); any_builtin |= partition_builtin_p (partition); } @@ -1508,13 +2516,7 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, for (++i; partitions.iterate (i, &partition); ++i) if (!partition_builtin_p (partition)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "fusing non-builtin partitions\n"); - dump_bitmap (dump_file, into->stmts); - dump_bitmap (dump_file, partition->stmts); - } - partition_merge_into (into, partition); + partition_merge_into (into, partition, FUSE_NON_BUILTIN); partitions.unordered_remove (i); partition_free (partition); i--; @@ -1530,21 +2532,14 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, for (i = i + 1; partitions.iterate (i, &partition); ++i) if (partition_reduction_p (partition)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "fusing partitions\n"); - dump_bitmap (dump_file, into->stmts); - dump_bitmap (dump_file, partition->stmts); - fprintf (dump_file, "because they have reductions\n"); - } - partition_merge_into (into, partition); + partition_merge_into (into, partition, FUSE_REDUCTION); partitions.unordered_remove (i); partition_free (partition); i--; } - /* Apply our simple cost model - fuse partitions with similar - memory accesses. */ + /* Apply our simple cost model - fuse partitions with shared memory + accesses. */ for (i = 0; partitions.iterate (i, &into); ++i) { bool changed = false; @@ -1553,17 +2548,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, for (int j = i + 1; partitions.iterate (j, &partition); ++j) { - if (similar_memory_accesses (rdg, into, partition)) + if (share_memory_accesses (rdg, into, partition)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "fusing partitions\n"); - dump_bitmap (dump_file, into->stmts); - dump_bitmap (dump_file, partition->stmts); - fprintf (dump_file, "because they have similar " - "memory accesses\n"); - } - partition_merge_into (into, partition); + partition_merge_into (into, partition, FUSE_SHARE_REF); partitions.unordered_remove (j); partition_free (partition); j--; @@ -1581,111 +2568,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, /* Build the partition dependency graph. */ if (partitions.length () > 1) { - pg = new_graph (partitions.length ()); - struct pgdata { - struct partition *partition; - vec<data_reference_p> writes; - vec<data_reference_p> reads; - }; -#define PGDATA(i) ((pgdata *)(pg->vertices[i].data)) - for (i = 0; partitions.iterate (i, &partition); ++i) - { - vertex *v = &pg->vertices[i]; - pgdata *data = new pgdata; - data_reference_p dr; - /* FIXME - leaks. */ - v->data = data; - bitmap_iterator bi; - unsigned j; - data->partition = partition; - data->reads = vNULL; - data->writes = vNULL; - EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, j, bi) - for (int k = 0; RDG_DATAREFS (rdg, j).iterate (k, &dr); ++k) - if (DR_IS_READ (dr)) - data->reads.safe_push (dr); - else - data->writes.safe_push (dr); - } - struct partition *partition1, *partition2; - for (i = 0; partitions.iterate (i, &partition1); ++i) - for (int j = i + 1; partitions.iterate (j, &partition2); ++j) - { - /* dependence direction - 0 is no dependence, -1 is back, - 1 is forth, 2 is both (we can stop then, merging will occur). */ - int dir = 0; - dir = pg_add_dependence_edges (rdg, loop_nest, dir, - PGDATA(i)->writes, - PGDATA(j)->reads); - if (dir != 2) - dir = pg_add_dependence_edges (rdg, loop_nest, dir, - PGDATA(i)->reads, - PGDATA(j)->writes); - if (dir != 2) - dir = pg_add_dependence_edges (rdg, loop_nest, dir, - PGDATA(i)->writes, - PGDATA(j)->writes); - if (dir == 1 || dir == 2) - add_edge (pg, i, j); - if (dir == -1 || dir == 2) - add_edge (pg, j, i); - } - - /* Add edges to the reduction partition (if any) to force it last. */ - unsigned j; - for (j = 0; partitions.iterate (j, &partition); ++j) - if (partition_reduction_p (partition)) - break; - if (j < partitions.length ()) - { - for (unsigned i = 0; partitions.iterate (i, &partition); ++i) - if (i != j) - add_edge (pg, i, j); - } - - /* Compute partitions we cannot separate and fuse them. */ - num_sccs = graphds_scc (pg, NULL); - for (i = 0; i < num_sccs; ++i) - { - struct partition *first; - int j; - for (j = 0; partitions.iterate (j, &first); ++j) - if (pg->vertices[j].component == i) - break; - for (j = j + 1; partitions.iterate (j, &partition); ++j) - if (pg->vertices[j].component == i) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "fusing partitions\n"); - dump_bitmap (dump_file, first->stmts); - dump_bitmap (dump_file, partition->stmts); - fprintf (dump_file, "because they are in the same " - "dependence SCC\n"); - } - partition_merge_into (first, partition); - partitions[j] = NULL; - partition_free (partition); - PGDATA (j)->partition = NULL; - } - } - - /* Now order the remaining nodes in postorder. */ - qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp); - partitions.truncate (0); - for (i = 0; i < pg->n_vertices; ++i) - { - pgdata *data = PGDATA (i); - if (data->partition) - partitions.safe_push (data->partition); - data->reads.release (); - data->writes.release (); - delete data; - } - gcc_assert (partitions.length () == (unsigned)num_sccs); - free_graph (pg); + merge_dep_scc_partitions (rdg, &ddr_table, &partitions, + rt_alias_check_p ? NULL : &alias_ddrs); + alias_ddrs.truncate (0); + if (rt_alias_check_p && partitions.length () > 1) + break_alias_scc_partitions (rdg, &ddr_table, &partitions, &alias_ddrs); } + finalize_partitions (&partitions, &alias_ddrs); + nbp = partitions.length (); if (nbp == 0 || (nbp == 1 && !partition_builtin_p (partitions[0])) @@ -1695,8 +2586,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, goto ldist_done; } + if (version_for_distribution_p (&partitions, &alias_ddrs)) + version_loop_by_alias_check (loop, &alias_ddrs); + if (dump_file && (dump_flags & TDF_DETAILS)) - dump_rdg_partitions (dump_file, partitions); + { + fprintf (dump_file, + "distribute loop <%d> into partitions:\n", loop->num); + dump_rdg_partitions (dump_file, partitions); + } FOR_EACH_VEC_ELT (partitions, i, partition) { @@ -1706,7 +2604,9 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, } ldist_done: - + free_data_refs (datarefs); + free_dependence_relations (dependences); + ddr_table.empty (); FOR_EACH_VEC_ELT (partitions, i, partition) partition_free (partition); @@ -1758,6 +2658,22 @@ pass_loop_distribution::execute (function *fun) control_dependences *cd = NULL; auto_vec<loop_p> loops_to_be_destroyed; + /* Compute topological order for basic blocks. Topological order is + needed because data dependence is computed for data references in + lexicographical order */ + if (bb_top_order_index == NULL) + { + int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); + + bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun)); + bb_top_order_index_size + = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, true); + for (int i = 0; i < bb_top_order_index_size; i++) + bb_top_order_index[rpo[i]] = i; + + free (rpo); + } + FOR_ALL_BB_FN (bb, fun) { gimple_stmt_iterator gsi; @@ -1767,6 +2683,9 @@ pass_loop_distribution::execute (function *fun) gimple_set_uid (gsi_stmt (gsi), -1); } + FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) + loop->aux = NULL; + /* We can at the moment only distribute non-nested loops, thus restrict walking to innermost loops. */ FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) @@ -1776,6 +2695,10 @@ pass_loop_distribution::execute (function *fun) int num = loop->num; unsigned int i; + /* Skip distributed loops. */ + if (loop->aux != NULL) + continue; + /* If the loop doesn't have a single exit we will fail anyway, so do that early. */ if (!single_exit (loop)) @@ -1862,16 +2785,26 @@ out: fprintf (dump_file, "Loop %d is the same.\n", num); } + FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) + loop->aux = NULL; + if (cd) delete cd; + if (bb_top_order_index != NULL) + { + free (bb_top_order_index); + bb_top_order_index = NULL; + bb_top_order_index_size = 0; + } + if (changed) { /* Destroy loop bodies that could not be reused. Do this late as we otherwise can end up refering to stale data in control dependences. */ unsigned i; FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop) - destroy_loop (loop); + destroy_loop (loop); /* Cached scalar evolutions now may refer to wrong or non-existing loops. */ diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c index 1bef2e4..0d83d33 100644 --- a/gcc/tree-vectorizer.c +++ b/gcc/tree-vectorizer.c @@ -469,6 +469,63 @@ fold_loop_vectorized_call (gimple *g, tree value) } } +/* If LOOP has been versioned during loop distribution, return the internal + call guarding it. */ + +static gimple * +vect_loop_dist_alias_call (struct loop *loop) +{ + gimple_stmt_iterator gsi; + gimple *g; + basic_block bb = loop_preheader_edge (loop)->src; + struct loop *outer_loop = bb->loop_father; + + /* Look upward in dominance tree. */ + for (; bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) && bb->loop_father == outer_loop; + bb = get_immediate_dominator (CDI_DOMINATORS, bb)) + { + g = last_stmt (bb); + if (g == NULL || gimple_code (g) != GIMPLE_COND) + continue; + + gsi = gsi_for_stmt (g); + gsi_prev (&gsi); + if (gsi_end_p (gsi)) + continue; + + g = gsi_stmt (gsi); + /* The guarding internal function call must have the same distribution + alias id. */ + if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS) + && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->ldist_alias_id)) + return g; + } + return NULL; +} + +/* Fold LOOP_DIST_ALIAS internal call stmt according to KEEP_P and update + any immediate uses of it's LHS. Stmt is folded to its second argument + if KEEP_P is true, otherwise to boolean_false_node. */ + +static void +fold_loop_dist_alias_call (gimple *g, bool keep_p) +{ + tree lhs = gimple_call_lhs (g); + use_operand_p use_p; + imm_use_iterator iter; + gimple *use_stmt; + gimple_stmt_iterator gsi = gsi_for_stmt (g); + tree folded_value = keep_p ? gimple_call_arg (g, 1) : boolean_false_node; + + update_call_from_tree (&gsi, folded_value); + FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) + { + FOR_EACH_IMM_USE_ON_STMT (use_p, iter) + SET_USE (use_p, folded_value); + update_stmt (use_stmt); + } +} + /* Set the uids of all the statements in basic blocks inside loop represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal call guarding the loop which has been if converted. */ @@ -595,7 +652,7 @@ vectorize_loops (void) else { loop_vec_info loop_vinfo, orig_loop_vinfo; - gimple *loop_vectorized_call; + gimple *loop_vectorized_call, *loop_dist_alias_call; try_vectorize: if (!((flag_tree_loop_vectorize && optimize_loop_nest_for_speed_p (loop)) @@ -603,6 +660,7 @@ vectorize_loops (void) continue; orig_loop_vinfo = NULL; loop_vectorized_call = vect_loop_vectorized_call (loop); + loop_dist_alias_call = vect_loop_dist_alias_call (loop); vectorize_epilogue: vect_location = find_loop_location (loop); if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION @@ -710,6 +768,12 @@ vectorize_loops (void) loop_vectorized_call = NULL; ret |= TODO_cleanup_cfg; } + if (loop_dist_alias_call) + { + fold_loop_dist_alias_call (loop_dist_alias_call, true); + loop_dist_alias_call = NULL; + ret |= TODO_cleanup_cfg; + } if (new_loop) { @@ -743,6 +807,15 @@ vectorize_loops (void) { fold_loop_vectorized_call (g, boolean_false_node); ret |= TODO_cleanup_cfg; + g = NULL; + } + else + g = vect_loop_dist_alias_call (loop); + + if (g) + { + fold_loop_dist_alias_call (g, false); + ret |= TODO_cleanup_cfg; } } } -- 1.9.1
Hi, This is the main patch of the change. It improves loop distribution by versioning loop under runtime alias check conditions, as well as better partition fusion. As described in comments, the patch basically implements distribution in the following steps: 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 dependences between statements. 3) Apart from RDG, compute data dependences 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 parallelly; 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 dependences. The vertices (PG:V) model all partitions and the edges (PG:E) model all data dependences 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 dependences because of possible alias relation of data references. We categorize PG's edge to two types: "true" edge that represents compilation time known data dependences; "alias" edge for all other data dependences. 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge partitions in each strong connected commponent (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 dependences of the removed "alias" edges. Create runtime alias checks for collected data dependences. 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 shouldn't be difficult): TODO: 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 This patch also fixes couple of latent bugs in the original implementation. After this change, kernel loop in hmmer can be distributed and vectorized as a result. This gives obvious performance improvement. There is still inefficient code generation issue which I will try to fix in loop split. Apart from this, the next opportunity in hmmer is to eliminate number of dead stores under proper alias information. Bootstrap and test at O2/O3 on x86_64 and AArch64. is it OK? Thanks, bin 2017-05-31 Bin Cheng <bin.cheng@arm.com> * cfgloop.h (struct loop): New field ldist_alias_id. * cfgloopmanip.c (lv_adjust_loop_entry_edge): Refine comment for new internal function. * internal-fn.c (expand_LOOP_DIST_ALIAS): New function. * internal-fn.def (IFN_LOOP_DIST_ALIAS): New internal function. * tree-loop-distribution.c: Add general explanantion on the pass. Include header file. (struct ddr_entry, struct ddr_entry_hasher): New structs. (ddr_entry_hasher::hash, ddr_entry_hasher::equal): New functions. (bb_top_order_index, bb_top_order_index_size): New static vars. (bb_top_order_cmp): New function. (stmts_from_loop): Get basic blocks in topological order. Don't free data references. (build_rdg): New parameter pointing to vector of data references. Store data references in it. (enum partition_type): New enum. (enum partition_kind, struct partition): Add comments. New fields. (partition_alloc, partition_free): Handle new fields of partition. (enum fuse_type, fuse_message): New enum and varaible. (partition_merge_into): New parameter. Update implementation wrto new fields of partition. (generate_loops_for_partition): Set ldist_alias_id information. (record_ddr, get_ddr, possible_data_dep_cycle_p): New functions. (build_rdg_partition_for_vertex): New parameter. Compute type info for partition. (classify_partition): New parameter. Only classify partition as reduction if the reduction is not included by all partitions. Retrieve cached ddr, rather than compute it on the fly. (ref_base_address): Delete. (similar_memory_accesses): Rename to ... (share_memory_accesses): ... this. (rdg_build_partitions): New parameter and update uses. (pg_add_dependence_edges): New parameter. Store ddr in parameter vector if it could be resolved by runtime alias check. (rdg_compute_data_dependence): New function. (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): Update uses. Break SCC and version loop with runtime alias checks. (pass_loop_distribution::execute): Compute topological order for basic blocks. Update uses. * tree-vectorizer.c (vect_loop_dist_alias_call): New. (fold_loop_dist_alias_call): New. (vectorize_loops): Fold IFN_LOOP_DIST_ALIAS call depending on successful vectorization or not. gcc/testsuite/ChangeLog 2017-05-31 Bin Cheng <bin.cheng@arm.com> * gcc.dg/tree-ssa/ldist-4.c: Adjust test string. * gcc.dg/tree-ssa/ldist-12.c: Ditto. * gcc.dg/tree-ssa/ldist-13.c: Ditto. * gcc.dg/tree-ssa/ldist-14.c: Ditto.