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

   1 /**
   2  * This file implements the x87 support and virtual to stack
   3  * register translation for the ia32 backend.
   4  *
   5  * @author: Michael Beck
   6  *
   7  * $Id$
   8  */
   9
  10 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif /* HAVE_CONFIG_H */
  13
  14 #include <assert.h>
  15
  16 #include "irnode_t.h"
  17 #include "irop_t.h"
  18 #include "irprog.h"
  19 #include "iredges_t.h"
  20 #include "irgmod.h"
  21 #include "ircons.h"
  22 #include "obst.h"
  23 #include "pmap.h"
  24 #include "pdeq.h"
  25 #include "irprintf.h"
  26 #include "debug.h"
  27
  28 #include "../belive_t.h"
  29 #include "../besched.h"
  30 #include "../benode_t.h"
  31 #include "ia32_new_nodes.h"
  32 #include "gen_ia32_new_nodes.h"
  33 #include "gen_ia32_regalloc_if.h"
  34 #include "ia32_x87.h"
  35
  36 #define N_x87_REGS 8
  37
  38 /* first and second binop index */
  39 #define BINOP_IDX_1     2
  40 #define BINOP_IDX_2 3
  41
  42 /* the unop index */
  43 #define UNOP_IDX  0
  44
  45 /* the store val index */
  46 #define STORE_VAL_IDX 2
  47
  48 #define MASK_TOS(x)             ((x) & (N_x87_REGS - 1))
  49
  50 /** the debug handle */
  51 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
  52
  53 /**
  54  * An exchange template.
  55  * Note that our virtual functions have the same inputs
  56  * and attributes as the real ones, so we can simple exchange
  57  * their opcodes!
  58  * Further, x87 supports inverse instructions, so we can handle them.
  59  */
  60 typedef struct _exchange_tmpl {
  61         ir_op *normal_op;       /**< the normal one */
  62         ir_op *reverse_op;      /**< the reverse one if exists */
  63         ir_op *normal_pop_op;   /**< the normal one with tos pop */
  64         ir_op *reverse_pop_op;  /**< the reverse one with tos pop */
  65 } exchange_tmpl;
  66
  67 /**
  68  * An entry on the simulated x87 stack.
  69  */
  70 typedef struct _st_entry {
  71         int     reg_idx;        /**< the virtual register index of this stack value */
  72         ir_node *node;          /**< the node that produced this value */
  73 } st_entry;
  74
  75 /**
  76  * The x87 state.
  77  */
  78 typedef struct _x87_state {
  79         st_entry st[N_x87_REGS];  /**< the register stack */
  80         int depth;                /**< the current stack depth */
  81         int tos;                  /**< position of the tos */
  82 } x87_state;
  83
  84 /** An empty state, used for blocks without fp instructions. */
  85 static const x87_state _empty = { { {0, NULL}, }, 0, 0 };
  86 static x87_state *empty = (x87_state *)&_empty;
  87
  88 /** The type of an instruction simulator */
  89 typedef void (*sim_func)(x87_state *state, ir_node *n, const arch_env_t *env);
  90
  91 /**
  92  * A block state: Every block has a x87 state at the beginning and at the end.
  93  */
  94 typedef struct _blk_state {
  95         x87_state *begin;   /**< state at the begin or NULL if not assigned */
  96         x87_state *end;     /**< state at the end or NULL if not assigned */
  97 } blk_state;
  98
  99 #define PTR_TO_BLKSTATE(p)      ((blk_state *)(p))
 100
 101 /**
 102  * The x87 simulator.
 103  */
 104 typedef struct _x87_simulator {
 105         struct obstack obst;      /**< an obstack for fast allocating */
 106         pmap *blk_states;         /**< map blocks to states */
 107         const arch_env_t *env;          /**< architecture environment */
 108 } x87_simulator;
 109
 110 /**
 111  * Returns the stack depth.
 112  *
 113  * @param state  the x87 state
 114  *
 115  * @return the x87 stack depth
 116  */
 117 static int x87_get_depth(const x87_state *state) {
 118         return state->depth;
 119 }
 120
 121 /**
 122  * Check if the state is empty.
 123  *
 124  * @param state  the x87 state
 125  *
 126  * returns non-zero if the x87 stack is empty
 127  */
 128 static int x87_state_is_empty(const x87_state *state) {
 129         return state->depth == 0;
 130 }
 131
 132 /**
 133  * Return the virtual register index at st(pos).
 134  *
 135  * @param state  the x87 state
 136  * @param pos    a stack position
 137  *
 138  * @return the vfp register index that produced the value at st(pos)
 139  */
 140 static int x87_get_st_reg(const x87_state *state, int pos) {
 141         assert(pos < state->depth);
 142         return state->st[MASK_TOS(state->tos + pos)].reg_idx;
 143 }
 144
 145 /**
 146  * Return the node at st(pos).
 147  *
 148  * @param state  the x87 state
 149  * @param pos    a stack position
 150  *
 151  * @return the IR node that produced the value at st(pos)
 152  */
 153 static ir_node *x87_get_st_node(const x87_state *state, int pos) {
 154         assert(pos < state->depth);
 155         return state->st[MASK_TOS(state->tos + pos)].node;
 156 }
 157
 158 #ifdef DEBUG_libfirm
 159 /**
 160  * Dump the stack for debugging.
 161  *
 162  * @param state  the x87 state
 163  */
 164 static void x87_dump_stack(const x87_state *state) {
 165         int i;
 166
 167         for (i = state->depth - 1; i >= 0; --i) {
 168                 DB((dbg, LEVEL_2, "vf%d ", x87_get_st_reg(state, i)));
 169         }
 170         DB((dbg, LEVEL_2, "<-- TOS\n"));
 171 }
 172 #endif /* DEBUG_libfirm */
 173
 174 /**
 175  * Set a virtual register to st(pos).
 176  *
 177  * @param state    the x87 state
 178  * @param reg_idx  the vfp register index that should be set
 179  * @param node     the IR node that produces the value of the vfp register
 180  * @param pos      the stack position where the new value should be entered
 181  */
 182 static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) {
 183         assert(0 < state->depth);
 184         state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx;
 185         state->st[MASK_TOS(state->tos + pos)].node    = node;
 186
 187         DB((dbg, LEVEL_2, "After SET_REG:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 188 }
 189
 190 /**
 191  * Set the tos virtual register.
 192  *
 193  * @param state    the x87 state
 194  * @param reg_idx  the vfp register index that should be set
 195  * @param node     the IR node that produces the value of the vfp register
 196  */
 197 static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node) {
 198         x87_set_st(state, reg_idx, node, 0);
 199 }
 200
 201 /**
 202  * Flush the x87 stack.
 203  *
 204  * @param state    the x87 state
 205  */
 206 static void x87_flush(x87_state *state) {
 207         state->depth = 0;
 208         state->tos   = 0;
 209 }
 210
 211 /**
 212  * Swap st(0) with st(pos).
 213  *
 214  * @param state    the x87 state
 215  * @param pos      the stack position to change the tos with
 216  */
 217 static void x87_fxch(x87_state *state, int pos) {
 218         st_entry entry;
 219         assert(pos < state->depth);
 220
 221         entry = state->st[MASK_TOS(state->tos + pos)];
 222         state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
 223         state->st[MASK_TOS(state->tos)] = entry;
 224
 225         DB((dbg, LEVEL_2, "After FXCH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 226 }
 227
 228 /**
 229  * Convert a virtual register to the stack index.
 230  *
 231  * @param state    the x87 state
 232  * @param reg_idx  the register vfp index
 233  *
 234  * @return the stack position where the register is stacked
 235  *         or -1 if the virtual register was not found
 236  */
 237 static int x87_on_stack(const x87_state *state, int reg_idx) {
 238         int i, tos = state->tos;
 239
 240         for (i = 0; i < state->depth; ++i)
 241                 if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx)
 242                         return i;
 243         return -1;
 244 }
 245
 246 /**
 247  * Push a virtual Register onto the stack.
 248  *
 249  * @param state    the x87 state
 250  * @param reg_idx  the register vfp index
 251  * @param node     the node that produces the value of the vfp register
 252  */
 253 static void x87_push(x87_state *state, int reg_idx, ir_node *node) {
 254         assert(x87_on_stack(state, reg_idx) == -1 && "double push");
 255         assert(state->depth < N_x87_REGS && "stack overrun");
 256
 257         ++state->depth;
 258         state->tos = MASK_TOS(state->tos - 1);
 259         state->st[state->tos].reg_idx = reg_idx;
 260         state->st[state->tos].node    = node;
 261
 262         DB((dbg, LEVEL_2, "After PUSH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 263 }
 264
 265 /**
 266  * Pop a virtual Register from the stack.
 267  */
 268 static void x87_pop(x87_state *state) {
 269         assert(state->depth > 0 && "stack underrun");
 270
 271         --state->depth;
 272         state->tos = MASK_TOS(state->tos + 1);
 273
 274         DB((dbg, LEVEL_2, "After POP:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 275 }
 276
 277 /**
 278  * Returns the block state of a block.
 279  *
 280  * @param sim    the x87 simulator handle
 281  * @param block  the current block
 282  *
 283  * @return the block state
 284  */
 285 static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) {
 286         pmap_entry *entry = pmap_find(sim->blk_states, block);
 287
 288         if (! entry) {
 289                 blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
 290                 bl_state->begin = NULL;
 291                 bl_state->end   = NULL;
 292
 293                 pmap_insert(sim->blk_states, block, bl_state);
 294                 return bl_state;
 295         }
 296
 297         return entry ? PTR_TO_BLKSTATE(entry->value) : NULL;
 298 }
 299
 300 /**
 301  * Creates a new x87 state.
 302  *
 303  * @param sim    the x87 simulator handle
 304  * @return a new x87 state
 305  */
 306 static x87_state *x87_alloc_state(x87_simulator *sim) {
 307         x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
 308         return res;
 309 }
 310
 311 /**
 312  * Create a new empty x87 state.
 313  *
 314  * @param sim    the x87 simulator handle
 315  * @return a new empty x87 state
 316  */
 317 static x87_state *x87_alloc_empty_state(x87_simulator *sim) {
 318         x87_state *res = x87_alloc_state(sim);
 319
 320         x87_flush(res);
 321         return res;
 322 }
 323
 324 /**
 325  * Clone a x87 state.
 326  *
 327  * @param sim    the x87 simulator handle
 328  * @param src    the x87 state that will be cloned
 329  *
 330  * @return a cloned copy of the src state
 331  */
 332 static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) {
 333         x87_state *res = x87_alloc_state(sim);
 334
 335         memcpy(res, src, sizeof(*res));
 336         return res;
 337 }
 338
 339 /**
 340  * Patch a virtual instruction into a x87 one and return
 341  * the value node.
 342  *
 343  * @param n   the IR node to patch
 344  * @param op  the x87 opcode to patch in
 345  */
 346 static ir_node *x87_patch_insn(ir_node *n, ir_op *op) {
 347         ir_mode *mode = get_irn_mode(n);
 348         ir_node *res = n;
 349
 350         set_irn_op(n, op);
 351
 352         if (mode == mode_T) {
 353                 /* patch all Proj's */
 354                 const ir_edge_t *edge;
 355
 356                 foreach_out_edge(n, edge) {
 357                         ir_node *proj = get_edge_src_irn(edge);
 358                         if (is_Proj(proj)) {
 359                                 mode = get_irn_mode(proj);
 360                                 if (mode_is_float(mode)) {
 361                                         res = proj;
 362                                         set_irn_mode(proj, mode_E);
 363                                 }
 364                         }
 365                 }
 366         }
 367         else if (mode_is_float(mode))
 368                 set_irn_mode(n, mode_E);
 369         return res;
 370 }
 371
 372 /* -------------- x87 perm --------------- */
 373
 374 /**
 375  * Creates a fxch for shuffle.
 376  *
 377  * @param state     the x87 state
 378  * @param pos       parameter for fxch
 379  * @param dst_block the block of the user
 380  *
 381  * Creates a new fxch node and reroute the user of the old node
 382  * to the fxch.
 383  *
 384  * @return the fxch node
 385  */
 386 static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block, ir_node *dst_block)
 387 {
 388         const ir_edge_t *edge;
 389         ir_node *n = x87_get_st_node(state, pos);
 390         ir_node *user = NULL;
 391         ir_node *fxch;
 392         int node_idx;
 393         ia32_attr_t *attr;
 394
 395         if (block == get_nodes_block(n)) {
 396                 /* this is a node from out block: change it's user */
 397                 foreach_out_edge(n, edge) {
 398                         ir_node *succ = get_edge_src_irn(edge);
 399
 400                         if (is_Phi(succ) && get_nodes_block(succ) == dst_block) {
 401                                 user = succ;
 402                                 node_idx = get_edge_src_pos(edge);
 403                                 break;
 404                         }
 405                 }
 406                 assert(user);
 407         }
 408
 409         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(block), block, n, get_irn_mode(n));
 410         attr = get_ia32_attr(fxch);
 411         attr->x87[0] = &ia32_st_regs[pos];
 412         attr->x87[2] = &ia32_st_regs[0];
 413
 414         if (user) {
 415                 DB((dbg, LEVEL_2, "%+F replaced input %d of %+F\n", fxch, node_idx, user));
 416                 set_irn_n(user, node_idx, fxch);
 417         }
 418         else {
 419                 /*
 420                  * This is a node from a dominator block. Changing it's user might be wrong,
 421                  * so just keep it alive.
 422                  * The "right" solution would require a new Phi, but we don't care here.
 423                  */
 424                 keep_alive(fxch);
 425         }
 426
 427         x87_fxch(state, pos);
 428         return fxch;
 429 }
 430
 431 /**
 432  * Calculate the necessary permutations to reach dst_state.
 433  *
 434  * These permutations are done with fxch instructions and placed
 435  * at the end of the block.
 436  *
 437  * Note that critical edges are removed here, so we need only
 438  * a shuffle if the current block has only one successor.
 439  *
 440  * @param sim        the simulator handle
 441  * @param block      the current block
 442  * @param state      the current x87 stack state, might be modified
 443  * @param dst_block  the destination block
 444  * @param dst_state  destination state
 445  *
 446  * @return state
 447  */
 448 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, ir_node *dst_block, const x87_state *dst_state) {
 449         int i, n_cycles, k, ri;
 450         unsigned cycles[4], all_mask;
 451         char cycle_idx[4][8];
 452         ir_node *fxch;
 453         ir_node *before, *after;
 454
 455         assert(state->depth == dst_state->depth);
 456
 457         /* Some mathematics here:
 458            If we have a cycle of lenght n that includes the tos,
 459            we need n-1 exchange operations.
 460            We can always add the tos and restore it, so we need
 461            n+1 exchange operations for a cycle not containing the tos.
 462            So, the maximum of needed operations is for a cycle of 7
 463            not including the tos == 8.
 464            This is so same number of ops we would need for store,
 465            so exchange is cheaper (we save the loads).
 466            On the other hand, we might need an additional exchange
 467            in the next block to bring one operand on top, so the
 468            number of ops in the first case is identical.
 469                  Further, no more than 4 cycles can exists.
 470         */
 471         all_mask = (1 << (state->depth)) - 1;
 472
 473         for (n_cycles = 0; all_mask; ++n_cycles) {
 474                 int src_idx, dst_idx;
 475
 476                 /* find the first free slot */
 477                 for (i = 0; i < state->depth; ++i) {
 478                         if (all_mask & (1 << i)) {
 479                                 all_mask &= ~(1 << i);
 480
 481                                 /* check if there are differences here */
 482                                 if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
 483                                         break;
 484                         }
 485                 }
 486
 487                 if (! all_mask) {
 488                         /* no more cycles found */
 489                         break;
 490                 }
 491
 492                 k = 0;
 493                 cycles[n_cycles] = (1 << i);
 494                 cycle_idx[n_cycles][k++] = i;
 495                 for (src_idx = i; ; src_idx = dst_idx) {
 496                         dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
 497
 498                         if ((all_mask & (1 << dst_idx)) == 0)
 499                                 break;
 500
 501                         cycle_idx[n_cycles][k++] = dst_idx;
 502                         cycles[n_cycles] |=  (1 << dst_idx);
 503                         all_mask       &= ~(1 << dst_idx);
 504                 }
 505                 cycle_idx[n_cycles][k] = -1;
 506         }
 507
 508         if (n_cycles <= 0) {
 509                 /* no permutation needed */
 510                 return state;
 511         }
 512
 513         /* Hmm: permutation needed */
 514         DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
 515         DEBUG_ONLY(x87_dump_stack(state));
 516         DB((dbg, LEVEL_2, "                  to\n"));
 517         DEBUG_ONLY(x87_dump_stack(dst_state));
 518
 519
 520 #ifdef DEBUG_libfirm
 521         DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
 522         for (ri = 0; ri < n_cycles; ++ri) {
 523                 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
 524                 for (k = 0; cycle_idx[ri][k] != -1; ++k)
 525                         DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
 526                 DB((dbg, LEVEL_2, "\n"));
 527         }
 528 #endif
 529
 530         after = NULL;
 531
 532         /*
 533          * Find the place node must be insert.
 534          * We have only one successor block, so the last instruction should
 535          * be a jump.
 536          */
 537         before = sched_last(block);
 538         assert(is_cfop(before));
 539
 540         /* now do the permutations */
 541         for (ri = 0; ri < n_cycles; ++ri) {
 542                 if ((cycles[ri] & 1) == 0) {
 543                         /* this cycle does not include the tos */
 544                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block);
 545                         if (after)
 546                                 sched_add_after(after, fxch);
 547                         else
 548                                 sched_add_before(before, fxch);
 549                         after = fxch;
 550                 }
 551                 for (k = 1; cycle_idx[ri][k] != -1; ++k) {
 552                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][k], block, dst_block);
 553                         if (after)
 554                                 sched_add_after(after, fxch);
 555                         else
 556                                 sched_add_before(before, fxch);
 557                         after = fxch;
 558                 }
 559                 if ((cycles[ri] & 1) == 0) {
 560                         /* this cycle does not include the tos */
 561                         fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block);
 562                         sched_add_after(after, fxch);
 563                 }
 564         }
 565         return state;
 566 }
 567
 568 /**
 569  * Create a fxch node before another node.
 570  *
 571  * @param state   the x87 state
 572  * @param n       the node before the fxch
 573  * @param pos     exchange st(pos) with st(0)
 574  * @param op_idx  if >= 0, replace input op_idx of n with the fxch result
 575  *
 576  * @return the fxch
 577  */
 578 static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) {
 579         ir_node *fxch, *pred;
 580         ia32_attr_t *attr;
 581
 582         x87_fxch(state, pos);
 583
 584         if (op_idx >= 0)
 585                 pred = get_irn_n(n, op_idx);
 586         else
 587                 pred = x87_get_st_node(state, pos);
 588
 589         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 590         attr = get_ia32_attr(fxch);
 591         attr->x87[0] = &ia32_st_regs[pos];
 592         attr->x87[2] = &ia32_st_regs[0];
 593
 594         if (op_idx >= 0)
 595                 set_irn_n(n, op_idx, fxch);
 596
 597         sched_add_before(n, fxch);
 598         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
 599         return fxch;
 600 }
 601
 602 /**
 603  * Create a fpush before node n.
 604  *
 605  * @param state   the x87 state
 606  * @param n       the node before the fpush
 607  * @param pos     push st(pos) on stack
 608  * @param op_idx  if >= 0, replace input op_idx of n with the fpush result
 609  */
 610 static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n, int pos, int op_idx) {
 611         ir_node *fpush, *pred;
 612         ia32_attr_t *attr;
 613         const arch_register_t *out = arch_get_irn_register(env, n);
 614
 615         x87_push(state, arch_register_get_index(out), n);
 616
 617         pred = get_irn_n(n, op_idx);
 618         fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 619         attr = get_ia32_attr(fpush);
 620         attr->x87[0] = &ia32_st_regs[pos];
 621         attr->x87[2] = &ia32_st_regs[0];
 622         if (op_idx >= 0)
 623                 set_irn_n(n, op_idx, fpush);
 624
 625         sched_add_before(n, fpush);
 626         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
 627 }
 628
 629 /**
 630  * Create a fpop before node n.
 631  *
 632  * @param state   the x87 state
 633  * @param n       the node before the fpop
 634  * @param num     pop 1 or 2 values
 635  * @param pred    node to use as predecessor of the fpop
 636  *
 637  * @return the fpop node
 638  */
 639 static ir_node *x87_create_fpop(const arch_env_t *env, x87_state *state, ir_node *n, int num, ir_node *pred) {
 640         ir_node *fpop;
 641         ia32_attr_t *attr;
 642
 643         while (num > 0) {
 644                 x87_pop(state);
 645                 fpop = new_rd_ia32_fpop(NULL, get_irn_irg(n), get_nodes_block(n), pred, mode_E);
 646                 attr = get_ia32_attr(fpop);
 647                 attr->x87[0] = &ia32_st_regs[0];
 648                 attr->x87[1] = &ia32_st_regs[0];
 649                 attr->x87[2] = &ia32_st_regs[0];
 650
 651                 sched_add_before(n, fpop);
 652                 DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->x87[0]->name));
 653
 654                 pred = fpop;
 655                 --num;
 656         }
 657         return fpop;
 658 }
 659
 660 /* --------------------------------- liveness ------------------------------------------ */
 661
 662 /**
 663  * The liveness transfer function.
 664  * Updates a live set over a single step from a given node to its predecessor.
 665  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 666  * @param arch_env The architecture environment.
 667  * @param irn      The node at which liveness should be computed.
 668  * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 669  *                 the registers live after irn.
 670  * @return live.
 671  */
 672 static unsigned vfp_liveness_transfer(const arch_env_t *arch_env, ir_node *irn, unsigned live)
 673 {
 674         int i, n;
 675         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 676
 677         if (arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 678                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 679                         live &= ~(1 << reg->index);
 680         }
 681
 682         for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
 683                 ir_node *op = get_irn_n(irn, i);
 684
 685                 if (mode_is_float(get_irn_mode(op)) && arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
 686                         const arch_register_t *reg = arch_get_irn_register(arch_env, op);
 687                         live |= 1 << reg->index;
 688                 }
 689         }
 690
 691         return live;
 692 }
 693
 694 /**
 695  * Put all live virtual registers at the end of a block into a bitset.
 696  * @param arch_env The architecture environment.
 697  * @param bl       The block.
 698  * @return The live bitset.
 699  */
 700 static unsigned vfp_liveness_end_of_block(const arch_env_t *arch_env, const ir_node *bl)
 701 {
 702         irn_live_t *li;
 703         unsigned live = 0;
 704         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 705
 706         live_foreach(bl, li) {
 707                 ir_node *irn = (ir_node *) li->irn;
 708                 if (live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 709                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 710                         live |= 1 << reg->index;
 711                 }
 712         }
 713
 714         return live;
 715 }
 716
 717 /**
 718  * Compute a bitset of registers which are live at another node.
 719  * @param arch_env The architecture environment.
 720  * @param pos      The node.
 721  * @return The live bitset.
 722  */
 723 static unsigned vfp_liveness_nodes_live_at(const arch_env_t *arch_env, const ir_node *pos)
 724 {
 725         const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
 726         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 727         ir_node *irn;
 728         unsigned live;
 729
 730         live = vfp_liveness_end_of_block(arch_env, bl);
 731
 732         sched_foreach_reverse(bl, irn) {
 733                 /*
 734                  * If we encounter the node we want to insert the Perm after,
 735                  * exit immediately, so that this node is still live
 736                  */
 737                 if (irn == pos)
 738                         return live;
 739
 740                 live = vfp_liveness_transfer(arch_env, irn, live);
 741         }
 742
 743         return live;
 744 }
 745
 746 /**
 747  * Returns true if a register is live in a set.
 748  *
 749  * @param reg_idx  the vfp register index
 750  * @param live     a live bitset
 751  */
 752 static unsigned is_vfp_live(int reg_idx, unsigned live) {
 753         return live & (1 << reg_idx);
 754 }
 755
 756 #ifdef DEBUG_libfirm
 757 /**
 758  * Dump liveness info.
 759  *
 760  * @param live  the live bitset
 761  */
 762 static void vfp_dump_live(unsigned live) {
 763         int i;
 764
 765         DB((dbg, LEVEL_2, "Live registers here: \n"));
 766         for (i = 0; i < 8; ++i) {
 767                 if (live & (1 << i)) {
 768                         DB((dbg, LEVEL_2, " vf%d", i));
 769                 }
 770         }
 771         DB((dbg, LEVEL_2, "\n"));
 772 }
 773 #endif /* DEBUG_libfirm */
 774
 775 /* --------------------------------- simulators ---------------------------------------- */
 776
 777 #define XCHG(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0)
 778
 779 /**
 780  * Simulate a virtual binop.
 781  *
 782  * @param state  the x87 state
 783  * @param n      the node that should be simulated (and patched)
 784  * @param env    the architecture environment
 785  * @param tmpl   the template containing the 4 possible x87 opcodes
 786  */
 787 static void sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const exchange_tmpl *tmpl) {
 788         int op2_idx, op1_idx = -1;
 789         int out_idx, do_pop =0;
 790         ia32_attr_t *attr;
 791         ir_op *dst;
 792         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
 793         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
 794         const arch_register_t *out = arch_get_irn_register(env, n);
 795         unsigned live = vfp_liveness_nodes_live_at(env, n);
 796
 797         DB((dbg, LEVEL_1, ">>> %s %s, %s -> %s\n", get_irn_opname(n),
 798                 arch_register_get_name(op1), arch_register_get_name(op2),
 799                 arch_register_get_name(out)));
 800         DEBUG_ONLY(vfp_dump_live(live));
 801
 802         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 803         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 804
 805         if (op2->index != REG_VFP_NOREG) {
 806                 /* second operand is a vfp register */
 807
 808                 if (is_vfp_live(op2->index, live)) {
 809                         /* Second operand is live. */
 810
 811                         if (is_vfp_live(op1->index, live)) {
 812                                 /* Both operands are live: push the first one.
 813                                    This works even for op1 == op2. */
 814                                 x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
 815                                 out_idx = op2_idx = 0;
 816                                 ++op1_idx;
 817                                 dst = tmpl->normal_op;
 818                                 do_pop = 0;
 819                         }
 820                         else {
 821                                 /* Second live, first operand is dead here, bring it to tos. */
 822                                 if (op1_idx != 0) {
 823                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 824                                         if (op2_idx == 0)
 825                                                 op2_idx = op1_idx;
 826                                 }
 827                                 op1_idx = out_idx = 0;
 828                                 dst = tmpl->normal_op;
 829                                 do_pop = 0;
 830                         }
 831                 }
 832                 else {
 833                         /* Second operand is dead. */
 834                         if (is_vfp_live(op1->index, live)) {
 835                                 /* First operand is live: bring second to tos. */
 836                                 if (op2_idx != 0) {
 837                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 838                                         if (op1_idx == 0)
 839                                                 op1_idx = op2_idx;
 840                                 }
 841                                 op2_idx = out_idx = 0;
 842                                 dst = tmpl->normal_op;
 843                                 do_pop = 0;
 844                         }
 845                         else {
 846                                 /* Both operands are dead here, pop them from the stack. */
 847                                 if (op2_idx == 0) {
 848                                         out_idx = op1_idx;
 849                                         XCHG(op2_idx, op1_idx);
 850                                         if (op1_idx == op2_idx) {
 851                                                 /* Both are identically, no pop needed. */
 852                                                 dst = tmpl->reverse_op;
 853                                                 do_pop = 0;
 854                                         }
 855                                         else {
 856                                                 dst = tmpl->reverse_pop_op;
 857                                                 do_pop = 1;
 858                                         }
 859                                 }
 860                                 else if (op1_idx == 0) {
 861                                         out_idx = op2_idx;
 862                                         if (op1_idx == op2_idx) {
 863                                                 /* Both are identically, no pop needed. */
 864                                                 dst = tmpl->normal_op;
 865                                                 do_pop = 0;
 866                                         }
 867                                         else {
 868                                                 dst = tmpl->normal_pop_op;
 869                                                 do_pop = 1;
 870                                         }
 871                                 }
 872                                 else {
 873                                         /* Bring the first on top. */
 874                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 875                                         if (op1_idx == op2_idx) {
 876                                                 /* Both are identically, no pop needed. */
 877                                                 out_idx = op1_idx = op2_idx = 0;
 878                                                 dst = tmpl->normal_op;
 879                                                 do_pop = 0;
 880                                         }
 881                                         else {
 882                                                 op1_idx = 0;
 883                                                 out_idx = op2_idx;
 884                                                 dst = tmpl->normal_pop_op;
 885                                                 do_pop = 1;
 886                                         }
 887                                 }
 888                         }
 889                 }
 890         }
 891         else {
 892                 /* second operand is an address mode */
 893                 if (is_vfp_live(op1->index, live)) {
 894                         /* first operand is live: push it here */
 895                         x87_create_fpush(env, state, n, op1_idx, BINOP_IDX_1);
 896                 }
 897                 else {
 898                         /* first operand is dead: bring it to tos */
 899                         if (op1_idx != 0)
 900                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 901                 }
 902                 op1_idx = out_idx = 0;
 903                 dst = tmpl->normal_op;
 904                 do_pop = 0;
 905         }
 906
 907         x87_set_st(state, arch_register_get_index(out), x87_patch_insn(n, dst), out_idx);
 908         if (do_pop)
 909                 x87_pop(state);
 910
 911         /* patch the operation */
 912         attr = get_ia32_attr(n);
 913         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 914         if (op2_idx >= 0)
 915                 attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
 916         attr->x87[2] = out = &ia32_st_regs[out_idx];
 917
 918         if (op2_idx > 0)
 919                 DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
 920                         arch_register_get_name(op1), arch_register_get_name(op2),
 921                         arch_register_get_name(out)));
 922         else
 923                 DB((dbg, LEVEL_1, "<<< %s %s, [AM] -> %s\n", get_irn_opname(n),
 924                         arch_register_get_name(op1),
 925                         arch_register_get_name(out)));
 926 }
 927
 928 /**
 929  * Simulate a virtual Unop.
 930  *
 931  * @param state  the x87 state
 932  * @param n      the node that should be simulated (and patched)
 933  * @param env    the architecture environment
 934  * @param op     the x87 opcode that will replace n's opcode
 935  */
 936 static void sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 937         int op1_idx, out_idx;
 938         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, UNOP_IDX));
 939         const arch_register_t *out = arch_get_irn_register(env, n);
 940         ia32_attr_t *attr;
 941         unsigned live = vfp_liveness_nodes_live_at(env, n);
 942
 943         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name));
 944         DEBUG_ONLY(vfp_dump_live(live));
 945
 946         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 947
 948         if (is_vfp_live(op1->index, live)) {
 949                 /* push the operand here */
 950                 x87_create_fpush(env, state, n, op1_idx, UNOP_IDX);
 951         }
 952         else {
 953                 /* operand is dead, bring it to tos */
 954                 if (op1_idx != 0)
 955                         x87_create_fxch(state, n, op1_idx, UNOP_IDX);
 956         }
 957
 958         x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op));
 959         op1_idx = out_idx = 0;
 960         attr = get_ia32_attr(n);
 961         attr->x87[0] = op1 = &ia32_st_regs[0];
 962         attr->x87[2] = out = &ia32_st_regs[0];
 963         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
 964 }
 965
 966 /**
 967  * Simulate a virtual Load instruction.
 968  *
 969  * @param state  the x87 state
 970  * @param n      the node that should be simulated (and patched)
 971  * @param env    the architecture environment
 972  * @param op     the x87 opcode that will replace n's opcode
 973  */
 974 static void sim_load(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 975         const arch_register_t *out = arch_get_irn_register(env, n);
 976         ia32_attr_t *attr;
 977
 978         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 979         x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
 980         attr = get_ia32_attr(n);
 981         attr->x87[2] = out = &ia32_st_regs[0];
 982         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 983 }
 984
 985 /**
 986  * Simulate a virtual Store.
 987  *
 988  * @param state  the x87 state
 989  * @param n      the node that should be simulated (and patched)
 990  * @param env    the architecture environment
 991  * @param op     the x87 store opcode
 992  * @param op_p   the x87 store and pop opcode
 993  */
 994 static void sim_store(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op, ir_op *op_p) {
 995         int op2_idx;
 996         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, STORE_VAL_IDX));
 997         ia32_attr_t *attr;
 998         unsigned live = vfp_liveness_nodes_live_at(env, n);
 999
