X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady.c;h=f205aa5fb807130937cbc94f8dcf177572e93fbf;hb=30369d28b8fabe4f66cee12f42ee475d9444cf9e;hp=1b24892299243595e00994c33b9531066c4da306;hpb=6c3146b96bc65d9de18f3f2b59faf33b8b9935d6;p=libfirm diff --git a/ir/be/bespillbelady.c b/ir/be/bespillbelady.c index 1b2489229..f205aa5fb 100644 --- a/ir/be/bespillbelady.c +++ b/ir/be/bespillbelady.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -22,7 +22,6 @@ * @brief Beladys spillalgorithm. * @author Daniel Grund, Matthias Braun * @date 20.09.2005 - * @version $Id$ */ #include "config.h" @@ -39,6 +38,8 @@ #include "ircons_t.h" #include "irprintf.h" #include "irnodeset.h" +#include "irtools.h" +#include "util.h" #include "beutil.h" #include "bearch.h" @@ -77,7 +78,7 @@ typedef struct loc_t { typedef struct workset_t { unsigned len; /**< current length */ - loc_t vals[0]; /**< array of the values/distances in this working set */ + loc_t vals[]; /**< array of the values/distances in this working set */ } workset_t; static struct obstack obst; @@ -89,8 +90,6 @@ static workset_t *ws; /**< the main workset used while processing a block. */ static be_uses_t *uses; /**< env for the next-use magic */ static ir_node *instr; /**< current instruction */ -static unsigned instr_nr; /**< current instruction number - (relative to block start) */ static spill_env_t *senv; /**< see bespill.h */ static ir_node **blocklist; @@ -213,9 +212,17 @@ static const loc_t *workset_contains(const workset_t *ws, const ir_node *val) static int loc_compare(const void *a, const void *b) { - const loc_t *p = a; - const loc_t *q = b; - return p->time - q->time; + const loc_t *p = ((const loc_t*) a); + const loc_t *q = ((const loc_t*) b); + const unsigned pt = p->time; + const unsigned qt = q->time; + + if (pt < qt) + return -1; + if (pt > qt) + return 1; + + return get_irn_node_nr(p->node) - get_irn_node_nr(q->node); } static void workset_sort(workset_t *workset) @@ -270,7 +277,7 @@ static block_info_t *new_block_info(void) static inline block_info_t *get_block_info(const ir_node *block) { - return get_irn_link(block); + return (block_info_t*)get_irn_link(block); } static inline void set_block_info(ir_node *block, block_info_t *info) @@ -281,8 +288,7 @@ static inline void set_block_info(ir_node *block, block_info_t *info) /** * @return The distance to the next use or 0 if irn has dont_spill flag set */ -static unsigned get_distance(ir_node *from, unsigned from_step, - const ir_node *def, int skip_from_uses) +static unsigned get_distance(ir_node *from, const ir_node *def, int skip_from_uses) { be_next_use_t use; unsigned costs; @@ -290,13 +296,13 @@ static unsigned get_distance(ir_node *from, unsigned from_step, assert(!arch_irn_is_ignore(def)); - use = be_get_next_use(uses, from, from_step, def, skip_from_uses); + use = be_get_next_use(uses, from, def, skip_from_uses); time = use.time; if (USES_IS_INFINITE(time)) return USES_INFINITY; /* We have to keep nonspillable nodes in the workingset */ - if (arch_irn_get_flags(skip_Proj_const(def)) & arch_irn_flags_dont_spill) + if (arch_get_irn_flags(skip_Proj_const(def)) & arch_irn_flags_dont_spill) return 0; /* give some bonus to rematerialisable nodes */ @@ -365,7 +371,7 @@ static void displace(workset_t *new_vals, int is_usage) /* 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); + unsigned dist = get_distance(instr, val, !is_usage); workset_set_time(ws, i, dist); } @@ -482,13 +488,13 @@ 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(skip_Proj_const(node)) & arch_irn_flags_dont_spill) { + if (arch_get_irn_flags(skip_Proj_const(node)) & arch_irn_flags_dont_spill) { loc.time = 0; DB((dbg, DBG_START, " %+F taken (dontspill node)\n", node, loc.time)); return loc; } - next_use = be_get_next_use(uses, first, 0, node, 0); + next_use = be_get_next_use(uses, first, node, 0); if (USES_IS_INFINITE(next_use.time)) { /* the nodes marked as live in shouldn't be dead, so it must be a phi */ assert(is_Phi(node)); @@ -534,13 +540,11 @@ static void decide_start_workset(const ir_node *block) { ir_loop *loop = get_irn_loop(block); ir_node *first; - ir_node *node; loc_t loc; loc_t *starters; loc_t *delayed; unsigned len; unsigned i; - int in; unsigned ws_count; int free_slots, free_pressure_slots; unsigned pressure; @@ -552,7 +556,7 @@ static void decide_start_workset(const ir_node *block) arity = get_irn_arity(block); pred_worksets = ALLOCAN(workset_t*, arity); all_preds_known = true; - for (in = 0; in < arity; ++in) { + for (int in = 0; in < arity; ++in) { ir_node *pred_block = get_Block_cfgpred_block(block, in); block_info_t *pred_info = get_block_info(pred_block); @@ -599,8 +603,7 @@ static void decide_start_workset(const ir_node *block) } /* check all Live-Ins */ - be_lv_foreach(lv, block, be_lv_state_in, in) { - ir_node *node = be_lv_get_irn(lv, block, in); + be_lv_foreach(lv, block, be_lv_state_in, node) { unsigned available; if (all_preds_known) { @@ -620,7 +623,7 @@ static void decide_start_workset(const ir_node *block) } pressure = be_get_loop_pressure(loop_ana, cls, loop); - assert(ARR_LEN(delayed) <= (signed)pressure); + assert(ARR_LEN(delayed) <= pressure); free_slots = n_regs - ARR_LEN(starters); free_pressure_slots = n_regs - (pressure - ARR_LEN(delayed)); free_slots = MIN(free_slots, free_pressure_slots); @@ -631,7 +634,8 @@ static void decide_start_workset(const ir_node *block) DB((dbg, DBG_START, "Loop pressure %d, taking %d delayed vals\n", pressure, free_slots)); if (free_slots > 0) { - int i; + size_t i; + qsort(delayed, ARR_LEN(delayed), sizeof(delayed[0]), loc_compare); for (i = 0; i < ARR_LEN(delayed) && free_slots > 0; ++i) { @@ -754,7 +758,6 @@ static void decide_start_workset(const ir_node *block) static void process_block(ir_node *block) { workset_t *new_vals; - ir_node *irn; unsigned iter; block_info_t *block_info; int arity; @@ -768,7 +771,7 @@ static void process_block(ir_node *block) /* no predecessor -> empty set */ workset_clear(ws); } else if (arity == 1) { - /* one predecessor, copy it's end workset */ + /* one predecessor, copy its end workset */ ir_node *pred_block = get_Block_cfgpred_block(block, 0); block_info_t *pred_info = get_block_info(pred_block); @@ -786,16 +789,17 @@ static void process_block(ir_node *block) set_block_info(block, block_info); DB((dbg, DBG_WSETS, "Start workset for %+F:\n", block)); - workset_foreach(ws, irn, iter) { - DB((dbg, DBG_WSETS, " %+F (%u)\n", irn, - workset_get_time(ws, iter))); + { + ir_node *irn; + workset_foreach(ws, irn, iter) { + 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 */ DB((dbg, DBG_WSETS, "Processing...\n")); - instr_nr = 0; /* TODO: this leaks (into the obstack)... */ new_vals = new_workset(); @@ -832,15 +836,16 @@ static void process_block(ir_node *block) workset_insert(new_vals, value, false); ); displace(new_vals, 0); - - instr_nr++; } /* Remember end-workset for this block */ block_info->end_workset = workset_clone(ws); DB((dbg, DBG_WSETS, "End workset for %+F:\n", block)); - workset_foreach(ws, irn, iter) - DB((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(ws, iter))); + { + ir_node *irn; + workset_foreach(ws, irn, iter) + DB((dbg, DBG_WSETS, " %+F (%u)\n", irn, workset_get_time(ws, iter))); + } } /** @@ -950,13 +955,10 @@ static void be_spill_belady(ir_graph *irg, const arch_register_class_t *rcls) { int i; - be_liveness_assure_sets(be_assure_liveness(irg)); + be_assure_live_sets(irg); stat_ev_tim_push(); - /* construct control flow loop tree */ - if (! (get_irg_loopinfo_state(irg) & loopinfo_cf_consistent)) { - construct_cf_backedges(irg); - } + assure_loopinfo(irg); stat_ev_tim_pop("belady_time_backedges"); stat_ev_tim_push(); @@ -1004,7 +1006,7 @@ static void be_spill_belady(ir_graph *irg, const arch_register_class_t *rcls) obstack_free(&obst, NULL); } -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady); +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady) void be_init_spillbelady(void) { static be_spiller_t belady_spiller = {