nsz Git - libfirm/blob - ir/be/beraextern.c

   1 /**
   2  * Author:      Daniel Grund
   3  * Date:                17.01.2006
   4  * Copyright:   (c) Universitaet Karlsruhe
   5  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
   6  *
   7  * Implementation of the RA-Interface for an external, (non-SSA) register allocator
   8  */
   9
  10 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif
  13
  14 #include "pmap.h"
  15 #include "pset.h"
  16
  17 #include "irnode_t.h"
  18 #include "irgraph_t.h"
  19 #include "irgwalk.h"
  20 #include "phiclass.h"
  21
  22 #include "beraextern.h"
  23 #include "bearch.h"
  24 #include "benode_t.h"
  25 #include "besched.h"
  26 #include "beutil.h"
  27
  28 typedef struct _be_raext_env_t {
  29         arch_env_t *aenv;
  30         const arch_register_class_t *cls;
  31         be_node_factory_t *fact;
  32         ir_graph *irg;
  33
  34         FILE *f;
  35         int next_var_nr;
  36         pmap *vars;
  37         pmap *blocks;
  38 } be_raext_env_t;
  39
  40
  41 /* Helpers */
  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)
  44
  45 #define set_var_nr(irn, nr)                             set_irn_link(irn, (void *)nr)
  46 #define get_var_nr(irn)                                 ((int)get_irn_link(irn))
  47
  48 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
  49
  50 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
  51         int max, i;
  52
  53         /* check arguments */
  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))
  56                         return 1;
  57
  58         /* check result(s) */
  59         if (get_irn_mode(irn) == mode_T) {
  60                 ir_node *proj;
  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))
  63                                 return 1;
  64                 return 0;
  65         } else {
  66                 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
  67         }
  68
  69         assert(0 && "Where did you come from???");
  70 }
  71
  72
  73 #ifdef WITH_LIBCORE
  74 static void be_ra_extern_register_options(lc_opt_entry_t *grp) {
  75         /* TODO */
  76 }
  77 #endif
  78
  79
  80 /**
  81  * Perform simple SSA-destruction with copies
  82  * TODO: Phi-Swap-Problem
  83  */
  84 static void ssa_destr_simple(ir_node *blk, void *env) {
  85         be_raext_env_t *raenv = env;
  86         ir_node *phi;
  87
  88         /* for all phi nodes (which are scheduled at first) */
  89         sched_foreach(blk, phi) {
  90                 int i, max;
  91
  92                 if (!is_Phi(phi))
  93                         break;
  94
  95                 if (!is_res_in_reg_class(phi))
  96                         continue;
  97
  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);
 105                 }
 106         }
 107 }
 108
 109
 110 /**
 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
 114  */
 115 static void values_to_vars(ir_node *irn, void *env) {
 116         be_raext_env_t *raenv = env;
 117         ir_node *n;
 118         pset *vals;
 119
 120         if (!is_sth_in_reg_class(raenv, irn))
 121                 return;
 122
 123         vals = get_phi_class(irn);
 124
 125         if (!vals) {
 126                 /* not a phi class member, value == var */
 127                 vals = pset_new_ptr(1);
 128                 pset_insert_ptr(vals, irn);
 129         }
 130
 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);
 134
 135         /* var to values mapping */
 136         pmap_insert_sth(raenv->vars, raenv->next_var_nr, vals);
 137         raenv->next_var_nr++;
 138 }
 139
 140
 141 /**
 142  * Dump all blocks and instructions in that block
 143  */
 144 static void dump_blocks(ir_node *blk, void *env) {
 145         be_raext_env_t *raenv = env;
 146         ir_node *irn;
 147         FILE *f = raenv->f;
 148         int nr = get_irn_node_nr(blk);
 149         pmap_insert_sth(raenv->blocks, nr, blk);
 150
 151         /* begin block scope */
 152         fprintf(f, "\n");
 153         fprintf(f, "  block %d {\n", nr);
 154
 155         /* for each instruction */
 156         for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
 157                 int max, i;
 158                 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
 159                         continue;
 160
 161                 fprintf(f, "    insn {\n");
 162
 163                         /*
 164                          * print all defs
 165                          */
 166                         fprintf(f, "      def");
 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));
 171                         } else {
 172                                 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls))
 173                                         fprintf(f, " %d", get_var_nr(irn));
 174                         }
 175                         fprintf(f,"\n");
 176
 177                         /*
 178                          * print all uses
 179                          */
 180                         fprintf(f, "      use");
 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));
 184                         fprintf(f,"\n");
 185
 186                 fprintf(f, "    }\n");
 187         }
 188
 189         /* end the block scope */
 190         fprintf(f, "  }\n", nr);
 191 }
 192
 193
 194 /**
 195  * Dump all control flow edges of this irg
 196  */
 197 static void dump_edges(ir_node *blk, void *env) {
 198         be_raext_env_t *raenv = env;
 199         int i, max;
 200
 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));
 205         }
 206 }
 207
 208
 209 /**
 210  * Dump all information needed by the external
 211  * register allocator to a single file.
 212  */
 213 static void dump_file(be_raext_env_t *raenv, char *filename) {
 214         FILE *f;
 215
 216         if (!(f = fopen(filename, "wt"))) {
 217                 fprintf(stderr, "Could not open file %s\n", filename);
 218                 exit(1);
 219         }
 220
 221         fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
 222         fprintf(f, "cfg %s {\n", "noname");
 223
 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);
 227
 228         fprintf(f, "}\n");
 229
 230         fclose(f);
 231 }
 232
 233
 234 /**
 235  * Allocate registers with an external program using a text-file interface.
 236  *
 237  * Do some computations (SSA-destruction and mapping of values--vars)
 238  * Write file
 239  * Execute external program
 240  * Read in results and apply them
 241  *
 242  */
 243 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
 244         be_raext_env_t raenv;
 245         int clsnr, clss;
 246
 247         raenv.irg = irg;
 248         raenv.fact = env->node_factory;
 249         raenv.aenv = env->arch_env;
 250
 251         /* For all register classes */
 252         for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
 253                 char *out, *in;
 254
 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;
 259
 260                 /* SSA destruction */
 261                 be_clear_links(irg);
 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);
 265
 266                 /* Write file */
 267                 out = "trallala";
 268                 dump_file(&raenv, out);
 269
 270                 /* Call */
 271                 //execute(out, in);
 272
 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);
 276
 277
 278                 /* Clean up for this register class */
 279                 pmap_destroy(raenv.blocks);
 280                 pmap_destroy(raenv.vars);
 281         }
 282 }
 283
 284
 285 const be_ra_t be_ra_chordal_allocator = {
 286 #ifdef WITH_LIBCORE
 287         be_ra_extern_register_options,
 288 #endif
 289         be_ra_extern_main
 290 };