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

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