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
17 ----------------------
19 inputfile ::= regs cfg .
21 regs ::= 'regs' regcount . // Anzahl der register (0..regcount-1), die zur Verfuegung stehen
23 cfg ::= 'cfg' ident '{' block* edge* '}' . // Steuerflussgraph der Prozedur
25 block ::= 'block' block-nr '{' insn* '}' . // Grundblock im cfg versehen mit einer nummer
27 edge ::= 'cf-edge' block-nr block-nr . // Steuerflusskante src-->tgt
29 insn ::= gen-insn // Befehl in einem block
32 gen-insn ::= 'insn' insn-nr '{' uses defs '}' .
33 copy-insn ::= 'copy' insn-nr '{' uses defs '}' .
35 defs ::= 'def' var-list . // Liste der definierten/verwendeten Variablen
36 uses ::= 'use' var-list .
42 | var-nr '<' reg-nr '>' . // reg-nr gibt register constraint an.
45 ident ::= non-whitespace-char*
46 regcount, block-nr, insn-nr, reg-nr, var-nr ::= integer
49 The output file format
50 -----------------------
52 outputfile ::= 'actions' '{' action-list '}'
55 #endif /* documentation of file formats */
70 #include <libcore/lc_opts.h>
71 #include <libcore/lc_opts_enum.h>
78 #include "irprintf_t.h"
80 #include "irgraph_t.h"
84 #include "beraextern.h"
91 * Environment with all the needed stuff
93 typedef struct _be_raext_env_t {
95 const arch_register_class_t *cls;
98 FILE *f; /**< file handle used for out- and input file */
99 pmap *vars; /**< maps variable numbers (int) to the corresponding SSA-values (pset of irns) */
100 pmap *blocks; /**< maps block numbers (int) to the block (ir_node*) having that node_nr */
103 /******************************************************************************
106 | | | |_ __ | |_ _ ___ _ __ ___
107 | | | | '_ \| __| |/ _ \| '_ \/ __|
108 | |__| | |_) | |_| | (_) | | | \__ \
109 \____/| .__/ \__|_|\___/|_| |_|___/
112 *****************************************************************************/
115 static void ssa_destr_simple(be_raext_env_t *);
116 static void ssa_destr_rastello(be_raext_env_t *);
117 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg);
119 static void (*ssa_destr)(be_raext_env_t*) = ssa_destr_simple;
120 static char callee[128] = "echo";
124 static const lc_opt_enum_const_ptr_items_t ssa_destr_items[] = {
125 { "simple", ssa_destr_simple },
126 { "rastello", ssa_destr_rastello },
130 static lc_opt_enum_const_ptr_var_t ssa_destr_var = {
131 (const void **) &ssa_destr, ssa_destr_items
134 static const lc_opt_table_entry_t be_ra_extern_options[] = {
135 LC_OPT_ENT_ENUM_FUNC_PTR("ssa_destr", "SSA destruction flavor", &ssa_destr_var),
136 LC_OPT_ENT_STR("callee", "The external program to call", callee, sizeof(callee)),
140 static void be_ra_extern_register_options(lc_opt_entry_t *root) {
141 lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext");
143 lc_opt_add_table(grp, be_ra_extern_options);
146 #endif /* WITH_LIBCORE */
148 const be_ra_t be_ra_external_allocator = {
150 be_ra_extern_register_options,
155 /******************************************************************************
158 | |__| | ___| |_ __ ___ _ __ ___
159 | __ |/ _ \ | '_ \ / _ \ '__/ __|
160 | | | | __/ | |_) | __/ | \__ \
161 |_| |_|\___|_| .__/ \___|_| |___/
164 *****************************************************************************/
166 #define mark_as_done(irn, pos) set_irn_link(irn, INT_TO_PTR(pos+1))
167 #define has_been_done(irn, pos) (PTR_TO_INT(get_irn_link(irn)) > pos)
169 #define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val)
170 #define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key)
171 #define set_var_nr(irn, nr) set_irn_link(irn, INT_TO_PTR(nr))
172 #define get_var_nr(irn) PTR_TO_INT(get_irn_link(irn))
176 * Checks if _the_ result of the irn belongs to the
177 * current register class (raenv->cls)
178 * NOTE: Only the first result is checked.
180 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
184 * Checks if the irn uses or defines values of the
185 * current register class (raenv->cls)
187 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
190 /* check arguments */
191 for (i=0, max=get_irn_arity(irn); i<max; ++i)
192 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
195 /* check result(s) */
196 if (get_irn_mode(irn) == mode_T) {
198 for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
199 if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
203 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
206 assert(0 && "Where did you come from???");
209 /******************************************************************************
211 / ____/ ____| /\ | __ \ | |
212 | (___| (___ / \ ______| | | | ___ ___| |_ _ __
213 \___ \\___ \ / /\ \______| | | |/ _ \/ __| __| '__|
214 ____) |___) / ____ \ | |__| | __/\__ \ |_| |
215 |_____/_____/_/ \_\ |_____/ \___||___/\__|_|
217 *****************************************************************************/
221 * Insert a copy for the argument of @p start_phi found at position @p pos.
222 * Also searches a phi-loop of arbitrary length to detect and resolve
223 * the class of phi-swap-problems. To search for a loop recursion is used.
225 * 1) Simplest case (phi with a non-phi arg):
226 * A single copy is inserted.
228 * 2) Phi chain (phi (with phi-arg)* with non=phi arg):
229 * Several copies are placed, each after returning from recursion.
232 * On detection a loop breaker is inserted, which is a copy of the start_phi.
233 * This copy then pretends beeing the argumnent of the last phi.
234 * Now case 2) can be used.
236 * The values of @p start_phi and @p pos never change during recursion.
238 * @p raenv Environment with all the stuff needed
239 * @p start_phi Phi node to process
240 * @p pos Argument position to insert copy/copies for
241 * @p curr_phi Phi node currently processed during recursion. Equals start_phi on initial call
243 * @return NULL If no copy is necessary
244 * NULL If the phi has already been processed at this pos
245 * Link field is used to keep track of processed positions
246 * In all other cases the ir_node *copy which was placed is returned.
248 static ir_node *insert_copies(be_raext_env_t *raenv, ir_node *start_phi, int pos, ir_node *curr_phi) {
249 ir_node *arg = get_irn_n(curr_phi, pos);
250 ir_node *arg_blk = get_nodes_block(arg);
251 ir_node *pred_blk = get_Block_cfgpred_block(get_nodes_block(curr_phi), pos);
252 ir_node *curr_cpy, *last_cpy;
254 assert(is_Phi(start_phi) && is_Phi(curr_phi));
256 if (has_been_done(start_phi, pos))
259 /* In case this is a 'normal' phi we insert into
260 * the schedule before the pred_blk irn */
263 /* If we detect a loop stop recursion. */
264 if (arg == start_phi) {
265 ir_node *loop_breaker;
266 if (start_phi == curr_phi) {
267 /* Phi directly uses itself. No copy necessary */
271 /* At least 2 phis are involved */
272 /* Insert a loop breaking copy (an additional variable T) */
273 loop_breaker = be_new_Copy(raenv->cls, raenv->irg, pred_blk, start_phi);
274 sched_add_before(pred_blk, loop_breaker);
279 /* If arg is a phi in the same block we have to continue search */
280 if (is_Phi(arg) && arg_blk == get_nodes_block(start_phi))
281 last_cpy = insert_copies(raenv, start_phi, pos, arg);
283 /* Insert copy of argument (may be the loop-breaker) */
284 curr_cpy = be_new_Copy(raenv->cls, raenv->irg, pred_blk, arg);
285 set_irn_n(curr_phi, pos, curr_cpy);
286 mark_as_done(curr_phi, pos);
287 sched_add_before(last_cpy, curr_cpy);
293 * Perform simple SSA-destruction with copies.
294 * The order of processing _must_ be
295 * for all positions {
300 * else the magic to keep track of processed phi-positions will fail in
301 * function 'insert_copies'
303 static void ssa_destr_simple_walker(ir_node *blk, void *env) {
304 be_raext_env_t *raenv = env;
308 /* for all argument positions of the phis */
309 for (pos=0, max=get_irn_arity(blk); pos<max; ++pos) {
311 /* for all phi nodes (which are scheduled first) */
312 sched_foreach(blk, phi) {
316 raenv->cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
317 insert_copies(raenv, phi, pos, phi);
323 static void ssa_destr_simple(be_raext_env_t *raenv) {
324 be_clear_links(raenv->irg);
325 irg_block_walk_graph(raenv->irg, ssa_destr_simple_walker, NULL, raenv);
329 static void ssa_destr_rastello(be_raext_env_t *raenv) {
330 phi_class_compute(raenv->irg);
331 //TODO irg_block_walk_graph(irg, ssa_destr_rastello, NULL, &raenv);
334 /******************************************************************************
336 \ \ / / | | |__ \ \ \ / /
337 \ \ / /_ _| |_ _ ___ ___ ) | \ \ / /_ _ _ __
338 \ \/ / _` | | | | |/ _ \/ __| / / \ \/ / _` | '__|
339 \ / (_| | | |_| | __/\__ \ / /_ \ / (_| | |
340 \/ \__,_|_|\__,_|\___||___/ |____| \/ \__,_|_|
341 *****************************************************************************/
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);