/**
* 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
*/
} loc_t;
-typedef struct _workset_t {
+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;
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 instr_nr; /**< current instruction number (relative to block start) */
spill_env_t *senv; /**< see bespill.h */
bitset_t *spilled; /**< bitset to keep all the irns which have already been spilled. */
{
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);
}
}
}
/* check if val is already contained */
- for(i=0; i<ws->len; ++i)
+ for (i=0; i<ws->len; ++i)
if (ws->vals[i].irn == val)
return;
static inline void workset_remove(workset_t *ws, ir_node *val)
{
int i;
- for(i=0; i<ws->len; ++i) {
+ for (i=0; i<ws->len; ++i) {
if (ws->vals[i].irn == val) {
ws->vals[i] = ws->vals[--ws->len];
return;
static inline int workset_get_index(const workset_t *ws, const ir_node *val)
{
int i;
- for(i=0; i<ws->len; ++i) {
+ for (i=0; i<ws->len; ++i) {
if (ws->vals[i].irn == val)
return i;
}
* @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)
#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;
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;
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. */
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)
/* 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"));
* 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);
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);
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;
* 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 = cls->n_regs - be_put_ignore_regs(irg, cls, NULL);
+ if (n_regs == 0)
return;
be_clear_links(irg);
/* 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;
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");
be_register_spiller("belady2", &belady_spiller);
FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady2");
}
-
-BE_REGISTER_MODULE_CONSTRUCTOR(be_init_spillbelady2);