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:
  10  *    PROG -i INPUTFILE -o OUTPUTFILE
  11  *
  12  *   1) Input file defines the interference graph
  13  *   2) Output file contains the instructions to perform
  14  *
  15
  16
  17 The input file format
  18 ----------------------
  19
  20 inputfile       ::= regs nodes interf affinities .
  21
  22 regs            ::= 'regs' regcount .                                           // Anzahl der register (0..regcount-1), die zur Verfuegung stehen
  23
  24 nodes           ::= 'nodes' '{' node* '}' .                                     // All nodes in the graph
  25
  26 node            ::= node-info
  27                           | node-info '<' reg-nr '>' .                          // Reg-nr is present in case of constraints
  28
  29 node-info       ::= node-nr spill-costs .
  30
  31 interf          ::= 'interferences' '{' i-edge* '}' .           // Interference edges of the graph
  32
  33 i-edge          ::= '(' node-nr ',' node-nr ')' .
  34
  35 affinities      ::= 'affinities' '{' a-edge* '}' .                      // Affinity edges of the graph
  36
  37 a-edge          ::= '(' node-nr ',' node-nr ',' weight ')' .
  38
  39
  40 weight, regcount, node-nr ::= int32 .
  41 spill-costs ::= int32 .                                                                 // negative spill costs indicate unspillable
  42
  43 The output file format
  44 -----------------------
  45
  46 outputfile      ::= spills | allocs .
  47
  48 spills          ::= 'spills' node-nr+ .
  49
  50 allocs          ::= 'allocs' alloc* .
  51
  52 alloc           ::= node-nr reg-nr .
  53
  54
  55 ******** End of file format docu ********/
  56
  57 #ifdef HAVE_CONFIG_H
  58 #include "config.h"
  59 #endif
  60
  61 #ifdef HAVE_MALLOC_H
  62  #include <malloc.h>
  63 #endif
  64 #ifdef HAVE_ALLOCA_H
  65  #include <alloca.h>
  66 #endif
  67
  68 #include <stdio.h>
  69 #include <stdlib.h>
  70 #include <limits.h>
  71 #ifdef WITH_LIBCORE
  72 #include <libcore/lc_opts.h>
  73 #include <libcore/lc_opts_enum.h>
  74 #endif
  75
  76 #include "set.h"
  77 #include "pset.h"
  78 #include "pmap.h"
  79 #include "bitset.h"
  80
  81 #include "irprintf_t.h"
  82 #include "irnode_t.h"
  83 #include "irgraph_t.h"
  84 #include "irgwalk.h"
  85 #include "iredges_t.h"
  86 #include "irdom_t.h"
  87 #include "phiclass.h"
  88
  89 #include "beraextern.h"
  90 #include "beabi.h"
  91 #include "bearch.h"
  92 #include "benode_t.h"
  93 #include "beirgmod.h"
  94 #include "besched_t.h"
  95 #include "beutil.h"
  96 #include "belive_t.h"
  97 #include "beinsn_t.h"
  98
  99 #include "bessadestrsimple.h"
 100
 101 #define DBG_LEVEL 2
 102
 103 /**
 104  * Environment with all the needed stuff
 105  */
 106 typedef struct _be_raext_env_t {
 107         arch_env_t *aenv;
 108         const arch_register_class_t *cls;
 109         ir_graph *irg;
 110         dom_front_info_t *dom_info;
 111
 112         FILE *f;                                /**< file handle used for out- and input file */
 113         set *vars;                              /**< contains all be_var_info_t */
 114         int n_cls_vars;                 /**< length of the array cls_vars */
 115         be_var_info_t **cls_vars;       /**< only the var_infos for current cls. needed for double iterating */
 116         DEBUG_ONLY(firm_dbg_module_t *dbg;)
 117 } be_raext_env_t;
 118
 119
 120
 121 /******************************************************************************
 122     _    _      _
 123    | |  | |    | |
 124    | |__| | ___| |_ __   ___ _ __ ___
 125    |  __  |/ _ \ | '_ \ / _ \ '__/ __|
 126    | |  | |  __/ | |_) |  __/ |  \__ \
 127    |_|  |_|\___|_| .__/ \___|_|  |___/
 128                  | |
 129                  |_|
 130  *****************************************************************************/
 131
 132
 133 #define pset_foreach(pset, irn)  for(irn=pset_first(pset); irn; irn=pset_next(pset))
 134 #define set_foreach(set, e)  for(e=set_first(set); e; e=set_next(set))
 135
 136 /**
 137  * Checks if _the_ result of the irn belongs to the
 138  * current register class (raenv->cls)
 139  * NOTE: Only the first result is checked.
 140  */
 141 #define is_res_in_reg_class(irn) arch_irn_has_reg_class(raenv->aenv, irn, -1, raenv->cls)
 142
 143 static INLINE ir_node *get_first_non_phi(pset *s) {
 144         ir_node *irn;
 145
 146         pset_foreach(s, irn)
 147                 if (!is_Phi(irn)) {
 148                         pset_break(s);
 149                         return irn;
 150                 }
 151
 152         assert(0 && "There must be a non-phi-irn in this");
 153         return NULL;
 154 }
 155
 156 static INLINE ir_node *get_first_phi(pset *s) {
 157         ir_node *irn;
 158
 159         pset_foreach(s, irn)
 160                 if (is_Phi(irn)) {
 161                         pset_break(s);
 162                         return irn;
 163                 }
 164
 165         assert(0 && "There must be a phi in this");
 166         return NULL;
 167 }
 168
 169 static int get_loop_weight(ir_node *irn) {
 170         int cost = 0;
 171         ir_loop *loop = get_irn_loop(get_nodes_block(irn));
 172
 173         if (loop) {
 174                 int d = get_loop_depth(loop);
 175                 cost = d*d;
 176         }
 177         return cost+1;
 178 }
 179
 180 #define get_const_weight(irn) (1)
 181
 182 #define get_spill_weight(irn)    get_loop_weight(irn)
 183 #define get_reload_weight(irn)   get_loop_weight(irn)
 184 #define get_affinity_weight(irn) get_loop_weight(irn)
 185
 186 /******************************************************************************
 187     _____                _            _____            _
 188    / ____|              | |          / ____|          (_)
 189   | |     ___  _ __  ___| |_ _ __   | |     ___  _ __  _  ___  ___
 190   | |    / _ \| '_ \/ __| __| '__|  | |    / _ \| '_ \| |/ _ \/ __|
 191   | |___| (_) | | | \__ \ |_| |     | |___| (_) | |_) | |  __/\__ \
 192    \_____\___/|_| |_|___/\__|_|      \_____\___/| .__/|_|\___||___/
 193                                                 | |
 194                                                 |_|
 195  *****************************************************************************/
 196
 197 static void handle_constraints_insn(be_raext_env_t *env, be_insn_t *insn)
 198 {
 199         ir_node *bl = get_nodes_block(insn->irn);
 200         int i;
 201
 202         for(i = 0; i < insn->use_start; ++i) {
 203                 be_operand_t *op = &insn->ops[i];
 204
 205                 if(op->has_constraints) {
 206                         ir_node *cpy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
 207                         sched_add_before(insn->next_insn, cpy);
 208                         edges_reroute(op->carrier, cpy, env->irg);
 209                 }
 210         }
 211
 212         for(i = insn->use_start; i < insn->n_ops; ++i) {
 213                 be_operand_t *op = &insn->ops[i];
 214
 215                 if(op->has_constraints) {
 216                         ir_node *cpy = be_new_Copy(op->req.cls, env->irg, bl, op->carrier);
 217                         sched_add_before(insn->irn, cpy);
 218                         set_irn_n(insn->irn, op->pos, cpy);
 219                         be_set_constr_limited(cpy, BE_OUT_POS(0), &op->req);
 220                 }
 221         }
 222 }
 223
 224 static void handle_constraints_block(ir_node *bl, void *data)
 225 {
 226         be_raext_env_t *raenv = data;
 227         int active            = bl != get_irg_start_block(raenv->irg);
 228
 229         ir_node *irn;
 230         be_insn_env_t ie;
 231         struct obstack obst;
 232
 233         ie.cls           = raenv->cls;
 234         ie.aenv          = raenv->aenv;
 235         ie.obst          = &obst;
 236         ie.ignore_colors = NULL;
 237         obstack_init(&obst);
 238
 239         irn = sched_first(bl);
 240         while(!sched_is_end(irn)) {
 241                 be_insn_t *insn = be_scan_insn(&ie, irn);
 242
 243                 if(insn->has_constraints)
 244                         handle_constraints_insn(raenv, insn);
 245
 246                 if(be_is_Barrier(irn))
 247                         active = !active;
 248
 249                 irn = insn->next_insn;
 250                 obstack_free(&obst, insn);
 251         }
 252 }
 253
 254 static void handle_constraints(be_raext_env_t *raenv) {
 255         irg_block_walk_graph(raenv->irg, NULL, handle_constraints_block, raenv);
 256 }
 257
 258
 259
 260
 261 /******************************************************************************
 262     _____
 263    |  __ \
 264    | |  | |_   _ _ __ ___  _ __   ___ _ __
 265    | |  | | | | | '_ ` _ \| '_ \ / _ \ '__|
 266    | |__| | |_| | | | | | | |_) |  __/ |
 267    |_____/ \__,_|_| |_| |_| .__/ \___|_|
 268                           | |
 269                           |_|
 270  *****************************************************************************/
 271
 272
 273 static void extract_vars_of_cls(be_raext_env_t *raenv) {
 274         int count = 0;
 275         be_var_info_t *vi;
 276
 277         raenv->cls_vars = xmalloc(set_count(raenv->vars) * sizeof(*raenv->cls_vars));
 278         assert(raenv->cls_vars);
 279
 280         set_foreach(raenv->vars, vi)
 281                 if (is_res_in_reg_class(get_first_non_phi(vi->values)))
 282                         raenv->cls_vars[count++] = vi;
 283
 284         raenv->cls_vars = realloc(raenv->cls_vars, count * sizeof(*raenv->cls_vars));
 285         assert(raenv->cls_vars);
 286
 287         raenv->n_cls_vars = count;
 288 }
 289
 290
 291 /**
 292  * Check if node irn has a limited-constraint at position pos.
 293  * If yes, dump it to FILE raenv->f
 294  */
 295 static INLINE void dump_constraint(be_raext_env_t *raenv, ir_node *irn, int pos) {
 296         bitset_t *bs = bitset_alloca(raenv->cls->n_regs);
 297         arch_register_req_t req;
 298
 299         arch_get_register_req(raenv->aenv, &req, irn, pos);
 300         if (arch_register_req_is(&req, limited)) {
 301                 int reg_nr;
 302                 req.limited(req.limited_env, bs);
 303                 reg_nr = bitset_next_set(bs, 0);
 304                 fprintf(raenv->f, "<%d>", reg_nr);
 305                 assert(-1 == bitset_next_set(bs, reg_nr+1) && "Constraints with more than 1 possible register are not supported");
 306         }
 307 }
 308
 309 #define UNSPILLABLE -1
 310
 311 static INLINE int get_spill_costs(be_raext_env_t *raenv, be_var_info_t *vi) {
 312         ir_node *irn;
 313         int c_spills=0, c_reloads=0;
 314
 315         pset_foreach(vi->values, irn) {
 316                 if (arch_irn_is(raenv->aenv, irn, ignore) || be_is_Reload(irn)) {
 317                         pset_break(vi->values);
 318                         return UNSPILLABLE;
 319                 }
 320
 321                 if (is_Phi(irn)) {
 322                         /* number of reloads is the number of non-phi uses of all values of this var */
 323                         const ir_edge_t *edge;
 324                         foreach_out_edge(irn, edge)
 325                                 if (!is_Phi(edge->src))
 326                                         c_reloads += get_reload_weight(edge->src);
 327                 } else {
 328                         /* number of spills is the number of non-phi values for this var */
 329                         c_spills += get_spill_weight(irn);
 330                 }
 331         }
 332
 333         return c_spills + c_reloads;
 334 }
 335
 336 static void dump_nodes(be_raext_env_t *raenv) {
 337         FILE *f = raenv->f;
 338         int i;
 339
 340         fprintf(f, "\nnodes {\n");
 341
 342         for (i=0; i<raenv->n_cls_vars; ++i) {
 343                 be_var_info_t *vi = raenv->cls_vars[i];
 344
 345                 if (vi->var_nr == SET_REMOVED)
 346                         continue;
 347
 348                 fprintf(f, "%d %d", vi->var_nr, get_spill_costs(raenv, vi));
 349                 dump_constraint(raenv, get_first_non_phi(vi->values), -1);
 350                 fprintf(f, "\n");
 351         }
 352
 353         fprintf(f, "}\n");
 354         fflush(f);
 355 }
 356
 357
 358 static void dump_interferences(be_raext_env_t *raenv) {
 359         int i,o;
 360         be_var_info_t *vi1, *vi2;
 361         ir_node *irn1, *irn2;
 362         FILE *f = raenv->f;
 363
 364         fprintf(f, "\ninterferences {\n");
 365
 366         for (i=0; i<raenv->n_cls_vars; ++i) {
 367                 vi1 = raenv->cls_vars[i];
 368
 369                 if (vi1->var_nr == SET_REMOVED)
 370                         continue;
 371
 372                 for (o=i+1; o<raenv->n_cls_vars; ++o) {
 373                         vi2 = raenv->cls_vars[o];
 374
 375                         if (vi2->var_nr == SET_REMOVED)
 376                                 continue;
 377
 378                         pset_foreach(vi1->values, irn1)
 379                                 pset_foreach(vi2->values, irn2)
 380                                         if (values_interfere(irn1, irn2)) {
 381                                                 pset_break(vi1->values);
 382                                                 pset_break(vi2->values);
 383                                                 fprintf(f, "(%d, %d)\n", vi1->var_nr, vi2->var_nr);
 384                                                 goto NextVar;
 385                                         }
 386
 387 NextVar: ;
 388                 }
 389         }
 390         fprintf(f, "}\n");
 391 }
 392
 393 static void dump_affinities_walker(ir_node *irn, void *env) {
 394         be_raext_env_t *raenv = env;
 395         arch_register_req_t req;
 396         int pos, max;
 397         be_var_info_t *vi1, *vi2;
 398
 399         if (arch_get_irn_reg_class(raenv->aenv, irn, -1) != raenv->cls || arch_irn_is(raenv->aenv, irn, ignore))
 400                 return;
 401
 402         vi1 = be_get_var_info(irn);
 403
 404         /* copies have affinities */
 405         if (arch_irn_classify(raenv->aenv, irn) == arch_irn_class_copy) {
 406                 ir_node *other = be_get_Copy_op(irn);
 407
 408                 if (! arch_irn_is(raenv->aenv, other, ignore)) {
 409                         vi2 = be_get_var_info(other);
 410
 411                         fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
 412                 }
 413         }
 414
 415
 416         /* should_be_equal constraints are affinites */
 417         for (pos = 0, max = get_irn_arity(irn); pos<max; ++pos) {
 418                 arch_get_register_req(raenv->aenv, &req, irn, pos);
 419
 420                 if (arch_register_req_is(&req, should_be_same) && arch_irn_is(raenv->aenv, req.other_same, ignore)) {
 421                         vi2 = be_get_var_info(req.other_same);
 422
 423                         fprintf(raenv->f, "(%d, %d, %d)\n",  vi1->var_nr, vi2->var_nr, get_affinity_weight(irn));
 424                 }
 425         }
 426 }
 427
 428
 429 static void dump_affinities(be_raext_env_t *raenv) {
 430         fprintf(raenv->f, "\naffinities {\n");
 431         irg_walk_graph(raenv->irg, NULL, dump_affinities_walker, raenv);
 432         fprintf(raenv->f, "}\n");
 433 }
 434
 435 /**
 436  * Dump all information needed by the external
 437  * register allocator to a single file.
 438  */
 439 static void dump_to_file(be_raext_env_t *raenv, char *filename) {
 440         FILE *f;
 441
 442         if (!(f = fopen(filename, "wt"))) {
 443                 fprintf(stderr, "Could not open file %s for writing\n", filename);
 444                 assert(0);
 445                 exit(0xdeadbeef);
 446         }
 447         raenv->f = f;
 448
 449         /* dump register info */
 450         fprintf(f, "regs %d\n", arch_register_class_n_regs(raenv->cls));
 451
 452         /* dump the interference graph */
 453         dump_nodes(raenv);
 454         dump_interferences(raenv);
 455         dump_affinities(raenv);
 456
 457         fclose(f);
 458 }
 459
 460 /******************************************************************************
 461     ______                     _
 462    |  ____|                   | |
 463    | |__  __  _____  ___ _   _| |_ ___
 464    |  __| \ \/ / _ \/ __| | | | __/ _ \
 465    | |____ >  <  __/ (__| |_| | ||  __/
 466    |______/_/\_\___|\___|\__,_|\__\___|
 467  *****************************************************************************/
 468
 469 /**
 470  * Execute the external register allocator specified in the
 471  * firm-option firm.be.ra.ext.callee
 472  */
 473 static void execute(char *prog_to_call, char *out_file, char *result_file) {
 474         char cmd_line[1024];
 475         int ret_status;
 476
 477         snprintf(cmd_line, sizeof(cmd_line), "%s -i %s -o %s", prog_to_call, out_file, result_file);
 478
 479         ret_status = system(cmd_line);
 480         assert(ret_status != -1 && "Invokation of external register allocator failed");
 481         assert(ret_status == 0 && "External register allocator is unhappy with sth.");
 482 }
 483
 484 /******************************************************************************
 485                          _         _____                 _ _
 486        /\               | |       |  __ \               | | |
 487       /  \   _ __  _ __ | |_   _  | |__) |___  ___ _   _| | |_
 488      / /\ \ | '_ \| '_ \| | | | | |  _  // _ \/ __| | | | | __|
 489     / ____ \| |_) | |_) | | |_| | | | \ \  __/\__ \ |_| | | |_
 490    /_/    \_\ .__/| .__/|_|\__, | |_|  \_\___||___/\__,_|_|\__|
 491             | |   | |       __/ |
 492             |_|   |_|      |___/
 493  *****************************************************************************/
 494
 495 /**
 496  * Spill a variable and add reloads before all uses.
 497  */
 498 static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) {
 499         be_var_info_t *vi = be_var_find(raenv->vars, var_nr);
 500         ir_node *spill=NULL, *ctx, *irn;
 501         ir_mode *mode;
 502         const ir_edge_t *edge, *ne;
 503         pset *spills  = pset_new_ptr(4);        /* the spills of this variable */
 504         pset *reloads = pset_new_ptr(4);        /* the reloads of this variable */
 505         int new_size, n_spills, n_reloads;
 506
 507         assert(vi && "Variable nr does not exist!");
 508         assert(pset_count(vi->values) && "There are no values associated to this variable");
 509
 510         /* the spill context is set to an arbitrary node of the phi-class,
 511          * or the node itself if it is not member of a phi class
 512          */
 513         if (pset_count(vi->values) == 1)
 514                 ctx = get_first_non_phi(vi->values);
 515         else
 516                 ctx = get_first_phi(vi->values);
 517
 518         DBG((raenv->dbg, LEVEL_2, "Spill context: %+F\n", ctx));
 519
 520         /* for each value of this variable insert the spills */
 521         pset_foreach(vi->values, irn) {
 522                 if (is_Phi(irn)) {
 523                         sched_remove(irn);
 524                         continue;
 525                 }
 526
 527                 /* all ordinary nodes must be spilled */
 528                 DBG((raenv->dbg, LEVEL_2, "  spilling %+F\n", irn));
 529                 spill = be_spill(raenv->aenv, irn, ctx);
 530
 531                 /* remember the spill */
 532                 pset_insert_ptr(spills, spill);
 533         }
 534
 535         assert(spill && "There must be at least one non-phi-node");
 536
 537         mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val));
 538
 539         /* insert reloads and wire them arbitrary*/
 540         pset_foreach(vi->values, irn)
 541                 foreach_out_edge_safe(irn, edge, ne) {
 542                         ir_node *reload, *src = edge->src;
 543                         if (is_Phi(src) || be_is_Spill(src))
 544                                 continue;
 545
 546                         /* all real uses must be reloaded */
 547                         DBG((raenv->dbg, LEVEL_2, "  reloading before %+F\n", src));
 548                         reload = be_reload(raenv->aenv, raenv->cls, edge->src, mode, spill);
 549                         set_irn_n(edge->src, edge->pos, reload);
 550
 551                         /* remember the reload */
 552                         pset_insert_ptr(reloads, reload);
 553                 }
 554
 555         /* correct the reload->spill pointers... */
 556         be_ssa_constr_set(raenv->dom_info, spills);
 557
 558
 559         /****** correct the variable <--> values mapping: ******
 560          *
 561          *  - if we had a phi class it gets split into several new variables
 562          *  - all reloads are new variables
 563          */
 564         n_spills = pset_count(spills);
 565         n_reloads = pset_count(reloads);
 566
 567         /* first make room for new pointers in the cls_var array */
 568         new_size = raenv->n_cls_vars + n_reloads + ((n_spills>1) ? n_spills : 0);
 569         raenv->cls_vars = realloc(raenv->cls_vars, (new_size) * sizeof(*raenv->cls_vars));
 570         assert(raenv->cls_vars && "Out of mem!?");
 571
 572         /* if we had a real phi-class, we must... */
 573         if (pset_count(spills) > 1) {
 574                 /* ...remove the old variable corresponding to the phi class */
 575                 vi->var_nr = SET_REMOVED;
 576
 577                 /* ...add new vars for each non-phi-member */
 578                 pset_foreach(spills, irn) {
 579                         ir_node *spilled = get_irn_n(irn, be_pos_Spill_val);
 580                         raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(spilled), spilled);
 581                 }
 582         }
 583
 584         /* add new variables for all reloads */
 585         pset_foreach(reloads, irn) {
 586                 assert(get_irn_node_nr(irn) != 1089);
 587                 raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(irn), irn);
 588         }
 589
 590         del_pset(spills);
 591         del_pset(reloads);
 592 }
 593
 594 #define INVALID_FILE_FORMAT assert(0 && "Invalid file format.")
 595 #define BUFLEN 32
 596 #define BUFCONV " %32s "
 597
 598 /**
 599  * Read in the actions performed by the external allocator.
 600  * Apply these transformations to the irg.
 601  * @return 1 if an allocation was read in. 0 otherwise.
 602  */
 603 static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 604         FILE *f;
 605         char buf[BUFLEN];
 606         int is_allocation = 0;
 607
 608         if (!(f = fopen(filename, "rt"))) {
 609                 fprintf(stderr, "Could not open file %s for reading\n", filename);
 610                 assert(0);
 611                 exit(0xdeadbeef);
 612         }
 613         raenv->f = f;
 614
 615         /* read the action */
 616         if (fscanf(f, BUFCONV, buf) != 1)
 617                 INVALID_FILE_FORMAT;
 618
 619         /* do we spill */
 620         if (!strcmp(buf, "spills")) {
 621                 int var_nr;
 622                 while (fscanf(f, " %d ", &var_nr) == 1)
 623                         var_add_spills_and_reloads(raenv, var_nr);
 624         } else
 625
 626         /* or do we allocate */
 627         if (!strcmp(buf, "allocs")) {
 628                 int var_nr, reg_nr;
 629
 630                 is_allocation = 1;
 631                 while (fscanf(f, " %d %d ", &var_nr, &reg_nr) == 2) {
 632                         ir_node *irn;
 633                         pset *vals = be_get_var_values(raenv->vars, var_nr);
 634
 635                         assert(vals && "Variable nr does not exist!");
 636                         pset_foreach(vals, irn)
 637                                 arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, reg_nr));
 638                 }
 639         } else
 640                 INVALID_FILE_FORMAT;
 641
 642         if (!feof(f))
 643                 INVALID_FILE_FORMAT;
 644
 645         fclose(f);
 646
 647         return is_allocation;
 648 }
 649
 650 static void check_allocation(be_raext_env_t *raenv) {
 651         int i, o;
 652
 653         for (i=0; i<raenv->n_cls_vars; ++i) {
 654                 be_var_info_t *vi1 = raenv->cls_vars[i];
 655
 656                 if (vi1->var_nr == SET_REMOVED)
 657                         continue;
 658
 659                 for (o=0; o<i; ++o) {
 660                         be_var_info_t *vi2 = raenv->cls_vars[o];
 661                         ir_node *irn1, *irn2;
 662
 663                         if (vi2->var_nr == SET_REMOVED)
 664                                 continue;
 665
 666                         pset_foreach(vi1->values, irn1)
 667                                 pset_foreach(vi2->values, irn2)
 668                                         if (values_interfere(irn1, irn2) && arch_get_irn_register(raenv->aenv, irn1) == arch_get_irn_register(raenv->aenv, irn2)) {
 669                                                 dump_ir_block_graph_sched(raenv->irg, "ERROR");
 670                                                 ir_fprintf(stdout, "SSA values %+F and %+F interfere. They belong to varible %d and %d respectively.\n", irn1, irn2, vi1->var_nr, vi2->var_nr);
 671                                                 assert(0 && "ERROR graph dumped");
 672                                         }
 673                 }
 674         }
 675 }
 676
 677 /******************************************************************************
 678     __  __       _
 679    |  \/  |     (_)
 680    | \  / | __ _ _ _ __
 681    | |\/| |/ _` | | '_ \
 682    | |  | | (_| | | | | |
 683    |_|  |_|\__,_|_|_| |_|
 684  *****************************************************************************/
 685
 686 /**
 687  * Default values for options
 688  */
 689 static set* (*ssa_destr)(ir_graph*,const arch_env_t*) = be_ssa_destr_simple;
 690 static char callee[128] = "\"E:/user/kimohoff/public/register allocator\"";
 691 //static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator";
 692
 693
 694 /**
 695  * Allocate registers with an external program using a text-file interface.
 696  *
 697  * Do some computations (SSA-destruction and mapping of values--vars)
 698  * Write file
 699  * Execute external program
 700  * Read in results and apply them
 701  *
 702  */
 703 static void be_ra_extern_main(const be_irg_t *bi) {
 704         be_main_env_t *env = bi->main_env;
 705         ir_graph *irg = bi->irg;
 706
 707         be_raext_env_t raenv;
 708         int clsnr, clss;
 709
 710         compute_doms(irg);
 711         edges_assure(irg);
 712
 713         raenv.irg      = irg;
 714         raenv.aenv     = env->arch_env;
 715         raenv.dom_info = be_compute_dominance_frontiers(irg);
 716         FIRM_DBG_REGISTER(raenv.dbg, "firm.be.raextern");
 717
 718         /* Insert copies for constraints */
 719         for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
 720                 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
 721                 handle_constraints(&raenv);
 722         }
 723
 724         be_dump(irg, "-extern-constr", dump_ir_block_graph_sched);
 725
 726         /* SSA destruction respectively transformation into "Conventional SSA" */
 727         raenv.vars = be_ssa_destr_simple(irg, env->arch_env);
 728         be_dump(irg, "-extern-ssadestr", dump_ir_block_graph_sched);
 729
 730
 731         /* For all register classes */
 732         for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
 733                 int done, round = 1;
 734                 char out[256], in[256];
 735
 736                 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
 737
 738                 extract_vars_of_cls(&raenv);
 739
 740                 do {
 741                         ir_snprintf(out, sizeof(out), "%F-%s-%d.ra", irg, raenv.cls->name, round);
 742                         ir_snprintf(in, sizeof(in), "%F-%s-%d.ra.res", irg, raenv.cls->name, round);
 743
 744                         be_liveness(irg);
 745
 746                         dump_to_file(&raenv, out);
 747                         execute(callee, out, in);
 748                         done = read_and_apply_results(&raenv, in);
 749                         be_abi_fix_stack_nodes(bi->abi);
 750
 751                         ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round);
 752                         be_dump(irg, in, dump_ir_block_graph_sched);
 753
 754                         round++;
 755                 } while (!done);
 756
 757                 check_allocation(&raenv);
 758
 759                 free(raenv.cls_vars);
 760         }
 761
 762         be_dump(irg, "-extern-alloc", dump_ir_block_graph_sched);
 763
 764         /* Clean up */
 765         free_ssa_destr_simple(raenv.vars);
 766         be_free_dominance_frontiers(raenv.dom_info);
 767 }
 768
 769 /******************************************************************************
 770      ____        _   _
 771     / __ \      | | (_)
 772    | |  | |_ __ | |_ _  ___  _ __  ___
 773    | |  | | '_ \| __| |/ _ \| '_ \/ __|
 774    | |__| | |_) | |_| | (_) | | | \__ \
 775     \____/| .__/ \__|_|\___/|_| |_|___/
 776           | |
 777           |_|
 778  *****************************************************************************/
 779
 780 #ifdef WITH_LIBCORE
 781
 782
 783 static const lc_opt_enum_func_ptr_items_t ssa_destr_items[] = {
 784         { "simple",     (int (*)()) be_ssa_destr_simple }, /* TODO make (void*) casts nicer */
 785         { NULL,      NULL }
 786 };
 787
 788 static lc_opt_enum_func_ptr_var_t ssa_destr_var = {
 789          (int (**)()) &ssa_destr, ssa_destr_items
 790 };
 791
 792 static const lc_opt_table_entry_t be_ra_extern_options[] = {
 793         LC_OPT_ENT_ENUM_FUNC_PTR("ssa_destr", "SSA destruction flavor", &ssa_destr_var),
 794         LC_OPT_ENT_STR("callee", "The external program to call", callee, sizeof(callee)),
 795         { NULL }
 796 };
 797
 798 static void be_ra_extern_register_options(lc_opt_entry_t *root) {
 799         lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext");
 800
 801         lc_opt_add_table(grp, be_ra_extern_options);
 802 }
 803
 804 #endif /* WITH_LIBCORE */
 805
 806 const be_ra_t be_ra_external_allocator = {
 807 #ifdef WITH_LIBCORE
 808         be_ra_extern_register_options,
 809 #endif
 810         be_ra_extern_main
 811 };