1000         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
1001         assert(op2_idx >= 0);
1002
1003         DB((dbg, LEVEL_1, ">>> %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
1004
1005         /* we can only store the tos to memory */
1006         if (op2_idx != 0)
1007                 x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX);
1008
1009         if (is_vfp_live(op2->index, live))
1010                 x87_patch_insn(n, op);
1011         else {
1012                 x87_pop(state);
1013                 x87_patch_insn(n, op_p);
1014         }
1015
1016         attr = get_ia32_attr(n);
1017         attr->x87[1] = op2 = &ia32_st_regs[0];
1018         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
1019 }
1020
1021 /**
1022  * Simulate a virtual Phi.
1023  * Just for cosmetic reasons change the mode of Phi nodes to mode_E.
1024  *
1025  * @param state  the x87 state
1026  * @param n      the node that should be simulated (and patched)
1027  * @param env    the architecture environment
1028  */
1029 static void sim_Phi(x87_state *state, ir_node *n, const arch_env_t *env) {
1030         ir_mode *mode = get_irn_mode(n);
1031
1032         if (mode_is_float(mode))
1033                 set_irn_mode(n, mode_E);
1034 }
1035
1036
1037 #define _GEN_BINOP(op, rev) \
1038 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1039         exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \
1040         sim_binop(state, n, env, &tmpl); \
1041 }
1042
1043 #define GEN_BINOP(op)     _GEN_BINOP(op, op)
1044 #define GEN_BINOPR(op)  _GEN_BINOP(op, op##r)
1045
1046 #define GEN_LOAD2(op, nop) \
1047 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1048         sim_load(state, n, env, op_ia32_##nop); \
1049 }
1050
1051 #define GEN_LOAD(op)    GEN_LOAD2(op, op)
1052
1053 #define GEN_UNOP(op) \
1054 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1055         sim_unop(state, n, env, op_ia32_##op); \
1056 }
1057
1058 #define GEN_STORE(op) \
1059 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1060         sim_store(state, n, env, op_ia32_##op, op_ia32_##op##p); \
1061 }
1062
1063 /* all stubs */
1064 GEN_BINOP(fadd)
1065 GEN_BINOPR(fsub)
1066 GEN_BINOP(fmul)
1067 GEN_BINOPR(fdiv)
1068
1069 GEN_UNOP(fabs)
1070 GEN_UNOP(fchs)
1071 GEN_UNOP(fsin)
1072 GEN_UNOP(fcos)
1073 GEN_UNOP(fsqrt)
1074
1075 GEN_LOAD(fld)
1076 GEN_LOAD(fild)
1077 GEN_LOAD(fldz)
1078 GEN_LOAD(fld1)
1079 GEN_LOAD2(fConst, fldConst)
1080
1081 GEN_STORE(fst)
1082 GEN_STORE(fist)
1083
1084 /**
1085  * Simulate a fCondJmp.
1086  *
1087  * @param state  the x87 state
1088  * @param n      the node that should be simulated (and patched)
1089  * @param env    the architecture environment
1090  */
1091 static void sim_fCondJmp(x87_state *state, ir_node *n, const arch_env_t *env) {
1092         int op2_idx, op1_idx = -1, pop_cnt = 0;
1093         ia32_attr_t *attr;
1094         ir_op *dst;
1095         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
1096         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
1097         unsigned live = vfp_liveness_nodes_live_at(env, n);
1098
1099         DB((dbg, LEVEL_1, ">>> %s %s, %s\n", get_irn_opname(n),
1100                 arch_register_get_name(op1), arch_register_get_name(op2)));
1101         DEBUG_ONLY(vfp_dump_live(live));
1102
1103         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1104         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
1105
1106         /* BEWARE: check for comp a,a cases, they might happen */
1107         if (op2->index != REG_VFP_NOREG) {
1108                 /* second operand is a vfp register */
1109
1110                 if (is_vfp_live(op2->index, live)) {
1111                         /* second operand is live */
1112
1113                         if (is_vfp_live(op1->index, live)) {
1114                                 /* both operands are live: move one of them to tos */
1115                                 if (op2_idx == 0) {
1116                                         XCHG(op2_idx, op1_idx);
1117                                         dst = op_ia32_fcomrJmp;
1118                                 }
1119                                 else if (op1_idx == 0) {
1120                                         dst = op_ia32_fcomJmp;
1121                                 }
1122                                 else {
1123                                         /* bring the first on top */
1124                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1125                                         if (op1_idx == op2_idx)
1126                                                 op2_idx = 0;
1127                                         op1_idx = 0;
1128                                         dst     = op_ia32_fcomJmp;
1129                                 }
1130                         }
1131                         else {
1132                                 /* second live, first operand is dead here, bring it to tos.
1133                                    This means further, op1_idx != op2_idx. */
1134                                 if (op1_idx != 0) {
1135                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1136                                         if (op2_idx == 0)
1137                                                 op2_idx = op1_idx;
1138                                 }
1139                                 op1_idx = 0;
1140                                 dst     = op_ia32_fcompJmp;
1141                                 pop_cnt = 1;
1142                         }
1143                 }
1144                 else {
1145                         /* second operand is dead */
1146                         if (is_vfp_live(op1->index, live)) {
1147                                 /* first operand is live: bring second to tos.
1148                                    This means further, op1_idx != op2_idx. */
1149                                 if (op2_idx != 0) {
1150                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1151                                         if (op1_idx == 0)
1152                                                 op1_idx = op2_idx;
1153                                 }
1154                                 op2_idx = 0;
1155                                 dst     = op_ia32_fcomrpJmp;
1156                                 pop_cnt = 1;
1157                         }
1158                         else {
1159                                 /* both operands are dead here, check first for identity. */
1160                                 if (op1_idx == op2_idx) {
1161                                         /* identically, one one needed */
1162                                         if (op1_idx != 0) {
1163                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1164                                                 op1_idx = op2_idx = 0;
1165                                         }
1166                                         dst     = op_ia32_fcompJmp;
1167                                         pop_cnt = 1;
1168                                 }
1169                                 /* different, move them to st and st(1) and pop both.
1170                                    The tricky part is to get one into st(1).*/
1171                                 else if (op2_idx == 1) {
1172                                         /* good, second operand is already in the right place, move the first */
1173                                         if (op1_idx != 0) {
1174                                                 /* bring the first on top */
1175                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1176                                                 op1_idx = 0;
1177                                         }
1178                                         dst     = op_ia32_fcomppJmp;
1179                                         pop_cnt = 2;
1180                                 }
1181                                 else if (op1_idx == 1) {
1182                                         /* good, first operand is already in the right place, move the second */
1183                                         if (op2_idx != 0) {
1184                                                 /* bring the first on top */
1185                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1186                                                 op2_idx = 0;
1187                                         }
1188                                         dst     = op_ia32_fcomrppJmp;
1189                                         pop_cnt = 2;
1190                                 }
1191                                 else {
1192                                         /* if one is already the TOS, we need two fxch */
1193                                         if (op1_idx == 0) {
1194                                                 /* first one is TOS, move to st(1) */
1195                                                 x87_create_fxch(state, n, 1, BINOP_IDX_1);
1196                                                 op1_idx = 1;
1197                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1198                                                 op2_idx = 0;
1199                                                 dst     = op_ia32_fcomrppJmp;
1200                                                 pop_cnt = 2;
1201                                         }
1202                                         else if (op2_idx == 0) {
1203                                                 /* second one is TOS, move to st(1) */
1204                                                 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1205                                                 op2_idx = 1;
1206                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1207                                                 op1_idx = 0;
1208                                                 dst     = op_ia32_fcomrppJmp;
1209                                                 pop_cnt = 2;
1210                                         }
1211                                         else {
1212                                                 /* none of them is either TOS or st(1), 3 fxch needed */
1213                                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1214                                                 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1215                                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1216                                                 op1_idx = 0;
1217                                                 op2_idx = 1;
1218                                                 dst     = op_ia32_fcomppJmp;
1219                                                 pop_cnt = 2;
1220                                         }
1221                                 }
1222                         }
1223                 }
1224         }
1225         else {
1226                 /* second operand is an address mode */
1227                 if (is_vfp_live(op1->index, live)) {
1228                         /* first operand is live: bring it to TOS */
1229                         if (op1_idx != 0) {
1230                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1231                                 op1_idx = 0;
1232                         }
1233                         dst = op_ia32_fcomJmp;
1234                 }
1235                 else {
1236                         /* first operand is dead: bring it to tos */
1237                         if (op1_idx != 0) {
1238                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1239                                 op1_idx = 0;
1240                         }
1241                 }
1242                 dst     = op_ia32_fcompJmp;
1243                 pop_cnt = 1;
1244         }
1245
1246         x87_patch_insn(n, dst);
1247         if (pop_cnt > 1)
1248                 x87_pop(state);
1249         if (pop_cnt > 0)
1250                 x87_pop(state);
1251
1252         /* patch the operation */
1253         attr = get_ia32_attr(n);
1254         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
1255         if (op2_idx >= 0)
1256                 attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
1257
1258         if (op2_idx >= 0)
1259                 DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(n),
1260                         arch_register_get_name(op1), arch_register_get_name(op2)));
1261         else
1262                 DB((dbg, LEVEL_1, "<<< %s %s, [AM]\n", get_irn_opname(n),
1263                         arch_register_get_name(op1)));
1264 }
1265
1266 /**
1267  * Simulate a be_Copy.
1268  *
1269  * @param state  the x87 state
1270  * @param n      the node that should be simulated (and patched)
1271  * @param env    the architecture environment
1272  */
1273 static void sim_Copy(x87_state *state, ir_node *n, const arch_env_t *env) {
1274         ir_mode *mode = get_irn_mode(n);
1275
1276         if (mode_is_float(mode)) {
1277                 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, 0));
1278                 const arch_register_t *out = arch_get_irn_register(env, n);
1279                 ir_node *node, *next;
1280                 ia32_attr_t *attr;
1281                 int op1_idx, out_idx;
1282                 unsigned live = vfp_liveness_nodes_live_at(env, n);
1283
1284                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1285
1286                 DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(n),
1287                         arch_register_get_name(op1), arch_register_get_name(out)));
1288           DEBUG_ONLY(vfp_dump_live(live));
1289
1290                 if (is_vfp_live(op1->index, live)) {
1291                         /* operand is still live,a real copy */
1292                         node = new_rd_ia32_fpush(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
1293                         arch_set_irn_register(env, node, out);
1294
1295                         x87_push(state, arch_register_get_index(out), node);
1296
1297                         attr = get_ia32_attr(node);
1298                         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
1299                         attr->x87[2] = out = &ia32_st_regs[0];
1300
1301                         next = sched_next(n);
1302                         sched_remove(n);
1303                         exchange(n, node);
1304                         sched_add_before(next, node);
1305                         DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(node), op1->name, out->name));
1306                 }
1307                 else {
1308                         out_idx = x87_on_stack(state, arch_register_get_index(out));
1309
1310                         if (out_idx >= 0 && out_idx != op1_idx) {
1311                                 /* op1 must be killed and placed where out is */
1312                                 if (out_idx == 0) {
1313                                         /* best case, simple remove and rename */
1314                                         x87_patch_insn(n, op_ia32_Pop);
1315                                         attr = get_ia32_attr(n);
1316                                         attr->x87[0] = op1 = &ia32_st_regs[0];
1317
1318                                         x87_pop(state);
1319                                         x87_set_st(state, arch_register_get_index(out), n, op1_idx - 1);
1320                                 }
1321                                 else {
1322                                         /* move op1 to tos, store and pop it */
1323                                         if (op1_idx != 0) {
1324                                                 x87_create_fxch(state, n, op1_idx, 0);
1325                                                 op1_idx = 0;
1326                                         }
1327                                         x87_patch_insn(n, op_ia32_Pop);
1328                                         attr = get_ia32_attr(n);
1329                                         attr->x87[0] = op1 = &ia32_st_regs[out_idx];
1330
1331                                         x87_pop(state);
1332                                         x87_set_st(state, arch_register_get_index(out), n, out_idx - 1);
1333                                 }
1334                                 DB((dbg, LEVEL_1, ">>> %s %s\n", get_irn_opname(n), op1->name));
1335                         }
1336                         else {
1337                                 /* just a virtual copy */
1338                                 x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx);
1339                                 sched_remove(n);
1340                                 DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n)));
1341                                 exchange(n, get_unop_op(n));
1342                         }
1343                 }
1344         }
1345 }
1346
1347 /**
1348  * Simulate a be_Call.
1349  *
1350  * @param state  the x87 state
1351  * @param n      the node that should be simulated
1352  * @param env    the architecture environment
1353  */
1354 static void sim_Call(x87_state *state, ir_node *n, const arch_env_t *env) {
1355         ir_type *call_tp = be_Call_get_type(n);
1356
1357         /* at the begin of a call the x87 state should be empty */
1358         assert(state->depth == 0 && "stack not empty before call");
1359
1360         /*
1361          * If the called function returns a float, it is returned in st(0).
1362          * This even happens if the return value is NOT used.
1363          * Moreover, only one return result is supported.
1364          */
1365         if (get_method_n_ress(call_tp) > 0) {
1366                 ir_type *res_type = get_method_res_type(call_tp, 0);
1367                 ir_mode *mode     = get_type_mode(res_type);
1368
1369                 if (mode && mode_is_float(mode)) {
1370                         /*
1371                          * TODO: what to push here? The result might be unused and currently
1372                          * we have no possibility to detect this :-(
1373                          */
1374                         x87_push(state, 0, n);
1375                 }
1376         }
1377 }
1378
1379 /**
1380  * Simulate a be_Spill.
1381  *
1382  * @param state  the x87 state
1383  * @param n      the node that should be simulated (and patched)
1384  * @param env    the architecture environment
1385  *
1386  * Should not happen, spills are lowered before x87 simulator see them.
1387  */
1388 static void sim_Spill(x87_state *state, ir_node *n, const arch_env_t *env) {
1389         assert(0 && "Spill not lowered");
1390         sim_fst(state, n, env);
1391 }
1392
1393 /**
1394  * Simulate a be_Reload.
1395  *
1396  * @param state  the x87 state
1397  * @param n      the node that should be simulated (and patched)
1398  * @param env    the architecture environment
1399  *
1400  * Should not happen, reloads are lowered before x87 simulator see them.
1401  */
1402 static void sim_Reload(x87_state *state, ir_node *n, const arch_env_t *env) {
1403         assert(0 && "Reload not lowered");
1404         sim_fld(state, n, env);
1405 }
1406
1407 /**
1408  * Simulate a be_Return.
1409  *
1410  * @param state  the x87 state
1411  * @param n      the node that should be simulated (and patched)
1412  * @param env    the architecture environment
1413  */
1414 static void sim_Return(x87_state *state, ir_node *n, const arch_env_t *env) {
1415         int n_res = be_Return_get_n_rets(n);
1416         int i, n_float_res = 0;
1417
1418         /* only floating point return values must resist on stack */
1419         for (i = 0; i < n_res; ++i) {
1420                 ir_node *res = get_irn_n(n, be_pos_Return_val + i);
1421
1422                 if (mode_is_float(get_irn_mode(res)))
1423                         ++n_float_res;
1424         }
1425         assert(x87_get_depth(state) == n_float_res);
1426
1427         /* pop them virtually */
1428         for (i = n_float_res - 1; i >= 0; --i)
1429                 x87_pop(state);
1430 }
1431
1432 /**
1433  * Kill any dead registers at block start by popping them from the stack.
1434  *
1435  * @param sim          the simulator handle
1436  * @param block        the current block
1437  * @param start_state  the x87 state at the begin of the block
1438  */
1439 static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state *start_state) {
1440         x87_state *state = start_state;
1441         ir_node *first_insn = sched_first(block);
1442         ir_node *keep = NULL;
1443         unsigned live = vfp_liveness_nodes_live_at(sim->env, block);
1444         unsigned kill_mask;
1445         int i, depth, num_pop;
1446
1447         kill_mask = 0;
1448         depth = x87_get_depth(state);
1449         for (i = depth - 1; i >= 0; --i) {
1450                 int reg = x87_get_st_reg(state, i);
1451
1452                 if (! is_vfp_live(reg, live))
1453                         kill_mask |= (1 << i);
1454         }
1455
1456         if (kill_mask) {
1457                 /* create a new state, will be changed */
1458                 state = x87_clone_state(sim, state);
1459
1460                 DB((dbg, LEVEL_1, "Killing deads:\n"));
1461                 DEBUG_ONLY(vfp_dump_live(live));
1462                 DEBUG_ONLY(x87_dump_stack(state));
1463
1464                 /* now kill registers */
1465                 while (kill_mask) {
1466                         /* we can only kill from TOS, so bring them up */
1467                         if (! (kill_mask & 1)) {
1468                                 /* search from behind, because we can to a double-pop */
1469                                 for (i = depth - 1; i >= 0; --i) {
1470                                         if (kill_mask & (1 << i)) {
1471                                                 kill_mask &= ~(1 << i);
1472                                                 kill_mask |= 1;
1473                                                 break;
1474                                         }
1475                                 }
1476
1477                                 if (keep)
1478                                         x87_set_st(state, -1, keep, i);
1479                                 keep = x87_create_fxch(state, first_insn, i, -1);
1480                         }
1481                         else if (! keep)
1482                                 keep = x87_get_st_node(state, 0);
1483
1484                         if ((kill_mask & 3) == 3) {
1485                                 /* we can do a double-pop */
1486                                 num_pop = 2;
1487                         }
1488                         else {
1489                                 /* only a single pop */
1490                                 num_pop = 1;
1491                         }
1492
1493                         depth -= num_pop;
1494                         kill_mask >>= num_pop;
1495                         keep = x87_create_fpop(sim->env, state, first_insn, num_pop, keep);
1496                 }
1497                 add_End_keepalive(get_irg_end(get_irn_irg(block)), keep);
1498         }
1499         return state;
1500 }
1501
1502 /**
1503  * Run a simulation and fix all virtual instructions for a block.
1504  *
1505  * @param sim          the simulator handle
1506  * @param block        the current block
1507  *
1508  * @return non-zero if simulation is complete,
1509  *         zero if the simulation must be rerun
1510  */
1511 static int x87_simulate_block(x87_simulator *sim, ir_node *block) {
1512         ir_node *n, *next;
1513         blk_state *bl_state = x87_get_bl_state(sim, block);
1514         x87_state *state = bl_state->begin;
1515         const ir_edge_t *edge;
1516         ir_node *start_block;
1517
1518         /* if we have no assigned start state, we must wait ... */
1519         if (! state)
1520                 return 0;
1521
1522         assert(bl_state->end == NULL);
1523
1524         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
1525
1526         /* at block begin, kill all dead registers */
1527         state = x87_kill_deads(sim, block, state);
1528
1529         /* beware, n might changed */
1530         for (n = sched_first(block); !sched_is_end(n); n = next) {
1531                 ir_op *op = get_irn_op(n);
1532
1533                 next = sched_next(n);
1534                 if (op->ops.generic) {
1535                         sim_func func = (sim_func)op->ops.generic;
1536
1537                         /* have work to do */
1538                         if (state == bl_state->begin) {
1539                                 /* create a new state, will be changed */
1540                                 state = x87_clone_state(sim, state);
1541                         }
1542
1543                         /* simulate it */
1544                         (*func)(state, n, sim->env);
1545                 }
1546         }
1547
1548         start_block = get_irg_start_block(get_irn_irg(block));
1549
1550         /* check if the state must be shuffled */
1551         foreach_block_succ(block, edge) {
1552                 ir_node *succ = get_edge_src_irn(edge);
1553                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1554
1555                 if (succ_state->begin && succ != start_block) {
1556                         /* There is already a begin state for this block, bad.
1557                            Do the necessary permutations.
1558                            Note that critical edges are removed, so this is always possible. */
1559                         x87_shuffle(sim, block, state, succ, succ_state->begin);
1560
1561                         /* Note further, that there can be only one such situation,
1562                            so we can break here. */
1563                         break;
1564                 }
1565         }
1566         bl_state->end = state;
1567
1568         /* now propagate the state to all successor blocks */
1569         foreach_block_succ(block, edge) {
1570                 ir_node *succ = get_edge_src_irn(edge);
1571                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1572
1573                 if (! succ_state->begin)
1574                         succ_state->begin = state;
1575         }
1576
1577         return 1;
1578 }
1579
1580 /**
1581  * Create a new x87 simulator.
1582  *
1583  * @param sim   a simulator handle, will be initialized
1584  * @param irg   the current graph
1585  * @param env   the architecture environment
1586  */
1587 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env_t *env) {
1588         obstack_init(&sim->obst);
1589         sim->blk_states = pmap_create();
1590         sim->env        = env;
1591
1592         FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
1593
1594         DB((dbg, LEVEL_1, "--------------------------------\n"
1595                 "x87 Simulator started for %+F\n", irg));
1596
1597   /* set the generic function pointer of instruction we must simulate */
1598         clear_irp_opcodes_generic_func();
1599
1600 #define ASSOC(op)       (op_ ## op)->ops.generic = (op_func)(sim_##op)
1601 #define ASSOC_IA32(op)  (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
1602 #define ASSOC_BE(op)    (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
1603         ASSOC_IA32(fConst);
1604         ASSOC_IA32(fld);
1605         ASSOC_IA32(fild);
1606         ASSOC_IA32(fld1);
1607         ASSOC_IA32(fldz);
1608         ASSOC_IA32(fadd);
1609         ASSOC_IA32(fsub);
1610         ASSOC_IA32(fmul);
1611         ASSOC_IA32(fdiv);
1612         ASSOC_IA32(fldz);
1613         ASSOC_IA32(fabs);
1614         ASSOC_IA32(fchs);
1615         ASSOC_IA32(fsin);
1616         ASSOC_IA32(fcos);
1617         ASSOC_IA32(fsqrt);
1618         ASSOC_IA32(fist);
1619         ASSOC_IA32(fst);
1620         ASSOC_IA32(fCondJmp);
1621         ASSOC_BE(Copy);
1622         ASSOC_BE(Call);
1623         ASSOC_BE(Spill);
1624         ASSOC_BE(Reload);
1625         ASSOC_BE(Return);
1626         ASSOC(Phi);
1627 #undef ASSOC_BE
1628 #undef ASSOC_IA32
1629 #undef ASSOC
1630 }
1631
1632 /**
1633  * Destroy a x87 simulator.
1634  *
1635  * @param sim  the simulator handle
1636  */
1637 static void x87_destroy_simulator(x87_simulator *sim) {
1638         pmap_destroy(sim->blk_states);
1639         obstack_free(&sim->obst, NULL);
1640         DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
1641 }
1642
1643 /**
1644  * Run a simulation and fix all virtual instructions for a graph.
1645  *
1646  * @param env       the architecture environment
1647  * @param irg       the current graph
1648  * @param blk_list  the block schedule list
1649  *
1650  * Needs a block-schedule.
1651  */
1652 void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) {
1653         ir_node *block, *start_block;
1654         pdeq *worklist;
1655         blk_state *bl_state;
1656         x87_simulator sim;
1657         int i;
1658
1659         /* we need liveness info for the current graph */
1660         be_liveness(irg);
1661
1662         /* create the simulator */
1663         x87_init_simulator(&sim, irg, env);
1664
1665         start_block = get_irg_start_block(irg);
1666         bl_state = x87_get_bl_state(&sim, start_block);
1667
1668         /* start with the empty state */
1669         bl_state->begin = empty;
1670
1671         worklist = new_pdeq();
1672
1673         /* create the worklist for the schedule. */
1674         for (i = 0; i < ARR_LEN(blk_list); ++i)
1675                 pdeq_putr(worklist, blk_list[i]);
1676
1677         /* iterate */
1678         do {
1679                 block = pdeq_getl(worklist);
1680                 if (! x87_simulate_block(&sim, block)) {
1681                         pdeq_putr(worklist, block);
1682                         continue;
1683                 }
1684         } while (! pdeq_empty(worklist));
1685
1686         /* kill it */
1687         x87_destroy_simulator(&sim);
1688 }