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

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