X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeschednormal.c;h=46aa21b19b00d2352e104f441bbf300b46d6a4a0;hb=4265d3c97c543f9c5d159d62117fb5de65a66df8;hp=bf6d1b81ee56224bafd413fc96f480f0954820fa;hpb=d42e276de068131fbc80a561ebf562540e7cbebc;p=libfirm diff --git a/ir/be/beschednormal.c b/ir/be/beschednormal.c index bf6d1b81e..46aa21b19 100644 --- a/ir/be/beschednormal.c +++ b/ir/be/beschednormal.c @@ -26,20 +26,26 @@ #include -#include "besched_t.h" +#include "besched.h" #include "belistsched.h" #include "belive_t.h" #include "beutil.h" #include "height.h" #include "irtools.h" #include "irgwalk.h" -#include "benode_t.h" +#include "benode.h" #include "array_t.h" // XXX there is no one time init for schedulers //#define NORMAL_DBG #include "irprintf.h" +/** An instance of the normal scheduler. */ +typedef struct instance_t { + ir_graph* irg; /**< the IR graph of this instance */ + struct obstack obst; /**< obstack for temporary data */ + ir_node* curr_list; /**< current block schedule list */ +} instance_t; static int must_be_scheduled(const ir_node* const irn) { @@ -50,31 +56,30 @@ static int must_be_scheduled(const ir_node* const irn) static ir_node *normal_select(void *block_env, ir_nodeset_t *ready_set, ir_nodeset_t *live_set) { + instance_t* inst = block_env; + ir_node* irn; + ir_node* next; + ir_node* last = NULL; ir_nodeset_iterator_t iter; - ir_node* block; - ir_node* irn; - ir_node** sched; - int sched_count; - (void)block_env; (void)live_set; - ir_nodeset_iterator_init(&iter, ready_set); - irn = ir_nodeset_iterator_next(&iter); - block = get_nodes_block(irn); - sched = get_irn_link(block); - sched_count = ARR_LEN(sched); - for (; sched_count-- != 0; ++sched) { - ir_node* irn = *sched; - if (ir_nodeset_contains(ready_set, irn) && - !arch_irn_class_is(irn, branch)) { + for (irn = inst->curr_list; irn != NULL; last = irn, irn = next) { + next = get_irn_link(irn); + if (ir_nodeset_contains(ready_set, irn)) { #if defined NORMAL_DBG ir_fprintf(stderr, "scheduling %+F\n", irn); #endif + if (last == NULL) + inst->curr_list = next; + else + set_irn_link(last, next); return irn; } } + ir_nodeset_iterator_init(&iter, ready_set); + irn = ir_nodeset_iterator_next(&iter); return irn; } @@ -124,7 +129,7 @@ static int count_result(const ir_node* irn) /* TODO high cost for store trees */ -static int normal_tree_cost(ir_node* irn) +static int normal_tree_cost(ir_node* irn, instance_t *inst) { flag_and_cost* fc; int arity; @@ -138,7 +143,7 @@ static int normal_tree_cost(ir_node* irn) return 0; if (is_Proj(irn)) { - return normal_tree_cost(get_Proj_pred(irn)); + return normal_tree_cost(get_Proj_pred(irn), inst); } arity = get_irn_arity(irn); @@ -149,7 +154,7 @@ static int normal_tree_cost(ir_node* irn) int i; ir_node* block = get_nodes_block(irn); - fc = xmalloc(sizeof(*fc) + sizeof(*fc->costs) * arity); + fc = OALLOCF(&inst->obst, flag_and_cost, costs, arity); fc->no_root = 0; costs = fc->costs; @@ -165,7 +170,7 @@ static int normal_tree_cost(ir_node* irn) flag_and_cost* pred_fc; ir_node* real_pred; - cost = normal_tree_cost(pred); + cost = normal_tree_cost(pred, inst); if (be_is_Barrier(pred)) cost = 1; // XXX hack: the barrier causes all users to have a reguse of #regs if (!arch_irn_is_ignore(pred)) { real_pred = (is_Proj(pred) ? get_Proj_pred(pred) : pred); @@ -209,14 +214,14 @@ static int normal_tree_cost(ir_node* irn) static void normal_cost_walker(ir_node* irn, void* env) { - (void)env; + instance_t *inst = env; #if defined NORMAL_DBG ir_fprintf(stderr, "cost walking node %+F\n", irn); #endif if (is_Block(irn)) return; if (!must_be_scheduled(irn)) return; - normal_tree_cost(irn); + normal_tree_cost(irn, inst); } @@ -298,8 +303,8 @@ static int root_cmp(const void* a, const void* b) static void normal_sched_block(ir_node* block, void* env) { + ir_node** roots = get_irn_link(block); heights_t* heights = env; - ir_node** roots = get_irn_link(block); int root_count; irn_cost_pair* root_costs; int i; @@ -366,37 +371,65 @@ static void normal_sched_block(ir_node* block, void* env) static void *normal_init_graph(const list_sched_selector_t *vtab, const be_irg_t *birg) { - ir_graph *irg = be_get_birg_irg(birg); - heights_t *heights; + instance_t* inst = XMALLOC(instance_t); + ir_graph* irg = be_get_birg_irg(birg); + heights_t* heights; (void)vtab; be_clear_links(irg); + obstack_init(&inst->obst); + inst->irg = irg; + heights = heights_new(irg); ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK); - irg_walk_graph(irg, normal_cost_walker, NULL, NULL); + irg_walk_graph(irg, normal_cost_walker, NULL, inst); irg_walk_graph(irg, collect_roots, NULL, NULL); inc_irg_visited(irg); ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED); irg_block_walk_graph(irg, normal_sched_block, NULL, heights); - ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED); + ir_free_resources(irg, IR_RESOURCE_IRN_VISITED); heights_free(heights); - return NULL; + return inst; } - static void *normal_init_block(void *graph_env, ir_node *block) { - (void)graph_env; - (void)block; - - return NULL; + instance_t* inst = graph_env; + ir_node** sched = get_irn_link(block); + ir_node* first = NULL; + int i; + + /* turn into a list, so we can easily remove nodes. + The link field is used anyway. */ + for (i = ARR_LEN(sched) - 1; i >= 0; --i) { + ir_node* irn = sched[i]; + if (!is_cfop(irn)) { + set_irn_link(irn, first); + first = irn; + } + } + /* note: we can free sched here, there should be no attempt to schedule + a block twice */ + DEL_ARR_F(sched); + set_irn_link(block, sched); + inst->curr_list = first; + return inst; } +void normal_finish_graph(void *env) +{ + instance_t *inst = env; + + /* block uses the link field to store the schedule */ + ir_free_resources(inst->irg, IR_RESOURCE_IRN_LINK); + obstack_free(&inst->obst, NULL); + xfree(inst); +} const list_sched_selector_t normal_selector = { normal_init_graph, @@ -408,5 +441,5 @@ const list_sched_selector_t normal_selector = { NULL, /* exectime */ NULL, /* latency */ NULL, /* finish_block */ - NULL /* finish_graph */ + normal_finish_graph };