X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady.c;h=815e0d6c6aea7d676769c0aab96c839c88849b3f;hb=1894b7dd99b524c25c8fa18c33c250ea2cde2e36;hp=407a1ac2b2e830e398deb7b0adc975438ede0c6d;hpb=9b761905834e9e389f21349d6e4bb1344d6b5654;p=libfirm diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index 407a1ac2b..815e0d6c6 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -44,7 +44,6 @@ #include "beutil.h" #include "bearch_t.h" -#include "bespillbelady.h" #include "beuses.h" #include "besched_t.h" #include "beirgmod.h" @@ -54,6 +53,7 @@ #include "bespilloptions.h" #include "beloopana.h" #include "beirg_t.h" +#include "bespill.h" #include "bemodule.h" #define DBG_SPILL 1 @@ -66,6 +66,10 @@ #define DBG_WORKSET 128 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) +/* factor to weight the different costs of reloading/rematerializing a node + (see bespill.h be_get_reload_costs_no_weight) */ +#define RELOAD_COST_FACTOR 10 + typedef enum { value_not_reloaded, /* the value has not been reloaded */ value_partially_reloaded, /* the value has been reloaded on some paths */ @@ -271,6 +275,7 @@ static INLINE unsigned get_distance(ir_node *from, unsigned from_step, { be_next_use_t use; int flags = arch_irn_get_flags(arch_env, def); + unsigned costs; unsigned time; assert(! (flags & arch_irn_flags_ignore)); @@ -283,10 +288,11 @@ static INLINE unsigned get_distance(ir_node *from, unsigned from_step, if(flags & arch_irn_flags_dont_spill) return 0; - time = use.time; - time += be_get_reload_costs_no_weight(senv, def, use.before) * 10; + costs = be_get_reload_costs_no_weight(senv, def, use.before); + assert(costs * RELOAD_COST_FACTOR < 1000); + time = use.time + 1000 - (costs * RELOAD_COST_FACTOR); - return use.time; + return time; } /** @@ -300,14 +306,15 @@ static INLINE unsigned get_distance(ir_node *from, unsigned from_step, */ static void displace(workset_t *new_vals, int is_usage) { - ir_node *val; - int i, len, max_allowed, demand, iter; - - ir_node **to_insert = alloca(n_regs * sizeof(to_insert[0])); - - /* - 1. Identify the number of needed slots and the values to reload - */ + ir_node **to_insert = alloca(n_regs * sizeof(to_insert[0])); + ir_node *val; + int i; + int len; + int spills_needed; + int demand; + int iter; + + /* 1. Identify the number of needed slots and the values to reload */ demand = 0; workset_foreach(new_vals, val, iter) { /* mark value as used */ @@ -315,31 +322,35 @@ static void displace(workset_t *new_vals, int is_usage) ir_nodeset_insert(&used, val); if (! workset_contains(ws, val)) { - DBG((dbg, DBG_DECIDE, " insert %+F\n", val)); - to_insert[demand++] = val; + DB((dbg, DBG_DECIDE, " insert %+F\n", val)); if (is_usage) { - DBG((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, instr)); + DB((dbg, DBG_SPILL, "Reload %+F before %+F\n", val, instr)); be_add_reload(senv, val, instr, cls, 1); } } else { - DBG((dbg, DBG_DECIDE, " %+F already in workset\n", val)); + DB((dbg, DBG_DECIDE, " %+F already in workset\n", val)); assert(is_usage); + /* remove the value from the current workset so it is not accidently + * spilled */ + workset_remove(ws, val); } + to_insert[demand++] = val; } - /* - 2. Make room for at least 'demand' slots - */ - len = workset_get_length(ws); - max_allowed = n_regs - demand; + /* 2. Make room for at least 'demand' slots */ + len = workset_get_length(ws); + spills_needed = len + demand - n_regs; + assert(spills_needed <= len); /* Only make more free room if we do not have enough */ - if (len > max_allowed) { - DBG((dbg, DBG_DECIDE, " disposing %d values\n", - ws->len - max_allowed)); + if (spills_needed > 0) { + ir_node *curr_bb = get_nodes_block(instr); + workset_t *ws_start = get_block_info(curr_bb)->start_workset; + + DB((dbg, DBG_DECIDE, " disposing %d values\n", spills_needed)); - /* get current next-use distance */ - for (i = 0; i < ws->len; ++i) { + /* calculate current next-use distance for live values */ + for (i = 0; i < len; ++i) { ir_node *val = workset_get_val(ws, i); unsigned dist = get_distance(instr, instr_nr, val, !is_usage); workset_set_time(ws, i, dist); @@ -348,43 +359,36 @@ static void displace(workset_t *new_vals, int is_usage) /* sort entries by increasing nextuse-distance*/ workset_sort(ws); - /* - Logic for not needed live-ins: If a value is disposed - before its first usage, remove it from start workset - We don't do this for phis though - */ - for (i = max_allowed; i < ws->len; ++i) { - ir_node *node = ws->vals[i].node; + /* Logic for not needed live-ins: If a value is disposed + * before its first usage, remove it from start workset + * We don't do this for phis though */ + for (i = len - spills_needed; i < len; ++i) { + ir_node *val = ws->vals[i].node; - DBG((dbg, DBG_DECIDE, " disposing node %+F (%u)\n", node, + DB((dbg, DBG_DECIDE, " disposing node %+F (%u)\n", val, workset_get_time(ws, i))); if(!USES_IS_INFINITE(ws->vals[i].time) && !ws->vals[i].reloaded) { - //be_add_spill(senv, node, instr); + //be_add_spill(senv, val, instr); } - if (is_Phi(node)) - continue; - - if (! ir_nodeset_contains(&used, node)) { - ir_node *curr_bb = get_nodes_block(instr); - workset_t *ws_start = get_block_info(curr_bb)->start_workset; - workset_remove(ws_start, node); - - DBG((dbg, DBG_DECIDE, " (and removing %+F from start workset)\n", node)); + if (!is_Phi(val) && ! ir_nodeset_contains(&used, val)) { + workset_remove(ws_start, val); + DB((dbg, DBG_DECIDE, " (and removing %+F from start workset)\n", val)); } } /* kill the last 'demand' entries in the array */ - workset_set_length(ws, max_allowed); + workset_set_length(ws, len - spills_needed); } - /* - 3. Insert the new values into the workset - */ - for (i = 0; i < demand; ++i) - workset_insert(ws, to_insert[i], 1); + /* 3. Insert the new values into the workset */ + for (i = 0; i < demand; ++i) { + ir_node *val = to_insert[i]; + + workset_insert(ws, val, 1); + } } /** Decides whether a specific node should be in the start workset or not @@ -413,7 +417,7 @@ static loc_t to_take_or_not_to_take(ir_node* first, ir_node *node, /* We have to keep nonspillable nodes in the workingset */ if(arch_irn_get_flags(arch_env, node) & arch_irn_flags_dont_spill) { loc.time = 0; - DBG((dbg, DBG_START, " %+F taken (dontspill node)\n", node, loc.time)); + DB((dbg, DBG_START, " %+F taken (dontspill node)\n", node, loc.time)); return loc; } @@ -422,7 +426,7 @@ static loc_t to_take_or_not_to_take(ir_node* first, ir_node *node, // the nodes marked as live in shouldn't be dead, so it must be a phi assert(is_Phi(node)); loc.time = USES_INFINITY; - DBG((dbg, DBG_START, " %+F not taken (dead)\n", node)); + DB((dbg, DBG_START, " %+F not taken (dead)\n", node)); if(is_Phi(node)) { be_spill_phi(senv, node); } @@ -432,10 +436,12 @@ static loc_t to_take_or_not_to_take(ir_node* first, ir_node *node, loc.time = next_use.time; if(next_use.outermost_loop >= get_loop_depth(loop)) { - DBG((dbg, DBG_START, " %+F taken (%u, loop %d)\n", node, loc.time, next_use.outermost_loop)); + DB((dbg, DBG_START, " %+F taken (%u, loop %d)\n", node, loc.time, + next_use.outermost_loop)); } else { loc.time = USES_PENDING; - DBG((dbg, DBG_START, " %+F delayed (outerloopdepth %d < loopdetph %d)\n", node, next_use.outermost_loop, get_loop_depth(loop))); + DB((dbg, DBG_START, " %+F delayed (outerdepth %d < loopdepth %d)\n", + node, next_use.outermost_loop, get_loop_depth(loop))); } return loc; } @@ -465,7 +471,7 @@ static void compute_live_ins(const ir_node *block) starters = NEW_ARR_F(loc_t, 0); delayed = NEW_ARR_F(loc_t, 0); - DBG((dbg, DBG_START, "Living at start of %+F:\n", block)); + DB((dbg, DBG_START, "Living at start of %+F:\n", block)); first = sched_first(block); /* check all Phis first */ @@ -506,13 +512,36 @@ static void compute_live_ins(const ir_node *block) /* so far we only put nodes into the starters list that are used inside * the loop. If register pressure in the loop is low then we can take some * values and let them live through the loop */ - if(free_slots > 0) { + if (free_slots > 0) { qsort(delayed, ARR_LEN(delayed), sizeof(delayed[0]), loc_compare); for (i = 0; i < ARR_LEN(delayed) && i < free_slots; ++i) { - DBG((dbg, DBG_START, " delayed %+F taken\n", delayed[i].node)); - ARR_APP1(loc_t, starters, delayed[i]); - delayed[i].node = NULL; + int p, arity; + loc_t *loc = & delayed[i]; + + /* don't use values which are dead in a known predecessors + * to not induce unnecessary reloads */ + arity = get_irn_arity(block); + for (p = 0; p < arity; ++p) { + ir_node *pred_block = get_Block_cfgpred_block(block, p); + block_info_t *pred_info = get_block_info(pred_block); + + if (pred_info == NULL) + continue; + + if (!workset_contains(pred_info->end_workset, loc->node)) { + DB((dbg, DBG_START, + " delayed %+F not live at pred %+F\n", loc->node, + pred_block)); + goto skip_delayed; + } + } + + DB((dbg, DBG_START, " delayed %+F taken\n", loc->node)); + ARR_APP1(loc_t, starters, *loc); + loc->node = NULL; + skip_delayed: + ; } } @@ -523,7 +552,7 @@ static void compute_live_ins(const ir_node *block) if(node == NULL || !is_Phi(node) || get_nodes_block(node) != block) continue; - DBG((dbg, DBG_START, " spilling delayed phi %+F\n", node)); + DB((dbg, DBG_START, " spilling delayed phi %+F\n", node)); be_spill_phi(senv, node); } DEL_ARR_F(delayed); @@ -544,7 +573,7 @@ static void compute_live_ins(const ir_node *block) if (! is_Phi(node) || get_nodes_block(node) != block) continue; - DBG((dbg, DBG_START, " spilling phi %+F\n", node)); + DB((dbg, DBG_START, " spilling phi %+F\n", node)); be_spill_phi(senv, node); } @@ -659,22 +688,22 @@ static void belady(ir_node *block) compute_live_ins(block); } - DBG((dbg, DBG_DECIDE, "\n")); - DBG((dbg, DBG_DECIDE, "Decide for %+F\n", block)); + DB((dbg, DBG_DECIDE, "\n")); + DB((dbg, DBG_DECIDE, "Decide for %+F\n", block)); block_info = new_block_info(); set_block_info(block, block_info); - DBG((dbg, DBG_WSETS, "Start workset for %+F:\n", block)); + DB((dbg, DBG_WSETS, "Start workset for %+F:\n", block)); workset_foreach(ws, irn, iter) { - DBG((dbg, DBG_WSETS, " %+F (%u)\n", irn, + DB((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(ws, iter))); } block_info->start_workset = workset_clone(ws); /* process the block from start to end */ - DBG((dbg, DBG_WSETS, "Processing...\n")); + DB((dbg, DBG_WSETS, "Processing...\n")); ir_nodeset_init(&used); instr_nr = 0; /* TODO: this leaks (into the obstack)... */ @@ -688,7 +717,7 @@ static void belady(ir_node *block) if (is_Phi(irn)) { continue; } - DBG((dbg, DBG_DECIDE, " ...%+F\n", irn)); + DB((dbg, DBG_DECIDE, " ...%+F\n", irn)); /* set instruction in the workset */ instr = irn; @@ -729,9 +758,9 @@ static void belady(ir_node *block) /* Remember end-workset for this block */ block_info->end_workset = workset_clone(ws); - DBG((dbg, DBG_WSETS, "End workset for %+F:\n", block)); + DB((dbg, DBG_WSETS, "End workset for %+F:\n", block)); workset_foreach(ws, irn, iter) - DBG((dbg, DBG_WSETS, " %+F (%u)\n", irn, + DB((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(ws, iter))); /* add successor blocks into worklist */ @@ -754,8 +783,8 @@ static void fix_block_borders(ir_node *block, void *data) int iter; (void) data; - DBG((dbg, DBG_FIX, "\n")); - DBG((dbg, DBG_FIX, "Fixing %+F\n", block)); + DB((dbg, DBG_FIX, "\n")); + DB((dbg, DBG_FIX, "Fixing %+F\n", block)); start_workset = get_block_info(block)->start_workset; @@ -766,7 +795,7 @@ static void fix_block_borders(ir_node *block, void *data) workset_t *pred_end_workset = get_block_info(pred)->end_workset; ir_node *node; - DBG((dbg, DBG_FIX, " Pred %+F\n", pred)); + DB((dbg, DBG_FIX, " Pred %+F\n", pred)); /* spill all values not used anymore */ workset_foreach(pred_end_workset, node, iter) { @@ -789,7 +818,7 @@ static void fix_block_borders(ir_node *block, void *data) && !pred_end_workset->vals[iter].reloaded) { ir_node *insert_point = be_get_end_of_block_insertion_point(pred); - DBG((dbg, DBG_SPILL, "Spill %+F before %+F\n", node, + DB((dbg, DBG_SPILL, "Spill %+F before %+F\n", node, insert_point)); be_add_spill(senv, node, insert_point); } @@ -813,8 +842,8 @@ static void fix_block_borders(ir_node *block, void *data) continue; /* node is not in memory at the end of pred -> reload it */ - DBG((dbg, DBG_FIX, " reload %+F\n", node)); - DBG((dbg, DBG_SPILL, "Reload %+F before %+F,%d\n", node, block, i)); + DB((dbg, DBG_FIX, " reload %+F\n", node)); + DB((dbg, DBG_SPILL, "Reload %+F before %+F,%d\n", node, block, i)); be_add_reload_on_edge(senv, node, block, i, cls, 1); } }