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

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