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  * The external register allocator is a program taking 2 arguments:
  10  *   1) An input file in which the cfg is defined
  11  *   2) An output file containing the essential actions performed during allocation
  12  */
  13
  14 #if 0
  15 ===============================================================================
  16 ===============================================================================
  17
  18 The input file format
  19 ----------------------
  20
  21 inputfile       ::= regs cfg .
  22
  23 regs            ::= 'regs' regcount .                                           // Anzahl der register (0..regcount-1), die zur Verfuegung stehen
  24
  25 cfg                     ::= 'cfg' ident '{' block* edge* '}' .          // Steuerflussgraph der Prozedur
  26
  27 block           ::= 'block' block-nr '{' insn* '}' .            // Grundblock im cfg versehen mit einer nummer
  28
  29 edge            ::= 'cf-edge' block-nr block-nr .                       // Steuerflusskante src-->tgt
  30
  31 insn            ::= gen-insn                                                            // Befehl in einem block
  32                           | copy-insn
  33
  34 gen-insn        ::= 'insn' insn-nr '{' uses defs '}' .
  35 copy-insn       ::= 'copy' insn-nr '{' uses defs '}' .
  36
  37 defs            ::= 'def' var-list .                                            // Liste der definierten/verwendeten Variablen
  38 uses            ::= 'use' var-list .
  39
  40 var-list        ::= var-ref
  41                           | var-ref var-list
  42
  43 var-ref         ::= var-nr
  44                           | var-nr '<' reg-nr '>' .                                     // reg-nr gibt register constraint an.
  45
  46
  47 ident           ::= non-whitespace-char*
  48 regcount, block-nr, insn-nr, reg-nr, var-nr ::= integer
  49
  50 ===============================================================================
  51 ===============================================================================
  52
  53 The output file format
  54 -----------------------
  55
  56 outputfile      ::= 'actions' '{' action-list '}'
  57 TODO
  58
  59 ===============================================================================
  60 ===============================================================================
  61 #endif /* documentation of file formats */
  62
  63 #ifdef HAVE_CONFIG_H
  64 #include "config.h"
  65 #endif
  66
  67 #ifdef WIN32
  68 #include <malloc.h>
  69 #else
  70 #include <alloca.h>
  71 #endif
  72
  73 #include <stdio.h>
  74 #include <stdlib.h>
  75
  76 #include "pmap.h"
  77 #include "pset.h"
  78 #include "bitset.h"
  79
  80 #include "irprintf_t.h"
  81 #include "irnode_t.h"
  82 #include "irgraph_t.h"
  83 #include "irgwalk.h"
  84 #include "phiclass.h"
  85
  86 #include "beraextern.h"
  87 #include "bearch.h"
  88 #include "benode_t.h"
  89 #include "besched.h"
  90 #include "beutil.h"
  91
  92 typedef struct _be_raext_env_t {
  93         arch_env_t *aenv;
  94         const arch_register_class_t *cls;
  95         ir_graph *irg;
  96
  97         FILE *f;                /**< file handle used for out- and input file */
  98         pmap *vars;             /**< maps variable numbers (int) to the corresponding SSA-values (pset of irns) */
  99         pmap *blocks;   /**< maps block numbers (int) to the block (ir_node*) having that node_nr */
 100 } be_raext_env_t;
 101
 102
 103 /**
 104  * Some little helpers
 105  */
 106 #define pmap_insert_sth(pmap, key, val) pmap_insert(pmap, (void *)key, (void *)val)
 107 #define pmap_get_sth(pmap, key)                 pmap_get(pmap, (void *)key)
 108 #define set_var_nr(irn, nr)                             set_irn_link(irn, INT_TO_PTR(nr))
 109 #define get_var_nr(irn)                                 (PTR_TO_INT(get_irn_link(irn)))
 110
 111
 112 /**
 113  * Checks if _the_ result of the irn belongs to the
 114  * current register class (raenv->cls)
 115  * NOTE: Only the first result is checked.
 116  */
 117 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
 118
 119
 120 /**
 121  * Checks if the irn uses or defines values of the
 122  * current register class (raenv->cls)
 123  */
 124 static INLINE int is_sth_in_reg_class(be_raext_env_t *raenv, const ir_node *irn) {
 125         int max, i;
 126
 127         /* check arguments */
 128         for (i=0, max=get_irn_arity(irn); i<max; ++i)
 129                 if (arch_irn_has_reg_class(raenv->aenv, get_irn_n(irn, i), -1, raenv->cls))
 130                         return 1;
 131
 132         /* check result(s) */
 133         if (get_irn_mode(irn) == mode_T) {
 134                 ir_node *proj;
 135                 for (proj = sched_next(irn); is_Proj(proj); proj = sched_next(proj))
 136                         if (arch_irn_has_reg_class(raenv->aenv, proj, -1, raenv->cls))
 137                                 return 1;
 138                 return 0;
 139         } else {
 140                 return arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls);
 141         }
 142
 143         assert(0 && "Where did you come from???");
 144 }
 145
 146
 147 /**
 148  * Perform simple SSA-destruction with copies
 149  * TODO: Phi-Swap-Problem
 150  */
 151 static void ssa_destr_simple(ir_node *blk, void *env) {
 152         be_raext_env_t *raenv = env;
 153         ir_node *phi;
 154
 155         /* for all phi nodes (which are scheduled at first) */
 156         sched_foreach(blk, phi) {
 157                 int i, max;
 158                 const arch_register_class_t *cls;
 159
 160                 if (!is_Phi(phi))
 161                         break;
 162
 163                 cls = arch_get_irn_reg_class(raenv->aenv, phi, -1);
 164
 165                 /* for all args of these phis */
 166                 for (i=0, max=get_irn_arity(phi); i<max; ++i) {
 167                         ir_node *arg = get_irn_n(phi, i);
 168                         ir_node *pred_blk = get_Block_cfgpred_block(blk, i);
 169                         ir_node *cpy = be_new_Copy(cls, raenv->irg, pred_blk, arg);
 170                         set_irn_n(phi, i, cpy);
 171                         sched_add_before(pred_blk, cpy);
 172                 }
 173         }
 174 }
 175
 176
 177 /**
 178  * Define variables (numbers) for all SSA-values.
 179  * All values in a phi class get assigned the same variable name.
 180  * The link field maps values to the var-name
 181  */
 182 static void values_to_vars(ir_node *irn, void *env) {
 183         be_raext_env_t *raenv = env;
 184         ir_node *n;
 185         int nr;
 186         pset *vals;
 187
 188         vals = get_phi_class(irn);
 189
 190         if (!vals) {
 191                 /* not a phi class member, value == var */
 192                 vals = pset_new_ptr(1);
 193                 pset_insert_ptr(vals, irn);
 194         }
 195
 196         /* value to var mapping */
 197         n = pset_first(vals);
 198         nr = get_irn_node_nr(n);
 199         for (; n; n=pset_next(vals))
 200                 set_var_nr(irn, nr);
 201
 202         /* var to values mapping */
 203         pmap_insert_sth(raenv->vars, nr, vals);
 204 }
 205
 206 /**
 207  * Check if node irn has a limited-constraint at position pos.
 208  * If yes, dump it to FILE raenv->f
 209  */
 210 static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
 211         bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
 212         arch_register_req_t req;
 213
 214         arch_get_register_req(raenv->aenv, &req, irn, pos);
 215         if (arch_register_req_is(&req, limited)) {
 216                 int reg_nr;
 217                 req.limited(irn, pos, bs);
 218                 reg_nr = bitset_next_set(bs, 0);
 219                 fprintf(raenv->f, " <%d>", reg_nr);
 220                 assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
 221         }
 222 }
 223
 224
 225 /**
 226  * Dump all blocks and instructions in that block
 227  */
 228 static void dump_blocks(ir_node *blk, void *env) {
 229         be_raext_env_t *raenv = env;
 230         ir_node *irn;
 231         FILE *f = raenv->f;
 232         int nr = get_irn_node_nr(blk);
 233
 234         pmap_insert_sth(raenv->blocks, nr, blk);
 235
 236         /* begin block scope */
 237         fprintf(f, "\n");
 238         fprintf(f, "  block %d {\n", nr);
 239
 240         /* for each instruction */
 241         for(irn=sched_first(blk); !sched_is_end(irn); irn=sched_next(irn)) {
 242                 int max, i;
 243                 if (is_Phi(irn) || !is_sth_in_reg_class(raenv, irn))
 244                         continue;
 245
 246                 fprintf(f, "    insn %ld {\n", get_irn_node_nr(irn));
 247
 248                         /*
 249                          * print all uses
 250                          */
 251                         fprintf(f, "      use");
 252                         for (i=0, max=get_irn_arity(irn); i<max; ++i) {
 253                                 ir_node *arg = get_irn_n(irn, i);
 254                                 if (arch_irn_has_reg_class(raenv->aenv, arg, -1, raenv->cls)) {
 255                                         fprintf(f, " %d", get_var_nr(arg));
 256                                         dump_constraint(raenv, irn, i);
 257                                 }
 258                         }
 259                         fprintf(f,"\n");
 260
 261                         /*
 262                          * print all defs
 263                          */
 264                         fprintf(f, "      def");
 265                         /* special handling of projs */
 266                         if (get_irn_mode(irn) == mode_T) {
 267                                 for (irn = sched_next(irn); is_Proj(irn); irn = sched_next(irn))
 268                                         if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
 269                                                 fprintf(f, " %d", get_var_nr(irn));
 270                                                 dump_constraint(raenv, irn, -1);
 271                                         }
 272                                 irn = sched_prev(irn); /* for outer loop */
 273                         } else {
 274                                 if (arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)) {
 275                                         fprintf(f, " %d", get_var_nr(irn));
 276                                         dump_constraint(raenv, irn, -1);
 277                                 }
 278                         }
 279                         fprintf(f,"\n");
 280
 281                 fprintf(f, "    }\n");
 282         }
 283
 284         /* end the block scope */
 285         fprintf(f, "  }\n");
 286 }
 287
 288
 289 /**
 290  * Dump all control flow edges of this irg
 291  */
 292 static void dump_edges(ir_node *blk, void *env) {
 293         be_raext_env_t *raenv = env;
 294         int i, max;
 295
 296         if (get_irg_start_block(get_irn_irg(blk)) == blk)
 297                 return;
 298
 299         /* dump cf edges in the flow-order "pred succ" */
 300         for (i=0, max=get_irn_arity(blk); i<max; ++i) {
 301                 ir_node *pred = get_Block_cfgpred_block(blk, i);
 302                 fprintf(raenv->f, "  cf_edge %ld %ld\n", get_irn_node_nr(pred), get_irn_node_nr(blk));
 303         }
 304 }
 305
 306
 307 /**
 308  * Dump all information needed by the external
 309  * register allocator to a single file.
 310  */
 311 static void dump_to_file(be_raext_env_t *raenv, char *filename) {
 312         FILE *f;
 313
 314         if (!(f = fopen(filename, "wt"))) {
 315                 fprintf(stderr, "Could not open file %s for writing\n", filename);
 316                 exit(1);
 317         }
 318         raenv->f = f;
 319
 320         fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
 321         fprintf(f, "cfg %s {\n", filename);
 322
 323         irg_block_walk_graph(raenv->irg, NULL, dump_blocks, raenv);
 324         irg_block_walk_graph(raenv->irg, NULL, dump_edges, raenv);
 325
 326         fprintf(f, "}\n");
 327
 328         fclose(f);
 329 }
 330
 331
 332 /**
 333  * Execute the external register allocator specified in the
 334  * firm-option TODO
 335  */
 336 static void execute(char *out_file, char *result_file) {
 337         char cmd_line[1024];
 338         char *app_name = "echo"; //TODO get from firm-options file
 339         int ret_status;
 340
 341         snprintf(cmd_line, sizeof(cmd_line), "%s %s %s", app_name, out_file, result_file);
 342
 343         ret_status = system(cmd_line);
 344         assert(ret_status != -1 && "Invokation of external register allocator failed");
 345 }
 346
 347
 348 /**
 349  * Read in the actions performed by the external allocator.
 350  * Apply these transformations to the irg->
 351  */
 352 static void read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 353         FILE *f;
 354
 355         if (!(f = fopen(filename, "rt"))) {
 356                 fprintf(stderr, "Could not open file %s for reading\n", filename);
 357                 exit(1);
 358         }
 359         raenv->f = f;
 360
 361         //TODO: free pmap entries (the psets) pmap_foreach(raenv.vars, pme)     del_pset(pme->value);
 362
 363         fclose(f);
 364 }
 365
 366
 367 /**
 368  * Allocate registers with an external program using a text-file interface.
 369  *
 370  * Do some computations (SSA-destruction and mapping of values--vars)
 371  * Write file
 372  * Execute external program
 373  * Read in results and apply them
 374  *
 375  */
 376 static void be_ra_extern_main(const be_main_env_t *env, ir_graph *irg) {
 377         be_raext_env_t raenv;
 378         int clsnr, clss;
 379
 380         raenv.irg = irg;
 381         raenv.aenv = env->arch_env;
 382         raenv.vars = pmap_create();
 383         raenv.blocks = pmap_create();
 384
 385         /* SSA destruction */
 386         be_clear_links(irg);
 387         irg_block_walk_graph(irg, ssa_destr_simple, NULL, &raenv);
 388         phi_class_compute(irg);
 389         irg_walk_graph(irg, values_to_vars, NULL, &raenv);
 390
 391         dump_ir_block_graph_sched(irg, "-extern-ssadestr");
 392
 393         /* For all register classes */
 394         for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
 395                 char out[256], in[256];
 396
 397                 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
 398                 ir_snprintf(out, sizeof(out), "%F-%s.ra", irg, raenv.cls->name);
 399                 ir_snprintf(in, sizeof(in), "%F-%s.ra.res", irg, raenv.cls->name);
 400
 401                 dump_to_file(&raenv, out);
 402
 403                 execute(out, in);
 404
 405                 read_and_apply_results(&raenv, in);
 406         }
 407
 408         /* Clean up */
 409         pmap_destroy(raenv.blocks);
 410         pmap_destroy(raenv.vars);
 411 }
 412
 413
 414 #ifdef WITH_LIBCORE
 415 static void be_ra_extern_register_options(lc_opt_entry_t *grp) {
 416         /* TODO */
 417 }
 418 #endif
 419
 420 const be_ra_t be_ra_external_allocator = {
 421 #ifdef WITH_LIBCORE
 422         be_ra_extern_register_options,
 423 #endif
 424         be_ra_extern_main
 425 };