From 818de80bfca25a30635a76bd9945792a495d26f8 Mon Sep 17 00:00:00 2001 From: Daniel Grund Date: Wed, 18 Jan 2006 17:40:33 +0000 Subject: [PATCH] Added unfinished and buggy implementation of the ra-interface for an external allocator. --- ir/be/bemain.c | 27 +++-- ir/be/beraextern.c | 290 +++++++++++++++++++++++++++++++++++++++++++++ ir/be/beraextern.h | 17 +++ 3 files changed, 321 insertions(+), 13 deletions(-) create mode 100644 ir/be/beraextern.c create mode 100644 ir/be/beraextern.h diff --git a/ir/be/bemain.c b/ir/be/bemain.c index 2d2b8d4cb..80983c4af 100644 --- a/ir/be/bemain.c +++ b/ir/be/bemain.c @@ -27,28 +27,29 @@ #include "irloop_t.h" #include "irtools.h" +#include "bearch.h" +#include "firm/bearch_firm.h" +#include "ia32/bearch_ia32.h" + #include "be_t.h" -#include "bechordal_t.h" -#include "bera.h" -#include "beifg.h" -#include "beifg_impl.h" #include "benumb_t.h" +#include "beutil.h" +#include "benode_t.h" +#include "beirgmod.h" #include "besched_t.h" #include "belistsched.h" #include "belive_t.h" -#include "beutil.h" -#include "bechordal.h" -#include "bearch.h" +#include "bespillilp.h" +#include "bespillbelady.h" +#include "bera.h" +#include "beraextern.h" +#include "bechordal_t.h" +#include "beifg.h" +#include "beifg_impl.h" #include "becopyoptmain.h" #include "becopystat.h" #include "bessadestr.h" -#include "benode_t.h" -#include "beirgmod.h" -#include "bespillilp.h" -#include "bespillbelady.h" -#include "firm/bearch_firm.h" -#include "ia32/bearch_ia32.h" #define DUMP_INITIAL (1 << 0) #define DUMP_SCHED (1 << 1) diff --git a/ir/be/beraextern.c b/ir/be/beraextern.c new file mode 100644 index 000000000..06d37f7ec --- /dev/null +++ b/ir/be/beraextern.c @@ -0,0 +1,290 @@ +/** + * Author: Daniel Grund + * Date: 17.01.2006 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * + * Implementation of the RA-Interface for an external, (non-SSA) register allocator + */ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#include "pmap.h" +#include "pset.h" + +#include "irnode_t.h" +#include "irgraph_t.h" +#include "irgwalk.h" +#include "phiclass.h" + +#include "beraextern.h" +#include "bearch.h" +#include "benode_t.h" +#include "besched.h" +#include "beutil.h" + +typedef struct _be_raext_env_t { + arch_env_t *aenv; + const arch_register_class_t *cls; + be_node_factory_t *fact; + ir_graph *irg; + + FILE *f; + int next_var_nr; + pmap *vars; + pmap *blocks; +} be_raext_env_t; + + +/* Helpers */ +#define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val) +#define pmap_get_sth(pmap, key) pmap_get(pmap, (void *)key) + +#define set_var_nr(irn, nr) set_irn_link(irn, (void *)nr) +#define get_var_nr(irn) ((int)get_irn_link(irn)) + +#define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls) + +static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) { + int max, i; + + /* check arguments */ + for (i=0, max=get_irn_arity(irn); iaenv, get_irn_n(irn, i), -1, raenv->cls)) + return 1; + + /* check result(s) */ + if (get_irn_mode(irn) == mode_T) { + ir_node *proj; + for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj)) + if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls)) + return 1; + return 0; + } else { + return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls); + } + + assert(0 && "Where did you come from???"); +} + + +#ifdef WITH_LIBCORE +static void be_ra_extern_register_options(lc_opt_entry_t *grp) { + /* TODO */ +} +#endif + + +/** + * Perform simple SSA-destruction with copies + * TODO: Phi-Swap-Problem + */ +static void ssa_destr_simple(ir_node *blk, void *env) { + be_raext_env_t *raenv = env; + ir_node *phi; + + /* for all phi nodes (which are scheduled at first) */ + sched_foreach(blk, phi) { + int i, max; + + if (!is_Phi(phi)) + break; + + if (!is_res_in_reg_class(phi)) + continue; + + /* for all args of these phis */ + for (i=0, max=get_irn_arity(phi); ifact, raenv->cls, raenv->irg, pred_blk, arg); + set_irn_n(phi, i, cpy); + sched_add_before(pred_blk, cpy); + } + } +} + + +/** + * Define variables (numbers) for all SSA-values. + * All values in a phi class get assigned the same variable name. + * The link field maps values to the var-name + */ +static void values_to_vars(ir_node *irn, void *env) { + be_raext_env_t *raenv = env; + ir_node *n; + pset *vals; + + if (!is_sth_in_reg_class(raenv, irn)) + return; + + vals = get_phi_class(irn); + + if (!vals) { + /* not a phi class member, value == var */ + vals = pset_new_ptr(1); + pset_insert_ptr(vals, irn); + } + + /* value to var mapping */ + for (n=pset_first(vals); n; n=pset_next(vals)) + set_var_nr(irn, raenv->next_var_nr); + + /* var to values mapping */ + pmap_insert_sth(raenv->vars, raenv->next_var_nr, vals); + raenv->next_var_nr++; +} + + +/** + * Dump all blocks and instructions in that block + */ +static void dump_blocks(ir_node *blk, void *env) { + be_raext_env_t *raenv = env; + ir_node *irn; + FILE *f = raenv->f; + int nr = get_irn_node_nr(blk); + pmap_insert_sth(raenv->blocks, nr, blk); + + /* begin block scope */ + fprintf(f, "\n"); + fprintf(f, " block %d {\n", nr); + + /* for each instruction */ + for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) { + int max, i; + if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn)) + continue; + + fprintf(f, " insn {\n"); + + /* + * print all defs + */ + fprintf(f, " def"); + if (get_irn_mode(irn) == mode_T) { + for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn)) + if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) + fprintf(f, " %d", get_var_nr(irn)); + } else { + if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) + fprintf(f, " %d", get_var_nr(irn)); + } + fprintf(f,"\n"); + + /* + * print all uses + */ + fprintf(f, " use"); + for (i=0, max=get_irn_arity(irn); iaenv, get_irn_n(irn, i), -1, raenv->cls)) + fprintf(f, " %d", get_var_nr(irn)); + fprintf(f,"\n"); + + fprintf(f, " }\n"); + } + + /* end the block scope */ + fprintf(f, " }\n", nr); +} + + +/** + * Dump all control flow edges of this irg + */ +static void dump_edges(ir_node *blk, void *env) { + be_raext_env_t *raenv = env; + int i, max; + + /* dump cf edges in the flow-order "pred succ" */ + for (i=0, max=get_irn_arity(blk); if, " cf_edge %d %d\n", get_irn_node_nr(pred), get_irn_node_nr(blk)); + } +} + + +/** + * Dump all information needed by the external + * register allocator to a single file. + */ +static void dump_file(be_raext_env_t *raenv, char *filename) { + FILE *f; + + if (!(f = fopen(filename, "wt"))) { + fprintf(stderr, "Could not open file %s\n", filename); + exit(1); + } + + fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls)); + fprintf(f, "cfg %s {\n", "noname"); + + fprintf(f, " variables %d\n", pmap_count(raenv->vars)); + irg_block_walk_graph(raenv->irg, dump_blocks, NULL, raenv); + irg_block_walk_graph(raenv->irg, dump_edges, NULL, raenv); + + fprintf(f, "}\n"); + + fclose(f); +} + + +/** + * Allocate registers with an external program using a text-file interface. + * + * Do some computations (SSA-destruction and mapping of values--vars) + * Write file + * Execute external program + * Read in results and apply them + * + */ +static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) { + be_raext_env_t raenv; + int clsnr, clss; + + raenv.irg = irg; + raenv.fact = env->node_factory; + raenv.aenv = env->arch_env; + + /* For all register classes */ + for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) { + char *out, *in; + + raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr); + raenv.vars = pmap_create(); + raenv.blocks = pmap_create(); + raenv.next_var_nr = 0; + + /* SSA destruction */ + be_clear_links(irg); + irg_block_walk_graph(irg, ssa_destr_simple, NULL, &raenv); + phi_class_compute(irg); + irg_walk_graph(irg, values_to_vars, NULL, &raenv); + + /* Write file */ + out = "trallala"; + dump_file(&raenv, out); + + /* Call */ + //execute(out, in); + + /* Read in results and apply them */ + //apply_results(&raenv, in); + //NOTE: free pmap entries (the psets) pmap_foreach(raenv.vars, pme) del_pset(pme->value); + + + /* Clean up for this register class */ + pmap_destroy(raenv.blocks); + pmap_destroy(raenv.vars); + } +} + + +const be_ra_t be_ra_chordal_allocator = { +#ifdef WITH_LIBCORE + be_ra_extern_register_options, +#endif + be_ra_extern_main +}; diff --git a/ir/be/beraextern.h b/ir/be/beraextern.h new file mode 100644 index 000000000..dcc42b94b --- /dev/null +++ b/ir/be/beraextern.h @@ -0,0 +1,17 @@ +/** + * Author: Daniel Grund + * Date: 17.01.2006 + * Copyright: (c) Universitaet Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * + * Implementation of the RA-Interface for an external, non-SSA register allocator + */ + +#ifndef _BERAEXTERN_H +#define _BERAEXTERN_H + +#include "bera.h" + +const be_ra_t be_ra_external_allocator; + +#endif \ No newline at end of file -- 2.20.1