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 "irprintf_t.h"
  18 #include "irnode_t.h"
  19 #include "irgraph_t.h"
  20 #include "irgwalk.h"
  21 #include "phiclass.h"
  22
  23 #include "beraextern.h"
  24 #include "bearch.h"
  25 #include "benode_t.h"
  26 #include "besched.h"
  27 #include "beutil.h"
  28
  29 typedef struct _be_raext_env_t {
  30         arch_env_t *aenv;
  31         const arch_register_class_t *cls;
  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 /* Helpers */
  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)
  43
  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)))
  46
  47 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
  48
  49 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
  50         int max, i;
  51
  52         /* check arguments */
  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))
  55                         return 1;
  56
  57         /* check result(s) */
  58         if (get_irn_mode(irn) == mode_T) {
  59                 ir_node *proj;
  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))
  62                                 return 1;
  63                 return 0;
  64         } else {
  65                 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
  66         }
  67
  68         assert(0 && "Where did you come from???");
  69 }
  70
  71
  72 #ifdef WITH_LIBCORE
  73 static void be_ra_extern_register_options(lc_opt_entry_t *grp) {
  74         /* TODO */
  75 }
  76 #endif
  77
  78
  79 /**
  80  * Perform simple SSA-destruction with copies
  81  * TODO: Phi-Swap-Problem
  82  */
  83 static void ssa_destr_simple(ir_node *blk, void *env) {
  84         be_raext_env_t *raenv = env;
  85         ir_node *phi;
  86
  87         /* for all phi nodes (which are scheduled at first) */
  88         sched_foreach(blk, phi) {
  89                 int i, max;
  90                 const arch_register_class_t *cls;
  91
  92                 if (!is_Phi(phi))
  93                         break;
  94
  95                 cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
  96
  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);
 104                 }
 105         }
 106 }
 107
 108
 109 /**
 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
 113  */
 114 static void values_to_vars(ir_node *irn, void *env) {
 115         be_raext_env_t *raenv = env;
 116         ir_node *n;
 117         pset *vals;
 118
 119         if (!is_sth_in_reg_class(raenv, irn))
 120                 return;
 121
 122         vals = get_phi_class(irn);
 123
 124         if (!vals) {
 125                 /* not a phi class member, value == var */
 126                 vals = pset_new_ptr(1);
 127                 pset_insert_ptr(vals, irn);
 128         }
 129
 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);
 133
 134         /* var to values mapping */
 135         pmap_insert_sth(raenv->vars, raenv->next_var_nr, vals);
 136         raenv->next_var_nr++;
 137 }
 138
 139
 140 /**
 141  * Dump all blocks and instructions in that block
 142  */
 143 static void dump_blocks(ir_node *blk, void *env) {
 144         be_raext_env_t *raenv = env;
 145         ir_node *irn;
 146         FILE *f = raenv->f;
 147         int nr = get_irn_node_nr(blk);
 148         pmap_insert_sth(raenv->blocks, nr, blk);
 149
 150         /* begin block scope */
 151         fprintf(f, "\n");
 152         fprintf(f, "  block %d {\n", nr);
 153
 154         /* for each instruction */
 155         for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
 156                 int max, i;
 157                 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
 158                         continue;
 159
 160                 fprintf(f, "    insn %d {\n", get_var_nr(irn));
 161
 162                         /*
 163                          * print all defs
 164                          */
 165                         fprintf(f, "      def");
 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 */
 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         raenv->f = f;
 222         fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
 223         fprintf(f, "cfg %s {\n", "noname");
 224
 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);
 228
 229         fprintf(f, "}\n");
 230
 231         fclose(f);
 232 }
 233
 234
 235 /**
 236  * Allocate registers with an external program using a text-file interface.
 237  *
 238  * Do some computations (SSA-destruction and mapping of values--vars)
 239  * Write file
 240  * Execute external program
 241  * Read in results and apply them
 242  *
 243  */
 244 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
 245         be_raext_env_t raenv;
 246         int clsnr, clss;
 247
 248         raenv.irg = irg;
 249         raenv.aenv = env->arch_env;
 250         raenv.vars = pmap_create();
 251         raenv.blocks = pmap_create();
 252         raenv.next_var_nr = 0;
 253
 254         /* SSA destruction */
 255         be_clear_links(irg);
 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);
 259
 260         dump_ir_block_graph_sched(irg, "-extern-ssadestr");
 261
 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];
 265
 266                 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
 267
 268                 /* Write file */
 269                 ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name);
 270                 dump_file(&raenv, out);
 271
 272                 /* Call */
 273                 //execute(out, in);
 274
 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);
 278
 279
 280         }
 281
 282         /* Clean up */
 283         pmap_destroy(raenv.blocks);
 284         pmap_destroy(raenv.vars);
 285 }
 286
 287
 288 const be_ra_t be_ra_external_allocator = {
 289 #ifdef WITH_LIBCORE
 290         be_ra_extern_register_options,
 291 #endif
 292         be_ra_extern_main
 293 };