X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=34139aa2487a4ccf4e524952e2bb17fc220b17aa;hb=ce6161a7e42a48f7422b7babcc64d8ace18e2687;hp=3f95d9c188c287111dc94b7d33913c2ace55e890;hpb=b0196335c375cbed13e8e1fea996a7651885db18;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index 3f95d9c18..34139aa24 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,515 +19,363 @@ /** * @file - * @brief Loop peeling and unrolling * @author Christian Helmer + * @brief loop inversion and loop unrolling + * * @version $Id$ */ -//#include "config.h" - -//#include -#include +#include "config.h" +#include "iroptimize.h" +#include "opt_init.h" #include "irnode.h" -#include "irnode_t.h" -#include "irgraph_t.h" -//#include "irprog_t.h" +#include "debug.h" +#include "error.h" -//#include "iroptimize.h" -#include "ircons_t.h" -#include "iropt_t.h" +#include "ircons.h" #include "irgopt.h" -//#include "irgmod.h" +#include "irgmod.h" #include "irgwalk.h" - -//#include "array_t.h" -#include "list.h" -//#include "pset.h" -//#include "pmap.h" -//#include "pdeq.h" -//#include "xmalloc.h" -//#include "pqueue.h" - #include "irouts.h" -#include "irloop_t.h" -#include "irbackedge_t.h" -//#include "opt_inline_t.h" -//#include "cgana.h" -//#include "trouts.h" -//#include "error.h" - -//#include "analyze_irg_args.h" -#include "iredges_t.h" -//#include "irflag_t.h" -//#include "irhooks.h" +#include "iredges.h" #include "irtools.h" -//#include "iropt_dbg.h" -#include "irpass_t.h" -#include "irloop.h" - #include "array_t.h" -#include "irdump.h" - -/* convenience macro for iterating over every phi node of the given block */ -#define for_each_phi(block, phi) \ - for ( (phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next( (phi) ) ) - -/* current loop */ -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 *); - -/* stores pair of node and number for the nodes predecessor */ -typedef struct loop_entry_t { - ir_node *node; /* node outside of the loop */ - int pred_irn_n; /* with pred_irn_n pointing inside loop */ - //loop_entry_t *next; -} loop_entry_t; - -//loop_entry_t loop_entry_list; - -/* Store complex values in the nodes link */ -typedef struct link_node_state_t { - unsigned cloned:1; - unsigned temp:1; /* < Node is temporarily copied, to resolve cycles */ - 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 */ -} link_node_state_t; - - -loop_entry_t *loop_entries; /* loop entries (from below) in the node graph */ -//int loop_entries_n; -loop_entry_t *head_entries; /* loop entries (from below) in the node graph */ -int backedges_n; -//loop_entry_t *backedges; /* backedges exclusively from the current loop */ -//loop_entry_t *alien_backedges; /* The head can be head of several loops. */ -//loop_entry_t *head_edges; /* The head can be head of several loops. */ - -ir_node *loop_cf_head = NULL; /* loop exit in the node graph */ -unsigned loop_cf_head_valid = 1; /* a loop may/must have one head, otherwise invalid */ - -unsigned has_sto; /* If we store inside the loop we might - * have disambiguation problems */ -//DBG -//void arrdump(ir_node **arr) -//{ -// int i; -// for (i=0; inode_nr), is_Block(arr[i])); -// } -//} +#include "beutil.h" +#include "irpass.h" +#include "irdom.h" -/** - * Returns the state of the given node. - */ -link_node_state_t *get_lstate(ir_node *n) -{ - return ((link_node_state_t *)n->link); -} +#include +#include "irbackedge_t.h" +#include "irphase_t.h" +#include "irloop_t.h" -/** - * Returns the link inside of the nodes state which is pointing to its copy - * most of the time during loop peeling. - */ -ir_node *get_copy(ir_node *n) -{ - return ((link_node_state_t *)n->link)->copy; -} -/** - * Sets the nodes copy information - */ -void set_copy(ir_node *n, ir_node *copy) -{ - ((link_node_state_t *)n->link)->copy = copy; -} +DEBUG_ONLY(static firm_dbg_module_t *dbg); -/** - * Returns true if the node or block is in cur_loop. - */ -unsigned is_in_loop(ir_node *node) -{ -// if (is_Block(node)) { -// if (node->loop == cur_loop) { -// printf(" INLOOP %ld \n", node->node_nr); -// } -// return (node->loop == cur_loop); -// } else { -// if ( get_nodes_block(node)->loop == cur_loop ) { -// printf(" INLOOP %ld \n", node->node_nr); -// } -// return ( get_nodes_block(node)->loop == cur_loop ); -// } - if (is_Block(node)) { - return (node->loop == cur_loop); - } else { - return ( get_nodes_block(node)->loop == cur_loop ); - } -} +/* DBG print stats for every procedure. */ +#define LOOP_OPT_STATS 1 -unsigned is_in_head(ir_node *node) -{ - if (is_Block(node)) { - return (node == loop_cf_head); - } else { - return ( get_nodes_block(node) == loop_cf_head ); - } -} +/* DBG: Ignore node limits and process every possible loop. */ +#define LOOP_IGNORE_NODE_LIMITS 0 /** - * Returns if the given be is an alien edge + * Convenience macro for iterating over every phi node of the given block. + * Requires phi list per block. */ -unsigned is_alien_edge(ir_node *n, int i) -{ - return( !is_in_loop( get_irn_n( n, i ) ) ); -} +#define for_each_phi(block, phi) \ + for ((phi) = get_Block_phis( (block) ); (phi) ; (phi) = get_Phi_next((phi))) -static void add_pred(ir_node* node, ir_node* x) -{ - ir_node** ins; - int n; - int i; +#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) -// if(!node) -// printf("NONODE\n"); +/* Currently processed loop. */ +static ir_loop *cur_loop; - //printf("addpred %ld pred %ld \n", node->node_nr, x->node_nr); +/* Flag for kind of unrolling. */ +typedef enum { + constant, + invariant +} unrolling_kind_flag; - // WHY limit it to blocks and phi? - assert(is_Block(node) || is_Phi(node)); +/* Condition for performing visiting a node during copy_walk. */ +typedef unsigned walker_condition(ir_node *); - n = get_irn_arity(node); - NEW_ARR_A(ir_node*, ins, n + 1); - for (i = 0; i < n; i++) - ins[i] = get_irn_n(node, i); - ins[n] = x; - set_irn_in(node, n + 1, ins); -} +/* Node and position of a predecessor. */ +typedef struct entry_edge { + ir_node *node; + int pos; + ir_node *pred; +} entry_edge; -void block_phi_walker(ir_node *n, void *env) -{ - const ir_edge_t *edge; - (void) env; +/* Node info for unrolling. */ +typedef struct unrolling_node_info { + ir_node **copies; +} unrolling_node_info; - /* RETURN */ - if (!is_Block(n)) - return; +/* Outs of the nodes head. */ +static entry_edge *cur_head_outs; - /* generate phi list for every block */ - n->attr.block.phis = NULL; +/* Information about the loop head */ +static ir_node *loop_head = NULL; +static unsigned loop_head_valid = 1; - foreach_out_edge(n, edge) { - ir_node *src = get_edge_src_irn(edge); - if (is_Phi(src)) - { - //printf("%ld has phi %ld \n", block->node_nr, src->node_nr); - add_Block_phi(n, src); - } - } -} +/* List of all inner loops, that are processed. */ +static ir_loop **loops; -/** - * Calls func() for every block in the given loop. - */ -void for_each_loop_block(ir_loop *loop, irg_walk_func *func, void *env) -{ - int elements, e; - elements = get_loop_n_elements(loop); +#if LOOP_OPT_STATS - for(e=0; enode_nr); - func(elem.node, env); - } - } -} +#define count_stats(val) (++val) +#define print_stats() (do_print_stats()) +#define reset_stats() (do_reset_stats()) -/** - * collects the blocks backedges and creates the phi list for every block - */ -void collect_backedges(ir_node *block, void *env) -{ - (void) env; +/* Stats */ +typedef struct loop_stats_t { + unsigned loops; + unsigned inverted; + unsigned too_large; + unsigned too_large_adapted; + unsigned cc_limit_reached; + unsigned calls_limit; - //printf("LOOP BLOCK %ld\n", block->node_nr); + unsigned u_simple_counting_loop; + unsigned constant_unroll; + unsigned invariant_unroll; - /* collect backedges */ - if (has_backedges(block)) - { - int i; - int arity = get_irn_arity(block); + unsigned unhandled; +} loop_stats_t; - for(i = 0; i < arity; ++i) { - ir_node *pred = get_irn_n(block, i); +static loop_stats_t stats; - loop_entry_t be; - be.node = block; - be.pred_irn_n = i; +/* Set stats to sero */ +static void do_reset_stats(void) +{ + memset(&stats, 0, sizeof(loop_stats_t)); +} - //ARR_APP1(loop_entry_t, head_edges, be); +/* Print stats */ +static void do_print_stats(void) +{ + 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) + +#endif + +/* Commandline parameters */ +typedef struct loop_opt_params_t { +unsigned max_loop_size; /* Maximum number of nodes [nodes]*/ +int depth_adaption; /* Loop nest depth adaption [percent] */ +unsigned allowed_calls; /* Number of calls allowed [number] */ +unsigned count_phi:1; /* Count phi nodes */ +unsigned count_proj:1; /* Count projections */ + +unsigned max_cc_size; /* Maximum condition chain size [nodes] */ +unsigned max_branches; + +unsigned max_unrolled_loop_size; /* [nodes] */ +unsigned allow_const_unrolling:1; +unsigned allow_invar_unrolling:1; +unsigned invar_unrolling_min_size; /* [nodes] */ + +} loop_opt_params_t; + +static loop_opt_params_t opt_params; + +/* Loop analysis informations */ +typedef struct loop_info_t { + unsigned nodes; /* node count */ + unsigned ld_st; /* load and store nodes */ + unsigned branches; /* number of conditions */ + unsigned calls; /* number of calls */ + unsigned cf_outs; /* number of cf edges which leave the loop */ + entry_edge cf_out; /* single loop leaving cf edge */ + int be_src_pos; /* position of the single own backedge in the head */ + + /* for inversion */ + unsigned cc_size; /* nodes in the condition chain */ + + /* for unrolling */ + unsigned max_unroll; /* Number of unrolls satisfying max_loop_size */ + unsigned exit_cond; /* 1 if condition==true exits the loop. */ + unsigned latest_value:1; /* 1 if condition is checked against latest counter value */ + unsigned needs_backedge:1; /* 0 if loop is completely unrolled */ + unsigned decreasing:1; /* Step operation is_Sub, or step is<0 */ + + /* IV informations of a simple loop */ + ir_node *start_val; + ir_node *step; + ir_node *end_val; + ir_node *iteration_phi; + ir_node *add; + + ir_tarval *count_tar; /* Number of loop iterations */ + + ir_node *duff_cond; /* Duff mod */ + unrolling_kind_flag unroll_kind; /* constant or invariant unrolling */ +} loop_info_t; + +/* Information about the current loop */ +static loop_info_t loop_info; + +/* 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) +{ + double perc = 100.0 + (double)opt_params.depth_adaption; + double factor = pow(perc / 100.0, depth); - if (is_backedge(block, i) ) - { - if ( is_in_loop(pred) ) { - //printf("be: %ld --> %ld \n", block->node_nr, pred->node_nr); - //ARR_APP1(loop_entry_t, backedges, be); - ++backedges_n; - } -// else { -// //printf("alien be: %ld --> %ld \n", block->node_nr, pred->node_nr); -// ARR_APP1(loop_entry_t, alien_backedges, be); -// } - } -// else { -// if ( !is_in_loop(pred) ) { -// ARR_APP1(loop_entry_t, head_edges, be); -// } + return (int)((double)opt_params.max_loop_size * factor); +} - } - } +/* Reset nodes link. For use with a walker. */ +static void reset_link(ir_node *node, void *env) +{ + (void)env; + set_irn_link(node, NULL); } -/** - * Walks through all loop nodes. - */ -unsigned loop_walker_rec(ir_node *node, - 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; - unsigned stop = 0; + return (get_irn_loop(get_block(node)) == cur_loop); +} - ir_graph *irg = current_ir_graph; +/* Returns 0 if the given edge is not a backedge + * with its pred in the cur_loop. */ +static unsigned is_own_backedge(ir_node *n, int pos) +{ + return (is_backedge(n, pos) && is_in_loop(get_irn_n(n, pos))); +} - /* RETURN if we walked out of the loop*/ - if (!is_in_loop(node)) - return 0; +/* Finds loop head and some loop_info as calls or else if necessary. */ +static void get_loop_info(ir_node *node, void *env) +{ + unsigned node_in_loop, pred_in_loop; + int i, arity; + (void)env; - if (pre) - { - unsigned stop = pre(node, env); - if (stop) - return stop; - } + arity = get_irn_arity(node); + for (i = 0; i < arity; i++) { + ir_node *pred = get_irn_n(node, i); - set_irn_visited(node, irg->visited); + pred_in_loop = is_in_loop(pred); + node_in_loop = is_in_loop(node); - if (node->op != op_Block) { - ir_node *pred = get_irn_n(node, -1); - if (pred->visited < irg->visited) + if (!node_in_loop && pred_in_loop && is_Block(node)) { - stop = loop_walker_rec(pred, pre, post, env); - if (stop) - return stop; + entry_edge entry; + entry.node = node; + entry.pos = i; + entry.pred = pred; + /* Count cf outs */ + ++loop_info.cf_outs; + loop_info.cf_out = entry; } - } - for (i = get_irn_arity(node) - 1; i >= 0; --i) { - ir_node *pred = get_irn_n(node, i); - if (pred->visited < irg->visited) - { - stop = loop_walker_rec(pred, pre, post, env); - if (stop) - return stop; - } - } + /* collect some loop information */ + if (node_in_loop) { + if (is_Phi(node) && opt_params.count_phi) + ++loop_info.nodes; + else if (is_Proj(node) && opt_params.count_proj) + ++loop_info.nodes; + else if (!is_Confirm(node) && !is_Const(node) && !is_SymConst(node)) + ++loop_info.nodes; - if (post) - return post(node, env); - return 0; -} + if (is_Load(node) || is_Store(node)) + ++loop_info.ld_st; -/** - * Walks through loop nodes. - * The entries of the loop (all edges pointing into the loop) have to be given. - */ -unsigned loop_walker(loop_entry_t *entries, - irg_walk_func_abortable *pre, irg_walk_func_abortable *post, void * env) -{ - int i; - int stop = 0; + if (is_Call(node)) + ++loop_info.calls; - for (i=0; !stop && i 1) + ++loop_info.branches; + + if (node_in_loop && !pred_in_loop && loop_head_valid) { + ir_node *cfgpred = get_Block_cfgpred(node, i); + + if (!is_in_loop(cfgpred)) { + DB((dbg, LEVEL_5, "potential head %+F because inloop and pred %+F not inloop\n", + node, pred)); + /* another head? We do not touch this. */ + if (loop_head && loop_head != node) { + loop_head_valid = 0; + } else { + loop_head = node; + } + } + } + } } - return stop; } -/** - * - */ -void find_loop_entries_walk(ir_node *node, void *env) +/* Finds all edges with users outside of the loop + * and definition inside the loop. */ +static void get_loop_entries(ir_node *node, void *env) { unsigned node_in_loop, pred_in_loop; + int i, arity; (void) env; - int i, arity; arity = get_irn_arity(node); - for (i = 0; i < arity; i++) { + for (i = 0; i < arity; ++i) { ir_node *pred = get_irn_n(node, i); pred_in_loop = is_in_loop(pred); node_in_loop = is_in_loop(node); - //Find the loops head/the blocks with cfpred outside of the loop - if (is_Block(node) && node_in_loop - && !pred_in_loop && loop_cf_head_valid) - { - ir_node *cfgpred = get_Block_cfgpred(node, i); - - if ( !is_in_loop(cfgpred) ) - { - // another head? We do not touch this. - // is this possible? - if (loop_cf_head && loop_cf_head != node) - { - loop_cf_head_valid = 0; - } - else - { - loop_cf_head = node; - } - } - } - - if ( pred_in_loop && !node_in_loop ) - { - /* we walked right into the loop. */ - loop_entry_t entry; + if (pred_in_loop && !node_in_loop) { + entry_edge entry; entry.node = node; - entry.pred_irn_n = i; - - //DBG -// printf("inloop: %ld --> inloop %ld (@ %d) \n", -// node->node_nr, pred->node_nr, i); - - ARR_APP1(loop_entry_t, loop_entries, entry); + entry.pos = i; + entry.pred = pred; + ARR_APP1(entry_edge, loop_entries, entry); } } } -///** -// * Finds invariant nodes and marks them as invariant. -// * (Post walk) -// */ -//unsigned get_invariants(ir_node *node, void *env) -//{ -// unsigned invar = 1; -// (void) env; -// -// if (is_Store(node)) -// { -// has_sto = 1; -// /* RETURN and abort walker */ -// return 1; -// } -// -// int arity = get_irn_arity(node); -// -// /* RETURN, no preds to visit */ -// if (arity == 0) return 0; -// -// if (is_Load(node)) -// { -// assert(arity>=2 && "expected load to have edge nr 1 (address)"); -// -// ir_node *pred = get_irn_n(node, 1); -// if (!is_in_loop(pred) /* Everything outside the loop is considered invariant */ -// || is_Const(pred) /* This is not true, but we also want the quasi-invariants. */ -// || is_SymConst(pred) -// || get_lstate(node)->invariant) -// { -// //printf("## CONSTLOAD: %ld \n", node->node_nr); -// get_lstate(node)->invariant = 1; -// } else -// { -// get_lstate(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); -// -// if ( !(!is_in_loop(pred) /* outside loop is loop invariant */ -// || is_Const(pred) /* constants */ -// || is_SymConst(pred) /* SymConst, if no Store */ -// || get_lstate(node)->invariant /* pred is marked as invariant */ -// ) ) -// { -// invar = 0; -// } -// } -// -// if (invar) { -// printf("const: %ld \n", node->node_nr); -// get_lstate(node)->invariant = 1; -// } else { -// get_lstate(node)->invariant = 0; -// } -//// DBG -//// if (!is_nodes_block_marked(pred)) { -//// //printf("pred outloop: %ld, pred %ld (const)\n", node->node_nr, pred->node_nr); -//// } else if (is_Const(pred) || is_SymConst(pred)) // || is_Phi(pred)) { -//// //printf("predconst: %ld, pred %ld CONST\n", node->node_nr, pred->node_nr); -//// } else if (pred->link == MARKED_CONST) { -//// //printf("predmarked: %ld, pred %ld const\n", node->node_nr, pred->node_nr); -//// } else { -//// mark=0; -//// } -// } -// return 0; -//} - -////TODO DBG Remove -//void phifix(ir_node *node, ir_node *newpred) -//{ -// ir_node *phi=get_Block_phis(node); -// while(phi) -// { -// int pa = get_irn_arity(phi); -// int ba = get_irn_arity(node); -// -// -// -// while(ba>pa) -// { -// printf("!!!!!!!!!! block has %d, phi had %d\n", ba, pa ); -// add_pred(phi, newpred); -// pa++; -// printf("!!!!!!!!!! block has %d, phi has now %d\n", ba, pa ); -// } -// phi=get_Phi_next(phi); -// } -//} - +/* ssa */ static ir_node *ssa_second_def; static ir_node *ssa_second_def_block; /** - * + * Walks the graph bottom up, searching for definitions and creates phis. */ -static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, - int first) +static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, int first) { int i; int n_cfgpreds; @@ -535,22 +383,24 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, ir_node *phi; ir_node **in; - /* This is needed because we create bads sometimes */ - if (is_Bad(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)) { + DB((dbg, LEVEL_5, "ssa bad %N\n", block)); return new_Bad(); + } - /* the other defs can't be marked for cases where a user of the original - * value is in the same block as the alternative definition. - * In this case we mustn't use the alternative definition. - * So we keep a flag that indicated wether we walked at least 1 block - * away and may use the alternative definition */ 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_lstate(block)->link; + ir_node *value = (ir_node *) get_irn_link(block); + DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value)); return value; } @@ -561,57 +411,72 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, n_cfgpreds = get_Block_n_cfgpreds(block); if (n_cfgpreds == 1) { ir_node *pred_block = get_Block_cfgpred_block(block, 0); - ir_node *value = search_def_and_create_phis(pred_block, mode, 0); + ir_node *value; + + DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block)); - get_lstate(block)->link = value; - //set_irn_link(block, value); + value = search_def_and_create_phis(pred_block, mode, 0); + set_irn_link(block, value); mark_irn_visited(block); + return value; } /* create a new Phi */ NEW_ARR_A(ir_node*, in, n_cfgpreds); - for(i = 0; i < n_cfgpreds; ++i) + for (i = 0; i < n_cfgpreds; ++i) in[i] = new_Unknown(mode); phi = new_r_Phi(block, n_cfgpreds, in, mode); - //set_irn_link(block, phi); - get_lstate(block)->link = phi; + /* Important: always keep block phi list up to date. */ + add_Block_phi(block, phi); + DB((dbg, LEVEL_5, "ssa phi creation: link new phi %N to block %N\n", phi, block)); + set_irn_link(block, phi); mark_irn_visited(block); /* 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, 0); + 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; const ir_edge_t *edge; const ir_edge_t *next; - /* no need to do anything */ + assert(orig_block && orig_val && second_block && second_val && + "no parameter of construct_ssa may be NULL"); + if (orig_val == second_val) return; irg = get_irn_irg(orig_val); + + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); inc_irg_visited(irg); mode = get_irn_mode(orig_val); - get_lstate(orig_block)->link = orig_val; - //set_irn_link(orig_block, orig_val); + set_irn_link(orig_block, orig_val); mark_irn_visited(orig_block); ssa_second_def_block = second_block; @@ -628,7 +493,7 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, if (is_End(user)) continue; - //DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j))); + DB((dbg, LEVEL_5, "original user %N\n", user)); if (is_Phi(user)) { ir_node *pred_block = get_Block_cfgpred_block(user_block, j); @@ -636,169 +501,209 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, } else { newval = search_def_and_create_phis(user_block, mode, 1); } - - /* don't fix newly created Phis from the SSA construction */ - if (newval != user) { - //DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval)); + if (newval != user && !is_Bad(newval)) set_irn_n(user, j, newval); - } } + + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); } +/***** Unrolling Helper Functions *****/ -/** - * Rewires the heads after peeling. This results in a tail-controlled loop. - */ -void fix_head(ir_node *loophead) +/* Assign the copy with index nr to node n */ +static void set_unroll_copy(ir_node *n, int nr, ir_node *cp) { - int headarity = get_irn_arity(loophead); - int i; - ir_node **loopheadnins; - ir_node **peelheadnins; - ir_node *phi; - ir_node *peelhead = get_copy(loophead); - int lheadin_c = 0; - int pheadin_c = 0; - - /** - * the loopheads new preds are: - * its own backedge(s) and the former backedge(s) of the peeled code - */ - int lhead_arity = 2 * backedges_n; //ARR_LEN(backedges); - int phead_arity = headarity - backedges_n; //ARR_LEN(backedges); + unrolling_node_info *info; + assert(nr != 0 && "0 reserved"); - /** We assume the worst case, in which every head entry - * origins from the same node. +1 for a null terminated list. - */ - //int tchead_arity = ARR_LEN(head_entries) + ( headarity - backedges_n) + 1 ; + info = (unrolling_node_info *)phase_get_irn_data(phase, n); + if (! info) { + ir_node **arr; - NEW_ARR_A(ir_node *, loopheadnins, lhead_arity ); - NEW_ARR_A(ir_node *, peelheadnins, phead_arity ); + 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 *)); - phi = get_Block_phis(loophead); - while(phi) { - NEW_ARR_A(ir_node *, get_lstate(phi)->ins, lhead_arity); - phi=get_Phi_next(phi); + phase_set_irn_data(phase, n, info); } + /* Original node */ + info->copies[0] = n; - phi = get_Block_phis(peelhead); - while(phi) - { - NEW_ARR_A(ir_node *, get_lstate(phi)->ins, phead_arity); - phi=get_Phi_next(phi); - } + info->copies[nr] = cp; +} - for (i = 0; i < headarity; i++) - { - ir_node *phi; - ir_node *orgjmp = get_irn_n(loophead, i); - ir_node *copyjmp = get_copy(orgjmp); +/* Returns a nodes copy if it exists, else NULL. */ +static ir_node *get_unroll_copy(ir_node *n, int nr) +{ + ir_node *cp; + unrolling_node_info *info = (unrolling_node_info *)phase_get_irn_data(phase, n); + if (! info) + return NULL; - /** - * Rewire the head blocks ins and their phi ins. - * Requires blocks phi list. - * - * 1. Alien bes origin from the peeled head (new head of the whole loop) - * 2. Loops own bes must be kept/copied to the loophead. - * 3. All other edges origin from the peeled head (new head of the loop) - */ + cp = info->copies[nr]; + return cp; +} - //printf("head i %d\n", i); +/***** Inversion Helper Functions *****/ - if (is_backedge(loophead, i)) - { - if (is_alien_edge(loophead, i)) { - peelheadnins[pheadin_c] = orgjmp; /* alien bes go to the peeled head */ - //set_backedge(peelhead, pheadin_c); - - // alien bes origin at the peeled head - for_each_phi(peelhead, phi) - { - //printf("alienbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n(phi, i)->node_nr); - get_lstate( phi )->ins[pheadin_c] = get_irn_n(phi, i); - } - //printf("alienbe %ld @ %d -> add to peelhead orgjump %ld\n", peelhead->node_nr, i, orgjmp->node_nr); - ++pheadin_c; - } else { - loopheadnins[lheadin_c] = orgjmp; /* keep/copy the loops own bes */ - //set_backedge(loophead, lheadin_c); - - for_each_phi(loophead, phi) { - //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n(phi, i)->node_nr); - get_lstate( phi )->ins[lheadin_c] = get_irn_n(phi, i); - } - //printf("normalbe %ld @ %d -> add to loophead orgjump %ld\n", loophead->node_nr, i, orgjmp->node_nr); - ++lheadin_c; - - loopheadnins[lheadin_c] = copyjmp; /* former bes of the peeled code origin now from the loophead */ - //set_not_backedge(loophead, lheadin_c); - - /* get_irn_n( get_copy_of(phi), i) get_copy_of(get_irn_n( phi, i)) - * Order is crucial! Preds outside of the loop are non existent, like Const. - */ - 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_lstate( phi )->ins[lheadin_c] = get_irn_n( get_copy(phi), i) ; - } - //printf("normalbe %ld @ %d -> add to loophead copyjump %ld\n", loophead->node_nr, i, copyjmp->node_nr); - ++lheadin_c; - } - } else { - peelheadnins[pheadin_c] = orgjmp; - //set_not_backedge(peelhead, pheadin_c); +/* Sets copy cp of node n. */ +static void set_inversion_copy(ir_node *n, ir_node *cp) +{ + phase_set_irn_data(phase, n, cp); +} - for_each_phi(peelhead, phi) { - //printf("edge phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( phi, i)->node_nr); - get_lstate( phi )->ins[pheadin_c] = get_irn_n(phi, i); - } - //printf("edge %ld @ %d -> add to peelhead orgjump %ld\n", peelhead->node_nr, i, orgjmp->node_nr); - ++pheadin_c; +/* 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; +} + +/* Resets block mark for given node. For use with walker */ +static void reset_block_mark(ir_node *node, void * env) +{ + (void) env; + + if (is_Block(node)) + set_Block_mark(node, 0); +} + +/* Returns mark of node, or its block if node is not a block. + * Used in this context to determine if node is in the condition chain. */ +static unsigned is_nodes_block_marked(ir_node* node) +{ + if (is_Block(node)) + return get_Block_mark(node); + else + return get_Block_mark(get_block(node)); +} + +/* Extends a nodes ins by node new. + * NOTE: This is slow if a node n needs to be extended more than once. */ +static void extend_irn(ir_node *n, ir_node *newnode, int new_is_backedge) +{ + ir_node **ins; + int i; + int arity = get_irn_arity(n); + int new_arity = arity + 1; + int *bes; + + NEW_ARR_A(int, bes, new_arity); + NEW_ARR_A(ir_node *, ins, new_arity); + + /* save bes */ + /* Bes are important! + * Another way would be recreating the looptree, + * but after that we cannot distinguish already processed loops + * from not yet processed ones. */ + if (is_Block(n)) { + for(i = 0; i < arity; ++i) { + bes[i] = is_backedge(n, i); } - }/* for */ + bes[i] = new_is_backedge; + } -// printf("pheadin %d arr %d lheadin %d arr %d \n", -// pheadin_c, ARR_LEN(peelheadnins), -// lheadin_c, ARR_LEN(loopheadnins)); + for(i = 0; i < arity; ++i) { + ins[i] = get_irn_n(n, i); + } + ins[i] = newnode; - assert(pheadin_c == ARR_LEN(peelheadnins) && - lheadin_c == ARR_LEN(loopheadnins) && - "the number of head elements does not match the predefined one"); + set_irn_in(n, new_arity, ins); - set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins); - set_irn_in(peelhead, ARR_LEN(peelheadnins), peelheadnins); + /* restore bes */ + if (is_Block(n)) { + for(i = 0; i < new_arity; ++i) { + if (bes[i]) + set_backedge(n, i); + } + } +} - for_each_phi(loophead, phi) { - ir_node **ins = get_lstate( phi )->ins; - set_irn_in(phi, lhead_arity, ins); +/* Extends a block by a copy of its pred at pos, + * fixing also the phis in the same way. */ +static void extend_ins_by_copy(ir_node *block, int pos) +{ + ir_node *new_in; + ir_node *phi; + ir_node *pred; + assert(is_Block(block)); + + /* Extend block by copy of definition at pos */ + pred = get_irn_n(block, pos); + new_in = get_inversion_copy(pred); + DB((dbg, LEVEL_5, "Extend block %N by %N cp of %N\n", block, new_in, pred)); + extend_irn(block, new_in, 0); + + /* Extend block phis by copy of definition at pos */ + for_each_phi(block, phi) { + ir_node *pred, *cp; + + pred = get_irn_n(phi, pos); + cp = get_inversion_copy(pred); + /* If the phis in is not in the condition chain (eg. a constant), + * there is no copy. */ + if (cp == NULL) + new_in = pred; + else + new_in = cp; + + DB((dbg, LEVEL_5, "Extend phi %N by %N cp of %N\n", phi, new_in, pred)); + extend_irn(phi, new_in, 0); } +} - for_each_phi(peelhead, phi) { - ir_node **ins = get_lstate( phi )->ins; - set_irn_in(phi, phead_arity, ins); +/* Returns the number of blocks backedges. With or without alien bes. */ +static int get_backedge_n(ir_node *block, unsigned with_alien) +{ + int i; + int be_n = 0; + int arity = get_irn_arity(block); + + assert(is_Block(block)); + + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(block, i); + if (is_backedge(block, i) && (with_alien || is_in_loop(pred))) + ++be_n; } + return be_n; } -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; - link_node_state_t *cpstate; cp = exact_copy(node); - set_copy(node, cp); - cpstate = XMALLOCZ(link_node_state_t); - cp->link = cpstate; - if (is_Block(cp)) - cp->loop = NULL; /* the copy does not belong to the loop */ - set_irn_visited(cp, current_ir_graph->visited); + 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; } + /** - * Peels the loop by copying the contents. Graph needs some rewiring after that. + * 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. */ -void peel_walk(ir_node *node) +static void copy_walk(ir_node *node, walker_condition *walk_condition, + ir_loop *set_loop) { int i; int arity; @@ -806,426 +711,2160 @@ void peel_walk(ir_node *node) ir_node **cpin; ir_graph *irg = current_ir_graph; - //(void) env; - - link_node_state_t *nodestate = get_lstate(node); - /** * break condition and cycle resolver, creating temporary node copies */ - if (node->visited >= irg->visited) - { - if (!nodestate->cloned && !nodestate->temp) - { - /** temporary clone this node - * because we were here before and would walk into a cycle - */ - rawcopy_node(node); - nodestate->temp=1; + 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 %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; } - //printf(" ----- WALK %ld ----- \n", node->node_nr); - /** - * WALK - */ - set_irn_visited(node, irg->visited); + /* Walk */ + mark_irn_visited(node); - if ( !is_Block(node) ) { - ir_node *pred = get_irn_n(node, -1); - if (is_in_loop(pred)) - peel_walk(pred); + if (!is_Block(node)) { + ir_node *pred = get_nodes_block(node); + if (walk_condition(pred)) + 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); - /* collect head entries */ - if ( is_in_head(pred) && !is_in_head(node) ) - { - loop_entry_t entry; - entry.node = node; - entry.pred_irn_n = i; - ARR_APP1(loop_entry_t, head_entries, entry); - } - - if (is_in_loop(pred)) - { - peel_walk(pred); - cpin[i] = get_copy(pred); //get_lstate(pred)->link; - //printf("copy of %ld gets in %ld", node->node_nr, cpin[i]->node_nr); + if (walk_condition(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; } - //printf("copy of %ld gets in %ld \n", node->node_nr, cpin[i]->node_nr); } - /** - * copy node / finalize temp node - */ - if (!nodestate->temp) { -// if (!is_Const(node) && !is_SymConst(node)) { - cp = rawcopy_node(node); -// } else { -// cp = node; -// //DBG -// printf("CONST FINAL: %ld -F> %ld \n", node->node_nr, cp->node_nr); -// nodestate->link = cp; -// } + /* copy node / finalize temp node */ + if (get_inversion_copy(node) == NULL) { + /* No temporary copy existent */ + 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); // nodestate->link; - //printf("FINALIZE: %ld \n", cp->node_nr); - } - - // special treatment for the head/condition: we need 3 heads for a tail-controlled and peeled loop - if (is_in_head(node)) { - // head/condition for the tail-controlled loop - // These copies are linked to the copies - rawcopy_node(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)); + if (!is_Block(node)) { + ir_node *cpblock = get_inversion_copy(get_nodes_block(node)); - /* set the block of the copy to the copied block */ - //printf(" PRE NODE %ld BLOCK %ld \n", cp->node_nr, get_nodes_block(cp)->node_nr); set_nodes_block(cp, cpblock ); - //printf(" POST NODE %ld BLOCK %ld \n", cp->node_nr, get_nodes_block(cp)->node_nr); - - /* fix the phi information in attr.phis (does not add the phi node to the block) */ - if( is_Phi(cp) ) - { + if (is_Phi(cp)) add_Block_phi(cpblock, cp); - //printf("PHI-BLOCK block %ld got its phi %ld\n", cpblock->node_nr, cp->node_nr); - } - } - else { - /* macroblock info is not copied */ - set_Block_MacroBlock(cp, cp); } - //dbg valid ins? -// for(i=0; inode_nr, cp->node_nr, cpin[i]->node_nr); - + /* Keeps phi list of temporary node. */ set_irn_in(cp, ARR_LEN(cpin), cpin); - -// for(i=0; i< ARR_LEN(cpin); i++) -// { -// printf("ins %ld: %ld \n", cp->node_nr, cpin[i]->node_nr); -// } - -//TODO REM -// if (!nodestate->temp) -// { -// nodestate->link = cp; -// cpstate = XMALLOCZ(link_node_state_t); -// cp->link = cpstate; -// } else { -// /* temporary copy is existent but without correct ins */ -// cp = nodestate->link; -// } - - - nodestate->temp = 0; - nodestate->cloned = 1; } -//void chklink (ir_node *n, void * e) -//{ -// ir_node *link = n->link; -// link_node_state_t *l = (link_node_state_t *)link; -// -// printf("n %ld\n", n->node_nr); -// printf("l p %ld\n", l->link); -// if (l->link) -// printf("l %ld\n", l->link->node_nr); -// -//} - /** - * Loop peeling, and fix the cf for the loop entry nodes, which have now more preds + * 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. */ -void peel(void) +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 entry_i; + int arity; + ir_node *cp; + ir_node **cpin; + + /** + * 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_entries)); + /* Walk */ + mark_irn_visited(node); - for(i = 0; i < ARR_LEN(loop_entries); i++) - { - loop_entry_t entry = loop_entries[i]; - ir_node *node = entry.node; - ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n); + if (!is_Block(node)) { + ir_node *block = get_nodes_block(node); + if (walk_condition(block)) + DB((dbg, LEVEL_5, "walk block %N\n", block)); + copy_walk_n(block, walk_condition, copy_index); + } - if (is_Block(node)) { - /* node is block and the given pred points inside the loop */ - ir_node *cppred; - - peel_walk( pred ); - - // leave keepalives out - if (is_End(node) && (is_Block(pred) || is_Phi(pred)) ) { - //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) ); - } else { - cppred = get_copy(pred); - //printf("fix block entry %ld to cp %ld\n", node->node_nr, cppred->node_nr); - add_pred( node, cppred ); - //printf("fix block entry %ld to cp %ld\n", node->node_nr, cppred->node_nr); - } + arity = get_irn_arity(node); + NEW_ARR_A(ir_node *, cpin, arity); - //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) ); + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(node, i); - //DBG - //phifix(node, cppred); + 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 { - /* node is somewhere in the graph, outside of the loop */ - //ir_node *cppred; - //ir_node *block; - //ir_node *cpblock; - peel_walk( pred ); - - // no ssa for keepalives - if (is_End(node) && (is_Block(pred) || is_Phi(pred)) ) { - //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) ); - } else { - //printf("fix entry %ld to %ld\n", node->node_nr, pred->node_nr); - entry_buffer[entry_c++] = pred; - } - - //add_End_keepalive(get_irg_end(current_ir_graph), get_copy_of(pred) ); + cpin[i] = pred; + } + } - // cannot construct_ssa here, because it needs another walker + /* 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)); + } - } /* is block */ - } /* for */ + if (!is_Block(node)) { + ir_node *cpblock = get_unroll_copy(get_nodes_block(node), copy_index); - //irg_walk_graph(current_ir_graph, chklink, NULL, NULL); + set_nodes_block(cp, cpblock ); + if (is_Phi(cp)) + add_Block_phi(cpblock, cp); + } - fix_head(loop_cf_head); + /* Keeps phi list of temporary node. */ + set_irn_in(cp, ARR_LEN(cpin), cpin); +} - //printf (" FIXHEAD DONE :D \n"); +/* 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; - entry_i = 0; + for(i = 0; i < blocks; ++i) { + ir_node *block = cc_blocks[i]; + int a; + int arity = get_irn_arity(block); - /* Generate phis for values from peeled code and original loop */ - for(i = 0; entry_i < entry_c; i++) - { - loop_entry_t entry = loop_entries[i]; - ir_node *node = entry.node; + /* Head is an exception. */ + if (block == loop_head) + continue; - if (is_Block(node)) - { - /* block */ - ir_node *phi=get_Block_phis(node); + 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)); - while(phi) - { - add_pred(phi, entry_buffer[entry_i++]); - phi=get_Phi_next(phi); + break; } - } else { - /* not block */ - - ir_node *cppred, *block, *cpblock, *pred; - - /** - * pred = get_irn_n(entry.node, entry.pred_irn_n); - * does not work, because we could have changed the nodes preds in construct_ssa - */ + } + } +} + +/* Unmarks all cc blocks using cc_blocks except head. + * TODO: invert head for unrolling? */ +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]; + + /* TODO Head is an exception. */ + /*if (block != loop_head)*/ + set_Block_mark(block, 0); + } + /*inversion_blocks_in_cc = 1;*/ + inversion_blocks_in_cc = 0; + + /* invalidate */ + loop_info.cc_size = 0; +} + +/** + * Populates head_entries with (node, pred_pos) tuple + * whereas the node's pred at pred_pos is in the 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. + * (Some blocks need to be removed once again.) + * Returns 1 if the given block belongs to the condition chain. + */ +static unsigned find_condition_chain(ir_node *block) +{ + const ir_edge_t *edge; + unsigned mark = 0; + unsigned has_be = 0; + unsigned jmp_only; + unsigned nodes_n = 0; + + mark_irn_visited(block); + + DB((dbg, LEVEL_5, "condition_chains for block %N\n", block)); + + /* Get node count */ + foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) { + ++nodes_n; + } + + /* Check if node count would exceed maximum cc size. + * TODO + * This is not optimal, as we search depth-first and break here, + * continuing with another subtree. */ + if (loop_info.cc_size + nodes_n > opt_params.max_cc_size) { + set_Block_mark(block, 0); + return 0; + } + + /* Check if block only has a jmp instruction. */ + jmp_only = 1; + foreach_out_edge(block, edge) { + ir_node *src = get_edge_src_irn(edge); + + if (! is_Block(src) && ! is_Jmp(src)) { + jmp_only = 0; + } + } + + /* Check cf outs if one is leaving the loop, + * or if this node has a backedge. */ + foreach_block_succ(block, edge) { + ir_node *src = get_edge_src_irn(edge); + int pos = get_edge_src_pos(edge); + + if (! is_in_loop(src)) + mark = 1; + + /* 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; + } + } + + /* 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); + ++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); + } + + foreach_block_succ(block, edge) { + ir_node *src = get_edge_src_irn( edge ); + + 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 fix_copy_inversion(void) +{ + ir_node *new_head; + ir_node **ins; + ir_node **phis; + ir_node *phi, *next; + ir_node *head_cp = get_inversion_copy(loop_head); + int arity = get_irn_arity(head_cp); + int backedges = get_backedge_n(head_cp, 0); + int new_arity = arity - backedges; + int pos; + int i; + + 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_Block(new_arity, ins); + + phis = NEW_ARR_F(ir_node *, 0); + + 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); + } + + pos = 0; + for_each_phi_safe(get_Block_phis(head_cp), phi, next) { + exchange(phi, phis[pos++]); + } + + 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; + 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); + } + + new_head = new_Block(new_arity, ins); + + 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)) { + ins[pos++] = pred; + } else {*/ + ins[pos++] = pred; + + } + } + + new_phi = new_rd_Phi(get_irn_dbg_info(phi), + new_head, new_arity, ins, + get_irn_mode(phi)); + + ARR_APP1(ir_node *, phis, new_phi); + + DB((dbg, LEVEL_5, "fix inverted head should exch %N by %N (pos %d)\n", phi, new_phi, pos )); + } + + 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); + + 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; + + /* + * The order of rewiring bottom-up is crucial. + * Any change of the order leads to lost information that would be needed later. + */ + + ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); + + /* 1. clone condition chain */ + inc_irg_visited(current_ir_graph); + + for (i = 0; i < ARR_LEN(head_entries); ++i) { + entry_edge entry = head_entries[i]; + ir_node *pred = get_irn_n(entry.node, entry.pos); + + DB((dbg, LEVEL_5, "\nInit walk block %N\n", pred)); + + copy_walk(pred, is_nodes_block_marked, cur_loop); + } + + ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); + + /* 2. Extends the head control flow successors ins + * with the definitions of the copied head node. */ + for (i = 0; i < ARR_LEN(head_entries); ++i) { + entry_edge head_out = head_entries[i]; + + if (is_Block(head_out.node)) + extend_ins_by_copy(head_out.node, head_out.pos); + } + + /* 3. construct_ssa for users of definitions in the condition chain, + * as there is now a second definition. */ + for (i = 0; i < ARR_LEN(head_entries); ++i) { + entry_edge head_out = head_entries[i]; + + /* Ignore keepalives */ + if (is_End(head_out.node)) + continue; + + /* Construct ssa for assignments in the condition chain. */ + if (!is_Block(head_out.node)) { + ir_node *pred, *cppred, *block, *cpblock; + + pred = head_out.pred; + cppred = get_inversion_copy(pred); + block = get_nodes_block(pred); + cpblock = get_nodes_block(cppred); + construct_ssa(block, pred, cpblock, cppred); + } + } + + /* + * If there is an assignment in the condition chain + * with a user also in the condition chain, + * the dominance frontier is in the new loop head. + * The dataflow loop is completely in the condition chain. + * Goal: + * To be wired: >| + * + * | ,--. | + * Phi_cp | | copied condition chain + * >| | | | + * >| ?__/ | + * >| ,-. + * Phi* | | new loop head with newly created phi. + * | | + * Phi | | original, inverted condition chain + * | | | + * ?__/ | + * + */ + for (i = 0; i < ARR_LEN(head_df_loop); ++i) { + entry_edge head_out = head_df_loop[i]; + + /* Construct ssa for assignments in the condition chain. */ + ir_node *pred, *cppred, *block, *cpblock; + + pred = head_out.pred; + cppred = get_inversion_copy(pred); + assert(cppred && pred); + block = get_nodes_block(pred); + cpblock = get_nodes_block(cppred); + construct_ssa(block, pred, cpblock, cppred); + } + + /* 4. Remove the ins which are no backedges from the original condition chain + * as the cc is now subsequent to the body. */ + fix_head_inversion(); + + /* 5. Remove the backedges of the copied condition chain, + * because it is going to be the new 'head' in advance to the loop. */ + fix_copy_inversion(); + +} + +/* Performs loop inversion of cur_loop if possible and reasonable. */ +static void loop_inversion(void) +{ + int loop_depth; + unsigned max_loop_nodes = opt_params.max_loop_size; + unsigned max_loop_nodes_adapted; + int depth_adaption = opt_params.depth_adaption; + + unsigned do_inversion = 1; + unsigned has_cc = 0; + + /* Depth of 0 is the procedure and 1 a topmost loop. */ + loop_depth = get_loop_depth(cur_loop) - 1; + + /* Calculating in per mil. */ + max_loop_nodes_adapted = get_max_nodes_adapted(loop_depth); + + DB((dbg, LEVEL_1, "max_nodes: %d\nmax_nodes_adapted %d at depth of %d (adaption %d)\n", + max_loop_nodes, max_loop_nodes_adapted, loop_depth, depth_adaption)); + + if (! (loop_info.nodes > 0)) + return; + +#if LOOP_IGNORE_NODE_LIMITS + DB((dbg, LEVEL_1, "WARNING: Loop node limitations ignored.")); +#else + if (loop_info.nodes > max_loop_nodes) { + /* Only for stats */ + DB((dbg, LEVEL_1, "Nodes %d > allowed nodes %d\n", + loop_info.nodes, loop_depth, max_loop_nodes)); + count_stats(stats.too_large); + /* no RETURN */ + /* Adaption might change it */ + } + + /* Limit processing to loops smaller than given parameter. */ + if (loop_info.nodes > max_loop_nodes_adapted) { + DB((dbg, LEVEL_1, "Nodes %d > allowed nodes (depth %d adapted) %d\n", + loop_info.nodes, loop_depth, max_loop_nodes_adapted)); + count_stats(stats.too_large_adapted); + return; + } + + if (loop_info.calls > opt_params.allowed_calls) { + DB((dbg, LEVEL_1, "Calls %d > allowed calls %d\n", + loop_info.calls, opt_params.allowed_calls)); + count_stats(stats.calls_limit); + return; + } +#endif + + /*inversion_head_node_limit = INT_MAX;*/ + ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); + + /* Reset block marks. + * We use block marks to flag blocks of the original condition chain. */ + irg_walk_graph(current_ir_graph, reset_block_mark, NULL, NULL); + + /*loop_info.blocks = get_loop_n_blocks(cur_loop);*/ + cond_chain_entries = NEW_ARR_F(entry_edge, 0); + head_df_loop = NEW_ARR_F(entry_edge, 0); + + /*head_inversion_node_count = 0;*/ + inversion_blocks_in_cc = 0; + + /* Use phase to keep copy of nodes from the condition chain. */ + phase = new_phase(current_ir_graph, phase_irn_init_default); + + /* Search for condition chains and temporarily save the blocks in an array. */ + cc_blocks = NEW_ARR_F(ir_node *, 0); + inc_irg_visited(current_ir_graph); + has_cc = find_condition_chain(loop_head); + + unmark_not_allowed_cc_blocks(); + DEL_ARR_F(cc_blocks); + +#if LOOP_IGNORE_NODE_LIMITS + (void) unmark_cc_blocks; +#else + /* Condition chain too large. + * Loop should better be small enough to fit into the cache. */ + /* TODO Of course, we should take a small enough cc in the first place, + * which is not that simple. (bin packing) */ + if (loop_info.cc_size > opt_params.max_cc_size) { + count_stats(stats.cc_limit_reached); + + do_inversion = 0; + + /* Unmark cc blocks except the head. + * Invert head only for possible unrolling. */ + unmark_cc_blocks(); + + } +#endif + + /* We also catch endless loops here, + * because they do not have a condition chain. */ + if (inversion_blocks_in_cc < 1) { + do_inversion = 0; + DB((dbg, LEVEL_3, + "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n", + inversion_blocks_in_cc)); + } + + if (do_inversion) { + cur_head_outs = NEW_ARR_F(entry_edge, 0); + + /* Get all edges pointing into the condition chain. */ + irg_walk_graph(current_ir_graph, get_head_outs, NULL, NULL); + + /* Do the inversion */ + inversion_walk(cur_head_outs); + + DEL_ARR_F(cur_head_outs); + + /* Duplicated blocks changed doms */ + set_irg_doms_inconsistent(current_ir_graph); + /* Loop content changed */ + set_irg_loopinfo_inconsistent(current_ir_graph); + /* TODO are they? Depends on set_irn_in and set_irn_n exchange and new_node. */ + set_irg_outs_inconsistent(current_ir_graph); + + count_stats(stats.inverted); + } + + /* free */ + phase_free(phase); + DEL_ARR_F(cond_chain_entries); + DEL_ARR_F(head_df_loop); + + ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); +} + +/* 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_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); + + /* Original loop_heads ins are: + * duff block and the own backedge */ + + ins[0] = loop_condition; + ins[1] = proj; + set_irn_in(loop_head, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of block loophead %N to pred %N and duffs entry %N \n" , loop_head, ins[0], ins[1])); + + for_each_phi(loop_head, phi) { + ir_node *pred = get_irn_n(phi, loop_info.be_src_pos); + /* TODO we think it is a phi, but for Mergesort it is not the case.*/ + + ir_node *last_pred = get_unroll_copy(pred, unroll_nr - 1); + + ins[0] = last_pred; + ins[1] = (ir_node*)get_irn_link(phi); + set_irn_in(phi, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of loophead phi %N to pred %N and duffs entry %N \n" , phi, ins[0], ins[1])); + } +} + +/* 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]; + + in[0] = get_irn_n(node, 0); + + exch = new_rd_Phi(get_irn_dbg_info(node), + get_nodes_block(node), 1, in, + get_irn_mode(node)); + + exchange(node, exch); + } +} + +/* 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); + + for_each_phi(loophead, phi) { + ir_node *topmost_def = get_irn_n(phi, be_src_pos); + ir_node *upper_def = get_unroll_copy(topmost_def, c); + ir_node *lower_phi = get_unroll_copy(phi, c + 1); + + /* It is possible, that the value used + * in the OWN backedge path is NOT defined in this loop. */ + if (is_in_loop(topmost_def)) + ins[0] = upper_def; + else + ins[0] = topmost_def; + + set_irn_in(lower_phi, 1, ins); + /* Need to replace phis with 1 in later. */ + } + } else { + /* Invariant case */ + /* Every node has 2 ins. One from the duff blocks + * and one from the previously unrolled loop. */ + ir_node *ins[2]; + /* Calculate corresponding projection of mod result for this copy c */ + ir_node *proj = new_Proj(loop_info.duff_cond, mode_X, unroll_nr - c - 1); + DB((dbg, LEVEL_4, "New duff proj %N\n" , proj)); + + ins[0] = new_jmp; + ins[1] = proj; + set_irn_in(lower, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of Block %N to pred %N and duffs entry %N \n" , lower, ins[0], ins[1])); + + for_each_phi(loophead, phi) { + ir_node *topmost_phi_pred = get_irn_n(phi, be_src_pos); + ir_node *upper_phi_pred; + ir_node *lower_phi; + ir_node *duff_phi; + + lower_phi = get_unroll_copy(phi, c + 1); + duff_phi = (ir_node*)get_irn_link(phi); + DB((dbg, LEVEL_4, "DD Link of %N is %N\n" , phi, duff_phi)); + + /* */ + if (is_in_loop(topmost_phi_pred)) { + upper_phi_pred = get_unroll_copy(topmost_phi_pred, c); + } else { + upper_phi_pred = topmost_phi_pred; + } + + ins[0] = upper_phi_pred; + ins[1] = duff_phi; + set_irn_in(lower_phi, 2, ins); + DB((dbg, LEVEL_4, "Rewire ins of %N to pred %N and duffs entry %N \n" , lower_phi, ins[0], ins[1])); + } + } + } + + /* Reconnect last copy. */ + for (i = 0; i < ARR_LEN(loop_entries); ++i) { + entry_edge edge = loop_entries[i]; + /* Last copy is at the bottom */ + ir_node *new_pred = get_unroll_copy(edge.pred, copies); + set_irn_n(edge.node, edge.pos, new_pred); + } + + /* Fix original loops head. + * Done in the end, as ins and be info were needed before. */ + if (loop_info.unroll_kind == constant) { + ir_node *phi; + ir_node *head_pred = get_irn_n(loop_head, be_src_pos); + ir_node *loop_condition = get_unroll_copy(head_pred, unroll_nr - 1); + + set_irn_n(loop_head, loop_info.be_src_pos, loop_condition); + + for_each_phi(loop_head, phi) { + ir_node *pred = get_irn_n(phi, be_src_pos); + ir_node *last_pred; + + /* It is possible, that the value used + * in the OWN backedge path is NOT assigned in this loop. */ + if (is_in_loop(pred)) + last_pred = get_unroll_copy(pred, copies); + else + last_pred = pred; + set_irn_n(phi, be_src_pos, last_pred); + } + + } else { + unrolling_fix_loop_head_inv(); + } +} + +/* Copies the cur_loop several times. */ +static void copy_loop(entry_edge *cur_loop_outs, int copies) +{ + int i, c; + + ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); + + for (c = 0; c < copies; ++c) { + + inc_irg_visited(current_ir_graph); + + DB((dbg, LEVEL_5, " ### Copy_loop copy nr: %d ###\n", c)); + for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) { + entry_edge entry = cur_loop_outs[i]; + ir_node *pred = get_irn_n(entry.node, entry.pos); + + copy_walk_n(pred, is_in_loop, c + 1); + } + } + + ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); +} + + +/* Creates a new phi from the given phi node omitting own bes, + * using be_block as supplier of backedge informations. */ +static ir_node *clone_phis_sans_bes(ir_node *phi, ir_node *be_block, ir_node *dest_block) +{ + ir_node **ins; + int arity = get_irn_arity(phi); + int i, c = 0; + ir_node *newphi; + + assert(get_irn_arity(phi) == get_irn_arity(be_block)); + assert(is_Phi(phi)); + + ins = NEW_ARR_F(ir_node *, arity); + for (i = 0; i < arity; ++i) { + if (! is_own_backedge(be_block, i)) { + ins[c] = get_irn_n(phi, i); + ++c; + } + } + + newphi = new_r_Phi(dest_block, c, ins, get_irn_mode(phi)); + + set_irn_link(phi, newphi); + DB((dbg, LEVEL_4, "Linking for duffs device %N to %N\n", phi, newphi)); + + return newphi; +} + +/* Creates a new block from the given block node omitting own bes, + * using be_block as supplier of backedge informations. */ +static ir_node *clone_block_sans_bes(ir_node *node, ir_node *be_block) +{ + ir_node **ins; + int arity = get_irn_arity(node); + int i, c = 0; + + assert(get_irn_arity(node) == get_irn_arity(be_block)); + assert(is_Block(node)); + + NEW_ARR_A(ir_node *, ins, arity); + for (i = 0; i < arity; ++i) { + if (! is_own_backedge(be_block, i)) { + ins[c] = get_irn_n(node, i); + ++c; + } + } + + return new_Block(c, ins); +} + +/* Creates a structure to calculate absolute value of node op. + * Returns mux node with absolute value. */ +static ir_node *new_Abs(ir_node *op, ir_mode *mode) +{ + ir_graph *irg = get_irn_irg(op); + ir_node *block = get_nodes_block(op); + ir_node *zero = new_r_Const(irg, get_mode_null(mode)); + ir_node *cmp = new_r_Cmp(block, op, zero); + ir_node *cond = new_r_Proj(cmp, mode_b, pn_Cmp_Lt); + ir_node *minus_op = new_r_Minus(block, op, mode); + ir_node *mux = new_r_Mux(block, cond, op, minus_op, mode); + + return mux; +} + + +/* Creates blocks for duffs device, using previously obtained + * informations about the iv. + * TODO split */ +static void create_duffs_block(void) +{ + ir_mode *mode; + + ir_node *block1, *count_block, *duff_block; + ir_node *ems, *ems_divmod, *ems_mod_proj, *cmp_null, + *cmp_proj, *ems_mode_cond, *x_true, *x_false, *const_null; + ir_node *true_val, *false_val; + ir_node *ins[2]; + + ir_node *duff_mod, *proj, *cond; + + ir_node *count, *correction, *unroll_c; + ir_node *cmp_bad_count, *good_count, *bad_count, *count_phi, *bad_count_neg; + ir_node *phi; + + mode = get_irn_mode(loop_info.end_val); + const_null = new_Const(get_mode_null(mode)); + + /* TODO naming + * 1. Calculate first approach to count. + * Condition: (end - start) % step == 0 */ + block1 = clone_block_sans_bes(loop_head, loop_head); + DB((dbg, LEVEL_4, "Duff block 1 %N\n", block1)); + + /* Create loop entry phis in first duff block + * as it becomes the loops preheader */ + for_each_phi(loop_head, phi) { + /* Returns phis pred if phi would have arity 1*/ + ir_node *new_phi = clone_phis_sans_bes(phi, loop_head, block1); + + DB((dbg, LEVEL_4, "HEAD %N phi %N\n", loop_head, phi)); + DB((dbg, LEVEL_4, "BLOCK1 %N phi %N\n", block1, new_phi)); + } + + ems = new_r_Sub(block1, loop_info.end_val, loop_info.start_val, + get_irn_mode(loop_info.end_val)); + DB((dbg, LEVEL_4, "BLOCK1 sub %N\n", ems)); + + + ems = new_Sub(loop_info.end_val, loop_info.start_val, + get_irn_mode(loop_info.end_val)); + + DB((dbg, LEVEL_4, "divmod ins %N %N\n", ems, loop_info.step)); + ems_divmod = new_r_DivMod(block1, + new_NoMem(), + ems, + loop_info.step, + mode, + op_pin_state_pinned); + + DB((dbg, LEVEL_4, "New module node %N\n", ems_divmod)); + + ems_mod_proj = new_r_Proj(ems_divmod, mode_Iu, pn_DivMod_res_mod); + cmp_null = new_r_Cmp(block1, ems_mod_proj, const_null); + cmp_proj = new_r_Proj(cmp_null, mode_b, pn_Cmp_Eq); + ems_mode_cond = new_r_Cond(block1, cmp_proj); + + + /* ems % step == 0 */ + x_true = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_true); + /* ems % step != 0 */ + x_false = new_r_Proj(ems_mode_cond, mode_X, pn_Cond_false); + + /* 2. Second block. + * Assures, duffs device receives a valid count. + * Condition: + * decreasing: count < 0 + * increasing: count > 0 + */ + ins[0] = x_true; + ins[1] = x_false; + + count_block = new_Block(2, ins); + DB((dbg, LEVEL_4, "Duff block 2 %N\n", count_block)); + + + /* Increase loop-taken-count depending on the loop condition + * uses the latest iv to compare to. */ + if (loop_info.latest_value == 1) { + /* ems % step == 0 : +0 */ + true_val = new_Const(get_mode_null(mode)); + /* ems % step != 0 : +1 */ + false_val = new_Const(get_mode_one(mode)); + } else { + ir_tarval *tv_two = new_tarval_from_long(2, mode); + /* ems % step == 0 : +1 */ + true_val = new_Const(get_mode_one(mode)); + /* ems % step != 0 : +2 */ + false_val = new_Const(tv_two); + } + + ins[0] = true_val; + ins[1] = false_val; + + correction = new_r_Phi(count_block, 2, ins, mode); + + count = new_r_Proj(ems_divmod, mode, pn_DivMod_res_div); + + /* (end - start) / step + correction */ + count = new_Add(count, correction, mode); + + cmp_bad_count = new_r_Cmp(count_block, count, const_null); + + /* We preconditioned the loop to be tail-controlled. + * So, if count is something 'wrong' like 0, + * negative/positive (depending on step direction), + * we may take the loop once (tail-contr.) and leave it + * to the existing condition, to break; */ + + /* Depending on step direction, we have to check for > or < 0 */ + if (loop_info.decreasing == 1) { + bad_count_neg = new_r_Proj(cmp_bad_count, mode_b, pn_Cmp_Lt); + } else { + bad_count_neg = new_r_Proj(cmp_bad_count, mode_b, pn_Cmp_Gt); + } + + bad_count_neg = new_r_Cond(count_block, bad_count_neg); + good_count = new_Proj(bad_count_neg, mode_X, pn_Cond_true); + bad_count = new_Proj(ems_mode_cond, mode_X, pn_Cond_false); + + /* 3. Duff Block + * Contains module to decide which loop to start from. */ + + ins[0] = good_count; + ins[1] = bad_count; + duff_block = new_Block(2, ins); + DB((dbg, LEVEL_4, "Duff block 3 %N\n", duff_block)); + + /* Get absolute value */ + ins[0] = new_Abs(count, mode); + /* Manually feed the aforementioned count = 1 (bad case)*/ + ins[1] = new_Const(get_mode_one(mode)); + count_phi = new_r_Phi(duff_block, 2, ins, mode); + + unroll_c = new_Const(new_tarval_from_long((long)unroll_nr, mode)); + + /* count % unroll_nr */ + duff_mod = new_r_Mod(duff_block, + new_NoMem(), + count_phi, + unroll_c, + mode, + op_pin_state_pinned); + + + proj = new_Proj(duff_mod, mode, pn_Mod_res); + /* condition does NOT create itself in the block of the proj! */ + cond = new_r_Cond(duff_block, proj); + + loop_info.duff_cond = cond; +} + +/* Returns 1 if given node is not in loop, + * or if it is a phi of the loop head with only loop invariant defs. + */ +static unsigned is_loop_invariant_def(ir_node *node) +{ + int i; + + if (! is_in_loop(node)) { + DB((dbg, LEVEL_4, "Not in loop %N\n", node)); + /* || is_Const(node) || is_SymConst(node)) {*/ + return 1; + } + + /* If this is a phi of the loophead shared by more than 1 loop, + * we need to check if all defs are not in the loop. */ + if (is_Phi(node)) { + ir_node *block; + block = get_nodes_block(node); + + /* To prevent unexpected situations. */ + if (block != loop_head) { + return 0; + } + + for (i = 0; i < get_irn_arity(node); ++i) { + /* Check if all bes are just loopbacks. */ + if (is_own_backedge(block, i) && get_irn_n(node, i) != node) + return 0; + } + DB((dbg, LEVEL_4, "invar %N\n", node)); + return 1; + } + DB((dbg, LEVEL_4, "Not invar %N\n", node)); + + return 0; +} + +/* Returns 1 if one pred of node is invariant and the other is not. + * invar_pred and other are set analogously. */ +static unsigned get_invariant_pred(ir_node *node, ir_node **invar_pred, ir_node **other) +{ + ir_node *pred0 = get_irn_n(node, 0); + ir_node *pred1 = get_irn_n(node, 1); + + *invar_pred = NULL; + *other = NULL; + + if (is_loop_invariant_def(pred0)) { + DB((dbg, LEVEL_4, "pred0 invar %N\n", pred0)); + *invar_pred = pred0; + *other = pred1; + } + + if (is_loop_invariant_def(pred1)) { + DB((dbg, LEVEL_4, "pred1 invar %N\n", pred1)); + + if (*invar_pred != NULL) { + /* RETURN. We do not want both preds to be invariant. */ + return 0; + } + + *other = pred0; + *invar_pred = pred1; + return 1; + } else { + DB((dbg, LEVEL_4, "pred1 not invar %N\n", pred1)); + + if (*invar_pred != NULL) + return 1; + else + return 0; + } +} + +/* Starts from a phi that may belong to an iv. + * If an add forms a loop with iteration_phi, + * and add uses a constant, 1 is returned + * and 'start' as well as 'add' are sane. */ +static unsigned get_start_and_add(ir_node *iteration_phi, unrolling_kind_flag role) +{ + int i; + ir_node *found_add = 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)) { + *const_pred = pred0; + *other = pred1; + } - pred = entry_buffer[entry_i++]; + /*DB((dbg, LEVEL_4, "is %N const\n", pred1));*/ + if (is_Const(pred1) || is_SymConst(pred1)) { + if (*const_pred != NULL) { + /* RETURN. We do not want both preds to be constant. */ + return 0; + } - //printf("pred %ld\n", pred->node_nr); - cppred = get_copy(pred); - //printf("cppred %ld\n", cppred->node_nr); - block = get_nodes_block(pred); - //printf("block %ld\n", block->node_nr); - cpblock = get_nodes_block(cppred); - //printf("cpblock %ld\n", cpblock->node_nr); + *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."); + } +} +/* Returns 1 if loop exits within 2 steps of the iv. + * Norm_proj means we do not exit the loop.*/ +static unsigned simulate_next(ir_tarval **count_tar, + ir_tarval *stepped, ir_tarval *step_tar, ir_tarval *end_tar, + pn_Cmp norm_proj) +{ + ir_tarval *next; + + DB((dbg, LEVEL_4, "Loop taken if (stepped)%ld %s (end)%ld ", + get_tarval_long(stepped), + get_pnc_string((norm_proj)), + get_tarval_long(end_tar))); + DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value)); + + /* If current iv does not stay in the loop, + * this run satisfied the exit condition. */ + if (! (tarval_cmp(stepped, end_tar) & norm_proj)) + return 1; + + DB((dbg, LEVEL_4, "Result: (stepped)%ld IS %s (end)%ld\n", + get_tarval_long(stepped), + get_pnc_string(tarval_cmp(stepped, end_tar)), + get_tarval_long(end_tar))); + + /* next step */ + if (is_Add(loop_info.add)) + next = tarval_add(stepped, step_tar); + else + /* sub */ + next = tarval_sub(stepped, step_tar, get_irn_mode(loop_info.end_val)); - //dump_ir_block_graph(current_ir_graph, "vorher"); - construct_ssa(block, pred, cpblock, cppred); - //add_End_keepalive(get_irg_end(current_ir_graph), cppred); + DB((dbg, LEVEL_4, "Loop taken if %ld %s %ld ", + get_tarval_long(next), + get_pnc_string(norm_proj), + get_tarval_long(end_tar))); + DB((dbg, LEVEL_4, "comparing latest value %d\n", loop_info.latest_value)); + /* Increase steps. */ + *count_tar = tarval_add(*count_tar, get_tarval_one(get_tarval_mode(*count_tar))); - //add_pred(get_irg_end(current_ir_graph), cppred); - //dump_ir_block_graph(current_ir_graph, "nachher"); + /* Next has to fail the loop condition, or we will never exit. */ + if (! (tarval_cmp(next, end_tar) & norm_proj)) + return 1; + else + return 0; +} +/* Check if loop meets requirements for a 'simple loop': + * - Exactly one cf out + * - Allowed calls + * - Max nodes after unrolling + * - tail-controlled + * - exactly one be + * - cmp + * Returns Projection of cmp node or NULL; */ +static ir_node *is_simple_loop(void) +{ + int arity, i; + ir_node *loop_block, *exit_block, *projx, *cond, *projres, *loop_condition; + + /* Maximum of one condition, and no endless loops. */ + if (loop_info.cf_outs != 1) + return NULL; + + DB((dbg, LEVEL_4, "1 loop exit\n")); + +#if LOOP_IGNORE_NODE_LIMITS + /* Ignore loop size. Probably not wise in other than testcases. */ + loop_info.max_unroll = 40; +#else + /* Calculate maximum unroll_nr keeping node count below limit. */ + loop_info.max_unroll = (int)((double)opt_params.max_unrolled_loop_size / (double)loop_info.nodes); + if (loop_info.max_unroll < 2) { + count_stats(stats.too_large); + return NULL; + } +#endif + + + DB((dbg, LEVEL_4, "maximum unroll factor %u, to not exceed node limit \n", + opt_params.max_unrolled_loop_size)); + + arity = get_irn_arity(loop_head); + /* RETURN if we have more than 1 be. */ + /* Get my backedges without alien bes. */ + loop_block = NULL; + for (i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(loop_head, i); + if (is_own_backedge(loop_head, i)) { + if (loop_block) + /* Our simple loops may have only one backedge. */ + return NULL; + else { + loop_block = get_nodes_block(pred); + loop_info.be_src_pos = i; + } } } + + DB((dbg, LEVEL_4, "loop has 1 own backedge.\n")); + + exit_block = get_nodes_block(loop_info.cf_out.pred); + /* The loop has to be tail-controlled. + * This can be changed/improved, + * but we would need a duff iv. */ + if (exit_block != loop_block) + return NULL; + + DB((dbg, LEVEL_4, "tail-controlled loop.\n")); + + /* find value on which loop exit depends */ + projx = loop_info.cf_out.pred; + cond = get_irn_n(projx, 0); + projres = get_irn_n(cond, 0); + loop_condition = get_irn_n(projres, 0); + + 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; } -void alloc_linkstructs(ir_node *node, void *env) +/* 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) { - (void) env; - link_node_state_t *state = XMALLOCZ(link_node_state_t); - node->link = (void *)state; + 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; } -void free_linkstructs(ir_node *node, void *env) +/* 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) { - (void) env; - xfree( (link_node_state_t*) node->link); + + ir_node *projres, *loop_condition, *iteration_path; + unsigned success, is_latest_val; + ir_tarval *step_tar; + ir_mode *mode; + + + /* RETURN if loop is not 'simple' */ + projres = is_simple_loop(); + if (projres == NULL) + return 0; + + /* Use a minimal size for the invariant unrolled loop, + * as duffs device produces overhead */ + if (loop_info.nodes < opt_params.invar_unrolling_min_size) + return 0; + + loop_condition = get_irn_n(projres, 0); + + success = get_invariant_pred(loop_condition, &loop_info.end_val, &iteration_path); + DB((dbg, LEVEL_4, "pred invar %d\n", success)); + + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Invariant End_val %N, other %N\n", loop_info.end_val, iteration_path)); + + /* We may find the add or the phi first. + * Until now we only have end_val. */ + if (is_Add(iteration_path) || is_Sub(iteration_path)) { + + /* We test against the latest value of the iv. */ + is_latest_val = 1; + + loop_info.add = iteration_path; + DB((dbg, LEVEL_4, "Case 1: Got add %N (maybe not sane)\n", loop_info.add)); + + /* Preds of the add should be step and the iteration_phi */ + success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got step %N\n", loop_info.step)); + + if (! is_Phi(loop_info.iteration_phi)) + return 0; + + DB((dbg, LEVEL_4, "Got phi %N\n", loop_info.iteration_phi)); + + /* Find start_val. + * Does necessary sanity check of add, if it is already set. */ + success = get_start_and_add(loop_info.iteration_phi, invariant); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got start A %N\n", loop_info.start_val)); + + } else if (is_Phi(iteration_path)) { + ir_node *new_iteration_phi; + + /* We compare with the value the iv had entering this run. */ + is_latest_val = 0; + + loop_info.iteration_phi = iteration_path; + DB((dbg, LEVEL_4, "Case 2: Got phi %N\n", loop_info.iteration_phi)); + + /* Find start_val and add-node. + * Does necessary sanity check of add, if it is already set. */ + success = get_start_and_add(loop_info.iteration_phi, invariant); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got start B %N\n", loop_info.start_val)); + DB((dbg, LEVEL_4, "Got add or sub %N\n", loop_info.add)); + + success = get_const_pred(loop_info.add, &loop_info.step, &new_iteration_phi); + if (! success) + return 0; + + DB((dbg, LEVEL_4, "Got step (B) %N\n", loop_info.step)); + + if (loop_info.iteration_phi != new_iteration_phi) + return 0; + + } else { + return 0; + } + + mode = get_irn_mode(loop_info.end_val); + + DB((dbg, LEVEL_4, "start %N, end %N, step %N\n", + loop_info.start_val, loop_info.end_val, loop_info.step)); + + if (mode != mode_Is && mode != mode_Iu) + return 0; + + /* TODO necessary? */ + if (!are_mode_I(loop_info.start_val, loop_info.step, loop_info.end_val)) + return 0; + + DB((dbg, LEVEL_4, "mode integer\n")); + + step_tar = get_Const_tarval(loop_info.step); + + if (tarval_is_null(step_tar)) { + /* TODO Might be worth a warning. */ + return 0; + } + + DB((dbg, LEVEL_4, "step is not 0\n")); + + create_duffs_block(); + + return loop_info.max_unroll; } -void decision_maker(void) +/* Returns unroll factor, + * given maximum unroll factor and number of loop passes. */ +static unsigned get_preferred_factor_constant(ir_tarval *count_tar) { - //inc_irg_visited(current_ir_graph); - //loop_walker( loop_entries, NULL, get_invariants, NULL ); + ir_tarval *tar_6, *tar_5, *tar_4, *tar_3, *tar_2; + unsigned prefer; + ir_mode *mode = get_irn_mode(loop_info.end_val); + + tar_6 = new_tarval_from_long(6, mode); + tar_5 = new_tarval_from_long(5, mode); + tar_4 = new_tarval_from_long(4, mode); + tar_3 = new_tarval_from_long(3, mode); + tar_2 = new_tarval_from_long(2, mode); + + /* loop passes % {6, 5, 4, 3, 2} == 0 */ + if (tarval_is_null(tarval_mod(count_tar, tar_6))) + prefer = 6; + else if (tarval_is_null(tarval_mod(count_tar, tar_5))) + prefer = 5; + else if (tarval_is_null(tarval_mod(count_tar, tar_4))) + prefer = 4; + else if (tarval_is_null(tarval_mod(count_tar, tar_3))) + prefer = 3; + else if (tarval_is_null(tarval_mod(count_tar, tar_2))) + prefer = 2; + else { + /* gcd(max_unroll, count_tar) */ + int a = loop_info.max_unroll; + int b = (int)get_tarval_long(count_tar); + int c; + DB((dbg, LEVEL_4, "gcd of max_unroll %d and count_tar %d: ", a, b)); - inc_irg_visited(current_ir_graph); - irg_walk_graph(current_ir_graph, alloc_linkstructs, NULL, NULL); + do { + c = a % b; + a = b; b = c; + } while( c != 0); - inc_irg_visited(current_ir_graph); - peel(); + DB((dbg, LEVEL_4, "%d\n", a)); + return a; + } - inc_irg_visited(current_ir_graph); - irg_walk_graph(current_ir_graph, free_linkstructs, NULL, NULL); + DB((dbg, LEVEL_4, "preferred unroll factor %d\n", prefer)); + + /* + * If our preference is greater than the allowed unroll factor + * we either might reduce the preferred factor and prevent a duffs device block, + * or create a duffs device block, from which in this case (constants only) + * we know the startloop at compiletime. + * The latter yields the following graphs. + * but for code generation we would want to use graph A. + * The graphs are equivalent. So, we can only reduce the preferred factor. + * A) B) + * PreHead PreHead + * | ,--. | ,--. + * \ Loop1 \ Loop2 \ + * \ | | / | | + * Loop2 / / Loop1 / + * | `--' | `--' + */ + + if (prefer <= loop_info.max_unroll) + return prefer; + else { + switch(prefer) { + case 6: + if (loop_info.max_unroll >= 3) + return 3; + else if (loop_info.max_unroll >= 2) + return 2; + else + return 0; + + case 4: + if (loop_info.max_unroll >= 2) + return 2; + else + return 0; + + default: + return 0; + } + } } +/* Check if cur_loop is a simple counting loop. + * Start, step and end are constants. + * TODO The whole constant case should use procedures similar to + * the invariant case, as they are more versatile. */ +/* TODO split. */ +static unsigned get_unroll_decision_constant(void) +{ + ir_node *projres, *loop_condition, *iteration_path; + unsigned success, is_latest_val; + ir_tarval *start_tar, *end_tar, *step_tar, *diff_tar, *count_tar, *stepped; + pn_Cmp proj_proj, norm_proj; + ir_mode *mode; + + /* RETURN if loop is not 'simple' */ + projres = is_simple_loop(); + if (projres == NULL) + return 0; + + /* One in of the loop condition needs to be loop invariant. => 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, "Case 2: Got add %N (maybe not sane)\n", loop_info.add)); + + /* Preds of the add should be step and the iteration_phi */ + success = get_const_pred(loop_info.add, &loop_info.step, &loop_info.iteration_phi); + if (! success) + return 0; + + 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, "Case 1: Got phi %N \n", loop_info.iteration_phi)); + + /* Find start_val and add-node. + * Does necessary sanity check of add, if it is already set. */ + success = get_start_and_add(loop_info.iteration_phi, constant); + if (! success) + return 0; + + 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_4, "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_pn_cmp(projres); + /* Assure that norm_proj is the stay-in-loop case. */ + if (loop_info.exit_cond == 1) + norm_proj = get_math_inverted_case(proj_proj); + else + norm_proj = proj_proj; + + DB((dbg, LEVEL_4, "normalized projection %s\n", get_pnc_string(norm_proj))); + + /* Executed at most once (stay in counting loop if a Eq b) */ + if (norm_proj == pn_Cmp_Eq) + /* TODO Might be worth a warning. */ + return 0; + + /* calculates next values and increases count_tar according to it */ + success = simulate_next(&count_tar, stepped, step_tar, end_tar, norm_proj); + if (! success) + return 0; + + /* We run loop once more, if we compare to the + * not yet in-/decreased iv. */ + if (is_latest_val == 0) { + DB((dbg, LEVEL_4, "condition uses not latest iv value\n")); + count_tar = tarval_add(count_tar, get_tarval_one(mode)); + } + + DB((dbg, LEVEL_4, "loop taken %ld times\n", get_tarval_long(count_tar))); + + /* Assure the loop is taken at least 1 time. */ + if (tarval_is_null(count_tar)) { + /* TODO Might be worth a warning. */ + return 0; + } + + loop_info.count_tar = count_tar; + return get_preferred_factor_constant(count_tar); +} /** - * TODO use list , not arr_F + * Loop unrolling */ -void analyze_loop(ir_loop *loop) +static void unroll_loop(void) { - /* Init new for every loop */ - loop_cf_head = NULL; - loop_cf_head_valid = 1; - //loop_entries_n = 0; - backedges_n = 0; - has_sto = 0; - cur_loop = loop; + if (! (loop_info.nodes > 0)) + return; + +#if LOOP_IGNORE_NODE_LIMITS + DB((dbg, LEVEL_1, "WARNING: Loop node limitations ignored.")); +#else + if (loop_info.nodes > opt_params.max_unrolled_loop_size) { + DB((dbg, LEVEL_2, "Nodes %d > allowed nodes %d\n", + loop_info.nodes, opt_params.max_unrolled_loop_size)); + count_stats(stats.too_large); + return; + } + + if (loop_info.calls > 0) { + DB((dbg, LEVEL_2, "Calls %d > allowed calls 0\n", + loop_info.calls)); + count_stats(stats.calls_limit); + return; + } +#endif + + 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_2, " *** 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 (loop_info.unroll_kind == constant) { + if ((int)get_tarval_long(loop_info.count_tar) == unroll_nr) + loop_info.needs_backedge = 0; + else + loop_info.needs_backedge = 1; + } else { + loop_info.needs_backedge = 1; + } + + /* Use phase to keep copy of nodes from the condition chain. */ + phase = new_phase(current_ir_graph, phase_irn_init_default); + + /* Copies the loop */ + copy_loop(loop_entries, unroll_nr - 1); + + /* Line up the floating copies. */ + place_copies(unroll_nr - 1); + + /* Remove phis with 1 in + * If there were no nested phis, this would not be necessary. + * Avoiding the creation in the first place + * leads to complex special cases. */ + irg_walk_graph(current_ir_graph, correct_phis, NULL, NULL); + + 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); + } + +} - /* arrays */ - //backedges = NEW_ARR_F(loop_entry_t, 0); - //alien_backedges = NEW_ARR_F(loop_entry_t, 0); - //head_edges = NEW_ARR_F(loop_entry_t, 0); +/* Analyzes the loop, and checks if size is within allowed range. + * Decides if loop will be processed. */ +static void init_analyze(ir_loop *loop) +{ + cur_loop = loop; - loop_entries = NEW_ARR_F(loop_entry_t, 0); - head_entries = NEW_ARR_F(loop_entry_t, 0); + loop_head = NULL; + loop_head_valid = 1; - inc_irg_visited( current_ir_graph ); - irg_walk_graph( current_ir_graph, block_phi_walker, NULL, NULL ); + /* Reset loop info */ + memset(&loop_info, 0, sizeof(loop_info_t)); - /* Collect all backedges */ - for_each_loop_block(loop, collect_backedges, NULL ); + DB((dbg, LEVEL_1, " >>>> current loop includes node %N <<<\n", + get_loop_node(loop, 0))); - /* Find loop entries walk, find head */ - inc_irg_visited( current_ir_graph ); - irg_walk_graph( current_ir_graph, find_loop_entries_walk, NULL, NULL ); + /* Collect loop informations: head, node counts. */ + irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL); /* RETURN if there is no valid head */ - if (!loop_cf_head || !loop_cf_head_valid) - { - //DBG printf("NOTE: There is no valid loop head. Nothing done.\n"); + 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)); } - decision_maker(); + if (loop_info.branches > opt_params.max_branches) { + DB((dbg, LEVEL_1, "Branches %d > allowed branches %d\n", + loop_info.branches, opt_params.max_branches)); + count_stats(stats.calls_limit); + return; + } - // TODO free all link states... or better put them on functionstack + switch (loop_op) { + case loop_op_inversion: + loop_inversion(); + break; - /* FREE */ - DEL_ARR_F(loop_entries); - DEL_ARR_F(head_entries); - //DEL_ARR_F(backedges); - //DEL_ARR_F(alien_backedges); - //DEL_ARR_F(head_edges); + case loop_op_unrolling: + unroll_loop(); + break; - //dump_ir_block_graph(current_ir_graph, "-lu1"); + default: + panic("Loop optimization not implemented."); + } + DB((dbg, LEVEL_1, " <<<< end of loop with node %N >>>>\n", + get_loop_node(loop, 0))); } -/** - * Find most inner loops and send them to analyze_loop - */ -void analyze_inner_loop(ir_loop *loop) +/* Find innermost loops and add them to loops. */ +static void find_innermost_loop(ir_loop *loop) { /* descend into sons */ int sons = get_loop_n_sons(loop); - //printf("found %d loops \n", sons); - - if (sons==0) - { - //printf("analyze loop %ld\n", loop->loop_nr); - analyze_loop(loop); - } - else - { + if (sons == 0) { + ARR_APP1(ir_loop *, loops, loop); + } else { int s; - for(s=0; sloop_nr); - analyze_inner_loop( get_loop_son(loop, 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))); } -//struct loop_unroll_pass_t { -// ir_graph_pass_t pass; -//}; +void do_loop_inversion(ir_graph *irg) +{ + loop_op = loop_op_inversion; -/** - * Wrapper to run loop_unroll() as a ir_prog pass. - */ -//static int loop_unroll_wrapper(ir_graph *irg, void *context) { -// -// (void)context; -// loop_unroll(irg); -// return 0; -//} - - -//ir_graph_pass_t *loop_unroll_pass(const char *name) -//{ -// struct loop_unroll_pass_t *pass = -// XMALLOCZ(struct loop_unroll_pass_t); -// -// return def_graph_pass_constructor( -// &pass->pass, name ? name : "loop_unroll", -// loop_unroll_wrapper); -//} + DB((dbg, LEVEL_1, " >>> inversion (Startnode %N) <<<\n", + get_irg_start(irg))); -/* -void firm_init_loopunroll(void) { - FIRM_DBG_REGISTER(dbg, "firm.opt.loopunroll"); -}*/ + loop_optimization(irg); + + assure_cf_loop(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"); +}