* @date 20.09.2005
* @version $Id$
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include <stdbool.h>
#include "ircons_t.h"
#include "irprintf.h"
#include "irnodeset.h"
-#include "xmalloc.h"
-#include "pdeq.h"
#include "beutil.h"
#include "bearch_t.h"
} workset_t;
static struct obstack obst;
-static const arch_env_t *arch_env;
static const arch_register_class_t *cls;
static const be_lv_t *lv;
static be_loopana_t *loop_ana;
static unsigned instr_nr; /**< current instruction number
(relative to block start) */
static spill_env_t *senv; /**< see bespill.h */
-static pdeq *worklist;
+static ir_node **blocklist;
static bool move_spills = true;
static bool respectloopdepth = true;
loc_t *loc;
int i;
/* check for current regclass */
- assert(arch_irn_consider_in_reg_alloc(arch_env, cls, val));
+ assert(arch_irn_consider_in_reg_alloc(cls, val));
/* check if val is already contained */
for (i = 0; i < workset->len; ++i) {
/**
* Removes the value @p val from the workset if present.
*/
-static INLINE void workset_remove(workset_t *workset, ir_node *val)
+static inline void workset_remove(workset_t *workset, ir_node *val)
{
int i;
for(i = 0; i < workset->len; ++i) {
}
}
-static INLINE const loc_t *workset_contains(const workset_t *ws,
+static inline const loc_t *workset_contains(const workset_t *ws,
const ir_node *val)
{
int i;
/**
* @return The distance to the next use or 0 if irn has dont_spill flag set
*/
-static INLINE unsigned get_distance(ir_node *from, unsigned from_step,
+static inline unsigned get_distance(ir_node *from, unsigned from_step,
const ir_node *def, int skip_from_uses)
{
be_next_use_t use;
- int flags = arch_irn_get_flags(arch_env, def);
unsigned costs;
unsigned time;
- assert(! (flags & arch_irn_flags_ignore));
+ assert(!arch_irn_is_ignore(def));
use = be_get_next_use(uses, from, from_step, def, skip_from_uses);
time = use.time;
return USES_INFINITY;
/* We have to keep nonspillable nodes in the workingset */
- if (flags & arch_irn_flags_dont_spill)
+ if (arch_irn_get_flags(def) & arch_irn_flags_dont_spill)
return 0;
/* give some bonus to rematerialisable nodes */
*/
static void displace(workset_t *new_vals, int is_usage)
{
- ir_node **to_insert = alloca(n_regs * sizeof(to_insert[0]));
- bool *spilled = alloca(n_regs * sizeof(spilled[0]));
+ ir_node **to_insert = ALLOCAN(ir_node*, n_regs);
+ bool *spilled = ALLOCAN(bool, n_regs);
ir_node *val;
int i;
int len;
loc.node = node;
loc.spilled = false;
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, node)) {
+ if (!arch_irn_consider_in_reg_alloc(cls, node)) {
loc.time = USES_INFINITY;
return loc;
}
/* We have to keep nonspillable nodes in the workingset */
- if (arch_irn_get_flags(arch_env, node) & arch_irn_flags_dont_spill) {
+ if (arch_irn_get_flags(node) & arch_irn_flags_dont_spill) {
loc.time = 0;
DB((dbg, DBG_START, " %+F taken (dontspill node)\n", node, loc.time));
return loc;
/* check predecessors */
arity = get_irn_arity(block);
- pred_worksets = alloca(sizeof(pred_worksets[0]) * arity);
+ pred_worksets = ALLOCAN(workset_t*, arity);
all_preds_known = true;
for(i = 0; i < arity; ++i) {
ir_node *pred_block = get_Block_cfgpred_block(block, i);
if (! is_Phi(node))
break;
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, node))
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
continue;
if (all_preds_known) {
int p, arity;
loc_t *loc = & delayed[i];
- /* don't use values which are dead in a known predecessors
- * to not induce unnecessary reloads */
- arity = get_irn_arity(block);
- for (p = 0; p < arity; ++p) {
- ir_node *pred_block = get_Block_cfgpred_block(block, p);
- block_info_t *pred_info = get_block_info(pred_block);
-
- if (pred_info == NULL)
- continue;
-
- if (!workset_contains(pred_info->end_workset, loc->node)) {
- DB((dbg, DBG_START,
- " delayed %+F not live at pred %+F\n", loc->node,
- pred_block));
- goto skip_delayed;
+ if (!is_Phi(loc->node)) {
+ /* don't use values which are dead in a known predecessors
+ * to not induce unnecessary reloads */
+ arity = get_irn_arity(block);
+ for (p = 0; p < arity; ++p) {
+ ir_node *pred_block = get_Block_cfgpred_block(block, p);
+ block_info_t *pred_info = get_block_info(pred_block);
+
+ if (pred_info == NULL)
+ continue;
+
+ if (!workset_contains(pred_info->end_workset, loc->node)) {
+ DB((dbg, DBG_START,
+ " delayed %+F not live at pred %+F\n", loc->node,
+ pred_block));
+ goto skip_delayed;
+ }
}
}
* whether it is used from a register or is reloaded
* before the use.
*/
-static void belady(ir_node *block)
+static void process_block(ir_node *block)
{
workset_t *new_vals;
ir_node *irn;
int iter;
block_info_t *block_info;
- int i, arity;
- int has_backedges = 0;
- //int first = 0;
- const ir_edge_t *edge;
+ int arity;
/* no need to process a block twice */
- if (get_block_info(block) != NULL) {
- return;
- }
+ assert(get_block_info(block) == NULL);
- /* check if all predecessor blocks are processed yet (though for backedges
- * we have to make an exception as we can't process them first) */
+ /* construct start workset */
arity = get_Block_n_cfgpreds(block);
- for(i = 0; i < arity; ++i) {
- ir_node *pred_block = get_Block_cfgpred_block(block, i);
- block_info_t *pred_info = get_block_info(pred_block);
-
- if (pred_info == NULL) {
- /* process predecessor first (it will be in the queue already) */
- if (!is_backedge(block, i)) {
- return;
- }
- has_backedges = 1;
- }
- }
- (void) has_backedges;
if (arity == 0) {
+ /* no predecessor -> empty set */
workset_clear(ws);
} else if (arity == 1) {
+ /* one predecessor, copy it's end workset */
ir_node *pred_block = get_Block_cfgpred_block(block, 0);
block_info_t *pred_info = get_block_info(pred_block);
assert(pred_info != NULL);
workset_copy(ws, pred_info->end_workset);
} else {
- /* we need 2 heuristics here, for the case when all predecessor blocks
- * are known and when some are backedges (and therefore can't be known
- * yet) */
+ /* multiple predecessors, do more advanced magic :) */
decide_start_workset(block);
}
workset_clear(new_vals);
for(i = 0, arity = get_irn_arity(irn); i < arity; ++i) {
ir_node *in = get_irn_n(irn, i);
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, in))
+ if (!arch_irn_consider_in_reg_alloc(cls, in))
continue;
/* (note that "spilled" is irrelevant here) */
foreach_out_edge(irn, edge) {
ir_node *proj = get_edge_src_irn(edge);
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, proj))
+ if (!arch_irn_consider_in_reg_alloc(cls, proj))
continue;
workset_insert(new_vals, proj, false);
}
} else {
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, irn))
+ if (!arch_irn_consider_in_reg_alloc(cls, irn))
continue;
workset_insert(new_vals, irn, false);
}
workset_foreach(ws, irn, iter)
DB((dbg, DBG_WSETS, " %+F (%u)\n", irn,
workset_get_time(ws, iter)));
-
- /* add successor blocks into worklist */
- foreach_block_succ(block, edge) {
- ir_node *succ = get_edge_src_irn(edge);
- pdeq_putr(worklist, succ);
- }
}
/**
DB((dbg, DBG_FIX, "\n"));
DB((dbg, DBG_FIX, "Fixing %+F\n", block));
+ arity = get_irn_arity(block);
+ /* can happen for endless loops */
+ if (arity == 0)
+ return;
+
start_workset = get_block_info(block)->start_workset;
/* process all pred blocks */
- arity = get_irn_arity(block);
for (i = 0; i < arity; ++i) {
ir_node *pred = get_Block_cfgpred_block(block, i);
workset_t *pred_end_workset = get_block_info(pred)->end_workset;
assert(!l->spilled);
/* we might have unknowns as argument for the phi */
- if (!arch_irn_consider_in_reg_alloc(arch_env, cls, node))
+ if (!arch_irn_consider_in_reg_alloc(cls, node))
continue;
}
}
}
+static void add_block(ir_node *block, void *data)
+{
+ (void) data;
+ ARR_APP1(ir_node*, blocklist, block);
+}
+
static void be_spill_belady(be_irg_t *birg, const arch_register_class_t *rcls)
{
+ int i;
ir_graph *irg = be_get_birg_irg(birg);
be_liveness_assure_sets(be_assure_liveness(birg));
+ stat_ev_tim_push();
/* construct control flow loop tree */
if (! (get_irg_loopinfo_state(irg) & loopinfo_cf_consistent)) {
construct_cf_backedges(irg);
}
+ stat_ev_tim_pop("belady_time_backedges");
+ stat_ev_tim_push();
be_clear_links(irg);
+ stat_ev_tim_pop("belady_time_clear_links");
+
+ ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
/* init belady env */
+ stat_ev_tim_push();
obstack_init(&obst);
- arch_env = birg->main_env->arch_env;
- cls = rcls;
- lv = be_get_birg_liveness(birg);
- n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
- ws = new_workset();
- uses = be_begin_uses(irg, lv);
- loop_ana = be_new_loop_pressure(birg);
- senv = be_new_spill_env(birg);
- worklist = new_pdeq();
-
- pdeq_putr(worklist, get_irg_start_block(irg));
-
- while(!pdeq_empty(worklist)) {
- ir_node *block = pdeq_getl(worklist);
- belady(block);
+ cls = rcls;
+ lv = be_get_birg_liveness(birg);
+ n_regs = cls->n_regs - be_put_ignore_regs(birg, cls, NULL);
+ ws = new_workset();
+ uses = be_begin_uses(irg, lv);
+ loop_ana = be_new_loop_pressure(birg, cls);
+ senv = be_new_spill_env(birg);
+ blocklist = NEW_ARR_F(ir_node*, 0);
+ irg_block_edges_walk(get_irg_start_block(irg), NULL, add_block, NULL);
+ stat_ev_tim_pop("belady_time_init");
+
+ stat_ev_tim_push();
+ /* walk blocks in reverse postorder */
+ for (i = ARR_LEN(blocklist) - 1; i >= 0; --i) {
+ process_block(blocklist[i]);
}
- /* end block might not be reachable in endless loops */
- belady(get_irg_end_block(irg));
-
- del_pdeq(worklist);
+ DEL_ARR_F(blocklist);
+ stat_ev_tim_pop("belady_time_belady");
+ stat_ev_tim_push();
/* belady was block-local, fix the global flow by adding reloads on the
* edges */
irg_block_walk_graph(irg, fix_block_borders, NULL, NULL);
+ stat_ev_tim_pop("belady_time_fix_borders");
+
+ ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
/* Insert spill/reload nodes into the graph and fix usages */
be_insert_spills_reloads(senv);
projects / libfirm / blobdiff