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

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