X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Floop.c;h=7aceb2dc2423e19805d91f03513b69cb2eac03ec;hb=a12f2398dca4d747909c57d749beab8a0e36698a;hp=90a706620c4048f4643e63206834e022cec48807;hpb=b2841b518c71c38924d6d64d290cebd1a4aa3a7a;p=libfirm diff --git a/ir/opt/loop.c b/ir/opt/loop.c index 90a706620..7aceb2dc2 100644 --- a/ir/opt/loop.c +++ b/ir/opt/loop.c @@ -19,8 +19,9 @@ /** * @file - * @brief Loop peeling and unrolling * @author Christian Helmer + * @brief loop inversion and loop unrolling, loop peeling + * * @version $Id$ */ #include "config.h" @@ -37,11 +38,12 @@ #include "irtools.h" #include "array_t.h" /* automatic array */ #include "beutil.h" /* get_block */ -#include "irloop_t.h" /* set_irn_loop */ +#include "irloop_t.h" /* set_irn_loop*/ + +#if 0 + #include "irdump_t.h" +#endif -// TODO during DBG -//#include "irnode_t.h" -#include "irdump.h" DEBUG_ONLY(static firm_dbg_module_t *dbg); @@ -55,17 +57,17 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg); /* current loop */ static ir_loop *cur_loop; -/* The loop walker should be possible to abort if nothing can be done anymore */ +/* abortable walker function */ typedef unsigned irg_walk_func_abortable(ir_node *, void *); -/* condition for breaking a copy_walk */ +/* condition for walking a node during a copy_walk */ typedef unsigned walker_condition(ir_node *); -/* stores node and position of a predecessor */ +/* node and position of a predecessor */ typedef struct out_edges { ir_node *node; int pred_irn_n; -} out_edges; +} out_edge; /* access complex values through the nodes links */ typedef struct node_info { @@ -73,17 +75,20 @@ typedef struct node_info { ir_node *copy; ir_node *link; /* temporary links for ssa creation */ ir_node **ins; /* ins for phi nodes, during rewiring of blocks */ + unsigned done; struct node_info *freelistnext; /* linked list to free all node_infos */ } node_info; static node_info *link_node_state_list; /* head of the linked list to free all node_infos */ -static out_edges *cur_loop_outs; /* A walker may start visiting the current loop with these nodes. */ -static out_edges *cur_head_outs; /* A walker may start visiting the cur head with these nodes. */ +static out_edge *cur_loop_outs; /* A walker may start visiting the current loop with these nodes. */ +static out_edge *cur_head_outs; /* A walker may start visiting the cur head with these nodes. */ static ir_node *loop_cf_head = NULL; /* Loop head node */ static unsigned loop_cf_head_valid = 1; /* A loop may have one head, otherwise we do not touch it. */ +ir_node **loops; + /* Inverted head */ static ir_node *loop_inv_head = NULL; /* Peeled head */ @@ -91,30 +96,41 @@ static ir_node *loop_peeled_head = NULL; /* Loop analysis informations */ typedef struct loop_info_t { - unsigned calls; - unsigned loads; - unsigned invariant_loads; /* number of load nodes */ - unsigned stores; /* number of store nodes */ unsigned blocks; /* number of blocks in the loop */ - unsigned opnodes_n; /* nodes that should result in an instruction */ - unsigned opnodes_head; + 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 opnodes_n; /* nodes that probably result in an instruction */ + unsigned do_invariant_opt; +#endif } loop_info_t; /* Information about the current loop */ static loop_info_t loop_info; /* A walker may start visiting a condition chain with these nodes. */ -static out_edges *cond_chain_entries; +static out_edge *cond_chain_entries; + +/* Number of unrolling */ +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; +static unsigned enable_inversion; +static unsigned enable_unrolling; + /** * * ============= AUXILIARY FUNCTIONS ===================================== */ + /** * Creates object on the heap, and adds it to a linked list to free it later. */ @@ -135,20 +151,24 @@ static node_info *get_node_info(ir_node *n) /* Allocates a node_info struct for the given node. For use with a walker. */ static void alloc_node_info(ir_node *node, void *env) { - node_info *state = new_node_info(); + node_info *state; (void) env; + state = new_node_info(); set_irn_link(node, (void *)state); } static void free_node_info(void) { - node_info *next; - next = link_node_state_list; - while(next->freelistnext) { - node_info *cur = next; - next = cur->freelistnext; - xfree( cur ); + int a = 0; + node_info *n; + n = link_node_state_list; + while(n) { + node_info *next = n->freelistnext; + ++a; + xfree(n); + n = next; } + link_node_state_list = NULL; } /** @@ -168,19 +188,48 @@ static void reset_node_infos(void) } } -/* Returns the */ +/* 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 a nodes copy. */ static ir_node *get_copy(ir_node *n) { return ((node_info *)get_irn_link(n))->copy; } -/* Links the node to its copy */ +/* Sets a nodes 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 */ +/** + * 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)) + +/* + * Returns 0 if the node or block is not in cur_loop. + */ static unsigned is_in_loop(ir_node *node) { return (get_irn_loop(get_block(node)) == cur_loop); @@ -192,13 +241,12 @@ static unsigned is_alien_edge(ir_node *n, int i) return(!is_in_loop(get_irn_n(n, i))); } -/* used for walker */ -static void unmark_block(ir_node *node, void * env) +/* used for block walker */ +static void reset_block_mark(ir_node *node, void * env) { (void) env; - DB((dbg, LEVEL_4, "UNMARK ...")); - DB((dbg, LEVEL_4, " UNMARK %ld\n", get_irn_node_nr(node))); - if(is_Block(node)) + + if (is_Block(node)) set_Block_mark(node, 0); } @@ -215,7 +263,7 @@ int get_loop_n_blocks(ir_loop *loop) { for(e=0; einvariant ) ) { - get_node_info(node)->invariant = 1; - ++loop_info.invariant_loads; - } else - { - get_node_info(node)->invariant = 0; - } - } else { - int i; - invar = 1; - /* find loop variant preds */ - for(i = 0; i < arity; ++i) { - ir_node *pred = get_irn_n(node, i); - - if ( is_in_loop(pred) /* outside loop is loop invariant */ - && !is_Const(pred) /* constants */ - && !is_SymConst(pred) /* SymConst */ - && !get_node_info(node)->invariant ) { /* pred is marked as invariant */ - invar = 0; - } - } + arity = get_irn_arity(node); + for (i = 0; i < arity; i++) { + ir_node *pred = get_irn_n(node, i); - if (invar) { - get_node_info(node)->invariant = 1; - } else { - get_node_info(node)->invariant = 0; + pred_in_loop = is_in_loop(pred); + node_in_loop = is_in_loop(node); + + if (pred_in_loop && !node_in_loop) { + out_edge entry; + entry.node = node; + entry.pred_irn_n = i; + ARR_APP1(out_edge, cur_loop_outs, entry); } } - 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) { @@ -375,7 +388,7 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) ir_node *phi; ir_node **in; - DB((dbg, LEVEL_4, "ssa sdacp: block %ld\n", get_irn_node_nr(block))); + DB((dbg, LEVEL_5, "ssa search_def_and_create_phis: block %ld\n", get_irn_node_nr(block))); /* Prevents creation of phi that would be bad anyway. * Dead and bad blocks. */ @@ -383,14 +396,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_4, "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 %ld\n", get_irn_node_nr(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_4, "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 %ld\n", get_irn_node_nr(value))); return value; } @@ -403,10 +416,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_4, "ssa 1 pred: walk pred %ld\n", get_irn_node_nr(pred_block))); + DB((dbg, LEVEL_5, "ssa 1 pred: walk pred %ld\n", get_irn_node_nr(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; @@ -424,26 +437,29 @@ 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_4, "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 %ld to block %ld\n", get_irn_node_nr(phi), get_irn_node_nr(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) { + ir_node *pred_val; ir_node *pred_block = get_Block_cfgpred_block(block, i); - ir_node *pred_val = search_def_and_create_phis(pred_block, mode); - DB((dbg, LEVEL_4, "ssa phi pred:phi %ld, pred %ld\n", get_irn_node_nr(phi), get_irn_node_nr(pred_val))); + assert(pred_block != NULL); + pred_val = search_def_and_create_phis(pred_block, mode); + 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))); 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) @@ -466,7 +482,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; @@ -483,7 +499,7 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, if (is_End(user)) continue; - DB((dbg, LEVEL_4, "original user %ld\n", get_irn_node_nr(user))); + DB((dbg, LEVEL_5, "original user %ld\n", get_irn_node_nr(user))); if (is_Phi(user)) { ir_node *pred_block = get_Block_cfgpred_block(user_block, j); @@ -500,6 +516,72 @@ 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 %ld to block %ld\n", + get_irn_node_nr(iter), get_irn_node_nr(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) +{ + int i; + for(i = 0; i < arr_n; ++i) { + ir_node *cppred, *block, *cpblock, *pred; + + pred = arr[i]; + cppred = get_copy(pred); + block = get_nodes_block(pred); + cpblock = get_nodes_block(cppred); + construct_ssa(block, pred, cpblock, cppred); + } +} + /* get the number of backedges without alien bes */ static int get_backedge_n(ir_node *loophead, unsigned with_alien) { @@ -508,34 +590,12 @@ static int get_backedge_n(ir_node *loophead, unsigned with_alien) int arity = get_irn_arity(loophead); for (i = 0; i < arity; ++i) { ir_node *pred = get_irn_n(loophead, i); - if (is_backedge(loophead, i) && ( with_alien || is_in_loop(pred)) ) + if (is_backedge(loophead, i) && (with_alien || is_in_loop(pred))) ++be_n; } 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); - else - set_not_backedge(node, i); - } -} - -/** - * - * ============= PEELING ===================================== - * - */ - /** * Rewires the heads after peeling. */ @@ -579,30 +639,25 @@ static void peel_fix_heads(void) */ if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) { loopheadnins[lheadin_c] = orgjmp; - /* marks out edge as backedge */ - get_node_info(orgjmp)->link = orgjmp; for_each_phi(loophead, phi) { get_node_info( phi )->ins[lheadin_c] = get_irn_n( phi, i) ; } ++lheadin_c; - loopheadnins[lheadin_c] = copyjmp; /* former bes of the peeled code origin now from the loophead */ - /* marks out edge as normal edge */ - get_node_info(copyjmp)->link = NULL; - /* get_irn_n( get_copy_of(phi), i) get_copy_of(get_irn_n( phi, i)) + /* former bes of the peeled code origin now from the loophead */ + loopheadnins[lheadin_c] = copyjmp; + + /* get_irn_n( get_copy_of(phi), i ) get_copy_of( get_irn_n( phi, i) ) * Order is crucial! Predecessors outside of the loop are non existent. * The copy (cloned with its ins!) has pred i, * but phis pred i might not have a copy of itself. */ for_each_phi(loophead, phi) { - //printf("normalbe phi %ld @ %d -> %ld\n", phi->node_nr, i, get_irn_n( get_copy_of(phi), i)->node_nr); get_node_info( phi )->ins[lheadin_c] = get_irn_n( get_copy(phi), i) ; } ++lheadin_c; } else { peelheadnins[pheadin_c] = orgjmp; - /* marks out edge as normal edge */ - get_node_info(orgjmp)->link = NULL; for_each_phi(peelhead, phi) { get_node_info( phi )->ins[pheadin_c] = get_irn_n(phi, i); } @@ -610,22 +665,14 @@ static void peel_fix_heads(void) } }/* for */ - //DBG assert(pheadin_c == ARR_LEN(peelheadnins) && lheadin_c == ARR_LEN(loopheadnins) && "the constructed head arities do not match the predefined arities"); - /** - * assign the ins to the nodes - */ + /* assign the ins to the nodes */ set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins); set_irn_in(peelhead, ARR_LEN(peelheadnins), peelheadnins); - /* Fixes the backedge information according to the link. - * Following loop optimizations might depend on it. */ - fix_backedge_info(loophead); - fix_backedge_info(peelhead); - for_each_phi(loophead, phi) { ir_node **ins = get_node_info( phi )->ins; set_irn_in(phi, lhead_arity, ins); @@ -639,64 +686,42 @@ 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) { + int i, arity; ir_node *cp; node_info *cpstate; cp = exact_copy(node); + + arity = get_irn_arity(node); + + for (i = 0; i < arity; ++i) { + if (is_backedge(node, i)) + set_backedge(cp, i); + } + 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 do we need to do this anyway? */ + set_Block_MacroBlock(cp, cp); + } return cp; } -//int temp = 0; -// -///* This walker copies all walked nodes. The walk_condition determines the nodes to walk. */ -//static void keepalives_walk(ir_node *node, walker_condition *walk_condition) -//{ -// int i; -// int arity; -// ir_graph *irg = current_ir_graph; -// -// /** -// * break condition and cycle resolver, creating temporary node copies -// */ -// if (get_irn_visited(node) >= get_irg_visited(irg)) { -// return; -// } -// -// /* Walk */ -// mark_irn_visited(node); -// -// if (!is_Block(node)) { -// ir_node *pred = get_nodes_block(node); -// if (walk_condition(pred)) -// keepalives_walk( pred, walk_condition ); -// } -// -// arity = get_irn_arity(node); -// -// for (i = get_irn_arity(node) - 1; i >= 0; --i) { -// ir_node *pred = get_irn_n(node, i); -// -// if (walk_condition(pred)) -// keepalives_walk( pred, walk_condition ); -// } -// -// add_End_keepalive(get_irg_end(current_ir_graph), node); -//} - - /** * This walker copies all walked nodes. * If the walk_condition is true for a node, it is walked. * All nodes node_info->copy attributes has to be NULL prior to every to every walk. */ -static void copy_walk(ir_node *node, walker_condition *walk_condition) +static void copy_walk(ir_node *node, walker_condition *walk_condition, ir_loop *set_loop) { int i; int arity; @@ -710,29 +735,22 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition) */ if (get_irn_visited(node) >= get_irg_visited(irg)) { /* Here we rely on nodestate's copy being initialized with NULL */ - DB((dbg, LEVEL_4, "copy_walk: We have already visited %ld\n", get_irn_node_nr(node))); + DB((dbg, LEVEL_5, "copy_walk: We have already visited %ld\n", get_irn_node_nr(node))); if (node_info->copy == NULL) { -// if (!is_Const(node) && !is_SymConst(node)) { - cp = rawcopy_node(node); -// } else { -// cp = node; -// node_info->copy = cp; -// } - DB((dbg, LEVEL_4, "The TEMP copy of %ld is created %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + 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))); } return; } -// add_End_keepalive(get_irg_end(current_ir_graph), node); - /* Walk */ mark_irn_visited(node); if (!is_Block(node)) { ir_node *pred = get_nodes_block(node); if (walk_condition(pred)) - DB((dbg, LEVEL_4, "walk block %ld\n", get_irn_node_nr(pred))); - copy_walk( pred, walk_condition ); + DB((dbg, LEVEL_5, "walk block %ld\n", get_irn_node_nr(pred))); + copy_walk(pred, walk_condition, set_loop); } arity = get_irn_arity(node); @@ -743,11 +761,11 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition) ir_node *pred = get_irn_n(node, i); if (walk_condition(pred)) { - DB((dbg, LEVEL_4, "walk node %ld\n", get_irn_node_nr(pred))); - copy_walk( pred, walk_condition ); + DB((dbg, LEVEL_5, "walk node %ld\n", get_irn_node_nr(pred))); + copy_walk(pred, walk_condition, set_loop); cpin[i] = get_copy(pred); - DB((dbg, LEVEL_4, "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 %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))); } else { cpin[i] = pred; } @@ -756,19 +774,12 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition) /* copy node / finalize temp node */ if (node_info->copy == NULL) { /* No temporary copy existent */ - - /* Do not copy constants TODO right? */ -// if (!is_Const(node) && !is_SymConst(node)) { - cp = rawcopy_node(node); -// } else { -// cp = node; -// node_info->copy = cp; -// } - DB((dbg, LEVEL_4, "The FINAL copy of %ld is CREATED %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); + 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))); } else { /* temporary copy is existent but without correct ins */ cp = get_copy(node); - DB((dbg, LEVEL_4, "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 %ld is EXISTENT %ld\n", get_irn_node_nr(node), get_irn_node_nr(cp))); } if (!is_Block(node)) { @@ -778,18 +789,16 @@ static void copy_walk(ir_node *node, walker_condition *walk_condition) /* fix the phi information in attr.phis */ if( is_Phi(cp) ) add_Block_phi(cpblock, cp); - } else { - /* macroblock info has not been copied */ - set_Block_MacroBlock(cp, cp); } - //TODO do? - //set_irn_loop(cp, cur_loop); + set_irn_loop(cp, set_loop); set_irn_in(cp, ARR_LEN(cpin), cpin); } -/* Loop peeling, and fix the cf for the loop entry nodes, which have now more preds */ -static void peel(out_edges *loop_outs) +/** + * Loop peeling, and fix the cf for the loop entry nodes, which have now more preds + */ +static void peel(out_edge *loop_outs) { int i; ir_node **entry_buffer; @@ -800,23 +809,23 @@ static void peel(out_edges *loop_outs) NEW_ARR_A(ir_node *, entry_buffer, ARR_LEN(loop_outs)); /* duplicate loop walk */ -// cur_head = loop_cf_head; inc_irg_visited(current_ir_graph); for(i = 0; i < ARR_LEN(loop_outs); i++) { - out_edges entry = 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); if (is_Block(node)) { - copy_walk( pred, is_in_loop ); + copy_walk(pred, is_in_loop, NULL); duplicate_preds(node, entry.pred_irn_n, get_copy(pred) ); } else { - copy_walk( pred, is_in_loop ); - if (!is_End(node)) /* leave out keepalives */ + copy_walk(pred, is_in_loop, NULL); + /* leave out keepalives */ + 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 */ + /* Cannot construct_ssa here, because it needs another walker. */ entry_buffer[entry_c++] = pred; } } @@ -827,49 +836,48 @@ static void peel(out_edges *loop_outs) peel_fix_heads(); /* Generate phis for values from peeled code and original loop */ - for(i = 0; i < entry_c; i++) + construct_ssa_foreach(entry_buffer, entry_c); + /*for(i = 0; i < entry_c; 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 = entry_buffer[i]; cppred = get_copy(pred); block = get_nodes_block(pred); cpblock = get_nodes_block(cppred); construct_ssa(block, pred, cpblock, cppred); - } + }*/ } -/* +/** * Populates head_entries with (node, pred_pos) tuple * whereas the node's pred at pred_pos is in the head but not the node itself. * Head and condition chain blocks must be marked. */ -static void get_head_entries(ir_node *node, void *env) +static void get_head_outs(ir_node *node, void *env) { int i; int arity = get_irn_arity(node); (void) env; - DB((dbg, LEVEL_5, "get head entries \n")); + DB((dbg, LEVEL_5, "get head entries %ld \n", get_irn_node_nr(node))); for(i = 0; i < arity; ++i) { /* node is not in the head, but the predecessor is. * (head or loop chain nodes are marked) */ + DB((dbg, LEVEL_5, "... ")); DB((dbg, LEVEL_5, "node %ld 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)))); + 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))) { - out_edges entry; + out_edge entry; entry.node = node; entry.pred_irn_n = i; - DB((dbg, LEVEL_4, - "Found head chain entry %ld @%d because !inloop %ld and inloop %ld\n", - node->node_nr, i, node->node_nr, get_irn_n(node, i)->node_nr)); - ARR_APP1(out_edges, cur_head_outs, entry); + 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)))); + ARR_APP1(out_edge, cur_head_outs, entry); } } } @@ -877,65 +885,56 @@ static void get_head_entries(ir_node *node, void *env) /** * Find condition chains, and add them to be inverted, until the node count exceeds the limit. * A block belongs to the chain if a condition branches out of the loop. - * Returns if the given block belongs to the condition chain. - * FIXME prevent collecting ALL loop blocks (may happen if all blocks jump out of the loop) + * Returns 1 if the given block belongs to the condition chain. */ -static unsigned 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; - printf("cd %ld\n", block->node_nr); + DB((dbg, LEVEL_5, "condition_chains for block %ld\n", get_irn_node_nr(block))); - /* we need all outs, including keeps (TODO firm function for that??) */ + /* Collect all outs, including keeps. + * (TODO firm function for number of out edges?) */ foreach_out_edge_kind(block, edge, EDGE_KIND_NORMAL) { ++nodes_n; } /* We do not want to collect more nodes from condition chains, than the limit allows us to. * Also, leave at least one block as body. */ - if (head_inversion_node_count + nodes_n > head_inversion_node_limit - || loop_info.blocks == head_inversion_block_count + 1) { + if (head_inversion_node_count + nodes_n > inversion_head_node_limit + || head_inversion_block_count + 1 == loop_info.blocks) { set_Block_mark(block, 0); - printf(" %ld over limit\n", block->node_nr); + return 0; } - printf("blocks ++ %ld\n", block->node_nr); -// ++loop_info.blocks; - /* First: check our successors, and add all succs that are outside of the loop to the list */ foreach_block_succ(block, edge) { ir_node *src = get_edge_src_irn( edge ); int pos = get_edge_src_pos( edge ); - printf("check %ld\n", src->node_nr); - - if (src->loop) - printf(" src %ld in loop %ld curlooop %ld \n", src->node_nr, src->loop->loop_nr, cur_loop->loop_nr); if (!is_in_loop(src)) { - out_edges entry; - printf(" src %ld @ %d into block %ld \n", src->node_nr, pos, block->node_nr); + out_edge entry; mark = 1; entry.node = src; entry.pred_irn_n = pos; - ARR_APP1(out_edges, cond_chain_entries, entry); + ARR_APP1(out_edge, cond_chain_entries, entry); mark_irn_visited(src); } } - /* this block is not part of the chain, - * because the chain would become too big or we have no succ outside of the loop */ if (mark == 0) { - printf("mark is 0 %ld\n", block->node_nr); + /* 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 { - printf("mark is 1 %ld\n", block->node_nr); set_Block_mark(block, 1); ++head_inversion_block_count; - DB((dbg, LEVEL_4, "block %ld is part of condition chain\n", get_irn_node_nr(block))); + DB((dbg, LEVEL_5, "block %ld is part of condition chain\n", get_irn_node_nr(block))); head_inversion_node_count += nodes_n; } @@ -947,27 +946,26 @@ static unsigned condition_chains(ir_node *block) { /* already done cases */ if (!is_in_loop( src ) || (get_irn_visited(src) >= get_irg_visited(current_ir_graph))) { -// printf("!inloop || visited %ld\n", block->node_nr); continue; } mark_irn_visited(src); - DB((dbg, LEVEL_4, "condition chain walk %ld\n", get_irn_node_nr(src))); - inchain = condition_chains( src ); + DB((dbg, LEVEL_5, "condition chain walk %ld\n", get_irn_node_nr(src))); + inchain = find_condition_chains(src); /* if successor is not part of chain we need to collect its outs */ - if ( !inchain ) { - out_edges entry; + if (!inchain) { + out_edge entry; entry.node = src; entry.pred_irn_n = pos; - ARR_APP1(out_edges, cond_chain_entries, entry); + ARR_APP1(out_edge, cond_chain_entries, entry); } } return mark; } /** - * + * Rewire the loop head and inverted head for loop inversion. */ static void inversion_fix_heads(void) { @@ -983,8 +981,11 @@ static void inversion_fix_heads(void) int iheadin_c = 0; int backedges_n = get_backedge_n(loophead, 0); - int lhead_arity = headarity - backedges_n; - int ihead_arity = backedges_n; + 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."); /* new in arrays for all phis in the head blocks */ NEW_ARR_A(ir_node *, loopheadnins, lhead_arity); @@ -1004,21 +1005,21 @@ static void inversion_fix_heads(void) * Rewire the head blocks ins and their phi ins. * Requires phi list per block. */ - if ( is_backedge(loophead, i) && !is_alien_edge(loophead, i) ) { - invheadnins[iheadin_c] = pred; - for_each_phi(invhead, phi) { - get_node_info( phi )->ins[iheadin_c] = get_irn_n( phi, i) ; - } - ++iheadin_c; - } else { + if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) { /* just copy these edges */ loopheadnins[lheadin_c] = pred; for_each_phi(loophead, phi) { - get_node_info( phi )->ins[lheadin_c] = get_irn_n(phi, i); + get_node_info(phi)->ins[lheadin_c] = get_irn_n(phi, i); } ++lheadin_c; + } else { + invheadnins[iheadin_c] = pred; + for_each_phi(invhead, phi) { + get_node_info(phi)->ins[iheadin_c] = get_irn_n(phi, i) ; + } + ++iheadin_c; } - }/* for */ + } /* assign the ins to the head blocks */ set_irn_in(loophead, ARR_LEN(loopheadnins), loopheadnins); @@ -1036,8 +1037,7 @@ static void inversion_fix_heads(void) } } - -static void loop_inversion_walk(out_edges *head_entries) +static void inversion_walk(out_edge *head_entries) { int i; ir_node *phi; @@ -1050,10 +1050,10 @@ static void loop_inversion_walk(out_edges *head_entries) head_phi_assign = NEW_ARR_F(ir_node *, 0); /* Find assignments in the condition chain, to construct_ssa for them after the loop inversion. */ - for_each_phi( loop_cf_head , phi) { + for_each_phi(loop_cf_head , phi) { for(i=0; i No Inversion done.\n", loop_info.blocks)); } - /* Generate phis for values that are assigned in the condition chain - * but not read in the loops body. - */ - for(i = 0; i < ARR_LEN(head_phi_assign); ++i) { - ir_node *def_block, *inhead_phi_def, *inv_def_block, *inv_inhead_phi_def; - /* Note: construct_ssa only fixes the FIRST nodes usage. */ - inhead_phi_def = head_phi_assign[i]; - inv_inhead_phi_def = get_copy(inhead_phi_def); - def_block = get_nodes_block(inhead_phi_def); - inv_def_block = get_nodes_block(inv_inhead_phi_def); - DB((dbg, LEVEL_4, - "construct_ssa (condition chain out values) original %ld and clone %ld\n", - get_irn_node_nr(inv_inhead_phi_def), get_irn_node_nr(inhead_phi_def))); - construct_ssa(inv_def_block, inv_inhead_phi_def, def_block, inhead_phi_def); + /* We also catch endless loops here, + * because they do not have a condition chain. */ + if (head_inversion_block_count < 1) { + do_inversion = 0; + DB((dbg, LEVEL_3, "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n", head_inversion_block_count)); } - loop_cf_head = get_copy(loop_cf_head); + + if (do_inversion) { + cur_head_outs = NEW_ARR_F(out_edge, 0); + + /* Get all edges pointing into the head or condition chain (outs). */ + irg_walk_graph(current_ir_graph, get_head_outs, NULL, NULL); + inversion_walk(cur_head_outs); + + DEL_ARR_F(cur_head_outs); + + set_irg_doms_inconsistent(current_ir_graph); + set_irg_loopinfo_inconsistent(current_ir_graph); + set_irg_outs_inconsistent(current_ir_graph); + } + + /* free */ + DEL_ARR_F(cond_chain_entries); + ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); } /** - * Decide if loop inversion, peeling or unrolling should be performed. - * Inversion creates abnormal looking loops. Be careful with optimizations after that. + * Returns last element of linked list of copies by + * walking the linked list. */ -static void decision_maker(void) +ir_node *get_last_copy(ir_node *node) { - unsigned do_peel = 0; - unsigned do_inversion = 1; + ir_node *copy, *cur; + cur = node; + while ((copy = get_copy(cur))) { + cur = copy; + } + return cur; +} - /* unsigned max_loop_opnodes = 2000000; */ +/** + * Rewire floating copies of the current loop. + */ +void unrolling_fix_cf(void) +{ + ir_node *loophead = loop_cf_head; + int headarity = get_irn_arity(loophead); + ir_node *phi, *headnode; + /*ir_node *high, *low;*/ + int i; - head_inversion_node_limit = 99910; + int uhead_in_n = 0; + int backedges_n = get_backedge_n(loophead, 0); + int unroll_arity = backedges_n; + + /* Create ins for all heads and their phis */ + headnode = get_copy(loophead); + for_each_copy(headnode) { + NEW_ARR_A(ir_node *, get_node_info(headnode)->ins, unroll_arity); + for_each_phi(headnode, phi) { + NEW_ARR_A(ir_node *, get_node_info(phi)->ins, unroll_arity); + } + } - cur_loop_outs = NEW_ARR_F(out_edges, 0); + /* Append the copies to the existing loop. */ + for (i = 0; i < headarity; i++) { + ir_node *upper_head = loophead; + ir_node *lower_head = get_copy(loophead); - /* Find loop entries walk, find head */ - inc_irg_visited( current_ir_graph ); - irg_walk_graph( current_ir_graph, get_loop_outs_and_info, NULL, NULL ); + ir_node *upper_pred = get_irn_n(loophead, i); + ir_node *lower_pred = get_copy(get_irn_n(loophead, i)); - /* RETURN if there is no valid head */ - if (!loop_cf_head || !loop_cf_head_valid) { - DB((dbg, LEVEL_1, "No valid loop head. Nothing done.\n")); - return; + ir_node *last_pred; + + /** + * Build unrolled loop top down + */ + if (is_backedge(loophead, i) && !is_alien_edge(loophead, i)) { + for_each_copy2(upper_head, lower_head, upper_pred, lower_pred) { + get_node_info(lower_head)->ins[uhead_in_n] = upper_pred; + + for_each_phi(upper_head, phi) { + ir_node *phi_copy = get_copy(phi); + get_node_info(phi_copy)->ins[uhead_in_n] = get_irn_n(phi, i); + } + } + + last_pred = upper_pred; + ++uhead_in_n; + + /* Fix the topmost loop heads backedges. */ + set_irn_n(loophead, i, last_pred); + for_each_phi(loophead, phi) { + ir_node *last_phi = get_last_copy(phi); + ir_node *pred = get_irn_n(last_phi, i); + set_irn_n(phi, i, pred); + } + } } + + headnode = get_copy(loophead); + for_each_copy(headnode) { + set_irn_in(headnode, unroll_arity, get_node_info(headnode)->ins); + for_each_phi(headnode, phi) { + set_irn_in(phi, unroll_arity, get_node_info(phi)->ins); + } + } +} + #if 0 - /* RETURN if there is a call in the loop */ - if (loop_info.calls) - return; +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; - /* Loop complexity too high */ - if (loop_info.opnodes_n > max_loop_opnodes) - return; + /* 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;*/ -// foreach_out_edge(loop_cf_head, edge) { -// ir_node *node = get_edge_src_irn(edge); -// if ( !is_Block(node) && !is_Proj(node) && !is_Phi(node) ) -// ++loop_info.opnodes_head; -// } + phi = new_r_Phi(block, n_cfgpreds, in, mode); - inc_irg_visited(current_ir_graph); - loop_walker( loop_outs, NULL, get_invariants, NULL ); + assert(phi && "phi null"); + assert(is_Bad(phi) && "phi bad"); - /* This could be improved with knowledge about variable range. */ - if (loop_info.stores == 0 && loop_info.invariant_loads > 0) - do_peel = 1; + /* 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); -#else - (void) get_invariants; + set_irn_n(node, phi_pos, phi); + return phi; +} #endif - do_peel = 0; - do_inversion = 1; - /* Loop peeling */ - if (do_peel) { - peel(cur_loop_outs); - reset_node_infos(); - } +/** + * Loop unrolling + * Could be improved with variable range informations. + */ +void loop_unrolling(void) +{ + int i, j; - DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-peeled1")); + unroll_times = 8; - DEL_ARR_F(cur_loop_outs); + cur_loop_outs = NEW_ARR_F(out_edge, 0); + irg_walk_graph( current_ir_graph, get_loop_outs, NULL, NULL ); - /* Loop inversion */ - /* Search for condition chains. We may not do this before peeling, as peeling changes things. */ - ir_reserve_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); - irg_walk_graph(current_ir_graph, unmark_block, NULL, NULL); + ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); - loop_info.blocks = get_loop_n_blocks(cur_loop); - cond_chain_entries = NEW_ARR_F(out_edges, 0); - head_inversion_node_count = 0; - head_inversion_block_count = 0; + /* duplicate whole loop content */ inc_irg_visited(current_ir_graph); - set_Block_mark(loop_cf_head, 1); - mark_irn_visited(loop_cf_head); - /* find condition chains */ - condition_chains(loop_cf_head); - DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-pre_inversion")); + 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); - // TODO assume number of phis to be created. prevent inversion in case ... + if (!is_Block(node)) { - /* Loop inversion */ - /* We catch endless loops here too, - * because they do not have a condition chain and a maximum of 1 block. */ - if (loop_info.blocks < 2) { - do_inversion = 0; - DB((dbg, LEVEL_1, "Loop contains %d (less than 2) blocks => No Inversion done.\n", loop_info.blocks)); + for (j = 0; j < unroll_times-1; ++j) { + copy_walk(pred, is_in_loop, cur_loop); + + pred = get_copy(pred); + } + } } - if (head_inversion_block_count < 1) { - do_inversion = 0; - DB((dbg, LEVEL_1, "Loop contains %d (less than 1) invertible blocks => No Inversion done.\n", head_inversion_block_count)); + 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) { + copy_walk(pred, is_in_loop, cur_loop); + duplicate_preds(node, entry.pred_irn_n, get_copy(pred)); + + pred = get_copy(pred); + } + } } + ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED); - if (do_inversion) { - cur_head_outs = NEW_ARR_F(out_edges, 0); + /* Line up the floating copies. */ + unrolling_fix_cf(); - /* get all edges pointing into the head or condition chain */ - irg_walk_graph(current_ir_graph, get_head_entries, NULL, NULL); - loop_inversion_walk(cur_head_outs); + /* Generate phis for all loop outs */ + 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); - DEL_ARR_F(cur_head_outs); + if (!is_Block(node) && !is_End(node)) { + DB((dbg, LEVEL_1, " construct_ssa_n def %ld node %ld pos %d\n", + get_irn_node_nr(pred), get_irn_node_nr(node), entry.pred_irn_n)); + construct_ssa_n(pred, node); + } } - DEBUG_ONLY(dump_ir_block_graph(current_ir_graph, "-inversed2")); + DEL_ARR_F(cur_loop_outs); - /* FREE */ - DEL_ARR_F(cond_chain_entries); - ir_free_resources(current_ir_graph, IR_RESOURCE_BLOCK_MARK); + set_irg_doms_inconsistent(current_ir_graph); + set_irg_loopinfo_inconsistent(current_ir_graph); + set_irg_outs_inconsistent(current_ir_graph); } -/* */ -static void analyze_loop(ir_loop *loop) +/* Initialization and */ +static void init_analyze(ir_loop *loop) { /* Init new for every loop */ cur_loop = loop; @@ -1260,60 +1377,92 @@ static void analyze_loop(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; - DB((dbg, LEVEL_1, " >>>> current loop includes node %ld <<<\n", get_irn_node_nr(get_loop_node(loop, 0)))); + DB((dbg, LEVEL_2, " >>>> current loop includes node %ld <<<\n", get_irn_node_nr(get_loop_node(loop, 0)))); + + 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) { + DB((dbg, LEVEL_2, "No valid loop head. Nothing done.\n")); + return; + } + + if (enable_peeling) + loop_peeling(); + + if (enable_inversion) + loop_inversion(); + if (enable_unrolling) + loop_unrolling(); - decision_maker(); +#if 0 + /* RETURN if there is a call in the loop */ + if (loop_info.calls) + return; +#endif - DB((dbg, LEVEL_1, " <<<< 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 %ld >>>>\n", get_irn_node_nr(get_loop_node(loop, 0)))); } /* Find most inner loops and send them to analyze_loop */ -static void analyze_inner_loop(ir_loop *loop) +static void find_most_inner_loop(ir_loop *loop) { /* descend into sons */ int sons = get_loop_n_sons(loop); - if (sons==0) { - analyze_loop(loop); + if (sons == 0) { + loop_element elem; + int el_n, i; + + el_n = get_loop_n_elements(loop); + + for (i=0; i < el_n; ++i) { + elem = get_loop_element(loop, i); + /* We can only rely on the blocks, + * as the loop attribute of the nodes seems not to be set. */ + if (is_ir_node(elem.kind) && is_Block(elem.node)) { + ARR_APP1(ir_node *, loops, elem.node); + DB((dbg, LEVEL_5, "Found most inner loop (contains block %+F)\n", elem.node)); + break; + } + } } else { int s; for(s=0; s>> loop optimization (Startnode %ld) <<<\n", get_irn_node_nr(get_irg_start(irg)))); + int i, sons, nr; /* Init */ link_node_state_list = NULL; + set_current_ir_graph(irg); /* preconditions */ edges_assure(irg); + assure_irg_outs(irg); + + /* NOTE: sets only the loop attribute of blocks, not nodes */ + /* NOTE: Kills links */ + assure_cf_loop(irg); + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST); collect_phiprojs(irg); ir_free_resources(irg, IR_RESOURCE_IRN_LINK); - set_current_ir_graph(irg); - assure_cf_loop(irg); - /* allocate node_info for additional information on nodes */ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK); irg_walk_graph(current_ir_graph, alloc_node_info, NULL, NULL); @@ -1321,27 +1470,115 @@ void loop_optimization(ir_graph *irg) loop = get_irg_loop(irg); sons = get_loop_n_sons(loop); - for (nr=0; nr>> loop optimization done (Startnode %ld) <<<\n", get_irn_node_nr(get_irg_start(irg)))); +void do_loop_unrolling(ir_graph *irg) +{ + enable_unrolling = 1; + enable_peeling = 0; + enable_inversion = 0; + + DB((dbg, LEVEL_2, " >>> unrolling (Startnode %ld) <<<\n", + get_irn_node_nr(get_irg_start(irg)))); + + loop_optimization(irg); + + DB((dbg, LEVEL_2, " >>> unrolling done (Startnode %ld) <<<\n", + get_irn_node_nr(get_irg_start(irg)))); } void do_loop_inversion(ir_graph *irg) { - /* TODO: add the code here that performs loop inversion only */ + enable_unrolling = 0; + enable_peeling = 0; + enable_inversion = 1; + + DB((dbg, LEVEL_2, " >>> inversion (Startnode %ld) <<<\n", + get_irn_node_nr(get_irg_start(irg)))); + loop_optimization(irg); + + DB((dbg, LEVEL_2, " >>> inversion done (Startnode %ld) <<<\n", + get_irn_node_nr(get_irg_start(irg)))); } void do_loop_peeling(ir_graph *irg) { - /* TODO: add the code here that performs loop peeling only */ + enable_unrolling = 0; + enable_peeling = 1; + enable_inversion = 0; + + DB((dbg, LEVEL_2, " >>> peeling (Startnode %ld) <<<\n", + get_irn_node_nr(get_irg_start(irg)))); + loop_optimization(irg); + + DB((dbg, LEVEL_2, " >>> peeling done (Startnode %ld) <<<\n", + get_irn_node_nr(get_irg_start(irg)))); + } void firm_init_loop_opt(void)