4 * Copyright: (c) Universitaet Karlsruhe
5 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
7 * Implementation of the RA-Interface for an external, (non-SSA) register allocator.
9 * The external register allocator is a program taking 2 arguments:
10 * 1) An input file in which the cfg is defined
11 * 2) An output file containing the essential actions performed during allocation
16 ----------------------
18 inputfile ::= regs cfg .
20 regs ::= 'regs' regcount . // Anzahl der register (0..regcount-1), die zur Verfuegung stehen
22 cfg ::= 'cfg' ident '{' block* edge* '}' . // Steuerflussgraph der Prozedur
24 block ::= 'block' block-nr '{' insn* '}' . // Grundblock im cfg versehen mit einer nummer
26 edge ::= 'cf-edge' block-nr block-nr . // Steuerflusskante src-->tgt
28 insn ::= gen-insn // Befehl in einem block
31 gen-insn ::= 'insn' insn-nr '{' uses defs '}' .
32 copy-insn ::= 'copy' insn-nr '{' uses defs '}' .
34 defs ::= 'def' var-list . // Liste der definierten/verwendeten Variablen
35 uses ::= 'use' var-list .
41 | var-nr '<' reg-nr '>' . // reg-nr gibt register constraint an.
44 ident ::= non-whitespace-char* .
45 regcount, block-nr, insn-nr, reg-nr, var-nr ::= integer .
48 The output file format
49 -----------------------
51 outputfile ::= action* .
53 action ::= 'spill' loc var-nr // insert a spill spill(var-nr);
54 | 'reload' loc var-nr var-nr // insert a reload var-nr[1] := reload(var-nr[2]);
55 | 'copy' loc var-nr var-nr // insert a copy var-nr[1] := var-nr[2];
56 | 'assign' var-nr reg-nr . // assign var-nr the register reg-nr
58 loc ::= 'before' insn-nr
63 * End of file format docu */
78 #include <libcore/lc_opts.h>
79 #include <libcore/lc_opts_enum.h>
86 #include "irprintf_t.h"
88 #include "irgraph_t.h"
92 #include "beraextern.h"
99 * Environment with all the needed stuff
101 typedef struct _be_raext_env_t {
103 const arch_register_class_t *cls;
106 FILE *f; /**< file handle used for out- and input file */
107 pmap *vars; /**< maps variable numbers (int) to the corresponding SSA-values (pset of irns) */
108 pmap *blocks; /**< maps block numbers (int) to the block (ir_node*) having that node_nr */
111 /******************************************************************************
114 | | | |_ __ | |_ _ ___ _ __ ___
115 | | | | '_ \| __| |/ _ \| '_ \/ __|
116 | |__| | |_) | |_| | (_) | | | \__ \
117 \____/| .__/ \__|_|\___/|_| |_|___/
120 *****************************************************************************/
123 static void ssa_destr_simple(be_raext_env_t *);
124 static void ssa_destr_rastello(be_raext_env_t *);
125 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg);
127 static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple;
128 static char callee[128] = "echo";
132 static const lc_opt_enum_const_ptr_items_t ssa_destr_items[] = {
133 { "simple", ssa_destr_simple },
134 { "rastello", ssa_destr_rastello },
138 static lc_opt_enum_const_ptr_var_t ssa_destr_var = {
139 (const void **) &ssa_destr, ssa_destr_items
142 static const lc_opt_table_entry_t be_ra_extern_options[] = {
143 LC_OPT_ENT_ENUM_FUNC_PTR("ssa_destr", "SSA destruction flavor", &ssa_destr_var),
144 LC_OPT_ENT_STR("callee", "The external program to call", callee, sizeof(callee)),
148 static void be_ra_extern_register_options(lc_opt_entry_t *root) {
149 lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext");
151 lc_opt_add_table(grp, be_ra_extern_options);
154 #endif /* WITH_LIBCORE */
156 const be_ra_t be_ra_external_allocator = {
158 be_ra_extern_register_options,
163 /******************************************************************************
166 | |__| | ___| |_ __ ___ _ __ ___
167 | __ |/ _ \ | '_ \ / _ \ '__/ __|
168 | | | | __/ | |_) | __/ | \__ \
169 |_| |_|\___|_| .__/ \___|_| |___/
172 *****************************************************************************/
174 #define mark_as_done(irn, pos) set_irn_link(irn, INT_TO_PTR(pos+1))
175 #define has_been_done(irn, pos) (PTR_TO_INT(get_irn_link(irn)) > pos)
177 #define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val)
178 #define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key)
179 #define set_var_nr(irn, nr) set_irn_link(irn, INT_TO_PTR(nr))
180 #define get_var_nr(irn) PTR_TO_INT(get_irn_link(irn))
184 * Checks if _the_ result of the irn belongs to the
185 * current register class (raenv->cls)
186 * NOTE: Only the first result is checked.
188 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
192 * Checks if the irn uses or defines values of the
193 * current register class (raenv->cls)
195 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
198 /* check arguments */
199 for (i=0, max=get_irn_arity(irn); i<max; ++i)
200 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
203 /* check result(s) */
204 if (get_irn_mode(irn) == mode_T) {
206 for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
207 if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
211 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
214 assert(0 && "Where did you come from???");
217 /******************************************************************************
219 / ____/ ____| /\ | __ \ | |
220 | (___| (___ / \ ______| | | | ___ ___| |_ _ __
221 \___ \\___ \ / /\ \______| | | |/ _ \/ __| __| '__|
222 ____) |___) / ____ \ | |__| | __/\__ \ |_| |
223 |_____/_____/_/ \_\ |_____/ \___||___/\__|_|
225 *****************************************************************************/
229 * Insert a copy for the argument of @p start_phi found at position @p pos.
230 * Also searches a phi-loop of arbitrary length to detect and resolve
231 * the class of phi-swap-problems. To search for a loop recursion is used.
233 * 1) Simplest case (phi with a non-phi arg):
234 * A single copy is inserted.
236 * 2) Phi chain (phi (with phi-arg)* with non=phi arg):
237 * Several copies are placed, each after returning from recursion.
240 * On detection a loop breaker is inserted, which is a copy of the start_phi.
241 * This copy then pretends beeing the argumnent of the last phi.
242 * Now case 2) can be used.
244 * The values of @p start_phi and @p pos never change during recursion.
246 * @p raenv Environment with all the stuff needed
247 * @p start_phi Phi node to process
248 * @p pos Argument position to insert copy/copies for
249 * @p curr_phi Phi node currently processed during recursion. Equals start_phi on initial call
251 * @return NULL If no copy is necessary
252 * NULL If the phi has already been processed at this pos
253 * Link field is used to keep track of processed positions
254 * In all other cases the ir_node *copy which was placed is returned.
256 static ir_node *insert_copies(be_raext_env_t *raenv, ir_node *start_phi, int pos, ir_node *curr_phi) {
257 ir_node *arg = get_irn_n(curr_phi, pos);
258 ir_node *arg_blk = get_nodes_block(arg);
259 ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos);
260 ir_node *curr_cpy, *last_cpy;
262 assert(is_Phi(start_phi) && is_Phi(curr_phi));
264 if (has_been_done(start_phi, pos))
267 /* In case this is a 'normal' phi we insert into
268 * the schedule before the pred_blk irn */
271 /* If we detect a loop stop recursion. */
272 if (arg == start_phi) {
273 ir_node *loop_breaker;
274 if (start_phi == curr_phi) {
275 /* Phi directly uses itself. No copy necessary */
279 /* At least 2 phis are involved */
280 /* Insert a loop breaking copy (an additional variable T) */
281 loop_breaker = be_new_Copy(raenv->cls, raenv->irg, pred_blk, start_phi);
282 sched_add_before(pred_blk, loop_breaker);
287 /* If arg is a phi in the same block we have to continue search */
288 if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi))
289 last_cpy = insert_copies(raenv, start_phi, pos, arg);
291 /* Insert copy of argument (may be the loop-breaker) */
292 curr_cpy = be_new_Copy(raenv->cls, raenv->irg, pred_blk, arg);
293 set_irn_n(curr_phi, pos, curr_cpy);
294 mark_as_done(curr_phi, pos);
295 sched_add_before(last_cpy, curr_cpy);
301 * Perform simple SSA-destruction with copies.
302 * The order of processing _must_ be
303 * for all positions {
308 * else the magic to keep track of processed phi-positions will fail in
309 * function 'insert_copies'
311 static void ssa_destr_simple_walker(ir_node *blk, void *env) {
312 be_raext_env_t *raenv = env;
316 /* for all argument positions of the phis */
317 for (pos=0, max=get_irn_arity(blk); pos<max; ++pos) {
319 /* for all phi nodes (which are scheduled first) */
320 sched_foreach(blk, phi) {
324 raenv->cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
325 insert_copies(raenv, phi, pos, phi);
331 static void ssa_destr_simple(be_raext_env_t *raenv) {
332 be_clear_links(raenv->irg);
333 irg_block_walk_graph(raenv->irg, ssa_destr_simple_walker, NULL, raenv);
337 static void ssa_destr_rastello(be_raext_env_t *raenv) {
338 phi_class_compute(raenv->irg);
339 //TODO irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv);
344 * Define variables (numbers) for all SSA-values.
345 * All values in a phi class get assigned the same variable name.
346 * The link field maps values to the var-name
348 static void values_to_vars(ir_node *irn, void *env) {
349 be_raext_env_t *raenv = env;
354 vals = get_phi_class(irn);
357 /* not a phi class member, value == var */
358 vals = pset_new_ptr(1);
359 pset_insert_ptr(vals, irn);
362 /* value to var mapping */
363 n = pset_first(vals);
364 nr = get_irn_node_nr(n);
365 for (; n; n=pset_next(vals))
368 /* var to values mapping */
369 pmap_insert_sth(raenv->vars, nr, vals);
372 /******************************************************************************
375 | | | |_ _ _ __ ___ _ __ ___ _ __
376 | | | | | | | '_ ` _ \| '_ \ / _ \ '__|
377 | |__| | |_| | | | | | | |_) | __/ |
378 |_____/ \__,_|_| |_| |_| .__/ \___|_|
381 *****************************************************************************/
384 * Check if node irn has a limited-constraint at position pos.
385 * If yes, dump it to FILE raenv->f
387 static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
388 bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
389 arch_register_req_t req;
391 arch_get_register_req(raenv->aenv, &req, irn, pos);
392 if (arch_register_req_is(&req, limited)) {
394 req.limited(irn, pos, bs);
395 reg_nr = bitset_next_set(bs, 0);
396 fprintf(raenv->f, " <%d>", reg_nr);
397 assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
403 * Dump all blocks and instructions in that block
405 static void dump_blocks(ir_node *blk, void *env) {
406 be_raext_env_t *raenv = env;
409 int nr = get_irn_node_nr(blk);
411 pmap_insert_sth(raenv->blocks, nr, blk);
413 /* begin block scope */
415 fprintf(f, " block %d {\n", nr);
417 /* for each instruction */
418 for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
420 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
423 fprintf(f, " insn %ld {\n", get_irn_node_nr(irn));
429 for (i=0, max=get_irn_arity(irn); i<max; ++i) {
430 ir_node *arg = get_irn_n(irn, i);
431 if (arch_irn_has_reg_class(raenv->aenv, arg, -1, raenv->cls)) {
432 fprintf(f, " %d", get_var_nr(arg));
433 dump_constraint(raenv, irn, i);
442 /* special handling of projs */
443 if (get_irn_mode(irn) == mode_T) {
444 for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn))
445 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
446 fprintf(f, " %d", get_var_nr(irn));
447 dump_constraint(raenv, irn, -1);
449 irn = sched_prev(irn); /* for outer loop */
451 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
452 fprintf(f, " %d", get_var_nr(irn));
453 dump_constraint(raenv, irn, -1);
461 /* end the block scope */
467 * Dump all control flow edges of this irg
469 static void dump_edges(ir_node *blk, void *env) {
470 be_raext_env_t *raenv = env;
473 if (get_irg_start_block(get_irn_irg(blk)) == blk)
476 /* dump cf edges in the flow-order "pred succ" */
477 for (i=0, max=get_irn_arity(blk); i<max; ++i) {
478 ir_node *pred = get_Block_cfgpred_block(blk, i);
479 fprintf(raenv->f, " cf_edge %ld %ld\n", get_irn_node_nr(pred), get_irn_node_nr(blk));
485 * Dump all information needed by the external
486 * register allocator to a single file.
488 static void dump_to_file(be_raext_env_t *raenv, char *filename) {
491 if (!(f = fopen(filename, "wt"))) {
492 fprintf(stderr, "Could not open file %s for writing\n", filename);
497 fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
498 fprintf(f, "cfg %s {\n", filename);
500 irg_block_walk_graph(raenv->irg, NULL, dump_blocks, raenv);
501 irg_block_walk_graph(raenv->irg, NULL, dump_edges, raenv);
509 /******************************************************************************
512 | |__ __ _____ ___ _ _| |_ ___
513 | __| \ \/ / _ \/ __| | | | __/ _ \
514 | |____ > < __/ (__| |_| | || __/
515 |______/_/\_\___|\___|\__,_|\__\___|
516 *****************************************************************************/
519 * Execute the external register allocator specified in the
520 * firm-option firm.be.ra.ext.callee
522 static void execute(char *out_file, char *result_file) {
526 snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", callee, out_file, result_file);
528 ret_status = system(cmd_line);
529 assert(ret_status != -1 && "Invokation of external register allocator failed");
532 /******************************************************************************
535 / \ _ __ _ __ | |_ _ | |__) |___ ___ _ _| | |_
536 / /\ \ | '_ \| '_ \| | | | | | _ // _ \/ __| | | | | __|
537 / ____ \| |_) | |_) | | |_| | | | \ \ __/\__ \ |_| | | |_
538 /_/ \_\ .__/| .__/|_|\__, | |_| \_\___||___/\__,_|_|\__|
541 *****************************************************************************/
544 * Read in the actions performed by the external allocator.
545 * Apply these transformations to the irg->
547 static void read_and_apply_results(be_raext_env_t *raenv, char *filename) {
550 if (!(f = fopen(filename, "rt"))) {
551 fprintf(stderr, "Could not open file %s for reading\n", filename);
556 //TODO: free pmap entries (the psets) pmap_foreach(raenv.vars, pme) del_pset(pme->value);
561 /******************************************************************************
565 | |\/| |/ _` | | '_ \
566 | | | | (_| | | | | |
567 |_| |_|\__,_|_|_| |_|
568 *****************************************************************************/
571 * Allocate registers with an external program using a text-file interface.
573 * Do some computations (SSA-destruction and mapping of values--vars)
575 * Execute external program
576 * Read in results and apply them
579 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
580 be_raext_env_t raenv;
584 raenv.aenv = env->arch_env;
585 raenv.vars = pmap_create();
586 raenv.blocks = pmap_create();
588 /* SSA destruction */
592 phi_class_compute(irg);
593 irg_walk_graph(irg, values_to_vars, NULL, &raenv);
595 dump_ir_block_graph_sched(irg, "-extern-ssadestr");
597 /* For all register classes */
598 for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
599 char out[256], in[256];
601 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
602 ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name);
603 ir_snprintf(in, sizeof(in), "%F-%s.ra.res", irg, raenv.cls->name);
605 dump_to_file(&raenv, out);
609 read_and_apply_results(&raenv, in);
613 pmap_destroy(raenv.blocks);
614 pmap_destroy(raenv.vars);