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