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         cmd_line[sizeof(cmd_line) - 1] = '\0';
 479
 480         ret_status = system(cmd_line);
 481         assert(ret_status != -1 && "Invokation of external register allocator failed");
 482         assert(ret_status == 0 && "External register allocator is unhappy with sth.");
 483 }
 484
 485 /******************************************************************************
 486                          _         _____                 _ _
 487        /\               | |       |  __ \               | | |
 488       /  \   _ __  _ __ | |_   _  | |__) |___  ___ _   _| | |_
 489      / /\ \ | '_ \| '_ \| | | | | |  _  // _ \/ __| | | | | __|
 490     / ____ \| |_) | |_) | | |_| | | | \ \  __/\__ \ |_| | | |_
 491    /_/    \_\ .__/| .__/|_|\__, | |_|  \_\___||___/\__,_|_|\__|
 492             | |   | |       __/ |
 493             |_|   |_|      |___/
 494  *****************************************************************************/
 495
 496 /**
 497  * Spill a variable and add reloads before all uses.
 498  */
 499 static INLINE void var_add_spills_and_reloads(be_raext_env_t *raenv, int var_nr) {
 500         be_var_info_t *vi = be_var_find(raenv->vars, var_nr);
 501         ir_node *spill=NULL, *ctx, *irn;
 502         ir_mode *mode;
 503         const ir_edge_t *edge, *ne;
 504         pset *spills  = pset_new_ptr(4);        /* the spills of this variable */
 505         pset *reloads = pset_new_ptr(4);        /* the reloads of this variable */
 506         int new_size, n_spills, n_reloads;
 507
 508         assert(vi && "Variable nr does not exist!");
 509         assert(pset_count(vi->values) && "There are no values associated to this variable");
 510
 511         /* the spill context is set to an arbitrary node of the phi-class,
 512          * or the node itself if it is not member of a phi class
 513          */
 514         if (pset_count(vi->values) == 1)
 515                 ctx = get_first_non_phi(vi->values);
 516         else
 517                 ctx = get_first_phi(vi->values);
 518
 519         DBG((raenv->dbg, LEVEL_2, "Spill context: %+F\n", ctx));
 520
 521         /* for each value of this variable insert the spills */
 522         pset_foreach(vi->values, irn) {
 523                 if (is_Phi(irn)) {
 524                         sched_remove(irn);
 525                         continue;
 526                 }
 527
 528                 /* all ordinary nodes must be spilled */
 529                 DBG((raenv->dbg, LEVEL_2, "  spilling %+F\n", irn));
 530                 spill = be_spill(raenv->aenv, irn, ctx);
 531
 532                 /* remember the spill */
 533                 pset_insert_ptr(spills, spill);
 534         }
 535
 536         assert(spill && "There must be at least one non-phi-node");
 537
 538         mode = get_irn_mode(get_irn_n(spill, be_pos_Spill_val));
 539
 540         /* insert reloads and wire them arbitrary*/
 541         pset_foreach(vi->values, irn)
 542                 foreach_out_edge_safe(irn, edge, ne) {
 543                         ir_node *reload, *src = edge->src;
 544                         if (is_Phi(src) || be_is_Spill(src))
 545                                 continue;
 546
 547                         /* all real uses must be reloaded */
 548                         DBG((raenv->dbg, LEVEL_2, "  reloading before %+F\n", src));
 549                         reload = be_reload(raenv->aenv, raenv->cls, edge->src, mode, spill);
 550                         set_irn_n(edge->src, edge->pos, reload);
 551
 552                         /* remember the reload */
 553                         pset_insert_ptr(reloads, reload);
 554                 }
 555
 556         /* correct the reload->spill pointers... */
 557         be_ssa_constr_set(raenv->dom_info, spills);
 558
 559
 560         /****** correct the variable <--> values mapping: ******
 561          *
 562          *  - if we had a phi class it gets split into several new variables
 563          *  - all reloads are new variables
 564          */
 565         n_spills = pset_count(spills);
 566         n_reloads = pset_count(reloads);
 567
 568         /* first make room for new pointers in the cls_var array */
 569         new_size = raenv->n_cls_vars + n_reloads + ((n_spills>1) ? n_spills : 0);
 570         raenv->cls_vars = realloc(raenv->cls_vars, (new_size) * sizeof(*raenv->cls_vars));
 571         assert(raenv->cls_vars && "Out of mem!?");
 572
 573         /* if we had a real phi-class, we must... */
 574         if (pset_count(spills) > 1) {
 575                 /* ...remove the old variable corresponding to the phi class */
 576                 vi->var_nr = SET_REMOVED;
 577
 578                 /* ...add new vars for each non-phi-member */
 579                 pset_foreach(spills, irn) {
 580                         ir_node *spilled = get_irn_n(irn, be_pos_Spill_val);
 581                         raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(spilled), spilled);
 582                 }
 583         }
 584
 585         /* add new variables for all reloads */
 586         pset_foreach(reloads, irn) {
 587                 assert(get_irn_node_nr(irn) != 1089);
 588                 raenv->cls_vars[raenv->n_cls_vars++] = be_var_add_value(raenv->vars, get_irn_node_nr(irn), irn);
 589         }
 590
 591         del_pset(spills);
 592         del_pset(reloads);
 593 }
 594
 595 #define INVALID_FILE_FORMAT assert(0 && "Invalid file format.")
 596 #define BUFLEN 32
 597 #define BUFCONV " %32s "
 598
 599 /**
 600  * Read in the actions performed by the external allocator.
 601  * Apply these transformations to the irg.
 602  * @return 1 if an allocation was read in. 0 otherwise.
 603  */
 604 static int read_and_apply_results(be_raext_env_t *raenv, char *filename) {
 605         FILE *f;
 606         char buf[BUFLEN];
 607         int is_allocation = 0;
 608
 609         if (!(f = fopen(filename, "rt"))) {
 610                 fprintf(stderr, "Could not open file %s for reading\n", filename);
 611                 assert(0);
 612                 exit(0xdeadbeef);
 613         }
 614         raenv->f = f;
 615
 616         /* read the action */
 617         if (fscanf(f, BUFCONV, buf) != 1)
 618                 INVALID_FILE_FORMAT;
 619
 620         /* do we spill */
 621         if (!strcmp(buf, "spills")) {
 622                 int var_nr;
 623                 while (fscanf(f, " %d ", &var_nr) == 1)
 624                         var_add_spills_and_reloads(raenv, var_nr);
 625         } else
 626
 627         /* or do we allocate */
 628         if (!strcmp(buf, "allocs")) {
 629                 int var_nr, reg_nr;
 630
 631                 is_allocation = 1;
 632                 while (fscanf(f, " %d %d ", &var_nr, &reg_nr) == 2) {
 633                         ir_node *irn;
 634                         pset *vals = be_get_var_values(raenv->vars, var_nr);
 635
 636                         assert(vals && "Variable nr does not exist!");
 637                         pset_foreach(vals, irn)
 638                                 arch_set_irn_register(raenv->aenv, irn, arch_register_for_index(raenv->cls, reg_nr));
 639                 }
 640         } else
 641                 INVALID_FILE_FORMAT;
 642
 643         if (!feof(f))
 644                 INVALID_FILE_FORMAT;
 645
 646         fclose(f);
 647
 648         return is_allocation;
 649 }
 650
 651 static void check_allocation(be_raext_env_t *raenv) {
 652         int i, o;
 653
 654         for (i=0; i<raenv->n_cls_vars; ++i) {
 655                 be_var_info_t *vi1 = raenv->cls_vars[i];
 656
 657                 if (vi1->var_nr == SET_REMOVED)
 658                         continue;
 659
 660                 for (o=0; o<i; ++o) {
 661                         be_var_info_t *vi2 = raenv->cls_vars[o];
 662                         ir_node *irn1, *irn2;
 663
 664                         if (vi2->var_nr == SET_REMOVED)
 665                                 continue;
 666
 667                         pset_foreach(vi1->values, irn1)
 668                                 pset_foreach(vi2->values, irn2)
 669                                         if (values_interfere(irn1, irn2) && arch_get_irn_register(raenv->aenv, irn1) == arch_get_irn_register(raenv->aenv, irn2)) {
 670                                                 dump_ir_block_graph_sched(raenv->irg, "ERROR");
 671                                                 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);
 672                                                 assert(0 && "ERROR graph dumped");
 673                                         }
 674                 }
 675         }
 676 }
 677
 678 /******************************************************************************
 679     __  __       _
 680    |  \/  |     (_)
 681    | \  / | __ _ _ _ __
 682    | |\/| |/ _` | | '_ \
 683    | |  | | (_| | | | | |
 684    |_|  |_|\__,_|_|_| |_|
 685  *****************************************************************************/
 686
 687 /**
 688  * Default values for options
 689  */
 690 static set* (*ssa_destr)(ir_graph*,const arch_env_t*) = be_ssa_destr_simple;
 691 static char callee[128] = "\"E:/user/kimohoff/public/register allocator\"";
 692 //static char callee[128] = "/ben/kimohoff/ipd-registerallocator/register_allocator";
 693
 694
 695 /**
 696  * Allocate registers with an external program using a text-file interface.
 697  *
 698  * Do some computations (SSA-destruction and mapping of values--vars)
 699  * Write file
 700  * Execute external program
 701  * Read in results and apply them
 702  *
 703  */
 704 static be_ra_timer_t *be_ra_extern_main(const be_irg_t *bi) {
 705         be_main_env_t *env = bi->main_env;
 706         ir_graph *irg = bi->irg;
 707
 708         be_raext_env_t raenv;
 709         int clsnr, clss;
 710
 711         compute_doms(irg);
 712         edges_assure(irg);
 713
 714         raenv.irg      = irg;
 715         raenv.aenv     = env->arch_env;
 716         raenv.dom_info = be_compute_dominance_frontiers(irg);
 717         FIRM_DBG_REGISTER(raenv.dbg, "firm.be.raextern");
 718
 719         /* Insert copies for constraints */
 720         for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
 721                 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
 722                 handle_constraints(&raenv);
 723         }
 724
 725         be_dump(irg, "-extern-constr", dump_ir_block_graph_sched);
 726
 727         /* SSA destruction respectively transformation into "Conventional SSA" */
 728         raenv.vars = be_ssa_destr_simple(irg, env->arch_env);
 729         be_dump(irg, "-extern-ssadestr", dump_ir_block_graph_sched);
 730
 731
 732         /* For all register classes */
 733         for(clsnr = 0, clss = arch_isa_get_n_reg_class(raenv.aenv->isa); clsnr < clss; ++clsnr) {
 734                 int done, round = 1;
 735                 char out[256], in[256];
 736
 737                 raenv.cls = arch_isa_get_reg_class(raenv.aenv->isa, clsnr);
 738
 739                 extract_vars_of_cls(&raenv);
 740
 741                 do {
 742                         ir_snprintf(out, sizeof(out), "%F-%s-%d.ra", irg, raenv.cls->name, round);
 743                         ir_snprintf(in, sizeof(in), "%F-%s-%d.ra.res", irg, raenv.cls->name, round);
 744
 745                         be_liveness(irg);
 746
 747                         dump_to_file(&raenv, out);
 748                         execute(callee, out, in);
 749                         done = read_and_apply_results(&raenv, in);
 750                         be_abi_fix_stack_nodes(bi->abi);
 751
 752                         ir_snprintf(in, sizeof(in), "-extern-%s-round-%d", raenv.cls->name, round);
 753                         be_dump(irg, in, dump_ir_block_graph_sched);
 754
 755                         round++;
 756                 } while (!done);
 757
 758                 check_allocation(&raenv);
 759
 760                 free(raenv.cls_vars);
 761         }
 762
 763         be_dump(irg, "-extern-alloc", dump_ir_block_graph_sched);
 764
 765         /* Clean up */
 766         free_ssa_destr_simple(raenv.vars);
 767         be_free_dominance_frontiers(raenv.dom_info);
 768
 769         return NULL;
 770 }
 771
 772 /******************************************************************************
 773      ____        _   _
 774     / __ \      | | (_)
 775    | |  | |_ __ | |_ _  ___  _ __  ___
 776    | |  | | '_ \| __| |/ _ \| '_ \/ __|
 777    | |__| | |_) | |_| | (_) | | | \__ \
 778     \____/| .__/ \__|_|\___/|_| |_|___/
 779           | |
 780           |_|
 781  *****************************************************************************/
 782
 783 #ifdef WITH_LIBCORE
 784
 785
 786 static const lc_opt_enum_func_ptr_items_t ssa_destr_items[] = {
 787         { "simple",     (int (*)()) be_ssa_destr_simple }, /* TODO make (void*) casts nicer */
 788         { NULL,      NULL }
 789 };
 790
 791 static lc_opt_enum_func_ptr_var_t ssa_destr_var = {
 792          (int (**)()) &ssa_destr, ssa_destr_items
 793 };
 794
 795 static const lc_opt_table_entry_t be_ra_extern_options[] = {
 796         LC_OPT_ENT_ENUM_FUNC_PTR("ssa_destr", "SSA destruction flavor", &ssa_destr_var),
 797         LC_OPT_ENT_STR("callee", "The external program to call", callee, sizeof(callee)),
 798         { NULL }
 799 };
 800
 801 static void be_ra_extern_register_options(lc_opt_entry_t *root) {
 802         lc_opt_entry_t *grp = lc_opt_get_grp(root, "ext");
 803
 804         lc_opt_add_table(grp, be_ra_extern_options);
 805 }
 806
 807 #endif /* WITH_LIBCORE */
 808
 809 const be_ra_t be_ra_external_allocator = {
 810 #ifdef WITH_LIBCORE
 811         be_ra_extern_register_options,
 812 #endif
 813         be_ra_extern_main
 814 };