X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=d1e1a5ca67a6fa54285f3f99379033141da5479b;hb=c1c777ab401f028f3bfef31836da00c3f3fc5e0c;hp=091077fb48e6a52548a744b6c936b8192df6f165;hpb=c63d25e6b7c006dc62b7e6706b9fd7059d4b2c90;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index 091077fb4..d1e1a5ca6 100644 --- a/ir/opt/loop.c +++ b/ir/opt/loop.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -24,14 +24,13 @@ * * @version $Id$ */ - #include "config.h" #include "iroptimize.h" #include "opt_init.h" #include "irnode.h" #include "debug.h" - +#include "error.h" #include "ircons.h" #include "irgopt.h" @@ -45,6 +44,7 @@ #include "irpass.h" #include "irdom.h" +#include #include "irbackedge_t.h" #include "irphase_t.h" #include "irloop_t.h" @@ -52,6 +52,12 @@ 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 + /** * Convenience macro for iterating over every phi node of the given block. * Requires phi list per block. @@ -63,40 +69,32 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg); for ((phi) = (head), (next) = (head) ? get_Phi_next((head)) : NULL; \ (phi) ; (phi) = (next), (next) = (next) ? get_Phi_next((next)) : NULL) -/* currently processed loop */ +/* Currently processed loop. */ static ir_loop *cur_loop; -/* Condition for performing copy_walk. */ +/* Flag for kind of unrolling. */ +typedef enum { + constant, + invariant +} unrolling_kind_flag; + +/* Condition for performing visiting a node during copy_walk. */ typedef unsigned walker_condition(ir_node *); -/* Node and position of a predecessor */ -typedef struct out_edge { +/* Node and position of a predecessor. */ +typedef struct entry_edge { ir_node *node; int pos; -} out_edge; - -/**/ -typedef struct inversion_node_info { - ir_node *copy; - ir_node **ins; - struct inversion_node_info *free_list_next; /* linked list to free all node_infos */ -} inversion_node_info; - -/* */ -typedef struct node_info { - ir_node **copy; - ir_node **ins; - struct ir_node *free_list_next; /* linked list to free all node_infos */ -} node_info; - -/* Head of the list for freeing node_infos */ -static ir_node *free_list; + ir_node *pred; +} entry_edge; -/* A walker may start visiting the current loop with these nodes. */ -static out_edge *cur_loop_outs; +/* Node info for unrolling. */ +typedef struct unrolling_node_info { + ir_node **copies; +} unrolling_node_info; /* Outs of the nodes head. */ -static out_edge *cur_head_outs; +static entry_edge *cur_head_outs; /* Information about the loop head */ static ir_node *loop_head = NULL; @@ -105,155 +103,157 @@ static unsigned loop_head_valid = 1; /* List of all inner loops, that are processed. */ static ir_loop **loops; -/* Inverted head */ -static ir_node *loop_inv_head = NULL; -/* Peeled head */ -static ir_node *loop_peeled_head = NULL; - -/* Loop analysis informations */ -typedef struct loop_info_t { - unsigned blocks; /* number of blocks in the loop */ - unsigned calls; /* number of calls */ - unsigned cf_outs; - out_edge cf_out; - ir_node *new_loop_head; -} loop_info_t; - -/* Information about the current loop */ -static loop_info_t loop_info; - -/* Outs of the condition chain (loop inversion). */ -static out_edge *cond_chain_entries; - -/* Arity of the unrolled loop heads. */ -static int unroll_arity; - -static ir_phase *phase; +#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; + unsigned inverted; + unsigned too_large; + unsigned too_large_adapted; + unsigned cc_limit_reached; + unsigned calls_limit; -/* TODO */ -static unsigned head_inversion_node_count; -static unsigned inversion_head_node_limit; -static unsigned head_inversion_block_count; + unsigned u_simple_counting_loop; + unsigned constant_unroll; + unsigned invariant_unroll; -static unsigned enable_peeling; -static unsigned enable_inversion; -static unsigned enable_unrolling; + unsigned unhandled; +} loop_stats_t; +static loop_stats_t stats; -/* Creates node_info. A linked list keeps all node_infos to free them again. */ -static node_info *new_node_info(ir_node *node) +/* Set stats to sero */ +static void do_reset_stats(void) { - node_info *l = XMALLOCZ(node_info); - l->free_list_next = free_list; - free_list = node; - l->copy = NULL; - return l; + memset(&stats, 0, sizeof(loop_stats_t)); } -/* Returns linked node_info for given node. */ -static node_info *get_node_info(ir_node *n) +/* Print stats */ +static void do_print_stats(void) { - return ((node_info *)get_irn_link(n)); + DB((dbg, LEVEL_2, "---------------------------------------\n")); + DB((dbg, LEVEL_2, "loops : %d\n",stats.loops)); + DB((dbg, LEVEL_2, "inverted : %d\n",stats.inverted)); + DB((dbg, LEVEL_2, "too_large : %d\n",stats.too_large)); + DB((dbg, LEVEL_2, "too_large_adapted : %d\n",stats.too_large_adapted)); + DB((dbg, LEVEL_2, "cc_limit_reached : %d\n",stats.cc_limit_reached)); + DB((dbg, LEVEL_2, "calls_limit : %d\n",stats.calls_limit)); + DB((dbg, LEVEL_2, "u_simple_counting : %d\n",stats.u_simple_counting_loop)); + DB((dbg, LEVEL_2, "constant_unroll : %d\n",stats.constant_unroll)); + 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) -/* Allocates a node_info struct for the given node */ -static void alloc_node_info(ir_node *node) -{ - node_info *state; - state = new_node_info(node); - set_irn_link(node, (void *)state); -} +#endif -/* Frees node info and copy array for given node. Returns next node of free_list. */ -static ir_node *free_info(ir_node *node) -{ - node_info *info = get_node_info(node); - ir_node *next = info->free_list_next; - /*DB((dbg, LEVEL_1, "FREE %N\n", node));*/ - DEL_ARR_F(info->copy); - xfree(info); - set_irn_link(node, NULL); - return next; -} +/* 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 */ -/* Free all created node_infos, including the copy arrays. */ -static void free_node_info(void) -{ - ir_node *node = free_list; - while (node) { - node = free_info(node); - } - free_list = NULL; -} +unsigned max_cc_size; /* Maximum condition chain size [nodes] */ +unsigned max_branches; -/* Free node_infos of blocks only, including the copy arrays. */ -static void free_node_info_blocks(void) -{ - ir_node *node = free_list; - ir_node *new_freelist = NULL; - while (node) { - ir_node *next; - if (is_Block(node)) { - next = free_info(node); - } else { - next = get_node_info(node)->free_list_next; - get_node_info(node)->free_list_next = new_freelist; - new_freelist = node; - } - node = next; - } - free_list = new_freelist; -} +unsigned max_unrolled_loop_size; /* [nodes] */ +unsigned allow_const_unrolling:1; +unsigned allow_invar_unrolling:1; +unsigned invar_unrolling_min_size; /* [nodes] */ -/* Reset nodes link. For use with a walker. */ -static void reset_link(ir_node *node, void *env) -{ - (void)env; - set_irn_link(node, NULL); -} +} loop_opt_params_t; -static void set_inversion_copy(ir_node *n, ir_node *cp) -{ - phase_set_irn_data(phase, n, cp); -} +static loop_opt_params_t opt_params; -/* Returns a nodes copy. */ -static ir_node *get_copy(ir_node *n, int index) -{ - ir_node *cp = ((node_info *)get_irn_link(n))->copy[index]; - return cp; -} +/* 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 */ + + /* for inversion */ + 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 */ + + /* IV informations of a simple loop */ + ir_node *start_val; + ir_node *step; + ir_node *end_val; + ir_node *iteration_phi; + ir_node *add; + + ir_tarval *count_tar; /* Number of loop iterations */ + + ir_node *duff_cond; /* Duff mod */ + unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */ +} loop_info_t; -/* Returns a nodes copy if it exists, or else the node. */ -static ir_node *get_inversion_copy(ir_node *n) -{ - ir_node *cp = (ir_node *)phase_get_irn_data(phase, n); - return cp; -} +/* Information about the current loop */ +static loop_info_t loop_info; -/* Returns a nodes copy, or node if there is no node info linked. */ -static ir_node *get_copy_safe(ir_node *node, int index) -{ - node_info *info = (node_info *)get_irn_link(node); - if (info != NULL) - return get_copy(node, index); - else - return node; -} +/* Outs of the condition chain (loop inversion). */ +static ir_node **cc_blocks; +/* df/cf edges with def in the condition chain */ +static entry_edge *cond_chain_entries; +/* Array of df loops found in the condition chain. */ +static entry_edge *head_df_loop; +/* Number of blocks in cc */ +static unsigned inversion_blocks_in_cc; + + +/* Cf/df edges leaving the loop. + * Called entries here, as they are used to enter the loop with walkers. */ +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; + +/* Loop operations. */ +typedef enum loop_op_t { + loop_op_inversion, + loop_op_unrolling, + loop_op_peeling +} loop_op_t; -/* Assigns the given array to a nodes node_info */ -static void set_copy_arr(ir_node *n, ir_node **arr) +/* Saves which loop operation to do until after basic tests. */ +static loop_op_t loop_op; + +/* Returns the maximum nodes for the given nest depth */ +static unsigned get_max_nodes_adapted(unsigned depth) { - ((node_info *)get_irn_link(n))->copy = arr; + double perc = 100.0 + (double)opt_params.depth_adaption; + double factor = pow(perc / 100.0, depth); + + return (int)((double)opt_params.max_loop_size * factor); } -/* Assigns a copy with given index to a node. - * Prerequirements are existing node_info and copy array. */ -static void set_copy(ir_node *n, int index, ir_node *copy) +/* Reset nodes link. For use with a walker. */ +static void reset_link(ir_node *node, void *env) { - ((node_info *)get_irn_link(n))->copy[index] = copy; + (void)env; + set_irn_link(node, NULL); } /* Returns 0 if the node or block is not in cur_loop. */ @@ -262,262 +262,14 @@ static unsigned is_in_loop(ir_node *node) return (get_irn_loop(get_block(node)) == cur_loop); } -/* Returns if the given be is an alien edge. - * This is the case when the pred is not in the loop. */ -static unsigned is_alien_edge(ir_node *n, int i) -{ - return(!is_in_loop(get_irn_n(n, i))); -} - +/* 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) { return (is_backedge(n, pos) && is_in_loop(get_irn_n(n, pos))); } -/* Resets block mark for given node. For use with walker */ -static void reset_block_mark(ir_node *node, void * env) -{ - (void) env; - - if (is_Block(node)) - set_Block_mark(node, 0); -} - -static unsigned is_nodes_block_marked(ir_node* node) -{ - if (is_Block(node)) - return get_Block_mark(node); - else - return get_Block_mark(get_block(node)); -} - -/* Returns the number of blocks in a loop. */ -static int get_loop_n_blocks(ir_loop *loop) -{ - int elements, e; - int blocks = 0; - elements = get_loop_n_elements(loop); - - for (e=0; e 1) + ++loop_info.branches; + + if (node_in_loop && !pred_in_loop && loop_head_valid) { + ir_node *cfgpred = get_Block_cfgpred(node, i); + + if (!is_in_loop(cfgpred)) { + DB((dbg, LEVEL_5, "potential head %+F because inloop and pred %+F not inloop\n", + node, pred)); + /* another head? We do not touch this. */ + if (loop_head && loop_head != node) { + loop_head_valid = 0; + } else { + loop_head = node; + } } } } } } -/**/ -static void correct_phis(ir_node *node, void *env) -{ - (void)env; - - if (is_Phi(node) && get_irn_arity(node) == 1) { - ir_node *exch; - ir_node *in[1]; - in[0] = get_irn_n(node, 0); - - exch = new_rd_Phi(get_irn_dbg_info(node), - get_nodes_block(node), 1, in, - get_irn_mode(node)); - - exchange(node, exch); - /* TODO make sure visited is copied */ - } - - -} -/* Adds all nodes pointing into the loop to loop_entries and also finds the loops head */ -static void get_loop_outs(ir_node *node, void *env) +/* Finds all edges with users outside of the loop + * and definition inside the loop. */ +static void get_loop_entries(ir_node *node, void *env) { unsigned node_in_loop, pred_in_loop; int i, arity; @@ -590,26 +358,23 @@ static void get_loop_outs(ir_node *node, void *env) node_in_loop = is_in_loop(node); if (pred_in_loop && !node_in_loop) { - out_edge entry; + entry_edge entry; entry.node = node; entry.pos = i; - ARR_APP1(out_edge, cur_loop_outs, entry); - if (is_Block(node)) { - ++loop_info.cf_outs; - loop_info.cf_out = entry; - } - DB((dbg, LEVEL_5, "loop outs %N\n", node)); + entry.pred = pred; + ARR_APP1(entry_edge, loop_entries, entry); } } } +/* ssa */ static ir_node *ssa_second_def; static ir_node *ssa_second_def_block; /** * Walks the graph bottom up, searching for definitions and creates phis. */ -static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) +static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int first) { int i; int n_cfgpreds; @@ -626,14 +391,14 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) return new_Bad(); } - if (block == ssa_second_def_block) { + if (block == ssa_second_def_block && !first) { DB((dbg, LEVEL_5, "ssa found second definition: use second def %N\n", ssa_second_def)); return ssa_second_def; } /* already processed this block? */ if (irn_visited(block)) { - ir_node *value = get_irn_link(block); + ir_node *value = (ir_node *) get_irn_link(block); DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value)); return value; } @@ -649,7 +414,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block)); - value = search_def_and_create_phis(pred_block, mode); + value = search_def_and_create_phis(pred_block, mode, 0); set_irn_link(block, value); mark_irn_visited(block); @@ -662,13 +427,9 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) in[i] = new_Unknown(mode); phi = new_r_Phi(block, n_cfgpreds, in, mode); - - /* Important: always keep block phi list up to date. */ add_Block_phi(block, phi); - DB((dbg, LEVEL_5, "ssa phi creation: link new phi %N to block %N\n", phi, block)); - set_irn_link(block, phi); mark_irn_visited(block); @@ -677,15 +438,18 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) ir_node *pred_val; ir_node *pred_block = get_Block_cfgpred_block(block, i); assert(pred_block != NULL); - pred_val = search_def_and_create_phis(pred_block, mode); + pred_val = search_def_and_create_phis(pred_block, mode, 0); + assert(pred_val != NULL); DB((dbg, LEVEL_5, "ssa phi pred:phi %N, pred %N\n", phi, pred_val)); set_irn_n(phi, i, pred_val); } + return phi; } + /** * Given a set of values this function constructs SSA-form for the users of the * first value (the users are determined through the out-edges of the value). @@ -702,7 +466,6 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, assert(orig_block && orig_val && second_block && second_val && "no parameter of construct_ssa may be NULL"); - /* no need to do anything */ if (orig_val == second_val) return; @@ -733,12 +496,10 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, if (is_Phi(user)) { ir_node *pred_block = get_Block_cfgpred_block(user_block, j); - newval = search_def_and_create_phis(pred_block, mode); + newval = search_def_and_create_phis(pred_block, mode, 1); } else { - newval = search_def_and_create_phis(user_block, mode); + newval = search_def_and_create_phis(user_block, mode, 1); } - - /* If we get a bad node the user keeps the original in. No second definition needed. */ if (newval != user && !is_Bad(newval)) set_irn_n(user, j, newval); } @@ -747,96 +508,172 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, } -/* Construct ssa for def and all of its copies. - * NOTE: Overwrites links of blocks. -*/ -static ir_node *construct_ssa_n(ir_node *def, ir_node *user, int copies) -{ - ir_graph *irg; - ir_mode *mode; - irg = get_irn_irg(def); - int i, user_arity; - ir_node *newval; +/***** Unrolling Helper Functions *****/ - ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); - inc_irg_visited(current_ir_graph); - mode = get_irn_mode(def); +/* Assign the copy with index nr to node n */ +static void set_unroll_copy(ir_node *n, int nr, ir_node *cp) +{ + unrolling_node_info *info; + assert(nr != 0 && "0 reserved"); - set_irn_link(get_nodes_block(def), def); - mark_irn_visited(get_nodes_block(def)); + info = (unrolling_node_info *)phase_get_irn_data(phase, n); + if (! info) { + ir_node **arr; - for (i = 0; i < copies; ++i) { - ir_node *cp = get_copy(def, i); - ir_node *block = get_nodes_block(cp); - set_irn_link(block, cp); - mark_irn_visited(block); + info = XMALLOCZ(unrolling_node_info); + arr = NEW_ARR_F(ir_node *, unroll_nr); + info->copies = arr; + memset(info->copies, 0, (unroll_nr) * sizeof(ir_node *)); - DB((dbg, LEVEL_5, "ssa mark cp %N of def %N usr %N\n", cp, def, user)); + phase_set_irn_data(phase, n, info); } + /* Original node */ + info->copies[0] = n; - /* TODO BUG BUG */ - newval = user; - user_arity = get_irn_arity(user); - for (i = 0; i < user_arity; ++i) { - ir_node *user_block = get_nodes_block(user); - if (get_irn_n(user, i) != def) - continue; - - DB((dbg, LEVEL_5, "ssa_n found edge of user %N\n", user)); + info->copies[nr] = cp; +} - if (is_Phi(user)) { - ir_node *pred_block = get_Block_cfgpred_block(user_block, i); - newval = search_def_and_create_phis(pred_block, mode); - } else { - newval = search_def_and_create_phis(user_block, mode); - } - /*TODO bads should not happen! */ - if (newval != user) { - DB((dbg, LEVEL_5, "=> ssa_n new in is %N\n", newval)); - set_irn_n(user, i, newval); - /*if (is_Phi(newval) && get_nodes_block(newval)== user_block) { - ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); - return newval; - }*/ - } +/* Returns a nodes copy if it exists, else NULL. */ +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); + if (! info) + return NULL; - /* BREAK, as we found and handled the definition */ - break; + cp = info->copies[nr]; + return cp; +} -#if 0 - if (is_Bad(newval)) { - DB((dbg, LEVEL_5, "=> ssa_n new in is BAD %N in graph %N\n", newval, current_ir_graph)); - add_End_keepalive(get_irg_end(current_ir_graph), newval); - dump_ir_block_graph(current_ir_graph, "-bad"); - assert(0); - } -#endif - } +/***** Inversion Helper Functions *****/ - ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); - return NULL; +/* Sets copy cp of node n. */ +static void set_inversion_copy(ir_node *n, ir_node *cp) +{ + phase_set_irn_data(phase, n, cp); } -/* Returns the number of backedges with or without alien bes. */ -static int get_backedge_n(ir_node *loophead, unsigned with_alien) +/* Getter of copy of n for inversion */ +static ir_node *get_inversion_copy(ir_node *n) { - int i; - int be_n = 0; - int arity = get_irn_arity(loophead); - for (i = 0; i < arity; ++i) { - ir_node *pred = get_irn_n(loophead, i); - if (is_backedge(loophead, i) && (with_alien || is_in_loop(pred))) - ++be_n; - } - return be_n; + ir_node *cp = (ir_node *)phase_get_irn_data(phase, n); + return cp; } -/** - * Returns a raw copy of the given node. - * Attributes are kept/set according to the needs of loop inversion. - */ -static ir_node *copy_node_inversion(ir_node *node) +/* Resets block mark for given node. For use with walker */ +static void reset_block_mark(ir_node *node, void * env) +{ + (void) env; + + if (is_Block(node)) + set_Block_mark(node, 0); +} + +/* 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) +{ + if (is_Block(node)) + return get_Block_mark(node); + else + return get_Block_mark(get_block(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) +{ + 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); + + /* save bes */ + /* Bes are important! + * Another way would be recreating the looptree, + * but after that we cannot distinguish already processed loops + * from not yet processed ones. */ + if (is_Block(n)) { + for(i = 0; i < arity; ++i) { + bes[i] = is_backedge(n, i); + } + bes[i] = new_is_backedge; + } + + for(i = 0; i < arity; ++i) { + ins[i] = get_irn_n(n, i); + } + ins[i] = newnode; + + set_irn_in(n, new_arity, ins); + + /* restore bes */ + if (is_Block(n)) { + for(i = 0; i < new_arity; ++i) { + if (bes[i]) + set_backedge(n, i); + } + } +} + +/* Extends a block by a copy of its pred at pos, + * fixing also the phis in the same way. */ +static void extend_ins_by_copy(ir_node *block, int pos) +{ + ir_node *new_in; + ir_node *phi; + ir_node *pred; + assert(is_Block(block)); + + /* Extend block by copy of definition at 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 block phis by copy of definition at pos */ + for_each_phi(block, phi) { + ir_node *pred, *cp; + + pred = get_irn_n(phi, pos); + cp = get_inversion_copy(pred); + /* If the phis in is not in the condition chain (eg. a constant), + * there is no copy. */ + if (cp == NULL) + new_in = pred; + else + 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); + } +} + +/* Returns the number of blocks backedges. With or without alien bes. */ +static int get_backedge_n(ir_node *block, unsigned with_alien) +{ + int i; + int be_n = 0; + int arity = get_irn_arity(block); + + assert(is_Block(block)); + + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(block, i); + if (is_backedge(block, i) && (with_alien || is_in_loop(pred))) + ++be_n; + } + return be_n; +} + +/* Returns a raw copy of the given node. + * Attributes are kept/set according to the needs of loop inversion. */ +static ir_node *copy_node(ir_node *node) { int i, arity; ir_node *cp; @@ -844,19 +681,16 @@ static ir_node *copy_node_inversion(ir_node *node) cp = exact_copy(node); arity = get_irn_arity(node); + /* Keep backedge info */ for (i = 0; i < arity; ++i) { if (is_backedge(node, i)) set_backedge(cp, i); } - set_inversion_copy(node, cp); - DB((dbg, LEVEL_5, "set copy of %N to cp %N \n", node, cp)); - if (is_Block(cp)) { - /* We may not keep the old macroblock. */ - set_Block_MacroBlock(cp, cp); set_Block_mark(cp, 0); } + return cp; } @@ -864,10 +698,11 @@ static ir_node *copy_node_inversion(ir_node *node) /** * This walker copies all walked nodes. * If the walk_condition is true for a node, it is copied. - * All nodes node_info copy attributes have to be NULL prior to every walk. + * All nodes node_info->copy have to be NULL prior to every walk. + * 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; @@ -882,7 +717,9 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, /* Here we rely on nodestate's copy being initialized with NULL */ DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node)); if (get_inversion_copy(node) == NULL) { - cp = copy_node_inversion(node); + cp = copy_node(node); + set_inversion_copy(node, cp); + DB((dbg, LEVEL_5, "The TEMP copy of %N is created %N\n", node, cp)); } return; @@ -919,7 +756,8 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, /* copy node / finalize temp node */ if (get_inversion_copy(node) == NULL) { /* No temporary copy existent */ - cp = copy_node_inversion(node); + cp = copy_node(node); + set_inversion_copy(node, cp); DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp)); } else { /* temporary copy is existent but without correct ins */ @@ -935,196 +773,143 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, add_Block_phi(cpblock, cp); } - set_irn_loop(cp, set_loop); - /* Keeps phi list of temporary node. */ set_irn_in(cp, ARR_LEN(cpin), cpin); } -/* Creates a new node from a given one, but with custom ins. */ -static ir_node *copy_node_changed( - ir_node *node, ir_node *block, int arity, ir_node **ins, ir_loop *loop) +/** + * This walker copies all walked nodes. + * If the walk_condition is true for a node, it is copied. + * All nodes node_info->copy have to be NULL prior to every walk. + * 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) { + int i; + int arity; ir_node *cp; - DB((dbg, LEVEL_5, "New node from %N in %N block %N arity %d\n", - node, get_irn_irg(node), block, arity)); -#if 0 - if (is_Phi(node)) { - cp = new_rd_Phi(get_irn_dbg_info(node), - block, - arity, - ins, - get_irn_mode(node)); + ir_node **cpin; - } else { -#endif - /* We want to keep phi nodes with arity 1, as it makes rewiring a lot easier. */ - cp = new_ir_node(get_irn_dbg_info(node), - get_irn_irg(node), - block, - get_irn_op(node), - get_irn_mode(node), - arity, - ins); - - /* By any means, keep the blocks phi list up-to-date, - because regaining it would destroy the links. */ - if (is_Phi(cp)) - add_Block_phi(block, cp); -/* TODO */ - if (get_irn_op(node) == get_irn_op(cp)) - copy_node_attr(get_irn_irg(node), node, cp); - - /*new_backedge_info(cp); function removed */ - if (is_Block(cp)) - set_Block_MacroBlock(cp, cp); - - set_irn_loop(cp, loop); - - /* Blocks are copied first, so that future phi nodes populate the phi list. */ - if (is_Block(cp)) - set_Block_phis(cp, NULL); - - DB((dbg, LEVEL_5, "New node %N in %N block %N arity %d\n", - cp, get_irn_irg(cp), block, arity)); - return cp; -} + /** + * break condition and cycle resolver, creating temporary node copies + */ + if (irn_visited(node)) { + /* Here we rely on nodestate's copy being initialized with NULL */ + DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node)); + if (get_unroll_copy(node, copy_index) == NULL) { + ir_node *u; + u = copy_node(node); + set_unroll_copy(node, copy_index, u); + DB((dbg, LEVEL_5, "The TEMP unknown of %N is created %N\n", node, u)); + } + return; + } -/* To be exchangeable, the unknown needs to have proper graph set. */ -static ir_node *new_node_unknown(ir_node *block, ir_mode *mode) -{ - ir_node *new = new_ir_node(NULL, get_irn_irg(block), block, op_Unknown, mode, 0, NULL); - return new; -} + /* Walk */ + mark_irn_visited(node); -/** - * Walker, to copy alle nodes that meet the walk_condition. - * Blocks are copied first, which is important for the creation of the phi lists. - * - */ -static ir_node *copy_walk_n(ir_node *node, walker_condition *walk_condition, int copy_index, int alloc_cp_arr) -{ - int i; - int arity; - unsigned headblock = 0; - ir_node *block, *cp, *new_cp; - ir_node **ins = NULL; + if (!is_Block(node)) { + ir_node *block = get_nodes_block(node); + if (walk_condition(block)) + DB((dbg, LEVEL_5, "walk block %N\n", block)); + copy_walk_n(block, walk_condition, copy_index); + } - if (irn_visited(node)) { - cp = get_copy(node, copy_index); + arity = get_irn_arity(node); + NEW_ARR_A(ir_node *, cpin, arity); - DB((dbg, LEVEL_5, "Visited %N\n", node)); + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(node, i); - if (cp != NULL) { - DB((dbg, LEVEL_5, "Visited. Return copy %N\n", cp)); - return cp; + if (walk_condition(pred)) { + DB((dbg, LEVEL_5, "walk node %N\n", pred)); + copy_walk_n(pred, walk_condition, copy_index); + cpin[i] = get_unroll_copy(pred, copy_index); + } else { + cpin[i] = pred; } + } - if (!is_Block(node)) { - ir_node *unknown = new_node_unknown( - get_nodes_block(node), - get_irn_mode(node)); - DB((dbg, LEVEL_5, " #### Create Unknown %N for %N\n", unknown, node)); - set_copy(node, copy_index, unknown); - return unknown; - } + /* copy node / finalize temp node */ + cp = get_unroll_copy(node, copy_index); + if (cp == NULL || is_Unknown(cp)) { + cp = copy_node(node); + set_unroll_copy(node, copy_index, cp); + DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp)); } else { - DB((dbg, LEVEL_5, "Walk %N\n", node)); - mark_irn_visited(node); - - /* Allocate array of copies */ - if (alloc_cp_arr > 0) { - ir_node **arr = NEW_ARR_F(ir_node *, alloc_cp_arr); - alloc_node_info(node); - for (i = 0; i < alloc_cp_arr; ++i) - arr[i] = NULL; - set_copy_arr(node, arr); - } + /* temporary copy is existent but without correct ins */ + cp = get_unroll_copy(node, copy_index); + DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp)); } - block = NULL; if (!is_Block(node)) { - ir_node *orig_block = get_nodes_block(node); - DB((dbg, LEVEL_5, "current node: %N about to walk block %N\n", node, orig_block)); - /* Check walk_condition for blocks not necessary */ + ir_node *cpblock = get_unroll_copy(get_nodes_block(node), copy_index); - if (orig_block == loop_head && is_Phi(node)) - headblock = 1; - - block = copy_walk_n(orig_block, walk_condition, copy_index, alloc_cp_arr); - DB((dbg, LEVEL_5, "current node: %N block %N blocks copy %N\n", - node, orig_block, block)); - } else { - if (node == loop_head) - headblock = 1; + set_nodes_block(cp, cpblock ); + if (is_Phi(cp)) + add_Block_phi(cpblock, cp); } + /* Keeps phi list of temporary node. */ + set_irn_in(cp, ARR_LEN(cpin), cpin); +} + +/* Removes alle Blocks with non marked predecessors from the condition chain. */ +static void unmark_not_allowed_cc_blocks(void) +{ + size_t blocks = ARR_LEN(cc_blocks); + size_t i; - arity = get_irn_arity(node); + for(i = 0; i < blocks; ++i) { + ir_node *block = cc_blocks[i]; + int a; + int arity = get_irn_arity(block); - if (headblock) { - /* Headblock and headblock-phi case */ - int in_c = 0; - DB((dbg, LEVEL_5, "Headblock/Phi from headblock\n")); - NEW_ARR_A(ir_node *, ins, unroll_arity); + /* Head is an exception. */ + if (block == loop_head) + continue; - for (i = 0; i < arity; ++i) { - ir_node *ret; - ir_node *pred = get_irn_n(node, i); - if (is_backedge(loop_head, i)) { - if (walk_condition(pred)) { - ret = copy_walk_n(pred, walk_condition, copy_index, alloc_cp_arr); - DB((dbg, LEVEL_5, "in %d = %N walked\n", i, ret)); - } else { - ret = pred; - DB((dbg, LEVEL_5, "in %d = %N not walked\n", i, ret)); - } - ins[in_c++] = ret; - } - } - arity = unroll_arity; - } else { - /* Normal case */ - NEW_ARR_A(ir_node *, ins, arity); + for(a = 0; a < arity; ++a) { + if (! is_nodes_block_marked(get_irn_n(block, a))) { + set_Block_mark(block, 0); + --inversion_blocks_in_cc; + DB((dbg, LEVEL_5, "Removed %N from cc (blocks in cc %d)\n", + block, inversion_blocks_in_cc)); - for (i = 0; i < arity; ++i) { - ir_node *ret; - ir_node *pred = get_irn_n(node, i); - if (walk_condition(pred)) { - ret = copy_walk_n(pred, walk_condition, copy_index, alloc_cp_arr); - DB((dbg, LEVEL_5, "in %d = %N walked\n", i, ret)); - } else { - ret = pred; - DB((dbg, LEVEL_5, "in %d = %N not walked\n", i, ret)); + break; } - ins[i] = ret; } } +} - /* NOW, after the walk, we may check if the blocks copy is already present. */ - cp = get_copy(node, copy_index); - if (cp != NULL && !is_Unknown(cp)) { - DB((dbg, LEVEL_5, "Must be Block %N copy is already present\n", node, cp)); - assert(is_Block(cp) && - "sanity: The copy should have been a block."); - return cp; - } +/* Unmarks all cc blocks using cc_blocks except head. + * TODO: invert head for unrolling? */ +static void unmark_cc_blocks(void) +{ + size_t blocks = ARR_LEN(cc_blocks); + size_t i; - new_cp = copy_node_changed(node, block, arity, ins, cur_loop); - set_copy(node, copy_index, new_cp); + for(i = 0; i < blocks; ++i) { + ir_node *block = cc_blocks[i]; - if (cp != NULL && is_Unknown(cp)) { - DB((dbg, LEVEL_5, "Found unknown %N in %N now exchanged by %N in %N\n", - cp, get_irn_irg(cp), new_cp, get_irn_irg(new_cp))); - exchange(cp, new_cp); + /* TODO Head is an exception. */ + /*if (block != loop_head)*/ + set_Block_mark(block, 0); } - return new_cp; + /*inversion_blocks_in_cc = 1;*/ + inversion_blocks_in_cc = 0; + + /* invalidate */ + loop_info.cc_size = 0; } /** * Populates head_entries with (node, pred_pos) tuple - * whereas the node's pred at pred_pos is in the head but not the node itself. - * Head and condition chain blocks must be marked. + * whereas the node's pred at pred_pos is in the cc but not the node itself. + * Also finds df loops inside the cc. + * Head and condition chain blocks have been marked previously. */ static void get_head_outs(ir_node *node, void *env) { @@ -1132,113 +917,137 @@ static void get_head_outs(ir_node *node, void *env) int arity = get_irn_arity(node); (void) env; - DB((dbg, LEVEL_5, "get head entries %N \n", node)); - for (i = 0; i < arity; ++i) { - /* node is not in the head, but the predecessor is. - * (head or loop chain nodes are marked) */ - - DB((dbg, LEVEL_5, "... ")); - DB((dbg, LEVEL_5, "node %N marked %d (0) pred %d marked %d (1) \n", - node, is_nodes_block_marked(node), i, - is_nodes_block_marked(get_irn_n(node, i)))); - if (!is_nodes_block_marked(node) && is_nodes_block_marked(get_irn_n(node, i))) { - out_edge entry; + entry_edge entry; entry.node = node; entry.pos = i; - ARR_APP1(out_edge, cur_head_outs, entry); + /* Saving also predecessor seems redundant, but becomes + * necessary when changing position of it, before + * dereferencing it.*/ + entry.pred = get_irn_n(node, i); + ARR_APP1(entry_edge, cur_head_outs, entry); + } + } + + arity = get_irn_arity(loop_head); - if (is_in_loop(node) && is_Block(node)) { - loop_info.new_loop_head = node; - DB((dbg, LEVEL_5, " SET NEW LOOPHEAD to %N\n", node)); + /* Find df loops inside the cc */ + if (is_Phi(node) && get_nodes_block(node) == loop_head) { + for (i = 0; i < arity; ++i) { + if (is_own_backedge(loop_head, i)) { + if (is_nodes_block_marked(get_irn_n(node, i))) { + entry_edge entry; + entry.node = node; + entry.pos = i; + entry.pred = get_irn_n(node, i); + ARR_APP1(entry_edge, head_df_loop, entry); + DB((dbg, LEVEL_5, "Found incc assignment node %N @%d is pred %N, graph %N %N\n", + node, i, entry.pred, current_ir_graph, get_irg_start_block(current_ir_graph))); + } } } } } /** - * Find condition chains, and add them to be inverted + * Find condition chains, and add them to be inverted. * A block belongs to the chain if a condition branches out of the loop. + * (Some blocks need to be removed once again.) * Returns 1 if the given block belongs to the condition chain. */ -static unsigned find_condition_chains(ir_node *block) +static unsigned find_condition_chain(ir_node *block) { - const ir_edge_t *edge; + const ir_edge_t *edge; unsigned mark = 0; - int nodes_n = 0; + unsigned has_be = 0; + unsigned jmp_only; + unsigned nodes_n = 0; + + mark_irn_visited(block); DB((dbg, LEVEL_5, "condition_chains for block %N\n", block)); - /* Collect all outs, including keeps. */ + /* Get node count */ foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) { ++nodes_n; } - /* Leave at least one block as body. */ - if (head_inversion_node_count + nodes_n > inversion_head_node_limit - || head_inversion_block_count + 1 == loop_info.blocks) { + /* Check if node count would exceed maximum cc size. + * TODO + * This is not optimal, as we search depth-first and break here, + * continuing with another subtree. */ + if (loop_info.cc_size + nodes_n > opt_params.max_cc_size) { set_Block_mark(block, 0); - return 0; } - /* First: check our successors, - * and add all of them, which are outside of the loop, to the list */ - foreach_block_succ(block, edge) { - ir_node *src = get_edge_src_irn( edge ); - int pos = get_edge_src_pos( edge ); + /* 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_in_loop(src)) { - out_edge entry; + /* Check cf outs if one is leaving the loop, + * or if this node has a backedge. */ + foreach_block_succ(block, edge) { + ir_node *src = get_edge_src_irn(edge); + int pos = get_edge_src_pos(edge); + if (! is_in_loop(src)) mark = 1; - entry.node = src; - entry.pos = pos; - ARR_APP1(out_edge, cond_chain_entries, entry); - mark_irn_visited(src); + + /* Inverting blocks with backedge outs leads to a cf edge + * from the inverted head, into the inverted head (skipping the body). + * As the body becomes the new loop head, + * 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; + break; } } - if (mark == 0) { - set_Block_mark(block, 0); - return 0; - } else { + /* We need all predecessors to already belong to the condition chain. + * Example of wrong case: * == in cc + * + * Head* ,--. + * /| \ B | + * / A* B / | + * / /\ / ? | + * / C* => D | + * / 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) { set_Block_mark(block, 1); - ++head_inversion_block_count; + ++inversion_blocks_in_cc; + loop_info.cc_size += nodes_n; DB((dbg, LEVEL_5, "block %N is part of condition chain\n", block)); - head_inversion_node_count += nodes_n; + ARR_APP1(ir_node *, cc_blocks, block); + } else { + set_Block_mark(block, 0); } - /* Second: walk all successors, - * and add them to the list if they are not part of the chain */ foreach_block_succ(block, edge) { - unsigned inchain; ir_node *src = get_edge_src_irn( edge ); - int pos = get_edge_src_pos( edge ); - - /* already done */ - if (!is_in_loop( src ) || irn_visited(src)) { - continue; - } - - mark_irn_visited(src); - DB((dbg, LEVEL_5, "condition chain walk %N\n", src)); - inchain = find_condition_chains(src); - /* if successor is not part of chain we need to collect its outs */ - if (!inchain) { - out_edge entry; - entry.node = src; - entry.pos = pos; - ARR_APP1(out_edge, cond_chain_entries, entry); - } + if (is_in_loop(src) && ! irn_visited(src)) + find_condition_chain(src); } + return mark; } /** - * Rewires the copied condition chain. Removes backedges. + * Rewires the copied condition chain. Removes backedges * as this condition chain is prior to the loop. * Copy of loop_head must have phi list and old (unfixed) backedge info of the loop head. * (loop_head is already fixed, we cannot rely on it.) @@ -1249,10 +1058,10 @@ 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); + int arity = get_irn_arity(head_cp); + int backedges = get_backedge_n(head_cp, 0); + int new_arity = arity - backedges; int pos; int i; @@ -1293,44 +1102,9 @@ static void fix_copy_inversion(void) DEL_ARR_F(phis); } -/**/ -static ir_node *fix_inner_cc_definitions(ir_node *phi, ir_node *pred) -{ - int i; - ir_node *head_phi; - ir_node **head_phi_ins; - ir_node *new_loop_head = loop_info.new_loop_head; - int new_loop_head_arity = get_irn_arity(new_loop_head); - DB((dbg, LEVEL_5, "NEW HEAD %N arity %d\n", new_loop_head, new_loop_head_arity)); - - NEW_ARR_A(ir_node *, head_phi_ins, new_loop_head_arity); - - for(i = 0; i < new_loop_head_arity; ++i) { - /* Rely on correct backedge info for the new loop head - * is set by extend_ins_by_copy. */ - if(is_nodes_block_marked(get_irn_n(new_loop_head, i))) { - head_phi_ins[i] = pred; - } else { - head_phi_ins[i] = get_inversion_copy(pred); - } - DB((dbg, LEVEL_5, "NEW HEAD %N in %N %N\n", new_loop_head, head_phi_ins[i], current_ir_graph)); - } - - head_phi= new_r_Phi(new_loop_head, - new_loop_head_arity, - head_phi_ins, - get_irn_mode(phi)); - - add_Block_phi(new_loop_head, head_phi); - - DB((dbg, LEVEL_5, "fix inner cc definitions: new head %N has new phi %N from cc phi %N @%N\n", - new_loop_head, head_phi, phi, pred)); - - return head_phi; -} - -/* Puts the original condition chain at the end of the loop, subsequently to the body. +/* Puts the original condition chain at the end of the loop, + * subsequently to the body. * Relies on block phi list and correct backedges. */ static void fix_head_inversion(void) @@ -1339,9 +1113,9 @@ 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; + int arity = get_irn_arity(loop_head); + int backedges = get_backedge_n(loop_head, 0); + int new_arity = backedges; int pos; int i; @@ -1360,31 +1134,33 @@ static void fix_head_inversion(void) for_each_phi(loop_head, phi) { ir_node *new_phi; + DB((dbg, LEVEL_5, "Fixing phi %N of loop head\n", phi)); NEW_ARR_A(ir_node *, ins, new_arity); pos = 0; - for(i = 0; i < arity; ++i) { + for (i = 0; i < arity; ++i) { ir_node *pred = get_irn_n(phi, i); if (is_own_backedge(loop_head, i)) { - DB((dbg, LEVEL_5, " !!! PHI not useful %N\n", phi)); - - /* If definition is in the condition chain, - * we need to create a phi in the new loop head */ - if (is_nodes_block_marked(pred)) - ins[pos++] = fix_inner_cc_definitions(phi, pred); - else + /* If assignment is in the condition chain, + * we need to create a phi in the new loop head. + * This can only happen for df, not cf. See find_condition_chains. */ + /*if (is_nodes_block_marked(pred)) { ins[pos++] = pred; + } else {*/ + ins[pos++] = pred; + } } + new_phi = new_rd_Phi(get_irn_dbg_info(phi), new_head, new_arity, ins, get_irn_mode(phi)); ARR_APP1(ir_node *, phis, new_phi); - DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N\n", phi, new_phi)); + DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N (pos %d)\n", phi, new_phi, pos )); } pos = 0; @@ -1401,9 +1177,9 @@ static void fix_head_inversion(void) } /* Does the loop inversion. */ -static void inversion_walk(out_edge *head_entries) +static void inversion_walk(entry_edge *head_entries) { - int i; + size_t i; /* * The order of rewiring bottom-up is crucial. @@ -1416,7 +1192,7 @@ static void inversion_walk(out_edge *head_entries) inc_irg_visited(current_ir_graph); for (i = 0; i < ARR_LEN(head_entries); ++i) { - out_edge entry = head_entries[i]; + entry_edge entry = head_entries[i]; ir_node *pred = get_irn_n(entry.node, entry.pos); DB((dbg, LEVEL_5, "\nInit walk block %N\n", pred)); @@ -1427,9 +1203,9 @@ static void inversion_walk(out_edge *head_entries) ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); /* 2. Extends the head control flow successors ins - * by the definitions of the copied head node. */ + * with the definitions of the copied head node. */ for (i = 0; i < ARR_LEN(head_entries); ++i) { - out_edge head_out = head_entries[i]; + entry_edge head_out = head_entries[i]; if (is_Block(head_out.node)) extend_ins_by_copy(head_out.node, head_out.pos); @@ -1438,18 +1214,17 @@ static void inversion_walk(out_edge *head_entries) /* 3. construct_ssa for users of definitions in the condition chain, * as there is now a second definition. */ for (i = 0; i < ARR_LEN(head_entries); ++i) { - out_edge head_out = head_entries[i]; + entry_edge head_out = head_entries[i]; + /* Ignore keepalives */ if (is_End(head_out.node)) continue; - ir_node *is_in_cc = get_nodes_block(get_irn_n(head_out.node, head_out.pos)); - /* Construct ssa for definitions in the condition chain. */ - /* TODO Why do we need the check for is_in_cc? All definitions should be there... */ - if (!is_Block(head_out.node) && is_nodes_block_marked(is_in_cc)) { + /* Construct ssa for assignments in the condition chain. */ + if (!is_Block(head_out.node)) { ir_node *pred, *cppred, *block, *cpblock; - pred = get_irn_n(head_out.node, head_out.pos); + pred = head_out.pred; cppred = get_inversion_copy(pred); block = get_nodes_block(pred); cpblock = get_nodes_block(cppred); @@ -1457,64 +1232,156 @@ static void inversion_walk(out_edge *head_entries) } } - /* 4. Remove the ins which are no backedges from the original condition chain, - * as the cc is now subsequently to the body. */ + /* + * If there is an assignment in the condition chain + * with a user also in the condition chain, + * the dominance frontier is in the new loop head. + * The dataflow loop is completely in the condition chain. + * Goal: + * To be wired: >| + * + * | ,--. | + * Phi_cp | | copied condition chain + * >| | | | + * >| ?__/ | + * >| ,-. + * Phi* | | new loop head with newly created phi. + * | | + * Phi | | original, inverted condition chain + * | | | + * ?__/ | + * + */ + for (i = 0; i < ARR_LEN(head_df_loop); ++i) { + entry_edge head_out = head_df_loop[i]; + + /* Construct ssa for assignments in the condition chain. */ + ir_node *pred, *cppred, *block, *cpblock; + + pred = head_out.pred; + cppred = get_inversion_copy(pred); + assert(cppred && pred); + block = get_nodes_block(pred); + cpblock = get_nodes_block(cppred); + construct_ssa(block, pred, cpblock, cppred); + } + + /* 4. Remove the ins which are no backedges from the original condition chain + * as the cc is now subsequent to the body. */ fix_head_inversion(); /* 5. Remove the backedges of the copied condition chain, - * because it is going to be the new 'head' in advance to the loop */ + * because it is going to be the new 'head' in advance to the loop. */ fix_copy_inversion(); + } -/* Analyse loop, if inversion is possible or reasonable. Then do the inversion. */ +/* Performs loop inversion of cur_loop if possible and reasonable. */ static void loop_inversion(void) { + 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; + + /* Depth of 0 is the procedure and 1 a topmost loop. */ + loop_depth = get_loop_depth(cur_loop) - 1; + + /* Calculating in per mil. */ + max_loop_nodes_adapted = get_max_nodes_adapted(loop_depth); - inversion_head_node_limit = INT_MAX; + 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)) + 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); + /* no RETURN */ + /* Adaption might change it */ + } + + /* Limit processing to loops smaller than given parameter. */ + 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); + 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); + return; + } +#endif + + /*inversion_head_node_limit = INT_MAX;*/ ir_reserve_resources(current_ir_graph, 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); - loop_info.blocks = get_loop_n_blocks(cur_loop); - cond_chain_entries = NEW_ARR_F(out_edge, 0); + /*loop_info.blocks = get_loop_n_blocks(cur_loop);*/ + cond_chain_entries = NEW_ARR_F(entry_edge, 0); + head_df_loop = NEW_ARR_F(entry_edge, 0); - head_inversion_node_count = 0; - head_inversion_block_count = 0; - - set_Block_mark(loop_head, 1); - mark_irn_visited(loop_head); + /*head_inversion_node_count = 0;*/ + 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); + /* 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); - /* Search for condition chains. */ - find_condition_chains(loop_head); + unmark_not_allowed_cc_blocks(); + DEL_ARR_F(cc_blocks); - DB((dbg, LEVEL_3, "Loop contains %d blocks.\n", loop_info.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); - if (loop_info.blocks < 2) { do_inversion = 0; - DB((dbg, LEVEL_3, - "Loop contains %d (less than 2) blocks => No Inversion done.\n", - loop_info.blocks)); + + /* 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 (head_inversion_block_count < 1) { + if (inversion_blocks_in_cc < 1) { do_inversion = 0; DB((dbg, LEVEL_3, "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n", - head_inversion_block_count)); + inversion_blocks_in_cc)); } if (do_inversion) { - cur_head_outs = NEW_ARR_F(out_edge, 0); + 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); @@ -1523,425 +1390,1381 @@ static void loop_inversion(void) inversion_walk(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? */ + /* TODO are they? Depends on set_irn_in and set_irn_n exchange and new_node. */ set_irg_outs_inconsistent(current_ir_graph); + + count_stats(stats.inverted); } /* free */ phase_free(phase); DEL_ARR_F(cond_chain_entries); + DEL_ARR_F(head_df_loop); + ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); } -/** - * Rewire floating copies of the current loop. - */ -static void place_copies(int copies) +/* Fix the original loop_heads ins for invariant unrolling case. */ +static void unrolling_fix_loop_head_inv(void) { - ir_node *loophead = loop_head; - int headarity = get_irn_arity(loophead); + ir_node *ins[2]; ir_node *phi; - int i, pos, c; - - pos = 0; - /* Append the copies to the existing loop. */ - for (i = 0; i < headarity; ++i) { - /* Build unrolled loop top down */ - if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) { - for (c = 0; c < copies; ++c) { - ir_node *upper_head; - ir_node *lower_head = get_copy(loophead, c); - ir_node *upper_pred; - - if (c == 0) { - upper_head = loophead; - upper_pred = get_irn_n(loophead, i); - } else { - upper_head = get_copy(loophead, c - 1); - upper_pred = get_copy_safe(get_irn_n(loophead, i), c - 1); - } - set_irn_n(lower_head, pos, upper_pred); - for_each_phi(loophead, phi) { - ir_node *lower_phi, *upper_phi, *upper_pred_phi; - lower_phi = get_copy(phi, c); - if (c == 0) { - upper_phi = phi; - upper_pred_phi = get_irn_n(phi, i); - } else { - upper_phi = get_copy(phi, c - 1); - upper_pred_phi = get_copy_safe(get_irn_n(phi, i), c - 1); - } + ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, 0); + ir_node *head_pred = get_irn_n(loop_head, loop_info.be_src_pos); + ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1); - DB((dbg, LEVEL_5, "Rewire %N @%d to %N\n", - lower_phi, pos, upper_pred_phi)); + /* Original loop_heads ins are: + * duff block and the own backedge */ - /* Relying on phi nodes with 1 in to be present. */ - assert(is_Phi(lower_phi)); + ins[0] = loop_condition; + ins[1] = proj; + set_irn_in(loop_head, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of block loophead %N to pred %N and duffs entry %N \n" , loop_head, ins[0], ins[1])); -/* Do not fix phis here. Chained phis will cause a defective copy array. */ -#if 0 - if (get_irn_arity(lower_phi) == 1) { - ir_node *single_in[1]; - ir_node *cp; - single_in[0] = upper_pred_phi; - - cp = new_rd_Phi(get_irn_dbg_info(lower_phi), - get_nodes_block(lower_phi), 1, single_in, - get_irn_mode(lower_phi)); + for_each_phi(loop_head, phi) { + ir_node *pred = get_irn_n(phi, loop_info.be_src_pos); + /* TODO we think it is a phi, but for Mergesort it is not the case.*/ - set_copy(phi, c, cp); - exchange(lower_phi, cp); - } else -#endif - set_irn_n(lower_phi, pos, upper_pred_phi); + ir_node *last_pred = get_unroll_copy(pred, unroll_nr - 1); - } - } - ++pos; - /* Fix the topmost loop heads backedges. */ - set_irn_n(loophead, i, get_copy(get_irn_n(loophead, i), copies - 1)); - for_each_phi(loophead, phi) { - ir_node *last_cp = get_copy_safe(get_irn_n(phi, i), copies - 1); - set_irn_n(phi, i, last_cp); - } - } + ins[0] = last_pred; + ins[1] = (ir_node*)get_irn_link(phi); + set_irn_in(phi, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of loophead phi %N to pred %N and duffs entry %N \n" , phi, ins[0], ins[1])); } } -/* Copies the cur_loop */ -static void copy_loop(out_edge *cur_loop_outs, int copies) +/* Removes previously created phis with only 1 in. */ +static void correct_phis(ir_node *node, void *env) { - int i, c; - unroll_arity = get_backedge_n(loop_head, 0); + (void)env; - ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); + if (is_Phi(node) && get_irn_arity(node) == 1) { + ir_node *exch; + ir_node *in[1]; - /* copy loop */ - for (c = 0; c < copies; ++c) { + in[0] = get_irn_n(node, 0); - inc_irg_visited(current_ir_graph); + exch = new_rd_Phi(get_irn_dbg_info(node), + get_nodes_block(node), 1, in, + get_irn_mode(node)); - DB((dbg, LEVEL_5, " ### Copy_loop copy n: %d ###\n", c)); - for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) { - out_edge entry = cur_loop_outs[i]; - ir_node *pred = get_irn_n(entry.node, entry.pos); + exchange(node, exch); + } +} + +/* Unrolling: Rewire floating copies. */ +static void place_copies(int copies) +{ + ir_node *loophead = loop_head; + size_t i; + int c; + int be_src_pos = loop_info.be_src_pos; + + /* Serialize loops by fixing their head ins. + * Processed are the copies. + * The original loop is done after that, to keep backedge infos. */ + for (c = 0; c < copies; ++c) { + ir_node *upper = get_unroll_copy(loophead, c); + ir_node *lower = get_unroll_copy(loophead, c + 1); + ir_node *phi; + ir_node *topmost_be_block = get_nodes_block(get_irn_n(loophead, be_src_pos)); + + /* Important: get the preds first and then their copy. */ + ir_node *upper_be_block = get_unroll_copy(topmost_be_block, c); + ir_node *new_jmp = new_r_Jmp(upper_be_block); + DB((dbg, LEVEL_5, " place_copies upper %N lower %N\n", upper, lower)); + + DB((dbg, LEVEL_5, "topmost be block %N \n", topmost_be_block)); + + if (loop_info.unroll_kind == constant) { + ir_node *ins[1]; + ins[0] = new_jmp; + set_irn_in(lower, 1, ins); + + for_each_phi(loophead, phi) { + ir_node *topmost_def = get_irn_n(phi, be_src_pos); + ir_node *upper_def = get_unroll_copy(topmost_def, c); + ir_node *lower_phi = get_unroll_copy(phi, c + 1); + + /* It is possible, that the value used + * in the OWN backedge path is NOT defined in this loop. */ + if (is_in_loop(topmost_def)) + ins[0] = upper_def; + else + ins[0] = topmost_def; + + set_irn_in(lower_phi, 1, ins); + /* Need to replace phis with 1 in later. */ + } + } else { + /* Invariant case */ + /* Every node has 2 ins. One from the duff blocks + * and one from the previously unrolled loop. */ + ir_node *ins[2]; + /* Calculate corresponding projection of mod result for this copy c */ + ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, unroll_nr - c - 1); + DB((dbg, LEVEL_4, "New duff proj %N\n" , proj)); + + ins[0] = new_jmp; + ins[1] = proj; + set_irn_in(lower, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of Block %N to pred %N and duffs entry %N \n" , lower, ins[0], ins[1])); + + for_each_phi(loophead, phi) { + ir_node *topmost_phi_pred = get_irn_n(phi, be_src_pos); + ir_node *upper_phi_pred; + ir_node *lower_phi; + ir_node *duff_phi; + + lower_phi = get_unroll_copy(phi, c + 1); + duff_phi = (ir_node*)get_irn_link(phi); + DB((dbg, LEVEL_4, "DD Link of %N is %N\n" , phi, duff_phi)); + + /* */ + if (is_in_loop(topmost_phi_pred)) { + upper_phi_pred = get_unroll_copy(topmost_phi_pred, c); + } else { + upper_phi_pred = topmost_phi_pred; + } + + ins[0] = upper_phi_pred; + ins[1] = duff_phi; + set_irn_in(lower_phi, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of %N to pred %N and duffs entry %N \n" , lower_phi, ins[0], ins[1])); + } + } + } + + /* Reconnect last copy. */ + for (i = 0; i < ARR_LEN(loop_entries); ++i) { + entry_edge edge = loop_entries[i]; + /* Last copy is at the bottom */ + ir_node *new_pred = get_unroll_copy(edge.pred, copies); + set_irn_n(edge.node, edge.pos, new_pred); + } + + /* Fix original loops head. + * Done in the end, as ins and be info were needed before. */ + if (loop_info.unroll_kind == constant) { + ir_node *phi; + ir_node *head_pred = get_irn_n(loop_head, be_src_pos); + ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1); - copy_walk_n(pred, is_in_loop, c, c ? 0 : copies); + set_irn_n(loop_head, loop_info.be_src_pos, loop_condition); + + for_each_phi(loop_head, phi) { + 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)) + last_pred = get_unroll_copy(pred, copies); + else + last_pred = pred; + set_irn_n(phi, be_src_pos, last_pred); + } + + } else { + unrolling_fix_loop_head_inv(); + } +} + +/* Copies the cur_loop several times. */ +static void copy_loop(entry_edge *cur_loop_outs, int copies) +{ + 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); + + DB((dbg, LEVEL_5, " ### Copy_loop copy nr: %d ###\n", c)); + for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) { + entry_edge entry = cur_loop_outs[i]; + ir_node *pred = get_irn_n(entry.node, entry.pos); + + copy_walk_n(pred, is_in_loop, c + 1); } } ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); } -/**/ -static void create_duffs_device(int unroll_number) + +/* Creates a new phi from the given phi node omitting own bes, + * using be_block as supplier of backedge informations. */ +static ir_node *clone_phis_sans_bes(ir_node *phi, ir_node *be_block, ir_node *dest_block) +{ + ir_node **ins; + int arity = get_irn_arity(phi); + int i, c = 0; + ir_node *newphi; + + assert(get_irn_arity(phi) == get_irn_arity(be_block)); + assert(is_Phi(phi)); + + ins = NEW_ARR_F(ir_node *, arity); + for (i = 0; i < arity; ++i) { + if (! is_own_backedge(be_block, i)) { + ins[c] = get_irn_n(phi, i); + ++c; + } + } + + newphi = new_r_Phi(dest_block, c, ins, get_irn_mode(phi)); + + set_irn_link(phi, newphi); + DB((dbg, LEVEL_4, "Linking for duffs device %N to %N\n", phi, newphi)); + + return newphi; +} + +/* Creates a new block from the given block node omitting own bes, + * using be_block as supplier of backedge informations. */ +static ir_node *clone_block_sans_bes(ir_node *node, ir_node *be_block) { - (void)unroll_number; + ir_node **ins; + int arity = get_irn_arity(node); + int i, c = 0; + + assert(get_irn_arity(node) == get_irn_arity(be_block)); + assert(is_Block(node)); + + NEW_ARR_A(ir_node *, ins, arity); + for (i = 0; i < arity; ++i) { + if (! is_own_backedge(be_block, i)) { + ins[c] = get_irn_n(node, i); + ++c; + } + } + + return new_Block(c, ins); +} + +/* Creates a structure to calculate absolute value of node op. + * Returns mux node with absolute value. */ +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 *minus_op = new_r_Minus(block, op, mode); + ir_node *mux = new_r_Mux(block, cond, op, minus_op, mode); + + return mux; } -#if 1 -static unsigned is_loop_invariant_val(ir_node *node) +/* Creates blocks for duffs device, using previously obtained + * informations about the iv. + * TODO split */ +static void create_duffs_block(void) +{ + ir_mode *mode; + + ir_node *block1, *count_block, *duff_block; + ir_node *ems, *ems_mod, *ems_div, *ems_mod_proj, *cmp_null, + *cmp_proj, *ems_mode_cond, *x_true, *x_false, *const_null; + ir_node *true_val, *false_val; + ir_node *ins[2]; + + ir_node *duff_mod, *proj, *cond; + + ir_node *count, *correction, *unroll_c; + ir_node *cmp_bad_count, *good_count, *bad_count, *count_phi, *bad_count_neg; + ir_node *phi; + + mode = get_irn_mode(loop_info.end_val); + const_null = new_Const(get_mode_null(mode)); + + /* TODO naming + * 1. Calculate first approach to count. + * Condition: (end - start) % step == 0 */ + block1 = clone_block_sans_bes(loop_head, loop_head); + DB((dbg, LEVEL_4, "Duff block 1 %N\n", block1)); + + /* Create loop entry phis in first duff block + * as it becomes the loops preheader */ + for_each_phi(loop_head, phi) { + /* Returns phis pred if phi would have arity 1*/ + ir_node *new_phi = clone_phis_sans_bes(phi, loop_head, block1); + + DB((dbg, LEVEL_4, "HEAD %N phi %N\n", loop_head, phi)); + DB((dbg, LEVEL_4, "BLOCK1 %N phi %N\n", block1, new_phi)); + } + + ems = new_r_Sub(block1, loop_info.end_val, loop_info.start_val, + get_irn_mode(loop_info.end_val)); + DB((dbg, LEVEL_4, "BLOCK1 sub %N\n", ems)); + + + ems = new_Sub(loop_info.end_val, loop_info.start_val, + get_irn_mode(loop_info.end_val)); + + 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_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); + cmp_proj = new_r_Proj(cmp_null, mode_b, pn_Cmp_Eq); + ems_mode_cond = new_r_Cond(block1, cmp_proj); + + + /* ems % step == 0 */ + x_true = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_true); + /* ems % step != 0 */ + x_false = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_false); + + /* 2. Second block. + * Assures, duffs device receives a valid count. + * Condition: + * decreasing: count < 0 + * increasing: count > 0 + */ + ins[0] = x_true; + ins[1] = x_false; + + count_block = new_Block(2, ins); + DB((dbg, LEVEL_4, "Duff block 2 %N\n", count_block)); + + + /* Increase loop-taken-count depending on the loop condition + * uses the latest iv to compare to. */ + if (loop_info.latest_value == 1) { + /* ems % step == 0 : +0 */ + true_val = new_Const(get_mode_null(mode)); + /* ems % step != 0 : +1 */ + false_val = new_Const(get_mode_one(mode)); + } else { + ir_tarval *tv_two = new_tarval_from_long(2, mode); + /* ems % step == 0 : +1 */ + true_val = new_Const(get_mode_one(mode)); + /* ems % step != 0 : +2 */ + false_val = new_Const(tv_two); + } + + ins[0] = true_val; + ins[1] = false_val; + + correction = new_r_Phi(count_block, 2, ins, mode); + + 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), + * we may take the loop once (tail-contr.) and leave it + * to the existing condition, to break; */ + + /* 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); + } else { + bad_count_neg = new_r_Proj(cmp_bad_count, mode_b, pn_Cmp_Gt); + } + + bad_count_neg = new_r_Cond(count_block, bad_count_neg); + good_count = new_Proj(bad_count_neg, mode_X, pn_Cond_true); + bad_count = new_Proj(ems_mode_cond, mode_X, pn_Cond_false); + + /* 3. Duff Block + * Contains module to decide which loop to start from. */ + + ins[0] = good_count; + ins[1] = bad_count; + duff_block = new_Block(2, ins); + DB((dbg, LEVEL_4, "Duff block 3 %N\n", duff_block)); + + /* Get absolute value */ + ins[0] = new_Abs(count, mode); + /* Manually feed the aforementioned count = 1 (bad case)*/ + ins[1] = new_Const(get_mode_one(mode)); + count_phi = new_r_Phi(duff_block, 2, ins, mode); + + unroll_c = new_Const(new_tarval_from_long((long)unroll_nr, mode)); + + /* count % unroll_nr */ + duff_mod = new_r_Mod(duff_block, + new_NoMem(), + count_phi, + unroll_c, + mode, + op_pin_state_pinned); + + + proj = new_Proj(duff_mod, mode, pn_Mod_res); + /* condition does NOT create itself in the block of the proj! */ + cond = new_r_Cond(duff_block, proj); + + loop_info.duff_cond = cond; +} + +/* Returns 1 if given node is not in loop, + * or if it is a phi of the loop head with only loop invariant defs. + */ +static unsigned is_loop_invariant_def(ir_node *node) { int i; - if (! is_in_loop(node)) + if (! is_in_loop(node)) { + DB((dbg, LEVEL_4, "Not in loop %N\n", node)); + /* || is_Const(node) || is_SymConst(node)) {*/ return 1; + } - /* TODO all cases? and how to use the dom tree for that. */ - + /* If this is a phi of the loophead shared by more than 1 loop, + * we need to check if all defs are not in the loop. */ if (is_Phi(node)) { + ir_node *block; + block = get_nodes_block(node); + + /* To prevent unexpected situations. */ + if (block != loop_head) { + return 0; + } + for (i = 0; i < get_irn_arity(node); ++i) { - if (is_own_backedge(get_nodes_block(node), i) && get_irn_n(node, i) != node) + /* Check if all bes are just loopbacks. */ + if (is_own_backedge(block, i) && get_irn_n(node, i) != node) return 0; } + DB((dbg, LEVEL_4, "invar %N\n", node)); + return 1; } - return 1; + DB((dbg, LEVEL_4, "Not invar %N\n", node)); + + return 0; } -/* TODO name */ -static ir_node *is_loop_iteration(ir_node *node) +/* Returns 1 if one pred of node is invariant and the other is not. + * invar_pred and other are set analogously. */ +static unsigned get_invariant_pred(ir_node *node, ir_node **invar_pred, ir_node **other) +{ + ir_node *pred0 = get_irn_n(node, 0); + ir_node *pred1 = get_irn_n(node, 1); + + *invar_pred = NULL; + *other = NULL; + + if (is_loop_invariant_def(pred0)) { + DB((dbg, LEVEL_4, "pred0 invar %N\n", pred0)); + *invar_pred = pred0; + *other = pred1; + } + + if (is_loop_invariant_def(pred1)) { + DB((dbg, LEVEL_4, "pred1 invar %N\n", pred1)); + + if (*invar_pred != NULL) { + /* RETURN. We do not want both preds to be invariant. */ + return 0; + } + + *other = pred0; + *invar_pred = pred1; + return 1; + } else { + DB((dbg, LEVEL_4, "pred1 not invar %N\n", pred1)); + + if (*invar_pred != NULL) + return 1; + else + return 0; + } +} + +/* Starts from a phi that may belong to an iv. + * If an add forms a loop with iteration_phi, + * and add uses a constant, 1 is returned + * and 'start' as well as 'add' are sane. */ +static unsigned get_start_and_add(ir_node *iteration_phi, unrolling_kind_flag role) { int i; - ir_node *found_add = NULL; + ir_node *found_add = loop_info.add; + int arity = get_irn_arity(iteration_phi); - if (!is_in_loop(node)) - return NULL; + DB((dbg, LEVEL_4, "Find start and add from %N\n", iteration_phi)); - if (is_Add(node)) - return node; + for (i = 0; i < arity; ++i) { - /*TODO all cases? and how do i use the dom tree for that.*/ + /* Find start_val which needs to be pred of the iteration_phi. + * If start_val already known, sanity check. */ + if (!is_backedge(get_nodes_block(loop_info.iteration_phi), i)) { + ir_node *found_start_val = get_irn_n(loop_info.iteration_phi, i); - if (is_Phi(node)) { - for (i = 0; i < get_irn_arity(node); ++i) { - ir_node *new_found; - if (! is_own_backedge(get_nodes_block(node), i)) - continue; - new_found = get_irn_n(node,i); + DB((dbg, LEVEL_4, "found_start_val %N\n", found_start_val)); - if (found_add && found_add != new_found) - return NULL; + /* We already found a start_val it has to be always the same. */ + if (loop_info.start_val && found_start_val != loop_info.start_val) + return 0; + + if ((role == constant) && !(is_SymConst(found_start_val) || is_Const(found_start_val))) + return 0; + else if((role == constant) && !(is_loop_invariant_def(found_start_val))) + return 0; - found_add = new_found; + loop_info.start_val = found_start_val; + } + + /* The phi has to be in the loop head. + * Follow all own backedges. Every value supplied from these preds of the phi + * needs to origin from the same add. */ + if (is_own_backedge(get_nodes_block(loop_info.iteration_phi), i)) { + ir_node *new_found = get_irn_n(loop_info.iteration_phi,i); + + DB((dbg, LEVEL_4, "is add? %N\n", new_found)); + + if (! (is_Add(new_found) || is_Sub(new_found)) || (found_add && found_add != new_found)) + return 0; + else + found_add = new_found; } } - return found_add; + + loop_info.add = found_add; + + return 1; } -/* counting loop */ -static unsigned get_unroll_decision(out_edge *cur_loop_outs) + +/* Returns 1 if one pred of node is a const value and the other is not. + * const_pred and other are set analogously. */ +static unsigned get_const_pred(ir_node *node, ir_node **const_pred, ir_node **other) { - int i; - ir_node *pred0, *pred1, *projx, *cond, *projres, *loop_condition; - ir_node *iteration, *add, *iteration_phi, *end_val, *step, *add_in0, *add_in1; + ir_node *pred0 = get_irn_n(node, 0); + ir_node *pred1 = get_irn_n(node, 1); - (void) cur_loop_outs; - (void) i; + DB((dbg, LEVEL_4, "Checking for constant pred of %N\n", node)); + *const_pred = NULL; + *other = NULL; - /* There is more than 1 condition for the loop exit. We cannot cope this with duffs device. */ - if (loop_info.cf_outs != 1) + /*DB((dbg, LEVEL_4, "is %N const\n", pred0));*/ + if (is_Const(pred0) || is_SymConst(pred0)) { + *const_pred = pred0; + *other = pred1; + } + + /*DB((dbg, LEVEL_4, "is %N const\n", pred1));*/ + if (is_Const(pred1) || is_SymConst(pred1)) { + if (*const_pred != NULL) { + /* RETURN. We do not want both preds to be constant. */ + return 0; + } + + *other = pred0; + *const_pred = pred1; + } + + if (*const_pred == NULL) return 0; + else + return 1; +} - /*TODO test for impact on performance */ - if (loop_info.calls > 0) +/* 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_tarval *next; + + DB((dbg, LEVEL_4, "Loop taken if (stepped)%ld %s (end)%ld ", + get_tarval_long(stepped), + get_pnc_string((norm_proj)), + get_tarval_long(end_tar))); + DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value)); + + /* If current iv does not stay in the loop, + * this run satisfied the exit condition. */ + if (! (tarval_cmp(stepped, end_tar) & norm_proj)) + return 1; + + 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_tarval_long(end_tar))); + + /* next step */ + if (is_Add(loop_info.add)) + next = tarval_add(stepped, step_tar); + else + /* sub */ + next = tarval_sub(stepped, step_tar, get_irn_mode(loop_info.end_val)); + + DB((dbg, LEVEL_4, "Loop taken if %ld %s %ld ", + get_tarval_long(next), + get_pnc_string(norm_proj), + get_tarval_long(end_tar))); + DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value)); + + /* Increase steps. */ + *count_tar = tarval_add(*count_tar, get_tarval_one(get_tarval_mode(*count_tar))); + + /* Next has to fail the loop condition, or we will never exit. */ + if (! (tarval_cmp(next, end_tar) & norm_proj)) + return 1; + else return 0; +} + +/* Check if loop meets requirements for a 'simple loop': + * - Exactly one cf out + * - Allowed calls + * - Max nodes after unrolling + * - tail-controlled + * - exactly one be + * - cmp + * Returns Projection of cmp node or NULL; */ +static ir_node *is_simple_loop(void) +{ + int arity, i; + ir_node *loop_block, *exit_block, *projx, *cond, *projres, *loop_condition; + + /* Maximum of one condition, and no endless loops. */ + if (loop_info.cf_outs != 1) + return NULL; + DB((dbg, LEVEL_4, "1 loop exit\n")); - projx = get_irn_n(loop_info.cf_out.node, loop_info.cf_out.pos); +#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); + return NULL; + } +#endif + + + DB((dbg, LEVEL_4, "maximum unroll factor %u, to not exceed node limit \n", + opt_params.max_unrolled_loop_size)); + + arity = get_irn_arity(loop_head); + /* RETURN if we have more than 1 be. */ + /* Get my backedges without alien bes. */ + loop_block = NULL; + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(loop_head, i); + if (is_own_backedge(loop_head, i)) { + if (loop_block) + /* Our simple loops may have only one backedge. */ + return NULL; + else { + loop_block = get_nodes_block(pred); + loop_info.be_src_pos = i; + } + } + } + + DB((dbg, LEVEL_4, "loop has 1 own backedge.\n")); + + exit_block = get_nodes_block(loop_info.cf_out.pred); + /* The loop has to be tail-controlled. + * This can be changed/improved, + * but we would need a duff iv. */ + if (exit_block != loop_block) + return NULL; + + DB((dbg, LEVEL_4, "tail-controlled loop.\n")); + + /* 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); - DB((dbg, LEVEL_2, " loop condition %N\n", loop_condition)); + if (!is_Cmp(loop_condition)) + return NULL; + + DB((dbg, LEVEL_5, "projection is %s\n", get_pnc_string(get_Proj_proj(projx)))); + + switch(get_Proj_proj(projx)) { + case pn_Cond_false: + loop_info.exit_cond = 0; + break; + case pn_Cond_true: + loop_info.exit_cond = 1; + break; + default: + panic("Cond Proj_proj other than true/false"); + } + + DB((dbg, LEVEL_4, "Valid Cmp.\n")); + + return projres; +} + +/* Returns 1 if all nodes are mode_Iu or mode_Is. */ +static unsigned are_mode_I(ir_node *n1, ir_node* n2, ir_node *n3) +{ + ir_mode *m1 = get_irn_mode(n1); + ir_mode *m2 = get_irn_mode(n2); + ir_mode *m3 = get_irn_mode(n3); + + if ((m1 == mode_Iu && m2 == mode_Iu && m3 == mode_Iu) || + (m1 == mode_Is && m2 == mode_Is && m3 == mode_Is)) + return 1; + else + return 0; +} + +/* Checks if cur_loop is a simple tail-controlled counting loop + * with start and end value loop invariant, step constant. */ +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; + + + /* RETURN if loop is not 'simple' */ + projres = is_simple_loop(); + if (projres == NULL) + return 0; + + /* Use a minimal size for the invariant unrolled loop, + * as duffs device produces overhead */ + if (loop_info.nodes < opt_params.invar_unrolling_min_size) + return 0; + + loop_condition = get_irn_n(projres, 0); + + success = get_invariant_pred(loop_condition, &loop_info.end_val, &iteration_path); + DB((dbg, LEVEL_4, "pred invar %d\n", success)); + + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Invariant End_val %N, other %N\n", loop_info.end_val, iteration_path)); + + /* We may find the add or the phi first. + * 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)); + + /* Preds of the add should be step and the iteration_phi */ + success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step)); + + if (! is_Phi(loop_info.iteration_phi)) + return 0; + + DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi)); + + /* Find start_val. + * Does necessary sanity check of add, if it is already set. */ + success = get_start_and_add(loop_info.iteration_phi, invariant); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got start A %N\n", loop_info.start_val)); + + } 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)); + + /* Find start_val and add-node. + * Does necessary sanity check of add, if it is already set. */ + success = get_start_and_add(loop_info.iteration_phi, invariant); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got start B %N\n", loop_info.start_val)); + DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add)); + + success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got step (B) %N\n", loop_info.step)); + + if (loop_info.iteration_phi != new_iteration_phi) + return 0; + + } else { + return 0; + } + + mode = get_irn_mode(loop_info.end_val); + + DB((dbg, LEVEL_4, "start %N, end %N, step %N\n", + loop_info.start_val, loop_info.end_val, loop_info.step)); + + if (mode != mode_Is && mode != mode_Iu) + return 0; + + /* TODO necessary? */ + if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val)) + return 0; + + DB((dbg, LEVEL_4, "mode integer\n")); + + step_tar = get_Const_tarval(loop_info.step); + + if (tarval_is_null(step_tar)) { + /* TODO Might be worth a warning. */ + return 0; + } + + DB((dbg, LEVEL_4, "step is not 0\n")); + + create_duffs_block(); + + return loop_info.max_unroll; +} + +/* Returns unroll factor, + * given maximum unroll factor and number of loop passes. */ +static unsigned get_preferred_factor_constant(ir_tarval *count_tar) +{ + ir_tarval *tar_6, *tar_5, *tar_4, *tar_3, *tar_2; + unsigned prefer; + ir_mode *mode = get_irn_mode(loop_info.end_val); + + tar_6 = new_tarval_from_long(6, mode); + tar_5 = new_tarval_from_long(5, mode); + tar_4 = new_tarval_from_long(4, mode); + tar_3 = new_tarval_from_long(3, mode); + tar_2 = new_tarval_from_long(2, mode); + + /* loop passes % {6, 5, 4, 3, 2} == 0 */ + if (tarval_is_null(tarval_mod(count_tar, tar_6))) + prefer = 6; + else if (tarval_is_null(tarval_mod(count_tar, tar_5))) + prefer = 5; + else if (tarval_is_null(tarval_mod(count_tar, tar_4))) + prefer = 4; + else if (tarval_is_null(tarval_mod(count_tar, tar_3))) + prefer = 3; + else if (tarval_is_null(tarval_mod(count_tar, tar_2))) + prefer = 2; + else { + /* gcd(max_unroll, count_tar) */ + int a = loop_info.max_unroll; + int b = (int)get_tarval_long(count_tar); + int c; + + DB((dbg, LEVEL_4, "gcd of max_unroll %d and count_tar %d: ", a, b)); + + do { + c = a % b; + a = b; b = c; + } while( c != 0); + + DB((dbg, LEVEL_4, "%d\n", a)); + return a; + } + + DB((dbg, LEVEL_4, "preferred unroll factor %d\n", prefer)); + + /* + * If our preference is greater than the allowed unroll factor + * we either might reduce the preferred factor and prevent a duffs device block, + * or create a duffs device block, from which in this case (constants only) + * we know the startloop at compiletime. + * The latter yields the following graphs. + * but for code generation we would want to use graph A. + * The graphs are equivalent. So, we can only reduce the preferred factor. + * A) B) + * PreHead PreHead + * | ,--. | ,--. + * \ Loop1 \ Loop2 \ + * \ | | / | | + * Loop2 / / Loop1 / + * | `--' | `--' + */ + + if (prefer <= loop_info.max_unroll) + return prefer; + else { + switch(prefer) { + case 6: + if (loop_info.max_unroll >= 3) + return 3; + else if (loop_info.max_unroll >= 2) + return 2; + else + return 0; + + case 4: + if (loop_info.max_unroll >= 2) + return 2; + else + return 0; + + default: + return 0; + } + } +} + +/* Check if cur_loop is a simple counting loop. + * Start, step and end are constants. + * TODO The whole constant case should use procedures similar to + * the invariant case, as they are more versatile. */ +/* 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; + + /* RETURN if loop is not 'simple' */ + projres = is_simple_loop(); + if (projres == NULL) + return 0; - /* One in of the loop condition needs to be loop invariant. - * The other in is assigned by an add. - * The add uses a loop invariant value - * and another value that depends on a loop invariant start value and the add itself. + /* One in of the loop condition needs to be loop invariant. => end_val + * The other in is assigned by an add. => add + * The add uses a loop invariant value => step + * and a phi with a loop invariant start_val and the add node as ins. ^ ^ | | .-, | Phi | \ | | - Add / - |__/ + ^ Add | + \ | \__| + cond + /\ */ - end_val = NULL; - /* Find the loop invariant in */ - /* Assumption that condition is cmp or mod. - TODO other? */ - pred0 = get_irn_n(loop_condition, 0); - pred1 = get_irn_n(loop_condition, 1); + loop_condition = get_irn_n(projres, 0); - if (is_loop_invariant_val(pred0)) { - end_val = pred0; - iteration = pred1; - } + success = get_const_pred(loop_condition, &loop_info.end_val, &iteration_path); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "End_val %N, other %N\n", loop_info.end_val, iteration_path)); + + /* We may find the add or the phi first. + * 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; - if (is_loop_invariant_val(pred1)) { - if (end_val != NULL) - /* RETURN. loop condition does not change during the loop. */ + loop_info.add = iteration_path; + DB((dbg, LEVEL_4, "Case 2: Got add %N (maybe not sane)\n", loop_info.add)); + + /* Preds of the add should be step and the iteration_phi */ + success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi); + if (! success) return 0; - end_val = pred1; - iteration = pred0; - } + DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step)); - DB((dbg, LEVEL_2, " end_val %N\n", end_val)); + if (! is_Phi(loop_info.iteration_phi)) + return 0; - /* Check for constraint of remaining in. */ - add = is_loop_iteration(iteration); - if (! add) - return 0; + DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi)); - DB((dbg, LEVEL_2, " add %N\n", add)); + /* Find start_val. + * Does necessary sanity check of add, if it is already set. */ + success = get_start_and_add(loop_info.iteration_phi, constant); + if (! success) + return 0; - add_in0 = get_irn_n(add, 0); - add_in1 = get_irn_n(add, 1); + DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val)); - if (is_loop_invariant_val(add_in0)) { - step = add_in0; - iteration_phi = add_in1; - } + } else if (is_Phi(iteration_path)) { + ir_node *new_iteration_phi; - if (is_loop_invariant_val(add_in1)) { - if (step != NULL) + /* 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 1: Got phi %N \n", loop_info.iteration_phi)); + + /* Find start_val and add-node. + * Does necessary sanity check of add, if it is already set. */ + success = get_start_and_add(loop_info.iteration_phi, constant); + if (! success) return 0; - step = add_in1; - iteration_phi = add_in0; - } - DB((dbg, LEVEL_2, " step %N\n", step)); + DB((dbg, LEVEL_4, "Got start %N\n", loop_info.start_val)); + DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add)); - if (! is_Phi(iteration_phi)) { - if (is_Phi(iteration)) - iteration_phi = iteration; - else + success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step)); + + if (loop_info.iteration_phi != new_iteration_phi) return 0; + + } else { + /* RETURN */ + return 0; + } + + mode = get_irn_mode(loop_info.end_val); + + DB((dbg, LEVEL_4, "start %N, end %N, step %N\n", + loop_info.start_val, loop_info.end_val, loop_info.step)); + + if (mode != mode_Is && mode != mode_Iu) + return 0; + + /* TODO necessary? */ + if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val)) + return 0; + + DB((dbg, LEVEL_4, "mode integer\n")); + + end_tar = get_Const_tarval(loop_info.end_val); + start_tar = get_Const_tarval(loop_info.start_val); + step_tar = get_Const_tarval(loop_info.step); + + if (tarval_is_null(step_tar)) + /* TODO Might be worth a warning. */ + return 0; + + DB((dbg, LEVEL_4, "step is not 0\n")); + + if ((!tarval_is_negative(step_tar)) ^ (!is_Sub(loop_info.add))) + loop_info.decreasing = 1; + + diff_tar = tarval_sub(end_tar, start_tar, mode); + + /* We need at least count_tar steps to be close to end_val, maybe more. + * No way, that we have gone too many steps. + * This represents the 'latest value'. + * (If condition checks against latest value, is checked later) */ + count_tar = tarval_div(diff_tar, step_tar); + + /* Iv will not pass end_val (except overflows). + * Nothing done, as it would yield to no advantage. */ + if (tarval_is_negative(count_tar)) { + DB((dbg, LEVEL_4, "Loop is endless or never taken.")); + /* TODO Might be worth a warning. */ + return 0; } - DB((dbg, LEVEL_2, " #### COUNTING LOOP step %N end %N phi %N\n", step, end_val, iteration_phi)); + count_stats(stats.u_simple_counting_loop); -#if 0 - phi for startval + loop_info.latest_value = is_latest_val; - mode = get_irn_mode(add); + /* TODO split here + if (! is_simple_counting_loop(&count_tar)) + return 0; + */ - block = new_Block(0, NULL); - /*set_irg_current_Block(current_ir_graph, block);*/ + /* stepped can be negative, if step < 0 */ + stepped = tarval_mul(count_tar, step_tar); - /*TODO*/ - unroll_mod_const = new_Const(unroll_number); - module = new_r_Mod(block, new_NoMem(), end_val, step, mode, op_pin_state_pinned); - /*new_Proj();*/ + /* step as close to end_val as possible, */ + /* |stepped| <= |end_tar|, and dist(stepped, end_tar) is smaller than a step. */ + if (is_Sub(loop_info.add)) + stepped = tarval_sub(start_tar, stepped, mode_Is); + else + stepped = tarval_add(start_tar, stepped); + DB((dbg, LEVEL_4, "stepped to %ld\n", get_tarval_long(stepped))); -#endif - return 0; + proj_proj = get_Proj_pn_cmp(projres); + /* Assure that norm_proj is the stay-in-loop case. */ + if (loop_info.exit_cond == 1) + norm_proj = get_math_inverted_case(proj_proj); + else + norm_proj = proj_proj; + + DB((dbg, LEVEL_4, "normalized projection %s\n", get_pnc_string(norm_proj))); + + /* Executed at most once (stay in counting loop if a Eq b) */ + if (norm_proj == pn_Cmp_Eq) + /* TODO Might be worth a warning. */ + return 0; + + /* calculates next values and increases count_tar according to it */ + success = simulate_next(&count_tar, stepped, step_tar, end_tar, norm_proj); + if (! success) + return 0; + + /* We run loop once more, if we compare to the + * not yet in-/decreased iv. */ + if (is_latest_val == 0) { + DB((dbg, LEVEL_4, "condition uses not latest iv value\n")); + count_tar = tarval_add(count_tar, get_tarval_one(mode)); + } + + DB((dbg, LEVEL_4, "loop taken %ld times\n", get_tarval_long(count_tar))); + + /* Assure the loop is taken at least 1 time. */ + if (tarval_is_null(count_tar)) { + /* TODO Might be worth a warning. */ + return 0; + } + + loop_info.count_tar = count_tar; + return get_preferred_factor_constant(count_tar); } -#endif /** * Loop unrolling */ static void unroll_loop(void) { - int i; - unsigned unroll_number; - out_edge *ssa_outs; - cur_loop_outs = NEW_ARR_F(out_edge, 0); - /* Get loop outs */ - irg_walk_graph(current_ir_graph, get_loop_outs, NULL, NULL); - - unroll_number = get_unroll_decision(cur_loop_outs); + if (! (loop_info.nodes > 0)) + return; - /*dump_ir_block_graph(current_ir_graph, "-pre");*/ +#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); + return; + } - if (unroll_number) { - create_duffs_device(unroll_number); + if (loop_info.calls > 0) { + DB((dbg, LEVEL_2, "Calls %d > allowed calls 0\n", + loop_info.calls)); + count_stats(stats.calls_limit); + return; + } +#endif - /* Copies the loop and allocs node_info */ - copy_loop(cur_loop_outs, unroll_number - 1); - /*dump_ir_block_graph(current_ir_graph, "-cp");*/ + unroll_nr = 0; - /* Line up the floating copies. */ - place_copies(unroll_number - 1); - /*dump_ir_block_graph(current_ir_graph, "-ord");*/ + /* get_unroll_decision_constant and invariant are completely + * independent for flexibility. + * Some checks may be performed twice. */ - /* Extend loop successors */ - ssa_outs = extend_ins(cur_loop_outs, unroll_number - 1); - /*dump_ir_block_graph(current_ir_graph, "-fixed")*/ ; + /* constant case? */ + if (opt_params.allow_const_unrolling) + unroll_nr = get_unroll_decision_constant(); + if (unroll_nr > 1) { + loop_info.unroll_kind = constant; - /* Links are going to be overwritten */ - free_node_info_blocks(); + } else { + /* invariant case? */ + if (opt_params.allow_invar_unrolling) + unroll_nr = get_unroll_decision_invariant(); + if (unroll_nr > 1) + loop_info.unroll_kind = invariant; + } - /* Generate phis for all loop outs */ - for (i = 0; i < ARR_LEN(ssa_outs); ++i) { - out_edge entry = ssa_outs[i]; - ir_node *node = entry.node; - ir_node *pred = get_irn_n(entry.node, entry.pos); + DB((dbg, LEVEL_2, " *** Unrolling %d times ***\n", unroll_nr)); - DB((dbg, LEVEL_5, "Do? construct_ssa_n def %N node %N pos %d\n", - pred, node, entry.pos)); + if (unroll_nr > 1) { + loop_entries = NEW_ARR_F(entry_edge, 0); - if (!is_End(node)) { - DB((dbg, LEVEL_5, "construct_ssa_n def %N node %N pos %d\n", - pred, node, entry.pos)); + /* Get loop outs */ + irg_walk_graph(current_ir_graph, get_loop_entries, NULL, NULL); - construct_ssa_n(pred, node, unroll_number - 1); - /*if (new_phi) - construct_ssa_n(pred, new_phi, unroll_number - 1);*/ - } + if (loop_info.unroll_kind == constant) { + if ((int)get_tarval_long(loop_info.count_tar) == unroll_nr) + loop_info.needs_backedge = 0; + else + loop_info.needs_backedge = 1; + } else { + loop_info.needs_backedge = 1; } - /*dump_ir_block_graph(current_ir_graph, "-ssa-done");*/ - /* FREE */ - free_node_info(); + /* Use phase to keep copy of nodes from the condition chain. */ + phase = new_phase(current_ir_graph, phase_irn_init_default); + + /* Copies the loop */ + copy_loop(loop_entries, unroll_nr - 1); + /* Line up the floating copies. */ + place_copies(unroll_nr - 1); + + /* Remove phis with 1 in + * If there were no nested phis, this would not be necessary. + * Avoiding the creation in the first place + * leads to complex special cases. */ irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL); - DEL_ARR_F(ssa_outs); + if (loop_info.unroll_kind == constant) + count_stats(stats.constant_unroll); + else + count_stats(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); + + DEL_ARR_F(loop_entries); } - DEL_ARR_F(cur_loop_outs); + } -/* Initialization and */ +/* Analyzes the loop, and checks if size is within allowed range. + * Decides if loop will be processed. */ static void init_analyze(ir_loop *loop) { - /* Init new for every loop */ cur_loop = loop; loop_head = NULL; loop_head_valid = 1; - loop_inv_head = NULL; - loop_peeled_head = NULL; - loop_info.calls = 0; - loop_info.blocks = 0; - loop_info.cf_outs = 0; + /* Reset loop info */ + memset(&loop_info, 0, sizeof(loop_info_t)); - DB((dbg, LEVEL_2, " >>>> current loop includes node %N <<<\n", - get_loop_node(loop, 0))); + DB((dbg, LEVEL_1, " >>>> current loop includes node %N <<<\n", + get_loop_node(loop, 0))); + /* Collect loop informations: head, node counts. */ irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL); /* RETURN if there is no valid head */ if (!loop_head || !loop_head_valid) { - DB((dbg, LEVEL_2, "No valid loop head. Nothing done.\n")); + DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n")); return; + } else { + DB((dbg, LEVEL_1, "Loophead: %N\n", loop_head)); } - DB((dbg, LEVEL_2, "Loophead: %N\n", loop_head)); + 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); + return; + } - if (enable_inversion) - loop_inversion(); + switch (loop_op) { + case loop_op_inversion: + loop_inversion(); + break; - if (enable_unrolling) - unroll_loop(); + case loop_op_unrolling: + unroll_loop(); + break; - DB((dbg, LEVEL_2, " <<<< end of loop with node %N >>>>\n", - get_loop_node(loop, 0))); + default: + panic("Loop optimization not implemented."); + } + DB((dbg, LEVEL_1, " <<<< end of loop with node %N >>>>\n", + get_loop_node(loop, 0))); } -/* Find most inner loops and send them to analyze_loop */ -static void find_most_inner_loop(ir_loop *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); + size_t 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", + DB((dbg, LEVEL_1, " >>> unrolling (Startnode %N) <<<\n", get_irg_start(irg))); loop_optimization(irg); - DB((dbg, LEVEL_2, " >>> unrolling done (Startnode %N) <<<\n", + DB((dbg, LEVEL_1, " >>> unrolling done (Startnode %N) <<<\n", get_irg_start(irg))); } void do_loop_inversion(ir_graph *irg) { - enable_unrolling = 0; - enable_peeling = 0; - enable_inversion = 1; + loop_op = loop_op_inversion; - DB((dbg, LEVEL_2, " >>> inversion (Startnode %N) <<<\n", + DB((dbg, LEVEL_1, " >>> inversion (Startnode %N) <<<\n", get_irg_start(irg))); loop_optimization(irg); - DB((dbg, LEVEL_2, " >>> inversion done (Startnode %N) <<<\n", + assure_cf_loop(irg); + + DB((dbg, LEVEL_1, " >>> inversion done (Startnode %N) <<<\n", get_irg_start(irg))); } void do_loop_peeling(ir_graph *irg) { - enable_unrolling = 0; - enable_peeling = 1; - enable_inversion = 0; + loop_op = loop_op_peeling; - DB((dbg, LEVEL_2, " >>> peeling (Startnode %N) <<<\n", + DB((dbg, LEVEL_1, " >>> peeling (Startnode %N) <<<\n", get_irg_start(irg))); loop_optimization(irg); - DB((dbg, LEVEL_2, " >>> peeling done (Startnode %N) <<<\n", + DB((dbg, LEVEL_1, " >>> peeling done (Startnode %N) <<<\n", get_irg_start(irg))); }