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 #include <assert.h>
  10
  11 #include "irnode_t.h"
  12 #include "irop_t.h"
  13 #include "irprog.h"
  14 #include "iredges_t.h"
  15 #include "irgmod.h"
  16 #include "obst.h"
  17 #include "pmap.h"
  18 #include "pdeq.h"
  19 #include "irprintf.h"
  20 #include "debug.h"
  21
  22 #include "..\belive_t.h"
  23 #include "..\besched.h"
  24 #include "..\benode_t.h"
  25 #include "ia32_new_nodes.h"
  26 #include "gen_ia32_new_nodes.h"
  27 #include "gen_ia32_regalloc_if.h"
  28 #include "ia32_x87.h"
  29
  30 #define N_x87_REGS 8
  31
  32 /* first and second binop index */
  33 #define BINOP_IDX_1     2
  34 #define BINOP_IDX_2 3
  35
  36 /* the unop index */
  37 #define UNOP_IDX  0
  38
  39 /* the store val index */
  40 #define STORE_VAL_IDX 2
  41
  42 #define MASK_TOS(x)             ((x) & (N_x87_REGS - 1))
  43
  44 /** the debug handle */
  45 static firm_dbg_module_t *dbg = NULL;
  46
  47 /**
  48  * An exchange template.
  49  * Note that our virtual functions have the same inputs
  50  * and attributes as the real ones, so we can simple exchange
  51  * their opcodes!
  52  * Further, x87 supports inverse instructions, so we can handle them.
  53  */
  54 typedef struct _exchange_tmpl {
  55         ir_op *normal_op;       /**< the normal one */
  56         ir_op *reverse_op;      /**< the reverse one if exists */
  57         ir_op *normal_pop_op;   /**< the normal one with tos pop */
  58         ir_op *reverse_pop_op;  /**< the reverse one with tos pop */
  59 } exchange_tmpl;
  60
  61 /**
  62  * The x87 state.
  63  */
  64 typedef struct _x87_state {
  65         const arch_register_t *st[N_x87_REGS];  /**< the register stack */
  66         int depth;                              /**< the current stack depth */
  67         int tos;                                /**< position of the tos */
  68 } x87_state;
  69
  70 /** An empty state, used for blocks without fp instructions. */
  71 static const x87_state _empty = { {0}, 0, 0 };
  72 static x87_state *empty = (x87_state *)&_empty;
  73
  74 /** The type of an instruction simulator */
  75 typedef void (*sim_func)(x87_state *state, ir_node *n, const arch_env_t *env);
  76
  77 /**
  78  * A block state: Every block has a x87 state at the beginning and at the end.
  79  */
  80 typedef struct _blk_state {
  81         x87_state *begin;   /**< state at the begin or NULL if not assigned */
  82         x87_state *end;     /**< state at the end or NULL if not assigned */
  83 } blk_state;
  84
  85 #define PTR_TO_BLKSTATE(p)      ((blk_state *)(p))
  86
  87 /**
  88  * The x87 simulator.
  89  */
  90 typedef struct _x87_simulator {
  91         struct obstack obst;      /**< an obstack for fast allocating */
  92         pmap *blk_states;         /**< map blocks to states */
  93         const arch_env_t *env;          /**< architecture environment */
  94 } x87_simulator;
  95
  96 /**
  97  * Check if the state is empty.
  98  */
  99 static int x87_state_is_empty(const x87_state *state) {
 100         return state->depth == 0;
 101 }
 102
 103 /**
 104  * Return the virtual register at st(pos).
 105  */
 106 static const arch_register_t *x87_get_reg(const x87_state *state, int pos) {
 107         assert(pos < state->depth);
 108         return state->st[MASK_TOS(state->tos + pos)];
 109 }
 110
 111 #ifdef DEBUG_libfirm
 112 /**
 113  * Dump the stack for debugging.
 114  */
 115 static void x87_dump_stack(const x87_state *state) {
 116         int i;
 117
 118         for (i = state->depth - 1; i >= 0; --i) {
 119                 const arch_register_t *vreg = x87_get_reg(state, i);
 120                 DB((dbg, LEVEL_2, "%s ", vreg->name));
 121         }
 122         DB((dbg, LEVEL_2, "<-- TOS\n"));
 123 }
 124 #endif /* DEBUG_libfirm */
 125
 126 /**
 127  * Set a virtual register to st(pos)
 128  */
 129 static void x87_set_reg(x87_state *state, const arch_register_t *vreg, int pos) {
 130         assert(0 < state->depth);
 131         state->st[MASK_TOS(state->tos + pos)] = vreg;
 132
 133         DB((dbg, LEVEL_2, "After SET_REG:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 134 }
 135
 136 /**
 137  * Set the tos virtual register
 138  */
 139 static void x87_set_tos_reg(x87_state *state, const arch_register_t *vreg) {
 140         x87_set_reg(state, vreg, 0);
 141 }
 142
 143 /**
 144  * Flush the x87 stack.
 145  */
 146 static void x87_flush(x87_state *state) {
 147         state->depth = 0;
 148         state->tos   = 0;
 149 }
 150
 151 /**
 152  * Swap st(0) with st(pos).
 153  */
 154 static void x87_fxch(x87_state *state, int pos) {
 155         const arch_register_t *vreg;
 156         assert(pos < state->depth);
 157
 158         vreg = state->st[MASK_TOS(state->tos + pos)];
 159         state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
 160         state->st[MASK_TOS(state->tos)] = vreg;
 161
 162         DB((dbg, LEVEL_2, "After FXCH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 163 }
 164
 165 /**
 166  * Convert a virtual register to the stack index.
 167  * Return -1 if the virtual register was not found.
 168  */
 169 static int x87_on_stack(const x87_state *state, const arch_register_t *vreg) {
 170         int i, tos = state->tos;
 171
 172         for (i = 0; i < state->depth; ++i)
 173                 if (state->st[MASK_TOS(tos + i)] == vreg)
 174                         return i;
 175         return -1;
 176 }
 177
 178 /**
 179  * Push a virtual Register onto the stack.
 180  */
 181 static void x87_push(x87_state *state, const arch_register_t *vreg) {
 182 //      assert(x87_on_stack(state, vreg) == -1 && "double push");
 183         assert(state->depth < N_x87_REGS && "stack overrun");
 184
 185         ++state->depth;
 186         state->tos = MASK_TOS(state->tos - 1);
 187         state->st[state->tos] = vreg;
 188
 189         DB((dbg, LEVEL_2, "After PUSH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 190 }
 191
 192 /**
 193  * Pop a virtual Register from the stack.
 194  */
 195 static void x87_pop(x87_state *state) {
 196         assert(state->depth > 0 && "stack underrun");
 197
 198         --state->depth;
 199         state->tos = MASK_TOS(state->tos + 1);
 200
 201         DB((dbg, LEVEL_2, "After POP:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 202 }
 203
 204 /**
 205  * Returns the block state of a block.
 206  */
 207 static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) {
 208         pmap_entry *entry = pmap_find(sim->blk_states, block);
 209
 210         if (! entry) {
 211                 blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
 212                 bl_state->begin = NULL;
 213                 bl_state->end   = NULL;
 214
 215                 pmap_insert(sim->blk_states, block, bl_state);
 216                 return bl_state;
 217         }
 218
 219         return entry ? PTR_TO_BLKSTATE(entry->value) : NULL;
 220 }
 221
 222 /**
 223  * Create a new x87 state.
 224  */
 225 static x87_state *x87_alloc_state(x87_simulator *sim) {
 226         x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
 227         return res;
 228 }
 229
 230 /**
 231  * Create a new empty x87 state.
 232  */
 233 static x87_state *x87_alloc_empty_state(x87_simulator *sim) {
 234         x87_state *res = x87_alloc_state(sim);
 235
 236         x87_flush(res);
 237         return res;
 238 }
 239
 240 /**
 241  * Clone a x87 state.
 242  */
 243 static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) {
 244         x87_state *res = x87_alloc_state(sim);
 245
 246         memcpy(res, src, sizeof(*res));
 247         return res;
 248 }
 249
 250 /* -------------- x87 perm --------------- */
 251
 252 /**
 253  * Calculate the necessary permutations to reach dst_state.
 254  */
 255 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, const x87_state *dst_state) {
 256         int i, n_rings, k, ri;
 257         unsigned rings[4], all_mask;
 258         char ring_idx[4][8];
 259
 260         assert(state->depth == dst_state->depth);
 261
 262         /* Some mathematics here:
 263            If we have a ring of lenght n that includes the tos,
 264            we need n-1 exchange operations.
 265            We can always add the tos and restore it, so we need
 266            n+1 exchange operations for a ring not containing the tos.
 267            So, the maximum of needed operations is for a ring of 7
 268            not including the tos == 8.
 269            This is so same number of ops we would need for store,
 270            so exchange is cheaper (we save the loads).
 271            On the other hand, we might need an additional exchange
 272            in the next block to bring one operand on top, so the
 273            number of ops in the first case is identical.
 274                  Further, no more than 4 rings can exists.
 275         */
 276         all_mask = (1 << (state->depth)) - 1;
 277
 278         for (n_rings = 0; all_mask; ++n_rings) {
 279                 int src_idx, dst_idx;
 280
 281                 /* find the first free slot */
 282                 for (i = 0; i < state->depth; ++i) {
 283                         if (all_mask & (1 << i)) {
 284                                 all_mask &= ~(1 << i);
 285
 286                                 /* check if there are differences here */
 287                                 if (x87_get_reg(state, i) != x87_get_reg(dst_state, i))
 288                                         break;
 289                         }
 290                 }
 291
 292                 if (! all_mask) {
 293                         /* no more rings found */
 294                         break;
 295                 }
 296
 297                 k = 0;
 298                 rings[n_rings] = (1 << i);
 299                 ring_idx[n_rings][k++] = i;
 300                 for (src_idx = i; ; src_idx = dst_idx) {
 301                         dst_idx = x87_on_stack(dst_state, x87_get_reg(state, src_idx));
 302
 303                         if ((all_mask & (1 << dst_idx)) == 0)
 304                                 break;
 305
 306                         ring_idx[n_rings][k++] = dst_idx;
 307                         rings[n_rings] |=  (1 << dst_idx);
 308                         all_mask       &= ~(1 << dst_idx);
 309                 }
 310                 ring_idx[n_rings][k] = -1;
 311         }
 312
 313         if (n_rings <= 0) {
 314                 /* no permutation needed */
 315                 return state;
 316         }
 317
 318         /* Hmm: permutation needed */
 319         DB((dbg, LEVEL_2, "\nNeed permutation: from\n"));
 320         DEBUG_ONLY(x87_dump_stack(state));
 321         DB((dbg, LEVEL_2, "                  to\n"));
 322         DEBUG_ONLY(x87_dump_stack(dst_state));
 323
 324
 325 #ifdef DEBUG_libfirm
 326         DB((dbg, LEVEL_2, "Need %d rings\n", n_rings));
 327         for (ri = 0; ri < n_rings; ++ri) {
 328                 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
 329                 for (k = 0; ring_idx[ri][k] != -1; ++k)
 330                         DB((dbg, LEVEL_2, " st%d ->", ring_idx[ri][k]));
 331                 DB((dbg, LEVEL_2, "\n"));
 332         }
 333 #endif
 334
 335         /* now do the permutations */
 336         for (ri = 0; ri < n_rings; ++ri) {
 337                 if ((rings[ri] & 1) == 0) {
 338                         /* this ring does not include the tos */
 339                         x87_fxch(state, ring_idx[ri][0]);
 340                 }
 341                 for (k = 1; ring_idx[ri][k] != -1; ++k) {
 342                         x87_fxch(state, ring_idx[ri][k]);
 343                 }
 344                 if ((rings[ri] & 1) == 0) {
 345                         /* this ring does not include the tos */
 346                         x87_fxch(state, ring_idx[ri][0]);
 347                 }
 348         }
 349         assert(0);
 350         return state;
 351 }
 352
 353 /**
 354  * Create a fxch before node n.
 355  */
 356 static void x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) {
 357         ir_node *fxch, *pred;
 358         ia32_attr_t *attr;
 359
 360         x87_fxch(state, pos);
 361
 362         pred = get_irn_n(n, op_idx);
 363         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 364         attr = get_ia32_attr(fxch);
 365         attr->x87[0] = &ia32_st_regs[pos];
 366         attr->x87[2] = &ia32_st_regs[0];
 367         set_irn_n(n, op_idx, fxch);
 368
 369         sched_add_before(n, fxch);
 370         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
 371 }
 372
 373 /**
 374  * Create a fpush before node n.
 375  */
 376 static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n, int pos, int op_idx) {
 377         ir_node *fpush, *pred;
 378         ia32_attr_t *attr;
 379
 380         x87_push(state, arch_get_irn_register(env, n));
 381
 382         pred = get_irn_n(n, op_idx);
 383         fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 384         attr = get_ia32_attr(fpush);
 385         attr->x87[0] = &ia32_st_regs[pos];
 386         attr->x87[2] = &ia32_st_regs[0];
 387         set_irn_n(n, op_idx, fpush);
 388
 389         sched_add_before(n, fpush);
 390         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
 391 }
 392
 393 /* --------------------------------- liveness ------------------------------------------ */
 394
 395 /**
 396  * The liveness transfer function.
 397  * Updates a live set over a single step from a given node to its predecessor.
 398  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 399  * @param arch_env The architecture environment.
 400  * @param irn      The node at which liveness should be computed.
 401  * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 402  *                 the registers live after irn.
 403  * @return live.
 404  */
 405 static unsigned vfp_liveness_transfer(const arch_env_t *arch_env, ir_node *irn, unsigned live)
 406 {
 407         int i, n;
 408         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 409
 410         if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 411                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 412                         live &= ~(1 << reg->index);
 413         }
 414
 415         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 416                 ir_node *op = get_irn_n(irn, i);
 417
 418                 if (arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
 419                         const arch_register_t *reg = arch_get_irn_register(arch_env, op);
 420                         live |= 1 << reg->index;
 421                 }
 422         }
 423
 424         return live;
 425 }
 426
 427 /**
 428  * Put all live virtual registers at the end of a block into a bitset.
 429  * @param arch_env The architecture environment.
 430  * @param bl       The block.
 431  * @return The live bitset.
 432  */
 433 static unsigned vfp_liveness_end_of_block(const arch_env_t *arch_env, const ir_node *bl)
 434 {
 435         irn_live_t *li;
 436         unsigned live = 0;
 437         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 438
 439         live_foreach(bl, li) {
 440                 ir_node *irn = (ir_node *) li->irn;
 441                 if (live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 442                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 443                         live |= 1 << reg->index;
 444                 }
 445         }
 446
 447         return live;
 448 }
 449
 450 /**
 451  * Compute a bitset of registers which are live at another node.
 452  * @param arch_env The architecture environment.
 453  * @param pos      The node.
 454  * @return The live bitset.
 455  */
 456 static unsigned vfp_liveness_nodes_live_at(const arch_env_t *arch_env, const ir_node *pos)
 457 {
 458         const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
 459         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 460         ir_node *irn;
 461         unsigned live;
 462
 463         live = vfp_liveness_end_of_block(arch_env, bl);
 464
 465         sched_foreach_reverse(bl, irn) {
 466                 /*
 467                  * If we encounter the node we want to insert the Perm after,
 468                  * exit immediately, so that this node is still live
 469                  */
 470                 if (irn == pos)
 471                         return live;
 472
 473                 live = vfp_liveness_transfer(arch_env, irn, live);
 474         }
 475
 476         return live;
 477 }
 478
 479 /**
 480  * Returns true if a register is live in a set.
 481  */
 482 static unsigned is_vfp_live(const arch_register_t *reg, unsigned live) {
 483         return live & (1 << reg->index);
 484 }
 485
 486 #ifdef DEBUG_libfirm
 487 /**
 488  * dump liveness info.
 489  */
 490 static vfp_dump_live(unsigned live) {
 491         int i;
 492
 493         DB((dbg, LEVEL_2, "Live registers here: \n"));
 494         for (i = 0; i < 8; ++i) {
 495                 if (live & (1 << i)) {
 496                         DB((dbg, LEVEL_2, " vf%d", i));
 497                 }
 498         }
 499         DB((dbg, LEVEL_2, "\n"));
 500 }
 501 #endif /* DEBUG_libfirm */
 502
 503 /* --------------------------------- simulators ---------------------------------------- */
 504
 505 #define XCHG(a, b) do { int t =(a); (a) = (b); (b) = t; } while (0)
 506
 507 /**
 508  * Simulate a virtual binop
 509  */
 510 static void sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const exchange_tmpl *tmpl) {
 511         int op1_idx, op2_idx = -1;
 512         int out_idx, do_pop =0;
 513         ia32_attr_t *attr;
 514         ir_op *dst;
 515         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
 516         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
 517         const arch_register_t *out = arch_get_irn_register(env, n);
 518         unsigned live = vfp_liveness_nodes_live_at(env, n);
 519
 520         DB((dbg, LEVEL_1, ">>> %s %s, %s -> %s\n", get_irn_opname(n), op1->name, op2->name, out->name));
 521   DEBUG_ONLY(vfp_dump_live(live));
 522
 523         op1_idx = x87_on_stack(state, op1);
 524
 525         if (op2->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]) {
 526                 /* second operand is a vfp register */
 527                 op2_idx = x87_on_stack(state, op2);
 528
 529                 if (is_vfp_live(op1, live)) {
 530                         /* first operand is live */
 531
 532                         if (is_vfp_live(op2, live)) {
 533                                 /* both operands are live: push the first one */
 534                                 x87_create_fpush(env, state, n, op1_idx, BINOP_IDX_1);
 535                                 out_idx = op1_idx = 0;
 536                                 ++op2_idx;
 537                                 dst = tmpl->normal_op;
 538                                 do_pop = 0;
 539                         }
 540                         else {
 541                                 /* first live, second operand is dead here, bring it to tos */
 542                                 if (op2_idx != 0) {
 543                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 544                                         if (op1_idx == 0)
 545                                                 op1_idx = op2_idx;
 546                                 }
 547                                 op2_idx = out_idx = 0;
 548                                 dst = tmpl->normal_op;
 549                                 do_pop = 0;
 550                         }
 551                 }
 552                 else {
 553                         /* first operand is dead */
 554                         if (is_vfp_live(op2, live)) {
 555                                 /* second operand is live: bring first to tos */
 556                                 if (op1_idx != 0) {
 557                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 558                                         if (op2_idx == 0)
 559                                                 op2_idx = op1_idx;
 560                                 }
 561                                 op1_idx = out_idx = 0;
 562                                 dst = tmpl->normal_op;
 563                                 do_pop = 0;
 564                         }
 565                         else {
 566                                 /* both operands are dead here, pop them from the stack */
 567                                 if (op1_idx == 0) {
 568                                         out_idx = op2_idx;
 569                                         XCHG(op1_idx, op2_idx);
 570                                         dst = tmpl->reverse_pop_op;
 571                                         do_pop = 1;
 572                                 }
 573                                 else if (op2_idx == 0) {
 574                                         out_idx = op1_idx;
 575                                         dst = tmpl->normal_pop_op;
 576                                         do_pop = 1;
 577                                 }
 578                                 else {
 579                                         /* bring the second on top */
 580                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 581                                         op2_idx = 0;
 582                                         out_idx = op1_idx;
 583                                         dst = tmpl->normal_pop_op;
 584                                         do_pop = 1;
 585                                 }
 586                         }
 587                 }
 588         }
 589         else {
 590                 /* second operand is an address mode */
 591                 if (is_vfp_live(op1, live)) {
 592                         /* first operand is live: push it here */
 593                         x87_create_fpush(env, state, n, op1_idx, BINOP_IDX_1);
 594                 }
 595                 else {
 596                         /* first operand is dead: bring it to tos */
 597                         if (op1_idx != 0)
 598                                 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 599                 }
 600                 op1_idx = out_idx = 0;
 601                 dst = tmpl->normal_op;
 602                 do_pop = 0;
 603         }
 604
 605         x87_set_reg(state, out, out_idx);
 606         if (do_pop)
 607                 x87_pop(state);
 608
 609         /* patch the operation */
 610         n->op = dst;
 611         attr = get_ia32_attr(n);
 612         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 613         attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
 614         attr->x87[2] = out = &ia32_st_regs[out_idx];
 615
 616         DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n), op1->name, op2->name, out->name));
 617 }
 618
 619 /**
 620  * Simulate a virtual Unop
 621  */
 622 static void sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 623         int op1_idx, out_idx;
 624         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, UNOP_IDX));
 625         const arch_register_t *out = arch_get_irn_register(env, n);
 626         ia32_attr_t *attr;
 627         unsigned live = vfp_liveness_nodes_live_at(env, n);
 628
 629         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name));
 630   DEBUG_ONLY(vfp_dump_live(live));
 631
 632         op1_idx = x87_on_stack(state, op1);
 633
 634         if (is_vfp_live(op1, live)) {
 635                 /* push the operand here */
 636                 x87_create_fpush(env, state, n, op1_idx, UNOP_IDX);
 637         }
 638         else {
 639                 /* operand is dead, bring it to tos */
 640                 if (op1_idx != 0)
 641                         x87_create_fxch(state, n, op1_idx, UNOP_IDX);
 642         }
 643
 644         x87_set_tos_reg(state, out);
 645         op1_idx = out_idx = 0;
 646         n->op = op;
 647         attr = get_ia32_attr(n);
 648         attr->x87[0] = op1 = &ia32_st_regs[0];
 649         attr->x87[2] = out = &ia32_st_regs[0];
 650         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
 651 }
 652
 653 /**
 654  * Simulate a virtual Load instructions
 655  */
 656 static void sim_load(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 657         const arch_register_t *out = arch_get_irn_register(env, n);
 658         ia32_attr_t *attr;
 659
 660         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name));
 661         x87_push(state, out);
 662         n->op = op;
 663         attr = get_ia32_attr(n);
 664         attr->x87[2] = out = &ia32_st_regs[0];
 665         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
 666 }
 667
 668 /**
 669  * Simulate a virtual Store
 670  */
 671 static void sim_fst(x87_state *state, ir_node *n, const arch_env_t *env) {
 672         int op2_idx;
 673         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, STORE_VAL_IDX));
 674         ia32_attr_t *attr;
 675         unsigned live = vfp_liveness_nodes_live_at(env, n);
 676
 677         op2_idx = x87_on_stack(state, op2);
 678
 679         DB((dbg, LEVEL_1, ">>> %s %s ->\n", get_irn_opname(n), op2->name));
 680
 681         /* we can only store the tos to memory */
 682         if (op2_idx != 0)
 683                 x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX);
 684
 685         if (is_vfp_live(op2, live))
 686                 n->op = op_ia32_fst;
 687         else {
 688                 x87_pop(state);
 689                 n->op = op_ia32_fstp;
 690         }
 691
 692         attr = get_ia32_attr(n);
 693         attr->x87[1] = op2 = &ia32_st_regs[0];
 694         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), op2->name));
 695 }
 696
 697 #define _GEN_BINOP(op, rev) \
 698 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 699         exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \
 700         sim_binop(state, n, env, &tmpl); \
 701 }
 702
 703 #define GEN_BINOP(op)     _GEN_BINOP(op, op)
 704 #define GEN_BINOPR(op)  _GEN_BINOP(op, op##r)
 705
 706 #define GEN_LOAD2(op, nop) \
 707 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 708         sim_load(state, n, env, op_ia32_##nop); \
 709 }
 710
 711 #define GEN_LOAD(op)    GEN_LOAD2(op, op)
 712
 713 #define GEN_UNOP(op) \
 714 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 715         sim_unop(state, n, env, op_ia32_##op); \
 716 }
 717
 718 /* all stubs */
 719 GEN_BINOP(fadd)
 720 GEN_BINOPR(fsub)
 721 GEN_BINOP(fmul)
 722 GEN_BINOPR(fdiv)
 723
 724 GEN_LOAD(fld)
 725 GEN_LOAD(fldz)
 726 GEN_LOAD(fld1)
 727 GEN_LOAD2(fConst, fldConst)
 728
 729 GEN_UNOP(fabs)
 730 GEN_UNOP(fchs)
 731 GEN_UNOP(fsin)
 732 GEN_UNOP(fcos)
 733 GEN_UNOP(fsqrt)
 734
 735 /**
 736  * Simulate a virtual Copy
 737  */
 738 static void sim_Copy(x87_state *state, ir_node *n, const arch_env_t *env) {
 739         ir_mode *mode = get_irn_mode(n);
 740
 741         if (mode_is_float(mode)) {
 742                 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, 0));
 743                 const arch_register_t *out = arch_get_irn_register(env, n);
 744                 ir_node *node, *next;
 745                 ia32_attr_t *attr;
 746                 int op1_idx;
 747                 unsigned live = vfp_liveness_nodes_live_at(env, n);
 748
 749                 op1_idx = x87_on_stack(state, op1);
 750
 751                 DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(n), op1->name, out->name));
 752           DEBUG_ONLY(vfp_dump_live(live));
 753
 754                 if (is_vfp_live(op1, live)) {
 755                         /* operand is still live,a real copy */
 756                         x87_push(state, out);
 757
 758                         node = new_rd_ia32_fpush(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
 759                         arch_set_irn_register(env, node, out);
 760
 761                         attr = get_ia32_attr(node);
 762                         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 763                         attr->x87[2] = out = &ia32_st_regs[0];
 764
 765                         next = sched_next(n);
 766                         sched_remove(n);
 767                         exchange(n, node);
 768                         sched_add_before(next, node);
 769                         DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(node), op1->name, out->name));
 770                 }
 771                 else {
 772                         /* just a virtual copy */
 773                         x87_set_reg(state, out, op1_idx);
 774                         sched_remove(n);
 775                         DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n)));
 776                 }
 777         }
 778 }
 779
 780 /**
 781  * Run a simulation and fix all virtual instructions for a block.
 782  *
 783  * @return non-zero if simulation is complete,
 784  *         zero if the simulation must be rerun
 785  */
 786 static int x87_simulate_block(x87_simulator *sim, ir_node *block) {
 787         ir_node *n, *next;
 788         blk_state *bl_state = x87_get_bl_state(sim, block);
 789         x87_state *state = bl_state->begin;
 790         const ir_edge_t *edge;
 791         ir_node *start_block;
 792
 793         /* if we have no assigned start state, we must wait ... */
 794         if (! state)
 795                 return 0;
 796
 797         assert(bl_state->end == NULL);
 798
 799         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
 800
 801         /* beware, n might changed */
 802         for (n = sched_first(block); !sched_is_end(n); n = next) {
 803                 ir_op *op = get_irn_op(n);
 804
 805                 next = sched_next(n);
 806                 if (op->ops.generic) {
 807                         sim_func func = (sim_func)op->ops.generic;
 808
 809                         /* have work to do */
 810                         if (state == bl_state->begin) {
 811                                 /* create a new state, will be changed */
 812                                 state = x87_clone_state(sim, state);
 813                         }
 814
 815                         /* simulate it */
 816                         (*func)(state, n, sim->env);
 817                 }
 818         }
 819
 820         start_block = get_irg_start_block(get_irn_irg(block));
 821
 822         /* check if the state must be shuffled */
 823         foreach_block_succ(block, edge) {
 824                 ir_node *succ = get_edge_src_irn(edge);
 825                 blk_state *succ_state = x87_get_bl_state(sim, succ);
 826
 827                 if (succ_state->begin && succ != start_block) {
 828                         /* There is already a begin state for this block, bad.
 829                            Do the necessary permutations.
 830                            Note that critical edges are removed, so this is always possible. */
 831                         x87_shuffle(sim, block, state, succ_state->begin);
 832
 833                         /* Note further, that there can be only one such situation,
 834                            so we can break here. */
 835                         break;
 836                 }
 837         }
 838         bl_state->end = state;
 839
 840         /* now propagate the state to all successor blocks */
 841         foreach_block_succ(block, edge) {
 842                 ir_node *succ = get_edge_src_irn(edge);
 843                 blk_state *succ_state = x87_get_bl_state(sim, succ);
 844
 845                 if (! succ_state->begin)
 846                         succ_state->begin = state;
 847         }
 848
 849         return 1;
 850 }
 851
 852 /**
 853  * Create a new x87 simulator.
 854  */
 855 static void x87_init_simulator(x87_simulator *sim, const arch_env_t *env) {
 856         obstack_init(&sim->obst);
 857         sim->blk_states = pmap_create();
 858         sim->env        = env;
 859
 860   FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
 861         firm_dbg_set_mask(dbg, SET_LEVEL_2);
 862
 863         DB((dbg, LEVEL_1, "x87 Simulator started\n"));
 864
 865   /* set the generic function pointer of instruction we must simulate */
 866         clear_irp_opcodes_generic_func();
 867
 868 #define ASSOC(op)           (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
 869 #define ASSOC_BE(op)    (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
 870         ASSOC(fConst);
 871         ASSOC(fld);
 872         ASSOC(fld1);
 873         ASSOC(fldz);
 874         ASSOC(fadd);
 875         ASSOC(fsub);
 876         ASSOC(fmul);
 877         ASSOC(fdiv);
 878         ASSOC(fldz);
 879         ASSOC(fabs);
 880         ASSOC(fchs);
 881         ASSOC(fsin);
 882         ASSOC(fcos);
 883         ASSOC(fsqrt);
 884         ASSOC(fst);
 885         ASSOC_BE(Copy);
 886 #undef ASSOC_BE
 887 #undef ASSOC
 888 }
 889
 890 /**
 891  * Destroy a x87 simulator.
 892  */
 893 static void x87_destroy_simulator(x87_simulator *sim) {
 894         pmap_destroy(sim->blk_states);
 895         obstack_free(&sim->obst, NULL);
 896         DB((dbg, LEVEL_1, "x87 Simulator stopped\n"));
 897 }
 898
 899 /**
 900  * Run a simulation and fix all virtual instructions for a graph.
 901  *
 902  * Needs a block-schedule.
 903  */
 904 void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) {
 905         ir_node *block, *start_block;
 906         pdeq *worklist;
 907         blk_state *bl_state;
 908         x87_simulator sim;
 909         int i;
 910
 911   /* we need liveness info for the current graph */
 912         be_liveness(irg);
 913
 914   /* create the simulator */
 915         x87_init_simulator(&sim, env);
 916
 917         start_block = get_irg_start_block(irg);
 918         bl_state = x87_get_bl_state(&sim, start_block);
 919
 920         /* start with the empty state */
 921         bl_state->begin = empty;
 922
 923         worklist = new_pdeq();
 924
 925         /* create the worklist for the schedule. */
 926         for (i = 0; i < ARR_LEN(blk_list); ++i)
 927                 pdeq_putr(worklist, blk_list[i]);
 928
 929         /* iterate */
 930         do {
 931                 block = pdeq_getl(worklist);
 932                 if (! x87_simulate_block(&sim, block)) {
 933                         pdeq_putr(worklist, block);
 934                         continue;
 935                 }
 936         } while (! pdeq_empty(worklist));
 937
 938   /* kill it */
 939         x87_destroy_simulator(&sim);
 940 }