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 N_x87_REGS 8
  57
  58 /* the unop index */
  59 #define UNOP_IDX 0
  60
  61 #define MASK_TOS(x)    ((x) & (N_x87_REGS - 1))
  62
  63 /** the debug handle */
  64 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  65
  66 /* Forward declaration. */
  67 typedef struct x87_simulator x87_simulator;
  68
  69 /**
  70  * An exchange template.
  71  * Note that our virtual functions have the same inputs
  72  * and attributes as the real ones, so we can simple exchange
  73  * their opcodes!
  74  * Further, x87 supports inverse instructions, so we can handle them.
  75  */
  76 typedef struct exchange_tmpl {
  77         ir_op *normal_op;       /**< the normal one */
  78         ir_op *reverse_op;      /**< the reverse one if exists */
  79         ir_op *normal_pop_op;   /**< the normal one with tos pop */
  80         ir_op *reverse_pop_op;  /**< the reverse one with tos pop */
  81 } exchange_tmpl;
  82
  83 /**
  84  * An entry on the simulated x87 stack.
  85  */
  86 typedef struct st_entry {
  87         int     reg_idx;        /**< the virtual register index of this stack value */
  88         ir_node *node;          /**< the node that produced this value */
  89 } st_entry;
  90
  91 /**
  92  * The x87 state.
  93  */
  94 typedef struct x87_state {
  95         st_entry st[N_x87_REGS];  /**< the register stack */
  96         int depth;                /**< the current stack depth */
  97         int tos;                  /**< position of the tos */
  98         x87_simulator *sim;       /**< The simulator. */
  99 } x87_state;
 100
 101 /** An empty state, used for blocks without fp instructions. */
 102 static x87_state _empty = { { {0, NULL}, }, 0, 0, NULL };
 103 static x87_state *empty = (x87_state *)&_empty;
 104
 105 /**
 106  * Return values of the instruction simulator functions.
 107  */
 108 enum {
 109         NO_NODE_ADDED = 0,  /**< No node that needs simulation was added. */
 110         NODE_ADDED    = 1   /**< A node that must be simulated was added by the simulator
 111                                  in the schedule AFTER the current node. */
 112 };
 113
 114 /**
 115  * The type of an instruction simulator function.
 116  *
 117  * @param state  the x87 state
 118  * @param n      the node to be simulated
 119  *
 120  * @return NODE_ADDED    if a node was added AFTER n in schedule that MUST be
 121  *                       simulated further
 122  *         NO_NODE_ADDED otherwise
 123  */
 124 typedef int (*sim_func)(x87_state *state, ir_node *n);
 125
 126 /**
 127  * A block state: Every block has a x87 state at the beginning and at the end.
 128  */
 129 typedef struct blk_state {
 130         x87_state *begin;   /**< state at the begin or NULL if not assigned */
 131         x87_state *end;     /**< state at the end or NULL if not assigned */
 132 } blk_state;
 133
 134 #define PTR_TO_BLKSTATE(p)    ((blk_state *)(p))
 135
 136 /** liveness bitset for vfp registers. */
 137 typedef unsigned char vfp_liveness;
 138
 139 /**
 140  * The x87 simulator.
 141  */
 142 struct x87_simulator {
 143         struct obstack obst;        /**< An obstack for fast allocating. */
 144         pmap *blk_states;           /**< Map blocks to states. */
 145         be_lv_t *lv;                /**< intrablock liveness. */
 146         vfp_liveness *live;         /**< Liveness information. */
 147         unsigned n_idx;             /**< The cached get_irg_last_idx() result. */
 148         waitq *worklist;            /**< Worklist of blocks that must be processed. */
 149         ia32_isa_t *isa;            /**< the ISA object */
 150 };
 151
 152 /**
 153  * Returns the current stack depth.
 154  *
 155  * @param state  the x87 state
 156  *
 157  * @return the x87 stack depth
 158  */
 159 static int x87_get_depth(const x87_state *state)
 160 {
 161         return state->depth;
 162 }  /* x87_get_depth */
 163
 164 /**
 165  * Return the virtual register index at st(pos).
 166  *
 167  * @param state  the x87 state
 168  * @param pos    a stack position
 169  *
 170  * @return the vfp register index that produced the value at st(pos)
 171  */
 172 static int x87_get_st_reg(const x87_state *state, int pos)
 173 {
 174         assert(pos < state->depth);
 175         return state->st[MASK_TOS(state->tos + pos)].reg_idx;
 176 }  /* x87_get_st_reg */
 177
 178 #ifdef DEBUG_libfirm
 179 /**
 180  * Return the node at st(pos).
 181  *
 182  * @param state  the x87 state
 183  * @param pos    a stack position
 184  *
 185  * @return the IR node that produced the value at st(pos)
 186  */
 187 static ir_node *x87_get_st_node(const x87_state *state, int pos)
 188 {
 189         assert(pos < state->depth);
 190         return state->st[MASK_TOS(state->tos + pos)].node;
 191 }  /* x87_get_st_node */
 192
 193 /**
 194  * Dump the stack for debugging.
 195  *
 196  * @param state  the x87 state
 197  */
 198 static void x87_dump_stack(const x87_state *state)
 199 {
 200         int i;
 201
 202         for (i = state->depth - 1; i >= 0; --i) {
 203                 DB((dbg, LEVEL_2, "vf%d(%+F) ", x87_get_st_reg(state, i),
 204                     x87_get_st_node(state, i)));
 205         }
 206         DB((dbg, LEVEL_2, "<-- TOS\n"));
 207 }  /* x87_dump_stack */
 208 #endif /* DEBUG_libfirm */
 209
 210 /**
 211  * Set a virtual register to st(pos).
 212  *
 213  * @param state    the x87 state
 214  * @param reg_idx  the vfp register index that should be set
 215  * @param node     the IR node that produces the value of the vfp register
 216  * @param pos      the stack position where the new value should be entered
 217  */
 218 static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos)
 219 {
 220         assert(0 < state->depth);
 221         state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx;
 222         state->st[MASK_TOS(state->tos + pos)].node    = node;
 223
 224         DB((dbg, LEVEL_2, "After SET_REG: "));
 225         DEBUG_ONLY(x87_dump_stack(state));
 226 }  /* x87_set_st */
 227
 228 /**
 229  * Set the tos virtual register.
 230  *
 231  * @param state    the x87 state
 232  * @param reg_idx  the vfp register index that should be set
 233  * @param node     the IR node that produces the value of the vfp register
 234  */
 235 static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node)
 236 {
 237         x87_set_st(state, reg_idx, node, 0);
 238 }  /* x87_set_tos */
 239
 240 /**
 241  * Swap st(0) with st(pos).
 242  *
 243  * @param state    the x87 state
 244  * @param pos      the stack position to change the tos with
 245  */
 246 static void x87_fxch(x87_state *state, int pos)
 247 {
 248         st_entry entry;
 249         assert(pos < state->depth);
 250
 251         entry = state->st[MASK_TOS(state->tos + pos)];
 252         state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
 253         state->st[MASK_TOS(state->tos)] = entry;
 254
 255         DB((dbg, LEVEL_2, "After FXCH: ")); DEBUG_ONLY(x87_dump_stack(state));
 256 }  /* x87_fxch */
 257
 258 /**
 259  * Convert a virtual register to the stack index.
 260  *
 261  * @param state    the x87 state
 262  * @param reg_idx  the register vfp index
 263  *
 264  * @return the stack position where the register is stacked
 265  *         or -1 if the virtual register was not found
 266  */
 267 static int x87_on_stack(const x87_state *state, int reg_idx)
 268 {
 269         int i, tos = state->tos;
 270
 271         for (i = 0; i < state->depth; ++i)
 272                 if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx)
 273                         return i;
 274         return -1;
 275 }  /* x87_on_stack */
 276
 277 /**
 278  * Push a virtual Register onto the stack, double pushed allowed.
 279  *
 280  * @param state     the x87 state
 281  * @param reg_idx   the register vfp index
 282  * @param node      the node that produces the value of the vfp register
 283  */
 284 static void x87_push_dbl(x87_state *state, int reg_idx, ir_node *node)
 285 {
 286         assert(state->depth < N_x87_REGS && "stack overrun");
 287
 288         ++state->depth;
 289         state->tos = MASK_TOS(state->tos - 1);
 290         state->st[state->tos].reg_idx = reg_idx;
 291         state->st[state->tos].node    = node;
 292
 293         DB((dbg, LEVEL_2, "After PUSH: ")); DEBUG_ONLY(x87_dump_stack(state));
 294 }  /* x87_push_dbl */
 295
 296 /**
 297  * Push a virtual Register onto the stack, double pushes are NOT allowed.
 298  *
 299  * @param state     the x87 state
 300  * @param reg_idx   the register vfp index
 301  * @param node      the node that produces the value of the vfp register
 302  * @param dbl_push  if != 0 double pushes are allowed
 303  */
 304 static void x87_push(x87_state *state, int reg_idx, ir_node *node)
 305 {
 306         assert(x87_on_stack(state, reg_idx) == -1 && "double push");
 307
 308         x87_push_dbl(state, reg_idx, node);
 309 }  /* x87_push */
 310
 311 /**
 312  * Pop a virtual Register from the stack.
 313  *
 314  * @param state     the x87 state
 315  */
 316 static void x87_pop(x87_state *state)
 317 {
 318         assert(state->depth > 0 && "stack underrun");
 319
 320         --state->depth;
 321         state->tos = MASK_TOS(state->tos + 1);
 322
 323         DB((dbg, LEVEL_2, "After POP: ")); DEBUG_ONLY(x87_dump_stack(state));
 324 }  /* x87_pop */
 325
 326 /**
 327  * Empty the fpu stack
 328  *
 329  * @param state     the x87 state
 330  */
 331 static void x87_emms(x87_state *state)
 332 {
 333         state->depth = 0;
 334         state->tos   = 0;
 335 }
 336
 337 /**
 338  * Returns the block state of a block.
 339  *
 340  * @param sim    the x87 simulator handle
 341  * @param block  the current block
 342  *
 343  * @return the block state
 344  */
 345 static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block)
 346 {
 347         pmap_entry *entry = pmap_find(sim->blk_states, block);
 348
 349         if (! entry) {
 350                 blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
 351                 bl_state->begin = NULL;
 352                 bl_state->end   = NULL;
 353
 354                 pmap_insert(sim->blk_states, block, bl_state);
 355                 return bl_state;
 356         }
 357
 358         return PTR_TO_BLKSTATE(entry->value);
 359 }  /* x87_get_bl_state */
 360
 361 /**
 362  * Creates a new x87 state.
 363  *
 364  * @param sim    the x87 simulator handle
 365  *
 366  * @return a new x87 state
 367  */
 368 static x87_state *x87_alloc_state(x87_simulator *sim)
 369 {
 370         x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
 371
 372         res->sim = sim;
 373         return res;
 374 }  /* x87_alloc_state */
 375
 376 /**
 377  * Clone a x87 state.
 378  *
 379  * @param sim    the x87 simulator handle
 380  * @param src    the x87 state that will be cloned
 381  *
 382  * @return a cloned copy of the src state
 383  */
 384 static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src)
 385 {
 386         x87_state *res = x87_alloc_state(sim);
 387
 388         *res = *src;
 389         return res;
 390 }  /* x87_clone_state */
 391
 392 /**
 393  * Patch a virtual instruction into a x87 one and return
 394  * the node representing the result value.
 395  *
 396  * @param n   the IR node to patch
 397  * @param op  the x87 opcode to patch in
 398  */
 399 static ir_node *x87_patch_insn(ir_node *n, ir_op *op)
 400 {
 401         ir_mode *mode = get_irn_mode(n);
 402         ir_node *res = n;
 403
 404         set_irn_op(n, op);
 405
 406         if (mode == mode_T) {
 407                 /* patch all Proj's */
 408                 const ir_edge_t *edge;
 409
 410                 foreach_out_edge(n, edge) {
 411                         ir_node *proj = get_edge_src_irn(edge);
 412                         if (is_Proj(proj)) {
 413                                 mode = get_irn_mode(proj);
 414                                 if (mode_is_float(mode)) {
 415                                         res = proj;
 416                                         set_irn_mode(proj, ia32_reg_classes[CLASS_ia32_st].mode);
 417                                 }
 418                         }
 419                 }
 420         } else if (mode_is_float(mode))
 421                 set_irn_mode(n, ia32_reg_classes[CLASS_ia32_st].mode);
 422         return res;
 423 }  /* x87_patch_insn */
 424
 425 /**
 426  * Returns the first Proj of a mode_T node having a given mode.
 427  *
 428  * @param n  the mode_T node
 429  * @param m  the desired mode of the Proj
 430  * @return The first Proj of mode @p m found or NULL.
 431  */
 432 static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m)
 433 {
 434         const ir_edge_t *edge;
 435
 436         assert(get_irn_mode(n) == mode_T && "Need mode_T node");
 437
 438         foreach_out_edge(n, edge) {
 439                 ir_node *proj = get_edge_src_irn(edge);
 440                 if (get_irn_mode(proj) == m)
 441                         return proj;
 442         }
 443
 444         return NULL;
 445 }  /* get_irn_Proj_for_mode */
 446
 447 /**
 448  * Wrap the arch_* function here so we can check for errors.
 449  */
 450 static inline const arch_register_t *x87_get_irn_register(const ir_node *irn)
 451 {
 452         const arch_register_t *res = arch_get_irn_register(irn);
 453
 454         assert(res->reg_class->regs == ia32_vfp_regs);
 455         return res;
 456 }  /* x87_get_irn_register */
 457
 458 static inline const arch_register_t *x87_irn_get_register(const ir_node *irn,
 459                                                           int pos)
 460 {
 461         const arch_register_t *res = arch_irn_get_register(irn, pos);
 462
 463         assert(res->reg_class->regs == ia32_vfp_regs);
 464         return res;
 465 }  /* x87_irn_get_register */
 466
 467 /* -------------- x87 perm --------------- */
 468
 469 /**
 470  * Creates a fxch for shuffle.
 471  *
 472  * @param state     the x87 state
 473  * @param pos       parameter for fxch
 474  * @param block     the block were fxch is inserted
 475  *
 476  * Creates a new fxch node and reroute the user of the old node
 477  * to the fxch.
 478  *
 479  * @return the fxch node
 480  */
 481 static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block)
 482 {
 483         ir_node         *fxch;
 484         ia32_x87_attr_t *attr;
 485
 486         fxch = new_bd_ia32_fxch(NULL, block);
 487         attr = get_ia32_x87_attr(fxch);
 488         attr->x87[0] = &ia32_st_regs[pos];
 489         attr->x87[2] = &ia32_st_regs[0];
 490
 491         keep_alive(fxch);
 492
 493         x87_fxch(state, pos);
 494         return fxch;
 495 }  /* x87_fxch_shuffle */
 496
 497 /**
 498  * Calculate the necessary permutations to reach dst_state.
 499  *
 500  * These permutations are done with fxch instructions and placed
 501  * at the end of the block.
 502  *
 503  * Note that critical edges are removed here, so we need only
 504  * a shuffle if the current block has only one successor.
 505  *
 506  * @param sim        the simulator handle
 507  * @param block      the current block
 508  * @param state      the current x87 stack state, might be modified
 509  * @param dst_block  the destination block
 510  * @param dst_state  destination state
 511  *
 512  * @return state
 513  */
 514 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block,
 515                               x87_state *state, ir_node *dst_block,
 516                               const x87_state *dst_state)
 517 {
 518         int      i, n_cycles, k, ri;
 519         unsigned cycles[4], all_mask;
 520         char     cycle_idx[4][8];
 521         ir_node  *fxch, *before, *after;
 522         (void) sim;
 523         (void) dst_block;
 524
 525         assert(state->depth == dst_state->depth);
 526
 527         /* Some mathematics here:
 528            If we have a cycle of length n that includes the tos,
 529            we need n-1 exchange operations.
 530            We can always add the tos and restore it, so we need
 531            n+1 exchange operations for a cycle not containing the tos.
 532            So, the maximum of needed operations is for a cycle of 7
 533            not including the tos == 8.
 534            This is the same number of ops we would need for using stores,
 535            so exchange is cheaper (we save the loads).
 536            On the other hand, we might need an additional exchange
 537            in the next block to bring one operand on top, so the
 538            number of ops in the first case is identical.
 539            Further, no more than 4 cycles can exists (4 x 2).
 540         */
 541         all_mask = (1 << (state->depth)) - 1;
 542
 543         for (n_cycles = 0; all_mask; ++n_cycles) {
 544                 int src_idx, dst_idx;
 545
 546                 /* find the first free slot */
 547                 for (i = 0; i < state->depth; ++i) {
 548                         if (all_mask & (1 << i)) {
 549                                 all_mask &= ~(1 << i);
 550
 551                                 /* check if there are differences here */
 552                                 if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
 553                                         break;
 554                         }
 555                 }
 556
 557                 if (! all_mask) {
 558                         /* no more cycles found */
 559                         break;
 560                 }
 561
 562                 k = 0;
 563                 cycles[n_cycles] = (1 << i);
 564                 cycle_idx[n_cycles][k++] = i;
 565                 for (src_idx = i; ; src_idx = dst_idx) {
 566                         dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
 567
 568                         if ((all_mask & (1 << dst_idx)) == 0)
 569                                 break;
 570
 571                         cycle_idx[n_cycles][k++] = dst_idx;
 572                         cycles[n_cycles] |=  (1 << dst_idx);
 573                         all_mask       &= ~(1 << dst_idx);
 574                 }
 575                 cycle_idx[n_cycles][k] = -1;
 576         }
 577
 578         if (n_cycles <= 0) {
 579                 /* no permutation needed */
 580                 return state;
 581         }
 582
 583         /* Hmm: permutation needed */
 584         DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
 585         DEBUG_ONLY(x87_dump_stack(state));
 586         DB((dbg, LEVEL_2, "                  to\n"));
 587         DEBUG_ONLY(x87_dump_stack(dst_state));
 588
 589
 590 #ifdef DEBUG_libfirm
 591         DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
 592         for (ri = 0; ri < n_cycles; ++ri) {
 593                 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
 594                 for (k = 0; cycle_idx[ri][k] != -1; ++k)
 595                         DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
 596                 DB((dbg, LEVEL_2, "\n"));
 597         }
 598 #endif
 599
 600         after = NULL;
 601
 602         /*
 603          * Find the place node must be insert.
 604          * We have only one successor block, so the last instruction should
 605          * be a jump.
 606          */
 607         before = sched_last(block);
 608         assert(is_cfop(before));
 609
 610         /* now do the permutations */
 611         for (ri = 0; ri < n_cycles; ++ri) {
 612                 if ((cycles[ri] & 1) == 0) {
 613                         /* this cycle does not include the tos */
 614                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block);
 615                         if (after)
 616                                 sched_add_after(after, fxch);
 617                         else
 618                                 sched_add_before(before, fxch);
 619                         after = fxch;
 620                 }
 621                 for (k = 1; cycle_idx[ri][k] != -1; ++k) {
 622                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][k], block);
 623                         if (after)
 624                                 sched_add_after(after, fxch);
 625                         else
 626                                 sched_add_before(before, fxch);
 627                         after = fxch;
 628                 }
 629                 if ((cycles[ri] & 1) == 0) {
 630                         /* this cycle does not include the tos */
 631                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block);
 632                         sched_add_after(after, fxch);
 633                 }
 634         }
 635         return state;
 636 }  /* x87_shuffle */
 637
 638 /**
 639  * Create a fxch node before another node.
 640  *
 641  * @param state   the x87 state
 642  * @param n       the node after the fxch
 643  * @param pos     exchange st(pos) with st(0)
 644  *
 645  * @return the fxch
 646  */
 647 static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos)
 648 {
 649         ir_node         *fxch;
 650         ia32_x87_attr_t *attr;
 651         ir_node         *block = get_nodes_block(n);
 652
 653         x87_fxch(state, pos);
 654
 655         fxch = new_bd_ia32_fxch(NULL, block);
 656         attr = get_ia32_x87_attr(fxch);
 657         attr->x87[0] = &ia32_st_regs[pos];
 658         attr->x87[2] = &ia32_st_regs[0];
 659
 660         keep_alive(fxch);
 661
 662         sched_add_before(n, fxch);
 663         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
 664         return fxch;
 665 }  /* x87_create_fxch */
 666
 667 /**
 668  * Create a fpush before node n.
 669  *
 670  * @param state     the x87 state
 671  * @param n         the node after the fpush
 672  * @param pos       push st(pos) on stack
 673  * @param op_idx    replace input op_idx of n with the fpush result
 674  */
 675 static void x87_create_fpush(x87_state *state, ir_node *n, int pos, int op_idx)
 676 {
 677         ir_node               *fpush, *pred = get_irn_n(n, op_idx);
 678         ia32_x87_attr_t       *attr;
 679         const arch_register_t *out = x87_get_irn_register(pred);
 680
 681         x87_push_dbl(state, arch_register_get_index(out), pred);
 682
 683         fpush = new_bd_ia32_fpush(NULL, get_nodes_block(n));
 684         attr  = get_ia32_x87_attr(fpush);
 685         attr->x87[0] = &ia32_st_regs[pos];
 686         attr->x87[2] = &ia32_st_regs[0];
 687
 688         keep_alive(fpush);
 689         sched_add_before(n, fpush);
 690
 691         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
 692 }  /* x87_create_fpush */
 693
 694 /**
 695  * Create a fpop before node n.
 696  *
 697  * @param state   the x87 state
 698  * @param n       the node after the fpop
 699  * @param num     pop 1 or 2 values
 700  *
 701  * @return the fpop node
 702  */
 703 static ir_node *x87_create_fpop(x87_state *state, ir_node *n, int num)
 704 {
 705         ir_node         *fpop = NULL;
 706         ia32_x87_attr_t *attr;
 707
 708         assert(num > 0);
 709         while (num > 0) {
 710                 x87_pop(state);
 711                 if (ia32_cg_config.use_ffreep)
 712                         fpop = new_bd_ia32_ffreep(NULL, get_nodes_block(n));
 713                 else
 714                         fpop = new_bd_ia32_fpop(NULL, get_nodes_block(n));
 715                 attr = get_ia32_x87_attr(fpop);
 716                 attr->x87[0] = &ia32_st_regs[0];
 717                 attr->x87[1] = &ia32_st_regs[0];
 718                 attr->x87[2] = &ia32_st_regs[0];
 719
 720                 keep_alive(fpop);
 721                 sched_add_before(n, fpop);
 722                 DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->x87[0]->name));
 723
 724                 --num;
 725         }
 726         return fpop;
 727 }  /* x87_create_fpop */
 728
 729 /* --------------------------------- liveness ------------------------------------------ */
 730
 731 /**
 732  * The liveness transfer function.
 733  * Updates a live set over a single step from a given node to its predecessor.
 734  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 735  *
 736  * @param irn      The node at which liveness should be computed.
 737  * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 738  *                 the registers live after irn.
 739  *
 740  * @return The live bitset.
 741  */
 742 static vfp_liveness vfp_liveness_transfer(ir_node *irn, vfp_liveness live)
 743 {
 744         int i, n;
 745         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 746
 747         if (get_irn_mode(irn) == mode_T) {
 748                 const ir_edge_t *edge;
 749
 750                 foreach_out_edge(irn, edge) {
 751                         ir_node *proj = get_edge_src_irn(edge);
 752
 753                         if (arch_irn_consider_in_reg_alloc(cls, proj)) {
 754                                 const arch_register_t *reg = x87_get_irn_register(proj);
 755                                 live &= ~(1 << arch_register_get_index(reg));
 756                         }
 757                 }
 758         } else if (arch_irn_consider_in_reg_alloc(cls, irn)) {
 759                 const arch_register_t *reg = x87_get_irn_register(irn);
 760                 live &= ~(1 << arch_register_get_index(reg));
 761         }
 762
 763         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 764                 ir_node *op = get_irn_n(irn, i);
 765
 766                 if (mode_is_float(get_irn_mode(op)) &&
 767                                 arch_irn_consider_in_reg_alloc(cls, op)) {
 768                         const arch_register_t *reg = x87_get_irn_register(op);
 769                         live |= 1 << arch_register_get_index(reg);
 770                 }
 771         }
 772         return live;
 773 }  /* vfp_liveness_transfer */
 774
 775 /**
 776  * Put all live virtual registers at the end of a block into a bitset.
 777  *
 778  * @param sim      the simulator handle
 779  * @param lv       the liveness information
 780  * @param bl       the block
 781  *
 782  * @return The live bitset at the end of this block
 783  */
 784 static vfp_liveness vfp_liveness_end_of_block(x87_simulator *sim, const ir_node *block)
 785 {
 786         int i;
 787         vfp_liveness live = 0;
 788         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 789         const be_lv_t *lv = sim->lv;
 790
 791         be_lv_foreach(lv, block, be_lv_state_end, i) {
 792                 const arch_register_t *reg;
 793                 const ir_node *node = be_lv_get_irn(lv, block, i);
 794                 if (!arch_irn_consider_in_reg_alloc(cls, node))
 795                         continue;
 796
 797                 reg = x87_get_irn_register(node);
 798                 live |= 1 << arch_register_get_index(reg);
 799         }
 800
 801         return live;
 802 }  /* vfp_liveness_end_of_block */
 803
 804 /** get the register mask from an arch_register */
 805 #define REGMASK(reg)    (1 << (arch_register_get_index(reg)))
 806
 807 /**
 808  * Return a bitset of argument registers which are live at the end of a node.
 809  *
 810  * @param sim    the simulator handle
 811  * @param pos    the node
 812  * @param kill   kill mask for the output registers
 813  *
 814  * @return The live bitset.
 815  */
 816 static unsigned vfp_live_args_after(x87_simulator *sim, const ir_node *pos, unsigned kill)
 817 {
 818         unsigned idx = get_irn_idx(pos);
 819
 820         assert(idx < sim->n_idx);
 821         return sim->live[idx] & ~kill;
 822 }  /* vfp_live_args_after */
 823
 824 /**
 825  * Calculate the liveness for a whole block and cache it.
 826  *
 827  * @param sim   the simulator handle
 828  * @param lv    the liveness handle
 829  * @param block the block
 830  */
 831 static void update_liveness(x87_simulator *sim, ir_node *block)
 832 {
 833         vfp_liveness live = vfp_liveness_end_of_block(sim, block);
 834         unsigned idx;
 835         ir_node *irn;
 836
 837         /* now iterate through the block backward and cache the results */
 838         sched_foreach_reverse(block, irn) {
 839                 /* stop at the first Phi: this produces the live-in */
 840                 if (is_Phi(irn))
 841                         break;
 842
 843                 idx = get_irn_idx(irn);
 844                 sim->live[idx] = live;
 845
 846                 live = vfp_liveness_transfer(irn, live);
 847         }
 848         idx = get_irn_idx(block);
 849         sim->live[idx] = live;
 850 }  /* update_liveness */
 851
 852 /**
 853  * Returns true if a register is live in a set.
 854  *
 855  * @param reg_idx  the vfp register index
 856  * @param live     a live bitset
 857  */
 858 #define is_vfp_live(reg_idx, live) ((live) & (1 << (reg_idx)))
 859
 860 #ifdef DEBUG_libfirm
 861 /**
 862  * Dump liveness info.
 863  *
 864  * @param live  the live bitset
 865  */
 866 static void vfp_dump_live(vfp_liveness live)
 867 {
 868         int i;
 869
 870         DB((dbg, LEVEL_2, "Live after: "));
 871         for (i = 0; i < 8; ++i) {
 872                 if (live & (1 << i)) {
 873                         DB((dbg, LEVEL_2, "vf%d ", i));
 874                 }
 875         }
 876         DB((dbg, LEVEL_2, "\n"));
 877 }  /* vfp_dump_live */
 878 #endif /* DEBUG_libfirm */
 879
 880 /* --------------------------------- simulators ---------------------------------------- */
 881
 882 /**
 883  * Simulate a virtual binop.
 884  *
 885  * @param state  the x87 state
 886  * @param n      the node that should be simulated (and patched)
 887  * @param tmpl   the template containing the 4 possible x87 opcodes
 888  *
 889  * @return NO_NODE_ADDED
 890  */
 891 static int sim_binop(x87_state *state, ir_node *n, const exchange_tmpl *tmpl)
 892 {
 893         int op2_idx = 0, op1_idx;
 894         int out_idx, do_pop = 0;
 895         ia32_x87_attr_t *attr;
 896         int permuted;
 897         ir_node *patched_insn;
 898         ir_op *dst;
 899         x87_simulator         *sim     = state->sim;
 900         ir_node               *op1     = get_irn_n(n, n_ia32_binary_left);
 901         ir_node               *op2     = get_irn_n(n, n_ia32_binary_right);
 902         const arch_register_t *op1_reg = x87_get_irn_register(op1);
 903         const arch_register_t *op2_reg = x87_get_irn_register(op2);
 904         const arch_register_t *out     = x87_irn_get_register(n, pn_ia32_res);
 905         int reg_index_1                = arch_register_get_index(op1_reg);
 906         int reg_index_2                = arch_register_get_index(op2_reg);
 907         vfp_liveness           live    = vfp_live_args_after(sim, n, REGMASK(out));
 908         int                    op1_live_after;
 909         int                    op2_live_after;
 910
 911         DB((dbg, LEVEL_1, ">>> %+F %s, %s -> %s\n", n,
 912                 arch_register_get_name(op1_reg), arch_register_get_name(op2_reg),
 913                 arch_register_get_name(out)));
 914         DEBUG_ONLY(vfp_dump_live(live));
 915         DB((dbg, LEVEL_1, "Stack before: "));
 916         DEBUG_ONLY(x87_dump_stack(state));
 917
 918         op1_idx = x87_on_stack(state, reg_index_1);
 919         assert(op1_idx >= 0);
 920         op1_live_after = is_vfp_live(arch_register_get_index(op1_reg), live);
 921
 922         attr     = get_ia32_x87_attr(n);
 923         permuted = attr->attr.data.ins_permuted;
 924
 925         if (reg_index_2 != REG_VFP_NOREG) {
 926                 assert(!permuted);
 927
 928                 /* second operand is a vfp register */
 929                 op2_idx = x87_on_stack(state, reg_index_2);
 930                 assert(op2_idx >= 0);
 931                 op2_live_after = is_vfp_live(arch_register_get_index(op2_reg), live);
 932
 933                 if (op2_live_after) {
 934                         /* Second operand is live. */
 935
 936                         if (op1_live_after) {
 937                                 /* Both operands are live: push the first one.
 938                                    This works even for op1 == op2. */
 939                                 x87_create_fpush(state, n, op1_idx, n_ia32_binary_right);
 940                                 /* now do fxxx (tos=tos X op) */
 941                                 op1_idx = 0;
 942                                 op2_idx += 1;
 943                                 out_idx = 0;
 944                                 dst = tmpl->normal_op;
 945                         } else {
 946                                 /* Second live, first operand is dead here, bring it to tos. */
 947                                 if (op1_idx != 0) {
 948                                         x87_create_fxch(state, n, op1_idx);
 949                                         if (op2_idx == 0)
 950                                                 op2_idx = op1_idx;
 951                                         op1_idx = 0;
 952                                 }
 953                                 /* now do fxxx (tos=tos X op) */
 954                                 out_idx = 0;
 955                                 dst = tmpl->normal_op;
 956                         }
 957                 } else {
 958                         /* Second operand is dead. */
 959                         if (op1_live_after) {
 960                                 /* First operand is live: bring second to tos. */
 961                                 if (op2_idx != 0) {
 962                                         x87_create_fxch(state, n, op2_idx);
 963                                         if (op1_idx == 0)
 964                                                 op1_idx = op2_idx;
 965                                         op2_idx = 0;
 966                                 }
 967                                 /* now do fxxxr (tos = op X tos) */
 968                                 out_idx = 0;
 969                                 dst = tmpl->reverse_op;
 970                         } else {
 971                                 /* Both operands are dead here, pop them from the stack. */
 972                                 if (op2_idx == 0) {
 973                                         if (op1_idx == 0) {
 974                                                 /* Both are identically and on tos, no pop needed. */
 975                                                 /* here fxxx (tos = tos X tos) */
 976                                                 dst = tmpl->normal_op;
 977                                                 out_idx = 0;
 978                                         } else {
 979                                                 /* now do fxxxp (op = op X tos, pop) */
 980                                                 dst = tmpl->normal_pop_op;
 981                                                 do_pop = 1;
 982                                                 out_idx = op1_idx;
 983                                         }
 984                                 } else if (op1_idx == 0) {
 985                                         assert(op1_idx != op2_idx);
 986                                         /* now do fxxxrp (op = tos X op, pop) */
 987                                         dst = tmpl->reverse_pop_op;
 988                                         do_pop = 1;
 989                                         out_idx = op2_idx;
 990                                 } else {
 991                                         /* Bring the second on top. */
 992                                         x87_create_fxch(state, n, op2_idx);
 993                                         if (op1_idx == op2_idx) {
 994                                                 /* Both are identically and on tos now, no pop needed. */
 995                                                 op1_idx = 0;
 996                                                 op2_idx = 0;
 997                                                 /* use fxxx (tos = tos X tos) */
 998                                                 dst = tmpl->normal_op;
 999                                                 out_idx = 0;
1000                                         } else {
1001                                                 /* op2 is on tos now */
1002                                                 op2_idx = 0;
1003                                                 /* use fxxxp (op = op X tos, pop) */
1004                                                 dst = tmpl->normal_pop_op;
1005                                                 out_idx = op1_idx;
1006                                                 do_pop = 1;
1007                                         }
1008                                 }
1009                         }
1010                 }
1011         } else {
1012                 /* second operand is an address mode */
1013                 if (op1_live_after) {
1014                         /* first operand is live: push it here */
1015                         x87_create_fpush(state, n, op1_idx, n_ia32_binary_left);
1016                         op1_idx = 0;
1017                 } else {
1018                         /* first operand is dead: bring it to tos */
1019                         if (op1_idx != 0) {
1020                                 x87_create_fxch(state, n, op1_idx);
1021                                 op1_idx = 0;
1022                         }
1023                 }
1024
1025                 /* use fxxx (tos = tos X mem) */
1026                 dst = permuted ? tmpl->reverse_op : tmpl->normal_op;
1027                 out_idx = 0;
1028         }
1029
1030         patched_insn = x87_patch_insn(n, dst);
1031         x87_set_st(state, arch_register_get_index(out), patched_insn, out_idx);
1032         if (do_pop) {
1033                 x87_pop(state);
1034         }
1035
1036         /* patch the operation */
1037         attr->x87[0] = op1_reg = &ia32_st_regs[op1_idx];
1038         if (reg_index_2 != REG_VFP_NOREG) {
1039                 attr->x87[1] = op2_reg = &ia32_st_regs[op2_idx];
1040         }
1041         attr->x87[2] = out = &ia32_st_regs[out_idx];
1042
1043         if (reg_index_2 != REG_VFP_NOREG) {
1044                 DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
1045                         arch_register_get_name(op1_reg), arch_register_get_name(op2_reg),
1046                         arch_register_get_name(out)));
1047         } else {
1048                 DB((dbg, LEVEL_1, "<<< %s %s, [AM] -> %s\n", get_irn_opname(n),
1049                         arch_register_get_name(op1_reg),
1050                         arch_register_get_name(out)));
1051         }
1052
1053         return NO_NODE_ADDED;
1054 }  /* sim_binop */
1055
1056 /**
1057  * Simulate a virtual Unop.
1058  *
1059  * @param state  the x87 state
1060  * @param n      the node that should be simulated (and patched)
1061  * @param op     the x87 opcode that will replace n's opcode
1062  *
1063  * @return NO_NODE_ADDED
1064  */
1065 static int sim_unop(x87_state *state, ir_node *n, ir_op *op)
1066 {
1067         int op1_idx;
1068         x87_simulator         *sim = state->sim;
1069         const arch_register_t *op1 = x87_get_irn_register(get_irn_n(n, UNOP_IDX));
1070         const arch_register_t *out = x87_get_irn_register(n);
1071         ia32_x87_attr_t *attr;
1072         unsigned live = vfp_live_args_after(sim, n, REGMASK(out));
1073
1074         DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name));
1075         DEBUG_ONLY(vfp_dump_live(live));
1076
1077         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1078
1079         if (is_vfp_live(arch_register_get_index(op1), live)) {
1080                 /* push the operand here */
1081                 x87_create_fpush(state, n, op1_idx, UNOP_IDX);
1082                 op1_idx = 0;
1083         }
1084         else {
1085                 /* operand is dead, bring it to tos */
1086                 if (op1_idx != 0) {
1087                         x87_create_fxch(state, n, op1_idx);
1088                         op1_idx = 0;
1089                 }
1090         }
1091
1092         x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op));
1093         attr = get_ia32_x87_attr(n);
1094         attr->x87[0] = op1 = &ia32_st_regs[0];
1095         attr->x87[2] = out = &ia32_st_regs[0];
1096         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
1097
1098         return NO_NODE_ADDED;
1099 }  /* sim_unop */
1100
1101 /**
1102  * Simulate a virtual Load instruction.
1103  *
1104  * @param state  the x87 state
1105  * @param n      the node that should be simulated (and patched)
1106  * @param op     the x87 opcode that will replace n's opcode
1107  *
1108  * @return NO_NODE_ADDED
1109  */
1110 static int sim_load(x87_state *state, ir_node *n, ir_op *op, int res_pos)
1111 {
1112         const arch_register_t *out = x87_irn_get_register(n, res_pos);
1113         ia32_x87_attr_t *attr;
1114
1115         DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, arch_register_get_name(out)));
1116         x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
1117         assert(out == x87_irn_get_register(n, res_pos));
1118         attr = get_ia32_x87_attr(n);
1119         attr->x87[2] = out = &ia32_st_regs[0];
1120         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
1121
1122         return NO_NODE_ADDED;
1123 }  /* sim_load */
1124
1125 /**
1126  * Rewire all users of @p old_val to @new_val iff they are scheduled after @p store.
1127  *
1128  * @param store   The store
1129  * @param old_val The former value
1130  * @param new_val The new value
1131  */
1132 static void collect_and_rewire_users(ir_node *store, ir_node *old_val, ir_node *new_val)
1133 {
1134         const ir_edge_t *edge, *ne;
1135
1136         foreach_out_edge_safe(old_val, edge, ne) {
1137                 ir_node *user = get_edge_src_irn(edge);
1138
1139                 if (! user || user == store)
1140                         continue;
1141
1142                 /* if the user is scheduled after the store: rewire */
1143                 if (sched_is_scheduled(user) && sched_comes_after(store, user)) {
1144                         int i;
1145                         /* find the input of the user pointing to the old value */
1146                         for (i = get_irn_arity(user) - 1; i >= 0; i--) {
1147                                 if (get_irn_n(user, i) == old_val)
1148                                         set_irn_n(user, i, new_val);
1149                         }
1150                 }
1151         }
1152 }  /* collect_and_rewire_users */
1153
1154 /**
1155  * Simulate a virtual Store.
1156  *
1157  * @param state  the x87 state
1158  * @param n      the node that should be simulated (and patched)
1159  * @param op     the x87 store opcode
1160  * @param op_p   the x87 store and pop opcode
1161  */
1162 static int sim_store(x87_state *state, ir_node *n, ir_op *op, ir_op *op_p)
1163 {
1164         ir_node               *val = get_irn_n(n, n_ia32_vfst_val);
1165         const arch_register_t *op2 = x87_get_irn_register(val);
1166         unsigned              live = vfp_live_args_after(state->sim, n, 0);
1167         int                   insn = NO_NODE_ADDED;
1168         ia32_x87_attr_t *attr;
1169         int op2_reg_idx, op2_idx, depth;
1170         int live_after_node;
1171         ir_mode *mode;
1172
1173         op2_reg_idx = arch_register_get_index(op2);
1174         op2_idx = x87_on_stack(state, op2_reg_idx);
1175         live_after_node = is_vfp_live(arch_register_get_index(op2), live);
1176         DB((dbg, LEVEL_1, ">>> %+F %s ->\n", n, arch_register_get_name(op2)));
1177         assert(op2_idx >= 0);
1178
1179         mode  = get_ia32_ls_mode(n);
1180         depth = x87_get_depth(state);
1181
1182         if (live_after_node) {
1183                 /*
1184                         Problem: fst doesn't support 96bit modes (spills), only fstp does
1185                                  fist doesn't support 64bit mode, only fistp
1186                         Solution:
1187                                 - stack not full: push value and fstp
1188                                 - stack full: fstp value and load again
1189                         Note that we cannot test on mode_E, because floats might be 96bit ...
1190                 */
1191                 if (get_mode_size_bits(mode) > 64 || (mode_is_int(mode) && get_mode_size_bits(mode) > 32)) {
1192                         if (depth < N_x87_REGS) {
1193                                 /* ok, we have a free register: push + fstp */
1194                                 x87_create_fpush(state, n, op2_idx, n_ia32_vfst_val);
1195                                 x87_pop(state);
1196                                 x87_patch_insn(n, op_p);
1197                         } else {
1198                                 ir_node  *vfld, *mem, *block, *rproj, *mproj;
1199                                 ir_graph *irg;
1200
1201                                 /* stack full here: need fstp + load */
1202                                 x87_pop(state);
1203                                 x87_patch_insn(n, op_p);
1204
1205                                 block = get_nodes_block(n);
1206                                 vfld  = new_bd_ia32_vfld(NULL, block, get_irn_n(n, 0), get_irn_n(n, 1), new_NoMem(), get_ia32_ls_mode(n));
1207
1208                                 /* copy all attributes */
1209                                 set_ia32_frame_ent(vfld, get_ia32_frame_ent(n));
1210                                 if (is_ia32_use_frame(n))
1211                                         set_ia32_use_frame(vfld);
1212                                 set_ia32_op_type(vfld, ia32_AddrModeS);
1213                                 add_ia32_am_offs_int(vfld, get_ia32_am_offs_int(n));
1214                                 set_ia32_am_sc(vfld, get_ia32_am_sc(n));
1215                                 set_ia32_ls_mode(vfld, get_ia32_ls_mode(n));
1216
1217                                 rproj = new_r_Proj(vfld, get_ia32_ls_mode(vfld), pn_ia32_vfld_res);
1218                                 mproj = new_r_Proj(vfld, mode_M, pn_ia32_vfld_M);
1219                                 mem   = get_irn_Proj_for_mode(n, mode_M);
1220
1221                                 assert(mem && "Store memory not found");
1222
1223                                 arch_set_irn_register(rproj, op2);
1224
1225                                 /* reroute all former users of the store memory to the load memory */
1226                                 irg = get_irn_irg(n);
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 = &ia32_st_regs[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 = &ia32_st_regs[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 = &ia32_st_regs[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_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 = &ia32_st_regs[op1_idx];
1606         attr->x87[0] = op1;
1607         if (op2_idx >= 0) {
1608                 op2 = &ia32_st_regs[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] = &ia32_st_regs[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] = &ia32_st_regs[op1_idx];
1746                 attr->x87[2] = &ia32_st_regs[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->regs != ia32_vfp_regs)
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 = &ia32_st_regs[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 = &ia32_st_regs[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       = obstack_alloc(&sim->obst, sizeof(*sim->live) * 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 = 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 = 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 */