X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=8e7fae7e6e66c939bf93a6feab9649dcd718b3ac;hb=9fbdcb82b2911748b70d5294195c248d4ee0edaf;hp=34139aa2487a4ccf4e524952e2bb17fc220b17aa;hpb=ce6161a7e42a48f7422b7babcc64d8ace18e2687;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index 34139aa24..8e7fae7e6 100644 --- a/ir/opt/loop.c +++ b/ir/opt/loop.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2010 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -22,11 +22,11 @@ * @author Christian Helmer * @brief loop inversion and loop unrolling * - * @version $Id$ */ - #include "config.h" +#include + #include "iroptimize.h" #include "opt_init.h" #include "irnode.h" @@ -44,20 +44,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. @@ -80,7 +74,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 { @@ -98,18 +92,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; @@ -129,13 +117,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)); @@ -149,28 +137,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; +unsigned max_unrolled_loop_size; /* [nodes] */ +bool allow_const_unrolling; +bool allow_invar_unrolling; unsigned invar_unrolling_min_size; /* [nodes] */ } loop_opt_params_t; @@ -179,23 +160,23 @@ static loop_opt_params_t opt_params; /* Loop analysis informations */ typedef struct loop_info_t { - unsigned nodes; /* node count */ - unsigned ld_st; /* load and store nodes */ - unsigned branches; /* number of conditions */ - unsigned calls; /* number of calls */ - unsigned cf_outs; /* number of cf edges which leave the loop */ - entry_edge cf_out; /* single loop leaving cf edge */ - int be_src_pos; /* position of the single own backedge in the head */ + unsigned nodes; /* node count */ + unsigned ld_st; /* load and store nodes */ + unsigned branches; /* number of conditions */ + unsigned calls; /* number of calls */ + unsigned cf_outs; /* number of cf edges which leave the loop */ + entry_edge cf_out; /* single loop leaving cf edge */ + int be_src_pos; /* position of the single own backedge in the head */ /* for inversion */ - unsigned cc_size; /* nodes in the condition chain */ + unsigned cc_size; /* nodes in the condition chain */ /* for unrolling */ - unsigned max_unroll; /* Number of unrolls satisfying max_loop_size */ - unsigned exit_cond; /* 1 if condition==true exits the loop. */ - unsigned latest_value:1; /* 1 if condition is checked against latest counter value */ - unsigned needs_backedge:1; /* 0 if loop is completely unrolled */ - unsigned decreasing:1; /* Step operation is_Sub, or step is<0 */ + unsigned max_unroll; /* Number of unrolls satisfying max_loop_size */ + unsigned exit_cond; /* 1 if condition==true exits the loop. */ + unsigned latest_value:1; /* 1 if condition is checked against latest counter value */ + unsigned needs_backedge:1; /* 0 if loop is completely unrolled */ + unsigned decreasing:1; /* Step operation is_Sub, or step is<0 */ /* IV informations of a simple loop */ ir_node *start_val; @@ -206,8 +187,8 @@ typedef struct loop_info_t { ir_tarval *count_tar; /* Number of loop iterations */ - ir_node *duff_cond; /* Duff mod */ - unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */ + ir_node *duff_cond; /* Duff mod */ + unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */ } loop_info_t; /* Information about the current loop */ @@ -229,7 +210,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 { @@ -258,34 +240,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; @@ -295,31 +290,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) @@ -333,7 +312,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; } @@ -379,7 +358,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; @@ -389,7 +368,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) { @@ -404,7 +383,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 */ @@ -425,7 +403,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. */ @@ -517,16 +495,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; @@ -538,7 +514,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; @@ -552,13 +528,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; } @@ -573,26 +549,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! @@ -635,7 +605,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) { @@ -651,12 +621,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; @@ -703,7 +673,7 @@ static ir_node *copy_node(ir_node *node) * Order of ins is important for later usage. */ static void copy_walk(ir_node *node, walker_condition *walk_condition, - ir_loop *set_loop) + ir_loop *set_loop) { int i; int arity; @@ -785,8 +755,8 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, * Order of ins is important for later usage. * Takes copy_index, to phase-link copy at specific index. */ -static void copy_walk_n(ir_node *node, - walker_condition *walk_condition, int copy_index) +static void copy_walk_n(ir_node *node, walker_condition *walk_condition, + int copy_index) { int i; int arity; @@ -860,8 +830,8 @@ static void copy_walk_n(ir_node *node, /* Removes alle Blocks with non marked predecessors from the condition chain. */ static void unmark_not_allowed_cc_blocks(void) { - int blocks = ARR_LEN(cc_blocks); - int i; + size_t blocks = ARR_LEN(cc_blocks); + size_t i; for(i = 0; i < blocks; ++i) { ir_node *block = cc_blocks[i]; @@ -889,8 +859,8 @@ static void unmark_not_allowed_cc_blocks(void) * TODO: invert head for unrolling? */ static void unmark_cc_blocks(void) { - int blocks = ARR_LEN(cc_blocks); - int i; + size_t blocks = ARR_LEN(cc_blocks); + size_t i; for(i = 0; i < blocks; ++i) { ir_node *block = cc_blocks[i]; @@ -957,13 +927,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); @@ -980,16 +950,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; } } @@ -999,8 +968,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). @@ -1008,7 +977,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; } } @@ -1021,13 +990,13 @@ static unsigned find_condition_chain(ir_node *block) * / A* B / | * / /\ / ? | * / C* => D | - * / D Head | + * / D Head | * / A \_| * C */ /* 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; @@ -1043,8 +1012,6 @@ static unsigned find_condition_chain(ir_node *block) if (is_in_loop(src) && ! irn_visited(src)) find_condition_chain(src); } - - return mark; } /** @@ -1059,10 +1026,11 @@ static void fix_copy_inversion(void) ir_node **ins; ir_node **phis; ir_node *phi, *next; - ir_node *head_cp = get_inversion_copy(loop_head); - int arity = get_irn_arity(head_cp); - int backedges = get_backedge_n(head_cp, 0); - int new_arity = arity - backedges; + 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, false); + int new_arity = arity - backedges; int pos; int i; @@ -1075,7 +1043,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); @@ -1114,9 +1082,10 @@ static void fix_head_inversion(void) ir_node **ins; ir_node *phi, *next; ir_node **phis; - int arity = get_irn_arity(loop_head); - int backedges = get_backedge_n(loop_head, 0); - int new_arity = backedges; + ir_graph *irg = get_irn_irg(loop_head); + int arity = get_irn_arity(loop_head); + int backedges = get_backedge_n(loop_head, false); + int new_arity = backedges; int pos; int i; @@ -1129,7 +1098,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); @@ -1178,19 +1147,19 @@ 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) { - int i; + size_t i; /* * The order of rewiring bottom-up is crucial. * 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]; @@ -1201,7 +1170,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. */ @@ -1278,15 +1247,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; @@ -1297,17 +1265,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 */ } @@ -1316,24 +1281,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); @@ -1343,39 +1307,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)); @@ -1385,29 +1345,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. */ @@ -1463,7 +1421,8 @@ static void correct_phis(ir_node *node, void *env) static void place_copies(int copies) { ir_node *loophead = loop_head; - int c, i; + size_t i; + int c; int be_src_pos = loop_info.be_src_pos; /* Serialize loops by fixing their head ins. @@ -1562,9 +1521,9 @@ static void place_copies(int copies) ir_node *pred = get_irn_n(phi, be_src_pos); ir_node *last_pred; - /* It is possible, that the value used - * in the OWN backedge path is NOT assigned in this loop. */ - if (is_in_loop(pred)) + /* It is possible, that the value used + * in the OWN backedge path is NOT assigned in this loop. */ + if (is_in_loop(pred)) last_pred = get_unroll_copy(pred, copies); else last_pred = pred; @@ -1579,11 +1538,12 @@ static void place_copies(int copies) /* Copies the cur_loop several times. */ static void copy_loop(entry_edge *cur_loop_outs, int copies) { - int i, c; + int c; ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); for (c = 0; c < copies; ++c) { + size_t i; inc_irg_visited(current_ir_graph); @@ -1632,9 +1592,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)); @@ -1657,10 +1617,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; } @@ -1674,8 +1633,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]; @@ -1712,21 +1671,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); @@ -1766,13 +1729,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), @@ -1781,12 +1742,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); @@ -1985,38 +1948,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)); @@ -2027,7 +1969,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 */ @@ -2039,7 +1981,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)); @@ -2064,7 +2006,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) @@ -2072,18 +2014,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)); @@ -2119,13 +2055,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: @@ -2139,8 +2074,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. */ @@ -2162,10 +2096,10 @@ static unsigned are_mode_I(ir_node *n1, ir_node* n2, ir_node *n3) static unsigned get_unroll_decision_invariant(void) { - ir_node *projres, *loop_condition, *iteration_path; - unsigned success, is_latest_val; - ir_tarval *step_tar; - ir_mode *mode; + ir_node *projres, *loop_condition, *iteration_path; + unsigned success; + ir_tarval *step_tar; + ir_mode *mode; /* RETURN if loop is not 'simple' */ @@ -2192,9 +2126,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)); @@ -2221,9 +2152,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)); @@ -2369,15 +2297,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 @@ -2395,9 +2324,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; @@ -2508,7 +2435,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; @@ -2529,17 +2456,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; @@ -2576,23 +2502,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; @@ -2611,7 +2533,7 @@ static void unroll_loop(void) if (opt_params.allow_invar_unrolling) unroll_nr = get_unroll_decision_invariant(); if (unroll_nr > 1) - loop_info.unroll_kind = invariant; + loop_info.unroll_kind = invariant; } DB((dbg, LEVEL_2, " *** Unrolling %d times ***\n", unroll_nr)); @@ -2632,7 +2554,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); @@ -2647,37 +2570,36 @@ 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)); - DB((dbg, LEVEL_1, " >>>> current loop includes node %N <<<\n", - get_loop_node(loop, 0))); + DB((dbg, LEVEL_1, " >>>> current loop %ld <<<\n", + get_loop_loop_nr(loop))); /* 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) { @@ -2690,13 +2612,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: @@ -2706,51 +2628,55 @@ static void init_analyze(ir_loop *loop) default: panic("Loop optimization not implemented."); } - DB((dbg, LEVEL_1, " <<<< end of loop with node %N >>>>\n", - get_loop_node(loop, 0))); + DB((dbg, LEVEL_1, " <<<< end of loop with node %ld >>>>\n", + get_loop_loop_nr(loop))); } /* Find innermost loops and add them to loops. */ static void find_innermost_loop(ir_loop *loop) { - /* descend into sons */ - int sons = get_loop_n_sons(loop); - - if (sons == 0) { - ARR_APP1(ir_loop *, loops, loop); - } else { - int s; - for (s=0; s>> 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) {