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

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