X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=46665db9293cc11d85533272d132a0a58210a6fe;hb=1c89dc2a2c3cccd6e29fcfbf65248496db66ab92;hp=2635ced1131f8618b3cc912d28013bf56407ef9b;hpb=9d4e23060441530a20af5d331268435bfe18f305;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index 2635ced11..46665db92 100644 --- a/ir/opt/loop.c +++ b/ir/opt/loop.c @@ -26,6 +26,8 @@ */ #include "config.h" +#include + #include "iroptimize.h" #include "opt_init.h" #include "irnode.h" @@ -43,20 +45,14 @@ #include "beutil.h" #include "irpass.h" #include "irdom.h" +#include "opt_manage.h" #include #include "irbackedge_t.h" -#include "irphase_t.h" +#include "irnodemap.h" #include "irloop_t.h" - -DEBUG_ONLY(static firm_dbg_module_t *dbg); - -/* DBG print stats for every procedure. */ -#define LOOP_OPT_STATS 1 - -/* DBG: Ignore node limits and process every possible loop. */ -#define LOOP_IGNORE_NODE_LIMITS 0 +DEBUG_ONLY(static firm_dbg_module_t *dbg;) /** * Convenience macro for iterating over every phi node of the given block. @@ -79,7 +75,7 @@ typedef enum { } unrolling_kind_flag; /* Condition for performing visiting a node during copy_walk. */ -typedef unsigned walker_condition(ir_node *); +typedef bool walker_condition(const ir_node *); /* Node and position of a predecessor. */ typedef struct entry_edge { @@ -97,18 +93,12 @@ typedef struct unrolling_node_info { static entry_edge *cur_head_outs; /* Information about the loop head */ -static ir_node *loop_head = NULL; -static unsigned loop_head_valid = 1; +static ir_node *loop_head = NULL; +static bool loop_head_valid = true; /* List of all inner loops, that are processed. */ static ir_loop **loops; -#if LOOP_OPT_STATS - -#define count_stats(val) (++val) -#define print_stats() (do_print_stats()) -#define reset_stats() (do_reset_stats()) - /* Stats */ typedef struct loop_stats_t { unsigned loops; @@ -128,13 +118,13 @@ typedef struct loop_stats_t { static loop_stats_t stats; /* Set stats to sero */ -static void do_reset_stats(void) +static void reset_stats(void) { memset(&stats, 0, sizeof(loop_stats_t)); } /* Print stats */ -static void do_print_stats(void) +static void print_stats(void) { DB((dbg, LEVEL_2, "---------------------------------------\n")); DB((dbg, LEVEL_2, "loops : %d\n",stats.loops)); @@ -148,28 +138,21 @@ static void do_print_stats(void) DB((dbg, LEVEL_2, "invariant_unroll : %d\n",stats.invariant_unroll)); DB((dbg, LEVEL_2, "=======================================\n")); } -#else -/* No stats */ -#define count_stats(val) ((void)0) -#define print_stats() ((void)0) -#define reset_stats() ((void)0) - -#endif /* Commandline parameters */ typedef struct loop_opt_params_t { unsigned max_loop_size; /* Maximum number of nodes [nodes]*/ int depth_adaption; /* Loop nest depth adaption [percent] */ unsigned allowed_calls; /* Number of calls allowed [number] */ -unsigned count_phi:1; /* Count phi nodes */ -unsigned count_proj:1; /* Count projections */ +bool count_phi; /* Count phi nodes */ +bool count_proj; /* Count projections */ unsigned max_cc_size; /* Maximum condition chain size [nodes] */ unsigned max_branches; unsigned max_unrolled_loop_size; /* [nodes] */ -unsigned allow_const_unrolling:1; -unsigned allow_invar_unrolling:1; +bool allow_const_unrolling; +bool allow_invar_unrolling; unsigned invar_unrolling_min_size; /* [nodes] */ } loop_opt_params_t; @@ -228,7 +211,8 @@ static entry_edge *loop_entries; /* Number of unrolls to perform */ static int unroll_nr; /* Phase is used to keep copies of nodes. */ -static ir_phase *phase; +static ir_nodemap map; +static struct obstack obst; /* Loop operations. */ typedef enum loop_op_t { @@ -257,34 +241,47 @@ static void reset_link(ir_node *node, void *env) } /* Returns 0 if the node or block is not in cur_loop. */ -static unsigned is_in_loop(ir_node *node) +static bool is_in_loop(const ir_node *node) { - return (get_irn_loop(get_block(node)) == cur_loop); + return get_irn_loop(get_block_const(node)) == cur_loop; } /* Returns 0 if the given edge is not a backedge * with its pred in the cur_loop. */ -static unsigned is_own_backedge(ir_node *n, int pos) +static bool is_own_backedge(const ir_node *n, int pos) { - return (is_backedge(n, pos) && is_in_loop(get_irn_n(n, pos))); + return is_backedge(n, pos) && is_in_loop(get_irn_n(n, pos)); } /* Finds loop head and some loop_info as calls or else if necessary. */ static void get_loop_info(ir_node *node, void *env) { - unsigned node_in_loop, pred_in_loop; + bool node_in_loop = is_in_loop(node); int i, arity; (void)env; + /* collect some loop information */ + if (node_in_loop) { + if (is_Phi(node) && opt_params.count_phi) + ++loop_info.nodes; + else if (is_Proj(node) && opt_params.count_proj) + ++loop_info.nodes; + else if (!is_Confirm(node) && !is_Const(node) && !is_SymConst(node)) + ++loop_info.nodes; + + if (is_Load(node) || is_Store(node)) + ++loop_info.ld_st; + + if (is_Call(node)) + ++loop_info.calls; + } + arity = get_irn_arity(node); for (i = 0; i < arity; i++) { - ir_node *pred = get_irn_n(node, i); - - pred_in_loop = is_in_loop(pred); - node_in_loop = is_in_loop(node); + ir_node *pred = get_irn_n(node, i); + bool pred_in_loop = is_in_loop(pred); - if (!node_in_loop && pred_in_loop && is_Block(node)) - { + if (is_Block(node) && !node_in_loop && pred_in_loop) { entry_edge entry; entry.node = node; entry.pos = i; @@ -294,31 +291,15 @@ static void get_loop_info(ir_node *node, void *env) loop_info.cf_out = entry; } - /* collect some loop information */ - if (node_in_loop) { - if (is_Phi(node) && opt_params.count_phi) - ++loop_info.nodes; - else if (is_Proj(node) && opt_params.count_proj) - ++loop_info.nodes; - else if (!is_Confirm(node) && !is_Const(node) && !is_SymConst(node)) - ++loop_info.nodes; - - if (is_Load(node) || is_Store(node)) - ++loop_info.ld_st; - - if (is_Call(node)) - ++loop_info.calls; - - } - /* Find the loops head/the blocks with cfpred outside of the loop */ if (is_Block(node)) { const ir_edge_t *edge; unsigned outs_n = 0; /* Count innerloop branches */ - foreach_out_edge_kind(node, edge, EDGE_KIND_NORMAL) { - if (is_Block(get_edge_src_irn(edge)) && is_in_loop(get_edge_src_irn(edge))) + foreach_out_edge_kind(node, edge, EDGE_KIND_BLOCK) { + ir_node *succ = get_edge_src_irn(edge); + if (is_Block(succ) && is_in_loop(succ)) ++outs_n; } if (outs_n > 1) @@ -332,7 +313,7 @@ static void get_loop_info(ir_node *node, void *env) node, pred)); /* another head? We do not touch this. */ if (loop_head && loop_head != node) { - loop_head_valid = 0; + loop_head_valid = false; } else { loop_head = node; } @@ -378,7 +359,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int fi { int i; int n_cfgpreds; - ir_graph *irg; + ir_graph *irg = get_irn_irg(block); ir_node *phi; ir_node **in; @@ -388,7 +369,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int fi * Dead and bad blocks. */ if (get_irn_arity(block) < 1 || is_Bad(block)) { DB((dbg, LEVEL_5, "ssa bad %N\n", block)); - return new_Bad(); + return new_r_Bad(irg, mode); } if (block == ssa_second_def_block && !first) { @@ -403,7 +384,6 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int fi return value; } - irg = get_irn_irg(block); assert(block != get_irg_start_block(irg)); /* a Block with only 1 predecessor needs no Phi */ @@ -424,7 +404,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int fi /* create a new Phi */ NEW_ARR_A(ir_node*, in, n_cfgpreds); for (i = 0; i < n_cfgpreds; ++i) - in[i] = new_Unknown(mode); + in[i] = new_r_Dummy(irg, mode); phi = new_r_Phi(block, n_cfgpreds, in, mode); /* Important: always keep block phi list up to date. */ @@ -516,16 +496,14 @@ static void set_unroll_copy(ir_node *n, int nr, ir_node *cp) unrolling_node_info *info; assert(nr != 0 && "0 reserved"); - info = (unrolling_node_info *)phase_get_irn_data(phase, n); + info = (unrolling_node_info*)ir_nodemap_get(&map, n); if (! info) { - ir_node **arr; + ir_node **arr = NEW_ARR_D(ir_node*, &obst, unroll_nr); + memset(arr, 0, unroll_nr * sizeof(ir_node*)); - info = XMALLOCZ(unrolling_node_info); - arr = NEW_ARR_F(ir_node *, unroll_nr); + info = OALLOCZ(&obst, unrolling_node_info); info->copies = arr; - memset(info->copies, 0, (unroll_nr) * sizeof(ir_node *)); - - phase_set_irn_data(phase, n, info); + ir_nodemap_insert(&map, n, info); } /* Original node */ info->copies[0] = n; @@ -537,7 +515,7 @@ static void set_unroll_copy(ir_node *n, int nr, ir_node *cp) static ir_node *get_unroll_copy(ir_node *n, int nr) { ir_node *cp; - unrolling_node_info *info = (unrolling_node_info *)phase_get_irn_data(phase, n); + unrolling_node_info *info = (unrolling_node_info *)ir_nodemap_get(&map, n); if (! info) return NULL; @@ -551,13 +529,13 @@ static ir_node *get_unroll_copy(ir_node *n, int nr) /* Sets copy cp of node n. */ static void set_inversion_copy(ir_node *n, ir_node *cp) { - phase_set_irn_data(phase, n, cp); + ir_nodemap_insert(&map, n, cp); } /* Getter of copy of n for inversion */ static ir_node *get_inversion_copy(ir_node *n) { - ir_node *cp = (ir_node *)phase_get_irn_data(phase, n); + ir_node *cp = (ir_node *)ir_nodemap_get(&map, n); return cp; } @@ -572,26 +550,20 @@ static void reset_block_mark(ir_node *node, void * env) /* Returns mark of node, or its block if node is not a block. * Used in this context to determine if node is in the condition chain. */ -static unsigned is_nodes_block_marked(ir_node* node) +static bool is_nodes_block_marked(const ir_node* node) { - if (is_Block(node)) - return get_Block_mark(node); - else - return get_Block_mark(get_block(node)); + return get_Block_mark(get_block_const(node)); } /* Extends a nodes ins by node new. * NOTE: This is slow if a node n needs to be extended more than once. */ -static void extend_irn(ir_node *n, ir_node *newnode, int new_is_backedge) +static void extend_irn(ir_node *n, ir_node *newnode, bool new_is_backedge) { - ir_node **ins; int i; int arity = get_irn_arity(n); int new_arity = arity + 1; - int *bes; - - NEW_ARR_A(int, bes, new_arity); - NEW_ARR_A(ir_node *, ins, new_arity); + ir_node **ins = XMALLOCN(ir_node*, new_arity); + bool *bes = XMALLOCN(bool, new_arity); /* save bes */ /* Bes are important! @@ -634,7 +606,7 @@ static void extend_ins_by_copy(ir_node *block, int pos) pred = get_irn_n(block, pos); new_in = get_inversion_copy(pred); DB((dbg, LEVEL_5, "Extend block %N by %N cp of %N\n", block, new_in, pred)); - extend_irn(block, new_in, 0); + extend_irn(block, new_in, false); /* Extend block phis by copy of definition at pos */ for_each_phi(block, phi) { @@ -650,12 +622,12 @@ static void extend_ins_by_copy(ir_node *block, int pos) new_in = cp; DB((dbg, LEVEL_5, "Extend phi %N by %N cp of %N\n", phi, new_in, pred)); - extend_irn(phi, new_in, 0); + extend_irn(phi, new_in, false); } } /* Returns the number of blocks backedges. With or without alien bes. */ -static int get_backedge_n(ir_node *block, unsigned with_alien) +static int get_backedge_n(ir_node *block, bool with_alien) { int i; int be_n = 0; @@ -956,13 +928,13 @@ static void get_head_outs(ir_node *node, void *env) * (Some blocks need to be removed once again.) * Returns 1 if the given block belongs to the condition chain. */ -static unsigned find_condition_chain(ir_node *block) +static void find_condition_chain(ir_node *block) { const ir_edge_t *edge; - unsigned mark = 0; - unsigned has_be = 0; - unsigned jmp_only; - unsigned nodes_n = 0; + bool mark = false; + bool has_be = false; + bool jmp_only = true; + unsigned nodes_n = 0; mark_irn_visited(block); @@ -979,16 +951,15 @@ static unsigned find_condition_chain(ir_node *block) * continuing with another subtree. */ if (loop_info.cc_size + nodes_n > opt_params.max_cc_size) { set_Block_mark(block, 0); - return 0; + return; } /* Check if block only has a jmp instruction. */ - jmp_only = 1; foreach_out_edge(block, edge) { ir_node *src = get_edge_src_irn(edge); - if (! is_Block(src) && ! is_Jmp(src)) { - jmp_only = 0; + if (!is_Block(src) && !is_Jmp(src)) { + jmp_only = false; } } @@ -998,8 +969,8 @@ static unsigned find_condition_chain(ir_node *block) ir_node *src = get_edge_src_irn(edge); int pos = get_edge_src_pos(edge); - if (! is_in_loop(src)) - mark = 1; + if (!is_in_loop(src)) + mark = true; /* Inverting blocks with backedge outs leads to a cf edge * from the inverted head, into the inverted head (skipping the body). @@ -1007,7 +978,7 @@ static unsigned find_condition_chain(ir_node *block) * this would introduce another loop in the existing loop. * This loop inversion cannot cope with this case. */ if (is_backedge(src, pos)) { - has_be = 1; + has_be = true; break; } } @@ -1026,7 +997,7 @@ static unsigned find_condition_chain(ir_node *block) */ /* Collect blocks containing only a Jmp. * Do not collect blocks with backedge outs. */ - if ((jmp_only == 1 || mark == 1) && has_be == 0) { + if ((jmp_only || mark) && !has_be) { set_Block_mark(block, 1); ++inversion_blocks_in_cc; loop_info.cc_size += nodes_n; @@ -1042,8 +1013,6 @@ static unsigned find_condition_chain(ir_node *block) if (is_in_loop(src) && ! irn_visited(src)) find_condition_chain(src); } - - return mark; } /** @@ -1059,8 +1028,9 @@ static void fix_copy_inversion(void) ir_node **phis; ir_node *phi, *next; ir_node *head_cp = get_inversion_copy(loop_head); + ir_graph *irg = get_irn_irg(head_cp); int arity = get_irn_arity(head_cp); - int backedges = get_backedge_n(head_cp, 0); + int backedges = get_backedge_n(head_cp, false); int new_arity = arity - backedges; int pos; int i; @@ -1074,7 +1044,7 @@ static void fix_copy_inversion(void) ins[pos++] = get_irn_n(head_cp, i); } - new_head = new_Block(new_arity, ins); + new_head = new_r_Block(irg, new_arity, ins); phis = NEW_ARR_F(ir_node *, 0); @@ -1113,8 +1083,9 @@ static void fix_head_inversion(void) ir_node **ins; ir_node *phi, *next; ir_node **phis; + ir_graph *irg = get_irn_irg(loop_head); int arity = get_irn_arity(loop_head); - int backedges = get_backedge_n(loop_head, 0); + int backedges = get_backedge_n(loop_head, false); int new_arity = backedges; int pos; int i; @@ -1128,7 +1099,7 @@ static void fix_head_inversion(void) ins[pos++] = get_irn_n(loop_head, i); } - new_head = new_Block(new_arity, ins); + new_head = new_r_Block(irg, new_arity, ins); phis = NEW_ARR_F(ir_node *, 0); @@ -1177,7 +1148,7 @@ static void fix_head_inversion(void) } /* Does the loop inversion. */ -static void inversion_walk(entry_edge *head_entries) +static void inversion_walk(ir_graph *irg, entry_edge *head_entries) { size_t i; @@ -1186,10 +1157,10 @@ static void inversion_walk(entry_edge *head_entries) * Any change of the order leads to lost information that would be needed later. */ - ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); /* 1. clone condition chain */ - inc_irg_visited(current_ir_graph); + inc_irg_visited(irg); for (i = 0; i < ARR_LEN(head_entries); ++i) { entry_edge entry = head_entries[i]; @@ -1200,7 +1171,7 @@ static void inversion_walk(entry_edge *head_entries) copy_walk(pred, is_nodes_block_marked, cur_loop); } - ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); /* 2. Extends the head control flow successors ins * with the definitions of the copied head node. */ @@ -1277,15 +1248,14 @@ static void inversion_walk(entry_edge *head_entries) } /* Performs loop inversion of cur_loop if possible and reasonable. */ -static void loop_inversion(void) +static void loop_inversion(ir_graph *irg) { int loop_depth; unsigned max_loop_nodes = opt_params.max_loop_size; unsigned max_loop_nodes_adapted; int depth_adaption = opt_params.depth_adaption; - unsigned do_inversion = 1; - unsigned has_cc = 0; + bool do_inversion = true; /* Depth of 0 is the procedure and 1 a topmost loop. */ loop_depth = get_loop_depth(cur_loop) - 1; @@ -1296,17 +1266,14 @@ static void loop_inversion(void) DB((dbg, LEVEL_1, "max_nodes: %d\nmax_nodes_adapted %d at depth of %d (adaption %d)\n", max_loop_nodes, max_loop_nodes_adapted, loop_depth, depth_adaption)); - if (! (loop_info.nodes > 0)) + if (loop_info.nodes == 0) return; -#if LOOP_IGNORE_NODE_LIMITS - DB((dbg, LEVEL_1, "WARNING: Loop node limitations ignored.")); -#else if (loop_info.nodes > max_loop_nodes) { /* Only for stats */ DB((dbg, LEVEL_1, "Nodes %d > allowed nodes %d\n", loop_info.nodes, loop_depth, max_loop_nodes)); - count_stats(stats.too_large); + ++stats.too_large; /* no RETURN */ /* Adaption might change it */ } @@ -1315,24 +1282,23 @@ static void loop_inversion(void) if (loop_info.nodes > max_loop_nodes_adapted) { DB((dbg, LEVEL_1, "Nodes %d > allowed nodes (depth %d adapted) %d\n", loop_info.nodes, loop_depth, max_loop_nodes_adapted)); - count_stats(stats.too_large_adapted); + ++stats.too_large_adapted; return; } if (loop_info.calls > opt_params.allowed_calls) { DB((dbg, LEVEL_1, "Calls %d > allowed calls %d\n", loop_info.calls, opt_params.allowed_calls)); - count_stats(stats.calls_limit); + ++stats.calls_limit; return; } -#endif /*inversion_head_node_limit = INT_MAX;*/ - ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); + ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK); /* Reset block marks. * We use block marks to flag blocks of the original condition chain. */ - irg_walk_graph(current_ir_graph, reset_block_mark, NULL, NULL); + irg_walk_graph(irg, reset_block_mark, NULL, NULL); /*loop_info.blocks = get_loop_n_blocks(cur_loop);*/ cond_chain_entries = NEW_ARR_F(entry_edge, 0); @@ -1342,39 +1308,35 @@ static void loop_inversion(void) inversion_blocks_in_cc = 0; /* Use phase to keep copy of nodes from the condition chain. */ - phase = new_phase(current_ir_graph, phase_irn_init_default); + ir_nodemap_init(&map, irg); + obstack_init(&obst); /* Search for condition chains and temporarily save the blocks in an array. */ cc_blocks = NEW_ARR_F(ir_node *, 0); - inc_irg_visited(current_ir_graph); - has_cc = find_condition_chain(loop_head); + inc_irg_visited(irg); + find_condition_chain(loop_head); unmark_not_allowed_cc_blocks(); DEL_ARR_F(cc_blocks); -#if LOOP_IGNORE_NODE_LIMITS - (void) unmark_cc_blocks; -#else /* Condition chain too large. * Loop should better be small enough to fit into the cache. */ /* TODO Of course, we should take a small enough cc in the first place, * which is not that simple. (bin packing) */ if (loop_info.cc_size > opt_params.max_cc_size) { - count_stats(stats.cc_limit_reached); + ++stats.cc_limit_reached; - do_inversion = 0; + do_inversion = false; /* Unmark cc blocks except the head. * Invert head only for possible unrolling. */ unmark_cc_blocks(); - } -#endif /* We also catch endless loops here, * because they do not have a condition chain. */ if (inversion_blocks_in_cc < 1) { - do_inversion = 0; + do_inversion = false; DB((dbg, LEVEL_3, "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n", inversion_blocks_in_cc)); @@ -1384,29 +1346,27 @@ static void loop_inversion(void) cur_head_outs = NEW_ARR_F(entry_edge, 0); /* Get all edges pointing into the condition chain. */ - irg_walk_graph(current_ir_graph, get_head_outs, NULL, NULL); + irg_walk_graph(irg, get_head_outs, NULL, NULL); /* Do the inversion */ - inversion_walk(cur_head_outs); + inversion_walk(irg, cur_head_outs); DEL_ARR_F(cur_head_outs); /* Duplicated blocks changed doms */ - set_irg_doms_inconsistent(current_ir_graph); - /* Loop content changed */ - set_irg_loopinfo_inconsistent(current_ir_graph); - /* TODO are they? Depends on set_irn_in and set_irn_n exchange and new_node. */ - set_irg_outs_inconsistent(current_ir_graph); + clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE + | IR_GRAPH_STATE_CONSISTENT_LOOPINFO); - count_stats(stats.inverted); + ++stats.inverted; } /* free */ - phase_free(phase); + obstack_free(&obst, NULL); + ir_nodemap_destroy(&map); DEL_ARR_F(cond_chain_entries); DEL_ARR_F(head_df_loop); - ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); + ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK); } /* Fix the original loop_heads ins for invariant unrolling case. */ @@ -1633,9 +1593,9 @@ static ir_node *clone_phis_sans_bes(ir_node *phi, ir_node *be_block, ir_node *de * using be_block as supplier of backedge informations. */ static ir_node *clone_block_sans_bes(ir_node *node, ir_node *be_block) { - ir_node **ins; int arity = get_irn_arity(node); int i, c = 0; + ir_node **ins; assert(get_irn_arity(node) == get_irn_arity(be_block)); assert(is_Block(node)); @@ -1658,10 +1618,9 @@ static ir_node *new_Abs(ir_node *op, ir_mode *mode) ir_graph *irg = get_irn_irg(op); ir_node *block = get_nodes_block(op); ir_node *zero = new_r_Const(irg, get_mode_null(mode)); - ir_node *cmp = new_r_Cmp(block, op, zero); - ir_node *cond = new_r_Proj(cmp, mode_b, pn_Cmp_Lt); + ir_node *cmp = new_r_Cmp(block, op, zero, ir_relation_less); ir_node *minus_op = new_r_Minus(block, op, mode); - ir_node *mux = new_r_Mux(block, cond, op, minus_op, mode); + ir_node *mux = new_r_Mux(block, cmp, op, minus_op, mode); return mux; } @@ -1675,8 +1634,8 @@ static void create_duffs_block(void) ir_mode *mode; ir_node *block1, *count_block, *duff_block; - ir_node *ems, *ems_divmod, *ems_mod_proj, *cmp_null, - *cmp_proj, *ems_mode_cond, *x_true, *x_false, *const_null; + ir_node *ems, *ems_mod, *ems_div, *ems_mod_proj, *cmp_null, + *ems_mode_cond, *x_true, *x_false, *const_null; ir_node *true_val, *false_val; ir_node *ins[2]; @@ -1713,21 +1672,25 @@ static void create_duffs_block(void) ems = new_Sub(loop_info.end_val, loop_info.start_val, get_irn_mode(loop_info.end_val)); - DB((dbg, LEVEL_4, "divmod ins %N %N\n", ems, loop_info.step)); - ems_divmod = new_r_DivMod(block1, + DB((dbg, LEVEL_4, "mod ins %N %N\n", ems, loop_info.step)); + ems_mod = new_r_Mod(block1, + new_NoMem(), + ems, + loop_info.step, + mode, + op_pin_state_pinned); + ems_div = new_r_Div(block1, new_NoMem(), ems, loop_info.step, mode, op_pin_state_pinned); - DB((dbg, LEVEL_4, "New module node %N\n", ems_divmod)); - - ems_mod_proj = new_r_Proj(ems_divmod, mode_Iu, pn_DivMod_res_mod); - cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null); - cmp_proj = new_r_Proj(cmp_null, mode_b, pn_Cmp_Eq); - ems_mode_cond = new_r_Cond(block1, cmp_proj); + DB((dbg, LEVEL_4, "New module node %N\n", ems_mod)); + ems_mod_proj = new_r_Proj(ems_mod, mode_Iu, pn_Mod_res); + cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null, ir_relation_less); + ems_mode_cond = new_r_Cond(block1, cmp_null); /* ems % step == 0 */ x_true = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_true); @@ -1767,13 +1730,11 @@ static void create_duffs_block(void) correction = new_r_Phi(count_block, 2, ins, mode); - count = new_r_Proj(ems_divmod, mode, pn_DivMod_res_div); + count = new_r_Proj(ems_div, mode, pn_Div_res); /* (end - start) / step + correction */ count = new_Add(count, correction, mode); - cmp_bad_count = new_r_Cmp(count_block, count, const_null); - /* We preconditioned the loop to be tail-controlled. * So, if count is something 'wrong' like 0, * negative/positive (depending on step direction), @@ -1782,12 +1743,14 @@ static void create_duffs_block(void) /* Depending on step direction, we have to check for > or < 0 */ if (loop_info.decreasing == 1) { - bad_count_neg = new_r_Proj(cmp_bad_count, mode_b, pn_Cmp_Lt); + cmp_bad_count = new_r_Cmp(count_block, count, const_null, + ir_relation_less); } else { - bad_count_neg = new_r_Proj(cmp_bad_count, mode_b, pn_Cmp_Gt); + cmp_bad_count = new_r_Cmp(count_block, count, const_null, + ir_relation_greater); } - bad_count_neg = new_r_Cond(count_block, bad_count_neg); + bad_count_neg = new_r_Cond(count_block, cmp_bad_count); good_count = new_Proj(bad_count_neg, mode_X, pn_Cond_true); bad_count = new_Proj(ems_mode_cond, mode_X, pn_Cond_false); @@ -1986,38 +1949,17 @@ static unsigned get_const_pred(ir_node *node, ir_node **const_pred, ir_node **ot return 1; } -/* Returns the mathematically inverted pn_Cmp. */ -static pn_Cmp get_math_inverted_case(pn_Cmp proj) -{ - switch(proj) { - case pn_Cmp_Eq: - return pn_Cmp_Lg; - case pn_Cmp_Lg: - return pn_Cmp_Eq; - case pn_Cmp_Lt: - return pn_Cmp_Ge; - case pn_Cmp_Le: - return pn_Cmp_Gt; - case pn_Cmp_Gt: - return pn_Cmp_Le; - case pn_Cmp_Ge: - return pn_Cmp_Lt; - default: - panic("Unhandled pn_Cmp."); - } -} - /* Returns 1 if loop exits within 2 steps of the iv. * Norm_proj means we do not exit the loop.*/ static unsigned simulate_next(ir_tarval **count_tar, ir_tarval *stepped, ir_tarval *step_tar, ir_tarval *end_tar, - pn_Cmp norm_proj) + ir_relation norm_proj) { ir_tarval *next; DB((dbg, LEVEL_4, "Loop taken if (stepped)%ld %s (end)%ld ", get_tarval_long(stepped), - get_pnc_string((norm_proj)), + get_relation_string((norm_proj)), get_tarval_long(end_tar))); DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value)); @@ -2028,7 +1970,7 @@ static unsigned simulate_next(ir_tarval **count_tar, DB((dbg, LEVEL_4, "Result: (stepped)%ld IS %s (end)%ld\n", get_tarval_long(stepped), - get_pnc_string(tarval_cmp(stepped, end_tar)), + get_relation_string(tarval_cmp(stepped, end_tar)), get_tarval_long(end_tar))); /* next step */ @@ -2040,7 +1982,7 @@ static unsigned simulate_next(ir_tarval **count_tar, DB((dbg, LEVEL_4, "Loop taken if %ld %s %ld ", get_tarval_long(next), - get_pnc_string(norm_proj), + get_relation_string(norm_proj), get_tarval_long(end_tar))); DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value)); @@ -2065,7 +2007,7 @@ static unsigned simulate_next(ir_tarval **count_tar, static ir_node *is_simple_loop(void) { int arity, i; - ir_node *loop_block, *exit_block, *projx, *cond, *projres, *loop_condition; + ir_node *loop_block, *exit_block, *projx, *cond, *cmp; /* Maximum of one condition, and no endless loops. */ if (loop_info.cf_outs != 1) @@ -2073,18 +2015,12 @@ static ir_node *is_simple_loop(void) DB((dbg, LEVEL_4, "1 loop exit\n")); -#if LOOP_IGNORE_NODE_LIMITS - /* Ignore loop size. Probably not wise in other than testcases. */ - loop_info.max_unroll = 40; -#else /* Calculate maximum unroll_nr keeping node count below limit. */ loop_info.max_unroll = (int)((double)opt_params.max_unrolled_loop_size / (double)loop_info.nodes); if (loop_info.max_unroll < 2) { - count_stats(stats.too_large); + ++stats.too_large; return NULL; } -#endif - DB((dbg, LEVEL_4, "maximum unroll factor %u, to not exceed node limit \n", opt_params.max_unrolled_loop_size)); @@ -2120,13 +2056,12 @@ static ir_node *is_simple_loop(void) /* find value on which loop exit depends */ projx = loop_info.cf_out.pred; cond = get_irn_n(projx, 0); - projres = get_irn_n(cond, 0); - loop_condition = get_irn_n(projres, 0); + cmp = get_irn_n(cond, 0); - if (!is_Cmp(loop_condition)) + if (!is_Cmp(cmp)) return NULL; - DB((dbg, LEVEL_5, "projection is %s\n", get_pnc_string(get_Proj_proj(projx)))); + DB((dbg, LEVEL_5, "projection is %s\n", get_relation_string(get_Proj_proj(projx)))); switch(get_Proj_proj(projx)) { case pn_Cond_false: @@ -2140,8 +2075,7 @@ static ir_node *is_simple_loop(void) } DB((dbg, LEVEL_4, "Valid Cmp.\n")); - - return projres; + return cmp; } /* Returns 1 if all nodes are mode_Iu or mode_Is. */ @@ -2164,7 +2098,7 @@ static unsigned get_unroll_decision_invariant(void) { ir_node *projres, *loop_condition, *iteration_path; - unsigned success, is_latest_val; + unsigned success; ir_tarval *step_tar; ir_mode *mode; @@ -2193,9 +2127,6 @@ static unsigned get_unroll_decision_invariant(void) * Until now we only have end_val. */ if (is_Add(iteration_path) || is_Sub(iteration_path)) { - /* We test against the latest value of the iv. */ - is_latest_val = 1; - loop_info.add = iteration_path; DB((dbg, LEVEL_4, "Case 1: Got add %N (maybe not sane)\n", loop_info.add)); @@ -2222,9 +2153,6 @@ static unsigned get_unroll_decision_invariant(void) } else if (is_Phi(iteration_path)) { ir_node *new_iteration_phi; - /* We compare with the value the iv had entering this run. */ - is_latest_val = 0; - loop_info.iteration_phi = iteration_path; DB((dbg, LEVEL_4, "Case 2: Got phi %N\n", loop_info.iteration_phi)); @@ -2370,15 +2298,16 @@ static unsigned get_preferred_factor_constant(ir_tarval *count_tar) /* TODO split. */ static unsigned get_unroll_decision_constant(void) { - ir_node *projres, *loop_condition, *iteration_path; - unsigned success, is_latest_val; - ir_tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar, *stepped; - pn_Cmp proj_proj, norm_proj; - ir_mode *mode; + ir_node *cmp, *iteration_path; + unsigned success, is_latest_val; + ir_tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar; + ir_tarval *stepped; + ir_relation proj_proj, norm_proj; + ir_mode *mode; /* RETURN if loop is not 'simple' */ - projres = is_simple_loop(); - if (projres == NULL) + cmp = is_simple_loop(); + if (cmp == NULL) return 0; /* One in of the loop condition needs to be loop invariant. => end_val @@ -2396,9 +2325,7 @@ static unsigned get_unroll_decision_constant(void) /\ */ - loop_condition = get_irn_n(projres, 0); - - success = get_const_pred(loop_condition, &loop_info.end_val, &iteration_path); + success = get_const_pred(cmp, &loop_info.end_val, &iteration_path); if (! success) return 0; @@ -2509,7 +2436,7 @@ static unsigned get_unroll_decision_constant(void) return 0; } - count_stats(stats.u_simple_counting_loop); + ++stats.u_simple_counting_loop; loop_info.latest_value = is_latest_val; @@ -2530,17 +2457,16 @@ static unsigned get_unroll_decision_constant(void) DB((dbg, LEVEL_4, "stepped to %ld\n", get_tarval_long(stepped))); - proj_proj = get_Proj_pn_cmp(projres); + proj_proj = get_Cmp_relation(cmp); /* Assure that norm_proj is the stay-in-loop case. */ if (loop_info.exit_cond == 1) - norm_proj = get_math_inverted_case(proj_proj); + norm_proj = get_negated_relation(proj_proj); else norm_proj = proj_proj; - DB((dbg, LEVEL_4, "normalized projection %s\n", get_pnc_string(norm_proj))); - + DB((dbg, LEVEL_4, "normalized projection %s\n", get_relation_string(norm_proj))); /* Executed at most once (stay in counting loop if a Eq b) */ - if (norm_proj == pn_Cmp_Eq) + if (norm_proj == ir_relation_equal) /* TODO Might be worth a warning. */ return 0; @@ -2577,23 +2503,19 @@ static void unroll_loop(void) if (! (loop_info.nodes > 0)) return; -#if LOOP_IGNORE_NODE_LIMITS - DB((dbg, LEVEL_1, "WARNING: Loop node limitations ignored.")); -#else if (loop_info.nodes > opt_params.max_unrolled_loop_size) { DB((dbg, LEVEL_2, "Nodes %d > allowed nodes %d\n", loop_info.nodes, opt_params.max_unrolled_loop_size)); - count_stats(stats.too_large); + ++stats.too_large; return; } if (loop_info.calls > 0) { DB((dbg, LEVEL_2, "Calls %d > allowed calls 0\n", loop_info.calls)); - count_stats(stats.calls_limit); + ++stats.calls_limit; return; } -#endif unroll_nr = 0; @@ -2633,7 +2555,8 @@ static void unroll_loop(void) } /* Use phase to keep copy of nodes from the condition chain. */ - phase = new_phase(current_ir_graph, phase_irn_init_default); + ir_nodemap_init(&map, current_ir_graph); + obstack_init(&obst); /* Copies the loop */ copy_loop(loop_entries, unroll_nr - 1); @@ -2648,28 +2571,27 @@ static void unroll_loop(void) irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL); if (loop_info.unroll_kind == constant) - count_stats(stats.constant_unroll); + ++stats.constant_unroll; else - count_stats(stats.invariant_unroll); + ++stats.invariant_unroll; - set_irg_doms_inconsistent(current_ir_graph); - set_irg_loopinfo_inconsistent(current_ir_graph); - /* TODO is it? */ - set_irg_outs_inconsistent(current_ir_graph); + clear_irg_state(current_ir_graph, IR_GRAPH_STATE_CONSISTENT_DOMINANCE); DEL_ARR_F(loop_entries); + obstack_free(&obst, NULL); + ir_nodemap_destroy(&map); } } /* Analyzes the loop, and checks if size is within allowed range. * Decides if loop will be processed. */ -static void init_analyze(ir_loop *loop) +static void init_analyze(ir_graph *irg, ir_loop *loop) { cur_loop = loop; - loop_head = NULL; - loop_head_valid = 1; + loop_head = NULL; + loop_head_valid = true; /* Reset loop info */ memset(&loop_info, 0, sizeof(loop_info_t)); @@ -2678,7 +2600,7 @@ static void init_analyze(ir_loop *loop) get_loop_node(loop, 0))); /* Collect loop informations: head, node counts. */ - irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL); + irg_walk_graph(irg, get_loop_info, NULL, NULL); /* RETURN if there is no valid head */ if (!loop_head || !loop_head_valid) { @@ -2691,13 +2613,13 @@ static void init_analyze(ir_loop *loop) if (loop_info.branches > opt_params.max_branches) { DB((dbg, LEVEL_1, "Branches %d > allowed branches %d\n", loop_info.branches, opt_params.max_branches)); - count_stats(stats.calls_limit); + ++stats.calls_limit; return; } switch (loop_op) { case loop_op_inversion: - loop_inversion(); + loop_inversion(irg); break; case loop_op_unrolling: @@ -2731,15 +2653,15 @@ static void set_loop_params(void) { opt_params.max_loop_size = 100; opt_params.depth_adaption = -50; - opt_params.count_phi = 1; - opt_params.count_proj = 0; + opt_params.count_phi = true; + opt_params.count_proj = false; opt_params.allowed_calls = 0; opt_params.max_cc_size = 5; - opt_params.allow_const_unrolling = 1; - opt_params.allow_invar_unrolling = 0; + opt_params.allow_const_unrolling = true; + opt_params.allow_invar_unrolling = false; opt_params.invar_unrolling_min_size = 20; opt_params.max_unrolled_loop_size = 400; @@ -2761,16 +2683,8 @@ void loop_optimization(ir_graph *irg) /* Preconditions */ set_current_ir_graph(irg); - edges_assure(irg); - assure_irg_outs(irg); - - /* NOTE: sets only the loop attribute of blocks, not nodes */ - /* NOTE: Kills links */ - assure_cf_loop(irg); - ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); collect_phiprojs(irg); - ir_free_resources(irg, IR_RESOURCE_IRN_LINK); loop = get_irg_loop(irg); sons = get_loop_n_sons(loop); @@ -2781,74 +2695,78 @@ void loop_optimization(ir_graph *irg) find_innermost_loop(get_loop_son(loop, nr)); } - ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK); /* Set all links to NULL */ - irg_walk_graph(current_ir_graph, reset_link, NULL, NULL); + irg_walk_graph(irg, reset_link, NULL, NULL); for (i = 0; i < ARR_LEN(loops); ++i) { ir_loop *loop = loops[i]; - count_stats(stats.loops); + ++stats.loops; /* Analyze and handle loop */ - init_analyze(loop); + init_analyze(irg, loop); /* Copied blocks do not have their phi list yet */ collect_phiprojs(irg); /* Set links to NULL * TODO Still necessary? */ - irg_walk_graph(current_ir_graph, reset_link, NULL, NULL); + irg_walk_graph(irg, reset_link, NULL, NULL); } print_stats(); DEL_ARR_F(loops); - ir_free_resources(irg, IR_RESOURCE_IRN_LINK); - ir_free_resources(irg, IR_RESOURCE_PHI_LIST); + ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST); } -void do_loop_unrolling(ir_graph *irg) +static ir_graph_state_t perform_loop_unrolling(ir_graph *irg) { loop_op = loop_op_unrolling; - - DB((dbg, LEVEL_1, " >>> unrolling (Startnode %N) <<<\n", - get_irg_start(irg))); - loop_optimization(irg); - - DB((dbg, LEVEL_1, " >>> unrolling done (Startnode %N) <<<\n", - get_irg_start(irg))); + return 0; } -void do_loop_inversion(ir_graph *irg) +static ir_graph_state_t perform_loop_inversion(ir_graph *irg) { loop_op = loop_op_inversion; - - DB((dbg, LEVEL_1, " >>> inversion (Startnode %N) <<<\n", - get_irg_start(irg))); - loop_optimization(irg); - - assure_cf_loop(irg); - - DB((dbg, LEVEL_1, " >>> inversion done (Startnode %N) <<<\n", - get_irg_start(irg))); + return 0; } -void do_loop_peeling(ir_graph *irg) +static ir_graph_state_t perform_loop_peeling(ir_graph *irg) { loop_op = loop_op_peeling; + loop_optimization(irg); + return 0; +} - DB((dbg, LEVEL_1, " >>> peeling (Startnode %N) <<<\n", - get_irg_start(irg))); +static optdesc_t opt_unroll_loops = { + "unroll-loops", + IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_CONSISTENT_OUTS | IR_GRAPH_STATE_CONSISTENT_LOOPINFO, + perform_loop_unrolling, +}; - loop_optimization(irg); +static optdesc_t opt_invert_loops = { + "invert-loops", + IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_CONSISTENT_OUTS | IR_GRAPH_STATE_CONSISTENT_LOOPINFO, + perform_loop_inversion, +}; - DB((dbg, LEVEL_1, " >>> peeling done (Startnode %N) <<<\n", - get_irg_start(irg))); +static optdesc_t opt_peel_loops = { + "peel-loops", + IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_CONSISTENT_OUTS | IR_GRAPH_STATE_CONSISTENT_LOOPINFO, + perform_loop_peeling, +}; -} +void do_loop_unrolling(ir_graph *irg) +{ perform_irg_optimization(irg, &opt_unroll_loops); } + +void do_loop_inversion(ir_graph *irg) +{ perform_irg_optimization(irg, &opt_invert_loops); } + +void do_loop_peeling(ir_graph *irg) +{ perform_irg_optimization(irg, &opt_peel_loops); } ir_graph_pass_t *loop_inversion_pass(const char *name) {