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