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 *****************************************************************************/
175 * Checks if _the_ result of the irn belongs to the
176 * current register class (raenv->cls)
177 * NOTE: Only the first result is checked.
179 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
183 * Checks if the irn uses or defines values of the
184 * current register class (raenv->cls)
186 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
189 /* check arguments */
190 for (i=0, max=get_irn_arity(irn); i<max; ++i)
191 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
194 /* check result(s) */
195 if (get_irn_mode(irn) == mode_T) {
197 for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
198 if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
202 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
205 assert(0 && "Where did you come from???");
208 /******************************************************************************
210 / ____/ ____| /\ | __ \ | |
211 | (___| (___ / \ ______| | | | ___ ___| |_ _ __
212 \___ \\___ \ / /\ \______| | | |/ _ \/ __| __| '__|
213 ____) |___) / ____ \ | |__| | __/\__ \ |_| |
214 |_____/_____/_/ \_\ |_____/ \___||___/\__|_|
216 *****************************************************************************/
218 #define mark_as_done(irn, pos) set_irn_link(irn, INT_TO_PTR(pos+1))
219 #define has_been_done(irn, pos) (PTR_TO_INT(get_irn_link(irn)) > pos)
222 * Insert a copy for the argument of @p start_phi found at position @p pos.
223 * Also searches a phi-loop of arbitrary length to detect and resolve
224 * the class of phi-swap-problems. To search for a loop recursion is used.
226 * 1) Simplest case (phi with a non-phi arg):
227 * A single copy is inserted.
229 * 2) Phi chain (phi (with phi-arg)* with non=phi arg):
230 * Several copies are placed, each after returning from recursion.
233 * On detection a loop breaker is inserted, which is a copy of the start_phi.
234 * This copy then pretends beeing the argumnent of the last phi.
235 * Now case 2) can be used.
237 * The values of @p start_phi and @p pos never change during recursion.
239 * @p raenv Environment with all the stuff needed
240 * @p start_phi Phi node to process
241 * @p pos Argument position to insert copy/copies for
242 * @p curr_phi Phi node currently processed during recursion. Equals start_phi on initial call
244 * @return NULL If no copy is necessary
245 * NULL If the phi has already been processed at this pos
246 * Link field is used to keep track of processed positions
247 * In all other cases the ir_node *copy which was placed is returned.
249 static ir_node *insert_copies(be_raext_env_t *raenv, ir_node *start_phi, int pos, ir_node *curr_phi) {
250 ir_node *arg = get_irn_n(curr_phi, pos);
251 ir_node *arg_blk = get_nodes_block(arg);
252 ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos);
253 ir_node *curr_cpy, *last_cpy;
255 assert(is_Phi(start_phi) && is_Phi(curr_phi));
257 if (has_been_done(start_phi, pos))
260 /* In case this is a 'normal' phi we insert into
261 * the schedule before the pred_blk irn */
264 /* If we detect a loop stop recursion. */
265 if (arg == start_phi) {
266 ir_node *loop_breaker;
267 if (start_phi == curr_phi) {
268 /* Phi directly uses itself. No copy necessary */
272 /* At least 2 phis are involved */
273 /* Insert a loop breaking copy (an additional variable T) */
274 loop_breaker = be_new_Copy(raenv->cls, raenv->irg, pred_blk, start_phi);
275 sched_add_before(pred_blk, loop_breaker);
280 /* If arg is a phi in the same block we have to continue search */
281 if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi))
282 last_cpy = insert_copies(raenv, start_phi, pos, arg);
284 /* Insert copy of argument (may be the loop-breaker) */
285 curr_cpy = be_new_Copy(raenv->cls, raenv->irg, pred_blk, arg);
286 set_irn_n(curr_phi, pos, curr_cpy);
287 mark_as_done(curr_phi, pos);
288 sched_add_before(last_cpy, curr_cpy);
294 * Perform simple SSA-destruction with copies.
295 * The order of processing _must_ be
296 * for all positions {
301 * else the magic to keep track of processed phi-positions will fail in
302 * function 'insert_copies'
304 static void ssa_destr_simple_walker(ir_node *blk, void *env) {
305 be_raext_env_t *raenv = env;
309 /* for all argument positions of the phis */
310 for (pos=0, max=get_irn_arity(blk); pos<max; ++pos) {
312 /* for all phi nodes (which are scheduled first) */
313 sched_foreach(blk, phi) {
317 raenv->cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
318 insert_copies(raenv, phi, pos, phi);
324 static void ssa_destr_simple(be_raext_env_t *raenv) {
325 be_clear_links(raenv->irg);
326 irg_block_walk_graph(raenv->irg, ssa_destr_simple_walker, NULL, raenv);
330 static void ssa_destr_rastello(be_raext_env_t *raenv) {
331 phi_class_compute(raenv->irg);
332 //TODO irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv);
335 /******************************************************************************
337 \ \ / / | | |__ \ \ \ / /
338 \ \ / /_ _| |___ ) | \ \ / /_ _ _ __ ___
339 \ \/ / _` | / __| / / \ \/ / _` | '__/ __|
340 \ / (_| | \__ \ / /_ \ / (_| | | \__ \
341 \/ \__,_|_|___/ |____| \/ \__,_|_| |___/
342 *****************************************************************************/
344 #define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val)
345 #define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key)
346 #define set_var_nr(irn, nr) set_irn_link(irn, INT_TO_PTR(nr))
347 #define get_var_nr(irn) PTR_TO_INT(get_irn_link(irn))
350 * Define variables (numbers) for all SSA-values.
351 * All values in a phi class get assigned the same variable name.
352 * The link field maps values to the var-name
354 static void values_to_vars(ir_node *irn, void *env) {
355 be_raext_env_t *raenv = env;
360 vals = get_phi_class(irn);
363 /* not a phi class member, value == var */
364 vals = pset_new_ptr(1);
365 pset_insert_ptr(vals, irn);
368 /* value to var mapping */
369 n = pset_first(vals);
370 nr = get_irn_node_nr(n);
371 for (; n; n=pset_next(vals))
374 /* var to values mapping */
375 pmap_insert_sth(raenv->vars, nr, vals);
378 /******************************************************************************
381 | | | |_ _ _ __ ___ _ __ ___ _ __
382 | | | | | | | '_ ` _ \| '_ \ / _ \ '__|
383 | |__| | |_| | | | | | | |_) | __/ |
384 |_____/ \__,_|_| |_| |_| .__/ \___|_|
387 *****************************************************************************/
391 * Check if node irn has a limited-constraint at position pos.
392 * If yes, dump it to FILE raenv->f
394 static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
395 bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
396 arch_register_req_t req;
398 arch_get_register_req(raenv->aenv, &req, irn, pos);
399 if (arch_register_req_is(&req, limited)) {
401 req.limited(irn, pos, bs);
402 reg_nr = bitset_next_set(bs, 0);
403 fprintf(raenv->f, " <%d>", reg_nr);
404 assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
410 * Dump all blocks and instructions in that block
412 static void dump_blocks(ir_node *blk, void *env) {
413 be_raext_env_t *raenv = env;
416 int nr = get_irn_node_nr(blk);
418 pmap_insert_sth(raenv->blocks, nr, blk);
420 /* begin block scope */
422 fprintf(f, " block %d {\n", nr);
424 /* for each instruction */
425 for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
427 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
435 fprintf(f, " %ld {\n", get_irn_node_nr(irn));
441 for (i=0, max=get_irn_arity(irn); i<max; ++i) {
442 ir_node *arg = get_irn_n(irn, i);
443 if (arch_irn_has_reg_class(raenv->aenv, arg, -1, raenv->cls)) {
444 fprintf(f, " %d", get_var_nr(arg));
445 dump_constraint(raenv, irn, i);
454 /* special handling of projs */
455 if (get_irn_mode(irn) == mode_T) {
456 for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn))
457 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
458 fprintf(f, " %d", get_var_nr(irn));
459 dump_constraint(raenv, irn, -1);
461 irn = sched_prev(irn); /* for outer loop */
463 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
464 fprintf(f, " %d", get_var_nr(irn));
465 dump_constraint(raenv, irn, -1);
473 /* end the block scope */
479 * Dump all control flow edges of this irg
481 static void dump_edges(ir_node *blk, void *env) {
482 be_raext_env_t *raenv = env;
485 if (get_irg_start_block(get_irn_irg(blk)) == blk)
488 /* dump cf edges in the flow-order "pred succ" */
489 for (i=0, max=get_irn_arity(blk); i<max; ++i) {
490 ir_node *pred = get_Block_cfgpred_block(blk, i);
491 fprintf(raenv->f, " cf_edge %ld %ld\n", get_irn_node_nr(pred), get_irn_node_nr(blk));
497 * Dump all information needed by the external
498 * register allocator to a single file.
500 static void dump_to_file(be_raext_env_t *raenv, char *filename) {
503 if (!(f = fopen(filename, "wt"))) {
504 fprintf(stderr, "Could not open file %s for writing\n", filename);
509 fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
510 fprintf(f, "cfg %s {\n", filename);
512 irg_block_walk_graph(raenv->irg, NULL, dump_blocks, raenv);
513 irg_block_walk_graph(raenv->irg, NULL, dump_edges, raenv);
521 /******************************************************************************
524 | |__ __ _____ ___ _ _| |_ ___
525 | __| \ \/ / _ \/ __| | | | __/ _ \
526 | |____ > < __/ (__| |_| | || __/
527 |______/_/\_\___|\___|\__,_|\__\___|
528 *****************************************************************************/
531 * Execute the external register allocator specified in the
532 * firm-option firm.be.ra.ext.callee
534 static void execute(char *out_file, char *result_file) {
538 snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", callee, out_file, result_file);
540 ret_status = system(cmd_line);
541 assert(ret_status != -1 && "Invokation of external register allocator failed");
544 /******************************************************************************
547 / \ _ __ _ __ | |_ _ | |__) |___ ___ _ _| | |_
548 / /\ \ | '_ \| '_ \| | | | | | _ // _ \/ __| | | | | __|
549 / ____ \| |_) | |_) | | |_| | | | \ \ __/\__ \ |_| | | |_
550 /_/ \_\ .__/| .__/|_|\__, | |_| \_\___||___/\__,_|_|\__|
553 *****************************************************************************/
555 #define pset_foreach(pset, irn) for(irn=pset_first(pset); irn; irn=pset_next(pset))
557 #define INVALID_FILE_FORMAT assert(0 && "Invalid file format.")
559 static INLINE int get_location(const char *s, size_t len) {
560 if (!strncmp(s, "before", len))
562 if (!strncmp(s, "after", len))
569 * Read in the actions performed by the external allocator.
570 * Apply these transformations to the irg.
572 static void read_and_apply_results(be_raext_env_t *raenv, char *filename) {
576 if (!(f = fopen(filename, "rt"))) {
577 fprintf(stderr, "Could not open file %s for reading\n", filename);
584 int loc, var_use, var_def, reg_nr;
587 /* assign register */
588 if (fscanf(f, " assign %d %d ", &var_use, ®_nr) == 2) {
589 pset *vals = pmap_get_sth(raenv->vars, var_use);
592 assert(vals && "Variable does not (yet?) exist!");
593 pset_foreach(vals, irn)
594 arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, var_use));
597 /* handle a reload */
598 else if (fscanf(f, " reload %s %d %d %d ", &where, &loc, &var_def, &var_use) == 4) {
599 int before = get_location(where, sizeof(where));
604 else if (fscanf(f, " spill %6s %d %d ", &where, &loc, &var_use) == 3) {
605 int before = get_location(where, sizeof(where));
615 /* Free the psets holding the variable-equivalence classes */
616 pmap_foreach(raenv->vars, pme)
617 del_pset(pme->value);
620 /******************************************************************************
624 | |\/| |/ _` | | '_ \
625 | | | | (_| | | | | |
626 |_| |_|\__,_|_|_| |_|
627 *****************************************************************************/
630 * Allocate registers with an external program using a text-file interface.
632 * Do some computations (SSA-destruction and mapping of values--vars)
634 * Execute external program
635 * Read in results and apply them
638 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
639 be_raext_env_t raenv;
643 raenv.aenv = env->arch_env;
644 raenv.vars = pmap_create();
645 raenv.blocks = pmap_create();
647 /* SSA destruction */
651 phi_class_compute(irg);
652 irg_walk_graph(irg, values_to_vars, NULL, &raenv);
654 dump_ir_block_graph_sched(irg, "-extern-ssadestr");
656 /* For all register classes */
657 for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
658 char out[256], in[256];
660 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
661 ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name);
662 ir_snprintf(in, sizeof(in), "%F-%s.ra.res", irg, raenv.cls->name);
664 dump_to_file(&raenv, out);
668 read_and_apply_results(&raenv, in);
672 pmap_destroy(raenv.blocks);
673 pmap_destroy(raenv.vars);