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_t.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 /* Forward declaration. */
  54 typedef struct _x87_simulator x87_simulator;
  55
  56 /**
  57  * An exchange template.
  58  * Note that our virtual functions have the same inputs
  59  * and attributes as the real ones, so we can simple exchange
  60  * their opcodes!
  61  * Further, x87 supports inverse instructions, so we can handle them.
  62  */
  63 typedef struct _exchange_tmpl {
  64         ir_op *normal_op;       /**< the normal one */
  65         ir_op *reverse_op;      /**< the reverse one if exists */
  66         ir_op *normal_pop_op;   /**< the normal one with tos pop */
  67         ir_op *reverse_pop_op;  /**< the reverse one with tos pop */
  68 } exchange_tmpl;
  69
  70 /**
  71  * An entry on the simulated x87 stack.
  72  */
  73 typedef struct _st_entry {
  74         int     reg_idx;        /**< the virtual register index of this stack value */
  75         ir_node *node;          /**< the node that produced this value */
  76 } st_entry;
  77
  78 /**
  79  * The x87 state.
  80  */
  81 typedef struct _x87_state {
  82         st_entry st[N_x87_REGS];  /**< the register stack */
  83         int depth;                /**< the current stack depth */
  84         int tos;                  /**< position of the tos */
  85         x87_simulator *sim;       /**< The simulator. */
  86 } x87_state;
  87
  88 /** An empty state, used for blocks without fp instructions. */
  89 static x87_state _empty = { { {0, NULL}, }, 0, 0 };
  90 static x87_state *empty = (x87_state *)&_empty;
  91
  92 /** The type of an instruction simulator function. */
  93 typedef int (*sim_func)(x87_state *state, ir_node *n);
  94
  95 /**
  96  * A block state: Every block has a x87 state at the beginning and at the end.
  97  */
  98 typedef struct _blk_state {
  99         x87_state *begin;   /**< state at the begin or NULL if not assigned */
 100         x87_state *end;     /**< state at the end or NULL if not assigned */
 101 } blk_state;
 102
 103 #define PTR_TO_BLKSTATE(p)      ((blk_state *)(p))
 104
 105 /**
 106  * The x87 simulator.
 107  */
 108 struct _x87_simulator {
 109         struct obstack obst;      /**< An obstack for fast allocating. */
 110         pmap *blk_states;         /**< Map blocks to states. */
 111         const arch_env_t *env;    /**< The architecture environment. */
 112         unsigned char *live;      /**< Liveness information. */
 113         unsigned n_idx;           /**< The cached get_irg_last_idx() result. */
 114 };
 115
 116 /**
 117  * Returns the current stack depth.
 118  *
 119  * @param state  the x87 state
 120  *
 121  * @return the x87 stack depth
 122  */
 123 static int x87_get_depth(const x87_state *state) {
 124         return state->depth;
 125 }
 126
 127 /**
 128  * Check if the state is empty.
 129  *
 130  * @param state  the x87 state
 131  *
 132  * returns non-zero if the x87 stack is empty
 133  */
 134 static int x87_state_is_empty(const x87_state *state) {
 135         return state->depth == 0;
 136 }
 137
 138 /**
 139  * Return the virtual register index at st(pos).
 140  *
 141  * @param state  the x87 state
 142  * @param pos    a stack position
 143  *
 144  * @return the vfp register index that produced the value at st(pos)
 145  */
 146 static int x87_get_st_reg(const x87_state *state, int pos) {
 147         assert(pos < state->depth);
 148         return state->st[MASK_TOS(state->tos + pos)].reg_idx;
 149 }
 150
 151 /**
 152  * Return the node at st(pos).
 153  *
 154  * @param state  the x87 state
 155  * @param pos    a stack position
 156  *
 157  * @return the IR node that produced the value at st(pos)
 158  */
 159 static ir_node *x87_get_st_node(const x87_state *state, int pos) {
 160         assert(pos < state->depth);
 161         return state->st[MASK_TOS(state->tos + pos)].node;
 162 }  /* x87_get_st_node */
 163
 164 #ifdef DEBUG_libfirm
 165 /**
 166  * Dump the stack for debugging.
 167  *
 168  * @param state  the x87 state
 169  */
 170 static void x87_dump_stack(const x87_state *state) {
 171         int i;
 172
 173         for (i = state->depth - 1; i >= 0; --i) {
 174                 DB((dbg, LEVEL_2, "vf%d ", x87_get_st_reg(state, i)));
 175         }
 176         DB((dbg, LEVEL_2, "<-- TOS\n"));
 177 }  /* x87_dump_stack */
 178 #endif /* DEBUG_libfirm */
 179
 180 /**
 181  * Set a virtual register to st(pos).
 182  *
 183  * @param state    the x87 state
 184  * @param reg_idx  the vfp register index that should be set
 185  * @param node     the IR node that produces the value of the vfp register
 186  * @param pos      the stack position where the new value should be entered
 187  */
 188 static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) {
 189         assert(0 < state->depth);
 190         state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx;
 191         state->st[MASK_TOS(state->tos + pos)].node    = node;
 192
 193         DB((dbg, LEVEL_2, "After SET_REG:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 194 }  /* x87_set_st */
 195
 196 /**
 197  * Set the tos virtual register.
 198  *
 199  * @param state    the x87 state
 200  * @param reg_idx  the vfp register index that should be set
 201  * @param node     the IR node that produces the value of the vfp register
 202  */
 203 static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node) {
 204         x87_set_st(state, reg_idx, node, 0);
 205 }  /* x87_set_tos */
 206
 207 #if 0
 208 /**
 209  * Flush the x87 stack.
 210  *
 211  * @param state    the x87 state
 212  */
 213 static void x87_flush(x87_state *state) {
 214         state->depth = 0;
 215         state->tos   = 0;
 216 }  /* x87_flush */
 217 #endif
 218
 219 /**
 220  * Swap st(0) with st(pos).
 221  *
 222  * @param state    the x87 state
 223  * @param pos      the stack position to change the tos with
 224  */
 225 static void x87_fxch(x87_state *state, int pos) {
 226         st_entry entry;
 227         assert(pos < state->depth);
 228
 229         entry = state->st[MASK_TOS(state->tos + pos)];
 230         state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
 231         state->st[MASK_TOS(state->tos)] = entry;
 232
 233         DB((dbg, LEVEL_2, "After FXCH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 234 }  /* x87_fxch */
 235
 236 /**
 237  * Convert a virtual register to the stack index.
 238  *
 239  * @param state    the x87 state
 240  * @param reg_idx  the register vfp index
 241  *
 242  * @return the stack position where the register is stacked
 243  *         or -1 if the virtual register was not found
 244  */
 245 static int x87_on_stack(const x87_state *state, int reg_idx) {
 246         int i, tos = state->tos;
 247
 248         for (i = 0; i < state->depth; ++i)
 249                 if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx)
 250                         return i;
 251         return -1;
 252 }  /* x87_on_stack */
 253
 254 /**
 255  * Push a virtual Register onto the stack, double pushed allowed.
 256  *
 257  * @param state     the x87 state
 258  * @param reg_idx   the register vfp index
 259  * @param node      the node that produces the value of the vfp register
 260  */
 261 static void x87_push_dbl(x87_state *state, int reg_idx, ir_node *node) {
 262         assert(state->depth < N_x87_REGS && "stack overrun");
 263
 264         ++state->depth;
 265         state->tos = MASK_TOS(state->tos - 1);
 266         state->st[state->tos].reg_idx = reg_idx;
 267         state->st[state->tos].node    = node;
 268
 269         DB((dbg, LEVEL_2, "After PUSH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 270 }  /* x87_push_dbl */
 271
 272 /**
 273  * Push a virtual Register onto the stack, double pushes are NOT allowed..
 274  *
 275  * @param state     the x87 state
 276  * @param reg_idx   the register vfp index
 277  * @param node      the node that produces the value of the vfp register
 278  * @param dbl_push  if != 0 double pushes are allowed
 279  */
 280 static void x87_push(x87_state *state, int reg_idx, ir_node *node) {
 281         assert(x87_on_stack(state, reg_idx) == -1 && "double push");
 282
 283         x87_push_dbl(state, reg_idx, node);
 284 }  /* x87_push */
 285
 286 /**
 287  * Pop a virtual Register from the stack.
 288  */
 289 static void x87_pop(x87_state *state) {
 290         assert(state->depth > 0 && "stack underrun");
 291
 292         --state->depth;
 293         state->tos = MASK_TOS(state->tos + 1);
 294
 295         DB((dbg, LEVEL_2, "After POP:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 296 }  /* x87_pop */
 297
 298 /**
 299  * Returns the block state of a block.
 300  *
 301  * @param sim    the x87 simulator handle
 302  * @param block  the current block
 303  *
 304  * @return the block state
 305  */
 306 static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) {
 307         pmap_entry *entry = pmap_find(sim->blk_states, block);
 308
 309         if (! entry) {
 310                 blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
 311                 bl_state->begin = NULL;
 312                 bl_state->end   = NULL;
 313
 314                 pmap_insert(sim->blk_states, block, bl_state);
 315                 return bl_state;
 316         }
 317
 318         return PTR_TO_BLKSTATE(entry->value);
 319 }  /* x87_get_bl_state */
 320
 321 /**
 322  * Creates a new x87 state.
 323  *
 324  * @param sim    the x87 simulator handle
 325  *
 326  * @return a new x87 state
 327  */
 328 static x87_state *x87_alloc_state(x87_simulator *sim) {
 329         x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
 330
 331         res->sim = sim;
 332         return res;
 333 }  /* x87_alloc_state */
 334
 335 #if 0
 336 /**
 337  * Create a new empty x87 state.
 338  *
 339  * @param sim    the x87 simulator handle
 340  *
 341  * @return a new empty x87 state
 342  */
 343 static x87_state *x87_alloc_empty_state(x87_simulator *sim) {
 344         x87_state *res = x87_alloc_state(sim);
 345
 346         x87_flush(res);
 347         return res;
 348 }  /* x87_alloc_empty_state */
 349 #endif
 350
 351 /**
 352  * Clone a x87 state.
 353  *
 354  * @param sim    the x87 simulator handle
 355  * @param src    the x87 state that will be cloned
 356  *
 357  * @return a cloned copy of the src state
 358  */
 359 static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) {
 360         x87_state *res = x87_alloc_state(sim);
 361
 362         memcpy(res, src, sizeof(*res));
 363         return res;
 364 }  /* x87_clone_state */
 365
 366 /**
 367  * Patch a virtual instruction into a x87 one and return
 368  * the value node.
 369  *
 370  * @param n   the IR node to patch
 371  * @param op  the x87 opcode to patch in
 372  */
 373 static ir_node *x87_patch_insn(ir_node *n, ir_op *op) {
 374         ir_mode *mode = get_irn_mode(n);
 375         ir_node *res = n;
 376
 377         set_irn_op(n, op);
 378
 379         if (mode == mode_T) {
 380                 /* patch all Proj's */
 381                 const ir_edge_t *edge;
 382
 383                 foreach_out_edge(n, edge) {
 384                         ir_node *proj = get_edge_src_irn(edge);
 385                         if (is_Proj(proj)) {
 386                                 mode = get_irn_mode(proj);
 387                                 if (mode_is_float(mode)) {
 388                                         res = proj;
 389                                         set_irn_mode(proj, mode_E);
 390                                 }
 391                         }
 392                 }
 393         }
 394         else if (mode_is_float(mode))
 395                 set_irn_mode(n, mode_E);
 396         return res;
 397 }  /* x87_patch_insn */
 398
 399 /**
 400  * Returns the first Proj of a mode_T node having a given mode.
 401  *
 402  * @param n  the mode_T node
 403  * @param m  the desired mode of the Proj
 404  * @return The first Proj of mode @p m found or NULL.
 405  */
 406 static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m) {
 407         const ir_edge_t *edge;
 408
 409         assert(get_irn_mode(n) == mode_T && "Need mode_T node");
 410
 411         foreach_out_edge(n, edge) {
 412                 ir_node *proj = get_edge_src_irn(edge);
 413                 if (get_irn_mode(proj) == m)
 414                         return proj;
 415         }
 416
 417         return NULL;
 418 }  /* get_irn_Proj_for_mode */
 419
 420 /**
 421  * Wrap the arch_* function here so we can check for errors.
 422  */
 423 static const arch_register_t *x87_get_irn_register(x87_simulator *sim, const ir_node *irn) {
 424         const arch_register_t *res;
 425
 426         res = arch_get_irn_register(sim->env, irn);
 427         assert(res->reg_class->regs == ia32_vfp_regs);
 428         return res;
 429 }
 430
 431 /* -------------- x87 perm --------------- */
 432
 433 /**
 434  * Creates a fxch for shuffle.
 435  *
 436  * @param state     the x87 state
 437  * @param pos       parameter for fxch
 438  * @param block     the block were fxch is inserted
 439  *
 440  * Creates a new fxch node and reroute the user of the old node
 441  * to the fxch.
 442  *
 443  * @return the fxch node
 444  */
 445 static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block)
 446 {
 447         ir_node         *fxch;
 448         ia32_attr_t     *attr;
 449
 450         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(block), block, mode_E);
 451         attr = get_ia32_attr(fxch);
 452         attr->x87[0] = &ia32_st_regs[pos];
 453         attr->x87[2] = &ia32_st_regs[0];
 454
 455         keep_alive(fxch);
 456
 457         x87_fxch(state, pos);
 458         return fxch;
 459 }  /* x87_fxch_shuffle */
 460
 461 /**
 462  * Calculate the necessary permutations to reach dst_state.
 463  *
 464  * These permutations are done with fxch instructions and placed
 465  * at the end of the block.
 466  *
 467  * Note that critical edges are removed here, so we need only
 468  * a shuffle if the current block has only one successor.
 469  *
 470  * @param sim        the simulator handle
 471  * @param block      the current block
 472  * @param state      the current x87 stack state, might be modified
 473  * @param dst_block  the destination block
 474  * @param dst_state  destination state
 475  *
 476  * @return state
 477  */
 478 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, ir_node *dst_block, const x87_state *dst_state) {
 479         int      i, n_cycles, k, ri;
 480         unsigned cycles[4], all_mask;
 481         char     cycle_idx[4][8];
 482         ir_node  *fxch, *before, *after;
 483
 484         assert(state->depth == dst_state->depth);
 485
 486         /* Some mathematics here:
 487            If we have a cycle of length n that includes the tos,
 488            we need n-1 exchange operations.
 489            We can always add the tos and restore it, so we need
 490            n+1 exchange operations for a cycle not containing the tos.
 491            So, the maximum of needed operations is for a cycle of 7
 492            not including the tos == 8.
 493            This is the same number of ops we would need for using stores,
 494            so exchange is cheaper (we save the loads).
 495            On the other hand, we might need an additional exchange
 496            in the next block to bring one operand on top, so the
 497            number of ops in the first case is identical.
 498            Further, no more than 4 cycles can exists (4 x 2).
 499         */
 500         all_mask = (1 << (state->depth)) - 1;
 501
 502         for (n_cycles = 0; all_mask; ++n_cycles) {
 503                 int src_idx, dst_idx;
 504
 505                 /* find the first free slot */
 506                 for (i = 0; i < state->depth; ++i) {
 507                         if (all_mask & (1 << i)) {
 508                                 all_mask &= ~(1 << i);
 509
 510                                 /* check if there are differences here */
 511                                 if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
 512                                         break;
 513                         }
 514                 }
 515
 516                 if (! all_mask) {
 517                         /* no more cycles found */
 518                         break;
 519                 }
 520
 521                 k = 0;
 522                 cycles[n_cycles] = (1 << i);
 523                 cycle_idx[n_cycles][k++] = i;
 524                 for (src_idx = i; ; src_idx = dst_idx) {
 525                         dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
 526
 527                         if ((all_mask & (1 << dst_idx)) == 0)
 528                                 break;
 529
 530                         cycle_idx[n_cycles][k++] = dst_idx;
 531                         cycles[n_cycles] |=  (1 << dst_idx);
 532                         all_mask       &= ~(1 << dst_idx);
 533                 }
 534                 cycle_idx[n_cycles][k] = -1;
 535         }
 536
 537         if (n_cycles <= 0) {
 538                 /* no permutation needed */
 539                 return state;
 540         }
 541
 542         /* Hmm: permutation needed */
 543         DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
 544         DEBUG_ONLY(x87_dump_stack(state));
 545         DB((dbg, LEVEL_2, "                  to\n"));
 546         DEBUG_ONLY(x87_dump_stack(dst_state));
 547
 548
 549 #ifdef DEBUG_libfirm
 550         DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
 551         for (ri = 0; ri < n_cycles; ++ri) {
 552                 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
 553                 for (k = 0; cycle_idx[ri][k] != -1; ++k)
 554                         DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
 555                 DB((dbg, LEVEL_2, "\n"));
 556         }
 557 #endif
 558
 559         after = NULL;
 560
 561         /*
 562          * Find the place node must be insert.
 563          * We have only one successor block, so the last instruction should
 564          * be a jump.
 565          */
 566         before = sched_last(block);
 567         assert(is_cfop(before));
 568
 569         /* now do the permutations */
 570         for (ri = 0; ri < n_cycles; ++ri) {
 571                 if ((cycles[ri] & 1) == 0) {
 572                         /* this cycle does not include the tos */
 573                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block);
 574                         if (after)
 575                                 sched_add_after(after, fxch);
 576                         else
 577                                 sched_add_before(before, fxch);
 578                         after = fxch;
 579                 }
 580                 for (k = 1; cycle_idx[ri][k] != -1; ++k) {
 581                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][k], block);
 582                         if (after)
 583                                 sched_add_after(after, fxch);
 584                         else
 585                                 sched_add_before(before, fxch);
 586                         after = fxch;
 587                 }
 588                 if ((cycles[ri] & 1) == 0) {
 589                         /* this cycle does not include the tos */
 590                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block);
 591                         sched_add_after(after, fxch);
 592                 }
 593         }
 594         return state;
 595 }  /* x87_shuffle */
 596
 597 /**
 598  * Create a fxch node before another node.
 599  *
 600  * @param state   the x87 state
 601  * @param n       the node after the fxch
 602  * @param pos     exchange st(pos) with st(0)
 603  * @param op_idx  if >= 0, replace input op_idx of n with the fxch result
 604  *
 605  * @return the fxch
 606  */
 607 static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) {
 608         ir_node     *fxch;
 609         ia32_attr_t *attr;
 610
 611         x87_fxch(state, pos);
 612
 613         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), mode_E);
 614         attr = get_ia32_attr(fxch);
 615         attr->x87[0] = &ia32_st_regs[pos];
 616         attr->x87[2] = &ia32_st_regs[0];
 617
 618         keep_alive(fxch);
 619
 620         sched_add_before(n, fxch);
 621         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
 622         return fxch;
 623 }  /* x87_create_fxch */
 624
 625 /**
 626  * Create a fpush before node n.
 627  *
 628  * @param state     the x87 state
 629  * @param n         the node after the fpush
 630  * @param pos       push st(pos) on stack
 631  * @param op_idx    replace input op_idx of n with the fpush result
 632  */
 633 static void x87_create_fpush(x87_state *state, ir_node *n, int pos, int op_idx) {
 634         ir_node               *fpush, *pred = get_irn_n(n, op_idx);
 635         ia32_attr_t           *attr;
 636         const arch_register_t *out = x87_get_irn_register(state->sim, pred);
 637
 638         x87_push_dbl(state, arch_register_get_index(out), pred);
 639
 640         fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), mode_E);
 641         attr  = get_ia32_attr(fpush);
 642         attr->x87[0] = &ia32_st_regs[pos];
 643         attr->x87[2] = &ia32_st_regs[0];
 644
 645         keep_alive(fpush);
 646         sched_add_before(n, fpush);
 647
 648         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
 649 }  /* x87_create_fpush */
 650
 651 /**
 652  * Create a fpop before node n.
 653  *
 654  * @param state   the x87 state
 655  * @param n       the node after the fpop
 656  * @param num     pop 1 or 2 values
 657  * @param pred    node to use as predecessor of the fpop
 658  *
 659  * @return the fpop node
 660  */
 661 static ir_node *x87_create_fpop(x87_state *state, ir_node *n, int num, ir_node *pred) {
 662         ir_node *fpop = pred;
 663         ia32_attr_t *attr;
 664
 665         while (num > 0) {
 666                 keep_alive(pred);
 667
 668                 x87_pop(state);
 669                 fpop = new_rd_ia32_fpop(NULL, get_irn_irg(n), get_nodes_block(n), mode_E);
 670                 attr = get_ia32_attr(fpop);
 671                 attr->x87[0] = &ia32_st_regs[0];
 672                 attr->x87[1] = &ia32_st_regs[0];
 673                 attr->x87[2] = &ia32_st_regs[0];
 674
 675                 sched_add_before(n, fpop);
 676                 DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->x87[0]->name));
 677
 678                 pred = fpop;
 679                 --num;
 680         }
 681         return fpop;
 682 }  /* x87_create_fpop */
 683
 684 /* --------------------------------- liveness ------------------------------------------ */
 685
 686 /**
 687  * The liveness transfer function.
 688  * Updates a live set over a single step from a given node to its predecessor.
 689  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 690  *
 691  * @param sim      The simulator handle.
 692  * @param irn      The node at which liveness should be computed.
 693  * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 694  *                 the registers live after irn.
 695  *
 696  * @return The live bitset.
 697  */
 698 static unsigned vfp_liveness_transfer(x87_simulator *sim, ir_node *irn, unsigned live)
 699 {
 700         int i, n;
 701         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 702         const arch_env_t *arch_env = sim->env;
 703
 704         if (arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 705                         const arch_register_t *reg = x87_get_irn_register(sim, irn);
 706                         live &= ~(1 << arch_register_get_index(reg));
 707         }
 708
 709         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 710                 ir_node *op = get_irn_n(irn, i);
 711
 712                 if (mode_is_float(get_irn_mode(op)) && arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
 713                         const arch_register_t *reg = x87_get_irn_register(sim, op);
 714                         live |= 1 << arch_register_get_index(reg);
 715                 }
 716         }
 717         return live;
 718 }  /* vfp_liveness_transfer */
 719
 720 /**
 721  * Put all live virtual registers at the end of a block into a bitset.
 722  *
 723  * @param sim      the simulator handle
 724  * @param lv       the liveness information
 725  * @param bl       the block
 726  *
 727  * @return The live bitset at the end of this block
 728  */
 729 static unsigned vfp_liveness_end_of_block(x87_simulator *sim, be_lv_t *lv, const ir_node *bl)
 730 {
 731         int i;
 732         unsigned live = 0;
 733         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 734         const arch_env_t *arch_env = sim->env;
 735
 736         be_lv_foreach(lv, bl, be_lv_state_end, i) {
 737                 ir_node *irn = be_lv_get_irn(lv, bl, i);
 738                 if (arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 739                         const arch_register_t *reg = x87_get_irn_register(sim, irn);
 740                         live |= 1 << arch_register_get_index(reg);
 741                 }
 742         }
 743
 744         return live;
 745 }  /* vfp_liveness_end_of_block */
 746
 747 /** get the register mask from an arch_register */
 748 #define REGMASK(reg)    (1 << (arch_register_get_index(reg)))
 749
 750 /**
 751  * Return a bitset of argument registers which are live at the end of a node.
 752  *
 753  * @param sim    the simulator handle
 754  * @param pos    the node
 755  * @param kill   kill mask for the output registers
 756  *
 757  * @return The live bitset.
 758  */
 759 static unsigned vfp_live_args_after(x87_simulator *sim, const ir_node *pos, unsigned kill)
 760 {
 761         unsigned idx = get_irn_idx(pos);
 762
 763         assert(idx < sim->n_idx);
 764         return sim->live[idx] & ~kill;
 765 }  /* vfp_live_args_after */
 766
 767 /**
 768  * Calculate the liveness for a whole block and cache it.
 769  *
 770  * @param sim  the simulator handle
 771  * @param lv   the liveness handle
 772  * @param blk  the block
 773  */
 774 static void update_liveness(x87_simulator *sim, be_lv_t *lv, ir_node *blk) {
 775         unsigned live = vfp_liveness_end_of_block(sim, lv, blk);
 776         unsigned idx;
 777         ir_node *irn;
 778
 779         /* now iterate through the block backward and cache the results */
 780         sched_foreach_reverse(blk, irn) {
 781                 /* stop at the first Phi: this produces the live-in */
 782                 if (is_Phi(irn))
 783                         break;
 784
 785                 idx = get_irn_idx(irn);
 786                 sim->live[idx] = live;
 787
 788                 live = vfp_liveness_transfer(sim, irn, live);
 789         }
 790         idx = get_irn_idx(blk);
 791         sim->live[idx] = live;
 792 }  /* update_liveness */
 793
 794 /**
 795  * Returns true if a register is live in a set.
 796  *
 797  * @param reg_idx  the vfp register index
 798  * @param live     a live bitset
 799  */
 800 #define is_vfp_live(reg_idx, live) ((live) & (1 << (reg_idx)))
 801
 802 #ifdef DEBUG_libfirm
 803 /**
 804  * Dump liveness info.
 805  *
 806  * @param live  the live bitset
 807  */
 808 static void vfp_dump_live(unsigned live) {
 809         int i;
 810
 811         DB((dbg, LEVEL_2, "Live registers here: \n"));
 812         for (i = 0; i < 8; ++i) {
 813                 if (live & (1 << i)) {
 814                         DB((dbg, LEVEL_2, " vf%d", i));
 815                 }
 816         }
 817         DB((dbg, LEVEL_2, "\n"));
 818 }  /* vfp_dump_live */
 819 #endif /* DEBUG_libfirm */
 820
 821 /* --------------------------------- simulators ---------------------------------------- */
 822
 823 #define XCHG(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0)
 824
 825 /**
 826  * Simulate a virtual binop.
 827  *
 828  * @param state  the x87 state
 829  * @param n      the node that should be simulated (and patched)
 830  * @param tmpl   the template containing the 4 possible x87 opcodes
 831  */
 832 static int sim_binop(x87_state *state, ir_node *n, const exchange_tmpl *tmpl) {
 833         int op2_idx, op1_idx = -1;
 834         int out_idx, do_pop =0;
 835         ia32_attr_t *attr;
 836         ir_op *dst;
 837         x87_simulator         *sim = state->sim;
 838         const arch_register_t *op1 = x87_get_irn_register(sim, get_irn_n(n, BINOP_IDX_1));
 839         const arch_register_t *op2 = x87_get_irn_register(sim, get_irn_n(n, BINOP_IDX_2));
 840         const arch_register_t *out = x87_get_irn_register(sim, n);
 841         unsigned live = vfp_live_args_after(sim, n, REGMASK(out));
 842
 843         DB((dbg, LEVEL_1, ">>> %+F %s, %s -> %s\n", n,
 844                 arch_register_get_name(op1), arch_register_get_name(op2),
 845                 arch_register_get_name(out)));
 846         DEBUG_ONLY(vfp_dump_live(live));
 847
 848         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 849         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 850
 851         if (arch_register_get_index(op2) != REG_VFP_NOREG) {
 852                 /* second operand is a vfp register */
 853
 854                 if (is_vfp_live(arch_register_get_index(op2), live)) {
 855                         /* Second operand is live. */
 856
 857                         if (is_vfp_live(arch_register_get_index(op1), live)) {
 858                                 /* Both operands are live: push the first one.
 859                                    This works even for op1 == op2. */
 860                                 x87_create_fpush(state, n, op2_idx, BINOP_IDX_2);
 861                                 out_idx = op2_idx = 0;
 862                                 ++op1_idx;
 863                                 dst = tmpl->normal_op;
 864                                 do_pop = 0;
 865                         }
 866                         else {
 867                                 /* Second live, first operand is dead here, bring it to tos. */
 868                                 if (op1_idx != 0) {
 869                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 870                                         if (op2_idx == 0)
 871                                                 op2_idx = op1_idx;
 872                                 }
 873                                 op1_idx = out_idx = 0;
 874                                 dst = tmpl->normal_op;
 875                                 do_pop = 0;
 876                         }
 877                 }
 878                 else {
 879                         /* Second operand is dead. */
 880                         if (is_vfp_live(arch_register_get_index(op1), live)) {
 881                                 /* First operand is live: bring second to tos. */
 882                                 if (op2_idx != 0) {
 883                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 884                                         if (op1_idx == 0)
 885                                                 op1_idx = op2_idx;
 886                                 }
 887                                 op2_idx = out_idx = 0;
 888                                 dst = tmpl->reverse_op;
 889                                 do_pop = 0;
 890                         }
 891                         else {
 892                                 /* Both operands are dead here, pop them from the stack. */
 893                                 if (op2_idx == 0) {
 894                                         out_idx = op1_idx;
 895                                         if (op1_idx == op2_idx) {
 896                                                 /* Both are identically, no pop needed. */
 897                                                 dst = tmpl->normal_op;
 898                                                 do_pop = 0;
 899                                         }
 900                                         else {
 901                                                 dst = tmpl->normal_pop_op;
 902                                                 do_pop = 1;
 903                                         }
 904                                 }
 905                                 else if (op1_idx == 0) {
 906                                         out_idx = op2_idx;
 907                                         XCHG(op2_idx, op1_idx);
 908                                         if (op1_idx == op2_idx) {
 909                                                 /* Both are identically, no pop needed. */
 910                                                 dst = tmpl->reverse_op;
 911                                                 do_pop = 0;
 912                                         }
 913                                         else {
 914                                                 dst = tmpl->reverse_pop_op;
 915                                                 do_pop = 1;
 916                                         }
 917                                 }
 918                                 else {
 919                                         /* Bring the second on top. */
 920                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 921                                         if (op1_idx == op2_idx) {
 922                                                 /* Both are identically, no pop needed. */
 923                                                 out_idx = op1_idx = op2_idx = 0;
 924                                                 dst = tmpl->normal_op;
 925                                                 do_pop = 0;
 926                                         }
 927                                         else {
 928                                                 op2_idx = 0;
 929                                                 out_idx = op1_idx;
 930                                                 dst = tmpl->normal_pop_op;
 931                                                 do_pop = 1;
 932                                         }
 933                                 }
 934                         }
 935                 }
 936         }
 937         else {
 938                 /* second operand is an address mode */
 939                 if (is_vfp_live(arch_register_get_index(op1), live)) {
 940                         /* first operand is live: push it here */
 941                         x87_create_fpush(state, n, op1_idx, BINOP_IDX_1);
 942                 }
 943                 else {
 944                         /* first operand is dead: bring it to tos */
 945                         if (op1_idx != 0)
 946                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 947                 }
 948                 op1_idx = out_idx = 0;
 949                 dst = tmpl->normal_op;
 950                 do_pop = 0;
 951         }
 952
 953         x87_set_st(state, arch_register_get_index(out), x87_patch_insn(n, dst), out_idx);
 954         if (do_pop)
 955                 x87_pop(state);
 956
 957         /* patch the operation */
 958         attr = get_ia32_attr(n);
 959         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 960         if (op2_idx >= 0)
 961                 attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
 962         attr->x87[2] = out = &ia32_st_regs[out_idx];
 963
 964         if (op2_idx >= 0)
 965                 DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
 966                         arch_register_get_name(op1), arch_register_get_name(op2),
 967                         arch_register_get_name(out)));
 968         else
 969                 DB((dbg, LEVEL_1, "<<< %s %s, [AM] -> %s\n", get_irn_opname(n),
 970                         arch_register_get_name(op1),
 971                         arch_register_get_name(out)));
 972
 973         return 0;
 974 }  /* sim_binop */
 975
 976 /**
 977  * Simulate a virtual Unop.
 978  *
 979  * @param state  the x87 state
 980  * @param n      the node that should be simulated (and patched)
 981  * @param op     the x87 opcode that will replace n's opcode
 982  */
 983 static int sim_unop(x87_state *state, ir_node *n, ir_op *op) {
 984         int op1_idx, out_idx;
 985         x87_simulator         *sim = state->sim;
 986         const arch_register_t *op1 = x87_get_irn_register(sim, get_irn_n(n, UNOP_IDX));
 987         const arch_register_t *out = x87_get_irn_register(sim, n);
 988         ia32_attr_t *attr;
 989         unsigned live = vfp_live_args_after(sim, n, REGMASK(out));
 990
 991         DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name));
 992         DEBUG_ONLY(vfp_dump_live(live));
 993
 994         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 995
 996         if (is_vfp_live(arch_register_get_index(op1), live)) {
 997                 /* push the operand here */
 998                 x87_create_fpush(state, n, op1_idx, UNOP_IDX);
 999         }
