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 << arch_register_get_index(reg));
 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 << arch_register_get_index(reg));
 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 << arch_register_get_index(reg);
 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 << arch_register_get_index(reg);
 650         }
 651
 652         return live;
 653 }
 654
 655 /** get the register mask from an arch_register */
 656 #define REGMASK(reg)    (1 << (arch_register_get_index(reg)))
 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                = arch_register_get_index(op1_reg);
 753         int reg_index_2                = arch_register_get_index(op2_reg);
 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,
 759                 arch_register_get_name(op1_reg), arch_register_get_name(op2_reg),
 760                 arch_register_get_name(out)));
 761         DEBUG_ONLY(vfp_dump_live(live);)
 762         DB((dbg, LEVEL_1, "Stack before: "));
 763         DEBUG_ONLY(x87_dump_stack(state);)
 764
 765         op1_idx = x87_on_stack(state, reg_index_1);
 766         assert(op1_idx >= 0);
 767         op1_live_after = is_vfp_live(reg_index_1, live);
 768
 769         attr     = get_ia32_x87_attr(n);
 770         permuted = attr->attr.data.ins_permuted;
 771
 772         int const out_reg_idx = arch_register_get_index(out);
 773         if (reg_index_2 != REG_VFP_VFP_NOREG) {
 774                 assert(!permuted);
 775
 776                 /* second operand is a vfp register */
 777                 op2_idx = x87_on_stack(state, reg_index_2);
 778                 assert(op2_idx >= 0);
 779                 op2_live_after = is_vfp_live(reg_index_2, live);
 780
 781                 if (op2_live_after) {
 782                         /* Second operand is live. */
 783
 784                         if (op1_live_after) {
 785                                 /* Both operands are live: push the first one.
 786                                    This works even for op1 == op2. */
 787                                 x87_create_fpush(state, n, op1_idx, out_reg_idx, op2);
 788                                 /* now do fxxx (tos=tos X op) */
 789                                 op1_idx = 0;
 790                                 op2_idx += 1;
 791                                 out_idx = 0;
 792                         } else {
 793                                 /* Second live, first operand is dead here, bring it to tos. */
 794                                 if (op1_idx != 0) {
 795                                         x87_create_fxch(state, n, op1_idx);
 796                                         if (op2_idx == 0)
 797                                                 op2_idx = op1_idx;
 798                                         op1_idx = 0;
 799                                 }
 800                                 /* now do fxxx (tos=tos X op) */
 801                                 out_idx = 0;
 802                         }
 803                 } else {
 804                         /* Second operand is dead. */
 805                         if (op1_live_after) {
 806                                 /* First operand is live: bring second to tos. */
 807                                 if (op2_idx != 0) {
 808                                         x87_create_fxch(state, n, op2_idx);
 809                                         if (op1_idx == 0)
 810                                                 op1_idx = op2_idx;
 811                                         op2_idx = 0;
 812                                 }
 813                                 /* now do fxxxr (tos = op X tos) */
 814                                 out_idx = 0;
 815                         } else {
 816                                 /* Both operands are dead here, pop them from the stack. */
 817                                 if (op2_idx == 0) {
 818                                         if (op1_idx == 0) {
 819                                                 /* Both are identically and on tos, no pop needed. */
 820                                                 /* here fxxx (tos = tos X tos) */
 821                                                 out_idx = 0;
 822                                         } else {
 823                                                 /* now do fxxxp (op = op X tos, pop) */
 824                                                 do_pop = 1;
 825                                                 out_idx = op1_idx;
 826                                         }
 827                                 } else if (op1_idx == 0) {
 828                                         assert(op1_idx != op2_idx);
 829                                         /* now do fxxxrp (op = tos X op, pop) */
 830                                         do_pop = 1;
 831                                         out_idx = op2_idx;
 832                                 } else {
 833                                         /* Bring the second on top. */
 834                                         x87_create_fxch(state, n, op2_idx);
 835                                         if (op1_idx == op2_idx) {
 836                                                 /* Both are identically and on tos now, no pop needed. */
 837                                                 op1_idx = 0;
 838                                                 op2_idx = 0;
 839                                                 /* use fxxx (tos = tos X tos) */
 840                                                 out_idx = 0;
 841                                         } else {
 842                                                 /* op2 is on tos now */
 843                                                 op2_idx = 0;
 844                                                 /* use fxxxp (op = op X tos, pop) */
 845                                                 out_idx = op1_idx;
 846                                                 do_pop = 1;
 847                                         }
 848                                 }
 849                         }
 850                 }
 851         } else {
 852                 /* second operand is an address mode */
 853                 if (op1_live_after) {
 854                         /* first operand is live: push it here */
 855                         x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
 856                         op1_idx = 0;
 857                 } else {
 858                         /* first operand is dead: bring it to tos */
 859                         if (op1_idx != 0) {
 860                                 x87_create_fxch(state, n, op1_idx);
 861                                 op1_idx = 0;
 862                         }
 863                 }
 864
 865                 /* use fxxx (tos = tos X mem) */
 866                 out_idx = 0;
 867         }
 868
 869         patched_insn = x87_patch_insn(n, op);
 870         x87_set_st(state, out_reg_idx, patched_insn, out_idx);
 871         if (do_pop) {
 872                 x87_pop(state);
 873         }
 874
 875         /* patch the operation */
 876         attr->pop    = do_pop;
 877         attr->x87[0] = op1_reg = get_st_reg(op1_idx);
 878         if (reg_index_2 != REG_VFP_VFP_NOREG) {
 879                 attr->x87[1] = op2_reg = get_st_reg(op2_idx);
 880         }
 881         attr->x87[2] = out = get_st_reg(out_idx);
 882
 883         if (reg_index_2 != REG_VFP_VFP_NOREG) {
 884                 DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
 885                         arch_register_get_name(op1_reg), arch_register_get_name(op2_reg),
 886                         arch_register_get_name(out)));
 887         } else {
 888                 DB((dbg, LEVEL_1, "<<< %s %s, [AM] -> %s\n", get_irn_opname(n),
 889                         arch_register_get_name(op1_reg),
 890                         arch_register_get_name(out)));
 891         }
 892
 893         return NO_NODE_ADDED;
 894 }
 895
 896 /**
 897  * Simulate a virtual Unop.
 898  *
 899  * @param state  the x87 state
 900  * @param n      the node that should be simulated (and patched)
 901  * @param op     the x87 opcode that will replace n's opcode
 902  *
 903  * @return NO_NODE_ADDED
 904  */
 905 static int sim_unop(x87_state *state, ir_node *n, ir_op *op)
 906 {
 907         arch_register_t const *const out  = x87_get_irn_register(n);
 908         unsigned               const live = vfp_live_args_after(state->sim, n, REGMASK(out));
 909         DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name));
 910         DEBUG_ONLY(vfp_dump_live(live);)
 911
 912         ir_node               *const op1         = get_irn_n(n, 0);
 913         arch_register_t const *const op1_reg     = x87_get_irn_register(op1);
 914         int                    const op1_reg_idx = arch_register_get_index(op1_reg);
 915         int                    const op1_idx     = x87_on_stack(state, op1_reg_idx);
 916         int                    const out_reg_idx = arch_register_get_index(out);
 917         if (is_vfp_live(op1_reg_idx, live)) {
 918                 /* push the operand here */
 919                 x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
 920         } else {
 921                 /* operand is dead, bring it to tos */
 922                 if (op1_idx != 0) {
 923                         x87_create_fxch(state, n, op1_idx);
 924                 }
 925         }
 926
 927         x87_set_st(state, out_reg_idx, x87_patch_insn(n, op), 0);
 928         ia32_x87_attr_t *const attr = get_ia32_x87_attr(n);
 929         attr->x87[2] = attr->x87[0] = get_st_reg(0);
 930         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), attr->x87[2]->name));
 931
 932         return NO_NODE_ADDED;
 933 }
 934
 935 /**
 936  * Simulate a virtual Load instruction.
 937  *
 938  * @param state  the x87 state
 939  * @param n      the node that should be simulated (and patched)
 940  * @param op     the x87 opcode that will replace n's opcode
 941  *
 942  * @return NO_NODE_ADDED
 943  */
 944 static int sim_load(x87_state *state, ir_node *n, ir_op *op, int res_pos)
 945 {
 946         const arch_register_t *out = x87_irn_get_register(n, res_pos);
 947         ia32_x87_attr_t *attr;
 948
 949         DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, arch_register_get_name(out)));
 950         x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
 951         assert(out == x87_irn_get_register(n, res_pos));
 952         attr = get_ia32_x87_attr(n);
 953         attr->x87[2] = out = get_st_reg(0);
 954         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 955
 956         return NO_NODE_ADDED;
 957 }
 958
 959 /**
 960  * Rewire all users of @p old_val to @new_val iff they are scheduled after @p store.
 961  *
 962  * @param store   The store
 963  * @param old_val The former value
 964  * @param new_val The new value
 965  */
 966 static void collect_and_rewire_users(ir_node *store, ir_node *old_val, ir_node *new_val)
 967 {
 968         foreach_out_edge_safe(old_val, edge) {
 969                 ir_node *user = get_edge_src_irn(edge);
 970                 /* if the user is scheduled after the store: rewire */
 971                 if (sched_is_scheduled(user) && sched_comes_after(store, user)) {
 972                         set_irn_n(user, get_edge_src_pos(edge), new_val);
 973                 }
 974         }
 975 }
 976
 977 /**
 978  * Simulate a virtual Store.
 979  *
 980  * @param state  the x87 state
 981  * @param n      the node that should be simulated (and patched)
 982  * @param op     the x87 store opcode
 983  */
 984 static int sim_store(x87_state *state, ir_node *n, ir_op *op)
 985 {
 986         ir_node               *const val = get_irn_n(n, n_ia32_vfst_val);
 987         arch_register_t const *const op2 = x87_get_irn_register(val);
 988         DB((dbg, LEVEL_1, ">>> %+F %s ->\n", n, arch_register_get_name(op2)));
 989
 990         bool           do_pop          = false;
 991         int            insn            = NO_NODE_ADDED;
 992         int      const op2_reg_idx     = arch_register_get_index(op2);
 993         int      const op2_idx         = x87_on_stack(state, op2_reg_idx);
 994         unsigned const live            = vfp_live_args_after(state->sim, n, 0);
 995         int      const live_after_node = is_vfp_live(op2_reg_idx, live);
 996         assert(op2_idx >= 0);
 997         if (live_after_node) {
 998                 /* Problem: fst doesn't support 80bit modes (spills), only fstp does
 999                  *          fist doesn't support 64bit mode, only fistp
1000                  * Solution:
1001                  *   - stack not full: push value and fstp
1002                  *   - stack full: fstp value and load again
1003                  * Note that we cannot test on mode_E, because floats might be 80bit ... */
1004                 ir_mode *const mode = get_ia32_ls_mode(n);
1005                 if (get_mode_size_bits(mode) > (mode_is_int(mode) ? 32 : 64)) {
1006                         if (x87_get_depth(state) < N_ia32_st_REGS) {
1007                                 /* ok, we have a free register: push + fstp */
1008                                 x87_create_fpush(state, n, op2_idx, REG_VFP_VFP_NOREG, val);
1009                                 x87_patch_insn(n, op);
1010                                 do_pop = true;
1011                         } else {
1012                                 /* stack full here: need fstp + load */
1013                                 x87_patch_insn(n, op);
1014                                 do_pop = true;
1015
1016                                 ir_node *const block = get_nodes_block(n);
1017                                 ir_node *const mem   = get_irn_Proj_for_mode(n, mode_M);
1018                                 ir_node *const vfld  = new_bd_ia32_vfld(NULL, block, get_irn_n(n, 0), get_irn_n(n, 1), mem, mode);
1019
1020                                 /* copy all attributes */
1021                                 set_ia32_frame_ent(vfld, get_ia32_frame_ent(n));
1022                                 if (is_ia32_use_frame(n))
1023                                         set_ia32_use_frame(vfld);
1024                                 set_ia32_op_type(vfld, ia32_AddrModeS);
1025                                 add_ia32_am_offs_int(vfld, get_ia32_am_offs_int(n));
1026                                 set_ia32_am_sc(vfld, get_ia32_am_sc(n));
1027                                 set_ia32_ls_mode(vfld, mode);
1028
1029                                 ir_node *const rproj = new_r_Proj(vfld, mode, pn_ia32_vfld_res);
1030                                 ir_node *const mproj = new_r_Proj(vfld, mode_M, pn_ia32_vfld_M);
1031
1032                                 arch_set_irn_register(rproj, op2);
1033
1034                                 /* reroute all former users of the store memory to the load memory */
1035                                 edges_reroute_except(mem, mproj, vfld);
1036
1037                                 sched_add_after(n, vfld);
1038
1039                                 /* rewire all users, scheduled after the store, to the loaded value */
1040                                 collect_and_rewire_users(n, val, rproj);
1041
1042                                 insn = NODE_ADDED;
1043                         }
1044                 } else {
1045                         /* we can only store the tos to memory */
1046                         if (op2_idx != 0)
1047                                 x87_create_fxch(state, n, op2_idx);
1048
1049                         /* mode size 64 or smaller -> use normal fst */
1050                         x87_patch_insn(n, op);
1051                 }
1052         } else {
1053                 /* we can only store the tos to memory */
1054                 if (op2_idx != 0)
1055                         x87_create_fxch(state, n, op2_idx);
1056
1057                 x87_patch_insn(n, op);
1058                 do_pop = true;
1059         }
1060
1061         if (do_pop)
1062                 x87_pop(state);
1063
1064         ia32_x87_attr_t *const attr = get_ia32_x87_attr(n);
1065         attr->pop    = do_pop;
1066         attr->x87[1] = get_st_reg(0);
1067         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(attr->x87[1])));
1068
1069         return insn;
1070 }
1071
1072 #define GEN_BINOP(op) \
1073 static int sim_##op(x87_state *state, ir_node *n) { \
1074         return sim_binop(state, n, op_ia32_##op); \
1075 }
1076
1077 #define GEN_LOAD(op)                                              \
1078 static int sim_##op(x87_state *state, ir_node *n) {               \
1079         return sim_load(state, n, op_ia32_##op, pn_ia32_v##op##_res); \
1080 }
1081
1082 #define GEN_UNOP(op) \
1083 static int sim_##op(x87_state *state, ir_node *n) { \
1084         return sim_unop(state, n, op_ia32_##op); \
1085 }
1086
1087 #define GEN_STORE(op) \
1088 static int sim_##op(x87_state *state, ir_node *n) { \
1089         return sim_store(state, n, op_ia32_##op); \
1090 }
1091
1092 /* all stubs */
1093 GEN_BINOP(fadd)
1094 GEN_BINOP(fsub)
1095 GEN_BINOP(fmul)
1096 GEN_BINOP(fdiv)
1097
1098 GEN_UNOP(fabs)
1099 GEN_UNOP(fchs)
1100
1101 GEN_LOAD(fld)
1102 GEN_LOAD(fild)
1103 GEN_LOAD(fldz)
1104 GEN_LOAD(fld1)
1105
1106 GEN_STORE(fst)
1107 GEN_STORE(fist)
1108
1109 static int sim_fprem(x87_state *const state, ir_node *const n)
1110 {
1111         (void)state;
1112         (void)n;
1113         panic("TODO implement");
1114         return NO_NODE_ADDED;
1115 }
1116
1117 /**
1118  * Simulate a virtual fisttp.
1119  *
1120  * @param state  the x87 state
1121  * @param n      the node that should be simulated (and patched)
1122  *
1123  * @return NO_NODE_ADDED
1124  */
1125 static int sim_fisttp(x87_state *state, ir_node *n)
1126 {
1127         ir_node               *val = get_irn_n(n, n_ia32_vfst_val);
1128         const arch_register_t *op2 = x87_get_irn_register(val);
1129         ia32_x87_attr_t *attr;
1130         int op2_reg_idx, op2_idx;
1131
1132         op2_reg_idx = arch_register_get_index(op2);
1133         op2_idx     = x87_on_stack(state, op2_reg_idx);
1134         DB((dbg, LEVEL_1, ">>> %+F %s ->\n", n, arch_register_get_name(op2)));
1135         assert(op2_idx >= 0);
1136
1137         /* Note: although the value is still live here, it is destroyed because
1138            of the pop. The register allocator is aware of that and introduced a copy
1139            if the value must be alive. */
1140
1141         /* we can only store the tos to memory */
1142         if (op2_idx != 0)
1143                 x87_create_fxch(state, n, op2_idx);
1144
1145         x87_pop(state);
1146         x87_patch_insn(n, op_ia32_fisttp);
1147
1148         attr = get_ia32_x87_attr(n);
1149         attr->x87[1] = op2 = get_st_reg(0);
1150         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
1151
1152         return NO_NODE_ADDED;
1153 }
1154
1155 /**
1156  * Simulate a virtual FtstFnstsw.
1157  *
1158  * @param state  the x87 state
1159  * @param n      the node that should be simulated (and patched)
1160  *
1161  * @return NO_NODE_ADDED
1162  */
1163 static int sim_FtstFnstsw(x87_state *state, ir_node *n)
1164 {
1165         x87_simulator         *sim         = state->sim;
1166         ia32_x87_attr_t       *attr        = get_ia32_x87_attr(n);
1167         ir_node               *op1_node    = get_irn_n(n, n_ia32_vFtstFnstsw_left);
1168         const arch_register_t *reg1        = x87_get_irn_register(op1_node);
1169         int                    reg_index_1 = arch_register_get_index(reg1);
1170         int                    op1_idx     = x87_on_stack(state, reg_index_1);
1171         unsigned               live        = vfp_live_args_after(sim, n, 0);
1172
1173         DB((dbg, LEVEL_1, ">>> %+F %s\n", n, arch_register_get_name(reg1)));
1174         DEBUG_ONLY(vfp_dump_live(live);)
1175         DB((dbg, LEVEL_1, "Stack before: "));
1176         DEBUG_ONLY(x87_dump_stack(state);)
1177         assert(op1_idx >= 0);
1178
1179         if (op1_idx != 0) {
1180                 /* bring the value to tos */
1181                 x87_create_fxch(state, n, op1_idx);
1182                 op1_idx = 0;
1183         }
1184
1185         /* patch the operation */
1186         x87_patch_insn(n, op_ia32_FtstFnstsw);
1187         reg1 = get_st_reg(op1_idx);
1188         attr->x87[0] = reg1;
1189         attr->x87[1] = NULL;
1190         attr->x87[2] = NULL;
1191
1192         if (!is_vfp_live(reg_index_1, live))
1193                 x87_create_fpop(state, sched_next(n), 1);
1194
1195         return NO_NODE_ADDED;
1196 }
1197
1198 /**
1199  * Simulate a Fucom
1200  *
1201  * @param state  the x87 state
1202  * @param n      the node that should be simulated (and patched)
1203  *
1204  * @return NO_NODE_ADDED
1205  */
1206 static int sim_Fucom(x87_state *state, ir_node *n)
1207 {
1208         int op1_idx;
1209         int op2_idx = -1;
1210         ia32_x87_attr_t *attr = get_ia32_x87_attr(n);
1211         ir_op *dst;
1212         x87_simulator         *sim        = state->sim;
1213         ir_node               *op1_node   = get_irn_n(n, n_ia32_vFucomFnstsw_left);
1214         ir_node               *op2_node   = get_irn_n(n, n_ia32_vFucomFnstsw_right);
1215         const arch_register_t *op1        = x87_get_irn_register(op1_node);
1216         const arch_register_t *op2        = x87_get_irn_register(op2_node);
1217         int reg_index_1 = arch_register_get_index(op1);
1218         int                    reg_index_2 = arch_register_get_index(op2);
1219         unsigned               live       = vfp_live_args_after(sim, n, 0);
1220         bool                   permuted   = attr->attr.data.ins_permuted;
1221         bool                   xchg       = false;
1222         int                    pops       = 0;
1223
1224         DB((dbg, LEVEL_1, ">>> %+F %s, %s\n", n,
1225                 arch_register_get_name(op1), arch_register_get_name(op2)));
1226         DEBUG_ONLY(vfp_dump_live(live);)
1227         DB((dbg, LEVEL_1, "Stack before: "));
1228         DEBUG_ONLY(x87_dump_stack(state);)
1229
1230         op1_idx = x87_on_stack(state, reg_index_1);
1231         assert(op1_idx >= 0);
1232
1233         /* BEWARE: check for comp a,a cases, they might happen */
1234         if (reg_index_2 != REG_VFP_VFP_NOREG) {
1235                 /* second operand is a vfp register */
1236                 op2_idx = x87_on_stack(state, reg_index_2);
1237                 assert(op2_idx >= 0);
1238
1239                 if (is_vfp_live(reg_index_2, live)) {
1240                         /* second operand is live */
1241
1242                         if (is_vfp_live(reg_index_1, live)) {
1243                                 /* both operands are live */
1244
1245                                 if (op1_idx == 0) {
1246                                         /* res = tos X op */
1247                                 } else if (op2_idx == 0) {
1248                                         /* res = op X tos */
1249                                         permuted = !permuted;
1250                                         xchg     = true;
1251                                 } else {
1252                                         /* bring the first one to tos */
1253                                         x87_create_fxch(state, n, op1_idx);
1254                                         if (op1_idx == op2_idx) {
1255                                                 op2_idx = 0;
1256                                         } else if (op2_idx == 0) {
1257                                                 op2_idx = op1_idx;
1258                                         }
1259                                         op1_idx = 0;
1260                                         /* res = tos X op */
1261                                 }
1262                         } else {
1263                                 /* second live, first operand is dead here, bring it to tos.
1264                                    This means further, op1_idx != op2_idx. */
1265                                 assert(op1_idx != op2_idx);
1266                                 if (op1_idx != 0) {
1267                                         x87_create_fxch(state, n, op1_idx);
1268                                         if (op2_idx == 0)
1269                                                 op2_idx = op1_idx;
1270                                         op1_idx = 0;
1271                                 }
1272                                 /* res = tos X op, pop */
1273                                 pops = 1;
1274                         }
1275                 } else {
1276                         /* second operand is dead */
1277                         if (is_vfp_live(reg_index_1, live)) {
1278                                 /* first operand is live: bring second to tos.
1279                                    This means further, op1_idx != op2_idx. */
1280                                 assert(op1_idx != op2_idx);
1281                                 if (op2_idx != 0) {
1282                                         x87_create_fxch(state, n, op2_idx);
1283                                         if (op1_idx == 0)
1284                                                 op1_idx = op2_idx;
1285                                         op2_idx = 0;
1286                                 }
1287                                 /* res = op X tos, pop */
1288                                 pops     = 1;
1289                                 permuted = !permuted;
1290                                 xchg     = true;
1291                         } else {
1292                                 /* both operands are dead here, check first for identity. */
1293                                 if (op1_idx == op2_idx) {
1294                                         /* identically, one pop needed */
1295                                         if (op1_idx != 0) {
1296                                                 x87_create_fxch(state, n, op1_idx);
1297                                                 op1_idx = 0;
1298                                                 op2_idx = 0;
1299                                         }
1300                                         /* res = tos X op, pop */
1301                                         pops    = 1;
1302                                 }
1303                                 /* different, move them to st and st(1) and pop both.
1304                                    The tricky part is to get one into st(1).*/
1305                                 else if (op2_idx == 1) {
1306                                         /* good, second operand is already in the right place, move the first */
1307                                         if (op1_idx != 0) {
1308                                                 /* bring the first on top */
1309                                                 x87_create_fxch(state, n, op1_idx);
1310                                                 assert(op2_idx != 0);
1311                                                 op1_idx = 0;
1312                                         }
1313                                         /* res = tos X op, pop, pop */
1314                                         pops = 2;
1315                                 } else if (op1_idx == 1) {
1316                                         /* good, first operand is already in the right place, move the second */
1317                                         if (op2_idx != 0) {
1318                                                 /* bring the first on top */
1319                                                 x87_create_fxch(state, n, op2_idx);
1320                                                 assert(op1_idx != 0);
1321                                                 op2_idx = 0;
1322                                         }
1323                                         /* res = op X tos, pop, pop */
1324                                         permuted = !permuted;
1325                                         xchg     = true;
1326                                         pops     = 2;
1327                                 } else {
1328                                         /* if one is already the TOS, we need two fxch */
1329                                         if (op1_idx == 0) {
1330                                                 /* first one is TOS, move to st(1) */
1331                                                 x87_create_fxch(state, n, 1);
1332                                                 assert(op2_idx != 1);
1333                                                 op1_idx = 1;
1334                                                 x87_create_fxch(state, n, op2_idx);
1335                                                 op2_idx = 0;
1336                                                 /* res = op X tos, pop, pop */
1337                                                 pops     = 2;
1338                                                 permuted = !permuted;
1339                                                 xchg     = true;
1340                                         } else if (op2_idx == 0) {
1341                                                 /* second one is TOS, move to st(1) */
1342                                                 x87_create_fxch(state, n, 1);
1343                                                 assert(op1_idx != 1);
1344                                                 op2_idx = 1;
1345                                                 x87_create_fxch(state, n, op1_idx);
1346                                                 op1_idx = 0;
1347                                                 /* res = tos X op, pop, pop */
1348                                                 pops    = 2;
1349                                         } else {
1350                                                 /* none of them is either TOS or st(1), 3 fxch needed */
1351                                                 x87_create_fxch(state, n, op2_idx);
1352                                                 assert(op1_idx != 0);
1353                                                 x87_create_fxch(state, n, 1);
1354                                                 op2_idx = 1;
1355                                                 x87_create_fxch(state, n, op1_idx);
1356                                                 op1_idx = 0;
1357                                                 /* res = tos X op, pop, pop */
1358                                                 pops    = 2;
1359                                         }
1360                                 }
1361                         }
1362                 }
1363         } else {
1364                 /* second operand is an address mode */
1365                 if (is_vfp_live(reg_index_1, live)) {
1366                         /* first operand is live: bring it to TOS */
1367                         if (op1_idx != 0) {
1368                                 x87_create_fxch(state, n, op1_idx);
1369                                 op1_idx = 0;
1370                         }
1371                 } else {
1372                         /* first operand is dead: bring it to tos */
1373                         if (op1_idx != 0) {
1374                                 x87_create_fxch(state, n, op1_idx);
1375                                 op1_idx = 0;
1376                         }
1377                         pops = 1;
1378                 }
1379         }
1380
1381         /* patch the operation */
1382         if (is_ia32_vFucomFnstsw(n)) {
1383                 int i;
1384
1385                 switch (pops) {
1386                 case 0: dst = op_ia32_FucomFnstsw;   break;
1387                 case 1: dst = op_ia32_FucompFnstsw;  break;
1388                 case 2: dst = op_ia32_FucomppFnstsw; break;
1389                 default: panic("invalid popcount");
1390                 }
1391
1392                 for (i = 0; i < pops; ++i) {
1393                         x87_pop(state);
1394                 }
1395         } else if (is_ia32_vFucomi(n)) {
1396                 switch (pops) {
1397                 case 0: dst = op_ia32_Fucomi;                  break;
1398                 case 1: dst = op_ia32_Fucompi; x87_pop(state); break;
1399                 case 2:
1400                         dst = op_ia32_Fucompi;
1401                         x87_pop(state);
1402                         x87_create_fpop(state, sched_next(n), 1);
1403                         break;
1404                 default: panic("invalid popcount");
1405                 }
1406         } else {
1407                 panic("invalid operation %+F", n);
1408         }
1409
1410         x87_patch_insn(n, dst);
1411         if (xchg) {
1412                 int tmp = op1_idx;
1413                 op1_idx = op2_idx;
1414                 op2_idx = tmp;
1415         }
1416
1417         op1 = get_st_reg(op1_idx);
1418         attr->x87[0] = op1;
1419         if (op2_idx >= 0) {
1420                 op2 = get_st_reg(op2_idx);
1421                 attr->x87[1] = op2;
1422         }
1423         attr->x87[2] = NULL;
1424         attr->attr.data.ins_permuted = permuted;
1425
1426         if (op2_idx >= 0) {
1427                 DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(n),
1428                         arch_register_get_name(op1), arch_register_get_name(op2)));
1429         } else {
1430                 DB((dbg, LEVEL_1, "<<< %s %s, [AM]\n", get_irn_opname(n),
1431                         arch_register_get_name(op1)));
1432         }
1433
1434         return NO_NODE_ADDED;
1435 }
1436
1437 /**
1438  * Simulate a Keep.
1439  *
1440  * @param state  the x87 state
1441  * @param n      the node that should be simulated (and patched)
1442  *
1443  * @return NO_NODE_ADDED
1444  */
1445 static int sim_Keep(x87_state *state, ir_node *node)
1446 {
1447         const ir_node         *op;
1448         const arch_register_t *op_reg;
1449         int                    reg_id;
1450         int                    op_stack_idx;
1451         unsigned               live;
1452         int                    i, arity;
1453
1454         DB((dbg, LEVEL_1, ">>> %+F\n", node));
1455
1456         arity = get_irn_arity(node);
1457         for (i = 0; i < arity; ++i) {
1458                 op      = get_irn_n(node, i);
1459                 op_reg  = arch_get_irn_register(op);
1460                 if (arch_register_get_class(op_reg) != &ia32_reg_classes[CLASS_ia32_vfp])
1461                         continue;
1462
1463                 reg_id = arch_register_get_index(op_reg);
1464                 live   = vfp_live_args_after(state->sim, node, 0);
1465
1466                 op_stack_idx = x87_on_stack(state, reg_id);
1467                 if (op_stack_idx >= 0 && !is_vfp_live(reg_id, live))
1468                         x87_create_fpop(state, sched_next(node), 1);
1469         }
1470
1471         DB((dbg, LEVEL_1, "Stack after: "));
1472         DEBUG_ONLY(x87_dump_stack(state);)
1473
1474         return NO_NODE_ADDED;
1475 }
1476
1477 /**
1478  * Keep the given node alive by adding a be_Keep.
1479  *
1480  * @param node  the node to kept alive
1481  */
1482 static void keep_float_node_alive(ir_node *node)
1483 {
1484         ir_node *block = get_nodes_block(node);
1485         ir_node *keep  = be_new_Keep(block, 1, &node);
1486         sched_add_after(node, keep);
1487 }
1488
1489 /**
1490  * Create a copy of a node. Recreate the node if it's a constant.
1491  *
1492  * @param state  the x87 state
1493  * @param n      the node to be copied
1494  *
1495  * @return the copy of n
1496  */
1497 static ir_node *create_Copy(x87_state *state, ir_node *n)
1498 {
1499         dbg_info *n_dbg = get_irn_dbg_info(n);
1500         ir_mode *mode = get_irn_mode(n);
1501         ir_node *block = get_nodes_block(n);
1502         ir_node *pred = get_irn_n(n, 0);
1503         ir_node *(*cnstr)(dbg_info *, ir_node *, ir_mode *) = NULL;
1504         ir_node *res;
1505         const arch_register_t *out;
1506         const arch_register_t *op1;
1507         ia32_x87_attr_t *attr;
1508
1509         /* Do not copy constants, recreate them. */
1510         switch (get_ia32_irn_opcode(pred)) {
1511         case iro_ia32_fldz:
1512                 cnstr = new_bd_ia32_fldz;
1513                 break;
1514         case iro_ia32_fld1:
1515                 cnstr = new_bd_ia32_fld1;
1516                 break;
1517         case iro_ia32_fldpi:
1518                 cnstr = new_bd_ia32_fldpi;
1519                 break;
1520         case iro_ia32_fldl2e:
1521                 cnstr = new_bd_ia32_fldl2e;
1522                 break;
1523         case iro_ia32_fldl2t:
1524                 cnstr = new_bd_ia32_fldl2t;
1525                 break;
1526         case iro_ia32_fldlg2:
1527                 cnstr = new_bd_ia32_fldlg2;
1528                 break;
1529         case iro_ia32_fldln2:
1530                 cnstr = new_bd_ia32_fldln2;
1531                 break;
1532         default:
1533                 break;
1534         }
1535
1536         out = x87_get_irn_register(n);
1537         op1 = x87_get_irn_register(pred);
1538
1539         if (cnstr != NULL) {
1540                 /* copy a constant */
1541                 res = (*cnstr)(n_dbg, block, mode);
1542
1543                 x87_push(state, arch_register_get_index(out), res);
1544
1545                 attr = get_ia32_x87_attr(res);
1546                 attr->x87[2] = get_st_reg(0);
1547         } else {
1548                 int op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1549
1550                 res = new_bd_ia32_fpushCopy(n_dbg, block, pred, mode);
1551
1552                 x87_push(state, arch_register_get_index(out), res);
1553
1554                 attr = get_ia32_x87_attr(res);
1555                 attr->x87[0] = get_st_reg(op1_idx);
1556                 attr->x87[2] = get_st_reg(0);
1557         }
1558         arch_set_irn_register(res, out);
1559
1560         return res;
1561 }
1562
1563 /**
1564  * Simulate a be_Copy.
1565  *
1566  * @param state  the x87 state
1567  * @param n      the node that should be simulated (and patched)
1568  *
1569  * @return NO_NODE_ADDED
1570  */
1571 static int sim_Copy(x87_state *state, ir_node *n)
1572 {
1573         arch_register_class_t const *const cls = arch_get_irn_reg_class(n);
1574         if (cls != &ia32_reg_classes[CLASS_ia32_vfp])
1575                 return NO_NODE_ADDED;
1576
1577         ir_node               *const pred = be_get_Copy_op(n);
1578         arch_register_t const *const op1  = x87_get_irn_register(pred);
1579         arch_register_t const *const out  = x87_get_irn_register(n);
1580         unsigned               const live = vfp_live_args_after(state->sim, n, REGMASK(out));
1581
1582         DB((dbg, LEVEL_1, ">>> %+F %s -> %s\n", n,
1583                 arch_register_get_name(op1), arch_register_get_name(out)));
1584         DEBUG_ONLY(vfp_dump_live(live);)
1585
1586         if (is_vfp_live(arch_register_get_index(op1), live)) {
1587                 /* Operand is still live, a real copy. We need here an fpush that can
1588                    hold a a register, so use the fpushCopy or recreate constants */
1589                 ir_node *const node = create_Copy(state, n);
1590
1591                 /* We have to make sure the old value doesn't go dead (which can happen
1592                  * when we recreate constants). As the simulator expected that value in
1593                  * the pred blocks. This is unfortunate as removing it would save us 1
1594                  * instruction, but we would have to rerun all the simulation to get
1595                  * this correct...
1596                  */
1597                 ir_node *const next = sched_next(n);
1598                 sched_remove(n);
1599                 exchange(n, node);
1600                 sched_add_before(next, node);
1601
1602                 if (get_irn_n_edges(pred) == 0) {
1603                         keep_float_node_alive(pred);
1604                 }
1605
1606                 DB((dbg, LEVEL_1, "<<< %+F %s -> ?\n", node, op1->name));
1607         } else {
1608                 /* Just a virtual copy. */
1609                 int const op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1610                 x87_set_st(state, arch_register_get_index(out), n, op1_idx);
1611         }
1612         return NO_NODE_ADDED;
1613 }
1614
1615 /**
1616  * Returns the vf0 result Proj of a Call.
1617  *
1618  * @para call  the Call node
1619  */
1620 static ir_node *get_call_result_proj(ir_node *call)
1621 {
1622         /* search the result proj */
1623         foreach_out_edge(call, edge) {
1624                 ir_node *proj = get_edge_src_irn(edge);
1625                 long pn = get_Proj_proj(proj);
1626
1627                 if (pn == pn_ia32_Call_vf0)
1628                         return proj;
1629         }
1630
1631         panic("result Proj missing");
1632 }
1633
1634 static int sim_Asm(x87_state *const state, ir_node *const n)
1635 {
1636         (void)state;
1637
1638         for (size_t i = get_irn_arity(n); i-- != 0;) {
1639                 arch_register_req_t const *const req = arch_get_irn_register_req_in(n, i);
1640                 if (req->cls == &ia32_reg_classes[CLASS_ia32_vfp])
1641                         panic("cannot handle %+F with x87 constraints", n);
1642         }
1643
1644         for (size_t i = arch_get_irn_n_outs(n); i-- != 0;) {
1645                 arch_register_req_t const *const req = arch_get_irn_register_req_out(n, i);
1646                 if (req->cls == &ia32_reg_classes[CLASS_ia32_vfp])
1647                         panic("cannot handle %+F with x87 constraints", n);
1648         }
1649
1650         return NO_NODE_ADDED;
1651 }
1652
1653 /**
1654  * Simulate a ia32_Call.
1655  *
1656  * @param state      the x87 state
1657  * @param n          the node that should be simulated (and patched)
1658  *
1659  * @return NO_NODE_ADDED
1660  */
1661 static int sim_Call(x87_state *state, ir_node *n)
1662 {
1663         DB((dbg, LEVEL_1, ">>> %+F\n", n));
1664
1665         /* at the begin of a call the x87 state should be empty */
1666         assert(state->depth == 0 && "stack not empty before call");
1667
1668         ir_type *const call_tp = get_ia32_call_attr_const(n)->call_tp;
1669         if (get_method_n_ress(call_tp) != 0) {
1670                 /* If the called function returns a float, it is returned in st(0).
1671                  * This even happens if the return value is NOT used.
1672                  * Moreover, only one return result is supported. */
1673                 ir_type *const res_type = get_method_res_type(call_tp, 0);
1674                 ir_mode *const mode     = get_type_mode(res_type);
1675                 if (mode && mode_is_float(mode)) {
1676                         ir_node               *const resproj = get_call_result_proj(n);
1677                         arch_register_t const *const reg     = x87_get_irn_register(resproj);
1678                         x87_push(state, arch_register_get_index(reg), resproj);
1679                 }
1680         }
1681         DB((dbg, LEVEL_1, "Stack after: "));
1682         DEBUG_ONLY(x87_dump_stack(state);)
1683
1684         return NO_NODE_ADDED;
1685 }
1686
1687 /**
1688  * Simulate a be_Return.
1689  *
1690  * @param state  the x87 state
1691  * @param n      the node that should be simulated (and patched)
1692  *
1693  * @return NO_NODE_ADDED
1694  */
1695 static int sim_Return(x87_state *state, ir_node *n)
1696 {
1697 #ifdef DEBUG_libfirm
1698         /* only floating point return values must reside on stack */
1699         int       n_float_res = 0;
1700         int const n_res       = be_Return_get_n_rets(n);
1701         for (int i = 0; i < n_res; ++i) {
1702                 ir_node *const res = get_irn_n(n, n_be_Return_val + i);
1703                 if (mode_is_float(get_irn_mode(res)))
1704                         ++n_float_res;
1705         }
1706         assert(x87_get_depth(state) == n_float_res);
1707 #endif
1708
1709         /* pop them virtually */
1710         x87_emms(state);
1711         return NO_NODE_ADDED;
1712 }
1713
1714 /**
1715  * Simulate a be_Perm.
1716  *
1717  * @param state  the x87 state
1718  * @param irn    the node that should be simulated (and patched)
1719  *
1720  * @return NO_NODE_ADDED
1721  */
1722 static int sim_Perm(x87_state *state, ir_node *irn)
1723 {
1724         int      i, n;
1725         ir_node *pred = get_irn_n(irn, 0);
1726         int     *stack_pos;
1727
1728         /* handle only floating point Perms */
1729         if (! mode_is_float(get_irn_mode(pred)))
1730                 return NO_NODE_ADDED;
1731
1732         DB((dbg, LEVEL_1, ">>> %+F\n", irn));
1733
1734         /* Perm is a pure virtual instruction on x87.
1735            All inputs must be on the FPU stack and are pairwise
1736            different from each other.
1737            So, all we need to do is to permutate the stack state. */
1738         n = get_irn_arity(irn);
1739         NEW_ARR_A(int, stack_pos, n);
1740
1741         /* collect old stack positions */
1742         for (i = 0; i < n; ++i) {
1743                 const arch_register_t *inreg = x87_get_irn_register(get_irn_n(irn, i));
1744                 int idx = x87_on_stack(state, arch_register_get_index(inreg));
1745
1746                 assert(idx >= 0 && "Perm argument not on x87 stack");
1747
1748                 stack_pos[i] = idx;
1749         }
1750         /* now do the permutation */
1751         foreach_out_edge(irn, edge) {
1752                 ir_node               *proj = get_edge_src_irn(edge);
1753                 const arch_register_t *out  = x87_get_irn_register(proj);
1754                 long                  num   = get_Proj_proj(proj);
1755
1756                 assert(0 <= num && num < n && "More Proj's than Perm inputs");
1757                 x87_set_st(state, arch_register_get_index(out), proj, stack_pos[(unsigned)num]);
1758         }
1759         DB((dbg, LEVEL_1, "<<< %+F\n", irn));
1760
1761         return NO_NODE_ADDED;
1762 }
1763
1764 /**
1765  * Kill any dead registers at block start by popping them from the stack.
1766  *
1767  * @param sim    the simulator handle
1768  * @param block  the current block
1769  * @param state  the x87 state at the begin of the block
1770  */
1771 static void x87_kill_deads(x87_simulator *const sim, ir_node *const block, x87_state *const state)
1772 {
1773         ir_node *first_insn = sched_first(block);
1774         ir_node *keep = NULL;
1775         unsigned live = vfp_live_args_after(sim, block, 0);
1776         unsigned kill_mask;
1777         int i, depth, num_pop;
1778
1779         kill_mask = 0;
1780         depth = x87_get_depth(state);
1781         for (i = depth - 1; i >= 0; --i) {
1782                 int reg = x87_get_st_reg(state, i);
1783
1784                 if (! is_vfp_live(reg, live))
1785                         kill_mask |= (1 << i);
1786         }
1787
1788         if (kill_mask) {
1789                 DB((dbg, LEVEL_1, "Killing deads:\n"));
1790                 DEBUG_ONLY(vfp_dump_live(live);)
1791                 DEBUG_ONLY(x87_dump_stack(state);)
1792
1793                 if (kill_mask != 0 && live == 0) {
1794                         /* special case: kill all registers */
1795                         if (ia32_cg_config.use_femms || ia32_cg_config.use_emms) {
1796                                 if (ia32_cg_config.use_femms) {
1797                                         /* use FEMMS on AMD processors to clear all */
1798                                         keep = new_bd_ia32_femms(NULL, block);
1799                                 } else {
1800                                         /* use EMMS to clear all */
1801                                         keep = new_bd_ia32_emms(NULL, block);
1802                                 }
1803                                 sched_add_before(first_insn, keep);
1804                                 keep_alive(keep);
1805                                 x87_emms(state);
1806                                 return;
1807                         }
1808                 }
1809                 /* now kill registers */
1810                 while (kill_mask) {
1811                         /* we can only kill from TOS, so bring them up */
1812                         if (! (kill_mask & 1)) {
1813                                 /* search from behind, because we can to a double-pop */
1814                                 for (i = depth - 1; i >= 0; --i) {
1815                                         if (kill_mask & (1 << i)) {
1816                                                 kill_mask &= ~(1 << i);
1817                                                 kill_mask |= 1;
1818                                                 break;
1819                                         }
1820                                 }
1821
1822                                 if (keep)
1823                                         x87_set_st(state, -1, keep, i);
1824                                 x87_create_fxch(state, first_insn, i);
1825                         }
1826
1827                         if ((kill_mask & 3) == 3) {
1828                                 /* we can do a double-pop */
1829                                 num_pop = 2;
1830                         }
1831                         else {
1832                                 /* only a single pop */
1833                                 num_pop = 1;
1834                         }
1835
1836                         depth -= num_pop;
1837                         kill_mask >>= num_pop;
1838                         keep = x87_create_fpop(state, first_insn, num_pop);
1839                 }
1840                 keep_alive(keep);
1841         }
1842 }
1843
1844 /**
1845  * Run a simulation and fix all virtual instructions for a block.
1846  *
1847  * @param sim          the simulator handle
1848  * @param block        the current block
1849  */
1850 static void x87_simulate_block(x87_simulator *sim, ir_node *block)
1851 {
1852         ir_node *n, *next;
1853         blk_state *bl_state = x87_get_bl_state(sim, block);
1854         x87_state *state = bl_state->begin;
1855         ir_node *start_block;
1856
1857         assert(state != NULL);
1858         /* already processed? */
1859         if (bl_state->end != NULL)
1860                 return;
1861
1862         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
1863         DB((dbg, LEVEL_2, "State at Block begin:\n "));
1864         DEBUG_ONLY(x87_dump_stack(state);)
1865
1866         /* create a new state, will be changed */
1867         state = x87_clone_state(sim, state);
1868         /* at block begin, kill all dead registers */
1869         x87_kill_deads(sim, block, state);
1870
1871         /* beware, n might change */
1872         for (n = sched_first(block); !sched_is_end(n); n = next) {
1873                 int node_inserted;
1874                 sim_func func;
1875                 ir_op *op = get_irn_op(n);
1876
1877                 /*
1878                  * get the next node to be simulated here.
1879                  * n might be completely removed from the schedule-
1880                  */
1881                 next = sched_next(n);
1882                 if (op->ops.generic != NULL) {
1883                         func = (sim_func)op->ops.generic;
1884
1885                         /* simulate it */
1886                         node_inserted = (*func)(state, n);
1887
1888                         /*
1889                          * sim_func might have added an additional node after n,
1890                          * so update next node
1891                          * beware: n must not be changed by sim_func
1892                          * (i.e. removed from schedule) in this case
1893                          */
1894                         if (node_inserted != NO_NODE_ADDED)
1895                                 next = sched_next(n);
1896                 }
1897         }
1898
1899         start_block = get_irg_start_block(get_irn_irg(block));
1900
1901         DB((dbg, LEVEL_2, "State at Block end:\n ")); DEBUG_ONLY(x87_dump_stack(state);)
1902
1903         /* check if the state must be shuffled */
1904         foreach_block_succ(block, edge) {
1905                 ir_node *succ = get_edge_src_irn(edge);
1906                 blk_state *succ_state;
1907
1908                 if (succ == start_block)
1909                         continue;
1910
1911                 succ_state = x87_get_bl_state(sim, succ);
1912
1913                 if (succ_state->begin == NULL) {
1914                         DB((dbg, LEVEL_2, "Set begin state for succ %+F:\n", succ));
1915                         DEBUG_ONLY(x87_dump_stack(state);)
1916                         succ_state->begin = state;
1917
1918                         waitq_put(sim->worklist, succ);
1919                 } else {
1920                         DB((dbg, LEVEL_2, "succ %+F already has a state, shuffling\n", succ));
1921                         /* There is already a begin state for the successor, bad.
1922                            Do the necessary permutations.
1923                            Note that critical edges are removed, so this is always possible:
1924                            If the successor has more than one possible input, then it must
1925                            be the only one.
1926                          */
1927                         x87_shuffle(block, state, succ_state->begin);
1928                 }
1929         }
1930         bl_state->end = state;
1931 }
1932
1933 /**
1934  * Register a simulator function.
1935  *
1936  * @param op    the opcode to simulate
1937  * @param func  the simulator function for the opcode
1938  */
1939 static void register_sim(ir_op *op, sim_func func)
1940 {
1941         assert(op->ops.generic == NULL);
1942         op->ops.generic = (op_func) func;
1943 }
1944
1945 /**
1946  * Create a new x87 simulator.
1947  *
1948  * @param sim       a simulator handle, will be initialized
1949  * @param irg       the current graph
1950  */
1951 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg)
1952 {
1953         obstack_init(&sim->obst);
1954         sim->blk_states = pmap_create();
1955         sim->n_idx      = get_irg_last_idx(irg);
1956         sim->live       = OALLOCN(&sim->obst, vfp_liveness, sim->n_idx);
1957
1958         DB((dbg, LEVEL_1, "--------------------------------\n"
1959                 "x87 Simulator started for %+F\n", irg));
1960
1961         /* set the generic function pointer of instruction we must simulate */
1962         ir_clear_opcodes_generic_func();
1963
1964         register_sim(op_ia32_Asm,          sim_Asm);
1965         register_sim(op_ia32_Call,         sim_Call);
1966         register_sim(op_ia32_vfld,         sim_fld);
1967         register_sim(op_ia32_vfild,        sim_fild);
1968         register_sim(op_ia32_vfld1,        sim_fld1);
1969         register_sim(op_ia32_vfldz,        sim_fldz);
1970         register_sim(op_ia32_vfadd,        sim_fadd);
1971         register_sim(op_ia32_vfsub,        sim_fsub);
1972         register_sim(op_ia32_vfmul,        sim_fmul);
1973         register_sim(op_ia32_vfdiv,        sim_fdiv);
1974         register_sim(op_ia32_vfprem,       sim_fprem);
1975         register_sim(op_ia32_vfabs,        sim_fabs);
1976         register_sim(op_ia32_vfchs,        sim_fchs);
1977         register_sim(op_ia32_vfist,        sim_fist);
1978         register_sim(op_ia32_vfisttp,      sim_fisttp);
1979         register_sim(op_ia32_vfst,         sim_fst);
1980         register_sim(op_ia32_vFtstFnstsw,  sim_FtstFnstsw);
1981         register_sim(op_ia32_vFucomFnstsw, sim_Fucom);
1982         register_sim(op_ia32_vFucomi,      sim_Fucom);
1983         register_sim(op_be_Copy,           sim_Copy);
1984         register_sim(op_be_Return,         sim_Return);
1985         register_sim(op_be_Perm,           sim_Perm);
1986         register_sim(op_be_Keep,           sim_Keep);
1987 }
1988
1989 /**
1990  * Destroy a x87 simulator.
1991  *
1992  * @param sim  the simulator handle
1993  */
1994 static void x87_destroy_simulator(x87_simulator *sim)
1995 {
1996         pmap_destroy(sim->blk_states);
1997         obstack_free(&sim->obst, NULL);
1998         DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
1999 }
2000
2001 /**
2002  * Pre-block walker: calculate the liveness information for the block
2003  * and store it into the sim->live cache.
2004  */
2005 static void update_liveness_walker(ir_node *block, void *data)
2006 {
2007         x87_simulator *sim = (x87_simulator*)data;
2008         update_liveness(sim, block);
2009 }
2010
2011 /*
2012  * Run a simulation and fix all virtual instructions for a graph.
2013  * Replaces all virtual floating point instructions and registers
2014  * by real ones.
2015  */
2016 void ia32_x87_simulate_graph(ir_graph *irg)
2017 {
2018         /* TODO improve code quality (less executed fxch) by using execfreqs */
2019
2020         ir_node       *block, *start_block;
2021         blk_state     *bl_state;
2022         x87_simulator sim;
2023
2024         /* create the simulator */
2025         x87_init_simulator(&sim, irg);
2026
2027         start_block = get_irg_start_block(irg);
2028         bl_state    = x87_get_bl_state(&sim, start_block);
2029
2030         /* start with the empty state */
2031         empty.sim       = &sim;
2032         bl_state->begin = &empty;
2033
2034         sim.worklist = new_waitq();
2035         waitq_put(sim.worklist, start_block);
2036
2037         be_assure_live_sets(irg);
2038         sim.lv = be_get_irg_liveness(irg);
2039
2040         /* Calculate the liveness for all nodes. We must precalculate this info,
2041          * because the simulator adds new nodes (possible before Phi nodes) which
2042          * would let a lazy calculation fail.
2043          * On the other hand we reduce the computation amount due to
2044          * precaching from O(n^2) to O(n) at the expense of O(n) cache memory.
2045          */
2046         irg_block_walk_graph(irg, update_liveness_walker, NULL, &sim);
2047
2048         /* iterate */
2049         do {
2050                 block = (ir_node*)waitq_get(sim.worklist);
2051                 x87_simulate_block(&sim, block);
2052         } while (! waitq_empty(sim.worklist));
2053
2054         /* kill it */
2055         del_waitq(sim.worklist);
2056         x87_destroy_simulator(&sim);
2057 }
2058
2059 /* Initializes the x87 simulator. */
2060 void ia32_init_x87(void)
2061 {
2062         FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
2063 }