*
* Implementation of the RA-Interface for an external, (non-SSA) register allocator.
*
- * The external register allocator is a program taking 2 arguments:
- * 1) An input file in which the cfg is defined
- * 2) An output file containing the essential actions performed during allocation
+ * The external register allocator is a program:
+ * PROG -i INPUTFILE -o OUTPUTFILE
+ *
+ * 1) Input file defines the interference graph
+ * 2) Output file contains the instructions to perform
*
nodes ::= 'nodes' '{' node* '}' . // All nodes in the graph
+node ::= node-info
+ | node-info '<' reg-nr '>' . // Reg-nr is present in case of constraints
+
+node-info ::= node-nr spill-costs .
+
interf ::= 'interferences' '{' edge* '}' . // Interference edges of the graph
affinities ::= 'affinities' '{' edge* '}' . // Affinity edges of the graph
-node ::= node-nr
- | node-nr '<' reg-nr '>' . // Reg-nr is present in case of constraints
-
-edge ::= '(' node-nr node-nr ')' .
+edge ::= '(' node-nr ',' node-nr ')' .
-regcount, node-nr ::= integer .
+spill-costs, regcount, node-nr ::= integer .
The output file format
#include "beirgmod.h"
#include "besched.h"
#include "beutil.h"
+#include "belive_t.h"
typedef struct _var_info_t var_info_t;
return NULL;
}
+/******************************************************************************
+ _____ _ _____ _
+ / ____| | | / ____| (_)
+ | | ___ _ __ ___| |_ _ __ | | ___ _ __ _ ___ ___
+ | | / _ \| '_ \/ __| __| '__| | | / _ \| '_ \| |/ _ \/ __|
+ | |___| (_) | | | \__ \ |_| | | |___| (_) | |_) | | __/\__ \
+ \_____\___/|_| |_|___/\__|_| \_____\___/| .__/|_|\___||___/
+ | |
+ |_|
+ *****************************************************************************/
+
+static void handle_constraints_walker(ir_node *irn, void *env) {
+ be_raext_env_t *raenv = env;
+ arch_register_req_t req;
+ int pos, max;
+
+ /* handle output constraints
+ * user -> irn becomes user -> cpy -> irn
+ */
+ arch_get_register_req(raenv->aenv, &req, irn, -1);
+ if (arch_register_req_is(&req, limited)) {
+ ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), irn);
+ const ir_edge_t *edge;
+
+ /* all users of the irn use the copy instead */
+ sched_add_after(irn, cpy);
+ foreach_out_edge(irn, edge)
+ set_irn_n(edge->src, edge->pos, cpy);
+ }
+
+
+ /* handle input constraints by converting them into output constraints
+ * of copies of the former argument
+ * irn -> arg becomes irn -> copy -> arg
+ */
+ for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
+ arch_get_register_req(raenv->aenv, &req, irn, pos);
+ if (arch_register_req_is(&req, limited)) {
+ ir_node *arg = get_irn_n(irn, pos);
+ ir_node *cpy = be_new_Copy(req.cls, raenv->irg, get_nodes_block(irn), arg);
+
+ /* use the copy instead */
+ sched_add_before(irn, cpy);
+ set_irn_n(irn, pos, cpy);
+
+ /* set an out constraint for the copy */
+ be_set_constr_limited(cpy, -1, &req);
+ }
+ }
+}
+
+static void handle_constraints(be_raext_env_t *raenv) {
+ irg_block_walk_graph(raenv->irg, NULL, handle_constraints_walker, raenv);
+}
+
/******************************************************************************
_____ _____ _____ _
static void ssa_destr_rastello(be_raext_env_t *raenv) {
assert(0 && "NYI");
- /* TODO
+ exit(0xDeadBeef);
+ /*
phi_class_compute(raenv->irg);
irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv);
*/
}
}
+static INLINE int get_spill_costs(var_info_t *vi) {
+ ir_node *irn;
+ int n_spills=0, n_reloads=0;
+
+ pset_foreach(vi->values, irn) {
+ if (is_Phi(irn)) {
+ /* number of reloads is the number of non-phi uses of all values of this var */
+ const ir_edge_t *edge;
+ foreach_out_edge(irn, edge)
+ if (!is_Phi(edge->src))
+ n_reloads++;
+ } else {
+ /* number of spills is the number of non-phi values for this var */
+ n_spills++;
+ }
+ }
+
+ return n_spills + n_reloads;
+}
static void dump_nodes(be_raext_env_t *raenv) {
FILE *f = raenv->f;
if (vi->var_nr == SET_REMOVED)
continue;
- fprintf(f, "%d", vi->var_nr);
+ fprintf(f, "%d %d", vi->var_nr, get_spill_costs(vi));
dump_constraint(raenv, get_first_non_phi(vi->values), -1);
fprintf(f, "\n");
}
if (values_interfere(irn1, irn2)) {
pset_break(vi1->values);
pset_break(vi2->values);
- fprintf(f, "(%d %d)\n", vi1->var_nr, vi2->var_nr);
+ fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
}
}
}
static void dump_affinities_walker(ir_node *irn, void *env) {
be_raext_env_t *raenv = env;
+ arch_register_req_t req;
+ int pos, max;
+ var_info_t *vi1, *vi2;
+ vi1 = get_var_info(irn);
+
+ /* copies have affinities */
+ /* TODO? remove this case by adding should_be_equal requirements */
if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy) {
- ir_node *src = get_irn_n(irn, 0);
- var_info_t *vi1 = get_irn_link(irn);
- var_info_t *vi2 = get_irn_link(src);
+ vi2 = get_var_info(get_irn_n(irn, 0));
- fprintf(raenv->f, "(%d %d)\n", vi1->var_nr, vi2->var_nr);
+ fprintf(raenv->f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
+ }
+
+
+ /* should_be_equal constraints are affinites */
+ for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
+ arch_get_register_req(raenv->aenv, &req, irn, pos);
+
+ if (arch_register_req_is(&req, should_be_same)) {
+ vi2 = get_var_info(req.other_same);
+
+ fprintf(raenv->f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
+ }
}
}
static void dump_affinities(be_raext_env_t *raenv) {
- fprintf(raenv->f, "\ninterferences {\n");
+ fprintf(raenv->f, "\naffinities {\n");
irg_walk_graph(raenv->irg, NULL, dump_affinities_walker, raenv);
fprintf(raenv->f, "}\n");
}
char cmd_line[1024];
int ret_status;
- snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", prog_to_call, out_file, result_file);
+ snprintf(cmd_line, sizeof(cmd_line), "%s -i %s -o %s", prog_to_call, out_file, result_file);
ret_status = system(cmd_line);
assert(ret_status != -1 && "Invokation of external register allocator failed");
}
/* correct the reload->spill pointers... */
- be_introduce_copies_for_set(raenv->dom_info, spills, reloads); /* TODO */
-
+ be_ssa_constr_set(raenv->dom_info, spills);
/****** correct the variable <--> values mapping: ******
*
pset_foreach(reloads, irn)
raenv->cls_vars[raenv->n_cls_vars++] = var_add_value(raenv, get_irn_node_nr(irn), irn);
-
-
del_pset(spills);
del_pset(reloads);
}
* Default values for options
*/
static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple;
-static char callee[128] = "echo";
+static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator";
/**
* Read in results and apply them
*
*/
-static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
+static void be_ra_extern_main(const be_irg_t *bi) {
+ be_main_env_t *env = bi->main_env;
+ ir_graph *irg = bi->irg;
+
be_raext_env_t raenv;
int clsnr, clss;
var_info_t *vi;
compute_doms(irg);
+ be_liveness(irg);
raenv.irg = irg;
raenv.aenv = env->arch_env;
raenv.dom_info = be_compute_dominance_frontiers(irg);
raenv.vars = new_set(compare_var_infos, 64);
+ /* Insert copies for constraints */
+ handle_constraints(&raenv);
+ dump_ir_block_graph_sched(irg, "-extern-constr");
- //TODO /* Insert copies */
- //TODO /* Change In to Out constraints */
-
- /* SSA destruction */
+ /* SSA destruction respectively transformation into "Conventional SSA" */
ssa_destr(&raenv);
+ dump_ir_block_graph_sched(irg, "-extern-ssadestr");
+
/* Mapping of SSA-Values <--> Variables */
phi_class_compute(irg);
be_clear_links(irg);
irg_walk_graph(irg, values_to_vars, NULL, &raenv);
- dump_ir_block_graph_sched(irg, "-extern-ssadestr");
-
/* For all register classes */
for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
int done = 0;
free(raenv.cls_vars);
}
+ dump_ir_block_graph_sched(irg, "-extern-alloc");
+
/* Clean up */
set_foreach(raenv.vars, vi)
del_pset(vi->values);
#ifdef WITH_LIBCORE
-static const lc_opt_enum_const_ptr_items_t ssa_destr_items[] = {
- { "simple", ssa_destr_simple },
- { "rastello", ssa_destr_rastello },
+
+static const lc_opt_enum_func_ptr_items_t ssa_destr_items[] = {
+ { "simple", (int (*)()) ssa_destr_simple }, /* TODO make (void*) casts nicer */
+ { "rastello", (int (*)()) ssa_destr_rastello },
{ NULL, NULL }
};
-static lc_opt_enum_const_ptr_var_t ssa_destr_var = {
- (const void **) &ssa_destr, ssa_destr_items
+static lc_opt_enum_func_ptr_var_t ssa_destr_var = {
+ (int (**)()) &ssa_destr, ssa_destr_items
};
static const lc_opt_table_entry_t be_ra_extern_options[] = {