*
* 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
set_irn_n(irn, pos, cpy);
/* set an out constraint for the copy */
- arch_set_register_req(raenv->aenv, -1, &req); /* TODO */
+ be_set_constr_limited(cpy, -1, &req);
}
}
}
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);
+ }
}
}
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);
+ be_ssa_constr_sets(raenv->dom_info, spills, reloads);
/****** correct the variable <--> values mapping: ******
* 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;
/* Insert copies for constraints */
handle_constraints(&raenv);
+ dump_ir_block_graph_sched(irg, "-extern-constr");
- /* 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 },
+ { "simple", (void*)ssa_destr_simple }, /* TODO make (void*) casts nicer */
+ { "rastello", (void*)ssa_destr_rastello },
{ NULL, NULL }
};
projects / libfirm / blobdiff