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