- const arch_env_t *arch_env;
- const be_chordal_env_t *chordal_env;
- struct obstack obst;
- int spill_cost; /**< the cost of a single spill node */
- int reload_cost; /**< the cost of a reload node */
- set *spills; /**< all spill_info_t's, which must be placed */
- pset *mem_phis; /**< set of all special spilled phis. allocated and freed separately */
-
- DEBUG_ONLY(firm_dbg_module_t *dbg;)
-};
-
-/**
- * Compare two spill infos.
- */
-static int cmp_spillinfo(const void *x, const void *y, size_t size) {
- const spill_info_t *xx = x;
- const spill_info_t *yy = y;
- return xx->spilled_node != yy->spilled_node;
-}
-
-/**
- * Returns spill info for a specific value (returns NULL if the info doesn't
- * exist yet)
- */
-static spill_info_t *find_spillinfo(const spill_env_t *env, ir_node *value) {
- spill_info_t info;
- int hash = nodeset_hash(value);
-
- info.spilled_node = value;
-
- return set_find(env->spills, &info, sizeof(info), hash);
-}
-
-/**
- * Returns spill info for a specific value (the value that is to be spilled)
- */
-static spill_info_t *get_spillinfo(const spill_env_t *env, ir_node *value) {
- spill_info_t info, *res;
- int hash = nodeset_hash(value);
-
- info.spilled_node = value;
- res = set_find(env->spills, &info, sizeof(info), hash);
-
- if (res == NULL) {
- info.reloaders = NULL;
- info.spill = NULL;
- info.old_spill = NULL;
- res = set_insert(env->spills, &info, sizeof(info), hash);
- }
-
- return res;
-}
-
-DEBUG_ONLY(
-/* Sets the debug module of a spill environment. */
-void be_set_spill_env_dbg_module(spill_env_t *env, firm_dbg_module_t *dbg) {
- env->dbg = dbg;
-}
-)
-
-/* Creates a new spill environment. */
-spill_env_t *be_new_spill_env(const be_chordal_env_t *chordal_env) {
- spill_env_t *env = xmalloc(sizeof(env[0]));
- env->spills = new_set(cmp_spillinfo, 1024);
- env->cls = chordal_env->cls;
- env->chordal_env = chordal_env;
- env->arch_env = env->chordal_env->birg->main_env->arch_env;
- env->mem_phis = pset_new_ptr_default();
- // TODO, ask backend about costs...
- env->spill_cost = 8;
- env->reload_cost = 5;
- obstack_init(&env->obst);
- return env;
-}
-
-/* Deletes a spill environment. */
-void be_delete_spill_env(spill_env_t *env) {
- del_set(env->spills);
- del_pset(env->mem_phis);
- obstack_free(&env->obst, NULL);
- free(env);
-}
-
-/*
- * ____ _ ____ _ _
- * | _ \| | __ _ ___ ___ | _ \ ___| | ___ __ _ __| |___
- * | |_) | |/ _` |/ __/ _ \ | |_) / _ \ |/ _ \ / _` |/ _` / __|
- * | __/| | (_| | (_| __/ | _ < __/ | (_) | (_| | (_| \__ \
- * |_| |_|\__,_|\___\___| |_| \_\___|_|\___/ \__,_|\__,_|___/
- *
- */
-
-void be_add_reload(spill_env_t *env, ir_node *to_spill, ir_node *before) {
- spill_info_t *info;
- reloader_t *rel;
-
- assert(arch_irn_consider_in_reg_alloc(env->arch_env, env->cls, to_spill));
-
- info = get_spillinfo(env, to_spill);
-
- if(is_Phi(to_spill)) {
- int i, arity;
- // create spillinfos for the phi arguments
- for(i = 0, arity = get_irn_arity(to_spill); i < arity; ++i) {
- ir_node *arg = get_irn_n(to_spill, i);
- get_spillinfo(env, arg);
- }
-
-#if 1
- // hackery... sometimes the morgan algo spilled the value of a phi,
- // the belady algo decides later to spill the whole phi, then sees the
- // spill node and adds a reload for that spill node, problem is the
- // reload gets attach to that same spill (and is totally unnecessary)
- if(info->old_spill != NULL &&
- (before == info->old_spill || value_dominates(before, info->old_spill))) {
- printf("spilledphi hack was needed...\n");
- before = sched_next(info->old_spill);
- }
-#endif
- }
-
- rel = obstack_alloc(&env->obst, sizeof(rel[0]));
- rel->reloader = before;
- rel->next = info->reloaders;
- info->reloaders = rel;
-}
-
-static ir_node *get_reload_insertion_point(ir_node *block, int pos) {
- ir_node *predblock, *last;
-
- /* simply add the reload to the beginning of the block if we only have 1 predecessor
- * (we don't need to check for phis as there can't be any in a block with only 1 pred)
- */
- if(get_Block_n_cfgpreds(block) == 1) {
- assert(!is_Phi(sched_first(block)));
- return sched_first(block);
- }
-
- /* We have to reload the value in pred-block */
- predblock = get_Block_cfgpred_block(block, pos);
- last = sched_last(predblock);
-
- /* we might have projs and keepanys behind the jump... */
- while(is_Proj(last) || be_is_Keep(last)) {
- last = sched_prev(last);
- assert(!sched_is_end(last));
- }
-
- if(!is_cfop(last)) {
- ir_graph *irg = get_irn_irg(block);
- ir_node *startblock = get_irg_start_block(irg);
-
- last = sched_next(last);
- // last node must be a cfop, only exception is the start block
- assert(last == startblock);
- }
-
- // add the reload before the (cond-)jump
- return last;
-}
-
-void be_add_reload_on_edge(spill_env_t *env, ir_node *to_spill, ir_node *block, int pos) {
- ir_node *before = get_reload_insertion_point(block, pos);
- be_add_reload(env, to_spill, before);
-}
-
-void be_spill_phi(spill_env_t *env, ir_node *node) {
- spill_info_t* spill;
- int i, arity;
-
- assert(is_Phi(node));
-
- pset_insert_ptr(env->mem_phis, node);
-
- // create spillinfos for the phi arguments
- spill = get_spillinfo(env, node);
- for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
- ir_node *arg = get_irn_n(node, i);
- get_spillinfo(env, arg);
- }
-
- // if we had a spill for the phi value before, then remove this spill from
- // schedule, as we will remove it in the insert spill/reload phase
- if(spill->spill != NULL && !is_Phi(spill->spill)) {
- assert(spill->old_spill == NULL);
- spill->old_spill = spill->spill;
- spill->spill = NULL;
- }
-}
-
-/*
- * ____ _ ____ _ _ _
- * / ___|_ __ ___ __ _| |_ ___ / ___| _ __ (_) | |___
- * | | | '__/ _ \/ _` | __/ _ \ \___ \| '_ \| | | / __|
- * | |___| | | __/ (_| | || __/ ___) | |_) | | | \__ \
- * \____|_| \___|\__,_|\__\___| |____/| .__/|_|_|_|___/
- * |_|
- */
-
-/**
- * Schedules a node after an instruction. (That is the place after all projs and phis
- * that are scheduled after the instruction)
- * This function also skips phi nodes at the beginning of a block
- */
-static void sched_add_after_insn(ir_node *sched_after, ir_node *node) {
- ir_node *next = sched_next(sched_after);
- while(is_Proj(next) || is_Phi(next)) {
- next = sched_next(next);
- }
- assert(next != NULL);
-
- if(sched_is_end(next)) {
- sched_add_after(sched_last(get_nodes_block(sched_after)), node);
- } else {
- sched_add_before(next, node);
- }
-}
-
-/**
- * Creates a spill.
- *
- * @param senv the spill environment
- * @param irn the node that should be spilled
- * @param ctx_irn an user of the spilled node
- *
- * @return a be_Spill node
- */
-static void spill_irn(spill_env_t *env, spill_info_t *spillinfo) {
- ir_node *to_spill = spillinfo->spilled_node;
-
- DBG((env->dbg, LEVEL_1, "%+F\n", to_spill));
-
- /* Trying to spill an already spilled value, no need for a new spill
- * node then, we can simply connect to the same one for this reload
- *
- * (although rematerialization code should handle most of these cases
- * this can still happen when spilling Phis)