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
17 #include "irprintf_t.h"
19 #include "irgraph_t.h"
23 #include "beraextern.h"
29 typedef struct _be_raext_env_t {
31 const arch_register_class_t *cls;
41 #define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val)
42 #define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key)
44 #define set_var_nr(irn, nr) set_irn_link(irn, INT_TO_PTR(nr))
45 #define get_var_nr(irn) (PTR_TO_INT(get_irn_link(irn)))
47 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
49 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
53 for (i=0, max=get_irn_arity(irn); i<max; ++i)
54 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
58 if (get_irn_mode(irn) == mode_T) {
60 for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
61 if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
65 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
68 assert(0 && "Where did you come from???");
73 static void be_ra_extern_register_options(lc_opt_entry_t *grp) {
80 * Perform simple SSA-destruction with copies
81 * TODO: Phi-Swap-Problem
83 static void ssa_destr_simple(ir_node *blk, void *env) {
84 be_raext_env_t *raenv = env;
87 /* for all phi nodes (which are scheduled at first) */
88 sched_foreach(blk, phi) {
90 const arch_register_class_t *cls;
95 cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
97 /* for all args of these phis */
98 for (i=0, max=get_irn_arity(phi); i<max; ++i) {
99 ir_node *arg = get_irn_n(phi, i);
100 ir_node *pred_blk = get_Block_cfgpred_block(blk, i);
101 ir_node *cpy = be_new_Copy(cls, raenv->irg, pred_blk, arg);
102 set_irn_n(phi, i, cpy);
103 sched_add_before(pred_blk, cpy);
110 * Define variables (numbers) for all SSA-values.
111 * All values in a phi class get assigned the same variable name.
112 * The link field maps values to the var-name
114 static void values_to_vars(ir_node *irn, void *env) {
115 be_raext_env_t *raenv = env;
119 if (!is_sth_in_reg_class(raenv, irn))
122 vals = get_phi_class(irn);
125 /* not a phi class member, value == var */
126 vals = pset_new_ptr(1);
127 pset_insert_ptr(vals, irn);
130 /* value to var mapping */
131 for (n=pset_first(vals); n; n=pset_next(vals))
132 set_var_nr(irn, raenv->next_var_nr);
134 /* var to values mapping */
135 pmap_insert_sth(raenv->vars, raenv->next_var_nr, vals);
136 raenv->next_var_nr++;
141 * Dump all blocks and instructions in that block
143 static void dump_blocks(ir_node *blk, void *env) {
144 be_raext_env_t *raenv = env;
147 int nr = get_irn_node_nr(blk);
148 pmap_insert_sth(raenv->blocks, nr, blk);
150 /* begin block scope */
152 fprintf(f, " block %d {\n", nr);
154 /* for each instruction */
155 for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
157 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
160 fprintf(f, " insn %d {\n", get_var_nr(irn));
166 if (get_irn_mode(irn) == mode_T) {
167 for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn))
168 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls))
169 fprintf(f, " %d", get_var_nr(irn));
170 irn = sched_prev(irn); /* for outer loop */
172 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls))
173 fprintf(f, " %d", get_var_nr(irn));
181 for (i=0, max=get_irn_arity(irn); i<max; ++i)
182 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
183 fprintf(f, " %d", get_var_nr(irn));
189 /* end the block scope */
190 fprintf(f, " }\n", nr);
195 * Dump all control flow edges of this irg
197 static void dump_edges(ir_node *blk, void *env) {
198 be_raext_env_t *raenv = env;
201 /* dump cf edges in the flow-order "pred succ" */
202 for (i=0, max=get_irn_arity(blk); i<max; ++i) {
203 ir_node *pred = get_Block_cfgpred_block(blk, i);
204 fprintf(raenv->f, " cf_edge %d %d\n", get_irn_node_nr(pred), get_irn_node_nr(blk));
210 * Dump all information needed by the external
211 * register allocator to a single file.
213 static void dump_file(be_raext_env_t *raenv, char *filename) {
216 if (!(f = fopen(filename, "wt"))) {
217 fprintf(stderr, "Could not open file %s\n", filename);
222 fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
223 fprintf(f, "cfg %s {\n", "noname");
225 fprintf(f, " variables %d\n", pmap_count(raenv->vars));
226 irg_block_walk_graph(raenv->irg, dump_blocks, NULL, raenv);
227 irg_block_walk_graph(raenv->irg, dump_edges, NULL, raenv);
236 * Allocate registers with an external program using a text-file interface.
238 * Do some computations (SSA-destruction and mapping of values--vars)
240 * Execute external program
241 * Read in results and apply them
244 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
245 be_raext_env_t raenv;
249 raenv.aenv = env->arch_env;
250 raenv.vars = pmap_create();
251 raenv.blocks = pmap_create();
252 raenv.next_var_nr = 0;
254 /* SSA destruction */
256 irg_block_walk_graph(irg, ssa_destr_simple, NULL, &raenv);
257 phi_class_compute(irg);
258 irg_walk_graph(irg, values_to_vars, NULL, &raenv);
260 dump_ir_block_graph_sched(irg, "-extern-ssadestr");
262 /* For all register classes */
263 for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
264 char out[256], in[256];
266 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
269 ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name);
270 dump_file(&raenv, out);
275 /* Read in results and apply them */
276 //apply_results(&raenv, in);
277 //NOTE: free pmap entries (the psets) pmap_foreach(raenv.vars, pme) del_pset(pme->value);
283 pmap_destroy(raenv.blocks);
284 pmap_destroy(raenv.vars);
288 const be_ra_t be_ra_external_allocator = {
290 be_ra_extern_register_options,