From af0c51ac87ab2a87caa03fa108f0d164987a2764 Mon Sep 17 00:00:00 2001 From: Ben Cheng Date: Thu, 28 Mar 2013 11:14:20 -0700 Subject: [GCC 4.8] Initial check-in of GCC 4.8.0 Change-Id: I0719d8a6d0f69b367a6ab6f10eb75622dbf12771 --- gcc-4.8/gcc/tree-loop-distribution.c | 1591 ++++++++++++++++++++++++++++++++++ 1 file changed, 1591 insertions(+) create mode 100644 gcc-4.8/gcc/tree-loop-distribution.c (limited to 'gcc-4.8/gcc/tree-loop-distribution.c') diff --git a/gcc-4.8/gcc/tree-loop-distribution.c b/gcc-4.8/gcc/tree-loop-distribution.c new file mode 100644 index 000000000..70f71b37c --- /dev/null +++ b/gcc-4.8/gcc/tree-loop-distribution.c @@ -0,0 +1,1591 @@ +/* Loop distribution. + Copyright (C) 2006-2013 Free Software Foundation, Inc. + Contributed by Georges-Andre Silber + and Sebastian Pop . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +/* This pass performs loop distribution: for example, the loop + + |DO I = 2, N + | A(I) = B(I) + C + | D(I) = A(I-1)*E + |ENDDO + + is transformed to + + |DOALL I = 2, N + | A(I) = B(I) + C + |ENDDO + | + |DOALL I = 2, N + | 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. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree-flow.h" +#include "cfgloop.h" +#include "tree-chrec.h" +#include "tree-data-ref.h" +#include "tree-scalar-evolution.h" +#include "tree-pass.h" + +enum partition_kind { + PKIND_NORMAL, PKIND_REDUCTION, PKIND_MEMSET, PKIND_MEMCPY +}; + +typedef struct partition_s +{ + bitmap stmts; + bool has_writes; + enum partition_kind kind; + /* data-references a kind != PKIND_NORMAL partition is about. */ + data_reference_p main_dr; + data_reference_p secondary_dr; +} *partition_t; + + +/* Allocate and initialize a partition from BITMAP. */ + +static partition_t +partition_alloc (bitmap stmts) +{ + partition_t partition = XCNEW (struct partition_s); + partition->stmts = stmts ? stmts : BITMAP_ALLOC (NULL); + partition->has_writes = false; + partition->kind = PKIND_NORMAL; + return partition; +} + +/* Free PARTITION. */ + +static void +partition_free (partition_t partition) +{ + BITMAP_FREE (partition->stmts); + free (partition); +} + +/* Returns true if the partition can be generated as a builtin. */ + +static bool +partition_builtin_p (partition_t partition) +{ + return partition->kind > PKIND_REDUCTION; +} + +/* Returns true if the partition has an writes. */ + +static bool +partition_has_writes (partition_t partition) +{ + return partition->has_writes; +} + +/* If bit I is not set, it means that this node represents an + operation that has already been performed, and that should not be + performed again. This is the subgraph of remaining important + computations that is passed to the DFS algorithm for avoiding to + include several times the same stores in different loops. */ +static bitmap remaining_stmts; + +/* A node of the RDG is marked in this bitmap when it has as a + predecessor a node that writes to memory. */ +static bitmap upstream_mem_writes; + +/* Returns true when DEF is an SSA_NAME defined in LOOP and used after + the LOOP. */ + +static bool +ssa_name_has_uses_outside_loop_p (tree def, loop_p loop) +{ + imm_use_iterator imm_iter; + use_operand_p use_p; + + FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def) + { + gimple use_stmt = USE_STMT (use_p); + if (!is_gimple_debug (use_stmt) + && loop != loop_containing_stmt (use_stmt)) + return true; + } + + return false; +} + +/* Returns true when STMT defines a scalar variable used after the + loop LOOP. */ + +static bool +stmt_has_scalar_dependences_outside_loop (loop_p loop, gimple stmt) +{ + def_operand_p def_p; + ssa_op_iter op_iter; + + if (gimple_code (stmt) == GIMPLE_PHI) + return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt), loop); + + FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF) + if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p), loop)) + return true; + + return false; +} + +/* Return a copy of LOOP placed before LOOP. */ + +static struct loop * +copy_loop_before (struct loop *loop) +{ + struct loop *res; + edge preheader = loop_preheader_edge (loop); + + initialize_original_copy_tables (); + res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader); + gcc_assert (res != NULL); + free_original_copy_tables (); + delete_update_ssa (); + + return res; +} + +/* Creates an empty basic block after LOOP. */ + +static void +create_bb_after_loop (struct loop *loop) +{ + edge exit = single_exit (loop); + + if (!exit) + return; + + split_edge (exit); +} + +/* Generate code for PARTITION from the code in LOOP. The loop is + copied when COPY_P is true. All the statements not flagged in the + PARTITION bitmap are removed from the loop or from its copy. The + statements are indexed in sequence inside a basic block, and the + basic blocks of a loop are taken in dom order. */ + +static void +generate_loops_for_partition (struct loop *loop, partition_t partition, + bool copy_p) +{ + unsigned i, x; + gimple_stmt_iterator bsi; + basic_block *bbs; + + if (copy_p) + { + loop = copy_loop_before (loop); + gcc_assert (loop != NULL); + create_preheader (loop, CP_SIMPLE_PREHEADERS); + create_bb_after_loop (loop); + } + + /* Remove stmts not in the PARTITION bitmap. The order in which we + visit the phi nodes and the statements is exactly as in + stmts_from_loop. */ + bbs = get_loop_body_in_dom_order (loop); + + if (MAY_HAVE_DEBUG_STMTS) + for (x = 0, i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + if (!bitmap_bit_p (partition->stmts, x++)) + reset_debug_uses (gsi_stmt (bsi)); + + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) + { + gimple stmt = gsi_stmt (bsi); + if (gimple_code (stmt) != GIMPLE_LABEL + && !is_gimple_debug (stmt) + && !bitmap_bit_p (partition->stmts, x++)) + reset_debug_uses (stmt); + } + } + + for (x = 0, i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);) + if (!bitmap_bit_p (partition->stmts, x++)) + { + gimple phi = gsi_stmt (bsi); + if (virtual_operand_p (gimple_phi_result (phi))) + mark_virtual_phi_result_for_renaming (phi); + remove_phi_node (&bsi, true); + } + else + gsi_next (&bsi); + + for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);) + { + gimple stmt = gsi_stmt (bsi); + if (gimple_code (stmt) != GIMPLE_LABEL + && !is_gimple_debug (stmt) + && !bitmap_bit_p (partition->stmts, x++)) + { + unlink_stmt_vdef (stmt); + gsi_remove (&bsi, true); + release_defs (stmt); + } + else + gsi_next (&bsi); + } + } + + free (bbs); +} + +/* Build the size argument for a memory operation call. */ + +static tree +build_size_arg_loc (location_t loc, data_reference_p dr, tree nb_iter) +{ + tree size; + size = fold_build2_loc (loc, MULT_EXPR, sizetype, + fold_convert_loc (loc, sizetype, nb_iter), + TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); + return fold_convert_loc (loc, size_type_node, size); +} + +/* Build an address argument for a memory operation call. */ + +static tree +build_addr_arg_loc (location_t loc, data_reference_p dr, tree nb_bytes) +{ + tree addr_base; + + addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr)); + addr_base = fold_convert_loc (loc, sizetype, addr_base); + + /* Test for a negative stride, iterating over every element. */ + if (tree_int_cst_sgn (DR_STEP (dr)) == -1) + { + addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base, + fold_convert_loc (loc, sizetype, nb_bytes)); + addr_base = size_binop_loc (loc, PLUS_EXPR, addr_base, + TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)))); + } + + return fold_build_pointer_plus_loc (loc, DR_BASE_ADDRESS (dr), addr_base); +} + +/* Generate a call to memset for PARTITION in LOOP. */ + +static void +generate_memset_builtin (struct loop *loop, partition_t partition) +{ + gimple_stmt_iterator gsi; + gimple stmt, fn_call; + tree nb_iter, mem, fn, nb_bytes; + location_t loc; + tree val; + + stmt = DR_STMT (partition->main_dr); + loc = gimple_location (stmt); + if (gimple_bb (stmt) == loop->latch) + nb_iter = number_of_latch_executions (loop); + else + nb_iter = number_of_exit_cond_executions (loop); + + /* The new statements will be placed before LOOP. */ + gsi = gsi_last_bb (loop_preheader_edge (loop)->src); + + nb_bytes = build_size_arg_loc (loc, partition->main_dr, nb_iter); + nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE, + false, GSI_CONTINUE_LINKING); + mem = build_addr_arg_loc (loc, partition->main_dr, nb_bytes); + mem = force_gimple_operand_gsi (&gsi, mem, true, NULL_TREE, + false, GSI_CONTINUE_LINKING); + + /* This exactly matches the pattern recognition in classify_partition. */ + val = gimple_assign_rhs1 (stmt); + if (integer_zerop (val) + || real_zerop (val) + || TREE_CODE (val) == CONSTRUCTOR) + val = integer_zero_node; + else if (integer_all_onesp (val)) + val = build_int_cst (integer_type_node, -1); + else + { + if (TREE_CODE (val) == INTEGER_CST) + val = fold_convert (integer_type_node, val); + else if (!useless_type_conversion_p (integer_type_node, TREE_TYPE (val))) + { + gimple cstmt; + tree tem = make_ssa_name (integer_type_node, NULL); + cstmt = gimple_build_assign_with_ops (NOP_EXPR, tem, val, NULL_TREE); + gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING); + val = tem; + } + } + + fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET)); + fn_call = gimple_build_call (fn, 3, mem, val, nb_bytes); + gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "generated memset"); + if (integer_zerop (val)) + fprintf (dump_file, " zero\n"); + else if (integer_all_onesp (val)) + fprintf (dump_file, " minus one\n"); + else + fprintf (dump_file, "\n"); + } +} + +/* Generate a call to memcpy for PARTITION in LOOP. */ + +static void +generate_memcpy_builtin (struct loop *loop, partition_t partition) +{ + gimple_stmt_iterator gsi; + gimple stmt, fn_call; + tree nb_iter, dest, src, fn, nb_bytes; + location_t loc; + enum built_in_function kind; + + stmt = DR_STMT (partition->main_dr); + loc = gimple_location (stmt); + if (gimple_bb (stmt) == loop->latch) + nb_iter = number_of_latch_executions (loop); + else + nb_iter = number_of_exit_cond_executions (loop); + + /* The new statements will be placed before LOOP. */ + gsi = gsi_last_bb (loop_preheader_edge (loop)->src); + + nb_bytes = build_size_arg_loc (loc, partition->main_dr, nb_iter); + nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE, + false, GSI_CONTINUE_LINKING); + dest = build_addr_arg_loc (loc, partition->main_dr, nb_bytes); + src = build_addr_arg_loc (loc, partition->secondary_dr, nb_bytes); + if (ptr_derefs_may_alias_p (dest, src)) + kind = BUILT_IN_MEMMOVE; + else + kind = BUILT_IN_MEMCPY; + + dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE, + false, GSI_CONTINUE_LINKING); + src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE, + false, GSI_CONTINUE_LINKING); + fn = build_fold_addr_expr (builtin_decl_implicit (kind)); + fn_call = gimple_build_call (fn, 3, dest, src, nb_bytes); + gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (kind == BUILT_IN_MEMCPY) + fprintf (dump_file, "generated memcpy\n"); + else + fprintf (dump_file, "generated memmove\n"); + } +} + +/* Remove and destroy the loop LOOP. */ + +static void +destroy_loop (struct loop *loop) +{ + unsigned nbbs = loop->num_nodes; + edge exit = single_exit (loop); + basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest; + basic_block *bbs; + unsigned i; + + bbs = get_loop_body_in_dom_order (loop); + + redirect_edge_pred (exit, src); + exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE); + exit->flags |= EDGE_FALLTHRU; + cancel_loop_tree (loop); + rescan_loop_exit (exit, false, true); + + for (i = 0; i < nbbs; i++) + { + /* We have made sure to not leave any dangling uses of SSA + names defined in the loop. With the exception of virtuals. + Make sure we replace all uses of virtual defs that will remain + outside of the loop with the bare symbol as delete_basic_block + will release them. */ + gimple_stmt_iterator gsi; + for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple phi = gsi_stmt (gsi); + if (virtual_operand_p (gimple_phi_result (phi))) + mark_virtual_phi_result_for_renaming (phi); + } + for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + tree vdef = gimple_vdef (stmt); + if (vdef && TREE_CODE (vdef) == SSA_NAME) + mark_virtual_operand_for_renaming (vdef); + } + delete_basic_block (bbs[i]); + } + free (bbs); + + set_immediate_dominator (CDI_DOMINATORS, dest, + recompute_dominator (CDI_DOMINATORS, dest)); +} + +/* Generates code for PARTITION. */ + +static void +generate_code_for_partition (struct loop *loop, + partition_t partition, bool copy_p) +{ + switch (partition->kind) + { + case PKIND_MEMSET: + generate_memset_builtin (loop, partition); + /* If this is the last partition for which we generate code, we have + to destroy the loop. */ + if (!copy_p) + destroy_loop (loop); + break; + + case PKIND_MEMCPY: + generate_memcpy_builtin (loop, partition); + /* If this is the last partition for which we generate code, we have + to destroy the loop. */ + if (!copy_p) + destroy_loop (loop); + break; + + case PKIND_REDUCTION: + /* Reductions all have to be in the last partition. */ + gcc_assert (!copy_p); + case PKIND_NORMAL: + generate_loops_for_partition (loop, partition, copy_p); + break; + + default: + gcc_unreachable (); + } +} + + +/* Returns true if the node V of RDG cannot be recomputed. */ + +static bool +rdg_cannot_recompute_vertex_p (struct graph *rdg, int v) +{ + if (RDG_MEM_WRITE_STMT (rdg, v)) + return true; + + return false; +} + +/* Returns true when the vertex V has already been generated in the + current partition (V is in PROCESSED), or when V belongs to another + partition and cannot be recomputed (V is not in REMAINING_STMTS). */ + +static inline bool +already_processed_vertex_p (bitmap processed, int v) +{ + return (bitmap_bit_p (processed, v) + || !bitmap_bit_p (remaining_stmts, v)); +} + +/* Returns NULL when there is no anti-dependence among the successors + of vertex V, otherwise returns the edge with the anti-dep. */ + +static struct graph_edge * +has_anti_dependence (struct vertex *v) +{ + struct graph_edge *e; + + if (v->succ) + for (e = v->succ; e; e = e->succ_next) + if (RDGE_TYPE (e) == anti_dd) + return e; + + return NULL; +} + +/* Returns true when V has an anti-dependence edge among its successors. */ + +static bool +predecessor_has_mem_write (struct graph *rdg, struct vertex *v) +{ + struct graph_edge *e; + + if (v->pred) + for (e = v->pred; e; e = e->pred_next) + if (bitmap_bit_p (upstream_mem_writes, e->src) + /* Don't consider flow channels: a write to memory followed + by a read from memory. These channels allow the split of + the RDG in different partitions. */ + && !RDG_MEM_WRITE_STMT (rdg, e->src)) + return true; + + return false; +} + +/* Initializes the upstream_mem_writes bitmap following the + information from RDG. */ + +static void +mark_nodes_having_upstream_mem_writes (struct graph *rdg) +{ + int v, x; + bitmap seen = BITMAP_ALLOC (NULL); + + for (v = rdg->n_vertices - 1; v >= 0; v--) + if (!bitmap_bit_p (seen, v)) + { + unsigned i; + vec nodes; + nodes.create (3); + + graphds_dfs (rdg, &v, 1, &nodes, false, NULL); + + FOR_EACH_VEC_ELT (nodes, i, x) + { + if (!bitmap_set_bit (seen, x)) + continue; + + if (RDG_MEM_WRITE_STMT (rdg, x) + || predecessor_has_mem_write (rdg, &(rdg->vertices[x])) + /* In anti dependences the read should occur before + the write, this is why both the read and the write + should be placed in the same partition. */ + || has_anti_dependence (&(rdg->vertices[x]))) + { + bitmap_set_bit (upstream_mem_writes, x); + } + } + + nodes.release (); + } +} + +/* Returns true when vertex u has a memory write node as a predecessor + in RDG. */ + +static bool +has_upstream_mem_writes (int u) +{ + return bitmap_bit_p (upstream_mem_writes, u); +} + +static void rdg_flag_vertex_and_dependent (struct graph *, int, partition_t, + bitmap, bitmap); + +/* Flag the uses of U stopping following the information from + upstream_mem_writes. */ + +static void +rdg_flag_uses (struct graph *rdg, int u, partition_t partition, bitmap loops, + bitmap processed) +{ + use_operand_p use_p; + struct vertex *x = &(rdg->vertices[u]); + gimple stmt = RDGV_STMT (x); + struct graph_edge *anti_dep = has_anti_dependence (x); + + /* Keep in the same partition the destination of an antidependence, + because this is a store to the exact same location. Putting this + in another partition is bad for cache locality. */ + if (anti_dep) + { + int v = anti_dep->dest; + + if (!already_processed_vertex_p (processed, v)) + rdg_flag_vertex_and_dependent (rdg, v, partition, loops, + processed); + } + + if (gimple_code (stmt) != GIMPLE_PHI) + { + if ((use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P) + { + tree use = USE_FROM_PTR (use_p); + + if (TREE_CODE (use) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (use)) + { + gimple def_stmt = SSA_NAME_DEF_STMT (use); + int v = rdg_vertex_for_stmt (rdg, def_stmt); + + if (v >= 0 + && !already_processed_vertex_p (processed, v)) + rdg_flag_vertex_and_dependent (rdg, v, partition, loops, + processed); + } + } + } + + if (is_gimple_assign (stmt) && has_upstream_mem_writes (u)) + { + tree op0 = gimple_assign_lhs (stmt); + + /* Scalar channels don't have enough space for transmitting data + between tasks, unless we add more storage by privatizing. */ + if (is_gimple_reg (op0)) + { + use_operand_p use_p; + imm_use_iterator iter; + + FOR_EACH_IMM_USE_FAST (use_p, iter, op0) + { + int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p)); + + if (!already_processed_vertex_p (processed, v)) + rdg_flag_vertex_and_dependent (rdg, v, partition, loops, + processed); + } + } + } +} + +/* Flag V from RDG as part of PARTITION, and also flag its loop number + in LOOPS. */ + +static void +rdg_flag_vertex (struct graph *rdg, int v, partition_t partition, bitmap loops) +{ + struct loop *loop; + + if (!bitmap_set_bit (partition->stmts, v)) + return; + + loop = loop_containing_stmt (RDG_STMT (rdg, v)); + bitmap_set_bit (loops, loop->num); + + if (rdg_cannot_recompute_vertex_p (rdg, v)) + { + partition->has_writes = true; + bitmap_clear_bit (remaining_stmts, v); + } +} + +/* Flag in the bitmap PARTITION the vertex V and all its predecessors. + Also flag their loop number in LOOPS. */ + +static void +rdg_flag_vertex_and_dependent (struct graph *rdg, int v, partition_t partition, + bitmap loops, bitmap processed) +{ + unsigned i; + vec nodes; + nodes.create (3); + int x; + + bitmap_set_bit (processed, v); + rdg_flag_uses (rdg, v, partition, loops, processed); + graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts); + rdg_flag_vertex (rdg, v, partition, loops); + + FOR_EACH_VEC_ELT (nodes, i, x) + if (!already_processed_vertex_p (processed, x)) + rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed); + + nodes.release (); +} + +/* Initialize CONDS with all the condition statements from the basic + blocks of LOOP. */ + +static void +collect_condition_stmts (struct loop *loop, vec *conds) +{ + unsigned i; + edge e; + vec exits = get_loop_exit_edges (loop); + + FOR_EACH_VEC_ELT (exits, i, e) + { + gimple cond = last_stmt (e->src); + + if (cond) + conds->safe_push (cond); + } + + exits.release (); +} + +/* Add to PARTITION all the exit condition statements for LOOPS + together with all their dependent statements determined from + RDG. */ + +static void +rdg_flag_loop_exits (struct graph *rdg, bitmap loops, partition_t partition, + bitmap processed) +{ + unsigned i; + bitmap_iterator bi; + vec conds; + conds.create (3); + + EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi) + collect_condition_stmts (get_loop (i), &conds); + + while (!conds.is_empty ()) + { + gimple cond = conds.pop (); + int v = rdg_vertex_for_stmt (rdg, cond); + bitmap new_loops = BITMAP_ALLOC (NULL); + + if (!already_processed_vertex_p (processed, v)) + rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed); + + EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi) + if (bitmap_set_bit (loops, i)) + collect_condition_stmts (get_loop (i), &conds); + + BITMAP_FREE (new_loops); + } + + conds.release (); +} + +/* Returns a bitmap in which all the statements needed for computing + the strongly connected component C of the RDG are flagged, also + including the loop exit conditions. */ + +static partition_t +build_rdg_partition_for_component (struct graph *rdg, rdgc c) +{ + int i, v; + partition_t partition = partition_alloc (NULL); + bitmap loops = BITMAP_ALLOC (NULL); + bitmap processed = BITMAP_ALLOC (NULL); + + FOR_EACH_VEC_ELT (c->vertices, i, v) + if (!already_processed_vertex_p (processed, v)) + rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed); + + rdg_flag_loop_exits (rdg, loops, partition, processed); + + BITMAP_FREE (processed); + BITMAP_FREE (loops); + return partition; +} + +/* Free memory for COMPONENTS. */ + +static void +free_rdg_components (vec components) +{ + int i; + rdgc x; + + FOR_EACH_VEC_ELT (components, i, x) + { + x->vertices.release (); + free (x); + } + + components.release (); +} + +/* Build the COMPONENTS vector with the strongly connected components + of RDG in which the STARTING_VERTICES occur. */ + +static void +rdg_build_components (struct graph *rdg, vec starting_vertices, + vec *components) +{ + int i, v; + bitmap saved_components = BITMAP_ALLOC (NULL); + int n_components = graphds_scc (rdg, NULL); + /* ??? Macros cannot process template types with more than one + argument, so we need this typedef. */ + typedef vec vec_int_heap; + vec *all_components = XNEWVEC (vec_int_heap, n_components); + + for (i = 0; i < n_components; i++) + all_components[i].create (3); + + for (i = 0; i < rdg->n_vertices; i++) + all_components[rdg->vertices[i].component].safe_push (i); + + FOR_EACH_VEC_ELT (starting_vertices, i, v) + { + int c = rdg->vertices[v].component; + + if (bitmap_set_bit (saved_components, c)) + { + rdgc x = XCNEW (struct rdg_component); + x->num = c; + x->vertices = all_components[c]; + + components->safe_push (x); + } + } + + for (i = 0; i < n_components; i++) + if (!bitmap_bit_p (saved_components, i)) + all_components[i].release (); + + free (all_components); + BITMAP_FREE (saved_components); +} + +/* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP. + For the moment we detect only the memset zero pattern. */ + +static void +classify_partition (loop_p loop, struct graph *rdg, partition_t partition) +{ + bitmap_iterator bi; + unsigned i; + tree nb_iter; + data_reference_p single_load, single_store; + bool volatiles_p = false; + + partition->kind = PKIND_NORMAL; + partition->main_dr = NULL; + partition->secondary_dr = NULL; + + EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi) + { + gimple stmt = RDG_STMT (rdg, i); + + if (gimple_has_volatile_ops (stmt)) + volatiles_p = true; + + /* If the stmt has uses outside of the loop fail. + ??? If the stmt is generated in another partition that + is not created as builtin we can ignore this. */ + if (stmt_has_scalar_dependences_outside_loop (loop, stmt)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "not generating builtin, partition has " + "scalar uses outside of the loop\n"); + partition->kind = PKIND_REDUCTION; + return; + } + } + + /* Perform general partition disqualification for builtins. */ + if (volatiles_p + || !flag_tree_loop_distribute_patterns) + return; + + nb_iter = number_of_exit_cond_executions (loop); + if (!nb_iter || nb_iter == chrec_dont_know) + return; + + /* Detect memset and memcpy. */ + single_load = NULL; + single_store = NULL; + EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi) + { + gimple stmt = RDG_STMT (rdg, i); + data_reference_p dr; + unsigned j; + + if (gimple_code (stmt) == GIMPLE_PHI) + continue; + + /* Any scalar stmts are ok. */ + if (!gimple_vuse (stmt)) + continue; + + /* Otherwise just regular loads/stores. */ + if (!gimple_assign_single_p (stmt)) + return; + + /* But exactly one store and/or load. */ + for (j = 0; RDG_DATAREFS (rdg, i).iterate (j, &dr); ++j) + { + if (DR_IS_READ (dr)) + { + if (single_load != NULL) + return; + single_load = dr; + } + else + { + if (single_store != NULL) + return; + single_store = dr; + } + } + } + + if (single_store && !single_load) + { + gimple stmt = DR_STMT (single_store); + tree rhs = gimple_assign_rhs1 (stmt); + if (!(integer_zerop (rhs) + || integer_all_onesp (rhs) + || real_zerop (rhs) + || (TREE_CODE (rhs) == CONSTRUCTOR + && !TREE_CLOBBER_P (rhs)) + || (INTEGRAL_TYPE_P (TREE_TYPE (rhs)) + && (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) + == TYPE_MODE (unsigned_char_type_node))))) + return; + if (TREE_CODE (rhs) == SSA_NAME + && !SSA_NAME_IS_DEFAULT_DEF (rhs) + && flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs)))) + return; + if (!adjacent_dr_p (single_store)) + return; + partition->kind = PKIND_MEMSET; + partition->main_dr = single_store; + } + else if (single_store && single_load) + { + gimple store = DR_STMT (single_store); + gimple load = DR_STMT (single_load); + /* Direct aggregate copy or via an SSA name temporary. */ + if (load != store + && gimple_assign_lhs (load) != gimple_assign_rhs1 (store)) + return; + if (!adjacent_dr_p (single_store) + || !adjacent_dr_p (single_load) + || !operand_equal_p (DR_STEP (single_store), + DR_STEP (single_load), 0)) + return; + /* Now check that if there is a dependence this dependence is + of a suitable form for memmove. */ + vec loops = vNULL; + ddr_p ddr; + loops.safe_push (loop); + ddr = initialize_data_dependence_relation (single_load, single_store, + loops); + compute_affine_dependence (ddr, loop); + if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) + { + free_dependence_relation (ddr); + loops.release (); + return; + } + if (DDR_ARE_DEPENDENT (ddr) != chrec_known) + { + if (DDR_NUM_DIST_VECTS (ddr) == 0) + { + free_dependence_relation (ddr); + loops.release (); + 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; + } + } + } + free_dependence_relation (ddr); + loops.release (); + partition->kind = PKIND_MEMCPY; + partition->main_dr = single_store; + partition->secondary_dr = single_load; + } +} + +/* 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. */ + +static bool +similar_memory_accesses (struct graph *rdg, partition_t partition1, + partition_t partition2) +{ + unsigned i, j, k, l; + bitmap_iterator bi, bj; + data_reference_p ref1, ref2; + + /* First check whether in the intersection of the two partitions are + any loads or stores. Common loads are the situation that happens + most often. */ + EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi) + if (RDG_MEM_WRITE_STMT (rdg, i) + || 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; + } + } + + return false; +} + +/* Aggregate several components into a useful partition that is + registered in the PARTITIONS vector. Partitions will be + distributed in different loops. */ + +static void +rdg_build_partitions (struct graph *rdg, vec components, + vec *other_stores, + vec *partitions, bitmap processed) +{ + int i; + rdgc x; + partition_t partition = partition_alloc (NULL); + + FOR_EACH_VEC_ELT (components, i, x) + { + partition_t np; + int v = x->vertices[0]; + + if (bitmap_bit_p (processed, v)) + continue; + + np = build_rdg_partition_for_component (rdg, x); + bitmap_ior_into (partition->stmts, np->stmts); + partition->has_writes = partition_has_writes (np); + bitmap_ior_into (processed, np->stmts); + partition_free (np); + + if (partition_has_writes (partition)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "ldist useful partition:\n"); + dump_bitmap (dump_file, partition->stmts); + } + + partitions->safe_push (partition); + partition = partition_alloc (NULL); + } + } + + /* Add the nodes from the RDG that were not marked as processed, and + that are used outside the current loop. These are scalar + computations that are not yet part of previous partitions. */ + for (i = 0; i < rdg->n_vertices; i++) + if (!bitmap_bit_p (processed, i) + && rdg_defs_used_in_other_loops_p (rdg, i)) + other_stores->safe_push (i); + + /* If there are still statements left in the OTHER_STORES array, + create other components and partitions with these stores and + their dependences. */ + if (other_stores->length () > 0) + { + vec comps; + comps.create (3); + vec foo; + foo.create (3); + + rdg_build_components (rdg, *other_stores, &comps); + rdg_build_partitions (rdg, comps, &foo, partitions, processed); + + foo.release (); + free_rdg_components (comps); + } + + /* If there is something left in the last partition, save it. */ + if (bitmap_count_bits (partition->stmts) > 0) + partitions->safe_push (partition); + else + partition_free (partition); +} + +/* Dump to FILE the PARTITIONS. */ + +static void +dump_rdg_partitions (FILE *file, vec partitions) +{ + int i; + partition_t partition; + + FOR_EACH_VEC_ELT (partitions, i, partition) + debug_bitmap_file (file, partition->stmts); +} + +/* Debug PARTITIONS. */ +extern void debug_rdg_partitions (vec ); + +DEBUG_FUNCTION void +debug_rdg_partitions (vec partitions) +{ + dump_rdg_partitions (stderr, partitions); +} + +/* Returns the number of read and write operations in the RDG. */ + +static int +number_of_rw_in_rdg (struct graph *rdg) +{ + int i, res = 0; + + for (i = 0; i < rdg->n_vertices; i++) + { + if (RDG_MEM_WRITE_STMT (rdg, i)) + ++res; + + if (RDG_MEM_READS_STMT (rdg, i)) + ++res; + } + + return res; +} + +/* Returns the number of read and write operations in a PARTITION of + the RDG. */ + +static int +number_of_rw_in_partition (struct graph *rdg, partition_t partition) +{ + int res = 0; + unsigned i; + bitmap_iterator ii; + + EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii) + { + if (RDG_MEM_WRITE_STMT (rdg, i)) + ++res; + + if (RDG_MEM_READS_STMT (rdg, i)) + ++res; + } + + return res; +} + +/* Returns true when one of the PARTITIONS contains all the read or + write operations of RDG. */ + +static bool +partition_contains_all_rw (struct graph *rdg, + vec partitions) +{ + int i; + partition_t partition; + int nrw = number_of_rw_in_rdg (rdg); + + FOR_EACH_VEC_ELT (partitions, i, partition) + if (nrw == number_of_rw_in_partition (rdg, partition)) + return true; + + return false; +} + +/* Generate code from STARTING_VERTICES in RDG. Returns the number of + distributed loops. */ + +static int +ldist_gen (struct loop *loop, struct graph *rdg, + vec starting_vertices) +{ + int i, nbp; + vec components; + components.create (3); + vec partitions; + partitions.create (3); + vec other_stores; + other_stores.create (3); + partition_t partition; + bitmap processed = BITMAP_ALLOC (NULL); + bool any_builtin; + + remaining_stmts = BITMAP_ALLOC (NULL); + upstream_mem_writes = BITMAP_ALLOC (NULL); + + for (i = 0; i < rdg->n_vertices; i++) + { + bitmap_set_bit (remaining_stmts, i); + + /* Save in OTHER_STORES all the memory writes that are not in + STARTING_VERTICES. */ + if (RDG_MEM_WRITE_STMT (rdg, i)) + { + int v; + unsigned j; + bool found = false; + + FOR_EACH_VEC_ELT (starting_vertices, j, v) + if (i == v) + { + found = true; + break; + } + + if (!found) + other_stores.safe_push (i); + } + } + + mark_nodes_having_upstream_mem_writes (rdg); + rdg_build_components (rdg, starting_vertices, &components); + rdg_build_partitions (rdg, components, &other_stores, &partitions, + processed); + BITMAP_FREE (processed); + + any_builtin = false; + FOR_EACH_VEC_ELT (partitions, i, partition) + { + classify_partition (loop, rdg, partition); + any_builtin |= partition_builtin_p (partition); + } + + /* If we are only distributing patterns fuse all partitions that + were not properly classified as builtins. Else fuse partitions + with similar memory accesses. */ + if (!flag_tree_loop_distribution) + { + partition_t into; + /* If we did not detect any builtin simply bail out. */ + if (!any_builtin) + { + nbp = 0; + goto ldist_done; + } + /* Only fuse adjacent non-builtin partitions, see PR53616. + ??? Use dependence information to improve partition ordering. */ + i = 0; + do + { + for (; partitions.iterate (i, &into); ++i) + if (!partition_builtin_p (into)) + break; + for (++i; partitions.iterate (i, &partition); ++i) + if (!partition_builtin_p (partition)) + { + bitmap_ior_into (into->stmts, partition->stmts); + if (partition->kind == PKIND_REDUCTION) + into->kind = PKIND_REDUCTION; + partitions.ordered_remove (i); + partition_free (partition); + i--; + } + else + break; + } + while ((unsigned) i < partitions.length ()); + } + else + { + partition_t into; + int j; + for (i = 0; partitions.iterate (i, &into); ++i) + { + if (partition_builtin_p (into)) + continue; + for (j = i + 1; + partitions.iterate (j, &partition); ++j) + { + if (!partition_builtin_p (partition) + /* ??? The following is horribly inefficient, + we are re-computing and analyzing data-references + of the stmts in the partitions all the time. */ + && similar_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"); + } + bitmap_ior_into (into->stmts, partition->stmts); + if (partition->kind == PKIND_REDUCTION) + into->kind = PKIND_REDUCTION; + partitions.ordered_remove (j); + partition_free (partition); + j--; + } + } + } + } + + /* Fuse all reduction partitions into the last. */ + if (partitions.length () > 1) + { + partition_t into = partitions.last (); + for (i = partitions.length () - 2; i >= 0; --i) + { + partition_t what = partitions[i]; + if (what->kind == PKIND_REDUCTION) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "fusing partitions\n"); + dump_bitmap (dump_file, into->stmts); + dump_bitmap (dump_file, what->stmts); + fprintf (dump_file, "because the latter has reductions\n"); + } + bitmap_ior_into (into->stmts, what->stmts); + into->kind = PKIND_REDUCTION; + partitions.ordered_remove (i); + partition_free (what); + } + } + } + + nbp = partitions.length (); + if (nbp == 0 + || (nbp == 1 && !partition_builtin_p (partitions[0])) + || (nbp > 1 && partition_contains_all_rw (rdg, partitions))) + { + nbp = 0; + goto ldist_done; + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_rdg_partitions (dump_file, partitions); + + FOR_EACH_VEC_ELT (partitions, i, partition) + generate_code_for_partition (loop, partition, i < nbp - 1); + + ldist_done: + + BITMAP_FREE (remaining_stmts); + BITMAP_FREE (upstream_mem_writes); + + FOR_EACH_VEC_ELT (partitions, i, partition) + partition_free (partition); + + other_stores.release (); + partitions.release (); + free_rdg_components (components); + return nbp; +} + +/* Distributes the code from LOOP in such a way that producer + statements are placed before consumer statements. When STMTS is + NULL, performs the maximal distribution, if STMTS is not NULL, + tries to separate only these statements from the LOOP's body. + Returns the number of distributed loops. */ + +static int +distribute_loop (struct loop *loop, vec stmts) +{ + int res = 0; + struct graph *rdg; + gimple s; + unsigned i; + vec vertices; + vec dependence_relations; + vec datarefs; + vec loop_nest; + + datarefs.create (10); + dependence_relations.create (100); + loop_nest.create (3); + rdg = build_rdg (loop, &loop_nest, &dependence_relations, &datarefs); + + if (!rdg) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "FIXME: Loop %d not distributed: failed to build the RDG.\n", + loop->num); + + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); + loop_nest.release (); + return res; + } + + vertices.create (3); + + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_rdg (dump_file, rdg); + + FOR_EACH_VEC_ELT (stmts, i, s) + { + int v = rdg_vertex_for_stmt (rdg, s); + + if (v >= 0) + { + vertices.safe_push (v); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, + "ldist asked to generate code for vertex %d\n", v); + } + } + + res = ldist_gen (loop, rdg, vertices); + vertices.release (); + free_rdg (rdg); + free_dependence_relations (dependence_relations); + free_data_refs (datarefs); + loop_nest.release (); + return res; +} + +/* Distribute all loops in the current function. */ + +static unsigned int +tree_loop_distribution (void) +{ + struct loop *loop; + loop_iterator li; + bool changed = false; + basic_block bb; + + FOR_ALL_BB (bb) + { + gimple_stmt_iterator gsi; + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + gimple_set_uid (gsi_stmt (gsi), -1); + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + gimple_set_uid (gsi_stmt (gsi), -1); + } + + /* We can at the moment only distribute non-nested loops, thus restrict + walking to innermost loops. */ + FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST) + { + vec work_list = vNULL; + basic_block *bbs; + int num = loop->num; + int nb_generated_loops = 0; + unsigned int i; + + /* If the loop doesn't have a single exit we will fail anyway, + so do that early. */ + if (!single_exit (loop)) + continue; + + /* Only optimize hot loops. */ + if (!optimize_loop_for_speed_p (loop)) + continue; + + /* Only distribute loops with a header and latch for now. */ + if (loop->num_nodes > 2) + 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) + { + gimple_stmt_iterator gsi; + for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + /* Distribute stmts which have defs that are used outside of + the loop. */ + if (stmt_has_scalar_dependences_outside_loop (loop, stmt)) + ; + /* Otherwise only distribute stores for now. */ + else if (!gimple_assign_single_p (stmt) + || is_gimple_reg (gimple_assign_lhs (stmt))) + continue; + + work_list.safe_push (stmt); + } + } + free (bbs); + + if (work_list.length () > 0) + nb_generated_loops = distribute_loop (loop, work_list); + + if (nb_generated_loops > 0) + changed = true; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + if (nb_generated_loops > 1) + fprintf (dump_file, "Loop %d distributed: split to %d loops.\n", + num, nb_generated_loops); + else + fprintf (dump_file, "Loop %d is the same.\n", num); + } + + work_list.release (); + } + + if (changed) + { + mark_virtual_operands_for_renaming (cfun); + rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); + } + +#ifdef ENABLE_CHECKING + verify_loop_structure (); +#endif + + return 0; +} + +static bool +gate_tree_loop_distribution (void) +{ + return flag_tree_loop_distribution + || flag_tree_loop_distribute_patterns; +} + +struct gimple_opt_pass pass_loop_distribution = +{ + { + GIMPLE_PASS, + "ldist", /* name */ + OPTGROUP_LOOP, /* optinfo_flags */ + gate_tree_loop_distribution, /* gate */ + tree_loop_distribution, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_LOOP_DISTRIBUTION, /* tv_id */ + PROP_cfg | PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_ggc_collect + | TODO_verify_ssa /* todo_flags_finish */ + } +}; -- cgit v1.2.3