From 63a21f07ac97d1e93086110d2564900417a2af5a Mon Sep 17 00:00:00 2001 From: Bin Cheng Date: Fri, 9 Jun 2017 13:11:59 +0100 Subject: [PATCH 11/14] partition-type-20170607.txt --- gcc/tree-loop-distribution.c | 107 +++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 103 insertions(+), 4 deletions(-) diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index eacd9a1..7e31fee8 100644 --- a/gcc/tree-loop-distribution.c +++ b/gcc/tree-loop-distribution.c @@ -51,6 +51,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" @@ -535,11 +536,19 @@ build_rdg (struct loop *loop, control_dependences *cd) } - +/* 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 { @@ -553,6 +562,7 @@ struct partition 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; @@ -632,6 +642,9 @@ static void 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; @@ -1141,6 +1154,47 @@ get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b) return (*slot)->ddr; } +/* In reduced dependence graph RDG for loop distribution, return true if + dependence between references DR1 and DR2 leads to a dependence cycle + and such dependence cycle can't be resolved by runtime alias check. */ + +static bool +data_dep_in_cycle_p (struct graph *rdg, + 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_data_dependence (rdg, dr1, dr2); + + /* In case of no data dependence. */ + 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. */ @@ -1151,7 +1205,8 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) auto_vec nodes; unsigned i, j; int x; - data_reference_p dr; + data_reference_p dr, dr1, dr2; + bitmap_iterator bi, bj; graphds_dfs (rdg, &v, 1, &nodes, false, NULL); @@ -1167,6 +1222,12 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) gcc_assert (slot != NULL); + /* 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)) bitmap_set_bit (partition->reads, *slot); else @@ -1174,6 +1235,43 @@ build_rdg_partition_for_vertex (struct graph *rdg, int v) } } + if (partition->type == PTYPE_SEQUENTIAL) + return partition; + + /* Further check if any data dependence prevents us from executing the + partition parallelly. */ + EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi) + { + dr1 = (*datarefs_vec)[i]; + EXECUTE_IF_SET_IN_BITMAP (partition->writes, 0, j, bj) + { + dr2 = (*datarefs_vec)[j]; + /* Partition can only be executed sequentially if there is any + data dependence cycle. */ + if (data_dep_in_cycle_p (rdg, dr1, dr2)) + { + partition->type = PTYPE_SEQUENTIAL; + return partition; + } + } + } + + EXECUTE_IF_SET_IN_BITMAP (partition->reads, 0, i, bi) + { + dr1 = (*datarefs_vec)[i]; + EXECUTE_IF_SET_IN_BITMAP (partition->writes, i + 1, j, bj) + { + dr2 = (*datarefs_vec)[j]; + /* Partition can only be executed sequentially if there is any + data dependence cycle. */ + if (data_dep_in_cycle_p (rdg, dr1, dr2)) + { + partition->type = PTYPE_SEQUENTIAL; + return partition; + } + } + } + return partition; } @@ -1473,8 +1571,9 @@ rdg_build_partitions (struct graph *rdg, 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); -- 1.9.1