-#include "bemodule.h"
-
-DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
-
-#define REMAT_COST_INFINITE 1000
-
-typedef struct reloader_t reloader_t;
-struct reloader_t {
- reloader_t *next;
- ir_node *can_spill_after;
- ir_node *reloader;
- ir_node *rematted_node;
- int remat_cost_delta; /** costs needed for rematerialization,
- compared to placing a reload */
-};
-
-typedef struct spill_t spill_t;
-struct spill_t {
- spill_t *next;
- ir_node *before; /**< spill has to be placed before this node (or earlier) */
- ir_node *spill;
-};
-
-typedef struct spill_info_t spill_info_t;
-struct spill_info_t {
- ir_node *to_spill; /**< the value that should get spilled */
- reloader_t *reloaders; /**< list of places where the value should get
- reloaded */
- spill_t *spills; /**< list of latest places where spill must be
- placed */
- double spill_costs; /**< costs needed for spilling the value */
- const arch_register_class_t *reload_cls; /** the register class in which the
- reload should be placed */
-};
-
-struct spill_env_t {
- const arch_env_t *arch_env;
- ir_graph *irg;
- struct obstack obst;
- be_irg_t *birg;
- 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 */
- ir_nodeset_t mem_phis; /**< set of all spilled phis. */
- ir_exec_freq *exec_freq;
- unsigned new_nodes_idx; /**< all old nodes idx is smaller than
- this */
-
-#ifdef FIRM_STATISTICS
- unsigned spill_count;
- unsigned reload_count;
- unsigned remat_count;
- unsigned spilled_phi_count;
-#endif
-};
-
-/**
- * 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;
- (void) size;
-
- return xx->to_spill != yy->to_spill;
-}
-
-/**
- * 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 = hash_irn(value);
-
- info.to_spill = value;
- res = set_find(env->spills, &info, sizeof(info), hash);
-
- if (res == NULL) {
- info.reloaders = NULL;
- info.spills = NULL;
- info.spill_costs = -1;
- info.reload_cls = NULL;
- res = set_insert(env->spills, &info, sizeof(info), hash);
- }
-
- return res;
-}
-
-spill_env_t *be_new_spill_env(be_irg_t *birg)
-{
- const arch_env_t *arch_env = birg->main_env->arch_env;
-
- spill_env_t *env = xmalloc(sizeof(env[0]));
- env->spills = new_set(cmp_spillinfo, 1024);
- env->irg = be_get_birg_irg(birg);
- env->birg = birg;
- env->arch_env = arch_env;
- ir_nodeset_init(&env->mem_phis);
- env->spill_cost = arch_env->isa->spill_cost;
- env->reload_cost = arch_env->isa->reload_cost;
- env->exec_freq = be_get_birg_exec_freq(birg);
- obstack_init(&env->obst);
-
-#ifdef FIRM_STATISTICS
- env->spill_count = 0;
- env->reload_count = 0;
- env->remat_count = 0;
- env->spilled_phi_count = 0;
-#endif
-
- return env;
-}
-
-void be_delete_spill_env(spill_env_t *env)
-{
- del_set(env->spills);
- ir_nodeset_destroy(&env->mem_phis);
- obstack_free(&env->obst, NULL);
- free(env);
-}
-
-/*
- * ____ _ ____ _ _
- * | _ \| | __ _ ___ ___ | _ \ ___| | ___ __ _ __| |___
- * | |_) | |/ _` |/ __/ _ \ | |_) / _ \ |/ _ \ / _` |/ _` / __|
- * | __/| | (_| | (_| __/ | _ < __/ | (_) | (_| | (_| \__ \
- * |_| |_|\__,_|\___\___| |_| \_\___|_|\___/ \__,_|\__,_|___/
- *
- */
-
-void be_add_spill(spill_env_t *env, ir_node *to_spill, ir_node *before)
-{
-#if 1
- spill_info_t *spill_info = get_spillinfo(env, to_spill);
- spill_t *spill;
- spill_t *s;
- spill_t *last;
-
- assert(! arch_irn_is(env->arch_env, to_spill, dont_spill));
- DB((dbg, LEVEL_1, "Add spill of %+F before %+F\n", to_spill, before));
-
- /* spills that are dominated by others are not needed */
- last = NULL;
- s = spill_info->spills;
- for( ; s != NULL; s = s->next) {
- /* no need to add this spill if it is dominated by another */
- if(value_dominates(s->before, before)) {
- DB((dbg, LEVEL_1, "...dominated by %+F, not added\n", s->before));
- return;
- }
- /* remove spills that we dominate */
- if(value_dominates(before, s->before)) {
- DB((dbg, LEVEL_1, "...remove old spill at %+F\n", s->before));
- if(last != NULL) {
- last->next = s->next;
- } else {
- spill_info->spills = s->next;
- }
- } else {
- last = s;
- }
- }
-
- spill = obstack_alloc(&env->obst, sizeof(spill[0]));
- spill->before = before;
- spill->next = spill_info->spills;
- spill->spill = NULL;
-
- spill_info->spills = spill;
-#endif
-}
-
-void be_add_remat(spill_env_t *env, ir_node *to_spill, ir_node *before,
- ir_node *rematted_node)
-{
- spill_info_t *spill_info;
- reloader_t *reloader;
-
- spill_info = get_spillinfo(env, to_spill);
-
- /* add the remat information */
- reloader = obstack_alloc(&env->obst, sizeof(reloader[0]));
- reloader->next = spill_info->reloaders;
- reloader->reloader = before;
- reloader->rematted_node = rematted_node;
- reloader->remat_cost_delta = 0; /* We will never have a cost win over a
- reload since we're not even allowed to
- create a reload */
-
- spill_info->reloaders = reloader;
-
- DBG((dbg, LEVEL_1, "creating spillinfo for %+F, will be rematerialized before %+F\n",
- to_spill, before));
-}
-
-void be_add_reload2(spill_env_t *env, ir_node *to_spill, ir_node *before,
- ir_node *can_spill_after, const arch_register_class_t *reload_cls,
- int allow_remat)
-{
- spill_info_t *info;
- reloader_t *rel;
-
- assert(! arch_irn_is(env->arch_env, to_spill, dont_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);
- }
- }
-
- assert(!is_Proj(before) && !be_is_Keep(before));