#include "bechordal_t.h"
-#define BIGM 100000.0
-
-#define DUMP_SOLUTION
-#define DUMP_ILP
+//#define DUMP_SOLUTION
+//#define DUMP_ILP
//#define KEEPALIVE /* keep alive all inserted remats and dump graph with remats */
#define COLLECT_REMATS /* enable rematerialization */
#define COLLECT_INVERSE_REMATS /* enable placement of inverse remats */
+//#define ONLY_BRIGGS_REMATS /* only remats without parameters (or only with ignored params) */
#define REMAT_WHILE_LIVE /* only remat values that are live */
//#define NO_ENLARGE_L1V3N355 /* do not remat after the death of some operand */
//#define EXECFREQ_LOOPDEPH /* compute execution frequency from loop depth only */
typedef struct _remat_t {
const ir_node *op; /**< for copy_irn */
const ir_node *value; /**< the value which is being recomputed by this remat */
- ir_node *proj; /**< not NULL if the above op produces a tuple */
+ const ir_node *proj; /**< not NULL if the above op produces a tuple */
int cost; /**< cost of this remat */
int inverse; /**< nonzero if this is an inverse remat */
} remat_t;
union {
struct {
ilp_var_t ilp;
- remat_t *remat; /** the remat this op belongs to */
+ const remat_t *remat; /** the remat this op belongs to */
int pre; /** 1, if this is a pressure-increasing remat */
} remat;
struct {
} op_t;
typedef struct _defs_t {
- ir_node *value;
- ir_node *spills; /**< points to the first spill for this value (linked by link field) */
- ir_node *remats; /**< points to the first definition for this value (linked by link field) */
+ const ir_node *value;
+ ir_node *spills; /**< points to the first spill for this value (linked by link field) */
+ ir_node *remats; /**< points to the first definition for this value (linked by link field) */
} defs_t;
typedef struct _remat_info_t {
} keyval_t;
typedef struct _spill_t {
- ir_node *irn;
- ilp_var_t reg_in;
- ilp_var_t mem_in;
- ilp_var_t reg_out;
- ilp_var_t mem_out;
- ilp_var_t spill;
+ ir_node *irn;
+ ilp_var_t reg_in;
+ ilp_var_t mem_in;
+ ilp_var_t reg_out;
+ ilp_var_t mem_out;
+ ilp_var_t spill;
} spill_t;
#ifdef WITH_MEMOPERANDS
typedef struct _memoperand_t {
- const ir_node *irn; /**< the irn */
+ ir_node *irn; /**< the irn */
unsigned int pos; /**< the position of the argument */
ilp_var_t ilp; /**< the ilp var for this memory operand */
} memoperand_t;
#endif
static keyval_t *
-set_find_keyval(set * set, void * key)
+set_find_keyval(set * set, const void * key)
{
keyval_t query;
}
static defs_t *
-set_find_def(set * set, ir_node * value)
+set_find_def(set * set, const ir_node * value)
{
defs_t query;
}
static defs_t *
-set_insert_def(set * set, ir_node * value)
+set_insert_def(set * set, const ir_node * value)
{
defs_t query;
}
static memoperand_t *
-set_find_memoperand(set * set, ir_node * irn, unsigned int pos)
+set_find_memoperand(set * set, const ir_node * irn, unsigned int pos)
{
memoperand_t query;
- query.irn = irn;
+ query.irn = (ir_node*)irn;
query.pos = pos;
return set_find(set, &query, sizeof(query), HASH_PTR(irn)+pos);
}
static spill_t *
-set_find_spill(set * set, ir_node * value)
+set_find_spill(set * set, const ir_node * value)
{
spill_t query;
- query.irn = value;
+ query.irn = (ir_node*)value;
return set_find(set, &query, sizeof(query), HASH_PTR(value));
}
}
}
+#ifdef NO_SINGLE_USE_REMATS
static int
get_irn_n_nonremat_edges(const spill_ilp_t * si, const ir_node * irn)
{
return i;
}
+#endif
+
+#ifdef ONLY_BRIGGS_REMATS
+static int
+get_irn_n_nonignore_args(const spill_ilp_t * si, const ir_node * irn)
+{
+ int n;
+ unsigned int ret = 0;
+
+ for(n=get_irn_arity(irn)-1; n>=0; --n) {
+ if(has_reg_class(si, irn)) ++ret;
+ }
+
+ return ret;
+}
+#endif
static INLINE void
get_remats_from_op(spill_ilp_t * si, const ir_node * op)
int n;
remat_t *remat;
+ if( has_reg_class(si, op)
#ifdef NO_SINGLE_USE_REMATS
- if(has_reg_class(si, op) && (get_irn_n_nonremat_edges(si, op) > 1)) {
-#else
- if(has_reg_class(si, op)) {
+ && (get_irn_n_nonremat_edges(si, op) > 1)
+#endif
+#ifdef ONLY_BRIGGS_REMATS
+ && (get_irn_n_nonignore_args(si, op) == 0)
#endif
+ ) {
remat = get_remat_from_op(si, op, op);
if(remat) {
add_remat(si, remat);
}
}
-#ifdef COLLECT_INVERSE_REMATS
+#if defined(COLLECT_INVERSE_REMATS) && !defined(ONLY_BRIGGS_REMATS)
/* repeat the whole stuff for each remat retrieved by get_remat_from_op(op, arg)
for each arg */
for (n = get_irn_arity(op)-1; n>=0; --n) {
}
static ir_node *
-insert_remat_after(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
+insert_remat_after(spill_ilp_t * si, const remat_t * remat, ir_node * pos, const pset * live)
{
char buf[256];
}
static ir_node *
-insert_remat_before(spill_ilp_t * si, const remat_t * remat, const ir_node * pos, const pset * live)
+insert_remat_before(spill_ilp_t * si, const remat_t * remat, ir_node * pos, const pset * live)
{
char buf[256];
next_post_remat(const ir_node * irn)
{
op_t *op;
+ ir_node *next;
if(is_Block(irn)) {
- irn = sched_block_first_nonphi(irn);
+ next = sched_block_first_nonphi(irn);
} else {
- irn = sched_next_op(irn);
+ next = sched_next_op(irn);
}
- if(sched_is_end(irn))
+ if(sched_is_end(next))
return NULL;
- op = (op_t*)get_irn_link(irn);
+ op = get_irn_link(next);
if(op->is_remat && !op->attr.remat.pre) {
- return irn;
+ return next;
}
return NULL;
set_foreach(args, keyval) {
spill_t *spill;
- ir_node *arg = keyval->key;
+ const ir_node *arg = keyval->key;
int i = PTR_TO_INT(keyval->val);
op_t *arg_op = get_irn_link(arg);
ilp_cst_t requirements;
for (n=get_irn_arity(tmp)-1; n>=0; --n) {
ir_node *remat_arg = get_irn_n(tmp, n);
op_t *arg_op = get_irn_link(remat_arg);
- ilp_var_t prev_lr;
if(!has_reg_class(si, remat_arg)) continue;
assert(!is_Proj(tmp));
if(op->is_remat) {
- ir_node *value = op->attr.remat.remat->value;
+ const ir_node *value = op->attr.remat.remat->value;
if(value == irn) {
/* only collect remats up to the first real use of a value */
}
}
}
- /* if the semicolon is missing, the microsoft compiler complains */
next_live: ;
}
}
static int
-values_interfere_in_block(const spill_ilp_t * si, ir_node * bb, ir_node * a, ir_node * b)
+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;
* @parameter visited contains a set of nodes already visited on this path
*/
static int
-find_copy_path(spill_ilp_t * si, ir_node * irn, ir_node * target, ilp_var_t any_interfere, pset * copies, pset * visited)
+find_copy_path(spill_ilp_t * si, const ir_node * irn, const ir_node * target, ilp_var_t any_interfere, pset * copies, pset * visited)
{
- ir_edge_t *edge;
- op_t *op = get_irn_link(irn);
- pset *visited_users = pset_new_ptr_default();
- int paths = 0;
+ const ir_edge_t *edge;
+ op_t *op = get_irn_link(irn);
+ pset *visited_users = pset_new_ptr_default();
+ int paths = 0;
- if(op->is_remat) return;
+ if(op->is_remat) return 0;
pset_insert_ptr(visited, irn);
}
static void
-gen_copy_constraints(spill_ilp_t * si, ir_node * a, ir_node * b, ilp_var_t any_interfere)
+gen_copy_constraints(spill_ilp_t * si, const ir_node * a, const ir_node * b, ilp_var_t any_interfere)
{
pset * copies = pset_new_ptr_default();
pset * visited = pset_new_ptr_default();
const ir_node *bb = irnlist->irn;
spill_bb_t *spill_bb = get_irn_link(bb);
spill_t *spilla,
- *spillb,
- query;
+ *spillb;
char buf[256];
- query.irn = a;
spilla = set_find_spill(spill_bb->ilp, a);
assert(spilla);
- query.irn = b;
spillb = set_find_spill(spill_bb->ilp, b);
assert(spillb);
}
/** 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 *ctx)
+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_graph *irg = get_irn_irg(bl);
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, cls_frame, irg, bl, frame, irn, ctx);
+ spill = be_new_Spill(cls, cls_frame, irg, bl, frame, irn);
/*
* search the right insertion point. a spill of a phi cannot be put
pset_foreach(remat_info->remats, remat)
{
if(remat->proj && get_irn_n_edges(remat->proj) == 0) {
- set_irn_n(remat->proj, -1, bad);
- set_irn_n(remat->proj, 0, bad);
+ set_irn_n((ir_node*)remat->proj, -1, bad);
+ set_irn_n((ir_node*)remat->proj, 0, bad);
}
if(get_irn_n_edges(remat->op) == 0) {
for (n=get_irn_arity(remat->op)-1; n>=-1; --n) {
- set_irn_n(remat->op, n, bad);
+ set_irn_n((ir_node*)remat->op, n, bad);
}
}
}
}
static pset *
-get_spills_for_value(spill_ilp_t * si, ir_node * value)
+get_spills_for_value(spill_ilp_t * si, const ir_node * value)
{
pset *spills = pset_new_ptr_default();
- ir_node *next;
- defs_t *defs;
+ const ir_node *next;
+ defs_t *defs;
defs = set_find_def(si->values, value);
return spills;
}
-static pset *
-get_remats_for_value(spill_ilp_t * si, ir_node * value)
-{
- pset *remats = pset_new_ptr_default();
-
- ir_node *next;
- defs_t *defs;
-
- pset_insert_ptr(remats, value);
- defs = set_find_def(si->values, value);
-
- if(defs && defs->remats) {
- for(next = defs->remats; next; next = get_irn_link(next)) {
- pset_insert_ptr(remats, next);
- }
- }
-
- return remats;
-}
-
-
/**
* @param before The node after which the spill will be placed in the schedule
*/
/* TODO set context properly */
static ir_node *
-insert_spill(spill_ilp_t * si, ir_node * irn, ir_node * value, ir_node * before)
+insert_spill(spill_ilp_t * si, ir_node * irn, const ir_node * value, ir_node * before)
{
defs_t *defs;
ir_node *spill;
DBG((si->dbg, LEVEL_3, "\t inserting spill for value %+F after %+F\n", irn, before));
- spill = be_spill2(arch_env, irn, before, irn);
+ spill = be_spill2(arch_env, irn, before);
defs = set_insert_def(si->values, value);
assert(defs);
* @param before The Phi node which has to be spilled
*/
static ir_node *
-insert_mem_phi(spill_ilp_t * si, const ir_node * phi)
+insert_mem_phi(spill_ilp_t * si, ir_node * phi)
{
ir_node *mem_phi;
ir_node **ins;
defs_t *defs;
int n;
- op_t *op = get_irn_link(phi);
NEW_ARR_A(ir_node*, ins, get_irn_arity(phi));
* Add reload before operation and add to list of defs
*/
static ir_node *
-insert_reload(spill_ilp_t * si, const ir_node * value, const ir_node * after)
+insert_reload(spill_ilp_t * si, const ir_node * value, ir_node * after)
{
defs_t *defs;
ir_node *reload,
}
static ir_node *
-insert_mem_copy(spill_ilp_t * si, const ir_node * bb, const ir_node * value)
+insert_mem_copy(spill_ilp_t * si, ir_node * bb, ir_node * value)
{
ir_node *insert_pos = bb;
ir_node *spill;
DBG((si->dbg, LEVEL_2, "\t inserting mem copy for value %+F after %+F\n", value, insert_pos));
- spill = be_spill2(arch_env, is_Block(insert_pos)?value:insert_pos, insert_pos, value);
+ spill = be_spill2(arch_env, is_Block(insert_pos)?value:insert_pos, insert_pos);
return spill;
}
if(!phi_m) continue;
for(n=get_irn_arity(phi)-1; n>=0; --n) {
- const ir_node *value = get_irn_n(phi, n);
+ ir_node *value = get_irn_n(phi, n);
defs_t *val_defs = set_find_def(si->values, value);
- ir_node *arg = get_irn_n(phi_m, n);
/* a spill of this value */
ir_node *spill;
spill_ilp_t *si = (spill_ilp_t*)data;
ir_node *irn;
spill_bb_t *spill_bb = get_irn_link(bb);
- int i;
/* reloads at end of block */
if(spill_bb->reloads) {
walker_kill_unused(ir_node * bb, void * data)
{
struct kill_helper *kh = data;
- const ir_node *bad = get_irg_bad(get_irn_irg(bb));
+ ir_node *bad = get_irg_bad(get_irn_irg(bb));
ir_node *irn;
lc_bitset_free(kh.used);
}
-static void
+void
print_irn_pset(pset * p)
{
ir_node *irn;
}
}
-static void
+void
dump_phi_class(spill_ilp_t * si, pset * phiclass, const char * file)
{
FILE *f = fopen(file, "w");
/* then fix uses of spills */
set_foreach(si->values, defs) {
- pset *reloads;
- pset *spills;
- ir_node *next = defs->remats;
+ pset *reloads;
+ pset *spills;
+ const ir_node *next = defs->remats;
int remats = 0;
reloads = pset_new_ptr_default();
/* first fix uses of remats and reloads */
set_foreach(si->values, defs) {
- pset *nodes;
- ir_node *next = defs->remats;
+ pset *nodes;
+ const ir_node *next = defs->remats;
if(next) {
nodes = pset_new_ptr_default();
if( sched_is_end(irn) ||
(be_is_Reload(irn) && has_reg_class(si, irn)) ||
/* do not move reload before its spill */
- (irn == be_get_Reload_mem(reload)) ) break;
+ (irn == be_get_Reload_mem(reload)) ||
+ /* do not move before phi */
+ is_Phi(irn)) break;
set_irn_link(irn, INT_TO_PTR(pressure+1));
DBG((si->dbg, LEVEL_5, "new regpressure before %+F: %d\n", irn, pressure+1));
static void
walker_spillslotassigner(ir_node * irn, void * data)
{
- spill_ilp_t *si = (spill_ilp_t*)data;
void *cls;
if(!be_is_Spill(irn)) return;
/* set spill context to phi class if it has one ;) */
-
+ (void) cls;
+#if 0
+ // Matze: not needed anymore
cls = get_phi_class(irn);
if(cls)
be_set_Spill_context(irn, cls);
else
be_set_Spill_context(irn, irn);
+#endif
}
#endif
#ifdef SOLVE
- DBG((si.dbg, LEVEL_1, "\tSolving %F\n", chordal_env->irg));
+ DBG((si.dbg, LEVEL_1, "\tSolving %s (%d variables, %d constraints)\n", problem_name, si.lpp->var_next, si.lpp->cst_next));
#ifdef ILP_TIMEOUT
lpp_set_time_limit(si.lpp, ILP_TIMEOUT);
#endif
projects / libfirm / blobdiff