diff options
Diffstat (limited to 'gcc/tree-loop-distribution.c')
| -rw-r--r-- | gcc/tree-loop-distribution.c | 1483 |
1 files changed, 1179 insertions, 304 deletions
diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c index a60454b5218..8d80cccf38f 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 dependencies between statements. + 3) Apart from RDG, compute data dependencies between memory references. + 4) Starting from seed statement, build up partition by adding depended + statements according to RDG's dependence information. Partition is + classified as parallel type if it can be executed paralleled; or as + sequential type if it can't. Parallel type partition is further + classified as different builtin kinds if it can be implemented as + builtin function calls. + 5) Build partition dependence graph (PG) based on data dependencies. + The vertices (PG:V) model all partitions and the edges (PG:E) model + all data dependencies between every partitions pair. In general, + data dependence is either compilation time known or unknown. In C + family languages, there exists quite amount compilation time unknown + dependencies because of possible alias relation of data references. + We categorize PG's edge to two types: "true" edge that represents + compilation time known data dependencies; "alias" edge for all other + data dependencies. + 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge + partitions in each strong connected component (SCC) correspondingly. + Build new PG for merged partitions. + 7) Traverse PG again and this time with both "true" and "alias" edges + included. We try to break SCCs by removing some edges. Because + SCCs by "true" edges are all fused in step 6), we can break SCCs + by removing some "alias" edges. It's NP-hard to choose optimal + edge set, fortunately simple approximation is good enough for us + given the small problem scale. + 8) Collect all data dependencies of the removed "alias" edges. Create + runtime alias checks for collected data dependencies. + 9) Version loop under the condition of runtime alias checks. Given + loop distribution generally introduces additional overhead, it is + only useful if vectorization is achieved in distributed loop. We + version loop with internal function call IFN_LOOP_DIST_ALIAS. If + no distributed loop can be vectorized, we simply remove distributed + loops and recover to the original one. + + 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" @@ -63,9 +111,55 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa.h" #include "cfgloop.h" #include "tree-scalar-evolution.h" +#include "params.h" #include "tree-vectorizer.h" +#define MAX_DATAREFS_NUM \ + ((unsigned) PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS)) + +/* Hashtable helpers. */ + +struct ddr_hasher : nofree_ptr_hash <struct data_dependence_relation> +{ + static inline hashval_t hash (const data_dependence_relation *); + static inline bool equal (const data_dependence_relation *, + const data_dependence_relation *); +}; + +/* Hash function for data dependence. */ + +inline hashval_t +ddr_hasher::hash (const data_dependence_relation *ddr) +{ + inchash::hash h; + h.add_ptr (DDR_A (ddr)); + h.add_ptr (DDR_B (ddr)); + return h.end (); +} + +/* Hash table equality function for data dependence. */ + +inline bool +ddr_hasher::equal (const data_dependence_relation *ddr1, + const data_dependence_relation *ddr2) +{ + return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2)); +} + +/* The loop (nest) to be distributed. */ +static vec<loop_p> loop_nest; + +/* Vector of data references in the loop to be distributed. */ +static vec<data_reference_p> datarefs_vec; + +/* Store index of data reference in aux field. */ +#define DR_INDEX(dr) ((uintptr_t) (dr)->aux) + +/* Hash table for data dependence relation in the loop to be distributed. */ +static hash_table<ddr_hasher> ddrs_table (389); + + /* A Reduced Dependence Graph (RDG) vertex representing a statement. */ struct rdg_vertex { @@ -336,8 +430,7 @@ create_rdg_cd_edges (struct graph *rdg, control_dependences *cd, loop_p loop) if that failed. */ static bool -create_rdg_vertices (struct graph *rdg, vec<gimple *> stmts, loop_p loop, - vec<data_reference_p> *datarefs) +create_rdg_vertices (struct graph *rdg, vec<gimple *> stmts, loop_p loop) { int i; gimple *stmt; @@ -357,12 +450,12 @@ create_rdg_vertices (struct graph *rdg, vec<gimple *> stmts, loop_p loop, if (gimple_code (stmt) == GIMPLE_PHI) continue; - unsigned drp = datarefs->length (); - if (!find_data_references_in_stmt (loop, stmt, datarefs)) + unsigned drp = datarefs_vec.length (); + if (!find_data_references_in_stmt (loop, stmt, &datarefs_vec)) return false; - for (unsigned j = drp; j < datarefs->length (); ++j) + for (unsigned j = drp; j < datarefs_vec.length (); ++j) { - data_reference_p dr = (*datarefs)[j]; + data_reference_p dr = datarefs_vec[j]; if (DR_IS_READ (dr)) RDGV_HAS_MEM_READS (v) = true; else @@ -373,16 +466,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 +539,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); } } @@ -431,24 +547,22 @@ free_rdg (struct graph *rdg) free_graph (rdg); } -/* Build the Reduced Dependence Graph (RDG) with one vertex per - statement of the loop nest LOOP_NEST, and one edge per data dependence or - scalar dependence. */ +/* Build the Reduced Dependence Graph (RDG) with one vertex per statement of + LOOP, and one edge per flow dependence or control dependence from control + dependence CD. During visiting each statement, data references are also + collected and recorded in global data DATAREFS_VEC. */ static struct graph * -build_rdg (vec<loop_p> loop_nest, control_dependences *cd) +build_rdg (struct loop *loop, control_dependences *cd) { 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); + stmts_from_loop (loop, &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)) { - datarefs.release (); free_rdg (rdg); return NULL; } @@ -456,43 +570,60 @@ build_rdg (vec<loop_p> loop_nest, control_dependences *cd) create_rdg_flow_edges (rdg); if (cd) - create_rdg_cd_edges (rdg, cd, loop_nest[0]); - - datarefs.release (); + create_rdg_cd_edges (rdg, cd, loop); return rdg; } - +/* 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; + /* Data references in the partition. */ + bitmap datarefs; }; /* Allocate and initialize a partition from BITMAP. */ static partition * -partition_alloc (bitmap stmts, bitmap loops) +partition_alloc (void) { partition *partition = XCNEW (struct partition); - partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL); - partition->loops = loops ? loops : BITMAP_ALLOC (NULL); + partition->stmts = BITMAP_ALLOC (NULL); + partition->loops = BITMAP_ALLOC (NULL); partition->reduction_p = false; partition->kind = PKIND_NORMAL; + partition->datarefs = BITMAP_ALLOC (NULL); return partition; } @@ -503,6 +634,7 @@ partition_free (partition *partition) { BITMAP_FREE (partition->stmts); BITMAP_FREE (partition->loops); + BITMAP_FREE (partition->datarefs); free (partition); } @@ -522,15 +654,57 @@ partition_reduction_p (partition *partition) return partition->reduction_p; } -/* Merge PARTITION into the partition DEST. */ +/* 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"}; + +static void +update_type_for_merge (struct graph *, partition *, partition *); + +/* Merge PARTITION into the partition DEST. RDG is the reduced dependence + graph and we update type for result partition if it is non-NULL. */ static void -partition_merge_into (partition *dest, partition *partition) +partition_merge_into (struct graph *rdg, partition *dest, + partition *partition, enum fuse_type ft) { + 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); + } + 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; + + /* Further check if any data dependence prevents us from executing the + new partition parallelly. */ + if (dest->type == PTYPE_PARALLEL && rdg != NULL) + update_type_for_merge (rdg, dest, partition); + + bitmap_ior_into (dest->datarefs, partition->datarefs); } @@ -618,11 +792,18 @@ generate_loops_for_partition (struct loop *loop, partition *partition, if (copy_p) { + int orig_loop_num = loop->orig_loop_num; loop = copy_loop_before (loop); gcc_assert (loop != NULL); + loop->orig_loop_num = orig_loop_num; create_preheader (loop, CP_SIMPLE_PREHEADERS); create_bb_after_loop (loop); } + else + { + /* Origin number is set to the new versioned loop's num. */ + gcc_assert (loop->orig_loop_num != loop->num); + } /* Remove stmts not in the PARTITION bitmap. */ bbs = get_loop_body_in_dom_order (loop); @@ -986,6 +1167,101 @@ generate_code_for_partition (struct loop *loop, return false; } +/* Return data dependence relation for data references A and B. The two + data references must be in lexicographic order wrto reduced dependence + graph RDG. We firstly try to find ddr from global ddr hash table. If + it doesn't exist, compute the ddr and cache it. */ + +static data_dependence_relation * +get_data_dependence (struct graph *rdg, data_reference_p a, data_reference_p b) +{ + struct data_dependence_relation ent, **slot; + struct data_dependence_relation *ddr; + + gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b)); + gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a)) + <= rdg_vertex_for_stmt (rdg, DR_STMT (b))); + ent.a = a; + ent.b = b; + slot = ddrs_table.find_slot (&ent, INSERT); + if (*slot == NULL) + { + ddr = initialize_data_dependence_relation (a, b, loop_nest); + compute_affine_dependence (ddr, loop_nest[0]); + *slot = ddr; + } + + return *slot; +} + +/* 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; + /* 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; +} + +/* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update + PARTITION1's type after merging PARTITION2 into PARTITION1. */ + +static void +update_type_for_merge (struct graph *rdg, + partition *partition1, partition *partition2) +{ + unsigned i, j; + bitmap_iterator bi, bj; + data_reference_p dr1, dr2; + + EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi) + { + unsigned start = (partition1 == partition2) ? i + 1 : 0; + + dr1 = datarefs_vec[i]; + EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, start, j, bj) + { + dr2 = datarefs_vec[j]; + if (DR_IS_READ (dr1) && DR_IS_READ (dr2)) + continue; + + /* Partition can only be executed sequentially if there is any + data dependence cycle. */ + if (data_dep_in_cycle_p (rdg, dr1, dr2)) + { + partition1->type = PTYPE_SEQUENTIAL; + return; + } + } + } +} /* Returns a partition with all the statements needed for computing the vertex V of the RDG, also including the loop exit conditions. */ @@ -993,10 +1269,11 @@ generate_code_for_partition (struct loop *loop, static partition * build_rdg_partition_for_vertex (struct graph *rdg, int v) { - partition *partition = partition_alloc (NULL, NULL); + partition *partition = partition_alloc (); auto_vec<int, 3> nodes; - unsigned i; + unsigned i, j; int x; + data_reference_p dr; graphds_dfs (rdg, &v, 1, &nodes, false, NULL); @@ -1005,23 +1282,45 @@ 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) + { + unsigned idx = (unsigned) DR_INDEX (dr); + gcc_assert (idx < datarefs_vec.length ()); + + /* 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; + + bitmap_set_bit (partition->datarefs, idx); + } } + if (partition->type == PTYPE_SEQUENTIAL) + return partition; + + /* Further check if any data dependence prevents us from executing the + partition parallelly. */ + update_type_for_merge (rdg, partition, partition); + return partition; } /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP. - For the moment we detect only the memset zero pattern. */ + For the moment we detect memset, memcpy and memmove patterns. Bitmap + STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions. */ static void -classify_partition (loop_p loop, struct graph *rdg, partition *partition) +classify_partition (loop_p loop, struct graph *rdg, partition *partition, + bitmap stmt_in_all_partitions) { bitmap_iterator bi; unsigned i; tree nb_iter; data_reference_p single_load, single_store; - bool volatiles_p = false; - bool plus_one = false; + bool volatiles_p = false, plus_one = false, has_reduction = false; partition->kind = PKIND_NORMAL; partition->main_dr = NULL; @@ -1036,16 +1335,31 @@ 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; + /* Due to limitation in the transform phase we have to fuse all + reduction partitions. As a result, this could cancel valid + loop distribution especially for loop that induction variable + is used outside of loop. To workaround this issue, we skip + marking partition as reudction if the reduction stmt belongs + to all partitions. In such case, reduction will be computed + correctly no matter how partitions are fused/distributed. */ + 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; @@ -1098,8 +1412,7 @@ classify_partition (loop_p loop, struct graph *rdg, partition *partition) return; nb_iter = number_of_latch_executions (loop); - if (!nb_iter || nb_iter == chrec_dont_know) - return; + gcc_assert (nb_iter && nb_iter != chrec_dont_know); if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, gimple_bb (DR_STMT (single_store)))) plus_one = true; @@ -1143,44 +1456,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_data_dependence (rdg, 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 +1484,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 access the same memory + object in RDG. */ 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; + unsigned i, j; bitmap_iterator bi, bj; - data_reference_p ref1, ref2; + data_reference_p dr1, dr2; /* First check whether in the intersection of the two partitions are any loads or stores. Common loads are the situation that happens @@ -1221,30 +1503,37 @@ 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; - } - } + /* Then check whether the two partitions access the same memory object. */ + EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi) + { + dr1 = datarefs_vec[i]; + + if (!DR_BASE_ADDRESS (dr1) + || !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1)) + continue; + + EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, 0, j, bj) + { + dr2 = datarefs_vec[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; } -/* Aggregate several components into a useful partition that is - registered in the PARTITIONS vector. Partitions will be - distributed in different loops. */ +/* For each seed statement in STARTING_STMTS, this function builds + partition for it by adding depended statements according to RDG. + All partitions are recorded in PARTITIONS. */ static void rdg_build_partitions (struct graph *rdg, @@ -1273,8 +1562,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); @@ -1365,67 +1655,97 @@ 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, modify and return DIR according to that. IF ALIAS_DDR is + not NULL, we record dependence introduced by possible alias between + two data references in ALIAS_DDRS; otherwise, we simply ignore such + dependence as if it doesn't exist at all. */ static int -pg_add_dependence_edges (struct graph *rdg, vec<loop_p> loops, int dir, - vec<data_reference_p> drs1, - vec<data_reference_p> drs2) +pg_add_dependence_edges (struct graph *rdg, int dir, + bitmap drs1, bitmap drs2, vec<ddr_p> *alias_ddrs) { - data_reference_p dr1, dr2; + unsigned i, j; + bitmap_iterator bi, bj; + data_reference_p dr1, dr2, saved_dr1; /* dependence direction - 0 is no dependence, -1 is back, 1 is forth, 2 is both (we can stop then, merging will occur). */ - for (int ii = 0; drs1.iterate (ii, &dr1); ++ii) - for (int jj = 0; drs2.iterate (jj, &dr2); ++jj) - { - data_reference_p saved_dr1 = dr1; - int this_dir = 1; - ddr_p ddr; - /* Re-shuffle data-refs to be in dominator 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]); - if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) - this_dir = 2; - else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) - { - if (DDR_REVERSED_P (ddr)) - { - std::swap (dr1, dr2); + EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi) + { + dr1 = datarefs_vec[i]; + + EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj) + { + int res, this_dir = 1; + ddr_p ddr; + + dr2 = datarefs_vec[j]; + + /* Skip all <read, read> data dependence. */ + if (DR_IS_READ (dr1) && DR_IS_READ (dr2)) + continue; + + saved_dr1 = dr1; + /* 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 = get_data_dependence (rdg, dr1, dr2); + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + { + this_dir = 0; + 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_BASE_ADDRESS (dr2) + || !DR_OFFSET (dr1) || !DR_OFFSET (dr2) + || !DR_INIT (dr1) || !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; + /* Data dependence could be resolved by runtime alias check, + record it in ALIAS_DDRS. */ + else if (alias_ddrs != NULL) + alias_ddrs->safe_push (ddr); + /* Or simply ignore it. */ + } + else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE) + { + if (DDR_REVERSED_P (ddr)) 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) - this_dir = 2; - /* If the overlap is exact preserve stmt order. */ - else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), 1)) - ; - else - { - /* Else as the distance vector is lexicographic positive - swap the dependence direction. */ + + /* 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) + this_dir = 2; + /* 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 this_dir = -this_dir; - } - } - else - this_dir = 0; - free_dependence_relation (ddr); - if (this_dir == 2) - return 2; - else if (dir == 0) - dir = this_dir; - else if (this_dir != 0 && dir != this_dir) - return 2; - /* Shuffle "back" dr1. */ - dr1 = saved_dr1; - } + } + else + this_dir = 0; + if (this_dir == 2) + return 2; + else if (dir == 0) + dir = this_dir; + else if (this_dir != 0 && dir != this_dir) + return 2; + /* Shuffle "back" dr1. */ + dr1 = saved_dr1; + } + } return dir; } @@ -1439,11 +1759,608 @@ pgcmp (const void *v1_, const void *v2_) return v2->post - v1->post; } -/* 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. - Returns the number of distributed loops. Set *DESTROY_P to whether - LOOP needs to be destroyed. */ +/* 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 + 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 should skipped when traversing the graph. */ + +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. If IGNORE_ALIAS_P + is true, data dependence caused by possible alias between references + is ignored, as if it doesn't exist at all; otherwise all depdendences + are considered. */ + +static struct graph * +build_partition_graph (struct graph *rdg, + vec<struct partition *> *partitions, + bool ignore_alias_p) +{ + int i, j; + struct partition *partition1, *partition2; + graph *pg = new_graph (partitions->length ()); + auto_vec<ddr_p> alias_ddrs, *alias_ddrs_p; + + alias_ddrs_p = ignore_alias_p ? NULL : &alias_ddrs; + + 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. */ + alias_ddrs.truncate (0); + + dir = pg_add_dependence_edges (rdg, dir, partition1->datarefs, + partition2->datarefs, alias_ddrs_p); + + /* Add edge to partition graph if there exists dependence. There + are two types of edges. One type edge is caused by compilation + time known 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.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.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 merge strong connected components + of PARTITIONS. In this function, data dependence caused by possible + alias between references is ignored, as if it doesn't exist at all. */ + +static void +merge_dep_scc_partitions (struct graph *rdg, + vec<struct partition *> *partitions) +{ + struct partition *partition1, *partition2; + struct pg_vdata *data; + graph *pg = build_partition_graph (rdg, partitions, true); + 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 (NULL, partition1, + partition2, FUSE_SAME_SCC); + partition1->type = PTYPE_SEQUENTIAL; + (*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. Store data dependence + relations for runtime alias check in ALIAS_DDRS. */ + +static void +break_alias_scc_partitions (struct graph *rdg, + 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, partitions, false); + + 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 (NULL, 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) +{ + profile_probability prob; + basic_block cond_bb; + struct loop *nloop; + tree lhs, arg0, cond_expr = NULL_TREE; + gimple_seq cond_stmts = NULL; + gimple *call_stmt = NULL; + auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs; + + /* Generate code for runtime alias checks if necessary. */ + gcc_assert (alias_ddrs->length () > 0); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Version loop <%d> with runtime alias check\n", loop->num); + + 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); + + /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */ + if (flag_tree_loop_vectorize) + { + /* Generate internal function call for loop distribution alias check. */ + call_stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS, + 2, NULL_TREE, cond_expr); + lhs = make_ssa_name (boolean_type_node); + gimple_call_set_lhs (call_stmt, lhs); + } + else + lhs = cond_expr; + + prob = profile_probability::guessed_always ().apply_scale (9, 10); + initialize_original_copy_tables (); + nloop = loop_version (loop, lhs, &cond_bb, prob, prob.invert (), + prob, prob.invert (), true); + free_original_copy_tables (); + /* Record the original loop number in newly generated loops. In case of + distribution, the original loop will be distributed and the new loop + is kept. */ + loop->orig_loop_num = nloop->num; + nloop->orig_loop_num = nloop->num; + nloop->dont_vectorize = true; + nloop->force_vectorize = false; + + if (call_stmt) + { + /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original + loop could be destroyed. */ + arg0 = build_int_cst (integer_type_node, loop->orig_loop_num); + gimple_call_set_arg (call_stmt, 0, arg0); + gimple_seq_add_stmt_without_update (&cond_stmts, call_stmt); + } + + 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) +{ + /* 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. */ + return (alias_ddrs->length () > 0); +} + +/* 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 (NULL, 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. Returns the number of + distributed loops. Set NB_CALLS to number of generated builtin calls. + Set *DESTROY_P to whether LOOP needs to be destroyed. */ static int distribute_loop (struct loop *loop, vec<gimple *> stmts, @@ -1453,16 +2370,18 @@ 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; - auto_vec<loop_p, 3> loop_nest; + loop_nest.create (0); if (!find_loop_nest (loop, &loop_nest)) - return 0; + { + loop_nest.release (); + return 0; + } - rdg = build_rdg (loop_nest, cd); + datarefs_vec.create (20); + rdg = build_rdg (loop, cd); if (!rdg) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -1470,19 +2389,45 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, "Loop %d not distributed: failed to build the RDG.\n", loop->num); + loop_nest.release (); + free_data_refs (datarefs_vec); + return 0; + } + + if (datarefs_vec.length () > MAX_DATAREFS_NUM) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "Loop %d not distributed: too many memory references.\n", + loop->num); + + free_rdg (rdg); + loop_nest.release (); + free_data_refs (datarefs_vec); return 0; } + data_reference_p dref; + for (i = 0; datarefs_vec.iterate (i, &dref); ++i) + dref->aux = (void *) (uintptr_t) i; + if (dump_file && (dump_flags & TDF_DETAILS)) dump_rdg (dump_file, rdg); auto_vec<struct partition *, 3> partitions; rdg_build_partitions (rdg, stmts, &partitions); + auto_vec<ddr_p> alias_ddrs; + + auto_bitmap stmt_in_all_partitions; + bitmap_copy (stmt_in_all_partitions, partitions[0]->stmts); + for (i = 1; partitions.iterate (i, &partition); ++i) + bitmap_and_into (stmt_in_all_partitions, partitions[i]->stmts); + any_builtin = false; FOR_EACH_VEC_ELT (partitions, i, partition) { - classify_partition (loop, rdg, partition); + classify_partition (loop, rdg, partition, stmt_in_all_partitions); any_builtin |= partition_builtin_p (partition); } @@ -1508,13 +2453,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 (NULL, into, partition, FUSE_NON_BUILTIN); partitions.unordered_remove (i); partition_free (partition); i--; @@ -1530,14 +2469,7 @@ 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 (rdg, into, partition, FUSE_REDUCTION); partitions.unordered_remove (i); partition_free (partition); i--; @@ -1553,17 +2485,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 (rdg, into, partition, FUSE_SHARE_REF); partitions.unordered_remove (j); partition_free (partition); j--; @@ -1581,111 +2505,14 @@ 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, &partitions); + alias_ddrs.truncate (0); + if (partitions.length () > 1) + break_alias_scc_partitions (rdg, &partitions, &alias_ddrs); } + finalize_partitions (&partitions, &alias_ddrs); + nbp = partitions.length (); if (nbp == 0 || (nbp == 1 && !partition_builtin_p (partitions[0])) @@ -1695,8 +2522,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,6 +2540,15 @@ distribute_loop (struct loop *loop, vec<gimple *> stmts, } ldist_done: + loop_nest.release (); + free_data_refs (datarefs_vec); + for (hash_table<ddr_hasher>::iterator iter = ddrs_table.begin (); + iter != ddrs_table.end (); ++iter) + { + free_dependence_relation (*iter); + *iter = NULL; + } + ddrs_table.empty (); FOR_EACH_VEC_ELT (partitions, i, partition) partition_free (partition); @@ -1758,6 +2601,26 @@ pass_loop_distribution::execute (function *fun) control_dependences *cd = NULL; auto_vec<loop_p> loops_to_be_destroyed; + if (number_of_loops (fun) <= 1) + return 0; + + /* 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_num; + 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 = last_basic_block_for_fn (cfun); + rpo_num = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, true); + for (int i = 0; i < rpo_num; i++) + bb_top_order_index[rpo[i]] = i; + + free (rpo); + } + FOR_ALL_BB_FN (bb, fun) { gimple_stmt_iterator gsi; @@ -1785,6 +2648,11 @@ pass_loop_distribution::execute (function *fun) if (!optimize_loop_for_speed_p (loop)) continue; + /* Don't distribute loop if niters is unknown. */ + tree niters = number_of_latch_executions (loop); + if (niters == NULL_TREE || niters == chrec_dont_know) + continue; + /* Initialize the worklist with stmts we seed the partitions with. */ bbs = get_loop_body_in_dom_order (loop); for (i = 0; i < loop->num_nodes; ++i) @@ -1865,13 +2733,20 @@ out: 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. */ |