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

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