diff options
-rw-r--r-- | gcc/Makefile.in | 2 | ||||
-rw-r--r-- | gcc/common.opt | 7 | ||||
-rw-r--r-- | gcc/noloopalias.c | 538 | ||||
-rw-r--r-- | gcc/passes.def | 2 | ||||
-rw-r--r-- | gcc/peel-last-iteration.c | 32 | ||||
-rw-r--r-- | gcc/timevar.def | 2 | ||||
-rw-r--r-- | gcc/tree-pass.h | 2 | ||||
-rw-r--r-- | gcc/uninline-innermost-loops.c | 456 |
8 files changed, 553 insertions, 488 deletions
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index e39125436ee1..fc4610b13f46 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1391,6 +1391,7 @@ OBJS = \ mode-switching.o \ modulo-sched.o \ multiple_target.o \ + noloopalias.o \ omp-offload.o \ omp-expand.o \ omp-general.o \ @@ -1563,7 +1564,6 @@ OBJS = \ tree-vrp.o \ tree.o \ typed-splay-tree.o \ - uninline-innermost-loops.o \ uncse.o \ valtrack.o \ value-prof.o \ diff --git a/gcc/common.opt b/gcc/common.opt index 01dc499b6716..a92591eb3e95 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2632,9 +2632,10 @@ fsplit-loops Common Report Var(flag_split_loops) Optimization Perform loop splitting. -fnoalias= -Common Joined Var(noalias) Init(0) -Move innermost loops to separate function +fnoloopalias +Common Report Var(flag_noloopalias) Optimization +Restrict pointer aliasing for function's loops +(allows more aggressive optimisations). flist-find-pipeline Common Report Var(list_find_pipe) Optimization diff --git a/gcc/noloopalias.c b/gcc/noloopalias.c new file mode 100644 index 000000000000..cf0f8159fd3c --- /dev/null +++ b/gcc/noloopalias.c @@ -0,0 +1,538 @@ +#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; + +static const char *uninlined_function_postfix = "loop"; + +/* If a callback returns a negative number, + * then we immediately bail out and return the + * return value from the callback. */ +typedef int (*stmt_callback) (gimple *stmt, void *g); +typedef int (*op_callback) (gimple *stmt, tree op, unsigned index, void *g); + + +/* Iterator helper, which can be used to iterate over all basic blocks, + * their statements and the statement's operands in a loop. + * For each statement and operator a callback will be invoked. + * If any callback invocation returns a non-null return code, + * the iteration will be stopped immediately and the non-null + * return code will be returned. */ + +static int +for_each_operand_in_loop (const struct loop *loop, stmt_callback stmt_cb, op_callback op_cb, void *g) +{ + basic_block *bbs; + unsigned num_nodes; + unsigned i; + int ret = 0; + + /* 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); + + if (stmt_cb) + { + ret = stmt_cb(stmt, g); + if (ret) + goto end; + } + + /* Iterate over operands in stmt. */ + for (j = 0; j < gimple_num_ops (stmt); j++) + { + tree op; + op = gimple_op (stmt, j); + if (op) + { + if (op_cb) + { + ret = op_cb (stmt, op, j, g); + if (ret) + goto end; + } + } + } + } + } + +end: + /* Free the bb list. */ + free (bbs); + + return ret; +} + +/* Given stmt is an assign statement and given op is its LHS. */ + +static bool +is_defined_in_stmt (const gimple *stmt, const tree op) +{ + if (gimple_code (stmt) == GIMPLE_ASSIGN) + { + tree 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) +{ + /* Get a gsi for the bb stmt belongs to (pointing to stmt). */ + gimple_stmt_iterator 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; +} + +static int +is_gimple_call (gimple *stmt, void *g) +{ + (void)g; + return (gimple_code (stmt) == GIMPLE_CALL); +} + +/* 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 int +collect_cb (gimple *stmt, tree op, unsigned index, void *g) +{ + expr_vec *v = (expr_vec *) g; + enum tree_code code; + + /* Whitelist LHS of assignments. */ + if (gimple_code (stmt) == GIMPLE_ASSIGN && index == 0) + return 0; + + code = TREE_CODE (op); + + /* Whitelist of supported codes */ + if (code == INTEGER_CST || + code == SSA_NAME || + code == MEM_REF) + return 0; + + /* Filter out op, which are not VAR_DECL or PARM_DECL. */ + if (code != VAR_DECL && code != PARM_DECL) + return -1; + + /* Filter out op without DECL_NAME. */ + if (!DECL_NAME (op)) + return -1; + + /* Filter out if op already included. */ + if (v->contains (op)) + return 0; + + /* Filter out ops, which are defined inside bb. */ + if (is_defined_inside (stmt, op)) + return 0; + + if (dump_file) + { + fprintf (dump_file, "Found new element for arguments list: "); + 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 0; +} + +/* 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; + int ret = for_each_operand_in_loop (loop, NULL, collect_cb, (void *) &v); + if (ret) + return vNULL; + + return v; +} + +/* Return non-null if loop contains a call statement with operands. */ + +static int +contains_call (struct loop *loop) +{ + return for_each_operand_in_loop (loop, is_gimple_call, NULL, NULL); +} + +struct var_to_parm_cb_p +{ + tree d; + tree d_parm; +}; + +/* Replace op in stmt by p->d_parm if op == p->d. */ + +static int +var_to_parm_cb (gimple *stmt, tree op, unsigned index, void *g) +{ + 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); + } + return 0; +} + +/* 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, NULL, 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)) && TREE_CODE (d) == VAR_DECL) + TYPE_RESTRICT (TREE_TYPE (d_parm)) = 1; + + /* 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 +outline_loop (struct loop *loop, expr_vec parameter_vector) +{ + /* Build function declaration. */ + char postfix[strlen(uninlined_function_postfix)+12]; + snprintf (postfix, sizeof (postfix), "%s%i", uninlined_function_postfix, loop->num); + tree name = clone_function_name (cfun->decl, 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); + + edge out = single_exit (loop); + + gcc_assert (out != NULL); + + basic_block out_bb = split_edge (out); + + /* 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); + + /* 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 */ + cgraph_edge::rebuild_edges (); + + push_cfun (child_cfun); + cgraph_edge::rebuild_edges (); + + pop_cfun (); +} + +static unsigned int +extract_loop_to_function () +{ + struct loop *loop; + expr_vec v = vNULL; + + /* First create the list of loop exits of cfun + (searches all edges of all bb in cfun). */ + record_loop_exits (); + + 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; + + /* Assure the loop is not the entire function. */ + if ((loop->num_nodes + 5) >= (unsigned)n_basic_blocks_for_fn (cfun)) + continue; + + /* We can't deal with calls inside of loops. */ + if (contains_call (loop)) + continue; + + /* First we get a unique list of operands in the loop, + which are defined outside of the loop. */ + v = collect_def_outside (loop); + if (v == vNULL) + continue; + + /* Ignore small loop, which don't offer optimisation potential. */ + if (v.length () < 10) + continue; + + if (dump_file) + fprintf (dump_file, "Outlining loop %d\n", loop->num); + + /* Now we create a new function with the given list of arguments. */ + outline_loop (loop, v); + } + + /* Free the list of loop exits of cfun. */ + release_recorded_exits (cfun); + + return 0; +} + +namespace { + +const pass_data pass_data_noloopalias = +{ + GIMPLE_PASS, /* type */ + "noloopalias", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_NOLOOPALIAS, /* tv_id */ + PROP_gimple_any, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_noloopalias: public gimple_opt_pass +{ +public: + pass_noloopalias (gcc::context *ctxt) + : gimple_opt_pass (pass_data_noloopalias, ctxt) + {} + + /* opt_pass methods: */ + virtual bool gate (function *) + { + return flag_noloopalias; + } + + virtual unsigned int execute (function *) + { + return extract_loop_to_function (); + } +}; + +} // anon namespace + +gimple_opt_pass * +make_pass_noloopalias (gcc::context *ctxt) +{ + return new pass_noloopalias (ctxt); +} diff --git a/gcc/passes.def b/gcc/passes.def index 9637edb57e20..6ebf8bbb8b49 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -45,7 +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); + NEXT_PASS (pass_noloopalias); TERMINATE_PASS_LIST (all_lowering_passes) /* Interprocedural optimization passes. */ diff --git a/gcc/peel-last-iteration.c b/gcc/peel-last-iteration.c index 7d6333a7e079..d18c01f1a3df 100644 --- a/gcc/peel-last-iteration.c +++ b/gcc/peel-last-iteration.c @@ -53,6 +53,8 @@ #include "dumpfile.h" #include "tree-pass.h" +static const char *uninlined_function_postfix = "loop"; + gcond * get_loop_exit_condition (const struct loop *loop); @@ -112,28 +114,13 @@ peel_in_fn (void) unsigned j; unsigned num_nodes; - const char * fun_to_uninline; - int fun_to_uninline_len; - - int uninlined_function_postfix_len; - gimple *return_stmt; - char fun_to_peel[256]; - int k; entry_edge = NULL; copied_def_stmt = NULL; - fun_to_uninline = noalias; - fun_to_uninline_len = strlen (fun_to_uninline); - uninlined_function_postfix_len = strlen (uninlined_function_postfix); - - /* FIXME Make this more safe. */ - snprintf(fun_to_peel, sizeof fun_to_peel, "%s.%s", fun_to_uninline, - uninlined_function_postfix); - loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES | LOOPS_HAVE_PREHEADERS); record_loop_exits (); @@ -142,14 +129,6 @@ peel_in_fn (void) FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) { k++; - if (strncmp (function_name (cfun), fun_to_peel, fun_to_uninline_len + 1 + uninlined_function_postfix_len) != 0) - { - if (dump_file) - fprintf (dump_file, "%s:%d (%s): wrong function %s\n", - __FILE__, __LINE__, __func__, - function_name (cfun)); - continue; - } if (k != 0) { if (dump_file) @@ -401,8 +380,11 @@ peel_in_fn (void) static bool gate_peel_last_iteration (void) { - /* Run this only as a post processing step for the uninlining pass. */ - return noalias != 0; + const char* cfun_name = function_name (cfun); + char needle[strlen (uninlined_function_postfix) + 2]; + snprintf (needle, sizeof (needle), ".%s", uninlined_function_postfix); + const char* result = strstr (cfun_name, needle); + return result != NULL; } namespace { diff --git a/gcc/timevar.def b/gcc/timevar.def index cf2d436e0639..1fdba72a8dda 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -143,6 +143,7 @@ DEFTIMEVAR (TV_FLATTEN_INLINING , "flatten inlining") DEFTIMEVAR (TV_EARLY_INLINING , "early inlining heuristics") DEFTIMEVAR (TV_INLINE_PARAMETERS , "inline parameters") DEFTIMEVAR (TV_INTEGRATION , "integration") +DEFTIMEVAR (TV_NOLOOPALIAS , "noloopalias") DEFTIMEVAR (TV_TREE_GIMPLIFY , "tree gimplify") DEFTIMEVAR (TV_TREE_EH , "tree eh") DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction") @@ -189,7 +190,6 @@ DEFTIMEVAR (TV_LOOP_SPLIT , "loop splitting") 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_PEEL_LAST_ITERATION, "peel last iteration") DEFTIMEVAR (TV_GRAPHITE , "Graphite") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index ade32c09617e..435286dbfba3 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -354,6 +354,7 @@ extern gimple_opt_pass *make_pass_refactor_eh (gcc::context *ctxt); extern gimple_opt_pass *make_pass_lower_eh (gcc::context *ctxt); extern gimple_opt_pass *make_pass_lower_eh_dispatch (gcc::context *ctxt); extern gimple_opt_pass *make_pass_lower_resx (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_noloopalias (gcc::context *ctxt); extern gimple_opt_pass *make_pass_build_cfg (gcc::context *ctxt); extern gimple_opt_pass *make_pass_early_tree_profile (gcc::context *ctxt); extern gimple_opt_pass *make_pass_cleanup_eh (gcc::context *ctxt); @@ -380,7 +381,6 @@ 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 deleted file mode 100644 index 3726e6efeeec..000000000000 --- a/gcc/uninline-innermost-loops.c +++ /dev/null @@ -1,456 +0,0 @@ -#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 "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" - -void -print_generic_expr (FILE *file, tree t, int flags); - -typedef vec <tree> expr_vec; - -extern const char * uninlined_function_postfix; -const char * uninlined_function_postfix = "innermost_loop"; - -static bool -is_defined_in_stmt (gimple *stmt, tree var) -{ - tree lhs; - if (gimple_code (stmt) == GIMPLE_ASSIGN) - { - lhs = gimple_assign_lhs (stmt); - if (lhs == var) - return true; - } - return false; -} - -static bool -is_defined_in_bb (gimple_stmt_iterator gsi, tree var) -{ - for (; !gsi_end_p (gsi); gsi_prev (&gsi)) - { - if (is_defined_in_stmt (gsi_stmt (gsi), var)) - return true; - } - return false; -} - -static bool -is_defined_outside (gimple *use, tree var) -{ - gimple_stmt_iterator gsi; - gsi = gsi_for_stmt (use); - gsi_prev (&gsi); - /* FIXME Recursively search other also predecessor bbs. */ - return !is_defined_in_bb (gsi, var); -} - -/* FIXME Is there a standard function to do this? */ -static bool -contained (expr_vec v, tree var) -{ - int i = 0; - tree u; - - FOR_EACH_VEC_ELT (v, i, u) - { - if (u == var) - return true; - } - return false; -} - -typedef void (*op_callback) (void * g, tree op, gimple *stmt, unsigned index); - -static void -for_each_operand_in_loop (struct loop * loop, op_callback cb, void * g) -{ - basic_block * bbs; - basic_block bb; - unsigned num_nodes; - unsigned i; - unsigned j; - gimple *stmt; - tree op; - - bbs = get_loop_body (loop); - num_nodes = loop->num_nodes; - for (i = 0; i < num_nodes; i++) - { - bb = bbs[i]; - gimple_stmt_iterator iter = gsi_start_bb (bb); - while (!gsi_end_p (iter)) - { - stmt = gsi_stmt (iter); - for (j = 0; j < gimple_num_ops (stmt); j++) - { - op = gimple_op (stmt, j); - if (op) - { - /* Here is the callback. */ - cb (g, op, stmt, j); - } - } - gsi_next (&iter); - } - } - free (bbs); -} - -static void -collect_cb (void * g, tree op, gimple *stmt, unsigned index) -{ - expr_vec * v = (expr_vec *) g; - enum tree_code code; - - if (gimple_code (stmt) == GIMPLE_ASSIGN && index == 0) - { - /* I assume operand 0 of an assignment is the lhs. */ - return; - } - - code = TREE_CODE (op); - if ((code == VAR_DECL || code == PARM_DECL) && - ! contained (*v, op) && - is_defined_outside (stmt, op)) - { - v->safe_push (op); - } -} - -static expr_vec -collect_def_outside (struct loop * loop) -{ - expr_vec v = vNULL; - for_each_operand_in_loop (loop, collect_cb, (void *) & v); - return v; -} - -static void -contains_call_cb (void * r, tree, gimple *stmt, unsigned) -{ - bool * ret = (bool *) r; - if (gimple_code (stmt) == GIMPLE_CALL) - *ret |= true; - else - *ret |= false; -} - -static bool -contains_call (struct loop * loop) -{ - bool ret; - ret = false; - for_each_operand_in_loop (loop, contains_call_cb, &ret); - return ret; -} - -struct var_to_parm_cb_p -{ - tree d; - tree d_parm; -}; - -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); - } -} - -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); -} - -static void -body_to_fun (struct loop * loop, expr_vec uv) -{ - tree name, decl, type, t, block; - gimple_seq body = NULL; - gimple *bind; - int i; - vec<tree> args; - struct function *fun; - basic_block new_bb, preheader; - edge out; - basic_block in_bb, out_bb; - - /* Make the new function similar to create_omp_child_function. */ - name = clone_function_name (cfun->decl, uninlined_function_postfix); - decl = build_decl (input_location, FUNCTION_DECL, name, NULL_TREE); - - 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; - - block = make_node (BLOCK); - DECL_INITIAL (decl) = block; - - 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; - - tree d_parm = NULL; - tree d = NULL; - tree t_first = NULL; - t = NULL; - - tree type_new = NULL; - - tree types = NULL_TREE; - tree *pp = &types; - - args = vNULL; - - /* Prepare the arguments collected earlier on. */ - i = 0; - FOR_EACH_VEC_ELT (uv, i, d) - { - args.safe_push (d); - - type_new = copy_node (TREE_TYPE (d)); - - *pp = build_tree_list (NULL, type_new); - pp = &TREE_CHAIN (*pp); - - 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; - TYPE_RESTRICT (TREE_TYPE (d_parm)) = 1; - convert_var_to_parm_uses (loop, d, d_parm); - - if (!t_first) - { - t = d_parm; - t_first = d_parm; - } - else - { - DECL_CHAIN (t) = d_parm; - t = d_parm; - } - } - - type = build_function_type (void_type_node, types); - - DECL_ARGUMENTS (decl) = t_first; - TREE_TYPE (decl) = type; - - push_struct_function (decl); - cfun->function_end_locus = DECL_SOURCE_LOCATION (decl); - pop_cfun (); - - /* Fill the function body. */ - bind = gimple_build_bind (NULL, body, block); - gimple_seq_add_stmt (&body, bind); - - gimple_set_body (decl, body); - - fun = DECL_STRUCT_FUNCTION (decl); - - init_tree_ssa (fun); - - out = single_exit (loop); - - out_bb = split_edge (out); - - /* FIXME I patched this function such that - it always creates the - preheader. - */ - preheader = create_preheader (loop, 128); - in_bb = preheader; - - new_bb = move_sese_region_to_fn (fun, in_bb, - out_bb, NULL_TREE); - - DECL_STRUCT_FUNCTION (decl)->curr_properties = cfun->curr_properties; - - /* Make the new function known. */ - cgraph_node::add_new_function (decl, true); - - gimple_stmt_iterator call_iter = gsi_start_bb (new_bb); - gimple *call_stmt; - call_stmt = gimple_build_call_vec (decl, args); - gsi_insert_after (&call_iter, call_stmt, - GSI_NEW_STMT); - - cgraph_edge::rebuild_edges (); - - push_cfun (fun); - cgraph_edge::rebuild_edges (); - pop_cfun (); -} - -static unsigned int -extract_loop_to_function (void) -{ - struct loop *loop; - struct loop *lu; - expr_vec v = vNULL; - bool cc; - - const char * fun_to_uninline; - unsigned n; - - lu = NULL; - - record_loop_exits (); - - fun_to_uninline = noalias; - - n = 0; - FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST) - { - /* FIXME Try to generalize this. */ - /* We assume that we outline at most one - innermost loop. - We choose the biggest loop, assuming - it will bring the most benefit. - FIXME Make sure there flows no data out of - the loop. - */ - if (single_exit (loop) && - strcmp (function_name (cfun), fun_to_uninline) == 0) - { - cc = contains_call (loop); - if (!cc && n < loop->num_nodes) - { - n = loop->num_nodes; - lu = loop; - } - } - } - - if (lu) - { - if (dump_file) - fprintf (dump_file, - "%s:%d (%s): uninlining in %s\n", - __FILE__, __LINE__, __func__, fun_to_uninline); - v = collect_def_outside (lu); - body_to_fun (lu, v); - } - - release_recorded_exits (cfun); - - return 0; -} - -static bool -gate_uninline_innermost_loops (void) -{ - return noalias != 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: */ - bool gate (function *) { return gate_uninline_innermost_loops (); } - 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); -} |