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
18 #include "irgraph_t.h"
22 #include "beraextern.h"
28 typedef struct _be_raext_env_t {
30 const arch_register_class_t *cls;
31 be_node_factory_t *fact;
42 #define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val)
43 #define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key)
45 #define set_var_nr(irn, nr) set_irn_link(irn, (void *)nr)
46 #define get_var_nr(irn) ((int)get_irn_link(irn))
48 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
50 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
54 for (i=0, max=get_irn_arity(irn); i<max; ++i)
55 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
59 if (get_irn_mode(irn) == mode_T) {
61 for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
62 if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
66 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
69 assert(0 && "Where did you come from???");
74 static void be_ra_extern_register_options(lc_opt_entry_t *grp) {
81 * Perform simple SSA-destruction with copies
82 * TODO: Phi-Swap-Problem
84 static void ssa_destr_simple(ir_node *blk, void *env) {
85 be_raext_env_t *raenv = env;
88 /* for all phi nodes (which are scheduled at first) */
89 sched_foreach(blk, phi) {
95 if (!is_res_in_reg_class(phi))
98 /* for all args of these phis */
99 for (i=0, max=get_irn_arity(phi); i<max; ++i) {
100 ir_node *arg = get_irn_n(phi, i);
101 ir_node *pred_blk = get_Block_cfgpred_block(blk, i);
102 ir_node *cpy = new_Copy(raenv->fact, raenv->cls, raenv->irg, pred_blk, arg);
103 set_irn_n(phi, i, cpy);
104 sched_add_before(pred_blk, cpy);
111 * Define variables (numbers) for all SSA-values.
112 * All values in a phi class get assigned the same variable name.
113 * The link field maps values to the var-name
115 static void values_to_vars(ir_node *irn, void *env) {
116 be_raext_env_t *raenv = env;
120 if (!is_sth_in_reg_class(raenv, irn))
123 vals = get_phi_class(irn);
126 /* not a phi class member, value == var */
127 vals = pset_new_ptr(1);
128 pset_insert_ptr(vals, irn);
131 /* value to var mapping */
132 for (n=pset_first(vals); n; n=pset_next(vals))
133 set_var_nr(irn, raenv->next_var_nr);
135 /* var to values mapping */
136 pmap_insert_sth(raenv->vars, raenv->next_var_nr, vals);
137 raenv->next_var_nr++;
142 * Dump all blocks and instructions in that block
144 static void dump_blocks(ir_node *blk, void *env) {
145 be_raext_env_t *raenv = env;
148 int nr = get_irn_node_nr(blk);
149 pmap_insert_sth(raenv->blocks, nr, blk);
151 /* begin block scope */
153 fprintf(f, " block %d {\n", nr);
155 /* for each instruction */
156 for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
158 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
161 fprintf(f, " insn {\n");
167 if (get_irn_mode(irn) == mode_T) {
168 for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn))
169 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls))
170 fprintf(f, " %d", get_var_nr(irn));
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);
221 fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
222 fprintf(f, "cfg %s {\n", "noname");
224 fprintf(f, " variables %d\n", pmap_count(raenv->vars));
225 irg_block_walk_graph(raenv->irg, dump_blocks, NULL, raenv);
226 irg_block_walk_graph(raenv->irg, dump_edges, NULL, raenv);
235 * Allocate registers with an external program using a text-file interface.
237 * Do some computations (SSA-destruction and mapping of values--vars)
239 * Execute external program
240 * Read in results and apply them
243 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
244 be_raext_env_t raenv;
248 raenv.fact = env->node_factory;
249 raenv.aenv = env->arch_env;
251 /* For all register classes */
252 for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
255 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
256 raenv.vars = pmap_create();
257 raenv.blocks = pmap_create();
258 raenv.next_var_nr = 0;
260 /* SSA destruction */
262 irg_block_walk_graph(irg, ssa_destr_simple, NULL, &raenv);
263 phi_class_compute(irg);
264 irg_walk_graph(irg, values_to_vars, NULL, &raenv);
268 dump_file(&raenv, out);
273 /* Read in results and apply them */
274 //apply_results(&raenv, in);
275 //NOTE: free pmap entries (the psets) pmap_foreach(raenv.vars, pme) del_pset(pme->value);
278 /* Clean up for this register class */
279 pmap_destroy(raenv.blocks);
280 pmap_destroy(raenv.vars);
285 const be_ra_t be_ra_chordal_allocator = {
287 be_ra_extern_register_options,