X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillbelady2.c;h=6abbbd5227ee83d39b37d0403ab6340de7400304;hb=7fc5212efdd0faf06fed3850760ca319bdc66afc;hp=bdc99fc7dd403cd3de68c716f771779f82e59578;hpb=6a4b9102668449bea6e3c0905df74f7ffff2768b;p=libfirm diff --git a/ir/be/bespillbelady2.c b/ir/be/bespillbelady2.c index bdc99fc7d..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,14 +156,16 @@ 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) { +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) { +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; @@ -173,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; @@ -184,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])); } @@ -193,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)) { @@ -202,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; @@ -214,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; @@ -231,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; } @@ -247,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) @@ -259,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; @@ -287,7 +295,7 @@ 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 = OALLOCZ(&bel->ob, block_info_t); @@ -315,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; @@ -349,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); @@ -367,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) { @@ -379,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; @@ -389,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; @@ -419,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. */ @@ -498,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) @@ -552,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); @@ -648,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; @@ -686,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")); @@ -698,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); @@ -734,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); @@ -772,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; @@ -1378,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; } @@ -1448,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); } @@ -1458,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); @@ -1477,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 @@ -1524,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"); @@ -1538,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);