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