X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=39df5e583a2ed10d72f4c522af7844626f34196e;hb=a619ce99e40de4eb4481a590970a881e9f24627a;hp=6e42f8792845c6bc0e92b9fad6694686fad01ee4;hpb=6b689655e2513b332d2b0e4020477ccf00a69a6b;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index 6e42f8792..39df5e583 100644 --- a/ir/opt/loop.c +++ b/ir/opt/loop.c @@ -26,6 +26,8 @@ */ #include "config.h" +#include "iroptimize.h" +#include "opt_init.h" #include "irnode.h" #include "debug.h" @@ -36,14 +38,10 @@ #include "irouts.h" #include "iredges.h" #include "irtools.h" -#include "array_t.h" /* automatic array */ -#include "beutil.h" /* get_block */ -#include "irloop_t.h" /* set_irn_loop*/ - -#if 0 - #include "irdump_t.h" -#endif - +#include "array_t.h" +#include "beutil.h" +#include "irloop_t.h" +#include "irpass.h" DEBUG_ONLY(static firm_dbg_module_t *dbg); @@ -96,14 +94,16 @@ static ir_node *loop_peeled_head = NULL; /* Loop analysis informations */ typedef struct loop_info_t { + unsigned blocks; /* number of blocks in the loop */ unsigned calls; /* number of calls */ unsigned loads; /* number of load nodes */ + unsigned outs; /* outs without keepalives */ +#if 0 unsigned invariant_loads; unsigned stores; /* number of store nodes */ - unsigned blocks; /* number of blocks in the loop */ unsigned opnodes_n; /* nodes that probably result in an instruction */ unsigned do_invariant_opt; - unsigned outs; /* outs without keepalives */ +#endif } loop_info_t; /* Information about the current loop */ @@ -116,7 +116,7 @@ static out_edge *cond_chain_entries; int unroll_times; static unsigned head_inversion_node_count; -static unsigned head_inversion_node_limit; +static unsigned inversion_head_node_limit; static unsigned head_inversion_block_count; static unsigned enable_peeling; @@ -128,40 +128,12 @@ static unsigned enable_unrolling; * ============= AUXILIARY FUNCTIONS ===================================== */ -/* Check for number of bads. This optimization should not produce bads. */ -DEBUG_ONLY( - int bads; - int previous_bads; - - void check_bad(ir_node *node, void *env) - { - (void)env; - - if (is_Bad(node)) { - DB((dbg, LEVEL_1, "WARNING: BAD %ld\n", get_irn_node_nr(node))); - ++bads; - } - } - - void is_bad(char *msg) - { - DB((dbg, LEVEL_1, "%s\n", msg ? msg : "")); - irg_walk_graph(current_ir_graph, check_bad, NULL,NULL); - if (msg && bads != previous_bads) - { - /*assert(!bads && "BADS!\n");*/ - DB((dbg, LEVEL_1, "####### BAD ########\n%s\n %d > %d ##############################\n", msg, previous_bads, bads)); - } - if (!msg) previous_bads=bads; - bads = 0; - /* dump_ir_block_graph(current_ir_graph, "-LASTGOOD"); */ - } -) /** * Creates object on the heap, and adds it to a linked list to free it later. */ -static node_info *new_node_info(void) { +static node_info *new_node_info(void) +{ node_info *l = XMALLOCZ(node_info); l->freelistnext = link_node_state_list; link_node_state_list = l; @@ -189,7 +161,7 @@ static void free_node_info(void) int a = 0; node_info *n; n = link_node_state_list; - while(n) { + while (n) { node_info *next = n->freelistnext; ++a; xfree(n); @@ -206,7 +178,7 @@ static void reset_node_infos(void) { node_info *next; next = link_node_state_list; - while(next->freelistnext) { + while (next->freelistnext) { node_info *cur = next; next = cur->freelistnext; cur->copy = NULL; @@ -215,35 +187,47 @@ static void reset_node_infos(void) } } +/* Returns the nodes node_info link. */ +static ir_node *get_link(ir_node *n) +{ + return ((node_info *)get_irn_link(n))->link; +} +/* Sets the nodes node_info link. */ +static void set_link(ir_node *n, ir_node *link) +{ + ((node_info *)get_irn_link(n))->link = link; +} -/* Returns the */ +/* Returns a nodes copy. */ static ir_node *get_copy(ir_node *n) { return ((node_info *)get_irn_link(n))->copy; } +/* Sets a nodes copy. */ +static void set_copy(ir_node *n, ir_node *copy) +{ + ((node_info *)get_irn_link(n) )->copy = copy; +} + /** - * Convenience macros for iterating over every copy in a linked list + * Convenience macro for iterating over every copy in a linked list * of copies. */ #define for_each_copy(node) \ for ( ; (node) ; (node) = get_copy(node)) +/** + * Convenience macro for iterating over every copy in 2 linked lists + * of copies in parallel. + */ #define for_each_copy2(high1, low1, high2, low2) \ for ( ; (low1) && (low2); (high1) = (low1), (low1) = get_copy(low1), \ (high2) = (low2), (low2) = get_copy(low2)) -/* Links the node to its copy */ -static void set_copy(ir_node *n, ir_node *copy) -{ - ((node_info *)get_irn_link(n) )->copy = copy; -} - -/* Returns 0 if the node or block is not in cur_loop. - * NOTE: get_irn_loop returns the ir_node loop attribute. - * But it seems only to be set correctly to blocks! - * Thus, we need to use get_block to get the loop. +/* + * Returns 0 if the node or block is not in cur_loop. */ static unsigned is_in_loop(ir_node *node) { @@ -271,14 +255,15 @@ static unsigned is_nodesblock_marked(ir_node* node) } /* Returns the number of blocks in a loop. */ -int get_loop_n_blocks(ir_loop *loop) { +static int get_loop_n_blocks(ir_loop *loop) +{ int elements, e; int blocks = 0; elements = get_loop_n_elements(loop); - for(e=0; einvariant )) { - get_node_info(node)->invariant = 1; - DB((dbg, LEVEL_2, "Invariant node found: %ld", get_irn_node_nr(node))); - ++loop_info.invariant_loads; - - } else { - get_node_info(node)->invariant = 0; - } - } else { - int i; - invar = 1; - /* find loop variant preds */ - for(i = 0; i < arity; ++i) { - ir_node *pred = get_irn_n(node, i); - - if ( is_in_loop(pred) /* assignments outside of the loop are loop invariant */ - && !is_Const(pred) /* constants */ - && !is_SymConst(pred) /* SymConst */ - && !get_node_info(node)->invariant ) { /* pred is marked as invariant */ - invar = 0; - break; - } - } - - get_node_info(node)->invariant = invar; - } - return 0; -} - static ir_node *ssa_second_def; static ir_node *ssa_second_def_block; /** - * Walks the graph bottom up, searching for definitions and create phis. - * (Does not handle the special case where the second definition is in the block of the user - * of the original definition because it is not necessary here.) + * Walks the graph bottom up, searching for definitions and creates phis. */ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) { @@ -470,7 +390,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) ir_node *phi; ir_node **in; - DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %ld\n", get_irn_node_nr(block))); + DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %N\n", block)); /* Prevents creation of phi that would be bad anyway. * Dead and bad blocks. */ @@ -478,14 +398,14 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) return new_Bad(); if (block == ssa_second_def_block) { - DB((dbg, LEVEL_5, "ssa found second definition: use second def %ld\n", get_irn_node_nr(ssa_second_def))); + DB((dbg, LEVEL_5, "ssa found second definition: use second def %N\n", ssa_second_def)); return ssa_second_def; } /* already processed this block? */ if (irn_visited(block)) { - ir_node *value = get_node_info(block)->link; - DB((dbg, LEVEL_5, "ssa already visited: use linked %ld\n", get_irn_node_nr(value))); + ir_node *value = get_link(block); + DB((dbg, LEVEL_5, "ssa already visited: use linked %N\n", value)); return value; } @@ -498,10 +418,10 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) ir_node *pred_block = get_Block_cfgpred_block(block, 0); ir_node *value; - DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %ld\n", get_irn_node_nr(pred_block))); + DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %N\n", pred_block)); value = search_def_and_create_phis(pred_block, mode); - get_node_info(block)->link = value; + set_link(block, value); mark_irn_visited(block); return value; @@ -509,7 +429,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) /* create a new Phi */ NEW_ARR_A(ir_node*, in, n_cfgpreds); - for(i = 0; i < n_cfgpreds; ++i) + for (i = 0; i < n_cfgpreds; ++i) in[i] = new_Unknown(mode); phi = new_r_Phi(block, n_cfgpreds, in, mode); @@ -519,20 +439,20 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) /* EVERY node is assumed to have a node_info linked. */ alloc_node_info(phi, NULL); - DB((dbg, LEVEL_5, "ssa phi creation: link new phi %ld to block %ld\n", get_irn_node_nr(phi), get_irn_node_nr(block))); + DB((dbg, LEVEL_5, "ssa phi creation: link new phi %N to block %N\n", phi, block)); - get_node_info(block)->link = phi; + set_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); assert(pred_block != NULL); pred_val = search_def_and_create_phis(pred_block, mode); assert(pred_val != NULL); - DB((dbg, LEVEL_5, "ssa phi pred:phi %ld, pred %ld\n", get_irn_node_nr(phi), get_irn_node_nr(pred_val))); + DB((dbg, LEVEL_5, "ssa phi pred:phi %N, pred %N\n", phi, pred_val)); set_irn_n(phi, i, pred_val); } return phi; @@ -564,7 +484,7 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, inc_irg_visited(irg); mode = get_irn_mode(orig_val); - get_node_info(orig_block)->link = orig_val; + set_link(orig_block, orig_val); mark_irn_visited(orig_block); ssa_second_def_block = second_block; @@ -581,7 +501,7 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, if (is_End(user)) continue; - DB((dbg, LEVEL_5, "original user %ld\n", get_irn_node_nr(user))); + DB((dbg, LEVEL_5, "original user %N\n", user)); if (is_Phi(user)) { ir_node *pred_block = get_Block_cfgpred_block(user_block, j); @@ -598,19 +518,64 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); } +/* + * Construct SSA for def and all of its copies. + */ +static void construct_ssa_n(ir_node *def, ir_node *user) +{ + ir_graph *irg; + ir_mode *mode; + ir_node *iter = def; + const ir_edge_t *edge; + const ir_edge_t *next; + irg = get_irn_irg(def); + + ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); + inc_irg_visited(irg); + + mode = get_irn_mode(def); + + for_each_copy(iter) { + set_link(get_nodes_block(iter), iter); + mark_irn_visited(get_nodes_block(iter)); + + DB((dbg, LEVEL_5, "ssa_n: Link def %N to block %N\n", + iter, get_nodes_block(iter))); + } + + /* Need to search the outs, because we need the in-pos on the user node. */ + foreach_out_edge_safe(def, edge, next) { + ir_node *edge_user = get_edge_src_irn(edge); + int edge_src = get_edge_src_pos(edge); + ir_node *user_block = get_nodes_block(user); + ir_node *newval; + + if (edge_user != user) + continue; + + if (is_Phi(user)) { + ir_node *pred_block = get_Block_cfgpred_block(user_block, edge_src); + newval = search_def_and_create_phis(pred_block, mode); + } else { + newval = search_def_and_create_phis(user_block, mode); + } + + if (newval != user && !is_Bad(newval)) + set_irn_n(user, edge_src, newval); + } + + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); +} + /** * Construct SSA for all definitions in arr. */ -void construct_ssa_foreach(ir_node **arr, int arr_n) +static void construct_ssa_foreach(ir_node **arr, int arr_n) { int i; - for(i = 0; i < arr_n; i++) { + for (i = 0; i < arr_n ; ++i) { ir_node *cppred, *block, *cpblock, *pred; - /* It is not possible to use - * pred = get_irn_n(entry.node, entry.pred_irn_n); - * because we might have changed the nodes predecessors in construct_ssa - */ pred = arr[i]; cppred = get_copy(pred); block = get_nodes_block(pred); @@ -633,28 +598,6 @@ static int get_backedge_n(ir_node *loophead, unsigned with_alien) return be_n; } -/** - * Sets the nodes backedges, according to its predecessors link. - */ -static void fix_backedge_info(ir_node *node) -{ - int i; - for (i = 0; i < get_irn_arity(node); ++i) { - ir_node *pred = get_irn_n(node, i); - if (get_node_info(pred)->link != NULL) { - set_backedge(node, i); - get_node_info(pred)->link = NULL; - DB((dbg, LEVEL_5, "fix backedge: node %ld pred %ld is backedge\n", - get_irn_node_nr(node), get_irn_node_nr(pred))); - } else { - set_not_backedge(node, i); - DB((dbg, LEVEL_5, "fix backedge: node %ld pred %ld is not backedge\n", - get_irn_node_nr(node), get_irn_node_nr(pred))); - } - } -} - - /** * Rewires the heads after peeling. */ @@ -732,13 +675,6 @@ static void peel_fix_heads(void) set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins); set_irn_in(peelhead, ARR_LEN(peelheadnins), peelheadnins); -#if 0 - fix_backedge_info(loophead); - fix_backedge_info(peelhead); -#else - (void)fix_backedge_info; -#endif - for_each_phi(loophead, phi) { ir_node **ins = get_node_info( phi )->ins; set_irn_in(phi, lhead_arity, ins); @@ -752,6 +688,7 @@ static void peel_fix_heads(void) /** * Create a raw copy (ins are still the old ones) of the given node. + * We rely on copies to be NOT visited. */ static ir_node *rawcopy_node(ir_node *node) { @@ -771,14 +708,22 @@ static ir_node *rawcopy_node(ir_node *node) set_copy(node, cp); cpstate = new_node_info(); set_irn_link(cp, cpstate); - mark_irn_visited(cp); + + + if (is_Block(cp)) { + /* TODO + * exact_copy already sets Macroblock. + * Why should we do this anyway? */ + set_Block_MacroBlock(cp, cp); + } + return cp; } /** * This walker copies all walked nodes. * If the walk_condition is true for a node, it is walked. - * All nodes node_info->copy attributes has to be NULL prior to every to every walk. + * All nodes node_info->copy attributes have to be NULL prior to every walk. */ static void copy_walk(ir_node *node, walker_condition *walk_condition, ir_loop *set_loop) { @@ -794,10 +739,10 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, ir_loop * */ if (get_irn_visited(node) >= get_irg_visited(irg)) { /* Here we rely on nodestate's copy being initialized with NULL */ - DB((dbg, LEVEL_5, "copy_walk: We have already visited %ld\n", get_irn_node_nr(node))); + DB((dbg, LEVEL_5, "copy_walk: We have already visited %N\n", node)); if (node_info->copy == NULL) { cp = rawcopy_node(node); - DB((dbg, LEVEL_5, "The TEMP copy of %ld is created %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + DB((dbg, LEVEL_5, "The TEMP copy of %N is created %N\n", node, cp)); } return; } @@ -808,7 +753,7 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, ir_loop * if (!is_Block(node)) { ir_node *pred = get_nodes_block(node); if (walk_condition(pred)) - DB((dbg, LEVEL_5, "walk block %ld\n", get_irn_node_nr(pred))); + DB((dbg, LEVEL_5, "walk block %N\n", pred)); copy_walk(pred, walk_condition, set_loop); } @@ -816,15 +761,15 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, ir_loop * NEW_ARR_A(ir_node *, cpin, arity); - for (i = get_irn_arity(node) - 1; i >= 0; --i) { + for (i = 0; i < arity; ++i) { ir_node *pred = get_irn_n(node, i); if (walk_condition(pred)) { - DB((dbg, LEVEL_5, "walk node %ld\n", get_irn_node_nr(pred))); + DB((dbg, LEVEL_5, "walk node %N\n", pred)); copy_walk(pred, walk_condition, set_loop); cpin[i] = get_copy(pred); - DB((dbg, LEVEL_5, "copy of %ld gets new in %ld which is copy of %ld\n", - get_irn_node_nr(node), get_irn_node_nr(get_copy(pred)), get_irn_node_nr(pred))); + DB((dbg, LEVEL_5, "copy of %N gets new in %N which is copy of %N\n", + node, get_copy(pred), pred)); } else { cpin[i] = pred; } @@ -834,62 +779,25 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition, ir_loop * if (node_info->copy == NULL) { /* No temporary copy existent */ cp = rawcopy_node(node); - DB((dbg, LEVEL_5, "The FINAL copy of %ld is CREATED %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + DB((dbg, LEVEL_5, "The FINAL copy of %N is CREATED %N\n", node, cp)); } else { /* temporary copy is existent but without correct ins */ cp = get_copy(node); - DB((dbg, LEVEL_5, "The FINAL copy of %ld is EXISTENT %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + 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)); set_nodes_block(cp, cpblock ); - /* fix the phi information in attr.phis */ - if( is_Phi(cp) ) + if (is_Phi(cp)) add_Block_phi(cpblock, cp); - } else { - /* macroblock info has not been copied */ - set_Block_MacroBlock(cp, cp); } set_irn_loop(cp, set_loop); set_irn_in(cp, ARR_LEN(cpin), cpin); } -/** - * This walker copies all walked nodes. - * If the walk_condition is true for a node, it is walked. - * All nodes node_info->copy attributes has to be NULL prior to every to every walk. - */ -static void loop_walker(ir_node *node, walker_condition *func) -{ - int i; - int arity; - ir_graph *irg = current_ir_graph; - - if (get_irn_visited(node) >= get_irg_visited(irg)) - return; - - /* Walk */ - mark_irn_visited(node); - - if (!is_Block(node)) { - ir_node *pred = get_nodes_block(node); - loop_walker(pred, func); - } - - arity = get_irn_arity(node); - - for (i = get_irn_arity(node) - 1; i >= 0; --i) { - ir_node *pred = get_irn_n(node, i); - loop_walker(pred, func); - } - - func(node); -} - - /** * Loop peeling, and fix the cf for the loop entry nodes, which have now more preds */ @@ -906,7 +814,7 @@ static void peel(out_edge *loop_outs) /* duplicate loop walk */ inc_irg_visited(current_ir_graph); - for(i = 0; i < ARR_LEN(loop_outs); i++) { + for (i = 0; i < ARR_LEN(loop_outs); i++) { out_edge entry = loop_outs[i]; ir_node *node = entry.node; ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n); @@ -917,11 +825,13 @@ static void peel(out_edge *loop_outs) } else { copy_walk(pred, is_in_loop, NULL); /* leave out keepalives */ - if (!is_End(node)) + if (!is_End(node)) { /* Node is user of a value defined inside the loop. * We'll need a phi since we duplicated the loop. */ /* Cannot construct_ssa here, because it needs another walker. */ - entry_buffer[entry_c++] = pred; + entry_buffer[entry_c] = pred; + ++entry_c; + } } } @@ -932,7 +842,7 @@ static void peel(out_edge *loop_outs) /* Generate phis for values from peeled code and original loop */ construct_ssa_foreach(entry_buffer, entry_c); - /*for(i = 0; i < entry_c; i++) + /*for (i = 0; i < entry_c; i++) { ir_node *cppred, *block, *cpblock, *pred; @@ -955,14 +865,14 @@ static void get_head_outs(ir_node *node, void *env) int arity = get_irn_arity(node); (void) env; - DB((dbg, LEVEL_5, "get head entries %ld \n", get_irn_node_nr(node))); + DB((dbg, LEVEL_5, "get head entries %N \n", node)); - for(i = 0; i < arity; ++i) { + for (i = 0; i < arity; ++i) { /* node is not in the head, but the predecessor is. * (head or loop chain nodes are marked) */ DB((dbg, LEVEL_5, "... ")); - DB((dbg, LEVEL_5, "node %ld marked %d (0) pred %d marked %d (1) \n", + DB((dbg, LEVEL_5, "node %N marked %d (0) pred %d marked %d (1) \n", node->node_nr, is_nodesblock_marked(node),i, is_nodesblock_marked(get_irn_n(node, i)))); if (!is_nodesblock_marked(node) && is_nodesblock_marked(get_irn_n(node, i))) { @@ -970,8 +880,8 @@ static void get_head_outs(ir_node *node, void *env) entry.node = node; entry.pred_irn_n = i; DB((dbg, LEVEL_5, - "Found head chain entry %ld @%d because !inloop %ld and inloop %ld\n", - get_irn_node_nr(node), i, get_irn_node_nr(node), get_irn_node_nr(get_irn_n(node, i)))); + "Found head chain entry %N @%d because !inloop %N and inloop %N\n", + node, i, node, get_irn_n(node, i))); ARR_APP1(out_edge, cur_head_outs, entry); } } @@ -982,12 +892,13 @@ static void get_head_outs(ir_node *node, void *env) * A block belongs to the chain if a condition branches out of the loop. * Returns 1 if the given block belongs to the condition chain. */ -static unsigned find_condition_chains(ir_node *block) { +static unsigned find_condition_chains(ir_node *block) +{ const ir_edge_t *edge; unsigned mark = 0; int nodes_n = 0; - DB((dbg, LEVEL_5, "condition_chains for block %ld\n", get_irn_node_nr(block))); + DB((dbg, LEVEL_5, "condition_chains for block %N\n", block)); /* Collect all outs, including keeps. * (TODO firm function for number of out edges?) */ @@ -995,10 +906,9 @@ static unsigned find_condition_chains(ir_node *block) { ++nodes_n; } - /* We do not want to collect more nodes from condition chains, than the limit allows us to. * Also, leave at least one block as body. */ - if (head_inversion_node_count + nodes_n > head_inversion_node_limit + if (head_inversion_node_count + nodes_n > inversion_head_node_limit || head_inversion_block_count + 1 == loop_info.blocks) { set_Block_mark(block, 0); @@ -1021,15 +931,16 @@ static unsigned find_condition_chains(ir_node *block) { } } - /* this block is not part of the chain, - * because the chain would become too long or we have no successor outside of the loop */ if (mark == 0) { + /* this block is not part of the chain, + * because the chain would become too long or we have no successor outside of the loop */ + set_Block_mark(block, 0); return 0; } else { set_Block_mark(block, 1); ++head_inversion_block_count; - DB((dbg, LEVEL_5, "block %ld is part of condition chain\n", get_irn_node_nr(block))); + DB((dbg, LEVEL_5, "block %N is part of condition chain\n", block)); head_inversion_node_count += nodes_n; } @@ -1045,7 +956,7 @@ static unsigned find_condition_chains(ir_node *block) { } mark_irn_visited(src); - DB((dbg, LEVEL_5, "condition chain walk %ld\n", get_irn_node_nr(src))); + DB((dbg, LEVEL_5, "condition chain walk %N\n", src)); inchain = find_condition_chains(src); /* if successor is not part of chain we need to collect its outs */ @@ -1079,8 +990,8 @@ static void inversion_fix_heads(void) int lhead_arity = backedges_n; int ihead_arity = headarity - backedges_n; - assert(lhead_arity != 0 && "loophead has arity 0. Probably wrong backedge informations."); - assert(ihead_arity != 0 && "inversionhead has arity 0. Probably wrong backedge informations."); + assert(lhead_arity != 0 && "Loophead has arity 0. Probably wrong backedge informations."); + assert(ihead_arity != 0 && "Inversionhead has arity 0. Probably wrong backedge informations."); /* new in arrays for all phis in the head blocks */ NEW_ARR_A(ir_node *, loopheadnins, lhead_arity); @@ -1103,14 +1014,12 @@ static void inversion_fix_heads(void) if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) { /* just copy these edges */ loopheadnins[lheadin_c] = pred; - /*get_node_info(pred)->link = NULL;*/ for_each_phi(loophead, phi) { get_node_info(phi)->ins[lheadin_c] = get_irn_n(phi, i); } ++lheadin_c; } else { invheadnins[iheadin_c] = pred; - /*get_node_info(pred)->link = (void *)1;*/ for_each_phi(invhead, phi) { get_node_info(phi)->ins[iheadin_c] = get_irn_n(phi, i) ; } @@ -1122,15 +1031,6 @@ static void inversion_fix_heads(void) set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins); set_irn_in(invhead, ARR_LEN(invheadnins), invheadnins); - -#if 0 - /* FIX and set former be to normal edges */ - fix_backedge_info(loophead); - fix_backedge_info(invhead); -#else - (void)fix_backedge_info; -#endif - /* assign the ins for the phis */ for_each_phi(loophead, phi) { ir_node **ins = get_node_info(phi)->ins; @@ -1155,9 +1055,11 @@ static void inversion_walk(out_edge *head_entries) head_phi_assign = NEW_ARR_F(ir_node *, 0); - /* Find assignments in the condition chain, to construct_ssa for them after the loop inversion. */ + /* Find assignments in the condition chain, + * to construct_ssa for them after the loop inversion. */ for_each_phi(loop_cf_head , phi) { - for(i=0; i 0) - do_peel = 1; -#endif - peel(cur_loop_outs); /* clean up */ @@ -1238,46 +1133,11 @@ void loop_peeling(void) } /* Loop inversion */ -void loop_inversion(void) +static void loop_inversion(void) { unsigned do_inversion = 1; - int i; - - -#if 0 - /* Loop complexity too high */ - if (loop_info.opnodes_n > max_opnodes) - return; -#endif - head_inversion_node_limit = INT_MAX; - -#if 0 - /* Search for invariant loads. */ - /* Did not apply on any of the testsuite cases. */ - - cur_loop_outs = NEW_ARR_F(out_edge, 0); - irg_walk_graph( current_ir_graph, get_loop_outs, NULL, NULL ); - - for(i = 0; i < ARR_LEN(cur_loop_outs); ++i) { - out_edge entry = cur_loop_outs[i]; - ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n); - loop_walker(pred, get_invariants); - } - - DEL_ARR_F(cur_loop_outs); - - /* This could be improved with knowledge about variable range.*/ - if (loop_info.stores == 0 && loop_info.invariant_loads > 0) { - /* Does not happen for any of the testsuite cases. */ - loop_info.do_invariant_opt = 1; - } - -#else - (void)loop_walker; - (void)get_invariants; - (void)i; -#endif + inversion_head_node_limit = INT_MAX; /* Search for condition chains. */ ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); @@ -1332,7 +1192,7 @@ void loop_inversion(void) * Returns last element of linked list of copies by * walking the linked list. */ -ir_node *get_last_copy(ir_node *node) +static ir_node *get_last_copy(ir_node *node) { ir_node *copy, *cur; cur = node; @@ -1345,7 +1205,7 @@ ir_node *get_last_copy(ir_node *node) /** * Rewire floating copies of the current loop. */ -void unrolling_fix_cf(void) +static void unrolling_fix_cf(void) { ir_node *loophead = loop_cf_head; int headarity = get_irn_arity(loophead); @@ -1353,9 +1213,7 @@ void unrolling_fix_cf(void) /*ir_node *high, *low;*/ int i; - int uhead_in_n = 0; - int backedges_n = get_backedge_n(loophead, 0); int unroll_arity = backedges_n; @@ -1390,7 +1248,7 @@ void unrolling_fix_cf(void) get_node_info(phi_copy)->ins[uhead_in_n] = get_irn_n(phi, i); } } - /*last_head = upper_head;*/ + last_pred = upper_pred; ++uhead_in_n; @@ -1413,48 +1271,78 @@ void unrolling_fix_cf(void) } } +#if 0 +static ir_node *add_phi(ir_node *node, int phi_pos) +{ + ir_mode *mode; + ir_node *phi; + ir_node **in; + mode = get_irn_mode(get_irn_n(node, phi_pos)); + ir_node *block = get_nodes_block(node); + int n_cfgpreds = get_irn_arity(block); + ir_node *pred = get_irn_n(node, phi_pos); + int i; + + /* create a new Phi */ + NEW_ARR_A(ir_node*, in, n_cfgpreds); + for (i = 0; i < n_cfgpreds; ++i) + in[i] = new_Unknown(mode); /*pred;*/ + + phi = new_r_Phi(block, n_cfgpreds, in, mode); + + assert(phi && "phi null"); + assert(is_Bad(phi) && "phi bad"); + + /* Important: always keep block phi list up to date. */ + add_Block_phi(block, phi); + /* EVERY node is assumed to have a node_info linked. */ + alloc_node_info(phi, NULL); + + set_irn_n(node, phi_pos, phi); + return phi; +} +#endif + + /** * Loop unrolling * Could be improved with variable range informations. */ -void loop_unrolling(void) +static void loop_unrolling(void) { int i, j; - ir_node **entry_buffer; - int entry_c = 0; - unroll_times = 2; + unroll_times = 7; cur_loop_outs = NEW_ARR_F(out_edge, 0); irg_walk_graph( current_ir_graph, get_loop_outs, NULL, NULL ); ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); - NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(cur_loop_outs)); /* duplicate whole loop content */ inc_irg_visited(current_ir_graph); - for(i = 0; i < ARR_LEN(cur_loop_outs); i++) { + for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) { out_edge entry = cur_loop_outs[i]; ir_node *node = entry.node; ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n); - - /* build linked list of copied nodes/blocks */ - if (is_Block(node)) { - for (j = 0; j < unroll_times-1; ++j) { + if (!is_Block(node)) { + for (j = 0; j < unroll_times - 1; ++j) { copy_walk(pred, is_in_loop, cur_loop); - duplicate_preds(node, entry.pred_irn_n, get_copy(pred)); - pred = get_copy(pred); } - } else { - for (j = 0; j < unroll_times-1; ++j) { + } + } + + for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) { + out_edge entry = cur_loop_outs[i]; + ir_node *node = entry.node; + ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n); + + if (is_Block(node)) { + for (j = 0; j < unroll_times - 1; ++j) { copy_walk(pred, is_in_loop, cur_loop); - if (!is_End(node)) /* leave out keepalives */ - /* Node node is user of a value defined inside the loop. - * We need a phi since we duplicated the loop. */ - /* Cannot construct_ssa here, because that would need another walker. */ - entry_buffer[entry_c++] = pred; + duplicate_preds(node, entry.pred_irn_n, get_copy(pred)); pred = get_copy(pred); } @@ -1462,13 +1350,33 @@ void loop_unrolling(void) } ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); - DEL_ARR_F(cur_loop_outs); + /*dump_ir_graph(current_ir_graph, "-raw");*/ + + /* LDBG 2 */ +#if 1 /* Line up the floating copies. */ unrolling_fix_cf(); /* Generate phis for all loop outs */ - construct_ssa_foreach(entry_buffer, entry_c); + for (i = 0; i < ARR_LEN(cur_loop_outs); ++i) { + out_edge entry = cur_loop_outs[i]; + ir_node *node = entry.node; + ir_node *pred = get_irn_n(entry.node, entry.pred_irn_n); + + if (!is_Block(node) && !is_End(node)) { + DB((dbg, LEVEL_5, " construct_ssa_n def %N node %N pos %d\n", + pred, node, entry.pred_irn_n)); + construct_ssa_n(pred, node); + } + } +#endif + + DEL_ARR_F(cur_loop_outs); + + set_irg_doms_inconsistent(current_ir_graph); + set_irg_loopinfo_inconsistent(current_ir_graph); + set_irg_outs_inconsistent(current_ir_graph); } /* Initialization and */ @@ -1482,15 +1390,12 @@ static void init_analyze(ir_loop *loop) loop_inv_head = NULL; loop_peeled_head = NULL; + loop_info.outs = 0; loop_info.calls = 0; - loop_info.invariant_loads = 0; loop_info.loads = 0; - loop_info.stores = 0; - loop_info.opnodes_n = 0; loop_info.blocks = 0; - loop_info.outs = 0; - DB((dbg, LEVEL_2, " >>>> current loop includes node %ld <<<\n", get_irn_node_nr(get_loop_node(loop, 0)))); + DB((dbg, LEVEL_2, " >>>> current loop includes node %N <<<\n", get_loop_node(loop, 0))); irg_walk_graph(current_ir_graph, get_loop_info, NULL, NULL); @@ -1514,7 +1419,7 @@ static void init_analyze(ir_loop *loop) return; #endif - DB((dbg, LEVEL_2, " <<<< end of loop with node %ld >>>>\n", get_irn_node_nr(get_loop_node(loop, 0)))); + DB((dbg, LEVEL_2, " <<<< end of loop with node %N >>>>\n", get_loop_node(loop, 0))); } /* Find most inner loops and send them to analyze_loop */ @@ -1541,7 +1446,7 @@ static void find_most_inner_loop(ir_loop *loop) } } else { int s; - for(s=0; s>> unrolling (Startnode %ld) <<<\n", - get_irn_node_nr(get_irg_start(irg)))); + DB((dbg, LEVEL_2, " >>> unrolling (Startnode %N) <<<\n", + get_irg_start(irg))); loop_optimization(irg); - DB((dbg, LEVEL_2, " >>> unrolling done (Startnode %ld) <<<\n", - get_irn_node_nr(get_irg_start(irg)))); + DB((dbg, LEVEL_2, " >>> unrolling done (Startnode %N) <<<\n", + get_irg_start(irg))); } void do_loop_inversion(ir_graph *irg) @@ -1662,13 +1569,13 @@ void do_loop_inversion(ir_graph *irg) enable_peeling = 0; enable_inversion = 1; - DB((dbg, LEVEL_2, " >>> inversion (Startnode %ld) <<<\n", - get_irn_node_nr(get_irg_start(irg)))); + DB((dbg, LEVEL_2, " >>> inversion (Startnode %N) <<<\n", + get_irg_start(irg))); loop_optimization(irg); - DB((dbg, LEVEL_2, " >>> inversion done (Startnode %ld) <<<\n", - get_irn_node_nr(get_irg_start(irg)))); + DB((dbg, LEVEL_2, " >>> inversion done (Startnode %N) <<<\n", + get_irg_start(irg))); } void do_loop_peeling(ir_graph *irg) @@ -1677,14 +1584,29 @@ void do_loop_peeling(ir_graph *irg) enable_peeling = 1; enable_inversion = 0; - DB((dbg, LEVEL_2, " >>> peeling (Startnode %ld) <<<\n", - get_irn_node_nr(get_irg_start(irg)))); + DB((dbg, LEVEL_2, " >>> peeling (Startnode %N) <<<\n", + get_irg_start(irg))); loop_optimization(irg); - DB((dbg, LEVEL_2, " >>> peeling done (Startnode %ld) <<<\n", - get_irn_node_nr(get_irg_start(irg)))); + DB((dbg, LEVEL_2, " >>> 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)