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