X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady2.c;h=6abbbd5227ee83d39b37d0403ab6340de7400304;hb=7fc5212efdd0faf06fed3850760ca319bdc66afc;hp=8da5a8e08b32d5c0f4824a0420b84a60fb42a206;hpb=f6750fd8b384d9795d13ab2985b4a4a631a31e7e;p=libfirm diff --git a/ir/be/bespillbelady2.c b/ir/be/bespillbelady2.c index 8da5a8e08..6abbbd522 100644 --- a/ir/be/bespillbelady2.c +++ b/ir/be/bespillbelady2.c @@ -58,7 +58,7 @@ #include "besched.h" #include "beirgmod.h" #include "belive_t.h" -#include "benode_t.h" +#include "benode.h" #include "bechordal_t.h" #include "bespill.h" #include "beloopana.h" @@ -101,7 +101,7 @@ DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;) /** * An association between a node and a point in time. */ -typedef struct _loc_t { +typedef struct loc_t { ir_node *irn; /**< A node. */ unsigned time; /**< A use time. In the global pass this is used @@ -110,12 +110,12 @@ typedef struct _loc_t { */ } loc_t; -typedef struct _workset_t { - int len; /**< current length */ - loc_t vals[0]; /**< inlined array of the values/distances in this working set */ +typedef struct workset_t { + int len; /**< current length */ + loc_t vals[0]; /**< inlined array of the values/distances in this working set */ } workset_t; -typedef struct _belady_env_t { +typedef struct belady_env_t { struct obstack ob; ir_graph *irg; const dfs_t *dfs; @@ -126,12 +126,12 @@ typedef struct _belady_env_t { ir_node **blocks; /**< Array of all blocks. */ int n_blocks; /**< Number of blocks in the graph. */ - int n_regs; /**< number of regs in this reg-class */ - workset_t *ws; /**< the main workset used while processing a block. ob-allocated */ - ir_node *instr; /**< current instruction */ - int instr_nr; /**< current instruction number (relative to block start) */ + int n_regs; /**< number of regs in this reg-class */ + workset_t *ws; /**< the main workset used while processing a block. ob-allocated */ + ir_node *instr; /**< current instruction */ + int instr_nr; /**< current instruction number (relative to block start) */ - spill_env_t *senv; /**< see bespill.h */ + spill_env_t *senv; /**< see bespill.h */ bitset_t *spilled; /**< bitset to keep all the irns which have already been spilled. */ ir_nodeset_t *extra_spilled; /** All nodes for which a special spill location has been computed. */ } belady_env_t; @@ -139,8 +139,8 @@ typedef struct _belady_env_t { static int loc_compare(const void *a, const void *b) { - const loc_t *p = a; - const loc_t *q = b; + const loc_t *p = (const loc_t*)a; + const loc_t *q = (const loc_t*)b; return (p->time > q->time) - (p->time < q->time); } @@ -148,7 +148,7 @@ static inline void workset_print(const workset_t *w) { int i; - for(i = 0; i < w->len; ++i) { + for (i = 0; i < w->len; ++i) { ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time); } } @@ -156,22 +156,18 @@ static inline void workset_print(const workset_t *w) /** * Alloc a new workset on obstack @p ob with maximum size @p max */ -static inline workset_t *new_workset(belady_env_t *env, struct obstack *ob) { - workset_t *res; - size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]); - res = obstack_alloc(ob, size); - memset(res, 0, size); - return res; +static inline workset_t *new_workset(belady_env_t *env, struct obstack *ob) +{ + return OALLOCFZ(ob, workset_t, vals, env->n_regs); } /** * Alloc a new instance on obstack and make it equal to @param ws */ -static inline workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) { - workset_t *res; - size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]); - res = obstack_alloc(ob, size); - memcpy(res, ws, size); +static inline workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) +{ + workset_t *res = OALLOCF(ob, workset_t, vals, env->n_regs); + memcpy(res, ws, sizeof(*res) + (env->n_regs)*sizeof(res->vals[0])); return res; } @@ -179,7 +175,8 @@ static inline workset_t *workset_clone(belady_env_t *env, struct obstack *ob, wo * Do NOT alloc anything. Make @param tgt equal to @param src. * returns @param tgt for convenience */ -static inline workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) { +static inline workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) +{ size_t size = sizeof(*src) + (env->n_regs)*sizeof(src->vals[0]); memcpy(tgt, src, size); return tgt; @@ -190,7 +187,8 @@ static inline workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset * @param count locations given at memory @param locs. * Set the length of @param ws to count. */ -static inline void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) { +static inline void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) +{ workset->len = count; memcpy(&(workset->vals[0]), locs, count * sizeof(locs[0])); } @@ -199,7 +197,8 @@ static inline void workset_bulk_fill(workset_t *workset, int count, const loc_t * Inserts the value @p val into the workset, iff it is not * already contained. The workset must not be full. */ -static inline void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) { +static inline void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) +{ int i; /* check for current regclass */ if (!arch_irn_consider_in_reg_alloc(env->cls, val)) { @@ -208,7 +207,7 @@ static inline void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val } /* check if val is already contained */ - for(i=0; ilen; ++i) + for (i=0; ilen; ++i) if (ws->vals[i].irn == val) return; @@ -220,16 +219,18 @@ static inline void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val /** * Removes all entries from this workset */ -static inline void workset_clear(workset_t *ws) { +static inline void workset_clear(workset_t *ws) +{ ws->len = 0; } /** * Removes the value @p val from the workset if present. */ -static inline void workset_remove(workset_t *ws, ir_node *val) { +static inline void workset_remove(workset_t *ws, ir_node *val) +{ int i; - for(i=0; ilen; ++i) { + for (i=0; ilen; ++i) { if (ws->vals[i].irn == val) { ws->vals[i] = ws->vals[--ws->len]; return; @@ -237,9 +238,10 @@ static inline void workset_remove(workset_t *ws, ir_node *val) { } } -static inline int workset_get_index(const workset_t *ws, const ir_node *val) { +static inline int workset_get_index(const workset_t *ws, const ir_node *val) +{ int i; - for(i=0; ilen; ++i) { + for (i=0; ilen; ++i) { if (ws->vals[i].irn == val) return i; } @@ -253,7 +255,7 @@ static inline int workset_get_index(const workset_t *ws, const ir_node *val) { * @p v A variable to put the current value in * @p i An integer for internal use */ -#define workset_foreach(ws, v, i) for(i=0; \ +#define workset_foreach(ws, v, i) for (i=0; \ v=(i < ws->len) ? ws->vals[i].irn : NULL, i < ws->len; \ ++i) @@ -265,9 +267,9 @@ static inline int workset_get_index(const workset_t *ws, const ir_node *val) { #define workset_sort(ws) qsort((ws)->vals, (ws)->len, sizeof((ws)->vals[0]), loc_compare); #define workset_contains(ws, n) (workset_get_index(ws, n) >= 0) -typedef struct _bring_in_t bring_in_t; +typedef struct bring_in_t bring_in_t; -typedef struct _block_info_t { +typedef struct block_info_t { belady_env_t *bel; ir_node *bl; int id; @@ -293,16 +295,15 @@ typedef struct _block_info_t { } block_info_t; -static inline void *new_block_info(belady_env_t *bel, int id) +static inline block_info_t *new_block_info(belady_env_t *bel, int id) { ir_node *bl = bel->blocks[id]; - block_info_t *res = obstack_alloc(&bel->ob, sizeof(*res)); - memset(res, 0, sizeof(res[0])); + block_info_t *res = OALLOCZ(&bel->ob, block_info_t); res->first_non_in = NULL; - res->last_ins = NULL; - res->bel = bel; - res->bl = bl; - res->id = id; + res->last_ins = NULL; + res->bel = bel; + res->bl = bl; + res->id = id; res->exec_freq = get_block_execfreq(bel->ef, bl); res->reload_cost = bel->arch->reload_cost * res->exec_freq; res->free_at_jump = bel->n_regs; @@ -322,32 +323,24 @@ static inline ir_node *block_info_get_last_ins(block_info_t *bi) return bi->last_ins; } -typedef struct _next_use_t { +typedef struct next_use_t { unsigned is_first_use : 1; /**< Indicate that this use is the first in the block. Needed to identify transport in values for the global pass. */ sched_timestep_t step; /**< The time step of the use. */ ir_node *irn; - struct _next_use_t *next; /**< The next use int this block + struct next_use_t *next; /**< The next use int this block or NULL. */ } next_use_t; -static void *next_use_init(ir_phase *phase, const ir_node *irn, void *old) -{ - (void) phase; - (void) irn; - (void) old; - return NULL; -} - static void build_next_uses(block_info_t *bi) { ir_node *irn; sched_renumber(bi->bl); - phase_init(&bi->next_uses, "next uses", bi->bel->irg, PHASE_DEFAULT_GROWTH, next_use_init, NULL); + phase_init(&bi->next_uses, bi->bel->irg, phase_irn_init_default); sched_foreach_reverse(bi->bl, irn) { int i; @@ -356,8 +349,8 @@ static void build_next_uses(block_info_t *bi) for (i = get_irn_arity(irn) - 1; i >= 0; --i) { ir_node *op = get_irn_n(irn, i); - next_use_t *curr = phase_get_irn_data(&bi->next_uses, op); - next_use_t *use = phase_alloc(&bi->next_uses, sizeof(use[0])); + next_use_t *curr = (next_use_t*)phase_get_irn_data(&bi->next_uses, op); + next_use_t *use = (next_use_t*)phase_alloc(&bi->next_uses, sizeof(use[0])); use->is_first_use = 1; use->step = sched_get_time_step(irn); @@ -374,7 +367,10 @@ static void build_next_uses(block_info_t *bi) } } -#define get_current_use(bi, irn) phase_get_irn_data(&(bi)->next_uses, (irn)) +static inline next_use_t *get_current_use(block_info_t *bi, const ir_node *node) +{ + return (next_use_t*)phase_get_irn_data(&bi->next_uses, node); +} static inline void advance_current_use(block_info_t *bi, const ir_node *irn) { @@ -386,8 +382,8 @@ static inline void advance_current_use(block_info_t *bi, const ir_node *irn) static __attribute__((unused)) int block_freq_gt(const void *a, const void *b) { - const ir_node * const *p = a; - const ir_node * const *q = b; + const ir_node * const *p = (const ir_node**)a; + const ir_node * const *q = (const ir_node**)b; block_info_t *pi = get_block_info(*p); block_info_t *qi = get_block_info(*q); double diff = qi->exec_freq - pi->exec_freq; @@ -396,8 +392,8 @@ static __attribute__((unused)) int block_freq_gt(const void *a, const void *b) static int block_freq_dfs_gt(const void *a, const void *b) { - const ir_node * const *p = a; - const ir_node * const *q = b; + const ir_node * const *p = (const ir_node**)a; + const ir_node * const *q = (const ir_node**)b; block_info_t *pi = get_block_info(*p); block_info_t *qi = get_block_info(*q); double diff; @@ -426,7 +422,7 @@ static int block_freq_dfs_gt(const void *a, const void *b) Data structures to represent bring in variables. */ -struct _bring_in_t { +struct bring_in_t { ir_node *irn; /**< The node to bring in. */ block_info_t *bi; /**< The block to which bring in should happen. */ int pressure_so_far; /**< The maximal pressure till the first use of irn in bl. */ @@ -442,8 +438,7 @@ struct _bring_in_t { static inline bring_in_t *new_bring_in(block_info_t *bi, ir_node *irn, const next_use_t *use) { - bring_in_t *br = obstack_alloc(&bi->bel->ob, sizeof(br[0])); - + bring_in_t *br = OALLOC(&bi->bel->ob, bring_in_t); br->irn = irn; br->bi = bi; br->first_use = use->irn; @@ -506,7 +501,7 @@ static inline unsigned get_curr_distance(block_info_t *bi, const ir_node *irn, i assert(!arch_irn_is_ignore(irn)); /* We have to keep non-spillable nodes in the working set */ - if(flags & arch_irn_flags_dont_spill) + if (flags & arch_irn_flags_dont_spill) return 0; if (!is_usage && use && use->step == curr_step) @@ -560,7 +555,8 @@ static inline int is_transport_in(const ir_node *bl, const ir_node *irn) * @p is_usage indicates that the values in new_vals are used (not defined) * In this case reloads must be performed */ -static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) { +static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) +{ belady_env_t *env = bi->bel; workset_t *ws = env->ws; ir_node **to_insert = ALLOCAN(ir_node*, env->n_regs); @@ -656,9 +652,10 @@ static void displace(block_info_t *bi, workset_t *new_vals, int is_usage) { * whether it is used from a register or is reloaded * before the use. */ -static void belady(belady_env_t *env, int id) { - block_info_t *block_info = new_block_info(env, id); - const ir_node *block = block_info->bl; +static void belady(belady_env_t *env, int id) +{ + block_info_t *block_info = new_block_info(env, id); + const ir_node *block = block_info->bl; workset_t *new_vals; ir_node *irn; @@ -694,7 +691,7 @@ static void belady(belady_env_t *env, int id) { /* allocate all values _used_ by this instruction */ workset_clear(new_vals); - for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) { + for (i = 0, arity = get_irn_arity(irn); i < arity; ++i) { workset_insert(env, new_vals, get_irn_n(irn, i)); } DBG((dbg, DBG_DECIDE, "\t* uses\n")); @@ -706,7 +703,7 @@ static void belady(belady_env_t *env, int id) { * augmenting the pressure. Note, that a variable is dead * if it has no further use in this block and is *not* live end */ - for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) { + for (i = 0, arity = get_irn_arity(irn); i < arity; ++i) { ir_node *op = get_irn_n(irn, i); next_use_t *use = get_current_use(block_info, op); @@ -742,7 +739,7 @@ static void belady(belady_env_t *env, int id) { env->instr_nr++; } - phase_free(&block_info->next_uses); + phase_deinit(&block_info->next_uses); /* Remember end-workset for this block */ block_info->ws_end = workset_clone(env, &env->ob, env->ws); @@ -780,22 +777,22 @@ enum { irn_act_live_through }; -typedef struct _block_state_t { - struct _block_state_t *next; - struct _block_state_t *next_intern; +typedef struct block_state_t { + struct block_state_t *next; + struct block_state_t *next_intern; block_info_t *bi; int pressure; workset_t *end_state; } block_state_t; -typedef struct _irn_action_t { - struct _irn_action_t *next; +typedef struct irn_action_t { + struct irn_action_t *next; ir_node *irn; const ir_node *bl; int act; } irn_action_t; -typedef struct _global_end_state_t { +typedef struct global_end_state_t { belady_env_t *env; bitset_t *succ_phis; bitset_t *committed; @@ -831,7 +828,7 @@ static inline const workset_t *get_end_state(global_end_state_t *ges, block_info static block_state_t *new_block_state(global_end_state_t *ges, block_info_t *bi) { block_state_t *bs = get_block_state(ges, bi); - block_state_t *nw = obstack_alloc(&ges->obst, sizeof(nw[0])); + block_state_t *nw = OALLOC(&ges->obst, block_state_t); nw->next_intern = bs; nw->next = ges->bs_top; @@ -854,7 +851,7 @@ static block_state_t *new_block_state(global_end_state_t *ges, block_info_t *bi) static irn_action_t *new_irn_action(global_end_state_t *ges, ir_node *irn, const ir_node *bl) { - irn_action_t *ia = obstack_alloc(&ges->obst, sizeof(ia[0])); + irn_action_t *ia = OALLOC(&ges->obst, irn_action_t); ia->irn = irn; ia->bl = bl; @@ -1386,7 +1383,7 @@ static bring_in_t **determine_global_order(belady_env_t *env) } obstack_ptr_grow(&env->ob, NULL); - res = obstack_finish(&env->ob); + res = (bring_in_t**)obstack_finish(&env->ob); qsort(res, n, sizeof(res[0]), bring_in_cmp); return res; } @@ -1414,8 +1411,8 @@ static void global_assign(belady_env_t *env) ges.version = ver_make_newer(ver_oldest); ges.succ_phis = bitset_irg_obstack_alloc(&ges.obst, env->irg); ges.committed = bitset_obstack_alloc(&ges.obst, env->n_blocks); - ges.bs_tops = obstack_alloc(&ges.obst, sizeof(ges.bs_tops[0]) * env->n_blocks); - ges.bs_tops_vers = obstack_alloc(&ges.obst, sizeof(ges.bs_tops_vers[0]) * env->n_blocks); + ges.bs_tops = OALLOCN(&ges.obst, block_state_t*, env->n_blocks); + ges.bs_tops_vers = OALLOCN(&ges.obst, unsigned, env->n_blocks); /* invalidate all state stack pointer versions */ for (i = 0; i < env->n_blocks; ++i) { @@ -1456,7 +1453,7 @@ static void global_assign(belady_env_t *env) static void collect_blocks(ir_node *bl, void *data) { - belady_env_t *env = data; + belady_env_t *env = (belady_env_t*)data; ++env->n_blocks; obstack_ptr_grow(&env->ob, bl); } @@ -1466,18 +1463,17 @@ static void collect_blocks(ir_node *bl, void *data) * In the transformed graph, the register pressure never exceeds the number * of available registers. * - * @param birg The backend graph + * @param irg The graph * @param cls The register class to spill */ -void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) +static void be_spill_belady(ir_graph *irg, const arch_register_class_t *cls) { - ir_graph *irg = be_get_birg_irg(birg); belady_env_t env; int i, n_regs; /* some special classes contain only ignore regs, nothing to do then */ - n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL); - if(n_regs == 0) + n_regs = be_get_n_allocatable_regs(irg, cls); + if (n_regs == 0) return; be_clear_links(irg); @@ -1485,21 +1481,21 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) /* init belady env */ obstack_init(&env.ob); env.irg = irg; - env.arch = be_get_birg_arch_env(birg); + env.arch = be_get_irg_arch_env(irg); env.cls = cls; - env.lv = be_get_birg_liveness(birg); + env.lv = be_get_irg_liveness(irg); env.dfs = env.lv->dfs; env.n_regs = n_regs; env.ws = new_workset(&env, &env.ob); - env.senv = be_new_spill_env(birg); - env.ef = be_get_birg_exec_freq(birg); + env.senv = be_new_spill_env(irg); + env.ef = be_get_irg_exec_freq(irg); env.spilled = bitset_irg_obstack_alloc(&env.ob, irg); env.extra_spilled = ir_nodeset_new(64); env.n_blocks = 0; irg_block_walk_graph(irg, NULL, collect_blocks, &env); obstack_ptr_grow(&env.ob, NULL); - env.blocks = obstack_finish(&env.ob); + env.blocks = (ir_node**)obstack_finish(&env.ob); /* renumbering in the blocks gives nicer debug output as number are smaller. */ #ifdef DEBUG_libfirm @@ -1532,6 +1528,7 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls) obstack_free(&env.ob, NULL); } +BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady2); void be_init_spillbelady2(void) { lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be"); @@ -1546,5 +1543,3 @@ void be_init_spillbelady2(void) be_register_spiller("belady2", &belady_spiller); FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady2"); } - -BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady2);