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