diff options
| -rw-r--r-- | gcc/Makefile.in | 1 | ||||
| -rw-r--r-- | gcc/common.opt | 5 | ||||
| -rw-r--r-- | gcc/passes.def | 1 | ||||
| -rw-r--r-- | gcc/timevar.def | 1 | ||||
| -rw-r--r-- | gcc/tree-pass.h | 1 | ||||
| -rw-r--r-- | gcc/uninline-innermost-loops.c | 624 |
6 files changed, 633 insertions, 0 deletions
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 42adaef66213..0a2721ef938e 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1587,6 +1587,7 @@ OBJS = \ tree-vrp.o \ tree.o \ typed-splay-tree.o \ + uninline-innermost-loops.o \ unique-ptr-tests.o \ uncse.o \ valtrack.o \ diff --git a/gcc/common.opt b/gcc/common.opt index c6d92b503c47..f230412db1fa 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2719,6 +2719,11 @@ fvectorize-more Common Report Var(flag_vectorize_more) Optimization Vectorize a bit more. +fnoloopalias= +Common Report Joined Var(noloopalias) Init(0) +Restrict pointer aliasing for given function's loops +(allows more aggressive optimisations). + funwind-tables Common Report Var(flag_unwind_tables) Optimization Just generate unwind tables for exception handling. diff --git a/gcc/passes.def b/gcc/passes.def index fe81b405f140..1258c442e4e3 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -45,6 +45,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_sprintf_length, false); NEXT_PASS (pass_walloca, /*strict_mode_p=*/true); NEXT_PASS (pass_build_cgraph_edges); + NEXT_PASS (pass_uninline_innermost_loops); TERMINATE_PASS_LIST (all_lowering_passes) /* Interprocedural optimization passes. */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 1e56e5014870..8e1091670863 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -193,6 +193,7 @@ DEFTIMEVAR (TV_LOOP_JAM , "unroll and jam") DEFTIMEVAR (TV_COMPLETE_UNROLL , "complete unrolling") DEFTIMEVAR (TV_TREE_PARALLELIZE_LOOPS, "tree parallelize loops") DEFTIMEVAR (TV_TREE_VECTORIZATION , "tree vectorization") +DEFTIMEVAR (TV_UNINLINE_INNERMOST_LOOPS, "uninline innermost loops") DEFTIMEVAR (TV_TREE_SLP_VECTORIZATION, "tree slp vectorization") DEFTIMEVAR (TV_GRAPHITE , "Graphite") DEFTIMEVAR (TV_GRAPHITE_TRANSFORMS , "Graphite loop transforms") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index abf6c4cfe3c3..aab90403ddba 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -382,6 +382,7 @@ extern gimple_opt_pass *make_pass_if_conversion (gcc::context *ctxt); extern gimple_opt_pass *make_pass_loop_distribution (gcc::context *ctxt); extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt); extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_uninline_innermost_loops (gcc::context *ctxt); extern gimple_opt_pass *make_pass_slp_vectorize (gcc::context *ctxt); extern gimple_opt_pass *make_pass_complete_unroll (gcc::context *ctxt); extern gimple_opt_pass *make_pass_complete_unrolli (gcc::context *ctxt); diff --git a/gcc/uninline-innermost-loops.c b/gcc/uninline-innermost-loops.c new file mode 100644 index 000000000000..d81a3307c8a4 --- /dev/null +++ b/gcc/uninline-innermost-loops.c @@ -0,0 +1,624 @@ +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "hash-set.h" +#include "machmode.h" +#include "vec.h" +#include "double-int.h" +#include "input.h" +#include "alias.h" +#include "symtab.h" +#include "options.h" +#include "wide-int.h" +#include "inchash.h" +#include "tree.h" +#include "fold-const.h" +#include "hashtab.h" +#include "tm.h" +#include "hard-reg-set.h" +#include "function.h" +#include "rtl.h" +#include "flags.h" +#include "statistics.h" +#include "real.h" +#include "fixed-value.h" +#include "insn-config.h" +#include "expmed.h" +#include "predict.h" +#include "dojump.h" +#include "explow.h" +#include "calls.h" +#include "varasm.h" +#include "stmt.h" +#include "expr.h" +#include "gimple-pretty-print.h" +#include "predict.h" +#include "dominance.h" +#include "cfg.h" +#include "cfgloop.h" +#include "cfghooks.h" +#include "basic-block.h" +#include "tree-ssa-alias.h" +#include "internal-fn.h" +#include "gimple-expr.h" +#include "is-a.h" +#include "gimple.h" +#include "gimplify.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "gimplify-me.h" +#include "gimple-ssa.h" +#include "tree-ssa-operands.h" +#include "tree-phinodes.h" +#include "ssa-iterators.h" +#include "dumpfile.h" +#include "tree-pass.h" +#include "ipa-ref.h" +#include "plugin-api.h" +#include "cgraph.h" +#include "function.h" +#include "tree-ssa.h" +#include "tree-into-ssa.h" + +typedef vec<tree> expr_vec; + +const char *uninlined_function_postfix = "innermost_loop"; + +/* Given stmt is an assign statement and given op is its LHS. */ + +static bool +is_defined_in_stmt (const gimple *stmt, const tree op) +{ + tree lhs; + if (gimple_code (stmt) == GIMPLE_ASSIGN) + { + lhs = gimple_assign_lhs (stmt); + if (lhs == op) + return true; + } + return false; +} + +/* Check if op is LHS of assignment within current bb. */ + +static bool +is_defined_inside (gimple *stmt, const tree op) +{ + gimple_stmt_iterator gsi; + + /* Get a gsi for the bb stmt belongs to (pointing to stmt). */ + gsi = gsi_for_stmt (stmt); + + /* Start search in previous stmt. */ + gsi_prev (&gsi); + + /* Iterate over all previous stmts in bb. */ + for (; !gsi_end_p (gsi); gsi_prev (&gsi)) + { + if (is_defined_in_stmt (gsi_stmt (gsi), op)) + return true; + } + return false; +} + +typedef void (*op_callback) (void *g, tree op, gimple *stmt, unsigned index); + +/* Call cb with arg g for each operand of each statement of each bb of the loop. */ + +static void +for_each_operand_in_loop (const struct loop *loop, op_callback cb, void *g) +{ + basic_block *bbs; + unsigned num_nodes; + unsigned i; + + /* Get the basic blocks. */ + bbs = get_loop_body (loop); + num_nodes = loop->num_nodes; + + /* Iterate over basic blocks. */ + for (i = 0; i < num_nodes; i++) + { + basic_block bb; + bb = bbs[i]; + + /* Iterate over statements in bb. */ + gimple_stmt_iterator iter = gsi_start_bb (bb); + for ( ; !gsi_end_p (iter); gsi_next (&iter)) + { + gimple *stmt; + unsigned j; + stmt = gsi_stmt (iter); + + /* Iterate over operands in bb. */ + for (j = 0; j < gimple_num_ops (stmt); j++) + { + tree op; + op = gimple_op (stmt, j); + if (op) + { + /* Here is the callback. */ + cb (g, op, stmt, j); + } + } + } + } + + /* Free the bb list. */ + free (bbs); +} + +/* Add operand to vector if: + - it is not LHS of assignment, and + - op is VAR_DECL or PARM_DECL, and + - op is not yet in v, and + - op is not defined inside of stmt's bb. */ + +static void +collect_cb (void *g, tree op, gimple *stmt, unsigned index) +{ + expr_vec *v = (expr_vec *) g; + enum tree_code code; + + if (dump_file) + fprintf (dump_file, "%s: Entering.\n", __func__); + + /* Filter out LHS of assignments. */ + if (gimple_code (stmt) == GIMPLE_ASSIGN && index == 0) + { + if (dump_file) + fprintf (dump_file, "Filtering out LHS of assignment.\n"); + return; + } + + code = TREE_CODE (op); + + /* Filter out op, which are not VAR_DECL or PARM_DECL. */ + if (code != VAR_DECL && code != PARM_DECL) + { + if (dump_file) + fprintf (dump_file, "Filtering out op, which is not (VAR_DECL or PARM_DECL).\n"); + return; + } + + /* Filter out if op already included. */ + if (v->contains (op)) + { + if (dump_file) + fprintf (dump_file, "Filtering out op, which is arleady included.\n"); + return; + } + + /* Filter out ops, which are defined inside bb. */ + if (is_defined_inside (stmt, op)) + { + if (dump_file) + fprintf (dump_file, "Filtering out op, which is defined inside bb.\n"); + return; + } + + if (dump_file) + { + fprintf (dump_file, "Calling safe_push() for op "); + const char *name = "<unknown name>"; + if (DECL_NAME(op) && IDENTIFIER_POINTER (DECL_NAME (op))) + name = identifier_to_locale (IDENTIFIER_POINTER (DECL_NAME (op))); + fprintf (dump_file, "'%s'\n", name); + } + + v->safe_push(op); +} + +/* Return unique list of operands in the given loop, + which are defined outside of the loop. */ + +static expr_vec +collect_def_outside (struct loop *loop) +{ + expr_vec v = vNULL; + + if (dump_file) + fprintf (dump_file, "%s: Entering.\n", __func__); + + for_each_operand_in_loop (loop, collect_cb, (void *) &v); + return v; +} + +/* Set boolean to true if: + - stmt is GIMPLE_CALL. */ + +static void +contains_call_cb (void *r, tree, gimple *stmt, unsigned) +{ + bool *ret = (bool *) r; + if (gimple_code (stmt) == GIMPLE_CALL) + *ret = true; +} + +/* Return true if loop contains a call statement with operands. */ + +static bool +contains_call (struct loop *loop) +{ + bool ret = false; + for_each_operand_in_loop (loop, contains_call_cb, (void *) &ret); + return ret; +} + +struct var_to_parm_cb_p +{ + tree d; + tree d_parm; +}; + +/* Replace op in stmt by p->d_parm if op == p->d. */ + +static void +var_to_parm_cb (void *g, tree op, gimple *stmt, unsigned index) +{ + struct var_to_parm_cb_p *p = (struct var_to_parm_cb_p *) g; + + if (p->d == op) + { + gimple_set_op (stmt, index, p->d_parm); + } +} + +/* Replace ops in all stmts of loop by p->d_parm if op == p->d. */ + +static void +convert_var_to_parm_uses (struct loop *loop, tree d, tree d_parm) +{ + struct var_to_parm_cb_p c; + c.d = d; + c.d_parm = d_parm; + for_each_operand_in_loop (loop, var_to_parm_cb, (void *) &c); +} + +/* Create a function declaration with void return type. */ + +static tree +build_void_function_declaration (struct loop *loop, tree name, expr_vec parameter_vector, vec<tree> *args) +{ + /* We use NULL_TREE as placeholder here. + This will be fixed later on. */ + tree type = NULL_TREE; + + /* Create the function declaration. */ + tree decl = build_decl (input_location, FUNCTION_DECL, name, type); + + TREE_STATIC (decl) = 1; + TREE_USED (decl) = 1; + DECL_ARTIFICIAL (decl) = 1; + DECL_NAMELESS (decl) = 0; + DECL_IGNORED_P (decl) = 0; + TREE_PUBLIC (decl) = 0; + DECL_UNINLINABLE (decl) = 1; + DECL_EXTERNAL (decl) = 0; + DECL_CONTEXT (decl) = NULL_TREE; + DECL_INITIAL (decl) = make_node (BLOCK); + BLOCK_SUPERCONTEXT (DECL_INITIAL (decl)) = decl; + DECL_ATTRIBUTES (decl) = DECL_ATTRIBUTES (cfun->decl); + + /* Create result declaration. */ + tree t = build_decl (DECL_SOURCE_LOCATION (decl), + RESULT_DECL, NULL_TREE, void_type_node); + + DECL_ARTIFICIAL (t) = 1; + DECL_IGNORED_P (t) = 1; + DECL_CONTEXT (t) = decl; + DECL_RESULT (decl) = t; + + /* Now we prepare several collections from the parameter vector. */ + + tree t_first = NULL; /* First element of decl chain. */ + tree t_last = NULL; /* Last element of decl chain. */ + tree types = NULL_TREE; /* TREE_LIST of types. */ + tree *pp = &types; /* Helper to create the TREE_LIST. */ + + /* Prepare the arguments collected earlier on. */ + int i = -1; + tree d = NULL; + FOR_EACH_VEC_ELT (parameter_vector, i, d) + { + /* Append parameter to args vector. */ + args->safe_push (d); + + /* Get parameter type. */ + tree type_new = copy_node (TREE_TYPE (d)); + + /* Append type to tree list. */ + *pp = build_tree_list (NULL, type_new); + pp = &TREE_CHAIN (*pp); + + /* Allocate and initialize parameter declaration. */ + tree d_parm = build_decl (DECL_SOURCE_LOCATION (decl), PARM_DECL, + DECL_NAME (d), type_new); + DECL_ARG_TYPE (d_parm) = TREE_TYPE (d); + DECL_ARTIFICIAL (d_parm) = 1; + DECL_CONTEXT (d_parm) = decl; + if (POINTER_TYPE_P (TREE_TYPE (d))) + TYPE_RESTRICT (TREE_TYPE (d_parm)) = 1; + + if (dump_file) + { + const char *name = "<unknown name>"; + tree t TREE_TYPE (d); + int isptr = 0; + if (DECL_NAME(d) && IDENTIFIER_POINTER (DECL_NAME (d))) + { + name = identifier_to_locale (IDENTIFIER_POINTER (DECL_NAME (d))); + isptr = POINTER_TYPE_P (t); + } + fprintf (dump_file, "Parameter %s isptr=%i\n", name, isptr); + } + + /* Convert the loop to use the parameters. */ + convert_var_to_parm_uses (loop, d, d_parm); + + if (!t_first) + { + t_first = d_parm; + t_last = d_parm; + } + else + { + DECL_CHAIN (t_last) = d_parm; + t_last = d_parm; + } + } + + /* Replace the placeholder type by the actual type (void f(args...)). */ + type = build_function_type (void_type_node, types); + TREE_TYPE (decl) = type; + DECL_ARGUMENTS (decl) = t_first; + + /* Allocate memory for the function structure. The call to + allocate_struct_function clobbers CFUN, so we need to restore + it afterward. */ + push_struct_function (decl); + cfun->function_end_locus = DECL_SOURCE_LOCATION (decl); + init_tree_ssa (cfun); + pop_cfun (); + + return decl; +} + +/* Converts the loop body into its own function + * with the given arguments. + * + * This is inspired by create_omp_child_function and create_loop_fn. */ + +static void +body_to_fun (struct loop *loop, expr_vec parameter_vector) +{ + /* Build function declaration. */ + tree name = clone_function_name (cfun->decl, uninlined_function_postfix); + vec<tree> args = vNULL; /* Vector of parameters. */ + tree decl = build_void_function_declaration (loop, name, parameter_vector, &args); + + /* Fill the function body. */ + gimple_seq body = NULL; + gimple *bind = gimple_build_bind (NULL, body, DECL_INITIAL (decl)); + gimple_seq_add_stmt (&body, bind); + + /* We'll create a CFG for child_fn, so no gimple body is needed. */ + gimple_set_body (decl, body); + + struct function *child_cfun = DECL_STRUCT_FUNCTION (decl); + + /* We need a SESE (single entry - single exit) region to ease the outlining. */ + + basic_block in_bb = create_preheader (loop, CP_FORCE_PREHEADERS); + + if (dump_file) + { + fprintf (dump_file, "%s: in_bb: %i\n", __func__, in_bb->index); + fprintf (dump_file, "%s: loop->header: %i\n", __func__, loop->header->index); + fprintf (dump_file, "%s: loop->latch: %i\n", __func__, loop->latch->index); + } + + edge out = single_exit (loop); + if (!out) + { + if (dump_file) + fprintf (dump_file, "Loop does not have a single exit!\n"); + } + + gcc_assert (out != NULL); + + if (dump_file) + { + fprintf (dump_file, "%s: Exit edge src: %i.\n", __func__, out->src->index); + fprintf (dump_file, "%s: Exit edge dest: %i.\n", __func__, out->dest->index); + } + + basic_block out_bb = split_edge (out); + + if (dump_file) + { + fprintf (dump_file, "%s: out_bb: %i\n", __func__, out_bb->index); + } + + /* Move the single-entry-single-exit region into its own function. + We get the new BB in the original function (which returns + the "factored-out" region. */ + basic_block new_bb = move_sese_region_to_fn (child_cfun, in_bb, + out_bb, NULL_TREE); + + if (dump_file) + { + fprintf (dump_file, "%s: new_bb: %i\n", __func__, new_bb->index); + fprintf (dump_file, "new_bb has %u edges: ", EDGE_COUNT(new_bb->preds)); + edge p; + edge_iterator ei; + FOR_EACH_EDGE (p, ei, new_bb->preds) + { + basic_block runner = p->src; + fprintf (dump_file, "bb%i, ", runner->index); + } + fprintf(dump_file, "-\n"); + } + + /* Add call statement into new bb */ + gimple *call_stmt = gimple_build_call_vec (decl, args); + gimple_stmt_iterator call_iter = gsi_start_bb (new_bb); + gsi_insert_after (&call_iter, call_stmt, GSI_NEW_STMT); + + /* Add return statement into new exit bb. */ + gimple *stmt = gimple_build_return (NULL); + gimple_stmt_iterator gsi = gsi_last_bb(out_bb); + gsi_insert_after (&gsi, stmt, GSI_NEW_STMT); + + /* Copy function properties */ + child_cfun->curr_properties = cfun->curr_properties; + + /* Create the new function call graph node */ + cgraph_node::get_create (decl); + /* Make the new function known. */ + cgraph_node::add_new_function (decl, true); + + /* Edge fixup */ + update_max_bb_count (); + cgraph_edge::rebuild_edges (); + + if (gimple_in_ssa_p (cfun)) + { + if (dump_file) + fprintf (dump_file, "gimple_in_ssa_p(cfun) is true\n"); + update_ssa (TODO_update_ssa); + } + else + { + if (dump_file) + fprintf (dump_file, "gimple_in_ssa_p(cfun) is false\n"); + } + + + push_cfun (child_cfun); + update_max_bb_count (); + cgraph_edge::rebuild_edges (); + + if (gimple_in_ssa_p (cfun)) + { + if (dump_file) + fprintf (dump_file, "gimple_in_ssa_p(child) is true\n"); + update_ssa (TODO_update_ssa); + } + else + { + if (dump_file) + fprintf (dump_file, "gimple_in_ssa_p(child) is false\n"); + } + + pop_cfun (); +} + +static unsigned int +extract_loop_to_function () +{ + struct loop *loop; + struct loop *lu; + expr_vec v = vNULL; + unsigned n; + + lu = NULL; + + /* First create the list of loop exits of cfun + (searches all edges of all bb in cfun). */ + record_loop_exits (); + + n = 0; + FOR_EACH_LOOP_FN (cfun, loop, LI_ONLY_INNERMOST) + { + /* We need single-entry single-exit loops. */ + if (!single_exit (loop)) + continue; + if (EDGE_COUNT(loop->header->preds) > 2) + continue; + + /* We can't deal with calls inside of loops. */ + if (contains_call (loop)) + continue; + + if (n < loop->num_nodes) + { + n = loop->num_nodes; + lu = loop; + } + } + + if (lu) + { + const char *fun_to_uninline = noloopalias; + if (dump_file) + fprintf (dump_file, + "%s:%d (%s): uninlining in %s\n", + __FILE__, __LINE__, __func__, fun_to_uninline); + + /* First we get a unique list of operands in the loop, + which are defined outside of the loop. */ + v = collect_def_outside (lu); + + /* Now we create a new function with the given list of arguments. */ + body_to_fun (lu, v); + } + + /* Free the list of loop exits of cfun. */ + release_recorded_exits (cfun); + + return 0; +} + +namespace { + +const pass_data pass_data_uninline_innermost_loops = +{ + GIMPLE_PASS, /* type */ + "uninline-innermost-loops", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_UNINLINE_INNERMOST_LOOPS, /* tv_id */ + PROP_gimple_any, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_uninline_innermost_loops: public gimple_opt_pass +{ +public: + pass_uninline_innermost_loops (gcc::context *ctxt) + : gimple_opt_pass (pass_data_uninline_innermost_loops, ctxt) + {} + + /* opt_pass methods: */ + virtual bool gate (function *fun) + { + const char *fun_to_uninline = noloopalias; + + if (fun_to_uninline == NULL) + return false; + + if (strcmp(fun_to_uninline, "*") == 0) + return true; + + if (fun == NULL) + return false; + + return (strcmp (function_name (fun), fun_to_uninline) == 0); + } + + virtual unsigned int execute (function *) + { + return extract_loop_to_function (); + } +}; + +} // anon namespace + +gimple_opt_pass * +make_pass_uninline_innermost_loops (gcc::context *ctxt) +{ + return new pass_uninline_innermost_loops (ctxt); +} |