X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=a6cf45feb9f96f82cf0fe68faeda3b1f2c43f514;hb=6730cf921d356d992d35526daf57f82af7ab0816;hp=c130a9f4556e5e3b19fac26bcb6469f5008fbd74;hpb=2cadf15bc35d3b26b94b7c5f2b972e95a23a7be0;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index c130a9f45..a6cf45feb 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-2010 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -19,14 +19,19 @@ /** * @file - * @brief Loop peeling and unrolling * @author Christian Helmer + * @brief loop inversion and loop unrolling + * * @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" @@ -35,288 +40,244 @@ #include "irouts.h" #include "iredges.h" #include "irtools.h" -#include "array_t.h" /* automatic array */ -#include "beutil.h" /* get_block */ +#include "array_t.h" +#include "beutil.h" +#include "irpass.h" +#include "irdom.h" + +#include "irbackedge_t.h" +#include "irphase_t.h" +#include "irloop_t.h" -// TODO during DBG -//#include "irnode_t.h" -#include "irdump.h" DEBUG_ONLY(static firm_dbg_module_t *dbg); +/* DBG print stats for every procedure. */ +#define LOOP_OPT_STATS 0 + +/* 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. */ #define for_each_phi(block, phi) \ - for ( (phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next( (phi) ) ) + for ((phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next((phi))) + +#define for_each_phi_safe(head, phi, next) \ + for ((phi) = (head), (next) = (head) ? get_Phi_next((head)) : NULL; \ + (phi) ; (phi) = (next), (next) = (next) ? get_Phi_next((next)) : NULL) -/* current loop */ +/* Currently processed loop. */ static ir_loop *cur_loop; -/* The loop walker should be possible to abort if nothing can be done anymore */ -typedef unsigned irg_walk_func_abortable(ir_node *, void *); +/* Flag for kind of unrolling. */ +typedef enum { + constant, + invariant +} unrolling_kind_flag; -/* condition for breaking a copy_walk */ +/* Condition for performing visiting a node during copy_walk. */ typedef unsigned walker_condition(ir_node *); -/* stores node and position of a predecessor */ -typedef struct out_edges { +/* Node and position of a predecessor. */ +typedef struct entry_edge { ir_node *node; - int pred_irn_n; -} out_edges; + int pos; + ir_node *pred; +} entry_edge; -/* access complex values through the nodes links */ -typedef struct node_info { - unsigned invariant:1; - ir_node *copy; - ir_node *link; /* temporary links for ssa creation */ - ir_node **ins; /* ins for phi nodes, during rewiring of blocks */ - struct node_info *freelistnext; /* linked list to free all node_infos */ -} node_info; +/* Node info for unrolling. */ +typedef struct unrolling_node_info { + ir_node **copies; + /*ir_node **ins;*/ +} unrolling_node_info; -static node_info *link_node_state_list; /* head of the linked list to free all node_infos */ +/* Outs of the nodes head. */ +static entry_edge *cur_head_outs; -static out_edges *cur_loop_outs; /* A walker may start visiting the current loop with these nodes. */ -static out_edges *cur_head_outs; /* A walker may start visiting the cur head with these nodes. */ +/* Information about the loop head */ +static ir_node *loop_head = NULL; +static unsigned loop_head_valid = 1; -static ir_node *loop_cf_head = NULL; /* Loop head node */ -static unsigned loop_cf_head_valid = 1; /* A loop may have one head, otherwise we do not touch it. */ +/* 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 calls; - unsigned loads; - unsigned invariant_loads; /* number of load nodes */ - unsigned stores; /* number of store nodes */ - unsigned blocks; /* number of blocks in the loop */ - unsigned opnodes_n; /* nodes that should result in an instruction */ - unsigned opnodes_head; -} loop_info_t; +#if LOOP_OPT_STATS -/* Information about the current loop */ -static loop_info_t loop_info; +#define count_stats(val) (++val) +#define print_stats() (do_print_stats()) +#define reset_stats() (do_reset_stats()) -/* A walker may start visiting a condition chain with these nodes. */ -static out_edges *cond_chain_entries; +/* Stats */ +typedef struct loop_stats_t { + unsigned loops; + unsigned inverted; + unsigned too_large; + unsigned too_large_adapted; + unsigned cc_limit_reached; + unsigned calls_limit; -static unsigned head_inversion_node_count; -static unsigned head_inversion_node_limit; -//static unsigned head_inversion_block_count; + unsigned u_simple_counting_loop; + unsigned constant_unroll; + unsigned invariant_unroll; -/** - * - * ============= AUXILIARY FUNCTIONS ===================================== - */ + unsigned unhandled; +} loop_stats_t; -/** - * Creates object on the heap, and adds it to a linked list to free it later. - */ -static node_info *new_node_info(void) { - node_info *l = XMALLOCZ(node_info); - l->freelistnext = link_node_state_list; - link_node_state_list = l; - l->copy = NULL; - l->invariant = 0; - return l; -} +static loop_stats_t stats; -static node_info *get_node_info(ir_node *n) +/* Set stats to sero */ +static void do_reset_stats(void) { - return ((node_info *)get_irn_link(n)); + memset(&stats, 0, sizeof(loop_stats_t)); } -/* Allocates a node_info struct for the given node. For use with a walker. */ -static void alloc_node_info(ir_node *node, void *env) +/* Print stats */ +static void do_print_stats(void) { - node_info *state = new_node_info(); - (void) env; - set_irn_link(node, (void *)state); + 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) -static void free_node_info(void) -{ - node_info *next; - next = link_node_state_list; - while(next->freelistnext) { - node_info *cur = next; - next = cur->freelistnext; - xfree( cur ); - } -} +#endif -/** - * Use the linked list to reset the reused values of all node_infos - * Reset in particular the copy attribute as copy_walk uses it to determine a present copy - */ -static void reset_node_infos(void) -{ - node_info *next; - next = link_node_state_list; - while(next->freelistnext) { - node_info *cur = next; - next = cur->freelistnext; - cur->copy = NULL; - cur->ins = NULL; - cur->link = NULL; - } -} +/* Commandline parameters */ +typedef struct loop_opt_params_t { + unsigned max_loop_size; /* Maximum number of nodes */ + int depth_adaption; /* Loop nest depth adaption */ + unsigned allowed_calls; /* Number of calls allowed */ + unsigned count_phi:1; /* Count phi nodes */ + unsigned count_proj:1; /* Count projections */ -/* Returns the */ -static ir_node *get_copy(ir_node *n) -{ - return ((node_info *)get_irn_link(n))->copy; -} + unsigned max_cc_size; /* Maximum condition chain size */ -/* Links the node to its copy */ -static void set_copy(ir_node *n, ir_node *copy) -{ - ((node_info *)get_irn_link(n) )->copy = copy; -} + unsigned allow_const_unrolling:1; + unsigned allow_invar_unrolling:1; -/* Returns 0 if the node or block is not in cur_loop */ -static unsigned is_in_loop(ir_node *node) -{ - return (get_irn_loop(get_block(node)) == cur_loop); -} +} loop_opt_params_t; -/* 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))); -} +static loop_opt_params_t opt_params; -/* used for walker */ -static void unmark_block(ir_node *node, void * env) -{ - (void) env; -// DB((dbg, LEVEL_1, "UNMARK %ld\n", node->node_nr)); - if(is_Block(node)) - set_Block_mark(node, 0); -} +/* Loop analysis informations */ +typedef struct loop_info_t { + unsigned nodes; /* node count */ + unsigned ld_st; /* load and store nodes */ + 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; + + 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; -static unsigned is_nodesblock_marked(ir_node* node) -{ - return (get_Block_mark(get_block(node))); -} +/* Information about the current loop */ +static loop_info_t loop_info; -/** - * Add newpred at position pos to node and also add the corresponding value to the phis. - * Requires block phi list. - */ -static void duplicate_preds(ir_node* node, unsigned pos, ir_node* newpred) +/* 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; + +/* 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) { - ir_node** ins; - ir_node *phi; - int block_arity; - int i; - - assert(is_Block(node) && "duplicate_preds is only allowed for blocks"); - - DB((dbg, LEVEL_5, "duplicate_preds(node %ld, pos %d, newpred %ld)\n", get_irn_node_nr(node), pos, get_irn_node_nr(newpred))); - - block_arity = get_irn_arity(node); + int adapt_permil = opt_params.depth_adaption * depth; + unsigned permil_change; - NEW_ARR_A(ir_node*, ins, block_arity + 1 ); - for (i = 0; i < block_arity; ++i) - ins[i] = get_irn_n(node, i); - ins[block_arity] = newpred; - - set_irn_in(node, block_arity + 1, ins); - - for_each_phi(node, phi) { - int phi_arity = get_irn_arity(phi); - DB((dbg, LEVEL_5, "duplicate_preds: fixing phi %ld\n", get_irn_node_nr(phi))); + if (adapt_permil < -1000) + return 0; - NEW_ARR_A(ir_node *, ins, block_arity + 1); - for(i=0; i < phi_arity; ++i) { - DB((dbg, LEVEL_5, "in %ld\n", get_irn_node_nr(get_irn_n(phi, i)))); - ins[i] = get_irn_n(phi, i); - } - ins[block_arity] = get_irn_n(phi, pos); - set_irn_in(phi, block_arity + 1, ins); - } + permil_change = 1000 + adapt_permil; + return (opt_params.max_loop_size * permil_change) / 1000; } -/* Walks through all nodes of cur_loop */ -static unsigned loop_walker_rec(ir_node *node, - irg_walk_func_abortable *pre, - irg_walk_func_abortable *post, void * env) +/* Reset nodes link. For use with a walker. */ +static void reset_link(ir_node *node, void *env) { - int i; - unsigned stop = 0; - ir_graph *irg = get_current_ir_graph(); - - /* RETURN if we walked out of the loop*/ - if (!is_in_loop(node)) - return 0; - - if (pre) { - unsigned stop = pre(node, env); - if (stop) - return stop; - } - - set_irn_visited(node, get_irg_visited(irg)); - - if (get_irn_op(node) != op_Block) { - ir_node *pred = get_irn_n(node, -1); - if (get_irn_visited(pred) < get_irg_visited(irg)) - { - stop = loop_walker_rec(pred, pre, post, env); - if (stop) - return stop; - } - } - - for (i = get_irn_arity(node) - 1; i >= 0; --i) { - ir_node *pred = get_irn_n(node, i); - if (get_irn_visited(pred) < get_irg_visited(irg)) { - stop = loop_walker_rec(pred, pre, post, env); - if (stop) - return stop; - } - } - - if (post) - return post(node, env); - return 0; + (void)env; + set_irn_link(node, NULL); } -/** - * Walks through loop nodes. - * The entries of the loop (all edges pointing into the loop) have to be given. - */ -static unsigned loop_walker(out_edges *entries, - irg_walk_func_abortable *pre, irg_walk_func_abortable *post, void * env) +/* Returns 0 if the node or block is not in cur_loop. */ +static unsigned is_in_loop(ir_node *node) { - int i; - int stop = 0; - - for (i=0; !stop && i=2 && "expected load node to have in[1] (address)"); - - ir_node *pred = get_irn_n(node, 1); - if ( (get_Load_volatility(node) == volatility_non_volatile) & - (!is_in_loop(pred) - || is_Const(pred) - || is_SymConst(pred) - || get_node_info(node)->invariant ) ) { - get_node_info(node)->invariant = 1; - ++loop_info.invariant_loads; - } else - { - get_node_info(node)->invariant = 0; - } - } else { - int i; - invar = 1; - /* find loop variant preds */ - for(i = 0; i < arity; ++i) { - ir_node *pred = get_irn_n(node, i); + arity = get_irn_arity(node); + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(node, i); - if ( is_in_loop(pred) /* outside loop is loop invariant */ - && !is_Const(pred) /* constants */ - && !is_SymConst(pred) /* SymConst */ - && !get_node_info(node)->invariant ) { /* pred is marked as invariant */ - invar = 0; - } - } + pred_in_loop = is_in_loop(pred); + node_in_loop = is_in_loop(node); - if (invar) { - get_node_info(node)->invariant = 1; - } else { - get_node_info(node)->invariant = 0; + if (pred_in_loop && !node_in_loop) { + entry_edge entry; + entry.node = node; + entry.pos = i; + entry.pred = pred; + ARR_APP1(entry_edge, loop_entries, entry); + /* Count cf outs */ + if (is_Block(node)) { + ++loop_info.cf_outs; + loop_info.cf_out = entry; + } } } - return 0; } - +/* ssa */ static ir_node *ssa_second_def; static ir_node *ssa_second_def_block; /** - * Walks the graph bottom up, searching for definitions and create phis. - * (Does not handle the special case where the second definition is in the block of the user - * of the original definition because it is not necessary here.) + * 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; @@ -429,22 +365,25 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) ir_node *phi; ir_node **in; - DB((dbg, LEVEL_5, "ssa sdacp: block %ld\n", get_irn_node_nr(block))); + DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %N\n", block)); /* Prevents creation of phi that would be bad anyway. * Dead and bad blocks. */ - if (get_irn_arity(block) < 1 || is_Bad(block)) - return new_Bad(); + if (get_irn_arity(block) < 1 || is_Bad(block)) { + ir_graph *irg = get_irn_irg(block); + DB((dbg, LEVEL_5, "ssa bad %N\n", block)); + return new_r_Bad(irg); + } - if (block == ssa_second_def_block) { - DB((dbg, LEVEL_5, "ssa found second definition: use second def %ld\n", get_irn_node_nr(ssa_second_def))); + 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_node_info(block)->link; - DB((dbg, LEVEL_5, "ssa already visited: use linked %ld\n", get_irn_node_nr(value))); + ir_node *value = (ir_node *) get_irn_link(block); + DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value)); return value; } @@ -457,10 +396,10 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) ir_node *pred_block = get_Block_cfgpred_block(block, 0); ir_node *value; - DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %ld\n", get_irn_node_nr(pred_block))); + DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block)); - value = search_def_and_create_phis(pred_block, mode); - get_node_info(block)->link = value; + value = search_def_and_create_phis(pred_block, mode, 0); + set_irn_link(block, value); mark_irn_visited(block); return value; @@ -468,39 +407,40 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) /* create a new Phi */ NEW_ARR_A(ir_node*, in, n_cfgpreds); - for(i = 0; i < n_cfgpreds; ++i) - in[i] = new_Unknown(mode); + for (i = 0; i < n_cfgpreds; ++i) + in[i] = new_r_Unknown(irg, mode); phi = new_r_Phi(block, n_cfgpreds, in, mode); - /* Important: always keep block phi list up to date. */ add_Block_phi(block, phi); - /* EVERY node is assumed to have a node_info linked. */ - alloc_node_info(phi, NULL); - - DB((dbg, LEVEL_5, "ssa phi creation: link new phi %ld to block %ld\n", get_irn_node_nr(phi), get_irn_node_nr(block))); - - get_node_info(block)->link = 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); /* set Phi predecessors */ - for(i = 0; i < n_cfgpreds; ++i) { + for (i = 0; i < n_cfgpreds; ++i) { + ir_node *pred_val; ir_node *pred_block = get_Block_cfgpred_block(block, i); - ir_node *pred_val = search_def_and_create_phis(pred_block, mode); - DB((dbg, LEVEL_5, "ssa phi pred:phi %ld, pred %ld\n", get_irn_node_nr(phi), get_irn_node_nr(pred_val))); + assert(pred_block != NULL); + 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). - * Uses the irn_visited flags. Works without using the dominance tree. + * Works without using the dominance tree. */ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, - ir_node *second_block, ir_node *second_val) + ir_node *second_block, ir_node *second_val) { ir_graph *irg; ir_mode *mode; @@ -510,7 +450,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; @@ -520,7 +459,7 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, inc_irg_visited(irg); mode = get_irn_mode(orig_val); - get_node_info(orig_block)->link = orig_val; + set_irn_link(orig_block, orig_val); mark_irn_visited(orig_block); ssa_second_def_block = second_block; @@ -537,16 +476,14 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, if (is_End(user)) continue; - DB((dbg, LEVEL_5, "original user %ld\n", get_irn_node_nr(user))); + DB((dbg, LEVEL_5, "original user %N\n", user)); 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); } @@ -554,806 +491,2251 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); } -/* get the number of backedges without alien bes */ -static int get_backedge_n(ir_node *loophead, unsigned with_alien) + +/***** Unrolling Helper Functions *****/ + +/* Assign the copy with index nr to node n */ +static void set_unroll_copy(ir_node *n, int nr, ir_node *cp) { - 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; + unrolling_node_info *info; + assert(nr != 0 && "0 reserved"); + + info = (unrolling_node_info *)phase_get_irn_data(phase, n); + if (! info) { + ir_node **arr; + + 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 *)); + + phase_set_irn_data(phase, n, info); } - return be_n; + /* Original node */ + info->copies[0] = n; + + info->copies[nr] = cp; } -/** - * Sets the nodes backedges, according to its predecessors link. - */ -static void fix_backedge_info(ir_node *node) +/* Returns a nodes copy if it exists, else NULL. */ +static ir_node *get_unroll_copy(ir_node *n, int nr) { - int i; - for (i = 0; i < get_irn_arity(node); ++i) - { - ir_node *pred = get_irn_n(node, i); - if (get_node_info(pred)->link != NULL) - set_backedge(node, i); - else - set_not_backedge(node, i); - } + ir_node *cp; + unrolling_node_info *info = (unrolling_node_info *)phase_get_irn_data(phase, n); + if (! info) + return NULL; + + cp = info->copies[nr]; + return cp; } -/** - * - * ============= PEELING ===================================== - * - */ -/** - * Rewires the heads after peeling. - */ -static void peel_fix_heads(void) +/***** Inversion Helper Functions *****/ + +/* Sets copy cp of node n. */ +static void set_inversion_copy(ir_node *n, ir_node *cp) { - ir_node **loopheadnins, **peelheadnins; - ir_node *loophead = loop_cf_head; - ir_node *peelhead = get_copy(loophead); + phase_set_irn_data(phase, n, cp); +} - int headarity = get_irn_arity(loophead); - ir_node *phi; - int i; +/* Getter of copy of n for inversion */ +static ir_node *get_inversion_copy(ir_node *n) +{ + ir_node *cp = (ir_node *)phase_get_irn_data(phase, n); + return cp; +} - int lheadin_c = 0; - int pheadin_c = 0; +/* 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); +} - int backedges_n = get_backedge_n(loophead, 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)); +} - int lhead_arity = 2 * backedges_n; - int phead_arity = headarity - backedges_n; +/* Extends a nodes ins by node new. + * NOTE: This is slow if a node n needs to be extended more than once. */ +static int extend_irn(ir_node *n, ir_node *new) +{ + ir_node **ins; + int i; + int arity = get_irn_arity(n); + int new_arity = arity + 1; - /* new in arrays */ - NEW_ARR_A(ir_node *, loopheadnins, lhead_arity ); - NEW_ARR_A(ir_node *, peelheadnins, phead_arity ); + NEW_ARR_A(ir_node *, ins, new_arity); - for_each_phi(loophead, phi) { - NEW_ARR_A(ir_node *, get_node_info(phi)->ins, lhead_arity); - } - for_each_phi(peelhead, phi) { - NEW_ARR_A(ir_node *, get_node_info(phi)->ins, phead_arity); + for(i = 0; i < arity; ++i) { + ins[i] = get_irn_n(n, i); } + ins[i] = new; - for (i = 0; i < headarity; i++) - { - ir_node *orgjmp = get_irn_n(loophead, i); - ir_node *copyjmp = get_copy(orgjmp); - - /** - * Rewire the head blocks ins and their phi ins. - * Requires phi list per block. - */ - if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) { - loopheadnins[lheadin_c] = orgjmp; - /* marks out edge as backedge */ - get_node_info(orgjmp)->link = orgjmp; - for_each_phi(loophead, phi) { - get_node_info( phi )->ins[lheadin_c] = get_irn_n( phi, i) ; - } - ++lheadin_c; - - loopheadnins[lheadin_c] = copyjmp; /* former bes of the peeled code origin now from the loophead */ - /* marks out edge as normal edge */ - get_node_info(copyjmp)->link = NULL; - /* get_irn_n( get_copy_of(phi), i) get_copy_of(get_irn_n( phi, i)) - * Order is crucial! Predecessors outside of the loop are non existent. - * The copy (cloned with its ins!) has pred i, - * but phis pred i might not have a copy of itself. - */ - for_each_phi(loophead, phi) { - //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( get_copy_of(phi), i)->node_nr); - get_node_info( phi )->ins[lheadin_c] = get_irn_n( get_copy(phi), i) ; - } - ++lheadin_c; - } else { - peelheadnins[pheadin_c] = orgjmp; - /* marks out edge as normal edge */ - get_node_info(orgjmp)->link = NULL; - for_each_phi(peelhead, phi) { - get_node_info( phi )->ins[pheadin_c] = get_irn_n(phi, i); - } - ++pheadin_c; - } - }/* for */ + set_irn_in(n, new_arity, ins); + return arity; +} - //DBG - assert(pheadin_c == ARR_LEN(peelheadnins) && - lheadin_c == ARR_LEN(loopheadnins) && - "the constructed head arities do not match the predefined arities"); +/* 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); + + /* 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; - /** - * assign the ins to the nodes - */ - set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins); - set_irn_in(peelhead, ARR_LEN(peelheadnins), peelheadnins); + DB((dbg, LEVEL_5, "Extend phi %N by %N cp of %N\n", phi, new_in, pred)); + extend_irn(phi, new_in); + } +} - /* Fixes the backedge information according to the link. - * Following loop optimizations might depend on it. */ - fix_backedge_info(loophead); - fix_backedge_info(peelhead); +/* 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); - for_each_phi(loophead, phi) { - ir_node **ins = get_node_info( phi )->ins; - set_irn_in(phi, lhead_arity, ins); - } + assert(is_Block(block) && "We only required backedges of blocks."); - for_each_phi(peelhead, phi) { - ir_node **ins = get_node_info( phi )->ins; - set_irn_in(phi, phead_arity, ins); + 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; } -/** - * Create a raw copy (ins are still the old ones) of the given node. - */ -static ir_node *rawcopy_node(ir_node *node) +/* 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; - node_info *cpstate; cp = exact_copy(node); - set_copy(node, cp); - cpstate = new_node_info(); - set_irn_link(cp, cpstate); - mark_irn_visited(cp); + arity = get_irn_arity(node); + + /* Keep backedge info */ + for (i = 0; i < arity; ++i) { + if (is_backedge(node, i)) + set_backedge(cp, i); + } + + if (is_Block(cp)) { + set_Block_mark(cp, 0); + } + return cp; } -//int temp = 0; -// -///* This walker copies all walked nodes. The walk_condition determines the nodes to walk. */ -//static void keepalives_walk(ir_node *node, walker_condition *walk_condition) -//{ -// int i; -// int arity; -// ir_graph *irg = current_ir_graph; -// -// /** -// * break condition and cycle resolver, creating temporary node copies -// */ -// if (get_irn_visited(node) >= get_irg_visited(irg)) { -// return; -// } -// -// /* Walk */ -// mark_irn_visited(node); -// -// if (!is_Block(node)) { -// ir_node *pred = get_nodes_block(node); -// if (walk_condition(pred)) -// keepalives_walk( pred, walk_condition ); -// } -// -// arity = get_irn_arity(node); -// -// for (i = get_irn_arity(node) - 1; i >= 0; --i) { -// ir_node *pred = get_irn_n(node, i); -// -// if (walk_condition(pred)) -// keepalives_walk( pred, walk_condition ); -// } -// -// add_End_keepalive(get_irg_end(current_ir_graph), node); -//} - /** * This walker copies all walked nodes. - * If the walk_condition is true for a node, it is walked. - * All nodes node_info->copy attributes has to be NULL prior to every to every walk. + * 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. */ -static void copy_walk(ir_node *node, walker_condition *walk_condition) +static void copy_walk(ir_node *node, walker_condition *walk_condition, + ir_loop *set_loop) { int i; int arity; ir_node *cp; ir_node **cpin; ir_graph *irg = current_ir_graph; - node_info *node_info = get_node_info(node); /** * break condition and cycle resolver, creating temporary node copies */ if (get_irn_visited(node) >= get_irg_visited(irg)) { /* Here we rely on nodestate's copy being initialized with NULL */ - DB((dbg, LEVEL_5, "copy_walk: We have already visited %ld\n", get_irn_node_nr(node))); - if (node_info->copy == NULL) { - if (!is_Const(node) && !is_SymConst(node)) { - cp = rawcopy_node(node); - } else { - cp = node; - node_info->copy = cp; - } - DB((dbg, LEVEL_5, "The TEMP copy of %ld is created %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node)); + if (get_inversion_copy(node) == NULL) { + 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; } -// add_End_keepalive(get_irg_end(current_ir_graph), node); - /* Walk */ mark_irn_visited(node); if (!is_Block(node)) { ir_node *pred = get_nodes_block(node); if (walk_condition(pred)) - DB((dbg, LEVEL_5, "walk block %ld\n", get_irn_node_nr(pred))); - copy_walk( pred, walk_condition ); + DB((dbg, LEVEL_5, "walk block %N\n", pred)); + copy_walk(pred, walk_condition, set_loop); } arity = get_irn_arity(node); NEW_ARR_A(ir_node *, cpin, arity); - for (i = get_irn_arity(node) - 1; i >= 0; --i) { + for (i = 0; i < arity; ++i) { ir_node *pred = get_irn_n(node, i); if (walk_condition(pred)) { - DB((dbg, LEVEL_5, "walk node %ld\n", get_irn_node_nr(pred))); - copy_walk( pred, walk_condition ); - cpin[i] = get_copy(pred); - DB((dbg, LEVEL_5, "copy of %ld gets new in %ld which is copy of %ld\n", - get_irn_node_nr(node), get_irn_node_nr(get_copy(pred)), get_irn_node_nr(pred))); + DB((dbg, LEVEL_5, "walk node %N\n", pred)); + copy_walk(pred, walk_condition, set_loop); + cpin[i] = get_inversion_copy(pred); + DB((dbg, LEVEL_5, "copy of %N gets new in %N which is copy of %N\n", + node, get_inversion_copy(pred), pred)); } else { cpin[i] = pred; } } /* copy node / finalize temp node */ - if (node_info->copy == NULL) { + if (get_inversion_copy(node) == NULL) { /* No temporary copy existent */ - - /* Do not copy constants TODO right? */ - if (!is_Const(node) && !is_SymConst(node)) { - cp = rawcopy_node(node); - } else { - cp = node; - node_info->copy = cp; - } - DB((dbg, LEVEL_5, "The FINAL copy of %ld is CREATED %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + 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 */ - cp = get_copy(node); - DB((dbg, LEVEL_5, "The FINAL copy of %ld is EXISTENT %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + cp = get_inversion_copy(node); + DB((dbg, LEVEL_5, "The FINAL copy of %N is EXISTENT %N\n", node, cp)); } if (!is_Block(node)) { - ir_node *cpblock = get_copy(get_nodes_block(node)); + ir_node *cpblock = get_inversion_copy(get_nodes_block(node)); set_nodes_block(cp, cpblock ); - /* fix the phi information in attr.phis */ - if( is_Phi(cp) ) + if (is_Phi(cp)) add_Block_phi(cpblock, cp); - } else { - /* macroblock info has not been copied */ - set_Block_MacroBlock(cp, cp); } + /* Keeps phi list of temporary node. */ set_irn_in(cp, ARR_LEN(cpin), cpin); } -/* Loop peeling, and fix the cf for the loop entry nodes, which have now more preds */ -static void peel(out_edges *loop_outs) +/** + * 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; - ir_node **entry_buffer; - int entry_c = 0; + int arity; + ir_node *cp; + ir_node **cpin; - ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); + /** + * 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; + } - NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(loop_outs)); + /* Walk */ + mark_irn_visited(node); - /* duplicate loop walk */ -// cur_head = loop_cf_head; - inc_irg_visited(current_ir_graph); + 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); + } - for(i = 0; i < ARR_LEN(loop_outs); i++) { - out_edges entry = loop_outs[i]; - ir_node *node = entry.node; - ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n); + arity = get_irn_arity(node); + NEW_ARR_A(ir_node *, cpin, arity); + + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(node, i); - if (is_Block(node)) { - copy_walk( pred, is_in_loop ); - duplicate_preds(node, entry.pred_irn_n, get_copy(pred) ); + 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 { - copy_walk( pred, is_in_loop ); - if (!is_End(node)) /* leave out keepalives */ - /* Node is user of a value defined inside the loop. - * We'll need a phi since we duplicated the loop. */ - /* cannot construct_ssa here, because it needs another walker */ - entry_buffer[entry_c++] = pred; + cpin[i] = pred; } } - ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); - - /* Rewires the 2 heads */ - peel_fix_heads(); + /* 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 { + /* 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)); + } - /* Generate phis for values from peeled code and original loop */ - for(i = 0; i < entry_c; i++) - { - ir_node *cppred, *block, *cpblock, *pred; + if (!is_Block(node)) { + ir_node *cpblock = get_unroll_copy(get_nodes_block(node), copy_index); - /* It is not possible to use - * pred = get_irn_n(entry.node, entry.pred_irn_n); - * because we might have changed the nodes predecessors in construct_ssa - */ - pred = entry_buffer[i]; - cppred = get_copy(pred); - block = get_nodes_block(pred); - cpblock = get_nodes_block(cppred); - construct_ssa(block, pred, cpblock, cppred); + 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); } -/* - * 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. - */ -static void get_head_entries(ir_node *node, void *env) +/* Removes alle Blocks with non marked predecessors from the condition chain. */ +static void unmark_not_allowed_cc_blocks(void) { + int blocks = ARR_LEN(cc_blocks); int i; - int arity = get_irn_arity(node); - (void) env; - for(i = 0; i < arity; ++i) { - /* node is not in the head, but the predecessor is. - * (head or loop chain nodes are marked) */ - if (!is_nodesblock_marked(node) && is_nodesblock_marked(get_irn_n(node, i))) { - out_edges entry; - entry.node = node; - entry.pred_irn_n = i; - DB((dbg, LEVEL_5, - "Found head chain entry %ld @%d because !inloop %ld and inloop %ld\n", - node->node_nr, i, node->node_nr, get_irn_n(node, i)->node_nr)); - ARR_APP1(out_edges, cur_head_outs, entry); - } - } -} + for(i = 0; i < blocks; ++i) { + ir_node *block = cc_blocks[i]; + int a; + int arity = get_irn_arity(block); -/** - * Find condition chains, and add them to be inverted, until the node count exceeds the limit. + /* Head is an exception. */ + if (block == loop_head) + continue; + + 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)); + + break; + } + } + } +} + +/* Unmarks all cc blocks using cc_blocks except head. */ +static void unmark_cc_blocks(void) +{ + int blocks = ARR_LEN(cc_blocks); + int i; + + for(i = 0; i < blocks; ++i) { + ir_node *block = cc_blocks[i]; + + /* Head is an exception. */ + if (block != loop_head) + set_Block_mark(block, 0); + } + inversion_blocks_in_cc = 1; + + /* 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 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) +{ + int i; + int arity = get_irn_arity(node); + (void) env; + + for (i = 0; i < arity; ++i) { + if (!is_nodes_block_marked(node) && is_nodes_block_marked(get_irn_n(node, i))) { + entry_edge entry; + entry.node = node; + entry.pos = i; + /* 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); + + /* 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 * A block belongs to the chain if a condition branches out of the loop. - * Returns if the given block belongs to the condition chain. - * FIXME prevent collecting ALL loop blocks (may happen if all blocks jump 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 condition_chains(ir_node *block) { - const ir_edge_t *edge; +static unsigned find_condition_chain(ir_node *block) +{ + const ir_edge_t *edge; unsigned mark = 0; - //unsigned over_limit = 0; + unsigned has_be = 0; + unsigned jmp_only; + unsigned nodes_n = 0; + + mark_irn_visited(block); - int nodes_n = 0; + DB((dbg, LEVEL_5, "condition_chains for block %N\n", block)); - /* we need all outs, including keeps (TODO firm function for that??) */ + /* Get node count */ foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) { ++nodes_n; } - /* We do not want to collect more nodes from condition chains, than the limit allows us to. */ - if (head_inversion_node_count + nodes_n > head_inversion_node_limit) { - //over_limit = 1; + /* 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); -// printf(" %ld over limit\n", block->node_nr); return 0; } - ++loop_info.blocks; + /* Check if block only has a jmp instruction. */ + jmp_only = 1; + foreach_out_edge(block, edge) { + ir_node *src = get_edge_src_irn(edge); - /* First: check our successors, and add all succs that are outside of the loop to the list */ + if (! is_Block(src) && ! is_Jmp(src)) { + jmp_only = 0; + } + } + + /* 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 ); + ir_node *src = get_edge_src_irn(edge); + int pos = get_edge_src_pos(edge); - if (!is_in_loop(src)) { - //printf(" src %ld @ %d into block %ld \n", src->node_nr, pos, block->node_nr); + if (! is_in_loop(src)) mark = 1; - out_edges entry; - entry.node = src; - entry.pred_irn_n = pos; - ARR_APP1(out_edges, 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; } } - /* this block is not part of the chain, - * because the chain would become too big or we have no succ outside of the loop */ - 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); - DB((dbg, LEVEL_5, "block %ld is part of condition chain\n", get_irn_node_nr(block))); - head_inversion_node_count += nodes_n; + ++inversion_blocks_in_cc; + loop_info.cc_size += nodes_n; + DB((dbg, LEVEL_5, "block %N is part of condition chain\n", block)); + 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 cases */ - if (!is_in_loop( src ) || (get_irn_visited(src) >= get_irg_visited(current_ir_graph))) - continue; - - mark_irn_visited(src); - inchain = condition_chains( src ); - - /* if successor is not part of chain we need to collect its outs */ - if ( !inchain ) { - out_edges entry; - entry.node = src; - entry.pred_irn_n = pos; - ARR_APP1(out_edges, 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. + * 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.) */ -static void inversion_fix_heads(void) +static void fix_copy_inversion(void) { - ir_node **loopheadnins, **invheadnins; - ir_node *loophead = loop_cf_head; - ir_node *invhead = get_copy(loophead); - - int headarity = get_irn_arity(loophead); - ir_node *phi; + ir_node *new_head; + ir_node **ins; + ir_node **phis; + ir_node *phi, *next; + ir_node *head_cp = get_inversion_copy(loop_head); + ir_graph *irg = get_irn_irg(head_cp); + int arity = get_irn_arity(head_cp); + int backedges = get_backedge_n(head_cp, 0); + int new_arity = arity - backedges; + int pos; int i; - int lheadin_c = 0; - int iheadin_c = 0; + NEW_ARR_A(ir_node *, ins, new_arity); + + pos = 0; + /* Remove block backedges */ + for(i = 0; i < arity; ++i) { + if (!is_backedge(head_cp, i)) + ins[pos++] = get_irn_n(head_cp, i); + } + + new_head = new_r_Block(irg, new_arity, ins); - int backedges_n = get_backedge_n(loophead, 0); - int lhead_arity = headarity - backedges_n; - int ihead_arity = backedges_n; + phis = NEW_ARR_F(ir_node *, 0); - /* new in arrays for all phis in the head blocks */ - NEW_ARR_A(ir_node *, loopheadnins, lhead_arity); - NEW_ARR_A(ir_node *, invheadnins, ihead_arity); + for_each_phi_safe(get_Block_phis(head_cp), phi, next) { + ir_node *new_phi; + NEW_ARR_A(ir_node *, ins, new_arity); + pos = 0; + for(i = 0; i < arity; ++i) { + if (!is_backedge(head_cp, i)) + ins[pos++] = get_irn_n(phi, i); + } + 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); + } - for_each_phi(loophead, phi) { - NEW_ARR_A(ir_node *, get_node_info(phi)->ins, lhead_arity); + pos = 0; + for_each_phi_safe(get_Block_phis(head_cp), phi, next) { + exchange(phi, phis[pos++]); } - for_each_phi(invhead, phi) { - NEW_ARR_A(ir_node *, get_node_info(phi)->ins, ihead_arity); + + exchange(head_cp, new_head); + + DEL_ARR_F(phis); +} + +/* 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) +{ + ir_node *new_head; + ir_node **ins; + ir_node *phi, *next; + ir_node **phis; + ir_graph *irg = get_irn_irg(loop_head); + int arity = get_irn_arity(loop_head); + int backedges = get_backedge_n(loop_head, 0); + int new_arity = backedges; + int pos; + int i; + + NEW_ARR_A(ir_node *, ins, new_arity); + + pos = 0; + /* Keep only backedges */ + for(i = 0; i < arity; ++i) { + if (is_own_backedge(loop_head, i)) + ins[pos++] = get_irn_n(loop_head, i); } - for (i = 0; i < headarity; i++) { - ir_node *pred = get_irn_n(loophead, i); + new_head = new_r_Block(irg, new_arity, ins); - /** - * Rewire the head blocks ins and their phi ins. - * Requires phi list per block. - */ - if ( is_backedge(loophead, i) ) { - invheadnins[iheadin_c] = pred; - for_each_phi(invhead, phi) { - get_node_info( phi )->ins[iheadin_c] = get_irn_n( phi, i) ; - } - ++iheadin_c; - } else { - /* just copy these edges */ - loopheadnins[lheadin_c] = pred; - for_each_phi(loophead, phi) { - get_node_info( phi )->ins[lheadin_c] = get_irn_n(phi, i); + phis = NEW_ARR_F(ir_node *, 0); + + 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) { + ir_node *pred = get_irn_n(phi, i); + + if (is_own_backedge(loop_head, i)) { + /* 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)) { + /* Cannot do this here. */ + ins[pos++] = pred; /*fix_inner_cc_definitions(phi, pred);*/ + } else { + ins[pos++] = pred; + } } - ++lheadin_c; } - }/* for */ - /* assign the ins to the head blocks */ - set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins); - set_irn_in(invhead, ARR_LEN(invheadnins), invheadnins); + new_phi = new_rd_Phi(get_irn_dbg_info(phi), + new_head, new_arity, ins, + get_irn_mode(phi)); - /* assign the ins for the phis */ - for_each_phi(loophead, phi) { - ir_node **ins = get_node_info(phi)->ins; - set_irn_in(phi, lhead_arity, ins); + ARR_APP1(ir_node *, phis, new_phi); + + DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N (arity %d)\n", phi, new_phi, pos )); } - for_each_phi(invhead, phi) { - ir_node **ins = get_node_info(phi)->ins; - set_irn_in(phi, ihead_arity, ins); + pos = 0; + for_each_phi_safe(get_Block_phis(loop_head), phi, next) { + DB((dbg, LEVEL_5, "fix inverted exch phi %N by %N\n", phi, phis[pos])); + if (phis[pos] != phi) + exchange(phi, phis[pos++]); } -} + DEL_ARR_F(phis); -static void loop_inversion_walk(out_edges *head_entries) + DB((dbg, LEVEL_5, "fix inverted head exch head block %N by %N\n", loop_head, new_head)); + exchange(loop_head, new_head); +} + +/* Does the loop inversion. */ +static void inversion_walk(entry_edge *head_entries) { int i; - ir_node *phi; - int entry_c = 0; - ir_node **entry_buffer; - ir_node **head_phi_assign; - - NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(head_entries)); - head_phi_assign = NEW_ARR_F(ir_node *, 0); - - /* Find assignments in the condition chain, to construct_ssa for them after the loop inversion. */ - for_each_phi( loop_cf_head , phi) { - for(i=0; i| + * + * | ,--. | + * 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_phi_assign); ++i) { - ir_node *def_block, *inhead_phi_def, *inv_def_block, *inv_inhead_phi_def; - /* Note: construct_ssa only fixes the FIRST nodes usage. */ - inhead_phi_def = head_phi_assign[i]; - inv_inhead_phi_def = get_copy(inhead_phi_def); - def_block = get_nodes_block(inhead_phi_def); - inv_def_block = get_nodes_block(inv_inhead_phi_def); - DB((dbg, LEVEL_5, - "construct_ssa (condition chain out values) original %ld and clone %ld\n", - get_irn_node_nr(inv_inhead_phi_def), get_irn_node_nr(inhead_phi_def))); - construct_ssa(inv_def_block, inv_inhead_phi_def, def_block, inhead_phi_def); - } - loop_cf_head = get_copy(loop_cf_head); + 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. */ + fix_copy_inversion(); } -/** - * Decide if loop inversion, peeling or unrolling should be performed. - * Inversion creates abnormal looking loops. Be careful with optimizations after that. - */ -static void decision_maker(void) +/* Performs loop inversion of cur_loop if possible and reasonable. */ +static void loop_inversion(void) { - unsigned do_peel = 0; unsigned do_inversion = 1; + unsigned has_cc = 0; - unsigned max_loop_opnodes = 200000; + /*inversion_head_node_limit = INT_MAX;*/ + ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); - head_inversion_node_limit = 99910; + /* 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); - cur_loop_outs = NEW_ARR_F(out_edges, 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); - /* Find loop entries walk, find head */ - inc_irg_visited( current_ir_graph ); - irg_walk_graph( current_ir_graph, get_loop_outs_and_info, NULL, NULL ); + /*head_inversion_node_count = 0;*/ + inversion_blocks_in_cc = 0; - /* RETURN if there is no valid head */ - if (!loop_cf_head || !loop_cf_head_valid) { - DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n")); - return; - } -#if 0 - /* RETURN if there is a call in the loop */ - if (loop_info.calls) - return; + /* Use phase to keep copy of nodes from the condition chain. */ + phase = new_phase(current_ir_graph, phase_irn_init_default); - /* Loop complexity too high */ - if (loop_info.opnodes_n > max_loop_opnodes) - return; + /* 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); + + unmark_not_allowed_cc_blocks(); + DEL_ARR_F(cc_blocks); + +#if LOOP_IGNORE_NODE_LIMITS + (void) unmark_cc_blocks; +#else + /* Condition chain too large. + * Loop should better be small enough to fit into the cache. */ + /* FIXME 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); + + /* Only head taken? */ + if (inversion_blocks_in_cc == 1) + do_inversion = 0; + else + /* Unmark cc blocks except the head. + * Invert head only for possible unrolling. */ + unmark_cc_blocks(); + } +#endif -// foreach_out_edge(loop_cf_head, edge) { -// ir_node *node = get_edge_src_irn(edge); -// if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) ) -// ++loop_info.opnodes_head; -// } + /* We also catch endless loops here, + * because they do not have a condition chain. */ + 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", + inversion_blocks_in_cc)); + } - inc_irg_visited(current_ir_graph); - loop_walker( loop_outs, NULL, get_invariants, NULL ); + if (do_inversion) { + cur_head_outs = NEW_ARR_F(entry_edge, 0); - /* This could be improved with knowledge about variable range. */ - if (loop_info.stores == 0 && loop_info.invariant_loads > 0) - do_peel = 1; + /* Get all edges pointing into the condition chain. */ + irg_walk_graph(current_ir_graph, get_head_outs, NULL, NULL); -#endif + /* Do the inversion */ + inversion_walk(cur_head_outs); + DEL_ARR_F(cur_head_outs); - do_peel = 1; - do_inversion = 1; + /* Duplicated blocks changed doms */ + set_irg_doms_inconsistent(current_ir_graph); + /* Loop content changed */ + set_irg_loopinfo_inconsistent(current_ir_graph); + /* TODO are they? Depends on set_irn_in and set_irn_n exchange and new_node. */ + set_irg_outs_inconsistent(current_ir_graph); - /* Loop peeling */ - if (do_peel) { - peel(cur_loop_outs); - reset_node_infos(); + count_stats(stats.inverted); } - DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-peeled1")); + /* free */ + phase_free(phase); + DEL_ARR_F(cond_chain_entries); + DEL_ARR_F(head_df_loop); - DEL_ARR_F(cur_loop_outs); + ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); +} - /* Loop inversion */ - /* Search for condition chains. We may not do this before peeling, as peeling changes things. */ - ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); - irg_walk_graph(current_ir_graph, unmark_block, NULL, NULL); +/* Fix the original loop_heads ins for invariant unrolling case. */ +static void unrolling_fix_loop_head_inv(void) +{ + ir_node *ins[2]; + ir_node *phi; + ir_node *proj = new_r_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); - cond_chain_entries = NEW_ARR_F(out_edges, 0); - head_inversion_node_count = 0; - inc_irg_visited(current_ir_graph); - set_Block_mark(loop_cf_head, 1); - mark_irn_visited(loop_cf_head); - /* find condition chains */ - condition_chains(loop_cf_head); + /* Original loop_heads ins are: + * duff block and the own backedge */ - // TODO assume number of phis to be created. prevent inversion... + ins[0] = loop_condition; + ins[1] = proj; - /* Loop inversion */ - if (loop_info.blocks < 2) { - do_inversion = 0; - DB((dbg, LEVEL_2, "Loop contains %d (less than 2) blocks => No Inversion done.\n", loop_info.blocks)); + set_irn_in(loop_head, 2, ins); + + for_each_phi(loop_head, phi) { + ir_node *pred = get_irn_n(phi, loop_info.be_src_pos); + ir_node *last_pred = get_unroll_copy(pred, unroll_nr - 1); + + ins[0] = last_pred; + ins[1] = get_irn_link(phi); + + set_irn_in(phi, 2, ins); } +} - if (do_inversion) { - cur_head_outs = NEW_ARR_F(out_edges, 0); +/* Removes previously created phis with only 1 in. */ +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]; - /* get all edges pointing into the head or condition chain */ - irg_walk_graph(current_ir_graph, get_head_entries, NULL, NULL); + in[0] = get_irn_n(node, 0); - loop_inversion_walk(cur_head_outs); + exch = new_rd_Phi(get_irn_dbg_info(node), + get_nodes_block(node), 1, in, + get_irn_mode(node)); - DEL_ARR_F(cur_head_outs); + exchange(node, exch); } +} - DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-inversed2")); +/* Unrolling: Rewire floating copies. */ +static void place_copies(int copies) +{ + ir_node *loophead = loop_head; + int c, i; + 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); - /* FREE */ - DEL_ARR_F(cond_chain_entries); - ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); + 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 previous unrolled loop. */ + ir_node *ins[2]; + /* Calculate corresponding projection of mod result for this copy c */ + ir_node *proj = new_r_Proj(loop_info.duff_cond, mode_X, unroll_nr - c - 1); + + ins[0] = new_jmp; + ins[1] = proj; + set_irn_in(lower, 1, ins); + + 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 = get_irn_link(lower_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); + } + } + } + + /* Reconnect loop landing pad with 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); + + 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 defined 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(); + } } -/* */ -static void analyze_loop(ir_loop *loop) +/* Copies the cur_loop several times. */ +static void copy_loop(entry_edge *cur_loop_outs, int copies) { - /* Init new for every loop */ - cur_loop = loop; + int i, c; + + ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); - loop_cf_head = NULL; - loop_cf_head_valid = 1; - loop_inv_head = NULL; - loop_peeled_head = NULL; + for (c = 0; c < copies; ++c) { - loop_info.calls = 0; - loop_info.invariant_loads = 0; - loop_info.loads = 0; - loop_info.stores = 0; - loop_info.opnodes_n = 0; - loop_info.blocks = 0; + inc_irg_visited(current_ir_graph); - DB((dbg, LEVEL_1, " >>>> current loop includes node %ld <<<\n", get_irn_node_nr(get_loop_node(loop, 0)))); + 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); - decision_maker(); + copy_walk_n(pred, is_in_loop, c + 1); + } + } - DB((dbg, LEVEL_1, " <<<< end of loop with node %ld >>>>\n", get_irn_node_nr(get_loop_node(loop, 0)))); + ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); } -/* Find most inner loops and send them to analyze_loop */ -static void analyze_inner_loop(ir_loop *loop) + +/* 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 *node, ir_node *be_block) { - /* descend into sons */ - int sons = get_loop_n_sons(loop); + ir_node **ins; + int arity = get_irn_arity(node); + int i, c = 0; - if (sons==0) { - analyze_loop(loop); - } else { - int s; - for(s=0; s 0 + */ + ins[0] = x_true; + ins[1] = x_false; + + count_block = new_r_Block(irg, 2, ins); + + /* 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_r_Const(irg, get_mode_null(mode)); + /* ems % step != 0 : +1 */ + false_val = new_r_Const(irg, get_mode_one(mode)); + } else { + tarval *tv_two = new_tarval_from_long(2, mode); + /* ems % step == 0 : +1 */ + true_val = new_r_Const(irg, get_mode_one(mode)); + /* ems % step != 0 : +2 */ + false_val = new_r_Const(irg, tv_two); + } + + ins[0] = true_val; + ins[1] = false_val; + + correction = new_r_Phi(count_block, 2, ins, mode); + + count = new_r_Proj(ems_divmod, mode, pn_DivMod_res_div); + + /* (end - start) / step + correction */ + count = new_r_Add(count_block, 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_X, pn_Cmp_Lt); + } else { + bad_count_neg = new_r_Proj(cmp_bad_count, mode_X, pn_Cmp_Gt); + } + + bad_count_neg = new_r_Cond(count_block, bad_count_neg); + good_count = new_r_Proj(bad_count_neg, mode_X, pn_Cond_true); + bad_count = new_r_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_r_Block(irg, 2, ins); + + /* Matze: I commented this line out because I was in the process of + * removing the Abs node. I don't understand that line at all anyway + * since no other code here checks for the presence of an Abs or creates + * one. So how can we know here that "count" is an Abs node... */ +#if 0 + /* count wants to be positive */ + ins[0] = get_Abs_op(count); +#endif + /* Manually feed the aforementioned count = 1 (bad case)*/ + ins[1] = new_r_Const(irg, get_mode_one(mode)); + count_phi = new_r_Phi(duff_block, 2, ins, mode); + + unroll_c = new_r_Const(irg, new_tarval_from_long((long)unroll_nr, mode)); + + /* count % unroll_nr */ + duff_mod = new_r_Mod(duff_block, + new_r_NoMem(irg), + count_phi, + unroll_c, + mode, + op_pin_state_pinned); + + proj = new_r_Proj(duff_mod, mode_X, pn_Mod_res); + 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. */ -void loop_optimization(ir_graph *irg) +static unsigned is_loop_invariant_def(ir_node *node) { - ir_loop *loop; - int sons, nr; + int i; - DB((dbg, LEVEL_1, " >>> loop optimization (Startnode %ld) <<<\n", get_irn_node_nr(get_irg_start(irg)))); + if (! is_in_loop(node)) + return 1; - /* Init */ - link_node_state_list = NULL; + /* 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); - /* preconditions */ - ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); - collect_phiprojs(irg); - ir_free_resources(irg, IR_RESOURCE_IRN_LINK); + /* To prevent unexpected situations. */ + if (block != loop_head) + return 0; - set_current_ir_graph(irg); - assure_cf_loop(irg); + for (i = 0; i < get_irn_arity(node); ++i) { + /* Check if all bes are just loopbacks. */ + if (is_own_backedge(block, i) && get_irn_n(node, i) != node) + return 0; + } + } + return 1; +} - /* allocate node_info for additional information on nodes */ - ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK); - irg_walk_graph(current_ir_graph, alloc_node_info, NULL, NULL); +/* 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); - loop = get_irg_loop(irg); - sons = get_loop_n_sons(loop); + *invar_pred = NULL; + *other = NULL; - for (nr=0; nr>> loop optimization done (Startnode %ld)<<<\n", get_irn_node_nr(get_irg_start(irg)))); + *other = pred0; + *invar_pred = pred1; + return 1; + } else { + return 0; + } } -void firm_init_loop(void) { +/* 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 = loop_info.add; + int arity = get_irn_arity(iteration_phi); + + DB((dbg, LEVEL_4, "Find start and add from %N\n", iteration_phi)); + + for (i = 0; i < arity; ++i) { + + /* 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); + + DB((dbg, LEVEL_4, "found_start_val %N\n", found_start_val)); + + /* 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; + + 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; + } + } + + loop_info.add = found_add; + + return 1; +} + + +/* 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) +{ + ir_node *pred0 = get_irn_n(node, 0); + ir_node *pred1 = get_irn_n(node, 1); + + DB((dbg, LEVEL_4, "Checking for constant pred of %N\n", node)); + + *const_pred = NULL; + *other = NULL; + + /*DB((dbg, LEVEL_4, "is %N const\n", pred0));*/ + if (is_Const(pred0) || is_SymConst(pred0)) { + DB((dbg, LEVEL_1, "%N is constant\n", 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) { + DB((dbg, LEVEL_1, "%N is ALSO constant\n", pred1)); + /* RETURN. We do not want both preds to be constant. */ + return 0; + } + + DB((dbg, LEVEL_4, "%N is constant\n", pred1)); + *other = pred0; + *const_pred = pred1; + } + + if (*const_pred == NULL) + return 0; + else + return 1; +} + +/* Returns the mathematically inverted pn_Cmp. */ +static pn_Cmp get_math_inverted_case(pn_Cmp proj) +{ + switch(proj) { + case pn_Cmp_Eq: + return pn_Cmp_Lg; + case pn_Cmp_Lg: + return pn_Cmp_Eq; + case pn_Cmp_Lt: + return pn_Cmp_Ge; + case pn_Cmp_Le: + return pn_Cmp_Gt; + case pn_Cmp_Gt: + return pn_Cmp_Le; + case pn_Cmp_Ge: + return pn_Cmp_Lt; + default: + panic("Unhandled pn_Cmp."); + } +} + +/* norm_proj means we do not exit the loop. */ +static unsigned simulate_next(tarval **count_tar, + tarval *stepped, tarval *step_tar, tarval *end_tar, pn_Cmp norm_proj) +{ + tarval *next; + + DB((dbg, LEVEL_1, "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_1, "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_1, "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_1, "Loop taken if %ld %s %ld ", + get_tarval_long(next), + get_pnc_string(norm_proj), + get_tarval_long(end_tar))); + DB((dbg, LEVEL_1, "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; + unsigned loop_depth, max_loop_nodes_adapted; + 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")); + +#if 0 + /* Ignore loop size. Probably not wise in other than testcases. */ + (void) max_loop_nodes_adapted; + (void) loop_depth; + + loop_info.max_unroll = 6; +#else + /* Calculate maximum unroll_nr keeping node count below limit. */ + loop_depth = get_loop_depth(cur_loop) - 1; + max_loop_nodes_adapted = get_max_nodes_adapted(loop_depth); + + loop_info.max_unroll = opt_params.max_loop_size / 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", + loop_info.max_unroll)); + + 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); + + 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; + tarval *start_tar, *step_tar; + ir_mode *mode; + + /* RETURN if loop is not 'simple' */ + projres = is_simple_loop(); + if (projres == NULL) + return 0; + + loop_condition = get_irn_n(projres, 0); + + success = get_invariant_pred(loop_condition, &loop_info.end_val, &iteration_path); + 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, "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 %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, "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 %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 %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); + start_tar = get_Const_tarval(loop_info.start_val); + + 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(tarval *count_tar) +{ + 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 split. */ +static unsigned get_unroll_decision_constant(void) +{ + ir_node *projres, *loop_condition, *iteration_path; + unsigned success, is_latest_val; + 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. => 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 | + \ | \__| + cond + /\ + */ + + loop_condition = get_irn_n(projres, 0); + + 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; + + loop_info.add = iteration_path; + DB((dbg, LEVEL_4, "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, constant); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got start %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, "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; + + 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)); + + 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_1, "Loop is endless or never taken.")); + /* TODO Might be worth a warning. */ + return 0; + } + + count_stats(stats.u_simple_counting_loop); + + loop_info.latest_value = is_latest_val; + + /* TODO split here + if (! is_simple_counting_loop(&count_tar)) + return 0; + */ + + /* stepped can be negative, if step < 0 */ + stepped = tarval_mul(count_tar, step_tar); + + /* 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))); + + proj_proj = get_Proj_proj(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); +} + +/** + * Loop unrolling + */ +static void unroll_loop(void) +{ + unroll_nr = 0; + + /* get_unroll_decision_constant and invariant are completely + * independent for flexibility. + * Some checks may be performed twice. */ + + /* constant case? */ + if (opt_params.allow_const_unrolling) + unroll_nr = get_unroll_decision_constant(); + if (unroll_nr > 1) { + loop_info.unroll_kind = constant; + + } else { + /* invariant case? */ + if (opt_params.allow_invar_unrolling) + unroll_nr = get_unroll_decision_invariant(); + if (unroll_nr > 1) + loop_info.unroll_kind = invariant; + } + + DB((dbg, LEVEL_1, " *** Unrolling %d times ***\n", unroll_nr)); + + if (unroll_nr > 1) { + loop_entries = NEW_ARR_F(entry_edge, 0); + + /* Get loop outs */ + irg_walk_graph(current_ir_graph, get_loop_entries, NULL, NULL); + + if ((int)get_tarval_long(loop_info.count_tar) == unroll_nr) + loop_info.needs_backedge = 0; + else + loop_info.needs_backedge = 1; + + /* 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*/ + irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL); + + /* dump_ir_block_graph(current_ir_graph, "-DONE"); */ + + 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); + } + +} + +/* Analyzes the loop, and checks if size is within allowed range. + * Decides if loop will be processed. */ +static void init_analyze(ir_loop *loop) +{ + /* Expect no benefit of big loops. */ + /* TODO tuning/make parameter */ + int loop_depth; + unsigned max_loop_nodes = opt_params.max_loop_size; + unsigned max_loop_nodes_adapted; + int max_calls = opt_params.allowed_calls; + int depth_adaption = opt_params.depth_adaption; + + cur_loop = loop; + + loop_head = NULL; + loop_head_valid = 1; + + /* Reset loop info */ + memset(&loop_info, 0, sizeof(loop_info_t)); + + DB((dbg, LEVEL_1, " >>>> current loop includes node %N <<<\n", + get_loop_node(loop, 0))); + + /* Collect loop informations: head, node counts. */ + irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL); + + /* Depth of 0 is the procedure and 1 a topmost loop. */ + loop_depth = get_loop_depth(loop) - 1; + + /* Calculating in per mil. */ + max_loop_nodes_adapted = get_max_nodes_adapted(loop_depth); + + 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, max_calls)); + count_stats(stats.calls_limit); + return; + } +#endif + + /* RETURN if there is no valid head */ + if (!loop_head || !loop_head_valid) { + DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n")); + return; + } else { + DB((dbg, LEVEL_1, "Loophead: %N\n", loop_head)); + } + + switch (loop_op) { + case loop_op_inversion: + loop_inversion(); + break; + + case loop_op_unrolling: + unroll_loop(); + break; + + default: + panic("Loop optimization not implemented."); + } + DB((dbg, LEVEL_1, " <<<< end of loop with node %N >>>>\n", + get_loop_node(loop, 0))); +} + +/* Find innermost loops and add them to loops. */ +static void find_innermost_loop(ir_loop *loop) +{ + /* descend into sons */ + int sons = get_loop_n_sons(loop); + + if (sons == 0) { + ARR_APP1(ir_loop *, loops, loop); + } else { + int s; + for (s=0; s>> unrolling (Startnode %N) <<<\n", + get_irg_start(irg))); + + loop_optimization(irg); + + DB((dbg, LEVEL_1, " >>> unrolling done (Startnode %N) <<<\n", + get_irg_start(irg))); +} + +void do_loop_inversion(ir_graph *irg) +{ + loop_op = loop_op_inversion; + + DB((dbg, LEVEL_1, " >>> inversion (Startnode %N) <<<\n", + get_irg_start(irg))); + + loop_optimization(irg); + + DB((dbg, LEVEL_1, " >>> inversion done (Startnode %N) <<<\n", + get_irg_start(irg))); +} + +void do_loop_peeling(ir_graph *irg) +{ + loop_op = loop_op_peeling; + + DB((dbg, LEVEL_1, " >>> peeling (Startnode %N) <<<\n", + get_irg_start(irg))); + + loop_optimization(irg); + + DB((dbg, LEVEL_1, " >>> peeling done (Startnode %N) <<<\n", + get_irg_start(irg))); + +} + +ir_graph_pass_t *loop_inversion_pass(const char *name) +{ + return def_graph_pass(name ? name : "loop_inversion", do_loop_inversion); +} + +ir_graph_pass_t *loop_unroll_pass(const char *name) +{ + return def_graph_pass(name ? name : "loop_unroll", do_loop_unrolling); +} + +ir_graph_pass_t *loop_peeling_pass(const char *name) +{ + return def_graph_pass(name ? name : "loop_peeling", do_loop_peeling); +} + +void firm_init_loop_opt(void) +{ FIRM_DBG_REGISTER(dbg, "firm.opt.loop"); }