-/** vim: set sw=4 ts=4:
- * @file bespillremat.c
- * @date 2006-04-06
- * @author Adam M. Szalkowski & Sebastian Hack
+/*
+ * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
*
- * ILP based spilling & rematerialization
+ * This file is part of libFirm.
*
- * Copyright (C) 2006 Universitaet Karlsruhe
- * Released under the GPL
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
+/**
+ * @file
+ * @brief ILP based spilling & rematerialization
+ * @author Adam M. Szalkowski
+ * @date 06.04.2006
+ * @version $Id$
*/
#ifdef HAVE_CONFIG_H
#include "config.h"
#include "irnode_t.h"
#include "ircons_t.h"
#include "irloop_t.h"
-#include "phiclass_t.h"
-#include "iredges.h"
+#include "irnodeset.h"
+#include "phiclass.h"
+#include "iredges_t.h"
#include "execfreq.h"
#include "irvrfy.h"
#include "irbackedge_t.h"
#include <lpp/mps.h>
#include <lpp/lpp_net.h>
#include <lpp/lpp_cplex.h>
-//#include <lc_pset.h>
-//#include <libcore/lc_bitset.h>
#include "be_t.h"
+#include "beirg_t.h"
#include "belive_t.h"
#include "besched_t.h"
-#include "beirgmod.h"
-#include "bearch.h"
+#include "bessaconstr.h"
+#include "bearch_t.h"
+#include "beintlive_t.h"
#include "beabi.h"
#include "benode_t.h"
#include "beutil.h"
#include "bepressurestat.h"
#include "beprofile.h"
#include "bespilloptions.h"
-
#include "bechordal_t.h"
+#include "bemodule.h"
-#ifdef WITH_LIBCORE
#include <libcore/lc_opts.h>
#include <libcore/lc_opts_enum.h>
-#endif /* WITH_LIBCORE */
#define DUMP_PROBLEM 1
#define DUMP_MPS 2
#define REMATS_NOINVERSE 2
#define REMATS_ALL 3
-static int opt_dump_flags = 0;
+static unsigned opt_dump_flags = 0;
static int opt_log = 0;
-static int opt_keep_alive = 0;
+static unsigned opt_keep_alive = 0;
static int opt_goodwin = 1;
static int opt_memcopies = 1;
static int opt_memoperands = 1;
static int opt_verify = VERIFY_MEMINTERF;
-static int opt_remats = REMATS_ALL;
+static unsigned opt_remats = REMATS_ALL;
static int opt_repair_schedule = 0;
static int opt_no_enlarge_liveness = 0;
static int opt_remat_while_live = 1;
static double opt_cost_remat = 1.0;
-#ifdef WITH_LIBCORE
static const lc_opt_enum_mask_items_t dump_items[] = {
{ "problem", DUMP_PROBLEM },
{ "mps", DUMP_MPS },
LC_OPT_ENT_DBL ("cost_memoperand", "cost of a memory operand", &opt_cost_memoperand),
LC_OPT_ENT_DBL ("cost_spill", "cost of a spill instruction", &opt_cost_spill),
LC_OPT_ENT_DBL ("cost_remat", "cost of a rematerialization", &opt_cost_remat),
- { NULL }
+ LC_OPT_LAST
};
-#endif
-
-
//#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */
//#define SCHEDULE_PHIM /* insert phim nodes into schedule */
typedef struct _spill_ilp_t {
const arch_register_class_t *cls;
int n_regs;
- const be_chordal_env_t *chordal_env;
+ be_irg_t *birg;
be_lv_t *lv;
lpp_t *lpp;
struct obstack *obst;
set *interferences;
ir_node *m_unknown;
set *memoperands;
+ phi_classes_t *pc;
#ifndef SCHEDULE_PHIM
pset *phims;
#endif
static INLINE int
has_reg_class(const spill_ilp_t * si, const ir_node * irn)
{
- return chordal_has_class(si->chordal_env, irn);
+ return arch_irn_consider_in_reg_alloc(si->birg->main_env->arch_env,
+ si->cls, irn);
}
#if 0
cmp_remat(const void *a, const void *b)
{
const remat_t *r = a;
- const remat_t *s = a;
+ const remat_t *s = b;
return !(r == s || r->op == s->op);
}
{
const spill_t *p = a;
const spill_t *q = b;
+ (void) size;
// return !(p->irn == q->irn && p->bb == q->bb);
return !(p->irn == q->irn);
{
const memoperand_t *p = a;
const memoperand_t *q = b;
+ (void) size;
return !(p->irn == q->irn && p->pos == q->pos);
}
{
const remat_info_t *p = a;
const remat_info_t *q = b;
+ (void) size;
return !(p->irn == q->irn);
}
{
const defs_t *p = a;
const defs_t *q = b;
+ (void) size;
return !(p->value == q->value);
}
{
const keyval_t *p = a;
const keyval_t *q = b;
+ (void) size;
return !(p->key == q->key);
}
return ((double)be_profile_get_block_execcount(get_block(irn))) + FUDGE;
#ifndef EXECFREQ_LOOPDEPH
- return get_block_execfreq(si->chordal_env->birg->exec_freq, get_block(irn)) + FUDGE;
+ return get_block_execfreq(si->birg->exec_freq, get_block(irn)) + FUDGE;
#else
if(is_Block(irn))
return exp(get_loop_depth(get_irn_loop(irn)) * log(10)) + FUDGE;
} else if(be_is_Reload(irn)){
return opt_cost_reload;
} else {
- return arch_get_op_estimated_cost(si->chordal_env->birg->main_env->arch_env, irn);
+ return arch_get_op_estimated_cost(si->birg->main_env->arch_env, irn);
}
}
is_rematerializable(const spill_ilp_t * si, const ir_node * irn)
{
int n;
- const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
+ const arch_env_t *arch_env = si->birg->main_env->arch_env;
int remat = (arch_irn_get_flags(arch_env, irn) & arch_irn_flags_rematerializable) != 0;
#if 0
DBG((si->dbg, LEVEL_5, "\t requesting inverse op for argument %d of op %+F\n", n, op));
/* else ask the backend to give an inverse op */
- if(arch_get_inverse(si->chordal_env->birg->main_env->arch_env, op, n, &inverse, si->obst)) {
+ if(arch_get_inverse(si->birg->main_env->arch_env, op, n, &inverse, si->obst)) {
int i;
DBG((si->dbg, LEVEL_4, "\t backend gave us an inverse op with %d nodes and cost %d\n", inverse.n, inverse.costs));
remat->proj = (inverse.n==2)?inverse.nodes[1]:NULL;
remat->inverse = 1;
- assert(is_Proj(remat->proj));
+ // Matze: commented this out, this doesn't seem to be true if
+ // the inverse is a simple operation with only 1 result...
+ //assert(is_Proj(remat->proj));
} else {
assert(0 && "I can not handle remats with more than 2 nodes");
}
ir_node *block;
ir_node *def_block = get_nodes_block(val);
int ret;
+ (void) si;
if(val == pos)
return 0;
static INLINE ir_node *
sched_block_last_noncf(const spill_ilp_t * si, const ir_node * bb)
{
- return sched_skip((ir_node*)bb, 0, sched_skip_cf_predicator, (void *) si->chordal_env->birg->main_env->arch_env);
+ return sched_skip((ir_node*)bb, 0, sched_skip_cf_predicator, (void *) si->birg->main_env->arch_env);
}
/**
static int
sched_skip_proj_predicator(const ir_node * irn, void * data)
{
+ (void) data;
return (is_Proj(irn));
}
} else {
insert = sched_next_op(insert);
}
+ sched_reset(irn);
sched_add_before(insert, irn);
}
insert = sched_next_nonproj(insert, 0);
insert = sched_prev(insert);
}
+ sched_reset(irn);
sched_add_after(insert, irn);
}
bb = is_Block(pos)?pos:get_nodes_block(pos);
copy = exact_copy(irn);
- _set_phi_class(copy, NULL);
+ set_phi_class(si->pc, copy, NULL);
set_nodes_block(copy, bb);
sched_put_before(si, pos, copy);
bb = is_Block(pos)?pos:get_nodes_block(pos);
copy = exact_copy(irn);
- _set_phi_class(copy, NULL);
+ set_phi_class(si->pc, copy, NULL);
set_nodes_block(copy, bb);
sched_put_after(pos, copy);
sched_foreach_reverse(bb, irn) {
int i;
- if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break;
+ if(!sched_skip_cf_predicator(irn, si->birg->main_env->arch_env)) break;
for(i=get_irn_arity(irn)-1; i>=0; --i) {
ir_node *arg = get_irn_n(irn,i);
ir_node *bb = get_Block_cfgpred_block(get_nodes_block(irn), n);
if(!has_reg_class(si, phi_arg)) {
- ir_node *copy = be_new_Copy(si->cls, si->chordal_env->irg, bb, phi_arg);
+ ir_node *copy = be_new_Copy(si->cls, si->birg->irg, bb, phi_arg);
ir_node *pos = sched_block_last_noncf(si, bb);
op_t *op = obstack_alloc(si->obst, sizeof(*op));
}
/* do not place post remats after jumps */
- if(sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) {
+ if(sched_skip_cf_predicator(irn, si->birg->main_env->arch_env)) {
del_pset(used);
del_pset(args);
break;
sched_foreach_reverse(bb, irn) {
int n;
- if(!sched_skip_cf_predicator(irn, si->chordal_env->birg->main_env->arch_env)) break;
+ if(!sched_skip_cf_predicator(irn, si->birg->main_env->arch_env)) break;
for (n=get_irn_arity(irn)-1; n>=0; --n) {
ir_node *irn_arg = get_irn_n(irn, n);
del_pset(use_end);
}
+#ifndef NDEBUG
/**
* Find a remat of value @p value in the epilog of @p pos
*/
return NULL;
}
+#endif
static spill_t *
add_to_spill_bb(spill_ilp_t * si, ir_node * bb, ir_node * irn)
ir_node *tmp;
spill_t *spill;
pset *defs = pset_new_ptr_default();
- const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
+ const arch_env_t *arch_env = si->birg->main_env->arch_env;
live = pset_new_ptr_default();
pset *used;
pset *remat_defs;
keyval_t *keyval;
- ilp_cst_t one_memoperand;
+ ilp_cst_t one_memoperand = -1;
/* iterate only until first phi */
if(is_Phi(irn))
assert(has_reg_class(si, tmp));
}
+#ifndef NDEBUG
for (n=get_irn_arity(irn)-1; n>=0; --n) {
ir_node *arg = get_irn_n(irn, n);
assert(!find_post_remat(arg, irn) && "there should be no post remat for an argument of an op");
}
+#endif
del_pset(remat_defs);
del_pset(used);
{
const interference_t *p = a;
const interference_t *q = b;
+ (void) size;
return !(p->a == q->a && p->b == q->b);
}
return result;
}
-static int
-values_interfere_in_block(const spill_ilp_t * si, const ir_node * bb, const ir_node * a, const ir_node * b)
+static
+int values_interfere_in_block(const spill_ilp_t *si, const ir_node *bb, const ir_node *a, const ir_node *b)
{
const ir_edge_t *edge;
- if(get_nodes_block(a) != bb && get_nodes_block(b) != bb) {
+ if (get_nodes_block(a) != bb && get_nodes_block(b) != bb) {
/* both values are live in, so they interfere */
return 1;
}
/* ensure a dominates b */
- if(value_dominates(b,a)) {
- const ir_node * t;
+ if (value_dominates(b, a)) {
+ const ir_node *t;
t = b;
b = a;
a = t;
/* the following code is stolen from bera.c */
- if(be_is_live_end(si->lv, bb, a))
+ if (be_is_live_end(si->lv, bb, a))
return 1;
foreach_out_edge(a, edge) {
const ir_node *user = edge->src;
- if(get_nodes_block(user) == bb
- && !is_Phi(user)
+ if (get_nodes_block(user) == bb
+ && ! is_Phi(user)
&& b != user
- && !pset_find_ptr(si->inverse_ops, user)
+ && ! pset_find_ptr(si->inverse_ops, user)
&& value_dominates(b, user))
return 1;
}
/* a is only interesting if it is in my register class and if it is inside a phi class */
- if (has_reg_class(si, a) && get_phi_class(a)) {
- if(a_op->is_remat || pset_find_ptr(si->inverse_ops, a))
+ if (has_reg_class(si, a) && get_phi_class(si->pc, a)) {
+ if (a_op->is_remat || pset_find_ptr(si->inverse_ops, a))
continue;
- for(l2=_be_lv_next_irn(si->lv, bb, 0xff, l1+1); l2>=0; l2=_be_lv_next_irn(si->lv, bb, 0xff, l2+1)) {
- ir_node *b = be_lv_get_irn(si->lv, bb, l2);
- op_t *b_op = get_irn_link(b);
-
+ for (l2 = _be_lv_next_irn(si->lv, bb, 0xff, l1 + 1); l2 >= 0; l2 = _be_lv_next_irn(si->lv, bb, 0xff, l2 + 1)) {
+ ir_node *b = be_lv_get_irn(si->lv, bb, l2);
+ op_t *b_op = get_irn_link(b);
/* a and b are only interesting if they are in the same phi class */
- if(has_reg_class(si, b) && get_phi_class(a) == get_phi_class(b)) {
- if(b_op->is_remat || pset_find_ptr(si->inverse_ops, b))
+ if (has_reg_class(si, b) && get_phi_class(si->pc, a) == get_phi_class(si->pc, b)) {
+ if (b_op->is_remat || pset_find_ptr(si->inverse_ops, b))
continue;
- if(values_interfere_in_block(si, bb, a, b)) {
+ if (values_interfere_in_block(si, bb, a, b)) {
DBG((si->dbg, LEVEL_4, "\tvalues interfere in %+F: %+F, %+F\n", bb, a, b));
set_insert_interference(si, si->interferences, a, b, bb);
}
char buf[256];
/* teste Speicherwerte auf Interferenz */
- /* analyze phi classes */
- phi_class_compute(si->chordal_env->irg);
-
DBG((si->dbg, LEVEL_2, "\t calling interferencewalker\n"));
- irg_block_walk_graph(si->chordal_env->irg, luke_interferencewalker, NULL, si);
+ irg_block_walk_graph(si->birg->irg, luke_interferencewalker, NULL, si);
/* now lets emit the ILP unequations for the crap */
set_foreach(si->interferences, interference) {
irnlist_t *irnlist;
- ilp_var_t interfere,
- any_interfere;
- ilp_cst_t any_interfere_cst,
- cst;
+ ilp_var_t interfere, any_interfere;
+ ilp_cst_t any_interfere_cst, cst;
const ir_node *a = interference->a;
const ir_node *b = interference->b;
/* any_interf <= \sum interf */
ir_snprintf(buf, sizeof(buf), "interfere_%N_%N", a, b);
any_interfere_cst = lpp_add_cst_uniq(si->lpp, buf, lpp_less, 0);
- any_interfere = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0);
+ any_interfere = lpp_add_var_default(si->lpp, buf, lpp_binary, 0.0, 1.0);
lpp_set_factor_fast(si->lpp, any_interfere_cst, any_interfere, 1.0);
static int mark_remat_nodes_hook(FILE *F, ir_node *n, ir_node *l)
{
spill_ilp_t *si = get_irg_link(current_ir_graph);
+ (void) l;
if(pset_find_ptr(si->all_possible_remats, n)) {
op_t *op = (op_t*)get_irn_link(n);
static void
dump_pressure_graph(spill_ilp_t * si, const char *suffix)
{
- be_dump(si->chordal_env->irg, suffix, dump_ir_block_graph_sched_pressure);
+ be_dump(si->birg->irg, suffix, dump_ir_block_graph_sched_pressure);
}
static void
++pos;
}
- si->keep = be_new_Keep(si->chordal_env->cls, si->chordal_env->irg, get_irg_end_block(si->chordal_env->irg), n_remats, ins);
+ si->keep = be_new_Keep(si->cls, si->birg->irg, get_irg_end_block(si->birg->irg), n_remats, ins);
obstack_free(si->obst, ins);
}
++pos;
}
- keep = be_new_Keep(si->chordal_env->cls, si->chordal_env->irg, get_irg_end_block(si->chordal_env->irg), n_spills, ins);
+ keep = be_new_Keep(si->cls, si->birg->irg, get_irg_end_block(si->birg->irg), n_spills, ins);
obstack_free(si->obst, ins);
}
/** insert a spill at an arbitrary position */
ir_node *be_spill2(const arch_env_t *arch_env, ir_node *irn, ir_node *insert)
{
- ir_node *bl = is_Block(insert)?insert:get_nodes_block(insert);
+ ir_node *bl = is_Block(insert) ? insert : get_nodes_block(insert);
ir_graph *irg = get_irn_irg(bl);
ir_node *frame = get_irg_frame(irg);
ir_node *spill;
ir_node *next;
- const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
+ const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, irn, -1);
+ const arch_register_class_t *cls_frame = arch_get_irn_reg_class(arch_env, frame, -1);
- spill = be_new_Spill(cls, irg, bl, irn);
+ spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn);
/*
* search the right insertion point. a spill of a phi cannot be put
static void
delete_remat(spill_ilp_t * si, ir_node * remat) {
int n;
- ir_node *bad = get_irg_bad(si->chordal_env->irg);
+ ir_node *bad = get_irg_bad(si->birg->irg);
sched_remove(remat);
}
}
+/* FIXME: is this still correct:? Proj's are neither scheduled anymore nor they have a block ... */
static void
clean_remat_info(spill_ilp_t * si)
{
int n;
remat_t *remat;
remat_info_t *remat_info;
- ir_node *bad = get_irg_bad(si->chordal_env->irg);
+ ir_node *bad = get_irg_bad(si->birg->irg);
set_foreach(si->remat_info, remat_info) {
if(!remat_info->remats) continue;
{
if(opt_keep_alive & KEEPALIVE_REMATS) {
int n;
- ir_node *bad = get_irg_bad(si->chordal_env->irg);
+ ir_node *bad = get_irg_bad(si->birg->irg);
if(si->keep) {
for (n=get_irn_arity(si->keep)-1; n>=0; --n) {
{
defs_t *defs;
ir_node *spill;
- const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
+ const arch_env_t *arch_env = si->birg->main_env->arch_env;
DBG((si->dbg, LEVEL_3, "\t inserting spill for value %+F after %+F\n", irn, before));
ins[n] = si->m_unknown;
}
- mem_phi = new_r_PhiM_nokeep(si->chordal_env->irg, get_nodes_block(phi), get_irn_arity(phi), ins);
+ mem_phi = new_r_PhiM_nokeep(si->birg->irg, get_nodes_block(phi), get_irn_arity(phi), ins);
defs = set_insert_def(si->values, phi);
assert(defs);
defs_t *defs;
ir_node *reload,
*spill;
- const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
+ const arch_env_t *arch_env = si->birg->main_env->arch_env;
DBG((si->dbg, LEVEL_3, "\t inserting reload for value %+F before %+F\n", value, after));
defs_t *defs;
ir_node *value = get_irn_n(memoperand->irn, memoperand->pos);
ir_node *spill;
- const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
+ const arch_env_t *arch_env = si->birg->main_env->arch_env;
DBG((si->dbg, LEVEL_2, "\t inserting memory operand for value %+F at %+F\n", value, memoperand->irn));
{
ir_node *insert_pos = bb;
ir_node *spill;
- const arch_env_t *arch_env = si->chordal_env->birg->main_env->arch_env;
+ const arch_env_t *arch_env = si->birg->main_env->arch_env;
/* find last definition of arg value in block */
ir_node *next;
kill_unused_phims(spill_ilp_t * si, struct kill_helper * kh)
{
ir_node *phi;
- ir_node *bad = get_irg_bad(si->chordal_env->irg);
+ ir_node *bad = get_irg_bad(si->birg->irg);
int n;
pset_foreach(si->phims, phi) {
{
struct kill_helper kh;
- kh.used = bitset_malloc(get_irg_last_idx(si->chordal_env->irg));
+ kh.used = bitset_malloc(get_irg_last_idx(si->birg->irg));
kh.si = si;
- irg_walk_graph(si->chordal_env->irg, walker_collect_used, NULL, kh.used);
+ irg_walk_graph(si->birg->irg, walker_collect_used, NULL, kh.used);
#ifndef SCHEDULE_PHIM
kill_unused_phims(si, &kh);
#endif
- irg_block_walk_graph(si->chordal_env->irg, walker_kill_unused, NULL, &kh);
+ irg_block_walk_graph(si->birg->irg, walker_kill_unused, NULL, &kh);
bitset_free(kh.used);
}
}
void
-dump_phi_class(spill_ilp_t * si, pset * phiclass, const char * file)
+dump_phi_class(spill_ilp_t *si, ir_node **phiclass, const char * file)
{
FILE *f = fopen(file, "w");
ir_node *irn;
interference_t *interference;
+ int i;
- pset_break(phiclass);
set_break(si->interferences);
ir_fprintf(f, "digraph phiclass {\n");
- pset_foreach(phiclass, irn) {
- if(is_Phi(irn))
- ir_fprintf(f, " %F%N [shape=box]\n",irn,irn);
+ for (i = ARR_LEN(phiclass) - 1; i >= 0; --i) {
+ irn = phiclass[i];
+ if (is_Phi(irn))
+ ir_fprintf(f, " %F%N [shape=box]\n", irn, irn);
}
- pset_foreach(phiclass, irn) {
+ for (i = ARR_LEN(phiclass) - 1; i >= 0; --i) {
int n;
- if(!is_Phi(irn)) continue;
+ irn = phiclass[i];
+ if (! is_Phi(irn))
+ continue;
- for(n=get_irn_arity(irn)-1; n>=0; --n) {
+ for (n = get_irn_arity(irn) - 1; n >= 0; --n) {
ir_node *arg = get_irn_n(irn, n);
- ir_fprintf(f, " %F%N -> %F%N\n",irn,irn,arg,arg);
+ ir_fprintf(f, " %F%N -> %F%N\n", irn, irn, arg, arg);
}
}
set_foreach(si->interferences, interference) {
- const ir_node *a = interference->a;
- const ir_node *b = interference->b;
- if(get_phi_class(a) == phiclass) {
- ir_fprintf(f, " %F%N -> %F%N [color=red,dir=none,style=bold]\n",a,a,b,b);
+ const ir_node *a = interference->a;
+ const ir_node *b = interference->b;
+ if (get_phi_class(si->pc, (ir_node *)a) == phiclass) {
+ ir_fprintf(f, " %F%N -> %F%N [color=red,dir=none,style=bold]\n", a, a, b, b);
}
}
rewire_uses(spill_ilp_t * si)
{
defs_t *defs;
- pset *ignore = pset_new_ptr(1);
- be_dom_front_info_t *dom_front = si->chordal_env->birg->dom_front;
+ ir_nodeset_t ignore;
- pset_insert_ptr(ignore, get_irg_end(si->chordal_env->irg));
+ ir_nodeset_init(&ignore);
+ ir_nodeset_insert(&ignore, get_irg_end(si->birg->irg));
/* then fix uses of spills */
set_foreach(si->values, defs) {
spills = get_spills_for_value(si, defs->value);
DBG((si->dbg, LEVEL_2, "\t %d remats, %d reloads, and %d spills for value %+F\n", remats, pset_count(reloads), pset_count(spills), defs->value));
if(pset_count(spills) > 1) {
+ be_ssa_construction_env_t senv;
+ ir_node *node;
//assert(pset_count(reloads) > 0);
// print_irn_pset(spills);
// print_irn_pset(reloads);
- be_ssa_constr_set_ignore(dom_front, si->lv, spills, ignore);
+ be_ssa_construction_init(&senv, si->birg);
+ be_ssa_construction_set_ignore_uses(&senv, &ignore);
+ pset_foreach(spills, node) {
+ be_ssa_construction_add_copy(&senv, node);
+ }
+ pset_foreach(spills, node) {
+ be_ssa_construction_fix_users(&senv, node);
+ }
+ be_ssa_construction_update_liveness_phis(&senv, si->lv);
+ pset_foreach(spills, node) {
+ be_liveness_update(si->lv, node);
+ }
+ be_ssa_construction_destroy(&senv);
}
del_pset(reloads);
/* first fix uses of remats and reloads */
set_foreach(si->values, defs) {
- pset *nodes;
const ir_node *next = defs->remats;
int orig_kept = 0;
if(next) {
- nodes = pset_new_ptr_default();
+ be_ssa_construction_env_t senv;
+
+ be_ssa_construction_init(&senv, si->birg);
+
if(sched_is_scheduled(defs->value)) {
- pset_insert_ptr(nodes, defs->value);
+ be_ssa_construction_add_copy(&senv, (ir_node*) defs->value);
orig_kept = 1;
}
+ next = defs->remats;
while(next) {
- pset_insert_ptr(nodes, next);
+ be_ssa_construction_add_copy(&senv, (ir_node*) next);
next = get_irn_link(next);
}
- DBG((si->dbg, LEVEL_4, "\t %d new definitions for value %+F\n", pset_count(nodes)-orig_kept, defs->value));
- be_ssa_constr_set(dom_front, si->lv, nodes);
+ if(sched_is_scheduled(defs->value)) {
+ be_ssa_construction_fix_users(&senv, (ir_node*) defs->value);
+ }
+
+ next = defs->remats;
+ while(next) {
+ be_ssa_construction_fix_users(&senv, (ir_node*) next);
+ next = get_irn_link(next);
+ }
+
+ be_ssa_construction_update_liveness_phis(&senv, si->lv);
+ if(sched_is_scheduled(defs->value)) {
+ be_liveness_update(si->lv, (ir_node*) defs->value);
+ }
+
+ next = defs->remats;
+ while(next) {
+ be_liveness_update(si->lv, (ir_node*) next);
+ next = get_irn_link(next);
+ }
- del_pset(nodes);
+ be_ssa_construction_destroy(&senv);
}
}
+ ir_nodeset_destroy(&ignore);
// remove_unused_defs(si);
}
DBG((si->dbg, LEVEL_1, "Applying results\n"));
delete_unnecessary_remats(si);
- si->m_unknown = new_r_Unknown(si->chordal_env->irg, mode_M);
- irg_block_walk_graph(si->chordal_env->irg, walker_spill_placer, NULL, si);
- irg_block_walk_graph(si->chordal_env->irg, walker_reload_placer, NULL, si);
+ si->m_unknown = new_r_Unknown(si->birg->irg, mode_M);
+ irg_block_walk_graph(si->birg->irg, walker_spill_placer, NULL, si);
+ irg_block_walk_graph(si->birg->irg, walker_reload_placer, NULL, si);
if(opt_memoperands)
insert_memoperands(si);
phim_fixer(si);
bitset_t *arch_regs = bitset_malloc(arch_n_regs);
bitset_t *abi_regs = bitset_malloc(arch_n_regs);
- arch_put_non_ignore_regs(si->chordal_env->birg->main_env->arch_env, si->cls, arch_regs);
- be_abi_put_ignore_regs(si->chordal_env->birg->abi, si->cls, abi_regs);
+ arch_put_non_ignore_regs(si->birg->main_env->arch_env, si->cls, arch_regs);
+ be_abi_put_ignore_regs(si->birg->abi, si->cls, abi_regs);
bitset_andnot(arch_regs, abi_regs);
arch_n_regs = bitset_popcnt(arch_regs);
static void
move_reloads_upward(spill_ilp_t * si)
{
- irg_block_walk_graph(si->chordal_env->irg, walker_reload_mover, NULL, si);
+ irg_block_walk_graph(si->birg->irg, walker_reload_mover, NULL, si);
}
static void
luke_meminterferencechecker(ir_node * bb, void * data)
{
- spill_ilp_t *si = (spill_ilp_t*)data;
- int l1, l2;
+ spill_ilp_t *si = (spill_ilp_t*)data;
+ int l1, l2;
be_lv_foreach(si->lv, bb, be_lv_state_end | be_lv_state_out | be_lv_state_in, l1) {
ir_node *a = be_lv_get_irn(si->lv, bb, l1);
- if(!be_is_Spill(a) && (!is_Phi(a) || get_irn_mode(a) != mode_T)) continue;
+ if (! be_is_Spill(a) && (!is_Phi(a) || get_irn_mode(a) != mode_T))
+ continue;
/* a is only interesting if it is in my register class and if it is inside a phi class */
- if (has_reg_class(si, a) && get_phi_class(a)) {
- for(l2=_be_lv_next_irn(si->lv, bb, 0xff, l1+1); l2>=0; l2=_be_lv_next_irn(si->lv, bb, 0xff, l2+1)) {
- ir_node *b = be_lv_get_irn(si->lv, bb, l2);
+ if (has_reg_class(si, a) && get_phi_class(si->pc, a)) {
+ for (l2 = _be_lv_next_irn(si->lv, bb, 0xff, l1 + 1); l2 >= 0; l2 = _be_lv_next_irn(si->lv, bb, 0xff, l2 + 1)) {
+ ir_node *b = be_lv_get_irn(si->lv, bb, l2);
- if(!be_is_Spill(b) && (!is_Phi(b) || get_irn_mode(b) != mode_T)) continue;
+ if (! be_is_Spill(b) && (! is_Phi(b) || get_irn_mode(b) != mode_T))
+ continue;
/* a and b are only interesting if they are in the same phi class */
- if(has_reg_class(si, b) && get_phi_class(a) == get_phi_class(b)) {
- if(values_interfere_in_block(si, bb, a, b)) {
+ if (has_reg_class(si, b) && get_phi_class(si->pc, a) == get_phi_class(si->pc, b)) {
+ if (values_interfere_in_block(si, bb, a, b)) {
ir_fprintf(stderr, "$$ Spills interfere in %+F: %+F, %+F \t$$\n", bb, a, b);
}
}
verify_phiclasses(spill_ilp_t * si)
{
/* analyze phi classes */
- phi_class_compute(si->chordal_env->irg);
+ phi_class_free(si->pc);
+ si->pc = phi_class_new_from_irg(si->birg->irg, 0);
DBG((si->dbg, LEVEL_2, "\t calling memory interference checker\n"));
- irg_block_walk_graph(si->chordal_env->irg, luke_meminterferencechecker, NULL, si);
+ irg_block_walk_graph(si->birg->irg, luke_meminterferencechecker, NULL, si);
}
void
-be_spill_remat(const be_chordal_env_t * chordal_env)
+be_spill_remat(be_irg_t *birg, const arch_register_class_t *cls)
{
char buf[256];
char problem_name[256];
char dump_suffix2[256];
struct obstack obst;
spill_ilp_t si;
- be_irg_t *birg = chordal_env->birg;
+ ir_graph *irg = be_get_birg_irg(birg);
- ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", chordal_env->irg, chordal_env->cls->name);
- ir_snprintf(dump_suffix, sizeof(dump_suffix), "-%s-remats", chordal_env->cls->name);
- ir_snprintf(dump_suffix2, sizeof(dump_suffix2), "-%s-pressure", chordal_env->cls->name);
+ ir_snprintf(problem_name, sizeof(problem_name), "%F_%s", irg, cls->name);
+ ir_snprintf(dump_suffix, sizeof(dump_suffix), "-%s-remats", cls->name);
+ ir_snprintf(dump_suffix2, sizeof(dump_suffix2), "-%s-pressure", cls->name);
FIRM_DBG_REGISTER(si.dbg, "firm.be.ra.spillremat");
DBG((si.dbg, LEVEL_1, "\n\n\t\t===== Processing %s =====\n\n", problem_name));
if(opt_verify & VERIFY_DOMINANCE)
- be_check_dominance(chordal_env->irg);
+ be_check_dominance(irg);
be_assure_dom_front(birg);
be_assure_liveness(birg);
obstack_init(&obst);
- si.chordal_env = chordal_env;
- si.obst = &obst;
- si.cls = chordal_env->cls;
- si.lpp = new_lpp(problem_name, lpp_minimize);
- si.remat_info = new_set(cmp_remat_info, 4096);
- si.interferences = new_set(cmp_interference, 32);
- si.memoperands = new_set(cmp_memoperands, 128);
+ si.obst = &obst;
+ si.birg = birg;
+ si.cls = cls;
+ si.lpp = new_lpp(problem_name, lpp_minimize);
+ si.remat_info = new_set(cmp_remat_info, 4096);
+ si.interferences = new_set(cmp_interference, 32);
+ si.memoperands = new_set(cmp_memoperands, 128);
si.all_possible_remats = pset_new_ptr_default();
- si.spills = pset_new_ptr_default();
- si.inverse_ops = pset_new_ptr_default();
- si.lv = birg->lv;
- si.keep = NULL;
- si.n_regs = get_n_regs(&si);
+ si.spills = pset_new_ptr_default();
+ si.inverse_ops = pset_new_ptr_default();
+ si.lv = birg->lv;
+ si.keep = NULL;
+ si.n_regs = get_n_regs(&si);
- set_irg_link(chordal_env->irg, &si);
- compute_doms(chordal_env->irg);
+ set_irg_link(irg, &si);
+ compute_doms(irg);
/* compute phi classes */
-// phi_class_compute(chordal_env->irg);
+ // phi_class_compute(irg);
if(opt_dump_flags & DUMP_STATS)
- be_analyze_regpressure(chordal_env, "-pre");
+ be_analyze_regpressure(birg, cls, "-pre");
DBG((si.dbg, LEVEL_2, "\t initializing\n"));
- irg_block_walk_graph(chordal_env->irg, luke_initializer, NULL, &si);
+ irg_block_walk_graph(irg, luke_initializer, NULL, &si);
if(opt_remats) {
/* collect remats */
DBG((si.dbg, LEVEL_1, "Collecting remats\n"));
- irg_walk_graph(chordal_env->irg, walker_remat_collector, NULL, &si);
+ irg_walk_graph(irg, walker_remat_collector, NULL, &si);
}
/* insert possible remats */
DBG((si.dbg, LEVEL_1, "Inserting possible remats\n"));
- irg_block_walk_graph(chordal_env->irg, walker_remat_insertor, NULL, &si);
+ irg_block_walk_graph(irg, walker_remat_insertor, NULL, &si);
DBG((si.dbg, LEVEL_2, " -> inserted %d possible remats\n", pset_count(si.all_possible_remats)));
if(opt_keep_alive & KEEPALIVE_REMATS) {
DBG((si.dbg, LEVEL_1, "Connecting remats with keep and dumping\n"));
connect_all_remats_with_keep(&si);
/* dump graph with inserted remats */
- dump_graph_with_remats(chordal_env->irg, dump_suffix);
+ dump_graph_with_remats(irg, dump_suffix);
}
/* insert copies for phi arguments not in my regclass */
- irg_walk_graph(chordal_env->irg, walker_regclass_copy_insertor, NULL, &si);
+ irg_walk_graph(irg, walker_regclass_copy_insertor, NULL, &si);
/* recompute liveness */
DBG((si.dbg, LEVEL_1, "Recomputing liveness\n"));
/* build the ILP */
DBG((si.dbg, LEVEL_1, "\tBuilding ILP\n"));
DBG((si.dbg, LEVEL_2, "\t endwalker\n"));
- irg_block_walk_graph(chordal_env->irg, luke_endwalker, NULL, &si);
+ irg_block_walk_graph(irg, luke_endwalker, NULL, &si);
DBG((si.dbg, LEVEL_2, "\t blockwalker\n"));
- irg_block_walk_graph(chordal_env->irg, luke_blockwalker, NULL, &si);
+ irg_block_walk_graph(irg, luke_blockwalker, NULL, &si);
- if(opt_memcopies) {
+ si.pc = phi_class_new_from_irg(birg->irg, 0);
+ if (opt_memcopies) {
DBG((si.dbg, LEVEL_2, "\t memcopyhandler\n"));
memcopyhandler(&si);
}
- if(opt_dump_flags & DUMP_PROBLEM) {
+ if (opt_dump_flags & DUMP_PROBLEM) {
FILE *f;
ir_snprintf(buf, sizeof(buf), "%s-spillremat.ilp", problem_name);
if ((f = fopen(buf, "wt")) != NULL) {
}
}
- if(opt_dump_flags & DUMP_MPS) {
+ if (opt_dump_flags & DUMP_MPS) {
FILE *f;
ir_snprintf(buf, sizeof(buf), "%s-spillremat.mps", problem_name);
- if((f = fopen(buf, "wt")) != NULL) {
+ if ((f = fopen(buf, "wt")) != NULL) {
mps_write_mps(si.lpp, s_mps_fixed, f);
fclose(f);
}
ir_snprintf(buf, sizeof(buf), "%s-spillremat.mst", problem_name);
- if((f = fopen(buf, "wt")) != NULL) {
+ if ((f = fopen(buf, "wt")) != NULL) {
mps_write_mst(si.lpp, s_mps_fixed, f);
fclose(f);
}
#endif
if(opt_keep_alive & (KEEPALIVE_SPILLS | KEEPALIVE_RELOADS))
- be_dump(chordal_env->irg, "-spills-placed", dump_ir_block_graph);
+ be_dump(irg, "-spills-placed", dump_ir_block_graph);
// move reloads upwards
be_liveness_recompute(si.lv);
- irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si);
+ irg_block_walk_graph(irg, walker_pressure_annotator, NULL, &si);
move_reloads_upward(&si);
if(opt_memcopies) {
verify_phiclasses(&si);
}
- irg_block_walk_graph(chordal_env->irg, walker_pressure_annotator, NULL, &si);
+ irg_block_walk_graph(irg, walker_pressure_annotator, NULL, &si);
if(opt_dump_flags & DUMP_PRESSURE)
dump_pressure_graph(&si, dump_suffix2);
if(opt_dump_flags & DUMP_STATS)
- be_analyze_regpressure(chordal_env, "-post");
+ be_analyze_regpressure(birg, cls, "-post");
if(opt_verify & VERIFY_DOMINANCE)
- be_check_dominance(chordal_env->irg);
+ be_check_dominance(irg);
- free_dom(chordal_env->irg);
+ free_dom(irg);
del_set(si.interferences);
del_pset(si.inverse_ops);
del_pset(si.all_possible_remats);
del_set(si.memoperands);
del_pset(si.spills);
free_lpp(si.lpp);
+ phi_class_free(si.pc);
obstack_free(&obst, NULL);
DBG((si.dbg, LEVEL_1, "\tdone.\n"));
}
projects / libfirm / blobdiff