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

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