1000         else {
1001                 /* operand is dead, bring it to tos */
1002                 if (op1_idx != 0)
1003                         x87_create_fxch(state, n, op1_idx, UNOP_IDX);
1004         }
1005
1006         x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op));
1007         op1_idx = out_idx = 0;
1008         attr = get_ia32_attr(n);
1009         attr->x87[0] = op1 = &ia32_st_regs[0];
1010         attr->x87[2] = out = &ia32_st_regs[0];
1011         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
1012
1013         return 0;
1014 }  /* sim_unop */
1015
1016 /**
1017  * Simulate a virtual Load instruction.
1018  *
1019  * @param state  the x87 state
1020  * @param n      the node that should be simulated (and patched)
1021  * @param op     the x87 opcode that will replace n's opcode
1022  */
1023 static int sim_load(x87_state *state, ir_node *n, ir_op *op) {
1024         const arch_register_t *out = x87_get_irn_register(state->sim, n);
1025         ia32_attr_t *attr;
1026
1027         DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, arch_register_get_name(out)));
1028         x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
1029         assert(out == x87_get_irn_register(state->sim, n));
1030         attr = get_ia32_attr(n);
1031         attr->x87[2] = out = &ia32_st_regs[0];
1032         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
1033
1034         return 0;
1035 }  /* sim_load */
1036
1037 /**
1038  * Rewire all users of @p old_val to @new_val iff they are scheduled after @p store.
1039  *
1040  * @param store   The store
1041  * @param old_val The former value
1042  * @param new_val The new value
1043  */
1044 static void collect_and_rewire_users(ir_node *store, ir_node *old_val, ir_node *new_val) {
1045         const ir_edge_t *edge, *ne;
1046
1047         foreach_out_edge_safe(old_val, edge, ne) {
1048                 ir_node *user = get_edge_src_irn(edge);
1049
1050                 if (! user || user == store)
1051                         continue;
1052
1053                 /* if the user is scheduled after the store: rewire */
1054                 if (sched_is_scheduled(user) && sched_comes_after(store, user)) {
1055                         int i;
1056                         /* find the input of the user pointing to the old value */
1057                         for (i = get_irn_arity(user) - 1; i >= 0; i--) {
1058                                 if (get_irn_n(user, i) == old_val)
1059                                         set_irn_n(user, i, new_val);
1060                         }
1061                 }
1062         }
1063 }  /* collect_and_rewire_users */
1064
1065 /**
1066  * Simulate a virtual Store.
1067  *
1068  * @param state  the x87 state
1069  * @param n      the node that should be simulated (and patched)
1070  * @param op     the x87 store opcode
1071  * @param op_p   the x87 store and pop opcode
1072  */
1073 static int sim_store(x87_state *state, ir_node *n, ir_op *op, ir_op *op_p) {
1074         x87_simulator         *sim = state->sim;
1075         ir_node               *val = get_irn_n(n, STORE_VAL_IDX);
1076         const arch_register_t *op2 = x87_get_irn_register(sim, val);
1077         unsigned              live = vfp_live_args_after(sim, n, 0);
1078         int                   insn = 0;
1079         ia32_attr_t *attr;
1080         int op2_idx, depth;
1081         ir_mode *mode;
1082
1083         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
1084         assert(op2_idx >= 0);
1085
1086         DB((dbg, LEVEL_1, ">>> %+F %s ->\n", n, arch_register_get_name(op2)));
1087
1088         mode  = get_ia32_ls_mode(n);
1089         depth = x87_get_depth(state);
1090
1091         /*
1092                 We can only store the tos to memory.
1093                 A store of mode_E with free registers
1094                 pushes value to tos, so skip it here.
1095         */
1096         if (! (mode == mode_E && depth < N_x87_REGS) && op2_idx != 0)
1097                 x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX);
1098
1099         if (is_vfp_live(arch_register_get_index(op2), live)) {
1100                 /*
1101                         Problem: fst doesn't support mode_E (spills), only fstp does
1102                         Solution:
1103                                 - stack not full: push value and fstp
1104                                 - stack full: fstp value and load again
1105                 */
1106                 if (mode == mode_E) {
1107                         if (depth < N_x87_REGS) {
1108                                 /* ok, we have a free register: push + fstp */
1109                                 x87_create_fpush(state, n, op2_idx, STORE_VAL_IDX);
1110                                 x87_pop(state);
1111                                 x87_patch_insn(n, op_p);
1112                         }
1113                         else {
1114                                 ir_node  *vfld, *mem, *block, *rproj, *mproj;
1115                                 ir_graph *irg;
1116
1117                                 /* stack full here: need fstp + load */
1118                                 x87_pop(state);
1119                                 x87_patch_insn(n, op_p);
1120
1121                                 block = get_nodes_block(n);
1122                                 irg   = get_irn_irg(n);
1123                                 vfld  = new_rd_ia32_vfld(NULL, irg, block, get_irn_n(n, 0), get_irn_n(n, 1), new_rd_NoMem(irg));
1124
1125                                 /* copy all attributes */
1126                                 set_ia32_frame_ent(vfld, get_ia32_frame_ent(n));
1127                                 if (is_ia32_use_frame(n))
1128                                         set_ia32_use_frame(vfld);
1129                                 set_ia32_am_flavour(vfld, get_ia32_am_flavour(n));
1130                                 set_ia32_op_type(vfld, ia32_am_Source);
1131                                 add_ia32_am_offs(vfld, get_ia32_am_offs(n));
1132                                 set_ia32_am_sc(vfld, get_ia32_am_sc(n));
1133                                 set_ia32_ls_mode(vfld, get_ia32_ls_mode(n));
1134
1135                                 rproj = new_r_Proj(irg, block, vfld, get_ia32_ls_mode(vfld), pn_ia32_vfld_res);
1136                                 mproj = new_r_Proj(irg, block, vfld, mode_M, pn_ia32_vfld_M);
1137                                 mem   = get_irn_Proj_for_mode(n, mode_M);
1138
1139                                 assert(mem && "Store memory not found");
1140
1141                                 arch_set_irn_register(sim->env, rproj, op2);
1142
1143                                 /* reroute all former users of the store memory to the load memory */
1144                                 edges_reroute(mem, mproj, irg);
1145                                 /* set the memory input of the load to the store memory */
1146                                 set_irn_n(vfld, 2, mem);
1147
1148                                 sched_add_after(n, vfld);
1149                                 sched_add_after(vfld, rproj);
1150
1151                                 /* rewire all users, scheduled after the store, to the loaded value */
1152                                 collect_and_rewire_users(n, val, rproj);
1153
1154                                 insn = 1;
1155                         }
1156                 }
1157                 else {
1158                         /* mode != mode_E -> use normal fst */
1159                         x87_patch_insn(n, op);
1160                 }
1161         }
1162         else {
1163                 x87_pop(state);
1164                 x87_patch_insn(n, op_p);
1165         }
1166
1167         attr = get_ia32_attr(n);
1168         attr->x87[1] = op2 = &ia32_st_regs[0];
1169         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
1170
1171         return insn;
1172 }  /* sim_store */
1173
1174 /**
1175  * Simulate a virtual Phi.
1176  * Just for cosmetic reasons change the mode of Phi nodes to mode_E.
1177  *
1178  * @param state  the x87 state
1179  * @param n      the node that should be simulated (and patched)
1180  * @param env    the architecture environment
1181  */
1182 static int sim_Phi(x87_state *state, ir_node *n, const arch_env_t *env) {
1183         ir_mode *mode = get_irn_mode(n);
1184
1185         if (mode_is_float(mode))
1186                 set_irn_mode(n, mode_E);
1187
1188         return 0;
1189 }  /* sim_Phi */
1190
1191
1192 #define _GEN_BINOP(op, rev) \
1193 static int sim_##op(x87_state *state, ir_node *n) { \
1194         exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \
1195         return sim_binop(state, n, &tmpl); \
1196 }
1197
1198 #define GEN_BINOP(op)   _GEN_BINOP(op, op)
1199 #define GEN_BINOPR(op)  _GEN_BINOP(op, op##r)
1200
1201 #define GEN_LOAD2(op, nop) \
1202 static int sim_##op(x87_state *state, ir_node *n) { \
1203         return sim_load(state, n, op_ia32_##nop); \
1204 }
1205
1206 #define GEN_LOAD(op)    GEN_LOAD2(op, op)
1207
1208 #define GEN_UNOP(op) \
1209 static int sim_##op(x87_state *state, ir_node *n) { \
1210         return sim_unop(state, n, op_ia32_##op); \
1211 }
1212
1213 #define GEN_STORE(op) \
1214 static int sim_##op(x87_state *state, ir_node *n) { \
1215         return sim_store(state, n, op_ia32_##op, op_ia32_##op##p); \
1216 }
1217
1218 /* all stubs */
1219 GEN_BINOP(fadd)
1220 GEN_BINOPR(fsub)
1221 GEN_BINOP(fmul)
1222 GEN_BINOPR(fdiv)
1223 GEN_BINOP(fprem)
1224
1225 GEN_UNOP(fabs)
1226 GEN_UNOP(fchs)
1227 GEN_UNOP(fsin)
1228 GEN_UNOP(fcos)
1229 GEN_UNOP(fsqrt)
1230
1231 GEN_LOAD(fld)
1232 GEN_LOAD(fild)
1233 GEN_LOAD(fldz)
1234 GEN_LOAD(fld1)
1235 GEN_LOAD2(fConst, fldConst)
1236
1237 GEN_STORE(fst)
1238 GEN_STORE(fist)
1239
1240 /**
1241  * Simulate a fCondJmp.
1242  *
1243  * @param state  the x87 state
1244  * @param n      the node that should be simulated (and patched)
1245  */
1246 static int sim_fCondJmp(x87_state *state, ir_node *n) {
1247         int op2_idx, op1_idx = -1, pop_cnt = 0;
1248         ia32_attr_t *attr;
1249         ir_op *dst;
1250         x87_simulator         *sim = state->sim;
1251         const arch_register_t *op1 = x87_get_irn_register(sim, get_irn_n(n, BINOP_IDX_1));
1252         const arch_register_t *op2 = x87_get_irn_register(sim, get_irn_n(n, BINOP_IDX_2));
1253         unsigned live = vfp_live_args_after(sim, n, 0);
1254
1255         DB((dbg, LEVEL_1, ">>> %+F %s, %s\n", n,
1256                 arch_register_get_name(op1), arch_register_get_name(op2)));
1257         DEBUG_ONLY(vfp_dump_live(live));
1258
1259         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1260         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
1261
1262         /* BEWARE: check for comp a,a cases, they might happen */
1263         if (arch_register_get_index(op2) != REG_VFP_NOREG) {
1264                 /* second operand is a vfp register */
1265
1266                 if (is_vfp_live(arch_register_get_index(op2), live)) {
1267                         /* second operand is live */
1268
1269                         if (is_vfp_live(arch_register_get_index(op1), live)) {
1270                                 /* both operands are live: move one of them to tos */
1271                                 if (op2_idx == 0) {
1272                                         XCHG(op2_idx, op1_idx);
1273                                         dst = op_ia32_fcomrJmp;
1274                                 }
1275                                 else if (op1_idx == 0) {
1276                                         dst = op_ia32_fcomJmp;
1277                                 }
1278                                 else {
1279                                         /* bring the first on top */
1280                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1281                                         if (op1_idx == op2_idx)
1282                                                 op2_idx = 0;
1283                                         op1_idx = 0;
1284                                         dst     = op_ia32_fcomJmp;
1285                                 }
1286                         }
1287                         else {
1288                                 /* second live, first operand is dead here, bring it to tos.
1289                                    This means further, op1_idx != op2_idx. */
1290                                 if (op1_idx != 0) {
1291                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1292                                         if (op2_idx == 0)
1293                                                 op2_idx = op1_idx;
1294                                 }
1295                                 op1_idx = 0;
1296                                 dst     = op_ia32_fcompJmp;
1297                                 pop_cnt = 1;
1298                         }
1299                 }
1300                 else {
1301                         /* second operand is dead */
1302                         if (is_vfp_live(arch_register_get_index(op1), live)) {
1303                                 /* first operand is live: bring second to tos.
1304                                    This means further, op1_idx != op2_idx. */
1305                                 if (op2_idx != 0) {
1306                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1307                                         if (op1_idx == 0)
1308                                                 op1_idx = op2_idx;
1309                                 }
1310                                 op2_idx = 0;
1311                                 dst     = op_ia32_fcomrpJmp;
1312                                 pop_cnt = 1;
1313                         }
1314                         else {
1315                                 /* both operands are dead here, check first for identity. */
1316                                 if (op1_idx == op2_idx) {
1317                                         /* identically, one one needed */
1318                                         if (op1_idx != 0) {
1319                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1320                                                 op1_idx = op2_idx = 0;
1321                                         }
1322                                         dst     = op_ia32_fcompJmp;
1323                                         pop_cnt = 1;
1324                                 }
1325                                 /* different, move them to st and st(1) and pop both.
1326                                    The tricky part is to get one into st(1).*/
1327                                 else if (op2_idx == 1) {
1328                                         /* good, second operand is already in the right place, move the first */
1329                                         if (op1_idx != 0) {
1330                                                 /* bring the first on top */
1331                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1332                                                 op1_idx = 0;
1333                                         }
1334                                         dst     = op_ia32_fcomppJmp;
1335                                         pop_cnt = 2;
1336                                 }
1337                                 else if (op1_idx == 1) {
1338                                         /* good, first operand is already in the right place, move the second */
1339                                         if (op2_idx != 0) {
1340                                                 /* bring the first on top */
1341                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1342                                                 op2_idx = 0;
1343                                         }
1344                                         dst     = op_ia32_fcomrppJmp;
1345                                         pop_cnt = 2;
1346                                 }
1347                                 else {
1348                                         /* if one is already the TOS, we need two fxch */
1349                                         if (op1_idx == 0) {
1350                                                 /* first one is TOS, move to st(1) */
1351                                                 x87_create_fxch(state, n, 1, BINOP_IDX_1);
1352                                                 op1_idx = 1;
1353                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1354                                                 op2_idx = 0;
1355                                                 dst     = op_ia32_fcomrppJmp;
1356                                                 pop_cnt = 2;
1357                                         }
1358                                         else if (op2_idx == 0) {
1359                                                 /* second one is TOS, move to st(1) */
1360                                                 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1361                                                 op2_idx = 1;
1362                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1363                                                 op1_idx = 0;
1364                                                 dst     = op_ia32_fcomrppJmp;
1365                                                 pop_cnt = 2;
1366                                         }
1367                                         else {
1368                                                 /* none of them is either TOS or st(1), 3 fxch needed */
1369                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1370                                                 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1371                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1372                                                 op1_idx = 0;
1373                                                 op2_idx = 1;
1374                                                 dst     = op_ia32_fcomppJmp;
1375                                                 pop_cnt = 2;
1376                                         }
1377                                 }
1378                         }
1379                 }
1380         }
1381         else {
1382                 /* second operand is an address mode */
1383                 if (is_vfp_live(arch_register_get_index(op1), live)) {
1384                         /* first operand is live: bring it to TOS */
1385                         if (op1_idx != 0) {
1386                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1387                                 op1_idx = 0;
1388                         }
1389                         dst = op_ia32_fcomJmp;
1390                 }
1391                 else {
1392                         /* first operand is dead: bring it to tos */
1393                         if (op1_idx != 0) {
1394                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1395                                 op1_idx = 0;
1396                         }
1397                 }
1398                 dst     = op_ia32_fcompJmp;
1399                 pop_cnt = 1;
1400         }
1401
1402         x87_patch_insn(n, dst);
1403         if (pop_cnt > 1)
1404                 x87_pop(state);
1405         if (pop_cnt > 0)
1406                 x87_pop(state);
1407
1408         /* patch the operation */
1409         attr = get_ia32_attr(n);
1410         attr->x87[1] = op1 = &ia32_st_regs[op1_idx];
1411         if (op2_idx >= 0)
1412                 attr->x87[2] = op2 = &ia32_st_regs[op2_idx];
1413
1414         if (op2_idx >= 0)
1415                 DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(n),
1416                         arch_register_get_name(op1), arch_register_get_name(op2)));
1417         else
1418                 DB((dbg, LEVEL_1, "<<< %s %s, [AM]\n", get_irn_opname(n),
1419                         arch_register_get_name(op1)));
1420
1421         return 0;
1422 }  /* sim_fCondJmp */
1423
1424 /**
1425  * Simulate a be_Copy.
1426  *
1427  * @param state  the x87 state
1428  * @param n      the node that should be simulated (and patched)
1429  */
1430 static int sim_Copy(x87_state *state, ir_node *n) {
1431         ir_mode *mode = get_irn_mode(n);
1432
1433         if (mode_is_float(mode)) {
1434                 x87_simulator         *sim = state->sim;
1435                 ir_node               *pred = get_irn_n(n, 0);
1436                 const arch_register_t *out = x87_get_irn_register(sim, n);
1437                 const arch_register_t *op1 = x87_get_irn_register(sim, pred);
1438                 ir_node               *node, *next;
1439                 ia32_attr_t           *attr;
1440                 int                   op1_idx, out_idx;
1441                 unsigned              live = vfp_live_args_after(sim, n, REGMASK(out));
1442                 ir_node               *(*cnstr)(dbg_info *, ir_graph *, ir_node *, ir_mode *);
1443
1444                 DB((dbg, LEVEL_1, ">>> %+F %s -> %s\n", n,
1445                         arch_register_get_name(op1), arch_register_get_name(out)));
1446                 DEBUG_ONLY(vfp_dump_live(live));
1447
1448                 /* Do not copy constants, recreate them. */
1449                 switch (get_ia32_irn_opcode(pred)) {
1450                 case iro_ia32_fldz:
1451                         cnstr = new_rd_ia32_fldz;
1452                         break;
1453                 case iro_ia32_fld1:
1454                         cnstr = new_rd_ia32_fld1;
1455                         break;
1456                 case iro_ia32_fldpi:
1457                         cnstr = new_rd_ia32_fldpi;
1458                         break;
1459                 case iro_ia32_fldl2e:
1460                         cnstr = new_rd_ia32_fldl2e;
1461                         break;
1462                 case iro_ia32_fldl2t:
1463                         cnstr = new_rd_ia32_fldl2t;
1464                         break;
1465                 case iro_ia32_fldlg2:
1466                         cnstr = new_rd_ia32_fldlg2;
1467                         break;
1468                 case iro_ia32_fldln2:
1469                         cnstr = new_rd_ia32_fldln2;
1470                         break;
1471                 default:
1472                         goto no_constant;
1473                 }
1474
1475                 /* copy a constant */
1476                 node = (*cnstr)(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), mode);
1477                 arch_set_irn_register(sim->env, node, out);
1478
1479                 x87_push(state, arch_register_get_index(out), node);
1480
1481                 attr = get_ia32_attr(node);
1482                 attr->x87[2] = out = &ia32_st_regs[0];
1483
1484                 next = sched_next(n);
1485                 sched_remove(n);
1486                 exchange(n, node);
1487                 sched_add_before(next, node);
1488                 DB((dbg, LEVEL_1, ">>> %+F -> %s\n", node, arch_register_get_name(out)));
1489                 return 0;
1490
1491 no_constant:
1492                 /* handle the infamous unknown value */
1493                 if (arch_register_get_index(op1) == REG_VFP_UKNWN) {
1494                         /* This happens before Phi nodes */
1495                         if (x87_state_is_empty(state)) {
1496                                 /* create some value */
1497                                 x87_patch_insn(n, op_ia32_fldz);
1498                                 attr = get_ia32_attr(n);
1499                                 attr->x87[2] = out = &ia32_st_regs[0];
1500                                 DB((dbg, LEVEL_1, "<<< %+F -> %s\n", n,
1501                                         arch_register_get_name(out)));
1502                         } else {
1503                                 /* Just copy one. We need here an fpush that can hold a
1504                                    a register, so use the fpushCopy. */
1505                                 node = new_rd_ia32_fpushCopy(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
1506                                 arch_set_irn_register(sim->env, node, out);
1507
1508                                 x87_push(state, arch_register_get_index(out), node);
1509
1510                                 attr = get_ia32_attr(node);
1511                                 attr->x87[0] = op1 =
1512                                 attr->x87[2] = out = &ia32_st_regs[0];
1513
1514                                 next = sched_next(n);
1515                                 sched_remove(n);
1516                                 exchange(n, node);
1517                                 sched_add_before(next, node);
1518                                 DB((dbg, LEVEL_1, "<<< %+F %s -> %s\n", node,
1519                                         arch_register_get_name(op1),
1520                                         arch_register_get_name(out)));
1521                         }
1522                         return 0;
1523                 }
1524
1525                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1526
1527                 if (is_vfp_live(arch_register_get_index(op1), live)) {
1528                         /* Operand is still live,a real copy. We need here an fpush that can hold a
1529                            a register, so use the fpushCopy. */
1530                         node = new_rd_ia32_fpushCopy(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
1531                         arch_set_irn_register(sim->env, node, out);
1532
1533                         x87_push(state, arch_register_get_index(out), node);
1534
1535                         attr = get_ia32_attr(node);
1536                         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
1537                         attr->x87[2] = out = &ia32_st_regs[0];
1538
1539                         next = sched_next(n);
1540                         sched_remove(n);
1541                         exchange(n, node);
1542                         sched_add_before(next, node);
1543                         DB((dbg, LEVEL_1, ">>> %+F %s -> %s\n", node, op1->name, out->name));
1544                 }
1545                 else {
1546                         out_idx = x87_on_stack(state, arch_register_get_index(out));
1547
1548                         if (out_idx >= 0 && out_idx != op1_idx) {
1549                                 /* op1 must be killed and placed where out is */
1550                                 if (out_idx == 0) {
1551                                         /* best case, simple remove and rename */
1552                                         x87_patch_insn(n, op_ia32_Pop);
1553                                         attr = get_ia32_attr(n);
1554                                         attr->x87[0] = op1 = &ia32_st_regs[0];
1555
1556                                         x87_pop(state);
1557                                         x87_set_st(state, arch_register_get_index(out), n, op1_idx - 1);
1558                                 }
1559                                 else {
1560                                         /* move op1 to tos, store and pop it */
1561                                         if (op1_idx != 0) {
1562                                                 x87_create_fxch(state, n, op1_idx, 0);
1563                                                 op1_idx = 0;
1564                                         }
1565                                         x87_patch_insn(n, op_ia32_Pop);
1566                                         attr = get_ia32_attr(n);
1567                                         attr->x87[0] = op1 = &ia32_st_regs[out_idx];
1568
1569                                         x87_pop(state);
1570                                         x87_set_st(state, arch_register_get_index(out), n, out_idx - 1);
1571                                 }
1572                                 DB((dbg, LEVEL_1, ">>> %+F %s\n", n, op1->name));
1573                         }
1574                         else {
1575                                 /* just a virtual copy */
1576                                 x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx);
1577                                 sched_remove(n);
1578                                 DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n)));
1579                                 exchange(n, get_unop_op(n));
1580                         }
1581                 }
1582         }
1583         return 0;
1584 }  /* sim_Copy */
1585
1586 /**
1587  * Simulate a be_Call.
1588  *
1589  * @param state  the x87 state
1590  * @param n      the node that should be simulated
1591  * @param env    the architecture environment
1592  */
1593 static int sim_Call(x87_state *state, ir_node *n, const arch_env_t *env) {
1594         ir_type *call_tp = be_Call_get_type(n);
1595
1596         /* at the begin of a call the x87 state should be empty */
1597         assert(state->depth == 0 && "stack not empty before call");
1598
1599         /*
1600          * If the called function returns a float, it is returned in st(0).
1601          * This even happens if the return value is NOT used.
1602          * Moreover, only one return result is supported.
1603          */
1604         if (get_method_n_ress(call_tp) > 0) {
1605                 ir_type *res_type = get_method_res_type(call_tp, 0);
1606                 ir_mode *mode     = get_type_mode(res_type);
1607
1608                 if (mode && mode_is_float(mode)) {
1609                         /*
1610                          * TODO: what to push here? The result might be unused and currently
1611                          * we have no possibility to detect this :-(
1612                          */
1613                         x87_push(state, 0, n);
1614                 }
1615         }
1616
1617         return 0;
1618 }  /* sim_Call */
1619
1620 /**
1621  * Simulate a be_Spill.
1622  *
1623  * @param state  the x87 state
1624  * @param n      the node that should be simulated (and patched)
1625  * @param env    the architecture environment
1626  *
1627  * Should not happen, spills are lowered before x87 simulator see them.
1628  */
1629 static int sim_Spill(x87_state *state, ir_node *n) {
1630         assert(0 && "Spill not lowered");
1631         return sim_fst(state, n);
1632 }  /* sim_Spill */
1633
1634 /**
1635  * Simulate a be_Reload.
1636  *
1637  * @param state  the x87 state
1638  * @param n      the node that should be simulated (and patched)
1639  * @param env    the architecture environment
1640  *
1641  * Should not happen, reloads are lowered before x87 simulator see them.
1642  */
1643 static int sim_Reload(x87_state *state, ir_node *n) {
1644         assert(0 && "Reload not lowered");
1645         return sim_fld(state, n);
1646 }  /* sim_Reload */
1647
1648 /**
1649  * Simulate a be_Return.
1650  *
1651  * @param state  the x87 state
1652  * @param n      the node that should be simulated (and patched)
1653  * @param env    the architecture environment
1654  */
1655 static int sim_Return(x87_state *state, ir_node *n) {
1656         int n_res = be_Return_get_n_rets(n);
1657         int i, n_float_res = 0;
1658
1659         /* only floating point return values must resist on stack */
1660         for (i = 0; i < n_res; ++i) {
1661                 ir_node *res = get_irn_n(n, be_pos_Return_val + i);
1662
1663                 if (mode_is_float(get_irn_mode(res)))
1664                         ++n_float_res;
1665         }
1666         assert(x87_get_depth(state) == n_float_res);
1667
1668         /* pop them virtually */
1669         for (i = n_float_res - 1; i >= 0; --i)
1670                 x87_pop(state);
1671
1672         return 0;
1673 }  /* sim_Return */
1674
1675 typedef struct _perm_data_t {
1676         const arch_register_t *in;
1677         const arch_register_t *out;
1678 } perm_data_t;
1679
1680 /**
1681  * Simulate a be_Perm.
1682  *
1683  * @param state  the x87 state
1684  * @param irn    the node that should be simulated (and patched)
1685  */
1686 static int sim_Perm(x87_state *state, ir_node *irn) {
1687         int             i, n;
1688         x87_simulator   *sim = state->sim;
1689         ir_node         *pred = get_irn_n(irn, 0);
1690         int             *stack_pos;
1691         const ir_edge_t *edge;
1692
1693         /* handle only floating point Perms */
1694         if (! mode_is_float(get_irn_mode(pred)))
1695                 return 0;
1696
1697         DB((dbg, LEVEL_1, ">>> %+F\n", irn));
1698
1699         /* Perm is a pure virtual instruction on x87.
1700            All inputs must be on the FPU stack and are pairwise
1701            different from each other.
1702            So, all we need to do is to permutate the stack state. */
1703         n = get_irn_arity(irn);
1704         NEW_ARR_A(int, stack_pos, n);
1705
1706         /* collect old stack positions */
1707         for (i = 0; i < n; ++i) {
1708                 const arch_register_t *inreg = x87_get_irn_register(sim, get_irn_n(irn, i));
1709                 int idx = x87_on_stack(state, arch_register_get_index(inreg));
1710
1711                 assert(idx >= 0 && "Perm argument not on x87 stack");
1712
1713                 stack_pos[i] = idx;
1714         }
1715         /* now do the permutation */
1716         foreach_out_edge(irn, edge) {
1717                 ir_node               *proj = get_edge_src_irn(edge);
1718                 const arch_register_t *out  = x87_get_irn_register(sim, proj);
1719                 long                  num   = get_Proj_proj(proj);
1720
1721                 assert(0 <= num && num < n && "More Proj's than Perm inputs");
1722                 x87_set_st(state, arch_register_get_index(out), proj, stack_pos[(unsigned)num]);
1723         }
1724         DB((dbg, LEVEL_1, "<<< %+F\n", irn));
1725
1726         return 0;
1727 }  /* be_Perm */
1728
1729 /**
1730  * Kill any dead registers at block start by popping them from the stack.
1731  *
1732  * @param sim          the simulator handle
1733  * @param block        the current block
1734  * @param start_state  the x87 state at the begin of the block
1735  */
1736 static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state *start_state) {
1737         x87_state *state = start_state;
1738         ir_node *first_insn = sched_first(block);
1739         ir_node *keep = NULL;
1740         unsigned live = vfp_live_args_after(sim, block, 0);
1741         unsigned kill_mask;
1742         int i, depth, num_pop;
1743
1744         kill_mask = 0;
1745         depth = x87_get_depth(state);
1746         for (i = depth - 1; i >= 0; --i) {
1747                 int reg = x87_get_st_reg(state, i);
1748
1749                 if (! is_vfp_live(reg, live))
1750                         kill_mask |= (1 << i);
1751         }
1752
1753         if (kill_mask) {
1754                 /* create a new state, will be changed */
1755                 state = x87_clone_state(sim, state);
1756
1757                 DB((dbg, LEVEL_1, "Killing deads:\n"));
1758                 DEBUG_ONLY(vfp_dump_live(live));
1759                 DEBUG_ONLY(x87_dump_stack(state));
1760
1761                 /* now kill registers */
1762                 while (kill_mask) {
1763                         /* we can only kill from TOS, so bring them up */
1764                         if (! (kill_mask & 1)) {
1765                                 /* search from behind, because we can to a double-pop */
1766                                 for (i = depth - 1; i >= 0; --i) {
1767                                         if (kill_mask & (1 << i)) {
1768                                                 kill_mask &= ~(1 << i);
1769                                                 kill_mask |= 1;
1770                                                 break;
1771                                         }
1772                                 }
1773
1774                                 if (keep)
1775                                         x87_set_st(state, -1, keep, i);
1776                                 keep = x87_create_fxch(state, first_insn, i, -1);
1777                         }
1778                         else if (! keep)
1779                                 keep = x87_get_st_node(state, 0);
1780
1781                         if ((kill_mask & 3) == 3) {
1782                                 /* we can do a double-pop */
1783                                 num_pop = 2;
1784                         }
1785                         else {
1786                                 /* only a single pop */
1787                                 num_pop = 1;
1788                         }
1789
1790                         depth -= num_pop;
1791                         kill_mask >>= num_pop;
1792                         keep = x87_create_fpop(state, first_insn, num_pop, keep);
1793                 }
1794                 keep_alive(keep);
1795         }
1796         return state;
1797 }  /* x87_kill_deads */
1798
1799 /**
1800  * Run a simulation and fix all virtual instructions for a block.
1801  *
1802  * @param sim          the simulator handle
1803  * @param block        the current block
1804  *
1805  * @return non-zero if simulation is complete,
1806  *         zero if the simulation must be rerun
1807  */
1808 static int x87_simulate_block(x87_simulator *sim, ir_node *block) {
1809         ir_node *n, *next;
1810         blk_state *bl_state = x87_get_bl_state(sim, block);
1811         x87_state *state = bl_state->begin;
1812         const ir_edge_t *edge;
1813         ir_node *start_block;
1814
1815         /* if we have no assigned start state, we must wait ... */
1816         if (! state)
1817                 return 0;
1818
1819         assert(bl_state->end == NULL);
1820
1821         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
1822         DB((dbg, LEVEL_2, "State at Block begin:\n ")); DEBUG_ONLY(x87_dump_stack(state));
1823
1824         /* at block begin, kill all dead registers */
1825         state = x87_kill_deads(sim, block, state);
1826
1827         /* beware, n might changed */
1828         for (n = sched_first(block); !sched_is_end(n); n = next) {
1829                 ir_op *op = get_irn_op(n);
1830
1831                 next = sched_next(n);
1832                 if (op->ops.generic) {
1833                         int node_inserted;
1834                         sim_func func = (sim_func)op->ops.generic;
1835
1836                         /* have work to do */
1837                         if (state == bl_state->begin) {
1838                                 /* create a new state, will be changed */
1839                                 state = x87_clone_state(sim, state);
1840                         }
1841
1842                         /* simulate it */
1843                         node_inserted = (*func)(state, n);
1844
1845                         /*
1846                                 sim_func might have added additional nodes after n,
1847                                 so update next node
1848                                 beware: n must not be changed by sim_func
1849                                 (i.e. removed from schedule) in this case
1850                         */
1851                         if (node_inserted)
1852                                 next = sched_next(n);
1853                 }
1854         }
1855
1856         start_block = get_irg_start_block(get_irn_irg(block));
1857
1858         /* check if the state must be shuffled */
1859         foreach_block_succ(block, edge) {
1860                 ir_node *succ = get_edge_src_irn(edge);
1861                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1862
1863                 if (succ_state->begin && succ != start_block) {
1864                         /* There is already a begin state for this block, bad.
1865                            Do the necessary permutations.
1866                            Note that critical edges are removed, so this is always possible. */
1867                         x87_shuffle(sim, block, state, succ, succ_state->begin);
1868
1869                         /* Note further, that there can be only one such situation,
1870                            so we can break here. */
1871                         break;
1872                 }
1873         }
1874         bl_state->end = state;
1875
1876         /* now propagate the state to all successor blocks */
1877         foreach_block_succ(block, edge) {
1878                 ir_node *succ = get_edge_src_irn(edge);
1879                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1880
1881                 if (! succ_state->begin)
1882                         succ_state->begin = state;
1883         }
1884
1885         DB((dbg, LEVEL_2, "State at Block end:\n ")); DEBUG_ONLY(x87_dump_stack(state));
1886
1887         return 1;
1888 }  /* x87_simulate_block */
1889
1890 /**
1891  * Create a new x87 simulator.
1892  *
1893  * @param sim   a simulator handle, will be initialized
1894  * @param irg   the current graph
1895  * @param env   the architecture environment
1896  */
1897 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env_t *env)
1898 {
1899         obstack_init(&sim->obst);
1900         sim->blk_states = pmap_create();
1901         sim->env        = env;
1902         sim->n_idx      = get_irg_last_idx(irg);
1903         sim->live       = obstack_alloc(&sim->obst, sizeof(*sim->live) * sim->n_idx);
1904
1905         FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
1906
1907         DB((dbg, LEVEL_1, "--------------------------------\n"
1908                 "x87 Simulator started for %+F\n", irg));
1909
1910         /* set the generic function pointer of instruction we must simulate */
1911         clear_irp_opcodes_generic_func();
1912
1913 #define ASSOC(op)       (op_ ## op)->ops.generic = (op_func)(sim_##op)
1914 #define ASSOC_IA32(op)  (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
1915 #define ASSOC_BE(op)    (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
1916         ASSOC_IA32(fConst);
1917         ASSOC_IA32(fld);
1918         ASSOC_IA32(fild);
1919         ASSOC_IA32(fld1);
1920         ASSOC_IA32(fldz);
1921         ASSOC_IA32(fadd);
1922         ASSOC_IA32(fsub);
1923         ASSOC_IA32(fmul);
1924         ASSOC_IA32(fdiv);
1925         ASSOC_IA32(fprem);
1926         ASSOC_IA32(fabs);
1927         ASSOC_IA32(fchs);
1928         ASSOC_IA32(fsin);
1929         ASSOC_IA32(fcos);
1930         ASSOC_IA32(fsqrt);
1931         ASSOC_IA32(fist);
1932         ASSOC_IA32(fst);
1933         ASSOC_IA32(fCondJmp);
1934         ASSOC_BE(Copy);
1935         ASSOC_BE(Call);
1936         ASSOC_BE(Spill);
1937         ASSOC_BE(Reload);
1938         ASSOC_BE(Return);
1939         ASSOC_BE(Perm);
1940         ASSOC(Phi);
1941 #undef ASSOC_BE
1942 #undef ASSOC_IA32
1943 #undef ASSOC
1944 }  /* x87_init_simulator */
1945
1946 /**
1947  * Destroy a x87 simulator.
1948  *
1949  * @param sim  the simulator handle
1950  */
1951 static void x87_destroy_simulator(x87_simulator *sim) {
1952         pmap_destroy(sim->blk_states);
1953         obstack_free(&sim->obst, NULL);
1954         DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
1955 }  /* x87_destroy_simulator */
1956
1957 /**
1958  * Run a simulation and fix all virtual instructions for a graph.
1959  *
1960  * @param env       the architecture environment
1961  * @param irg       the current graph
1962  * @param blk_list  the block schedule list
1963  *
1964  * Needs a block-schedule.
1965  */
1966 void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) {
1967         ir_node       *block, *start_block;
1968         waitq         *worklist;
1969         blk_state     *bl_state;
1970         x87_simulator sim;
1971         int           i, n;
1972         be_lv_t       *lv;
1973         ir_graph      *rem = current_ir_graph;
1974
1975         current_ir_graph = irg;
1976
1977         /* create the simulator */
1978         x87_init_simulator(&sim, irg, env);
1979
1980         start_block = get_irg_start_block(irg);
1981         bl_state = x87_get_bl_state(&sim, start_block);
1982
1983         /* start with the empty state */
1984         bl_state->begin = empty;
1985         empty->sim      = &sim;
1986
1987         worklist = new_waitq();
1988
1989         /* Create the worklist for the schedule and calculate the liveness
1990            for all nodes. We must precalculate this info, because the
1991            simulator adds new nodes (and possible before Phi nodes) which
1992            let fail the old lazy calculation.
1993            On the other hand we reduce the computation amount due to
1994            precaching from O(n^2) to O(n) at the expense of O(n) cache memory.
1995          */
1996         lv = be_liveness(irg);
1997         for (i = 0, n = ARR_LEN(blk_list); i < n; ++i) {
1998                 update_liveness(&sim, lv, blk_list[i]);
1999                 waitq_put(worklist, blk_list[i]);
2000         }
2001         be_liveness_free(lv);
2002
2003         /* iterate */
2004         do {
2005                 block = waitq_get(worklist);
2006                 if (! x87_simulate_block(&sim, block)) {
2007                         waitq_put(worklist, block);
2008                         continue;
2009                 }
2010         } while (! pdeq_empty(worklist));
2011
2012         /* kill it */
2013         del_waitq(worklist);
2014         x87_destroy_simulator(&sim);
2015         current_ir_graph = rem;
2016 }  /* x87_simulate_graph */