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