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
15 ===============================================================================
16 ===============================================================================
19 ----------------------
21 inputfile ::= regs cfg .
23 regs ::= 'regs' regcount . // Anzahl der register (0..regcount-1), die zur Verfuegung stehen
25 cfg ::= 'cfg' ident '{' block* edge* '}' . // Steuerflussgraph der Prozedur
27 block ::= 'block' block-nr '{' insn* '}' . // Grundblock im cfg versehen mit einer nummer
29 edge ::= 'cf-edge' block-nr block-nr . // Steuerflusskante src-->tgt
31 insn ::= gen-insn // Befehl in einem block
34 gen-insn ::= 'insn' insn-nr '{' uses defs '}' .
35 copy-insn ::= 'copy' insn-nr '{' uses defs '}' .
37 defs ::= 'def' var-list . // Liste der definierten/verwendeten Variablen
38 uses ::= 'use' var-list .
44 | var-nr '<' reg-nr '>' . // reg-nr gibt register constraint an.
47 ident ::= non-whitespace-char*
48 regcount, block-nr, insn-nr, reg-nr, var-nr ::= integer
50 ===============================================================================
51 ===============================================================================
53 The output file format
54 -----------------------
56 outputfile ::= 'actions' '{' action-list '}'
59 ===============================================================================
60 ===============================================================================
61 #endif /* documentation of file formats */
80 #include "irprintf_t.h"
82 #include "irgraph_t.h"
86 #include "beraextern.h"
92 typedef struct _be_raext_env_t {
94 const arch_register_class_t *cls;
97 FILE *f; /**< file handle used for out- and input file */
98 pmap *vars; /**< maps variable numbers (int) to the corresponding SSA-values (pset of irns) */
99 pmap *blocks; /**< maps block numbers (int) to the block (ir_node*) having that node_nr */
104 * Some little helpers
106 #define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val)
107 #define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key)
108 #define set_var_nr(irn, nr) set_irn_link(irn, INT_TO_PTR(nr))
109 #define get_var_nr(irn) (PTR_TO_INT(get_irn_link(irn)))
113 * Checks if _the_ result of the irn belongs to the
114 * current register class (raenv->cls)
115 * NOTE: Only the first result is checked.
117 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
121 * Checks if the irn uses or defines values of the
122 * current register class (raenv->cls)
124 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
127 /* check arguments */
128 for (i=0, max=get_irn_arity(irn); i<max; ++i)
129 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
132 /* check result(s) */
133 if (get_irn_mode(irn) == mode_T) {
135 for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
136 if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
140 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
143 assert(0 && "Where did you come from???");
148 * Perform simple SSA-destruction with copies
149 * TODO: Phi-Swap-Problem
151 static void ssa_destr_simple(ir_node *blk, void *env) {
152 be_raext_env_t *raenv = env;
155 /* for all phi nodes (which are scheduled at first) */
156 sched_foreach(blk, phi) {
158 const arch_register_class_t *cls;
163 cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
165 /* for all args of these phis */
166 for (i=0, max=get_irn_arity(phi); i<max; ++i) {
167 ir_node *arg = get_irn_n(phi, i);
168 ir_node *pred_blk = get_Block_cfgpred_block(blk, i);
169 ir_node *cpy = be_new_Copy(cls, raenv->irg, pred_blk, arg);
170 set_irn_n(phi, i, cpy);
171 sched_add_before(pred_blk, cpy);
178 * Define variables (numbers) for all SSA-values.
179 * All values in a phi class get assigned the same variable name.
180 * The link field maps values to the var-name
182 static void values_to_vars(ir_node *irn, void *env) {
183 be_raext_env_t *raenv = env;
188 vals = get_phi_class(irn);
191 /* not a phi class member, value == var */
192 vals = pset_new_ptr(1);
193 pset_insert_ptr(vals, irn);
196 /* value to var mapping */
197 n = pset_first(vals);
198 nr = get_irn_node_nr(n);
199 for (; n; n=pset_next(vals))
202 /* var to values mapping */
203 pmap_insert_sth(raenv->vars, nr, vals);
207 * Check if node irn has a limited-constraint at position pos.
208 * If yes, dump it to FILE raenv->f
210 static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
211 bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
212 arch_register_req_t req;
214 arch_get_register_req(raenv->aenv, &req, irn, pos);
215 if (arch_register_req_is(&req, limited)) {
217 req.limited(irn, pos, bs);
218 reg_nr = bitset_next_set(bs, 0);
219 fprintf(raenv->f, " <%d>", reg_nr);
220 assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
226 * Dump all blocks and instructions in that block
228 static void dump_blocks(ir_node *blk, void *env) {
229 be_raext_env_t *raenv = env;
232 int nr = get_irn_node_nr(blk);
234 pmap_insert_sth(raenv->blocks, nr, blk);
236 /* begin block scope */
238 fprintf(f, " block %d {\n", nr);
240 /* for each instruction */
241 for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
243 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
246 fprintf(f, " insn %ld {\n", get_irn_node_nr(irn));
252 for (i=0, max=get_irn_arity(irn); i<max; ++i) {
253 ir_node *arg = get_irn_n(irn, i);
254 if (arch_irn_has_reg_class(raenv->aenv, arg, -1, raenv->cls)) {
255 fprintf(f, " %d", get_var_nr(arg));
256 dump_constraint(raenv, irn, i);
265 /* special handling of projs */
266 if (get_irn_mode(irn) == mode_T) {
267 for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn))
268 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
269 fprintf(f, " %d", get_var_nr(irn));
270 dump_constraint(raenv, irn, -1);
272 irn = sched_prev(irn); /* for outer loop */
274 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
275 fprintf(f, " %d", get_var_nr(irn));
276 dump_constraint(raenv, irn, -1);
284 /* end the block scope */
290 * Dump all control flow edges of this irg
292 static void dump_edges(ir_node *blk, void *env) {
293 be_raext_env_t *raenv = env;
296 if (get_irg_start_block(get_irn_irg(blk)) == blk)
299 /* dump cf edges in the flow-order "pred succ" */
300 for (i=0, max=get_irn_arity(blk); i<max; ++i) {
301 ir_node *pred = get_Block_cfgpred_block(blk, i);
302 fprintf(raenv->f, " cf_edge %ld %ld\n", get_irn_node_nr(pred), get_irn_node_nr(blk));
308 * Dump all information needed by the external
309 * register allocator to a single file.
311 static void dump_to_file(be_raext_env_t *raenv, char *filename) {
314 if (!(f = fopen(filename, "wt"))) {
315 fprintf(stderr, "Could not open file %s for writing\n", filename);
320 fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
321 fprintf(f, "cfg %s {\n", filename);
323 irg_block_walk_graph(raenv->irg, NULL, dump_blocks, raenv);
324 irg_block_walk_graph(raenv->irg, NULL, dump_edges, raenv);
333 * Execute the external register allocator specified in the
336 static void execute(char *out_file, char *result_file) {
338 char *app_name = "echo"; //TODO get from firm-options file
341 snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", app_name, out_file, result_file);
343 ret_status = system(cmd_line);
344 assert(ret_status != -1 && "Invokation of external register allocator failed");
349 * Read in the actions performed by the external allocator.
350 * Apply these transformations to the irg->
352 static void read_and_apply_results(be_raext_env_t *raenv, char *filename) {
355 if (!(f = fopen(filename, "rt"))) {
356 fprintf(stderr, "Could not open file %s for reading\n", filename);
361 //TODO: free pmap entries (the psets) pmap_foreach(raenv.vars, pme) del_pset(pme->value);
368 * Allocate registers with an external program using a text-file interface.
370 * Do some computations (SSA-destruction and mapping of values--vars)
372 * Execute external program
373 * Read in results and apply them
376 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
377 be_raext_env_t raenv;
381 raenv.aenv = env->arch_env;
382 raenv.vars = pmap_create();
383 raenv.blocks = pmap_create();
385 /* SSA destruction */
387 irg_block_walk_graph(irg, ssa_destr_simple, NULL, &raenv);
388 phi_class_compute(irg);
389 irg_walk_graph(irg, values_to_vars, NULL, &raenv);
391 dump_ir_block_graph_sched(irg, "-extern-ssadestr");
393 /* For all register classes */
394 for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
395 char out[256], in[256];
397 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
398 ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name);
399 ir_snprintf(in, sizeof(in), "%F-%s.ra.res", irg, raenv.cls->name);
401 dump_to_file(&raenv, out);
405 read_and_apply_results(&raenv, in);
409 pmap_destroy(raenv.blocks);
410 pmap_destroy(raenv.vars);
415 static void be_ra_extern_register_options(lc_opt_entry_t *grp) {
420 const be_ra_t be_ra_external_allocator = {
422 be_ra_extern_register_options,