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