ir_node *irn; /**< A node. */
unsigned time; /**< A use time.
In the global pass this is used
ir_node *irn; /**< A node. */
unsigned time; /**< A use time.
In the global pass this is used
-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 */
- 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) */
+ 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) */
- spill_env_t *senv; /**< see bespill.h */
- bitset_t *spilled; /**< bitset to keep all the irns which have already been spilled. */
+ 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. */
ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time);
}
}
ir_fprintf(stderr, "%+F %d\n", w->vals[i].irn, w->vals[i].time);
}
}
-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);
-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]));
* Inserts the value @p val into the workset, iff it is not
* already contained. The workset must not be full.
*/
* Inserts the value @p val into the workset, iff it is not
* already contained. The workset must not be full.
*/
// DBG((dbg, DBG_WORKSET, "Skipped %+F\n", val));
return;
}
/* check if val is already contained */
// DBG((dbg, DBG_WORKSET, "Skipped %+F\n", val));
return;
}
/* check if val is already contained */
#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)
#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)
- 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);
#define get_block_info(block) ((block_info_t *)get_irn_link(block))
#define set_block_info(block, info) set_irn_link(block, info)
#define get_block_info(block) ((block_info_t *)get_irn_link(block))
#define set_block_info(block, info) set_irn_link(block, info)
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;
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;
- 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);
for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
ir_node *op = get_irn_n(irn, i);
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]));
-#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);
+}
block_info_t *pi = get_block_info(*p);
block_info_t *qi = get_block_info(*q);
double diff = qi->exec_freq - pi->exec_freq;
block_info_t *pi = get_block_info(*p);
block_info_t *qi = get_block_info(*q);
double diff = qi->exec_freq - pi->exec_freq;
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. */
ir_node *first_use; /**< The first user of irn in bl. */
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. */
ir_node *first_use; /**< The first user of irn in bl. */
int is_remat : 1; /**< Is rematerializable. */
int sect_pressure; /**< Offset to maximum pressure in block. */
int is_remat : 1; /**< Is rematerializable. */
int sect_pressure; /**< Offset to maximum pressure in block. */
{
belady_env_t *env = bi->bel;
sched_timestep_t curr_step = sched_get_time_step(env->instr);
next_use_t *use = get_current_use(bi, irn);
{
belady_env_t *env = bi->bel;
sched_timestep_t curr_step = sched_get_time_step(env->instr);
next_use_t *use = get_current_use(bi, irn);
- /* We have to keep nonspillable nodes in the workingset */
- if(flags & arch_irn_flags_dont_spill)
+ /* We have to keep non-spillable nodes in the working set */
+ if (flags & arch_irn_flags_dont_spill)
* @param irn The node in question.
* @return 1, if node is something transported into @p bl, 0 if not.
* @note The function will only give correct answers in the case
* @param irn The node in question.
* @return 1, if node is something transported into @p bl, 0 if not.
* @note The function will only give correct answers in the case
* @p is_usage indicates that the values in new_vals are used (not defined)
* In this case reloads must be performed
*/
* @p is_usage indicates that the values in new_vals are used (not defined)
* In this case reloads must be performed
*/
int i, len, max_allowed, demand, iter;
ir_node *val;
int i, len, max_allowed, demand, iter;
ir_node *val;
-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;
* Phis are no real instr (see insert_starters())
* instr_nr does not increase */
if (is_Proj(irn) || is_Phi(irn))
* Phis are no real instr (see insert_starters())
* instr_nr does not increase */
if (is_Proj(irn) || is_Phi(irn))
workset_insert(env, new_vals, get_irn_n(irn, i));
}
DBG((dbg, DBG_DECIDE, "\t* uses\n"));
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
*/
* augmenting the pressure. Note, that a variable is dead
* if it has no further use in this block and is *not* live end
*/
ir_node *op = get_irn_n(irn, i);
next_use_t *use = get_current_use(block_info, op);
ir_node *op = get_irn_n(irn, i);
next_use_t *use = get_current_use(block_info, op);
if (is_op_forking(get_irn_op(env->instr))) {
for (i = get_irn_arity(env->instr) - 1; i >= 0; --i) {
ir_node *op = get_irn_n(env->instr, i);
if (is_op_forking(get_irn_op(env->instr))) {
for (i = get_irn_arity(env->instr) - 1; i >= 0; --i) {
ir_node *op = get_irn_n(env->instr, i);
/* Remember end-workset for this block */
block_info->ws_end = workset_clone(env, &env->ob, env->ws);
/* Remember end-workset for this block */
block_info->ws_end = workset_clone(env, &env->ob, env->ws);
-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;
{
int id = bi->id;
assert(!ver_is_younger(ges->bs_tops_vers[id], ges->version));
return ver_is_older(ges->bs_tops_vers[id], ges->version) ? NULL : ges->bs_tops[bi->id];
}
{
int id = bi->id;
assert(!ver_is_younger(ges->bs_tops_vers[id], ges->version));
return ver_is_older(ges->bs_tops_vers[id], ges->version) ? NULL : ges->bs_tops[bi->id];
}
{
block_state_t *bs = get_block_state(ges, bi);
return bs ? bs->end_state : bi->ws_end;
{
block_state_t *bs = get_block_state(ges, bi);
return bs ? bs->end_state : bi->ws_end;
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);
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);
if (is_transport_in(bl, irn)) {
int i, n = get_irn_arity(bl);
if (is_transport_in(bl, irn)) {
int i, n = get_irn_arity(bl);
c = can_make_available_at_end(ges, pr, op, limit - glob_costs, level + 1);
else
c = 0.0;
c = can_make_available_at_end(ges, pr, op, limit - glob_costs, level + 1);
else
c = 0.0;
*
* If the second is larger than the first,
* we have to increment the total block pressure and hence
*
* If the second is larger than the first,
* we have to increment the total block pressure and hence
DBG((dbg, DBG_GLOBAL, "\t-> use blocked. local reload: %+F, try spill at: %+F\n",
br->first_use, better_spill_loc));
be_add_reload(env->senv, irn, br->first_use, env->cls, 1);
DBG((dbg, DBG_GLOBAL, "\t-> use blocked. local reload: %+F, try spill at: %+F\n",
br->first_use, better_spill_loc));
be_add_reload(env->senv, irn, br->first_use, env->cls, 1);
- be_add_spill(env->senv, irn, sched_next(better_spill_loc));
+ be_add_spill(env->senv, irn, better_spill_loc);
+ ir_nodeset_insert(env->extra_spilled, irn);
* which additionally live through the block to their pressure.
* at the point were the actually treated use is, we have to increase
* which additionally live through the block to their pressure.
* at the point were the actually treated use is, we have to increase
qsort(res, n, sizeof(res[0]), bring_in_cmp);
return res;
}
qsort(res, n, sizeof(res[0]), bring_in_cmp);
return res;
}
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.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);
for (br = determine_global_order(env); *br; ++br)
optimize_variable(&ges, *br);
for (br = determine_global_order(env); *br; ++br)
optimize_variable(&ges, *br);
&& !bitset_contains_irn(ges.succ_phis, irn))
be_spill_phi(env->senv, irn);
}
}
&& !bitset_contains_irn(ges.succ_phis, irn))
be_spill_phi(env->senv, irn);
}
}
+
+ /* check dominance for specially spilled nodes. */
+ foreach_ir_nodeset (env->extra_spilled, irn, iter)
+ make_spill_locations_dominate_irn(env->senv, irn);
* In the transformed graph, the register pressure never exceeds the number
* of available registers.
*
* In the transformed graph, the register pressure never exceeds the number
* of available registers.
*
env.n_blocks = 0;
irg_block_walk_graph(irg, NULL, collect_blocks, &env);
obstack_ptr_grow(&env.ob, NULL);
env.n_blocks = 0;
irg_block_walk_graph(irg, NULL, collect_blocks, &env);
obstack_ptr_grow(&env.ob, NULL);
+ /* check dominance for specially spilled nodes. */
+ {
+ ir_nodeset_iterator_t iter;
+ ir_node *irn;
+
+ foreach_ir_nodeset (env.extra_spilled, irn, iter)
+ make_spill_locations_dominate_irn(env.senv, irn);
+ }
+
/* Insert spill/reload nodes into the graph and fix usages */
be_insert_spills_reloads(env.senv);
/* clean up */
be_delete_spill_env(env.senv);
/* Insert spill/reload nodes into the graph and fix usages */
be_insert_spills_reloads(env.senv);
/* clean up */
be_delete_spill_env(env.senv);
void be_init_spillbelady2(void)
{
lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
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_spiller("belady2", &belady_spiller);
FIRM_DBG_REGISTER(dbg, "firm.be.spill.belady2");
}