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