nsz Git - libfirm/blob - ir/be/ia32/ia32_x87.c

   1 /**
   2  * This file implements the x87 support and virtual to stack
   3  * register translation for the ia32 backend.
   4  *
   5  * @author: Michael Beck
   6  *
   7  * $Id$
   8  */
   9
  10 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif /* HAVE_CONFIG_H */
  13
  14 #include <assert.h>
  15
  16 #include "irnode_t.h"
  17 #include "irop_t.h"
  18 #include "irprog.h"
  19 #include "iredges_t.h"
  20 #include "irgmod.h"
  21 #include "ircons.h"
  22 #include "obst.h"
  23 #include "pmap.h"
  24 #include "pdeq.h"
  25 #include "irprintf.h"
  26 #include "debug.h"
  27
  28 #include "../belive_t.h"
  29 #include "../besched.h"
  30 #include "../benode_t.h"
  31 #include "ia32_new_nodes.h"
  32 #include "gen_ia32_new_nodes.h"
  33 #include "gen_ia32_regalloc_if.h"
  34 #include "ia32_x87.h"
  35
  36 #define N_x87_REGS 8
  37
  38 /* first and second binop index */
  39 #define BINOP_IDX_1     2
  40 #define BINOP_IDX_2 3
  41
  42 /* the unop index */
  43 #define UNOP_IDX  0
  44
  45 /* the store val index */
  46 #define STORE_VAL_IDX 2
  47
  48 #define MASK_TOS(x)             ((x) & (N_x87_REGS - 1))
  49
  50 /** the debug handle */
  51 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  52
  53 /**
  54  * An exchange template.
  55  * Note that our virtual functions have the same inputs
  56  * and attributes as the real ones, so we can simple exchange
  57  * their opcodes!
  58  * Further, x87 supports inverse instructions, so we can handle them.
  59  */
  60 typedef struct _exchange_tmpl {
  61         ir_op *normal_op;       /**< the normal one */
  62         ir_op *reverse_op;      /**< the reverse one if exists */
  63         ir_op *normal_pop_op;   /**< the normal one with tos pop */
  64         ir_op *reverse_pop_op;  /**< the reverse one with tos pop */
  65 } exchange_tmpl;
  66
  67 /**
  68  * An entry on the simulated x87 stack.
  69  */
  70 typedef struct _st_entry {
  71         int     reg_idx;        /**< the virtual register index of this stack value */
  72         ir_node *node;          /**< the node that produced this value */
  73 } st_entry;
  74
  75 /**
  76  * The x87 state.
  77  */
  78 typedef struct _x87_state {
  79         st_entry st[N_x87_REGS];  /**< the register stack */
  80         int depth;                /**< the current stack depth */
  81         int tos;                  /**< position of the tos */
  82 } x87_state;
  83
  84 /** An empty state, used for blocks without fp instructions. */
  85 static const x87_state _empty = { {0, NULL}, 0, 0 };
  86 static x87_state *empty = (x87_state *)&_empty;
  87
  88 /** The type of an instruction simulator */
  89 typedef void (*sim_func)(x87_state *state, ir_node *n, const arch_env_t *env);
  90
  91 /**
  92  * A block state: Every block has a x87 state at the beginning and at the end.
  93  */
  94 typedef struct _blk_state {
  95         x87_state *begin;   /**< state at the begin or NULL if not assigned */
  96         x87_state *end;     /**< state at the end or NULL if not assigned */
  97 } blk_state;
  98
  99 #define PTR_TO_BLKSTATE(p)      ((blk_state *)(p))
 100
 101 /**
 102  * The x87 simulator.
 103  */
 104 typedef struct _x87_simulator {
 105         struct obstack obst;      /**< an obstack for fast allocating */
 106         pmap *blk_states;         /**< map blocks to states */
 107         const arch_env_t *env;          /**< architecture environment */
 108 } x87_simulator;
 109
 110 /**
 111  * Returns the stack depth.
 112  *
 113  * @param state  the x87 state
 114  *
 115  * @return the x87 stack depth
 116  */
 117 static int x87_get_depth(const x87_state *state) {
 118         return state->depth;
 119 }
 120
 121 /**
 122  * Check if the state is empty.
 123  *
 124  * @param state  the x87 state
 125  *
 126  * returns non-zero if the x87 stack is empty
 127  */
 128 static int x87_state_is_empty(const x87_state *state) {
 129         return state->depth == 0;
 130 }
 131
 132 /**
 133  * Return the virtual register index at st(pos).
 134  *
 135  * @param state  the x87 state
 136  * @param pos    a stack position
 137  *
 138  * @return the vfp register index that produced the value at st(pos)
 139  */
 140 static int x87_get_st_reg(const x87_state *state, int pos) {
 141         assert(pos < state->depth);
 142         return state->st[MASK_TOS(state->tos + pos)].reg_idx;
 143 }
 144
 145 /**
 146  * Return the node at st(pos).
 147  *
 148  * @param state  the x87 state
 149  * @param pos    a stack position
 150  *
 151  * @return the IR node that produced the value at st(pos)
 152  */
 153 static ir_node *x87_get_st_node(const x87_state *state, int pos) {
 154         assert(pos < state->depth);
 155         return state->st[MASK_TOS(state->tos + pos)].node;
 156 }
 157
 158 #ifdef DEBUG_libfirm
 159 /**
 160  * Dump the stack for debugging.
 161  *
 162  * @param state  the x87 state
 163  */
 164 static void x87_dump_stack(const x87_state *state) {
 165         int i;
 166
 167         for (i = state->depth - 1; i >= 0; --i) {
 168                 DB((dbg, LEVEL_2, "vf%d ", x87_get_st_reg(state, i)));
 169         }
 170         DB((dbg, LEVEL_2, "<-- TOS\n"));
 171 }
 172 #endif /* DEBUG_libfirm */
 173
 174 /**
 175  * Set a virtual register to st(pos).
 176  *
 177  * @param state    the x87 state
 178  * @param reg_idx  the vfp register index that should be set
 179  * @param node     the IR node that produces the value of the vfp register
 180  * @param pos      the stack position where the new value should be entered
 181  */
 182 static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) {
 183         assert(0 < state->depth);
 184         state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx;
 185         state->st[MASK_TOS(state->tos + pos)].node    = node;
 186
 187         DB((dbg, LEVEL_2, "After SET_REG:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 188 }
 189
 190 /**
 191  * Set the tos virtual register.
 192  *
 193  * @param state    the x87 state
 194  * @param reg_idx  the vfp register index that should be set
 195  * @param node     the IR node that produces the value of the vfp register
 196  */
 197 static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node) {
 198         x87_set_st(state, reg_idx, node, 0);
 199 }
 200
 201 /**
 202  * Flush the x87 stack.
 203  *
 204  * @param state    the x87 state
 205  */
 206 static void x87_flush(x87_state *state) {
 207         state->depth = 0;
 208         state->tos   = 0;
 209 }
 210
 211 /**
 212  * Swap st(0) with st(pos).
 213  *
 214  * @param state    the x87 state
 215  * @param pos      the stack position to change the tos with
 216  */
 217 static void x87_fxch(x87_state *state, int pos) {
 218         st_entry entry;
 219         assert(pos < state->depth);
 220
 221         entry = state->st[MASK_TOS(state->tos + pos)];
 222         state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
 223         state->st[MASK_TOS(state->tos)] = entry;
 224
 225         DB((dbg, LEVEL_2, "After FXCH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 226 }
 227
 228 /**
 229  * Convert a virtual register to the stack index.
 230  *
 231  * @param state    the x87 state
 232  * @param reg_idx  the register vfp index
 233  *
 234  * @return the stack position where the register is stacked
 235  *         or -1 if the virtual register was not found
 236  */
 237 static int x87_on_stack(const x87_state *state, int reg_idx) {
 238         int i, tos = state->tos;
 239
 240         for (i = 0; i < state->depth; ++i)
 241                 if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx)
 242                         return i;
 243         return -1;
 244 }
 245
 246 /**
 247  * Push a virtual Register onto the stack.
 248  *
 249  * @param state    the x87 state
 250  * @param reg_idx  the register vfp index
 251  * @param node     the node that produces the value of the vfp register
 252  */
 253 static void x87_push(x87_state *state, int reg_idx, ir_node *node) {
 254         assert(x87_on_stack(state, reg_idx) == -1 && "double push");
 255         assert(state->depth < N_x87_REGS && "stack overrun");
 256
 257         ++state->depth;
 258         state->tos = MASK_TOS(state->tos - 1);
 259         state->st[state->tos].reg_idx = reg_idx;
 260         state->st[state->tos].node    = node;
 261
 262         DB((dbg, LEVEL_2, "After PUSH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 263 }
 264
 265 /**
 266  * Pop a virtual Register from the stack.
 267  */
 268 static void x87_pop(x87_state *state) {
 269         assert(state->depth > 0 && "stack underrun");
 270
 271         --state->depth;
 272         state->tos = MASK_TOS(state->tos + 1);
 273
 274         DB((dbg, LEVEL_2, "After POP:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 275 }
 276
 277 /**
 278  * Returns the block state of a block.
 279  *
 280  * @param sim    the x87 simulator handle
 281  * @param block  the current block
 282  *
 283  * @return the block state
 284  */
 285 static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) {
 286         pmap_entry *entry = pmap_find(sim->blk_states, block);
 287
 288         if (! entry) {
 289                 blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
 290                 bl_state->begin = NULL;
 291                 bl_state->end   = NULL;
 292
 293                 pmap_insert(sim->blk_states, block, bl_state);
 294                 return bl_state;
 295         }
 296
 297         return entry ? PTR_TO_BLKSTATE(entry->value) : NULL;
 298 }
 299
 300 /**
 301  * Creates a new x87 state.
 302  *
 303  * @param sim    the x87 simulator handle
 304  * @return a new x87 state
 305  */
 306 static x87_state *x87_alloc_state(x87_simulator *sim) {
 307         x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
 308         return res;
 309 }
 310
 311 /**
 312  * Create a new empty x87 state.
 313  *
 314  * @param sim    the x87 simulator handle
 315  * @return a new empty x87 state
 316  */
 317 static x87_state *x87_alloc_empty_state(x87_simulator *sim) {
 318         x87_state *res = x87_alloc_state(sim);
 319
 320         x87_flush(res);
 321         return res;
 322 }
 323
 324 /**
 325  * Clone a x87 state.
 326  *
 327  * @param sim    the x87 simulator handle
 328  * @param src    the x87 state that will be cloned
 329  *
 330  * @return a cloned copy of the src state
 331  */
 332 static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) {
 333         x87_state *res = x87_alloc_state(sim);
 334
 335         memcpy(res, src, sizeof(*res));
 336         return res;
 337 }
 338
 339 /**
 340  * Patch a virtual instruction into a x87 one and return
 341  * the value node.
 342  *
 343  * @param n   the IR node to patch
 344  * @param op  the x87 opcode to patch in
 345  */
 346 static ir_node *x87_patch_insn(ir_node *n, ir_op *op) {
 347         ir_mode *mode = get_irn_mode(n);
 348         ir_node *res = n;
 349
 350         set_irn_op(n, op);
 351
 352         if (mode == mode_T) {
 353                 /* patch all Proj's */
 354                 const ir_edge_t *edge;
 355
 356                 foreach_out_edge(n, edge) {
 357                         ir_node *proj = get_edge_src_irn(edge);
 358                         if (is_Proj(proj)) {
 359                                 mode = get_irn_mode(proj);
 360                                 if (mode_is_float(mode)) {
 361                                         res = proj;
 362                                         set_irn_mode(proj, mode_E);
 363                                 }
 364                         }
 365                 }
 366         }
 367         else if (mode_is_float(mode))
 368                 set_irn_mode(n, mode_E);
 369         return res;
 370 }
 371
 372 /* -------------- x87 perm --------------- */
 373
 374 /**
 375  * Creates a fxch for shuffle.
 376  *
 377  * @param state     the x87 state
 378  * @param pos       parameter for fxch
 379  * @param dst_block the block of the user
 380  *
 381  * Creates a new fxch node and reroute the user of the old node
 382  * to the fxch.
 383  *
 384  * @return the fxch node
 385  */
 386 static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block, ir_node *dst_block)
 387 {
 388         const ir_edge_t *edge;
 389         ir_node *n = x87_get_st_node(state, pos);
 390         ir_node *user = NULL;
 391         ir_node *fxch;
 392         int node_idx;
 393         ia32_attr_t *attr;
 394
 395         if (block == get_nodes_block(n)) {
 396                 /* this is a node from out block: change it's user */
 397                 foreach_out_edge(n, edge) {
 398                         ir_node *succ = get_edge_src_irn(edge);
 399
 400                         if (is_Phi(succ) && get_nodes_block(succ) == dst_block) {
 401                                 user = succ;
 402                                 node_idx = get_edge_src_pos(edge);
 403                                 break;
 404                         }
 405                 }
 406                 assert(user);
 407         }
 408
 409         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(block), block, n, get_irn_mode(n));
 410         attr = get_ia32_attr(fxch);
 411         attr->x87[0] = &ia32_st_regs[pos];
 412         attr->x87[2] = &ia32_st_regs[0];
 413
 414         if (user) {
 415                 DB((dbg, LEVEL_2, "%+F replaced input %d of %+F\n", fxch, node_idx, user));
 416                 set_irn_n(user, node_idx, fxch);
 417         }
 418         else {
 419                 /*
 420                  * This is a node from a dominator block. Changing it's user might be wrong,
 421                  * so just keep it alive.
 422                  * The "right" solution would require a new Phi, but we don't care here.
 423                  */
 424                 keep_alive(fxch);
 425         }
 426
 427         x87_fxch(state, pos);
 428         return fxch;
 429 }
 430
 431 /**
 432  * Calculate the necessary permutations to reach dst_state.
 433  *
 434  * These permutations are done with fxch instructions and placed
 435  * at the end of the block.
 436  *
 437  * Note that critical edges are removed here, so we need only
 438  * a shuffle if the current block has only one successor.
 439  *
 440  * @param sim        the simulator handle
 441  * @param block      the current block
 442  * @param state      the current x87 stack state, might be modified
 443  * @param dst_block  the destination block
 444  * @param dst_state  destination state
 445  *
 446  * @return state
 447  */
 448 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, ir_node *dst_block, const x87_state *dst_state) {
 449         int i, n_cycles, k, ri;
 450         unsigned cycles[4], all_mask;
 451         char cycle_idx[4][8];
 452         ir_node *fxch;
 453         ir_node *before, *after;
 454
 455         assert(state->depth == dst_state->depth);
 456
 457         /* Some mathematics here:
 458            If we have a cycle of lenght n that includes the tos,
 459            we need n-1 exchange operations.
 460            We can always add the tos and restore it, so we need
 461            n+1 exchange operations for a cycle not containing the tos.
 462            So, the maximum of needed operations is for a cycle of 7
 463            not including the tos == 8.
 464            This is so same number of ops we would need for store,
 465            so exchange is cheaper (we save the loads).
 466            On the other hand, we might need an additional exchange
 467            in the next block to bring one operand on top, so the
 468            number of ops in the first case is identical.
 469                  Further, no more than 4 cycles can exists.
 470         */
 471         all_mask = (1 << (state->depth)) - 1;
 472
 473         for (n_cycles = 0; all_mask; ++n_cycles) {
 474                 int src_idx, dst_idx;
 475
 476                 /* find the first free slot */
 477                 for (i = 0; i < state->depth; ++i) {
 478                         if (all_mask & (1 << i)) {
 479                                 all_mask &= ~(1 << i);
 480
 481                                 /* check if there are differences here */
 482                                 if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
 483                                         break;
 484                         }
 485                 }
 486
 487                 if (! all_mask) {
 488                         /* no more cycles found */
 489                         break;
 490                 }
 491
 492                 k = 0;
 493                 cycles[n_cycles] = (1 << i);
 494                 cycle_idx[n_cycles][k++] = i;
 495                 for (src_idx = i; ; src_idx = dst_idx) {
 496                         dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
 497
 498                         if ((all_mask & (1 << dst_idx)) == 0)
 499                                 break;
 500
 501                         cycle_idx[n_cycles][k++] = dst_idx;
 502                         cycles[n_cycles] |=  (1 << dst_idx);
 503                         all_mask       &= ~(1 << dst_idx);
 504                 }
 505                 cycle_idx[n_cycles][k] = -1;
 506         }
 507
 508         if (n_cycles <= 0) {
 509                 /* no permutation needed */
 510                 return state;
 511         }
 512
 513         /* Hmm: permutation needed */
 514         DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
 515         DEBUG_ONLY(x87_dump_stack(state));
 516         DB((dbg, LEVEL_2, "                  to\n"));
 517         DEBUG_ONLY(x87_dump_stack(dst_state));
 518
 519
 520 #ifdef DEBUG_libfirm
 521         DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
 522         for (ri = 0; ri < n_cycles; ++ri) {
 523                 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
 524                 for (k = 0; cycle_idx[ri][k] != -1; ++k)
 525                         DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
 526                 DB((dbg, LEVEL_2, "\n"));
 527         }
 528 #endif
 529
 530         after = NULL;
 531
 532         /*
 533          * Find the place node must be insert.
 534          * We have only one successor block, so the last instruction should
 535          * be a jump.
 536          */
 537         before = sched_last(block);
 538         assert(is_cfop(before));
 539
 540         /* now do the permutations */
 541         for (ri = 0; ri < n_cycles; ++ri) {
 542                 if ((cycles[ri] & 1) == 0) {
 543                         /* this cycle does not include the tos */
 544                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block);
 545                         if (after)
 546                                 sched_add_after(after, fxch);
 547                         else
 548                                 sched_add_before(before, fxch);
 549                         after = fxch;
 550                 }
 551                 for (k = 1; cycle_idx[ri][k] != -1; ++k) {
 552                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][k], block, dst_block);
 553                         if (after)
 554                                 sched_add_after(after, fxch);
 555                         else
 556                                 sched_add_before(before, fxch);
 557                         after = fxch;
 558                 }
 559                 if ((cycles[ri] & 1) == 0) {
 560                         /* this cycle does not include the tos */
 561                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block);
 562                         sched_add_after(after, fxch);
 563                 }
 564         }
 565         return state;
 566 }
 567
 568 /**
 569  * Create a fxch node before another node.
 570  *
 571  * @param state   the x87 state
 572  * @param n       the node before the fxch
 573  * @param pos     exchange st(pos) with st(0)
 574  * @param op_idx  if >= 0, replace input op_idx of n with the fxch result
 575  *
 576  * @return the fxch
 577  */
 578 static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) {
 579         ir_node *fxch, *pred;
 580         ia32_attr_t *attr;
 581
 582         x87_fxch(state, pos);
 583
 584         if (op_idx >= 0)
 585                 pred = get_irn_n(n, op_idx);
 586         else
 587                 pred = x87_get_st_node(state, pos);
 588
 589         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 590         attr = get_ia32_attr(fxch);
 591         attr->x87[0] = &ia32_st_regs[pos];
 592         attr->x87[2] = &ia32_st_regs[0];
 593
 594         if (op_idx >= 0)
 595                 set_irn_n(n, op_idx, fxch);
 596
 597         sched_add_before(n, fxch);
 598         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
 599         return fxch;
 600 }
 601
 602 /**
 603  * Create a fpush before node n.
 604  *
 605  * @param state   the x87 state
 606  * @param n       the node before the fpush
 607  * @param pos     push st(pos) on stack
 608  * @param op_idx  if >= 0, replace input op_idx of n with the fpush result
 609  */
 610 static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n, int pos, int op_idx) {
 611         ir_node *fpush, *pred;
 612         ia32_attr_t *attr;
 613         const arch_register_t *out = arch_get_irn_register(env, n);
 614
 615         x87_push(state, arch_register_get_index(out), n);
 616
 617         pred = get_irn_n(n, op_idx);
 618         fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 619         attr = get_ia32_attr(fpush);
 620         attr->x87[0] = &ia32_st_regs[pos];
 621         attr->x87[2] = &ia32_st_regs[0];
 622         if (op_idx >= 0)
 623                 set_irn_n(n, op_idx, fpush);
 624
 625         sched_add_before(n, fpush);
 626         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
 627 }
 628
 629 /**
 630  * Create a fpop before node n.
 631  *
 632  * @param state   the x87 state
 633  * @param n       the node before the fpop
 634  * @param num     pop 1 or 2 values
 635  * @param pred    node to use as predecessor of the fpop
 636  *
 637  * @return the fpop node
 638  */
 639 static ir_node *x87_create_fpop(const arch_env_t *env, x87_state *state, ir_node *n, int num, ir_node *pred) {
 640         ir_node *fpop;
 641         ia32_attr_t *attr;
 642
 643         while (num > 0) {
 644                 x87_pop(state);
 645                 fpop = new_rd_ia32_fpop(NULL, get_irn_irg(n), get_nodes_block(n), pred, mode_E);
 646                 attr = get_ia32_attr(fpop);
 647                 attr->x87[0] = &ia32_st_regs[0];
 648                 attr->x87[1] = &ia32_st_regs[0];
 649                 attr->x87[2] = &ia32_st_regs[0];
 650
 651                 sched_add_before(n, fpop);
 652                 DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->x87[0]->name));
 653
 654                 pred = fpop;
 655                 --num;
 656         }
 657         return fpop;
 658 }
 659
 660 /* --------------------------------- liveness ------------------------------------------ */
 661
 662 /**
 663  * The liveness transfer function.
 664  * Updates a live set over a single step from a given node to its predecessor.
 665  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 666  * @param arch_env The architecture environment.
 667  * @param irn      The node at which liveness should be computed.
 668  * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 669  *                 the registers live after irn.
 670  * @return live.
 671  */
 672 static unsigned vfp_liveness_transfer(const arch_env_t *arch_env, ir_node *irn, unsigned live)
 673 {
 674         int i, n;
 675         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 676
 677         if (arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 678                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 679                         live &= ~(1 << reg->index);
 680         }
 681
 682         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 683                 ir_node *op = get_irn_n(irn, i);
 684
 685                 if (mode_is_float(get_irn_mode(op)) && arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
 686                         const arch_register_t *reg = arch_get_irn_register(arch_env, op);
 687                         live |= 1 << reg->index;
 688                 }
 689         }
 690
 691         return live;
 692 }
 693
 694 /**
 695  * Put all live virtual registers at the end of a block into a bitset.
 696  * @param arch_env The architecture environment.
 697  * @param bl       The block.
 698  * @return The live bitset.
 699  */
 700 static unsigned vfp_liveness_end_of_block(const arch_env_t *arch_env, const ir_node *bl)
 701 {
 702         irn_live_t *li;
 703         unsigned live = 0;
 704         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 705
 706         live_foreach(bl, li) {
 707                 ir_node *irn = (ir_node *) li->irn;
 708                 if (live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 709                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 710                         live |= 1 << reg->index;
 711                 }
 712         }
 713
 714         return live;
 715 }
 716
 717 /**
 718  * Compute a bitset of registers which are live at another node.
 719  * @param arch_env The architecture environment.
 720  * @param pos      The node.
 721  * @return The live bitset.
 722  */
 723 static unsigned vfp_liveness_nodes_live_at(const arch_env_t *arch_env, const ir_node *pos)
 724 {
 725         const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
 726         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 727         ir_node *irn;
 728         unsigned live;
 729
 730         live = vfp_liveness_end_of_block(arch_env, bl);
 731
 732         sched_foreach_reverse(bl, irn) {
 733                 /*
 734                  * If we encounter the node we want to insert the Perm after,
 735                  * exit immediately, so that this node is still live
 736                  */
 737                 if (irn == pos)
 738                         return live;
 739
 740                 live = vfp_liveness_transfer(arch_env, irn, live);
 741         }
 742
 743         return live;
 744 }
 745
 746 /**
 747  * Returns true if a register is live in a set.
 748  *
 749  * @param reg_idx  the vfp register index
 750  * @param live     a live bitset
 751  */
 752 static unsigned is_vfp_live(int reg_idx, unsigned live) {
 753         return live & (1 << reg_idx);
 754 }
 755
 756 #ifdef DEBUG_libfirm
 757 /**
 758  * Dump liveness info.
 759  *
 760  * @param live  the live bitset
 761  */
 762 static void vfp_dump_live(unsigned live) {
 763         int i;
 764
 765         DB((dbg, LEVEL_2, "Live registers here: \n"));
 766         for (i = 0; i < 8; ++i) {
 767                 if (live & (1 << i)) {
 768                         DB((dbg, LEVEL_2, " vf%d", i));
 769                 }
 770         }
 771         DB((dbg, LEVEL_2, "\n"));
 772 }
 773 #endif /* DEBUG_libfirm */
 774
 775 /* --------------------------------- simulators ---------------------------------------- */
 776
 777 #define XCHG(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0)
 778
 779 /**
 780  * Simulate a virtual binop.
 781  *
 782  * @param state  the x87 state
 783  * @param n      the node that should be simulated (and patched)
 784  * @param env    the architecture environment
 785  * @param tmpl   the template containing the 4 possible x87 opcodes
 786  */
 787 static void sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const exchange_tmpl *tmpl) {
 788         int op2_idx, op1_idx = -1;
 789         int out_idx, do_pop =0;
 790         ia32_attr_t *attr;
 791         ir_op *dst;
 792         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
 793         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
 794         const arch_register_t *out = arch_get_irn_register(env, n);
 795         unsigned live = vfp_liveness_nodes_live_at(env, n);
 796
 797         DB((dbg, LEVEL_1, ">>> %s %s, %s -> %s\n", get_irn_opname(n),
 798                 arch_register_get_name(op2), arch_register_get_name(op1),
 799                 arch_register_get_name(out)));
 800   DEBUG_ONLY(vfp_dump_live(live));
 801
 802         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 803
 804         if (op1->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]) {
 805                 /* first operand is a vfp register */
 806                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 807
 808                 if (is_vfp_live(op2->index, live)) {
 809                         /* Second operand is live. */
 810
 811                         if (is_vfp_live(op1->index, live)) {
 812                                 /* Both operands are live: push the first one.
 813                                    This works even for op1 == op2. */
 814                                 x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
 815                                 out_idx = op2_idx = 0;
 816                                 ++op1_idx;
 817                                 dst = tmpl->normal_op;
 818                                 do_pop = 0;
 819                         }
 820                         else {
 821                                 /* Second live, first operand is dead here, bring it to tos. */
 822                                 if (op1_idx != 0) {
 823                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 824                                         if (op2_idx == 0)
 825                                                 op2_idx = op1_idx;
 826                                 }
 827                                 op1_idx = out_idx = 0;
 828                                 dst = tmpl->normal_op;
 829                                 do_pop = 0;
 830                         }
 831                 }
 832                 else {
 833                         /* Second operand is dead. */
 834                         if (is_vfp_live(op1->index, live)) {
 835                                 /* First operand is live: bring second to tos. */
 836                                 if (op2_idx != 0) {
 837                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 838                                         if (op1_idx == 0)
 839                                                 op1_idx = op2_idx;
 840                                 }
 841                                 op2_idx = out_idx = 0;
 842                                 dst = tmpl->normal_op;
 843                                 do_pop = 0;
 844                         }
 845                         else {
 846                                 /* Both operands are dead here, pop them from the stack. */
 847                                 if (op2_idx == 0) {
 848                                         out_idx = op1_idx;
 849                                         XCHG(op2_idx, op1_idx);
 850                                         if (op1_idx == op2_idx) {
 851                                                 /* Both are identically, no pop needed. */
 852                                                 dst = tmpl->reverse_op;
 853                                                 do_pop = 0;
 854                                         }
 855                                         else {
 856                                                 dst = tmpl->reverse_pop_op;
 857                                                 do_pop = 1;
 858                                         }
 859                                 }
 860                                 else if (op1_idx == 0) {
 861                                         out_idx = op2_idx;
 862                                         if (op1_idx == op2_idx) {
 863                                                 /* Both are identically, no pop needed. */
 864                                                 dst = tmpl->normal_op;
 865                                                 do_pop = 0;
 866                                         }
 867                                         else {
 868                                                 dst = tmpl->normal_pop_op;
 869                                                 do_pop = 1;
 870                                         }
 871                                 }
 872                                 else {
 873                                         /* Bring the first on top. */
 874                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 875                                         if (op1_idx == op2_idx) {
 876                                                 /* Both are identically, no pop needed. */
 877                                                 out_idx = op1_idx = op2_idx = 0;
 878                                                 dst = tmpl->normal_op;
 879                                                 do_pop = 0;
 880                                         }
 881                                         else {
 882                                                 op1_idx = 0;
 883                                                 out_idx = op2_idx;
 884                                                 dst = tmpl->normal_pop_op;
 885                                                 do_pop = 1;
 886                                         }
 887                                 }
 888                         }
 889                 }
 890         }
 891         else {
 892                 /* first operand is an address mode */
 893                 if (is_vfp_live(op2->index, live)) {
 894                         /* second operand is live: push it here */
 895                         x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
 896                 }
 897                 else {
 898                         /* second operand is dead: bring it to tos */
 899                         if (op2_idx != 0)
 900                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 901                 }
 902                 op2_idx = out_idx = 0;
 903                 dst = tmpl->normal_op;
 904                 do_pop = 0;
 905         }
 906
 907         x87_set_st(state, arch_register_get_index(out), x87_patch_insn(n, dst), out_idx);
 908         if (do_pop)
 909                 x87_pop(state);
 910
 911         /* patch the operation */
 912         attr = get_ia32_attr(n);
 913         if (op1_idx >= 0)
 914                 attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 915         attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
 916         attr->x87[2] = out = &ia32_st_regs[out_idx];
 917
 918         DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
 919                 arch_register_get_name(op2), arch_register_get_name(op1),
 920                 arch_register_get_name(out)));
 921 }
 922
 923 /**
 924  * Simulate a virtual Unop.
 925  *
 926  * @param state  the x87 state
 927  * @param n      the node that should be simulated (and patched)
 928  * @param env    the architecture environment
 929  * @param op     the x87 opcode that will replace n's opcode
 930  */
 931 static void sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 932         int op1_idx, out_idx;
 933         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, UNOP_IDX));
 934         const arch_register_t *out = arch_get_irn_register(env, n);
 935         ia32_attr_t *attr;
 936         unsigned live = vfp_liveness_nodes_live_at(env, n);
 937
 938         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name));
 939   DEBUG_ONLY(vfp_dump_live(live));
 940
 941         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 942
 943         if (is_vfp_live(op1->index, live)) {
 944                 /* push the operand here */
 945                 x87_create_fpush(env, state, n, op1_idx, UNOP_IDX);
 946         }
 947         else {
 948                 /* operand is dead, bring it to tos */
 949                 if (op1_idx != 0)
 950                         x87_create_fxch(state, n, op1_idx, UNOP_IDX);
 951         }
 952
 953         x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op));
 954         op1_idx = out_idx = 0;
 955         attr = get_ia32_attr(n);
 956         attr->x87[0] = op1 = &ia32_st_regs[0];
 957         attr->x87[2] = out = &ia32_st_regs[0];
 958         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
 959 }
 960
 961 /**
 962  * Simulate a virtual Load instruction.
 963  *
 964  * @param state  the x87 state
 965  * @param n      the node that should be simulated (and patched)
 966  * @param env    the architecture environment
 967  * @param op     the x87 opcode that will replace n's opcode
 968  */
 969 static void sim_load(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 970         const arch_register_t *out = arch_get_irn_register(env, n);
 971         ia32_attr_t *attr;
 972
 973         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 974         x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
 975         attr = get_ia32_attr(n);
 976         attr->x87[2] = out = &ia32_st_regs[0];
 977         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 978 }
 979
 980 /**
 981  * Simulate a virtual Store.
 982  *
 983  * @param state  the x87 state
 984  * @param n      the node that should be simulated (and patched)
 985  * @param env    the architecture environment
 986  * @param op     the x87 store opcode
 987  * @param op_p   the x87 store and pop opcode
 988  */
 989 static void sim_store(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op, ir_op *op_p) {
 990         int op2_idx;
 991         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, STORE_VAL_IDX));
 992         ia32_attr_t *attr;
 993         unsigned live = vfp_liveness_nodes_live_at(env, n);
 994
 995         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 996
 997         DB((dbg, LEVEL_1, ">>> %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
 998
 999         /* we can only store the tos to memory */
1000         if (op2_idx != 0)
1001                 x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX);
1002
1003         if (is_vfp_live(op2->index, live))
1004                 x87_patch_insn(n, op);
1005         else {
1006                 x87_pop(state);
1007                 x87_patch_insn(n, op_p);
1008         }
1009
1010         attr = get_ia32_attr(n);
1011         attr->x87[1] = op2 = &ia32_st_regs[0];
1012         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
1013 }
1014
1015 /**
1016  * Simulate a virtual Phi.
1017  * Just for cosmetic reasons change the mode of Phi nodes to mode_E.
1018  *
1019  * @param state  the x87 state
1020  * @param n      the node that should be simulated (and patched)
1021  * @param env    the architecture environment
1022  */
1023 static void sim_Phi(x87_state *state, ir_node *n, const arch_env_t *env) {
1024         ir_mode *mode = get_irn_mode(n);
1025
1026         if (mode_is_float(mode))
1027                 set_irn_mode(n, mode_E);
1028 }
1029
1030
1031 #define _GEN_BINOP(op, rev) \
1032 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1033         exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \
1034         sim_binop(state, n, env, &tmpl); \
1035 }
1036
1037 #define GEN_BINOP(op)     _GEN_BINOP(op, op)
1038 #define GEN_BINOPR(op)  _GEN_BINOP(op, op##r)
1039
1040 #define GEN_LOAD2(op, nop) \
1041 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1042         sim_load(state, n, env, op_ia32_##nop); \
1043 }
1044
1045 #define GEN_LOAD(op)    GEN_LOAD2(op, op)
1046
1047 #define GEN_UNOP(op) \
1048 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1049         sim_unop(state, n, env, op_ia32_##op); \
1050 }
1051
1052 #define GEN_STORE(op) \
1053 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1054         sim_store(state, n, env, op_ia32_##op, op_ia32_##op##p); \
1055 }
1056
1057 /* all stubs */
1058 GEN_BINOP(fadd)
1059 GEN_BINOPR(fsub)
1060 GEN_BINOP(fmul)
1061 GEN_BINOPR(fdiv)
1062
1063 GEN_UNOP(fabs)
1064 GEN_UNOP(fchs)
1065 GEN_UNOP(fsin)
1066 GEN_UNOP(fcos)
1067 GEN_UNOP(fsqrt)
1068
1069 GEN_LOAD(fld)
1070 GEN_LOAD(fild)
1071 GEN_LOAD(fldz)
1072 GEN_LOAD(fld1)
1073 GEN_LOAD2(fConst, fldConst)
1074
1075 GEN_STORE(fst)
1076 GEN_STORE(fist)
1077
1078 /**
1079  * Simulate a fCondJmp.
1080  *
1081  * @param state  the x87 state
1082  * @param n      the node that should be simulated (and patched)
1083  * @param env    the architecture environment
1084  */
1085 static void sim_fCondJmp(x87_state *state, ir_node *n, const arch_env_t *env) {
1086         int op2_idx, op1_idx = -1, pop_cnt = 0;
1087         ia32_attr_t *attr;
1088         ir_op *dst;
1089         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
1090         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
1091         unsigned live = vfp_liveness_nodes_live_at(env, n);
1092
1093         DB((dbg, LEVEL_1, ">>> %s %s, %s\n", get_irn_opname(n),
1094                 arch_register_get_name(op2), arch_register_get_name(op1)));
1095   DEBUG_ONLY(vfp_dump_live(live));
1096
1097         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
1098
1099         /* BEWARE: check for comp a,a cases, they might happen */
1100         if (op1->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]) {
1101                 /* first operand is a vfp register */
1102                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1103
1104                 if (is_vfp_live(op2->index, live)) {
1105                         /* second operand is live */
1106
1107                         if (is_vfp_live(op1->index, live)) {
1108                                 /* both operands are live: move one of them to tos */
1109                                 if (op2_idx == 0) {
1110                                         XCHG(op2_idx, op1_idx);
1111                                         dst = op_ia32_fcomrJmp;
1112                                 }
1113                                 else if (op1_idx == 0) {
1114                                         dst = op_ia32_fcomJmp;
1115                                 }
1116                                 else {
1117                                         /* bring the first on top */
1118                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1119                                         if (op1_idx == op2_idx)
1120                                                 op2_idx = 0;
1121                                         op1_idx = 0;
1122                                         dst     = op_ia32_fcomJmp;
1123                                 }
1124                         }
1125                         else {
1126                                 /* second live, first operand is dead here, bring it to tos.
1127                                    This means further, op1_idx != op2_idx. */
1128                                 if (op1_idx != 0) {
1129                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1130                                         if (op2_idx == 0)
1131                                                 op2_idx = op1_idx;
1132                                 }
1133                                 op1_idx = 0;
1134                                 dst     = op_ia32_fcompJmp;
1135                                 pop_cnt = 1;
1136                         }
1137                 }
1138                 else {
1139                         /* second operand is dead */
1140                         if (is_vfp_live(op1->index, live)) {
1141                                 /* first operand is live: bring second to tos.
1142                                    This means further, op1_idx != op2_idx. */
1143                                 if (op2_idx != 0) {
1144                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1145                                         if (op1_idx == 0)
1146                                                 op1_idx = op2_idx;
1147                                 }
1148                                 op2_idx = 0;
1149                                 dst     = op_ia32_fcomrpJmp;
1150                                 pop_cnt = 1;
1151                         }
1152                         else {
1153                                 /* both operands are dead here, check first for identity. */
1154                                 if (op1_idx == op2_idx) {
1155                                         /* identically, one one needed */
1156                                         if (op1_idx != 0) {
1157                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1158                                                 op1_idx = op2_idx = 0;
1159                                         }
1160                                         dst     = op_ia32_fcompJmp;
1161                                         pop_cnt = 1;
1162                                 }
1163                                 /* different, move them to st and st(1) and pop both.
1164                                    The tricky part is to get one into st(1).*/
1165                                 else if (op2_idx == 1) {
1166                                         /* good, second operand is already in the right place, move the first */
1167                                         if (op1_idx != 0) {
1168                                                 /* bring the first on top */
1169                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1170                                                 op1_idx = 0;
1171                                         }
1172                                         dst     = op_ia32_fcomppJmp;
1173                                         pop_cnt = 2;
1174                                 }
1175                                 else if (op1_idx == 1) {
1176                                         /* good, first operand is already in the right place, move the second */
1177                                         if (op2_idx != 0) {
1178                                                 /* bring the first on top */
1179                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1180                                                 op2_idx = 0;
1181                                         }
1182                                         dst     = op_ia32_fcomrppJmp;
1183                                         pop_cnt = 2;
1184                                 }
1185                                 else {
1186                                         /* if one is already the TOS, we need two fxch */
1187                                         if (op1_idx == 0) {
1188                                                 /* first one is TOS, move to st(1) */
1189                                                 x87_create_fxch(state, n, 1, BINOP_IDX_1);
1190                                                 op1_idx = 1;
1191                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1192                                                 op2_idx = 0;
1193                                                 dst     = op_ia32_fcomrppJmp;
1194                                                 pop_cnt = 2;
1195                                         }
1196                                         else if (op2_idx == 0) {
1197                                                 /* second one is TOS, move to st(1) */
1198                                                 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1199                                                 op2_idx = 1;
1200                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1201                                                 op1_idx = 0;
1202                                                 dst     = op_ia32_fcomrppJmp;
1203                                                 pop_cnt = 2;
1204                                         }
1205                                         else {
1206                                                 /* none of them is either TOS or st(1), 3 fxch needed */
1207                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1208                                                 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1209                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1210                                                 op1_idx = 0;
1211                                                 op2_idx = 1;
1212                                                 dst     = op_ia32_fcomppJmp;
1213                                                 pop_cnt = 2;
1214                                         }
1215                                 }
1216                         }
1217                 }
1218         }
1219         else {
1220                 /* first operand is an address mode */
1221                 if (is_vfp_live(op2->index, live)) {
1222                         /* second operand is live: bring it to TOS */
1223                         if (op2_idx != 0) {
1224                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1225                                 op2_idx = 0;
1226                         }
1227                         dst = op_ia32_fcomrJmp;
1228                 }
1229                 else {
1230                         /* second operand is dead: bring it to tos */
1231                         if (op2_idx != 0) {
1232                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1233                                 op2_idx = 0;
1234                         }
1235                 }
1236                 dst     = op_ia32_fcomrpJmp;
1237                 pop_cnt = 1;
1238         }
1239
1240         x87_patch_insn(n, dst);
1241         if (pop_cnt > 1)
1242                 x87_pop(state);
1243         if (pop_cnt > 0)
1244                 x87_pop(state);
1245
1246         /* patch the operation */
1247         attr = get_ia32_attr(n);
1248         if (op1_idx >= 0)
1249                 attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
1250         attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
1251
1252         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(n),
1253                 arch_register_get_name(op2), arch_register_get_name(op1)));
1254 }
1255
1256 /**
1257  * Simulate a be_Copy.
1258  *
1259  * @param state  the x87 state
1260  * @param n      the node that should be simulated (and patched)
1261  * @param env    the architecture environment
1262  */
1263 static void sim_Copy(x87_state *state, ir_node *n, const arch_env_t *env) {
1264         ir_mode *mode = get_irn_mode(n);
1265
1266         if (mode_is_float(mode)) {
1267                 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, 0));
1268                 const arch_register_t *out = arch_get_irn_register(env, n);
1269                 ir_node *node, *next;
1270                 ia32_attr_t *attr;
1271                 int op1_idx, out_idx;
1272                 unsigned live = vfp_liveness_nodes_live_at(env, n);
1273
1274                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1275
1276                 DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(n),
1277                         arch_register_get_name(op1), arch_register_get_name(out)));
1278           DEBUG_ONLY(vfp_dump_live(live));
1279
1280                 if (is_vfp_live(op1->index, live)) {
1281                         /* operand is still live,a real copy */
1282                         node = new_rd_ia32_fpush(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
1283                         arch_set_irn_register(env, node, out);
1284
1285                         x87_push(state, arch_register_get_index(out), node);
1286
1287                         attr = get_ia32_attr(node);
1288                         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
1289                         attr->x87[2] = out = &ia32_st_regs[0];
1290
1291                         next = sched_next(n);
1292                         sched_remove(n);
1293                         exchange(n, node);
1294                         sched_add_before(next, node);
1295                         DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(node), op1->name, out->name));
1296                 }
1297                 else {
1298                         out_idx = x87_on_stack(state, arch_register_get_index(out));
1299
1300                         if (out_idx >= 0 && out_idx != op1_idx) {
1301                                 /* op1 must be killed and placed where out is */
1302                                 if (out_idx == 0) {
1303                                         /* best case, simple remove and rename */
1304                                         x87_patch_insn(n, op_ia32_Pop);
1305                                         attr = get_ia32_attr(n);
1306                                         attr->x87[0] = op1 = &ia32_st_regs[0];
1307
1308                                         x87_pop(state);
1309                                         x87_set_st(state, arch_register_get_index(out), n, op1_idx - 1);
1310                                 }
1311                                 else {
1312                                         /* move op1 to tos, store and pop it */
1313                                         if (op1_idx != 0) {
1314                                                 x87_create_fxch(state, n, op1_idx, 0);
1315                                                 op1_idx = 0;
1316                                         }
1317                                         x87_patch_insn(n, op_ia32_Pop);
1318                                         attr = get_ia32_attr(n);
1319                                         attr->x87[0] = op1 = &ia32_st_regs[out_idx];
1320
1321                                         x87_pop(state);
1322                                         x87_set_st(state, arch_register_get_index(out), n, out_idx - 1);
1323                                 }
1324                                 DB((dbg, LEVEL_1, ">>> %s %s\n", get_irn_opname(n), op1->name));
1325                         }
1326                         else {
1327                                 /* just a virtual copy */
1328                                 x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx);
1329                                 sched_remove(n);
1330                                 DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n)));
1331                                 exchange(n, get_unop_op(n));
1332                         }
1333                 }
1334         }
1335 }
1336
1337 /**
1338  * Simulate a be_Call.
1339  *
1340  * @param state  the x87 state
1341  * @param n      the node that should be simulated
1342  * @param env    the architecture environment
1343  */
1344 static void sim_Call(x87_state *state, ir_node *n, const arch_env_t *env) {
1345         ir_type *call_tp = be_Call_get_type(n);
1346
1347         /* at the begin of a call the x87 state should be empty */
1348         assert(state->depth == 0 && "stack not empty before call");
1349
1350         /*
1351          * If the called function returns a float, it is returned in st(0).
1352          * This even happens if the return value is NOT used.
1353          * Moreover, only one return result is supported.
1354          */
1355         if (get_method_n_ress(call_tp) > 0) {
1356                 ir_type *res_type = get_method_res_type(call_tp, 0);
1357                 ir_mode *mode     = get_type_mode(res_type);
1358
1359                 if (mode && mode_is_float(mode)) {
1360                         /*
1361                          * TODO: what to push here? The result might be unused and currently
1362                          * we have no possibility to detect this :-(
1363                          */
1364                         x87_push(state, 0, n);
1365                 }
1366         }
1367 }
1368
1369 /**
1370  * Simulate a be_Spill.
1371  *
1372  * @param state  the x87 state
1373  * @param n      the node that should be simulated (and patched)
1374  * @param env    the architecture environment
1375  *
1376  * Should not happen, spills are lowered before x87 simulator see them.
1377  */
1378 static void sim_Spill(x87_state *state, ir_node *n, const arch_env_t *env) {
1379         assert(0 && "Spill not lowered");
1380         sim_fst(state, n, env);
1381 }
1382
1383 /**
1384  * Simulate a be_Reload.
1385  *
1386  * @param state  the x87 state
1387  * @param n      the node that should be simulated (and patched)
1388  * @param env    the architecture environment
1389  *
1390  * Should not happen, reloads are lowered before x87 simulator see them.
1391  */
1392 static void sim_Reload(x87_state *state, ir_node *n, const arch_env_t *env) {
1393         assert(0 && "Reload not lowered");
1394         sim_fld(state, n, env);
1395 }
1396
1397 /**
1398  * Simulate a be_Return.
1399  *
1400  * @param state  the x87 state
1401  * @param n      the node that should be simulated (and patched)
1402  * @param env    the architecture environment
1403  */
1404 static void sim_Return(x87_state *state, ir_node *n, const arch_env_t *env) {
1405         assert(x87_get_depth(state) == 1);
1406         x87_pop(state);
1407 }
1408
1409 /**
1410  * Kill any dead registers at block start by popping them from the stack.
1411  *
1412  * @param sim          the simulator handle
1413  * @param block        the current block
1414  * @param start_state  the x87 state at the begin of the block
1415  */
1416 static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state *start_state) {
1417         x87_state *state = start_state;
1418         ir_node *first_insn = sched_first(block);
1419         ir_node *keep = NULL;
1420         unsigned live = vfp_liveness_nodes_live_at(sim->env, block);
1421         unsigned kill_mask;
1422         int i, depth, num_pop;
1423
1424         kill_mask = 0;
1425         depth = x87_get_depth(state);
1426         for (i = depth - 1; i >= 0; --i) {
1427                 int reg = x87_get_st_reg(state, i);
1428
1429                 if (! is_vfp_live(reg, live))
1430                         kill_mask |= (1 << i);
1431         }
1432
1433         if (kill_mask) {
1434                 /* create a new state, will be changed */
1435                 state = x87_clone_state(sim, state);
1436
1437                 DB((dbg, LEVEL_1, "Killing deads:\n"));
1438                 DEBUG_ONLY(vfp_dump_live(live));
1439                 DEBUG_ONLY(x87_dump_stack(state));
1440
1441                 /* now kill registers */
1442                 while (kill_mask) {
1443                         /* we can only kill from TOS, so bring them up */
1444                         if (! (kill_mask & 1)) {
1445                                 /* search from behind, because we can to a double-pop */
1446                                 for (i = depth - 1; i >= 0; --i) {
1447                                         if (kill_mask & (1 << i)) {
1448                                                 kill_mask &= ~(1 << i);
1449                                                 kill_mask |= 1;
1450                                                 break;
1451                                         }
1452                                 }
1453
1454                                 if (keep)
1455                                         x87_set_st(state, -1, keep, i);
1456                                 keep = x87_create_fxch(state, first_insn, i, -1);
1457                         }
1458                         else if (! keep)
1459                                 keep = x87_get_st_node(state, 0);
1460
1461                         if ((kill_mask & 3) == 3) {
1462                                 /* we can do a double-pop */
1463                                 num_pop = 2;
1464                         }
1465                         else {
1466                                 /* only a single pop */
1467                                 num_pop = 1;
1468                         }
1469
1470                         depth -= num_pop;
1471                         kill_mask >>= num_pop;
1472                         keep = x87_create_fpop(sim->env, state, first_insn, num_pop, keep);
1473                 }
1474                 add_End_keepalive(get_irg_end(get_irn_irg(block)), keep);
1475         }
1476         return state;
1477 }
1478
1479 /**
1480  * Run a simulation and fix all virtual instructions for a block.
1481  *
1482  * @param sim          the simulator handle
1483  * @param block        the current block
1484  *
1485  * @return non-zero if simulation is complete,
1486  *         zero if the simulation must be rerun
1487  */
1488 static int x87_simulate_block(x87_simulator *sim, ir_node *block) {
1489         ir_node *n, *next;
1490         blk_state *bl_state = x87_get_bl_state(sim, block);
1491         x87_state *state = bl_state->begin;
1492         const ir_edge_t *edge;
1493         ir_node *start_block;
1494
1495         /* if we have no assigned start state, we must wait ... */
1496         if (! state)
1497                 return 0;
1498
1499         assert(bl_state->end == NULL);
1500
1501         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
1502
1503         /* at block begin, kill all dead registers */
1504         state = x87_kill_deads(sim, block, state);
1505
1506         /* beware, n might changed */
1507         for (n = sched_first(block); !sched_is_end(n); n = next) {
1508                 ir_op *op = get_irn_op(n);
1509
1510                 next = sched_next(n);
1511                 if (op->ops.generic) {
1512                         sim_func func = (sim_func)op->ops.generic;
1513
1514                         /* have work to do */
1515                         if (state == bl_state->begin) {
1516                                 /* create a new state, will be changed */
1517                                 state = x87_clone_state(sim, state);
1518                         }
1519
1520                         /* simulate it */
1521                         (*func)(state, n, sim->env);
1522                 }
1523         }
1524
1525         start_block = get_irg_start_block(get_irn_irg(block));
1526
1527         /* check if the state must be shuffled */
1528         foreach_block_succ(block, edge) {
1529                 ir_node *succ = get_edge_src_irn(edge);
1530                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1531
1532                 if (succ_state->begin && succ != start_block) {
1533                         /* There is already a begin state for this block, bad.
1534                            Do the necessary permutations.
1535                            Note that critical edges are removed, so this is always possible. */
1536                         x87_shuffle(sim, block, state, succ, succ_state->begin);
1537
1538                         /* Note further, that there can be only one such situation,
1539                            so we can break here. */
1540                         break;
1541                 }
1542         }
1543         bl_state->end = state;
1544
1545         /* now propagate the state to all successor blocks */
1546         foreach_block_succ(block, edge) {
1547                 ir_node *succ = get_edge_src_irn(edge);
1548                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1549
1550                 if (! succ_state->begin)
1551                         succ_state->begin = state;
1552         }
1553
1554         return 1;
1555 }
1556
1557 /**
1558  * Create a new x87 simulator.
1559  *
1560  * @param sim   a simulator handle, will be initialized
1561  * @param irg   the current graph
1562  * @param env   the architecture environment
1563  */
1564 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env_t *env) {
1565         obstack_init(&sim->obst);
1566         sim->blk_states = pmap_create();
1567         sim->env        = env;
1568
1569         FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
1570         firm_dbg_set_mask(dbg, SET_LEVEL_2);
1571
1572         DB((dbg, LEVEL_1, "--------------------------------\n"
1573                 "x87 Simulator started for %+F\n", irg));
1574
1575   /* set the generic function pointer of instruction we must simulate */
1576         clear_irp_opcodes_generic_func();
1577
1578 #define ASSOC(op)       (op_ ## op)->ops.generic = (op_func)(sim_##op)
1579 #define ASSOC_IA32(op)  (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
1580 #define ASSOC_BE(op)    (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
1581         ASSOC_IA32(fConst);
1582         ASSOC_IA32(fld);
1583         ASSOC_IA32(fild);
1584         ASSOC_IA32(fld1);
1585         ASSOC_IA32(fldz);
1586         ASSOC_IA32(fadd);
1587         ASSOC_IA32(fsub);
1588         ASSOC_IA32(fmul);
1589         ASSOC_IA32(fdiv);
1590         ASSOC_IA32(fldz);
1591         ASSOC_IA32(fabs);
1592         ASSOC_IA32(fchs);
1593         ASSOC_IA32(fsin);
1594         ASSOC_IA32(fcos);
1595         ASSOC_IA32(fsqrt);
1596         ASSOC_IA32(fist);
1597         ASSOC_IA32(fst);
1598         ASSOC_IA32(fCondJmp);
1599         ASSOC_BE(Copy);
1600         ASSOC_BE(Call);
1601         ASSOC_BE(Spill);
1602         ASSOC_BE(Reload);
1603         ASSOC_BE(Return);
1604         ASSOC(Phi);
1605 #undef ASSOC_BE
1606 #undef ASSOC_IA32
1607 #undef ASSOC
1608 }
1609
1610 /**
1611  * Destroy a x87 simulator.
1612  *
1613  * @param sim  the simulator handle
1614  */
1615 static void x87_destroy_simulator(x87_simulator *sim) {
1616         pmap_destroy(sim->blk_states);
1617         obstack_free(&sim->obst, NULL);
1618         DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
1619 }
1620
1621 /**
1622  * Run a simulation and fix all virtual instructions for a graph.
1623  *
1624  * @param env       the architecture environment
1625  * @param irg       the current graph
1626  * @param blk_list  the block schedule list
1627  *
1628  * Needs a block-schedule.
1629  */
1630 void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) {
1631         ir_node *block, *start_block;
1632         pdeq *worklist;
1633         blk_state *bl_state;
1634         x87_simulator sim;
1635         int i;
1636
1637         /* we need liveness info for the current graph */
1638         be_liveness(irg);
1639
1640         /* create the simulator */
1641         x87_init_simulator(&sim, irg, env);
1642
1643         start_block = get_irg_start_block(irg);
1644         bl_state = x87_get_bl_state(&sim, start_block);
1645
1646         /* start with the empty state */
1647         bl_state->begin = empty;
1648
1649         worklist = new_pdeq();
1650
1651         /* create the worklist for the schedule. */
1652         for (i = 0; i < ARR_LEN(blk_list); ++i)
1653                 pdeq_putr(worklist, blk_list[i]);
1654
1655         /* iterate */
1656         do {
1657                 block = pdeq_getl(worklist);
1658                 if (! x87_simulate_block(&sim, block)) {
1659                         pdeq_putr(worklist, block);
1660                         continue;
1661                 }
1662         } while (! pdeq_empty(worklist));
1663
1664         /* kill it */
1665         x87_destroy_simulator(&sim);
1666 }