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 = state->sim;
1663         ir_node                     *pred;
1664         const arch_register_t       *out;
1665         const arch_register_t       *op1;
1666         const arch_register_class_t *class;
1667         ir_node                     *node, *next;
1668         ia32_x87_attr_t             *attr;
1669         int                         op1_idx, out_idx;
1670         unsigned                    live;
1671
1672         class = arch_get_irn_reg_class(sim->arch_env, n, -1);
1673         if (class->regs != ia32_vfp_regs)
1674                 return 0;
1675
1676         pred = get_irn_n(n, 0);
1677         out  = x87_get_irn_register(sim, n);
1678         op1  = x87_get_irn_register(sim, pred);
1679         live = vfp_live_args_after(sim, n, REGMASK(out));
1680
1681         DB((dbg, LEVEL_1, ">>> %+F %s -> %s\n", n,
1682                 arch_register_get_name(op1), arch_register_get_name(out)));
1683         DEBUG_ONLY(vfp_dump_live(live));
1684
1685         /* handle the infamous unknown value */
1686         if (arch_register_get_index(op1) == REG_VFP_UKNWN) {
1687                 /* Operand is still live, a real copy. We need here an fpush that can
1688                    hold a a register, so use the fpushCopy or recreate constants */
1689                 node = create_Copy(state, n);
1690
1691                 assert(is_ia32_fldz(node));
1692                 next = sched_next(n);
1693                 sched_remove(n);
1694                 exchange(n, node);
1695                 sched_add_before(next, node);
1696
1697                 DB((dbg, LEVEL_1, "<<< %+F %s -> %s\n", node, op1->name,
1698                     arch_get_irn_register(sim->arch_env, node)->name));
1699                 return NO_NODE_ADDED;
1700         }
1701
1702         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1703
1704         if (is_vfp_live(arch_register_get_index(op1), live)) {
1705                 ir_node *pred = get_irn_n(n, 0);
1706
1707                 /* Operand is still live, a real copy. We need here an fpush that can
1708                    hold a a register, so use the fpushCopy or recreate constants */
1709                 node = create_Copy(state, n);
1710
1711                 /* We have to make sure the old value doesn't go dead (which can happen
1712                  * when we recreate constants). As the simulator expected that value in
1713                  * the pred blocks. This is unfortunate as removing it would save us 1
1714                  * instruction, but we would have to rerun all the simulation to get
1715                  * this correct...
1716                  */
1717                 next = sched_next(n);
1718                 sched_remove(n);
1719                 exchange(n, node);
1720                 sched_add_before(next, node);
1721
1722                 if(get_irn_n_edges(pred) == 0) {
1723                         keep_float_node_alive(state, pred);
1724                 }
1725
1726                 DB((dbg, LEVEL_1, "<<< %+F %s -> %s\n", node, op1->name,
1727                     arch_get_irn_register(sim->arch_env, node)->name));
1728         } else {
1729                 out_idx = x87_on_stack(state, arch_register_get_index(out));
1730
1731                 if (out_idx >= 0 && out_idx != op1_idx) {
1732                         /* Matze: out already on stack? how can this happen? */
1733                         assert(0);
1734
1735                         /* op1 must be killed and placed where out is */
1736                         if (out_idx == 0) {
1737                                 /* best case, simple remove and rename */
1738                                 x87_patch_insn(n, op_ia32_Pop);
1739                                 attr = get_ia32_x87_attr(n);
1740                                 attr->x87[0] = op1 = &ia32_st_regs[0];
1741
1742                                 x87_pop(state);
1743                                 x87_set_st(state, arch_register_get_index(out), n, op1_idx - 1);
1744                         } else {
1745                                 /* move op1 to tos, store and pop it */
1746                                 if (op1_idx != 0) {
1747                                         x87_create_fxch(state, n, op1_idx);
1748                                         op1_idx = 0;
1749                                 }
1750                                 x87_patch_insn(n, op_ia32_Pop);
1751                                 attr = get_ia32_x87_attr(n);
1752                                 attr->x87[0] = op1 = &ia32_st_regs[out_idx];
1753
1754                                 x87_pop(state);
1755                                 x87_set_st(state, arch_register_get_index(out), n, out_idx - 1);
1756                         }
1757                         DB((dbg, LEVEL_1, "<<< %+F %s\n", n, op1->name));
1758                 } else {
1759                         /* just a virtual copy */
1760                         x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx);
1761                         /* don't remove the node to keep the verifier quiet :),
1762                            the emitter won't emit any code for the node */
1763 #if 0
1764                         sched_remove(n);
1765                         DB((dbg, LEVEL_1, "<<< KILLED %s\n", get_irn_opname(n)));
1766                         exchange(n, get_unop_op(n));
1767 #endif
1768                 }
1769         }
1770         return NO_NODE_ADDED;
1771 }  /* sim_Copy */
1772
1773 /**
1774  * Returns the result proj of the call
1775  */
1776 static ir_node *get_call_result_proj(ir_node *call) {
1777         const ir_edge_t *edge;
1778
1779         /* search the result proj */
1780         foreach_out_edge(call, edge) {
1781                 ir_node *proj = get_edge_src_irn(edge);
1782                 long pn = get_Proj_proj(proj);
1783
1784                 if (pn == pn_be_Call_first_res) {
1785                         return proj;
1786                 }
1787         }
1788
1789         return NULL;
1790 }  /* get_call_result_proj */
1791
1792 /**
1793  * Simulate a be_Call.
1794  *
1795  * @param state      the x87 state
1796  * @param n          the node that should be simulated
1797  * @param arch_env   the architecture environment
1798  *
1799  * @return NO_NODE_ADDED
1800  */
1801 static int sim_Call(x87_state *state, ir_node *n, const arch_env_t *arch_env)
1802 {
1803         ir_type *call_tp = be_Call_get_type(n);
1804         ir_type *res_type;
1805         ir_mode *mode;
1806         ir_node *resproj;
1807         const arch_register_t *reg;
1808         (void) arch_env;
1809
1810         DB((dbg, LEVEL_1, ">>> %+F\n", n));
1811
1812         /* at the begin of a call the x87 state should be empty */
1813         assert(state->depth == 0 && "stack not empty before call");
1814
1815         if (get_method_n_ress(call_tp) <= 0)
1816                 goto end_call;
1817
1818         /*
1819          * If the called function returns a float, it is returned in st(0).
1820          * This even happens if the return value is NOT used.
1821          * Moreover, only one return result is supported.
1822          */
1823         res_type = get_method_res_type(call_tp, 0);
1824         mode     = get_type_mode(res_type);
1825
1826         if (mode == NULL || !mode_is_float(mode))
1827                 goto end_call;
1828
1829         resproj = get_call_result_proj(n);
1830         assert(resproj != NULL);
1831
1832         reg = x87_get_irn_register(state->sim, resproj);
1833         x87_push(state, arch_register_get_index(reg), resproj);
1834
1835 end_call:
1836         DB((dbg, LEVEL_1, "Stack after: "));
1837         DEBUG_ONLY(x87_dump_stack(state));
1838
1839         return NO_NODE_ADDED;
1840 }  /* sim_Call */
1841
1842 /**
1843  * Simulate a be_Spill.
1844  *
1845  * @param state  the x87 state
1846  * @param n      the node that should be simulated (and patched)
1847  *
1848  * Should not happen, spills are lowered before x87 simulator see them.
1849  */
1850 static int sim_Spill(x87_state *state, ir_node *n) {
1851         assert(0 && "Spill not lowered");
1852         return sim_fst(state, n);
1853 }  /* sim_Spill */
1854
1855 /**
1856  * Simulate a be_Reload.
1857  *
1858  * @param state  the x87 state
1859  * @param n      the node that should be simulated (and patched)
1860  *
1861  * Should not happen, reloads are lowered before x87 simulator see them.
1862  */
1863 static int sim_Reload(x87_state *state, ir_node *n) {
1864         assert(0 && "Reload not lowered");
1865         return sim_fld(state, n);
1866 }  /* sim_Reload */
1867
1868 /**
1869  * Simulate a be_Return.
1870  *
1871  * @param state  the x87 state
1872  * @param n      the node that should be simulated (and patched)
1873  *
1874  * @return NO_NODE_ADDED
1875  */
1876 static int sim_Return(x87_state *state, ir_node *n) {
1877         int n_res = be_Return_get_n_rets(n);
1878         int i, n_float_res = 0;
1879
1880         /* only floating point return values must resist on stack */
1881         for (i = 0; i < n_res; ++i) {
1882                 ir_node *res = get_irn_n(n, be_pos_Return_val + i);
1883
1884                 if (mode_is_float(get_irn_mode(res)))
1885                         ++n_float_res;
1886         }
1887         assert(x87_get_depth(state) == n_float_res);
1888
1889         /* pop them virtually */
1890         for (i = n_float_res - 1; i >= 0; --i)
1891                 x87_pop(state);
1892
1893         return NO_NODE_ADDED;
1894 }  /* sim_Return */
1895
1896 typedef struct _perm_data_t {
1897         const arch_register_t *in;
1898         const arch_register_t *out;
1899 } perm_data_t;
1900
1901 /**
1902  * Simulate a be_Perm.
1903  *
1904  * @param state  the x87 state
1905  * @param irn    the node that should be simulated (and patched)
1906  *
1907  * @return NO_NODE_ADDED
1908  */
1909 static int sim_Perm(x87_state *state, ir_node *irn) {
1910         int             i, n;
1911         x87_simulator   *sim = state->sim;
1912         ir_node         *pred = get_irn_n(irn, 0);
1913         int             *stack_pos;
1914         const ir_edge_t *edge;
1915
1916         /* handle only floating point Perms */
1917         if (! mode_is_float(get_irn_mode(pred)))
1918                 return NO_NODE_ADDED;
1919
1920         DB((dbg, LEVEL_1, ">>> %+F\n", irn));
1921
1922         /* Perm is a pure virtual instruction on x87.
1923            All inputs must be on the FPU stack and are pairwise
1924            different from each other.
1925            So, all we need to do is to permutate the stack state. */
1926         n = get_irn_arity(irn);
1927         NEW_ARR_A(int, stack_pos, n);
1928
1929         /* collect old stack positions */
1930         for (i = 0; i < n; ++i) {
1931                 const arch_register_t *inreg = x87_get_irn_register(sim, get_irn_n(irn, i));
1932                 int idx = x87_on_stack(state, arch_register_get_index(inreg));
1933
1934                 assert(idx >= 0 && "Perm argument not on x87 stack");
1935
1936                 stack_pos[i] = idx;
1937         }
1938         /* now do the permutation */
1939         foreach_out_edge(irn, edge) {
1940                 ir_node               *proj = get_edge_src_irn(edge);
1941                 const arch_register_t *out  = x87_get_irn_register(sim, proj);
1942                 long                  num   = get_Proj_proj(proj);
1943
1944                 assert(0 <= num && num < n && "More Proj's than Perm inputs");
1945                 x87_set_st(state, arch_register_get_index(out), proj, stack_pos[(unsigned)num]);
1946         }
1947         DB((dbg, LEVEL_1, "<<< %+F\n", irn));
1948
1949         return NO_NODE_ADDED;
1950 }  /* sim_Perm */
1951
1952 static int sim_Barrier(x87_state *state, ir_node *node) {
1953         //const arch_env_t *arch_env = state->sim->arch_env;
1954         int i, arity;
1955
1956         /* materialize unknown if needed */
1957         arity = get_irn_arity(node);
1958         for(i = 0; i < arity; ++i) {
1959                 const arch_register_t       *reg;
1960                 ir_node                     *zero;
1961                 ir_node                     *block;
1962                 ia32_x87_attr_t             *attr;
1963                 ir_node                     *in    = get_irn_n(node, i);
1964
1965                 if(!is_ia32_Unknown_VFP(in))
1966                         continue;
1967
1968                 /* TODO: not completely correct... */
1969                 reg = &ia32_vfp_regs[REG_VFP_UKNWN];
1970
1971                 /* create a zero */
1972                 block = get_nodes_block(node);
1973                 zero  = new_rd_ia32_fldz(NULL, current_ir_graph, block, mode_E);
1974                 x87_push(state, arch_register_get_index(reg), zero);
1975
1976                 attr = get_ia32_x87_attr(zero);
1977                 attr->x87[2] = &ia32_st_regs[0];
1978
1979                 sched_add_before(node, zero);
1980
1981                 set_irn_n(node, i, zero);
1982         }
1983
1984         return NO_NODE_ADDED;
1985 }
1986
1987
1988 /**
1989  * Kill any dead registers at block start by popping them from the stack.
1990  *
1991  * @param sim          the simulator handle
1992  * @param block        the current block
1993  * @param start_state  the x87 state at the begin of the block
1994  *
1995  * @return the x87 state after dead register killed
1996  */
1997 static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state *start_state) {
1998         x87_state *state = start_state;
1999         ir_node *first_insn = sched_first(block);
2000         ir_node *keep = NULL;
2001         unsigned live = vfp_live_args_after(sim, block, 0);
2002         unsigned kill_mask;
2003         int i, depth, num_pop;
2004
2005         kill_mask = 0;
2006         depth = x87_get_depth(state);
2007         for (i = depth - 1; i >= 0; --i) {
2008                 int reg = x87_get_st_reg(state, i);
2009
2010                 if (! is_vfp_live(reg, live))
2011                         kill_mask |= (1 << i);
2012         }
2013
2014         if (kill_mask) {
2015                 /* create a new state, will be changed */
2016                 state = x87_clone_state(sim, state);
2017
2018                 DB((dbg, LEVEL_1, "Killing deads:\n"));
2019                 DEBUG_ONLY(vfp_dump_live(live));
2020                 DEBUG_ONLY(x87_dump_stack(state));
2021
2022                 /* now kill registers */
2023                 while (kill_mask) {
2024                         /* we can only kill from TOS, so bring them up */
2025                         if (! (kill_mask & 1)) {
2026                                 /* search from behind, because we can to a double-pop */
2027                                 for (i = depth - 1; i >= 0; --i) {
2028                                         if (kill_mask & (1 << i)) {
2029                                                 kill_mask &= ~(1 << i);
2030                                                 kill_mask |= 1;
2031                                                 break;
2032                                         }
2033                                 }
2034
2035                                 if (keep)
2036                                         x87_set_st(state, -1, keep, i);
2037                                 x87_create_fxch(state, first_insn, i);
2038                         }
2039
2040                         if ((kill_mask & 3) == 3) {
2041                                 /* we can do a double-pop */
2042                                 num_pop = 2;
2043                         }
2044                         else {
2045                                 /* only a single pop */
2046                                 num_pop = 1;
2047                         }
2048
2049                         depth -= num_pop;
2050                         kill_mask >>= num_pop;
2051                         keep = x87_create_fpop(state, first_insn, num_pop);
2052                 }
2053                 keep_alive(keep);
2054         }
2055         return state;
2056 }  /* x87_kill_deads */
2057
2058 /**
2059  * If we have PhiEs with unknown operands then we have to make sure that some
2060  * value is actually put onto the stack.
2061  */
2062 static void fix_unknown_phis(x87_state *state, ir_node *block,
2063                              ir_node *pred_block, int pos)
2064 {
2065         ir_node *node, *op;
2066
2067         sched_foreach(block, node) {
2068                 ir_node               *zero;
2069                 const arch_register_t *reg;
2070                 ia32_x87_attr_t       *attr;
2071
2072                 if(!is_Phi(node))
2073                         break;
2074
2075                 op = get_Phi_pred(node, pos);
2076                 if(!is_ia32_Unknown_VFP(op))
2077                         continue;
2078
2079                 reg = arch_get_irn_register(state->sim->arch_env, node);
2080
2081                 /* create a zero at end of pred block */
2082                 zero = new_rd_ia32_fldz(NULL, current_ir_graph, pred_block, mode_E);
2083                 x87_push(state, arch_register_get_index(reg), zero);
2084
2085                 attr = get_ia32_x87_attr(zero);
2086                 attr->x87[2] = &ia32_st_regs[0];
2087
2088                 assert(is_ia32_fldz(zero));
2089                 sched_add_before(sched_last(pred_block), zero);
2090
2091                 set_Phi_pred(node, pos, zero);
2092         }
2093 }
2094
2095 /**
2096  * Run a simulation and fix all virtual instructions for a block.
2097  *
2098  * @param sim          the simulator handle
2099  * @param block        the current block
2100  */
2101 static void x87_simulate_block(x87_simulator *sim, ir_node *block) {
2102         ir_node *n, *next;
2103         blk_state *bl_state = x87_get_bl_state(sim, block);
2104         x87_state *state = bl_state->begin;
2105         const ir_edge_t *edge;
2106         ir_node *start_block;
2107
2108         assert(state != NULL);
2109         /* already processed? */
2110         if (bl_state->end != NULL)
2111                 return;
2112
2113         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
2114         DB((dbg, LEVEL_2, "State at Block begin:\n "));
2115         DEBUG_ONLY(x87_dump_stack(state));
2116
2117         /* at block begin, kill all dead registers */
2118         state = x87_kill_deads(sim, block, state);
2119         /* create a new state, will be changed */
2120         state = x87_clone_state(sim, state);
2121
2122         /* beware, n might change */
2123         for (n = sched_first(block); !sched_is_end(n); n = next) {
2124                 int node_inserted;
2125                 sim_func func;
2126                 ir_op *op = get_irn_op(n);
2127
2128                 next = sched_next(n);
2129                 if (op->ops.generic == NULL)
2130                         continue;
2131
2132                 func = (sim_func)op->ops.generic;
2133
2134                 /* simulate it */
2135                 node_inserted = (*func)(state, n);
2136
2137                 /*
2138                         sim_func might have added an additional node after n,
2139                         so update next node
2140                         beware: n must not be changed by sim_func
2141                         (i.e. removed from schedule) in this case
2142                 */
2143                 if (node_inserted != NO_NODE_ADDED)
2144                         next = sched_next(n);
2145         }
2146
2147         start_block = get_irg_start_block(get_irn_irg(block));
2148
2149         DB((dbg, LEVEL_2, "State at Block end:\n ")); DEBUG_ONLY(x87_dump_stack(state));
2150
2151         /* check if the state must be shuffled */
2152         foreach_block_succ(block, edge) {
2153                 ir_node *succ = get_edge_src_irn(edge);
2154                 blk_state *succ_state;
2155
2156                 if (succ == start_block)
2157                         continue;
2158
2159                 succ_state = x87_get_bl_state(sim, succ);
2160
2161                 fix_unknown_phis(state, succ, block, get_edge_src_pos(edge));
2162
2163                 if (succ_state->begin == NULL) {
2164                         DB((dbg, LEVEL_2, "Set begin state for succ %+F:\n", succ));
2165                         DEBUG_ONLY(x87_dump_stack(state));
2166                         succ_state->begin = state;
2167
2168                         waitq_put(sim->worklist, succ);
2169                 } else {
2170                         DB((dbg, LEVEL_2, "succ %+F already has a state, shuffling\n", succ));
2171                         /* There is already a begin state for the successor, bad.
2172                            Do the necessary permutations.
2173                            Note that critical edges are removed, so this is always possible:
2174                            If the successor has more than one possible input, then it must
2175                            be the only one.
2176                          */
2177                         x87_shuffle(sim, block, state, succ, succ_state->begin);
2178                 }
2179         }
2180         bl_state->end = state;
2181 }  /* x87_simulate_block */
2182
2183 /**
2184  * Create a new x87 simulator.
2185  *
2186  * @param sim       a simulator handle, will be initialized
2187  * @param irg       the current graph
2188  * @param arch_env  the architecture environment
2189  */
2190 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg,
2191                                const arch_env_t *arch_env)
2192 {
2193         obstack_init(&sim->obst);
2194         sim->blk_states = pmap_create();
2195         sim->arch_env   = arch_env;
2196         sim->n_idx      = get_irg_last_idx(irg);
2197         sim->live       = obstack_alloc(&sim->obst, sizeof(*sim->live) * sim->n_idx);
2198
2199         DB((dbg, LEVEL_1, "--------------------------------\n"
2200                 "x87 Simulator started for %+F\n", irg));
2201
2202         /* set the generic function pointer of instruction we must simulate */
2203         clear_irp_opcodes_generic_func();
2204
2205 #define ASSOC(op)       (op_ ## op)->ops.generic = (op_func)(sim_##op)
2206 #define ASSOC_IA32(op)  (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
2207 #define ASSOC_BE(op)    (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
2208         ASSOC_IA32(fld);
2209         ASSOC_IA32(fild);
2210         ASSOC_IA32(fld1);
2211         ASSOC_IA32(fldz);
2212         ASSOC_IA32(fadd);
2213         ASSOC_IA32(fsub);
2214         ASSOC_IA32(fmul);
2215         ASSOC_IA32(fdiv);
2216         ASSOC_IA32(fprem);
2217         ASSOC_IA32(fabs);
2218         ASSOC_IA32(fchs);
2219         ASSOC_IA32(fist);
2220         ASSOC_IA32(fst);
2221         ASSOC_IA32(fCondJmp);
2222         ASSOC_BE(Copy);
2223         ASSOC_BE(Call);
2224         ASSOC_BE(Spill);
2225         ASSOC_BE(Reload);
2226         ASSOC_BE(Return);
2227         ASSOC_BE(Perm);
2228         ASSOC_BE(Keep);
2229         ASSOC_BE(Barrier);
2230 #undef ASSOC_BE
2231 #undef ASSOC_IA32
2232 #undef ASSOC
2233 }  /* x87_init_simulator */
2234
2235 /**
2236  * Destroy a x87 simulator.
2237  *
2238  * @param sim  the simulator handle
2239  */
2240 static void x87_destroy_simulator(x87_simulator *sim) {
2241         pmap_destroy(sim->blk_states);
2242         obstack_free(&sim->obst, NULL);
2243         DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
2244 }  /* x87_destroy_simulator */
2245
2246 /**
2247  * Pre-block walker: calculate the liveness information for the block
2248  * and store it into the sim->live cache.
2249  */
2250 static void update_liveness_walker(ir_node *block, void *data) {
2251         x87_simulator *sim = data;
2252         update_liveness(sim, block);
2253 }  /* update_liveness_walker */
2254
2255 /**
2256  * Run a simulation and fix all virtual instructions for a graph.
2257  *
2258  * @param env       the architecture environment
2259  * @param irg       the current graph
2260  *
2261  * Needs a block-schedule.
2262  */
2263 void x87_simulate_graph(const arch_env_t *arch_env, be_irg_t *birg) {
2264         ir_node       *block, *start_block;
2265         blk_state     *bl_state;
2266         x87_simulator sim;
2267         ir_graph      *irg = be_get_birg_irg(birg);
2268
2269         /* create the simulator */
2270         x87_init_simulator(&sim, irg, arch_env);
2271
2272         start_block = get_irg_start_block(irg);
2273         bl_state    = x87_get_bl_state(&sim, start_block);
2274
2275         /* start with the empty state */
2276         bl_state->begin = empty;
2277         empty->sim      = &sim;
2278
2279         sim.worklist = new_waitq();
2280         waitq_put(sim.worklist, start_block);
2281
2282         be_assure_liveness(birg);
2283         sim.lv = be_get_birg_liveness(birg);
2284 //      sim.lv = be_liveness(be_get_birg_irg(birg));
2285         be_liveness_assure_sets(sim.lv);
2286
2287         /* Calculate the liveness for all nodes. We must precalculate this info,
2288          * because the simulator adds new nodes (possible before Phi nodes) which
2289          * would let a lazy calculation fail.
2290          * On the other hand we reduce the computation amount due to
2291          * precaching from O(n^2) to O(n) at the expense of O(n) cache memory.
2292          */
2293         irg_block_walk_graph(irg, update_liveness_walker, NULL, &sim);
2294
2295         /* iterate */
2296         do {
2297                 block = waitq_get(sim.worklist);
2298                 x87_simulate_block(&sim, block);
2299         } while (! waitq_empty(sim.worklist));
2300
2301         /* kill it */
2302         del_waitq(sim.worklist);
2303         x87_destroy_simulator(&sim);
2304 }  /* x87_simulate_graph */
2305
2306 void ia32_init_x87(void) {
2307         FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
2308 }  /* ia32_init_x87 */