/* Loop distribution.
- Copyright (C) 2006-2013 Free Software Foundation, Inc.
+ Copyright (C) 2006-2015 Free Software Foundation, Inc.
Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
and Sebastian Pop <sebastian.pop@amd.com>.
#include "config.h"
#include "system.h"
#include "coretypes.h"
+#include "alias.h"
+#include "symtab.h"
+#include "options.h"
#include "tree.h"
+#include "fold-const.h"
+#include "predict.h"
+#include "tm.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
+#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "stor-layout.h"
#include "gimple-ssa.h"
#include "tree-cfg.h"
#include "tree-phinodes.h"
#include "ssa-iterators.h"
+#include "stringpool.h"
#include "tree-ssanames.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop.h"
dot_rdg (struct graph *rdg)
{
/* When debugging, you may want to enable the following code. */
-#if 1
+#ifdef HAVE_POPEN
FILE *file = popen ("dot -Tx11", "w");
if (!file)
return;
for (i = 0; i < loop->num_nodes; i++)
{
basic_block bb = bbs[i];
- gimple_stmt_iterator bsi;
- gimple stmt;
- for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
- if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi))))
- stmts->safe_push (gsi_stmt (bsi));
+ for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
+ gsi_next (&bsi))
+ if (!virtual_operand_p (gimple_phi_result (bsi.phi ())))
+ stmts->safe_push (bsi.phi ());
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
+ gsi_next (&bsi))
{
- stmt = gsi_stmt (bsi);
+ gimple stmt = gsi_stmt (bsi);
if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
stmts->safe_push (stmt);
}
build_rdg (vec<loop_p> loop_nest, control_dependences *cd)
{
struct graph *rdg;
- vec<gimple> stmts;
vec<data_reference_p> datarefs;
/* Create the RDG vertices from the stmts of the loop nest. */
- stmts.create (10);
+ auto_vec<gimple, 10> stmts;
stmts_from_loop (loop_nest[0], &stmts);
rdg = new_graph (stmts.length ());
datarefs.create (10);
if (!create_rdg_vertices (rdg, stmts, loop_nest[0], &datarefs))
{
- stmts.release ();
datarefs.release ();
free_rdg (rdg);
return NULL;
data_reference_p main_dr;
data_reference_p secondary_dr;
tree niter;
+ bool plus_one;
} *partition_t;
edge preheader = loop_preheader_edge (loop);
initialize_original_copy_tables ();
- res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
+ res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, NULL, preheader);
gcc_assert (res != NULL);
free_original_copy_tables ();
delete_update_ssa ();
bool copy_p)
{
unsigned i;
- gimple_stmt_iterator bsi;
basic_block *bbs;
if (copy_p)
{
basic_block bb = bbs[i];
- for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
+ gsi_next (&bsi))
{
- gimple phi = gsi_stmt (bsi);
+ gphi *phi = bsi.phi ();
if (!virtual_operand_p (gimple_phi_result (phi))
&& !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
reset_debug_uses (phi);
}
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
{
gimple stmt = gsi_stmt (bsi);
if (gimple_code (stmt) != GIMPLE_LABEL
{
basic_block bb = bbs[i];
- for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
+ for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
{
- gimple phi = gsi_stmt (bsi);
+ gphi *phi = bsi.phi ();
if (!virtual_operand_p (gimple_phi_result (phi))
&& !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
remove_phi_node (&bsi, true);
gsi_next (&bsi);
}
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
+ for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
{
gimple stmt = gsi_stmt (bsi);
if (gimple_code (stmt) != GIMPLE_LABEL
{
/* Choose an arbitrary path through the empty CFG part
that this unnecessary control stmt controls. */
- if (gimple_code (stmt) == GIMPLE_COND)
+ if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
{
- gimple_cond_make_false (stmt);
+ gimple_cond_make_false (cond_stmt);
update_stmt (stmt);
}
else if (gimple_code (stmt) == GIMPLE_SWITCH)
{
+ gswitch *switch_stmt = as_a <gswitch *> (stmt);
gimple_switch_set_index
- (stmt, CASE_LOW (gimple_switch_label (stmt, 1)));
+ (switch_stmt, CASE_LOW (gimple_switch_label (switch_stmt, 1)));
update_stmt (stmt);
}
else
/* 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)
+build_size_arg_loc (location_t loc, data_reference_p dr, tree nb_iter,
+ bool plus_one)
{
- tree size;
- size = fold_build2_loc (loc, MULT_EXPR, sizetype,
- fold_convert_loc (loc, sizetype, nb_iter),
+ tree size = fold_convert_loc (loc, sizetype, nb_iter);
+ if (plus_one)
+ size = size_binop (PLUS_EXPR, size, size_one_node);
+ size = fold_build2_loc (loc, MULT_EXPR, sizetype, size,
TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
- return fold_convert_loc (loc, size_type_node, size);
+ size = fold_convert_loc (loc, size_type_node, size);
+ return size;
}
/* Build an address argument for a memory operation call. */
/* 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, partition->niter);
+ nb_bytes = build_size_arg_loc (loc, partition->main_dr, partition->niter,
+ partition->plus_one);
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);
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);
+ tree tem = make_ssa_name (integer_type_node);
+ gimple cstmt = gimple_build_assign (tem, NOP_EXPR, val);
gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING);
val = tem;
}
/* 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, partition->niter);
+ nb_bytes = build_size_arg_loc (loc, partition->main_dr, partition->niter,
+ partition->plus_one);
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);
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))
+ for (gphi_iterator gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
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))
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
tree vdef = gimple_vdef (stmt);
build_rdg_partition_for_vertex (struct graph *rdg, int v)
{
partition_t partition = partition_alloc (NULL, NULL);
- vec<int> nodes;
+ auto_vec<int, 3> nodes;
unsigned i;
int x;
- nodes.create (3);
graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
FOR_EACH_VEC_ELT (nodes, i, x)
loop_containing_stmt (RDG_STMT (rdg, x))->num);
}
- nodes.release ();
return partition;
}
tree nb_iter;
data_reference_p single_load, single_store;
bool volatiles_p = false;
+ bool plus_one = false;
partition->kind = PKIND_NORMAL;
partition->main_dr = NULL;
partition->secondary_dr = NULL;
partition->niter = NULL_TREE;
+ partition->plus_one = false;
EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
{
if (!single_store)
return;
- if (!dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
- gimple_bb (DR_STMT (single_store))))
- nb_iter = number_of_latch_executions (loop);
- else
- nb_iter = number_of_exit_cond_executions (loop);
+ nb_iter = number_of_latch_executions (loop);
if (!nb_iter || nb_iter == chrec_dont_know)
return;
+ if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
+ gimple_bb (DR_STMT (single_store))))
+ plus_one = true;
if (single_store && !single_load)
{
partition->kind = PKIND_MEMSET;
partition->main_dr = single_store;
partition->niter = nb_iter;
+ partition->plus_one = plus_one;
}
else if (single_store && single_load)
{
partition->main_dr = single_store;
partition->secondary_dr = single_load;
partition->niter = nb_iter;
+ partition->plus_one = plus_one;
}
}
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)))
{
- data_reference_p tem = dr1;
- dr1 = dr2;
- dr2 = tem;
+ std::swap (dr1, dr2);
this_dir = -this_dir;
}
ddr = initialize_data_dependence_relation (dr1, dr2, loops);
{
if (DDR_REVERSED_P (ddr))
{
- data_reference_p tem = dr1;
- dr1 = dr2;
- dr2 = tem;
+ std::swap (dr1, dr2);
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) == 0)
+ 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. */
+ this_dir = -this_dir;
+ }
}
else
this_dir = 0;
dir = this_dir;
else if (dir != this_dir)
return 2;
+ /* Shuffle "back" dr1. */
+ dr1 = saved_dr1;
}
return dir;
}
control_dependences *cd, int *nb_calls)
{
struct graph *rdg;
- vec<loop_p> loop_nest;
- vec<partition_t> partitions;
partition_t partition;
bool any_builtin;
int i, nbp;
int num_sccs = 1;
*nb_calls = 0;
- loop_nest.create (3);
+ auto_vec<loop_p, 3> loop_nest;
if (!find_loop_nest (loop, &loop_nest))
- {
- loop_nest.release ();
- return 0;
- }
+ return 0;
rdg = build_rdg (loop_nest, cd);
if (!rdg)
"Loop %d not distributed: failed to build the RDG.\n",
loop->num);
- loop_nest.release ();
return 0;
}
if (dump_file && (dump_flags & TDF_DETAILS))
dump_rdg (dump_file, rdg);
- partitions.create (3);
+ auto_vec<partition_t, 3> partitions;
rdg_build_partitions (rdg, stmts, &partitions);
any_builtin = false;
FOR_EACH_VEC_ELT (partitions, i, partition)
partition_free (partition);
- partitions.release ();
free_rdg (rdg);
- loop_nest.release ();
return nbp - *nb_calls;
}
/* Distribute all loops in the current function. */
-static unsigned int
-tree_loop_distribution (void)
+namespace {
+
+const pass_data pass_data_loop_distribution =
+{
+ GIMPLE_PASS, /* type */
+ "ldist", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_loop_distribution : public gimple_opt_pass
+{
+public:
+ pass_loop_distribution (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_loop_distribution, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *)
+ {
+ return flag_tree_loop_distribution
+ || flag_tree_loop_distribute_patterns;
+ }
+
+ virtual unsigned int execute (function *);
+
+}; // class pass_loop_distribution
+
+unsigned int
+pass_loop_distribution::execute (function *fun)
{
struct loop *loop;
- loop_iterator li;
bool changed = false;
basic_block bb;
control_dependences *cd = NULL;
- FOR_ALL_BB (bb)
+ FOR_ALL_BB_FN (bb, fun)
{
gimple_stmt_iterator gsi;
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
/* We can at the moment only distribute non-nested loops, thus restrict
walking to innermost loops. */
- FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
+ FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
{
- vec<gimple> work_list = vNULL;
+ auto_vec<gimple> work_list;
basic_block *bbs;
int num = loop->num;
unsigned int i;
bbs = get_loop_body_in_dom_order (loop);
for (i = 0; i < loop->num_nodes; ++i)
{
- gimple_stmt_iterator gsi;
- for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gphi_iterator gsi = gsi_start_phis (bbs[i]);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
if (virtual_operand_p (gimple_phi_result (phi)))
continue;
/* Distribute stmts which have defs that are used outside of
- the loop. */
+ the loop. */
if (!stmt_has_scalar_dependences_outside_loop (loop, phi))
continue;
work_list.safe_push (phi);
}
- for (gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
/* If there is a stmt with side-effects bail out - we
- cannot and should not distribute this loop. */
+ cannot and should not distribute this loop. */
if (gimple_has_side_effects (stmt))
{
work_list.truncate (0);
}
/* Distribute stmts which have defs that are used outside of
- the loop. */
+ 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)))
+ else if (!gimple_vdef (stmt))
continue;
work_list.safe_push (stmt);
}
else if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Loop %d is the same.\n", num);
-
- work_list.release ();
}
if (cd)
if (changed)
{
- mark_virtual_operands_for_renaming (cfun);
+ /* Cached scalar evolutions now may refer to wrong or non-existing
+ loops. */
+ scev_reset_htab ();
+ mark_virtual_operands_for_renaming (fun);
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
}
return 0;
}
-static bool
-gate_tree_loop_distribution (void)
-{
- return flag_tree_loop_distribution
- || flag_tree_loop_distribute_patterns;
-}
-
-namespace {
-
-const pass_data pass_data_loop_distribution =
-{
- GIMPLE_PASS, /* type */
- "ldist", /* name */
- OPTGROUP_LOOP, /* optinfo_flags */
- true, /* has_gate */
- true, /* has_execute */
- TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
- ( PROP_cfg | PROP_ssa ), /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_ssa, /* todo_flags_finish */
-};
-
-class pass_loop_distribution : public gimple_opt_pass
-{
-public:
- pass_loop_distribution (gcc::context *ctxt)
- : gimple_opt_pass (pass_data_loop_distribution, ctxt)
- {}
-
- /* opt_pass methods: */
- bool gate () { return gate_tree_loop_distribution (); }
- unsigned int execute () { return tree_loop_distribution (); }
-
-}; // class pass_loop_distribution
-
} // anon namespace
gimple_opt_pass *
projects / gcc.git / blobdiff