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  * Check if the state is empty.
 112  */
 113 static int x87_state_is_empty(const x87_state *state) {
 114         return state->depth == 0;
 115 }
 116
 117 /**
 118  * Return the virtual register index at st(pos).
 119  */
 120 static int x87_get_st_reg(const x87_state *state, int pos) {
 121         assert(pos < state->depth);
 122         return state->st[MASK_TOS(state->tos + pos)].reg_idx;
 123 }
 124
 125 /**
 126  * Return the node at st(pos).
 127  */
 128 static ir_node *x87_get_st_node(const x87_state *state, int pos) {
 129         assert(pos < state->depth);
 130         return state->st[MASK_TOS(state->tos + pos)].node;
 131 }
 132
 133 #ifdef DEBUG_libfirm
 134 /**
 135  * Dump the stack for debugging.
 136  */
 137 static void x87_dump_stack(const x87_state *state) {
 138         int i;
 139
 140         for (i = state->depth - 1; i >= 0; --i) {
 141                 DB((dbg, LEVEL_2, "vf%d ", x87_get_st_reg(state, i)));
 142         }
 143         DB((dbg, LEVEL_2, "<-- TOS\n"));
 144 }
 145 #endif /* DEBUG_libfirm */
 146
 147 /**
 148  * Set a virtual register to st(pos)
 149  */
 150 static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) {
 151         assert(0 < state->depth);
 152         state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx;
 153         state->st[MASK_TOS(state->tos + pos)].node    = node;
 154
 155         DB((dbg, LEVEL_2, "After SET_REG:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 156 }
 157
 158 /**
 159  * Set the tos virtual register
 160  */
 161 static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node) {
 162         x87_set_st(state, reg_idx, node, 0);
 163 }
 164
 165 /**
 166  * Flush the x87 stack.
 167  */
 168 static void x87_flush(x87_state *state) {
 169         state->depth = 0;
 170         state->tos   = 0;
 171 }
 172
 173 /**
 174  * Swap st(0) with st(pos).
 175  */
 176 static void x87_fxch(x87_state *state, int pos) {
 177         st_entry entry;
 178         assert(pos < state->depth);
 179
 180         entry = state->st[MASK_TOS(state->tos + pos)];
 181         state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
 182         state->st[MASK_TOS(state->tos)] = entry;
 183
 184         DB((dbg, LEVEL_2, "After FXCH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 185 }
 186
 187 /**
 188  * Convert a virtual register to the stack index.
 189  * Return -1 if the virtual register was not found.
 190  */
 191 static int x87_on_stack(const x87_state *state, int reg_idx) {
 192         int i, tos = state->tos;
 193
 194         for (i = 0; i < state->depth; ++i)
 195                 if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx)
 196                         return i;
 197         return -1;
 198 }
 199
 200 /**
 201  * Push a virtual Register onto the stack.
 202  */
 203 static void x87_push(x87_state *state, int reg_idx, ir_node *node) {
 204         assert(x87_on_stack(state, reg_idx) == -1 && "double push");
 205         assert(state->depth < N_x87_REGS && "stack overrun");
 206
 207         ++state->depth;
 208         state->tos = MASK_TOS(state->tos - 1);
 209         state->st[state->tos].reg_idx = reg_idx;
 210         state->st[state->tos].node    = node;
 211
 212         DB((dbg, LEVEL_2, "After PUSH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 213 }
 214
 215 /**
 216  * Pop a virtual Register from the stack.
 217  */
 218 static void x87_pop(x87_state *state) {
 219         assert(state->depth > 0 && "stack underrun");
 220
 221         --state->depth;
 222         state->tos = MASK_TOS(state->tos + 1);
 223
 224         DB((dbg, LEVEL_2, "After POP:\n ")); DEBUG_ONLY(x87_dump_stack(state));
 225 }
 226
 227 /**
 228  * Returns the block state of a block.
 229  */
 230 static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) {
 231         pmap_entry *entry = pmap_find(sim->blk_states, block);
 232
 233         if (! entry) {
 234                 blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
 235                 bl_state->begin = NULL;
 236                 bl_state->end   = NULL;
 237
 238                 pmap_insert(sim->blk_states, block, bl_state);
 239                 return bl_state;
 240         }
 241
 242         return entry ? PTR_TO_BLKSTATE(entry->value) : NULL;
 243 }
 244
 245 /**
 246  * Create a new x87 state.
 247  */
 248 static x87_state *x87_alloc_state(x87_simulator *sim) {
 249         x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
 250         return res;
 251 }
 252
 253 /**
 254  * Create a new empty x87 state.
 255  */
 256 static x87_state *x87_alloc_empty_state(x87_simulator *sim) {
 257         x87_state *res = x87_alloc_state(sim);
 258
 259         x87_flush(res);
 260         return res;
 261 }
 262
 263 /**
 264  * Clone a x87 state.
 265  */
 266 static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) {
 267         x87_state *res = x87_alloc_state(sim);
 268
 269         memcpy(res, src, sizeof(*res));
 270         return res;
 271 }
 272
 273 /**
 274  * Patch a virtual instruction into a x87 one and return
 275  * the value node.
 276  */
 277 static ir_node *x87_patch_insn(ir_node *n, ir_op *op) {
 278         ir_mode *mode = get_irn_mode(n);
 279         ir_node *res = n;
 280
 281         set_irn_op(n, op);
 282
 283         if (mode == mode_T) {
 284                 /* patch all Proj's */
 285                 const ir_edge_t *edge;
 286
 287                 foreach_out_edge(n, edge) {
 288                         ir_node *proj = get_edge_src_irn(edge);
 289                         if (is_Proj(proj)) {
 290                                 mode = get_irn_mode(proj);
 291                                 if (mode_is_float(mode)) {
 292                                         res = proj;
 293                                         set_irn_mode(proj, mode_E);
 294                                 }
 295                         }
 296                 }
 297         }
 298         else if (mode_is_float(mode))
 299                 set_irn_mode(n, mode_E);
 300         return res;
 301 }
 302
 303 /* -------------- x87 perm --------------- */
 304
 305 /**
 306  * Creates a fxch for shuffle.
 307  *
 308  * @param state     the x87 state
 309  * @param pos       parameter for fxch
 310  * @param dst_block the block of the user
 311  *
 312  * Creates a new fxch node and reroute the user of the old node
 313  * to the fxch.
 314  *
 315  * @return the fxch node
 316  */
 317 static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block, ir_node *dst_block)
 318 {
 319         const ir_edge_t *edge;
 320         ir_node *n = x87_get_st_node(state, pos);
 321         ir_node *user = NULL;
 322         ir_node *fxch;
 323         int node_idx;
 324         ia32_attr_t *attr;
 325
 326         if (block == get_nodes_block(n)) {
 327                 /* this is a node from out block: change it's user */
 328                 foreach_out_edge(n, edge) {
 329                         ir_node *succ = get_edge_src_irn(edge);
 330
 331                         if (is_Phi(succ) && get_nodes_block(succ) == dst_block) {
 332                                 user = succ;
 333                                 node_idx = get_edge_src_pos(edge);
 334                                 break;
 335                         }
 336                 }
 337                 assert(user);
 338         }
 339
 340         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(block), block, n, get_irn_mode(n));
 341         attr = get_ia32_attr(fxch);
 342         attr->x87[0] = &ia32_st_regs[pos];
 343         attr->x87[2] = &ia32_st_regs[0];
 344
 345         if (user) {
 346                 DB((dbg, LEVEL_2, "%+F replaced input %d of %+F\n", fxch, node_idx, user));
 347                 set_irn_n(user, node_idx, fxch);
 348         }
 349         else {
 350                 /*
 351                  * This is a node from a dominator block. Changing it's user might be wrong,
 352                  * so just keep it alive.
 353                  * The "right" solution would require a new Phi, but we don't care here.
 354                  */
 355                 keep_alive(fxch);
 356         }
 357
 358         x87_fxch(state, pos);
 359         return fxch;
 360 }
 361
 362 /**
 363  * Calculate the necessary permutations to reach dst_state.
 364  *
 365  * These permutations are done with fxch instructions and placed
 366  * at the end of the block.
 367  *
 368  * Note that critical edges are removed here, so we need only
 369  * a shuffle if the current block has only one successor.
 370  *
 371  * @param sim        the simulator handle
 372  * @param block      the current block
 373  * @param state      the current x87 stack state, might be modified
 374  * @param dst_block  the destination block
 375  * @param dst_state  destination state
 376  *
 377  * @return state
 378  */
 379 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, ir_node *dst_block, const x87_state *dst_state) {
 380         int i, n_rings, k, ri;
 381         unsigned rings[4], all_mask;
 382         char ring_idx[4][8];
 383         ir_node *fxch;
 384         ir_node *before, *after;
 385
 386         assert(state->depth == dst_state->depth);
 387
 388         /* Some mathematics here:
 389            If we have a ring of lenght n that includes the tos,
 390            we need n-1 exchange operations.
 391            We can always add the tos and restore it, so we need
 392            n+1 exchange operations for a ring not containing the tos.
 393            So, the maximum of needed operations is for a ring of 7
 394            not including the tos == 8.
 395            This is so same number of ops we would need for store,
 396            so exchange is cheaper (we save the loads).
 397            On the other hand, we might need an additional exchange
 398            in the next block to bring one operand on top, so the
 399            number of ops in the first case is identical.
 400                  Further, no more than 4 rings can exists.
 401         */
 402         all_mask = (1 << (state->depth)) - 1;
 403
 404         for (n_rings = 0; all_mask; ++n_rings) {
 405                 int src_idx, dst_idx;
 406
 407                 /* find the first free slot */
 408                 for (i = 0; i < state->depth; ++i) {
 409                         if (all_mask & (1 << i)) {
 410                                 all_mask &= ~(1 << i);
 411
 412                                 /* check if there are differences here */
 413                                 if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
 414                                         break;
 415                         }
 416                 }
 417
 418                 if (! all_mask) {
 419                         /* no more rings found */
 420                         break;
 421                 }
 422
 423                 k = 0;
 424                 rings[n_rings] = (1 << i);
 425                 ring_idx[n_rings][k++] = i;
 426                 for (src_idx = i; ; src_idx = dst_idx) {
 427                         dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
 428
 429                         if ((all_mask & (1 << dst_idx)) == 0)
 430                                 break;
 431
 432                         ring_idx[n_rings][k++] = dst_idx;
 433                         rings[n_rings] |=  (1 << dst_idx);
 434                         all_mask       &= ~(1 << dst_idx);
 435                 }
 436                 ring_idx[n_rings][k] = -1;
 437         }
 438
 439         if (n_rings <= 0) {
 440                 /* no permutation needed */
 441                 return state;
 442         }
 443
 444         /* Hmm: permutation needed */
 445         DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
 446         DEBUG_ONLY(x87_dump_stack(state));
 447         DB((dbg, LEVEL_2, "                  to\n"));
 448         DEBUG_ONLY(x87_dump_stack(dst_state));
 449
 450
 451 #ifdef DEBUG_libfirm
 452         DB((dbg, LEVEL_2, "Need %d rings\n", n_rings));
 453         for (ri = 0; ri < n_rings; ++ri) {
 454                 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
 455                 for (k = 0; ring_idx[ri][k] != -1; ++k)
 456                         DB((dbg, LEVEL_2, " st%d ->", ring_idx[ri][k]));
 457                 DB((dbg, LEVEL_2, "\n"));
 458         }
 459 #endif
 460
 461         after = NULL;
 462
 463         /*
 464          * Find the place node must be insert.
 465          * We have only one successor block, so the last instruction should
 466          * be a jump.
 467          */
 468         before = sched_last(block);
 469         assert(is_cfop(before));
 470
 471         /* now do the permutations */
 472         for (ri = 0; ri < n_rings; ++ri) {
 473                 if ((rings[ri] & 1) == 0) {
 474                         /* this ring does not include the tos */
 475                         fxch = x87_fxch_shuffle(state, ring_idx[ri][0], block, dst_block);
 476                         if (after)
 477                                 sched_add_after(after, fxch);
 478                         else
 479                                 sched_add_before(before, fxch);
 480                         after = fxch;
 481                 }
 482                 for (k = 1; ring_idx[ri][k] != -1; ++k) {
 483                         fxch = x87_fxch_shuffle(state, ring_idx[ri][k], block, dst_block);
 484                         if (after)
 485                                 sched_add_after(after, fxch);
 486                         else
 487                                 sched_add_before(before, fxch);
 488                         after = fxch;
 489                 }
 490                 if ((rings[ri] & 1) == 0) {
 491                         /* this ring does not include the tos */
 492                         fxch = x87_fxch_shuffle(state, ring_idx[ri][0], block, dst_block);
 493                         sched_add_after(after, fxch);
 494                 }
 495         }
 496         return state;
 497 }
 498
 499 /**
 500  * Create a fxch before node n.
 501  */
 502 static void x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) {
 503         ir_node *fxch, *pred;
 504         ia32_attr_t *attr;
 505
 506         x87_fxch(state, pos);
 507
 508         pred = get_irn_n(n, op_idx);
 509         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 510         attr = get_ia32_attr(fxch);
 511         attr->x87[0] = &ia32_st_regs[pos];
 512         attr->x87[2] = &ia32_st_regs[0];
 513         set_irn_n(n, op_idx, fxch);
 514
 515         sched_add_before(n, fxch);
 516         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
 517 }
 518
 519 /**
 520  * Create a fpush before node n.
 521  */
 522 static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n, int pos, int op_idx) {
 523         ir_node *fpush, *pred;
 524         ia32_attr_t *attr;
 525         const arch_register_t *out = arch_get_irn_register(env, n);
 526
 527         x87_push(state, arch_register_get_index(out), n);
 528
 529         pred = get_irn_n(n, op_idx);
 530         fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 531         attr = get_ia32_attr(fpush);
 532         attr->x87[0] = &ia32_st_regs[pos];
 533         attr->x87[2] = &ia32_st_regs[0];
 534         set_irn_n(n, op_idx, fpush);
 535
 536         sched_add_before(n, fpush);
 537         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
 538 }
 539
 540 /* --------------------------------- liveness ------------------------------------------ */
 541
 542 /**
 543  * The liveness transfer function.
 544  * Updates a live set over a single step from a given node to its predecessor.
 545  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 546  * @param arch_env The architecture environment.
 547  * @param irn      The node at which liveness should be computed.
 548  * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 549  *                 the registers live after irn.
 550  * @return live.
 551  */
 552 static unsigned vfp_liveness_transfer(const arch_env_t *arch_env, ir_node *irn, unsigned live)
 553 {
 554         int i, n;
 555         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 556
 557         if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 558                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 559                         live &= ~(1 << reg->index);
 560         }
 561
 562         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 563                 ir_node *op = get_irn_n(irn, i);
 564
 565                 if (mode_is_float(get_irn_mode(op)) && arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
 566                         const arch_register_t *reg = arch_get_irn_register(arch_env, op);
 567                         live |= 1 << reg->index;
 568                 }
 569         }
 570
 571         return live;
 572 }
 573
 574 /**
 575  * Put all live virtual registers at the end of a block into a bitset.
 576  * @param arch_env The architecture environment.
 577  * @param bl       The block.
 578  * @return The live bitset.
 579  */
 580 static unsigned vfp_liveness_end_of_block(const arch_env_t *arch_env, const ir_node *bl)
 581 {
 582         irn_live_t *li;
 583         unsigned live = 0;
 584         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 585
 586         live_foreach(bl, li) {
 587                 ir_node *irn = (ir_node *) li->irn;
 588                 if (live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 589                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 590                         live |= 1 << reg->index;
 591                 }
 592         }
 593
 594         return live;
 595 }
 596
 597 /**
 598  * Compute a bitset of registers which are live at another node.
 599  * @param arch_env The architecture environment.
 600  * @param pos      The node.
 601  * @return The live bitset.
 602  */
 603 static unsigned vfp_liveness_nodes_live_at(const arch_env_t *arch_env, const ir_node *pos)
 604 {
 605         const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
 606         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 607         ir_node *irn;
 608         unsigned live;
 609
 610         live = vfp_liveness_end_of_block(arch_env, bl);
 611
 612         sched_foreach_reverse(bl, irn) {
 613                 /*
 614                  * If we encounter the node we want to insert the Perm after,
 615                  * exit immediately, so that this node is still live
 616                  */
 617                 if (irn == pos)
 618                         return live;
 619
 620                 live = vfp_liveness_transfer(arch_env, irn, live);
 621         }
 622
 623         return live;
 624 }
 625
 626 /**
 627  * Returns true if a register is live in a set.
 628  */
 629 static unsigned is_vfp_live(const arch_register_t *reg, unsigned live) {
 630         return live & (1 << reg->index);
 631 }
 632
 633 #ifdef DEBUG_libfirm
 634 /**
 635  * dump liveness info.
 636  */
 637 static void vfp_dump_live(unsigned live) {
 638         int i;
 639
 640         DB((dbg, LEVEL_2, "Live registers here: \n"));
 641         for (i = 0; i < 8; ++i) {
 642                 if (live & (1 << i)) {
 643                         DB((dbg, LEVEL_2, " vf%d", i));
 644                 }
 645         }
 646         DB((dbg, LEVEL_2, "\n"));
 647 }
 648 #endif /* DEBUG_libfirm */
 649
 650 /* --------------------------------- simulators ---------------------------------------- */
 651
 652 #define XCHG(a, b) do { int t =(a); (a) = (b); (b) = t; } while (0)
 653
 654 /**
 655  * Simulate a virtual binop
 656  */
 657 static void sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const exchange_tmpl *tmpl) {
 658         int op2_idx, op1_idx = -1;
 659         int out_idx, do_pop =0;
 660         ia32_attr_t *attr;
 661         ir_op *dst;
 662         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
 663         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
 664         const arch_register_t *out = arch_get_irn_register(env, n);
 665         unsigned live = vfp_liveness_nodes_live_at(env, n);
 666
 667         DB((dbg, LEVEL_1, ">>> %s %s, %s -> %s\n", get_irn_opname(n),
 668                 arch_register_get_name(op2), arch_register_get_name(op1),
 669                 arch_register_get_name(out)));
 670   DEBUG_ONLY(vfp_dump_live(live));
 671
 672         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 673
 674         if (op1->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]) {
 675                 /* first operand is a vfp register */
 676                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 677
 678                 if (is_vfp_live(op2, live)) {
 679                         /* second operand is live */
 680
 681                         if (is_vfp_live(op1, live)) {
 682                                 /* both operands are live: push the first one */
 683                                 x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
 684                                 out_idx = op2_idx = 0;
 685                                 ++op1_idx;
 686                                 dst = tmpl->normal_op;
 687                                 do_pop = 0;
 688                         }
 689                         else {
 690                                 /* second live, first operand is dead here, bring it to tos */
 691                                 if (op1_idx != 0) {
 692                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 693                                         if (op2_idx == 0)
 694                                                 op2_idx = op1_idx;
 695                                 }
 696                                 op1_idx = out_idx = 0;
 697                                 dst = tmpl->normal_op;
 698                                 do_pop = 0;
 699                         }
 700                 }
 701                 else {
 702                         /* second operand is dead */
 703                         if (is_vfp_live(op1, live)) {
 704                                 /* first operand is live: bring second to tos */
 705                                 if (op2_idx != 0) {
 706                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 707                                         if (op1_idx == 0)
 708                                                 op1_idx = op2_idx;
 709                                 }
 710                                 op2_idx = out_idx = 0;
 711                                 dst = tmpl->normal_op;
 712                                 do_pop = 0;
 713                         }
 714                         else {
 715                                 /* both operands are dead here, pop them from the stack */
 716                                 if (op2_idx == 0) {
 717                                         out_idx = op1_idx;
 718                                         XCHG(op2_idx, op1_idx);
 719                                         dst = tmpl->reverse_pop_op;
 720                                         do_pop = 1;
 721                                 }
 722                                 else if (op1_idx == 0) {
 723                                         out_idx = op2_idx;
 724                                         dst = tmpl->normal_pop_op;
 725                                         do_pop = 1;
 726                                 }
 727                                 else {
 728                                         /* bring the first on top */
 729                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 730                                         op1_idx = 0;
 731                                         out_idx = op2_idx;
 732                                         dst = tmpl->normal_pop_op;
 733                                         do_pop = 1;
 734                                 }
 735                         }
 736                 }
 737         }
 738         else {
 739                 /* first operand is an address mode */
 740                 if (is_vfp_live(op2, live)) {
 741                         /* second operand is live: push it here */
 742                         x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
 743                 }
 744                 else {
 745                         /* second operand is dead: bring it to tos */
 746                         if (op2_idx != 0)
 747                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 748                 }
 749                 op2_idx = out_idx = 0;
 750                 dst = tmpl->normal_op;
 751                 do_pop = 0;
 752         }
 753
 754         x87_set_st(state, arch_register_get_index(out), x87_patch_insn(n, dst), out_idx);
 755         if (do_pop)
 756                 x87_pop(state);
 757
 758         /* patch the operation */
 759         attr = get_ia32_attr(n);
 760         if (op1_idx >= 0)
 761                 attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 762         attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
 763         attr->x87[2] = out = &ia32_st_regs[out_idx];
 764
 765         DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
 766                 arch_register_get_name(op2), arch_register_get_name(op1),
 767                 arch_register_get_name(out)));
 768 }
 769
 770 /**
 771  * Simulate a virtual Unop
 772  */
 773 static void sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 774         int op1_idx, out_idx;
 775         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, UNOP_IDX));
 776         const arch_register_t *out = arch_get_irn_register(env, n);
 777         ia32_attr_t *attr;
 778         unsigned live = vfp_liveness_nodes_live_at(env, n);
 779
 780         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name));
 781   DEBUG_ONLY(vfp_dump_live(live));
 782
 783         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 784
 785         if (is_vfp_live(op1, live)) {
 786                 /* push the operand here */
 787                 x87_create_fpush(env, state, n, op1_idx, UNOP_IDX);
 788         }
 789         else {
 790                 /* operand is dead, bring it to tos */
 791                 if (op1_idx != 0)
 792                         x87_create_fxch(state, n, op1_idx, UNOP_IDX);
 793         }
 794
 795         x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op));
 796         op1_idx = out_idx = 0;
 797         attr = get_ia32_attr(n);
 798         attr->x87[0] = op1 = &ia32_st_regs[0];
 799         attr->x87[2] = out = &ia32_st_regs[0];
 800         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
 801 }
 802
 803 /**
 804  * Simulate a virtual Load instructions
 805  */
 806 static void sim_load(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 807         const arch_register_t *out = arch_get_irn_register(env, n);
 808         ia32_attr_t *attr;
 809
 810         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 811         x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
 812         attr = get_ia32_attr(n);
 813         attr->x87[2] = out = &ia32_st_regs[0];
 814         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 815 }
 816
 817 /**
 818  * Simulate a virtual Store
 819  */
 820 static void sim_store(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op, ir_op *op_p) {
 821         int op2_idx;
 822         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, STORE_VAL_IDX));
 823         ia32_attr_t *attr;
 824         unsigned live = vfp_liveness_nodes_live_at(env, n);
 825
 826         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 827
 828         DB((dbg, LEVEL_1, ">>> %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
 829
 830         /* we can only store the tos to memory */
 831         if (op2_idx != 0)
 832                 x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX);
 833
 834         if (is_vfp_live(op2, live))
 835                 x87_patch_insn(n, op);
 836         else {
 837                 x87_pop(state);
 838                 x87_patch_insn(n, op_p);
 839         }
 840
 841         attr = get_ia32_attr(n);
 842         attr->x87[1] = op2 = &ia32_st_regs[0];
 843         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
 844 }
 845
 846 /**
 847  * Simulate a virtual Phi.
 848  * Just for cosmetic reasons change the mode of Phi nodes to mode_E.
 849  */
 850 static void sim_Phi(x87_state *state, ir_node *n, const arch_env_t *env) {
 851         ir_mode *mode = get_irn_mode(n);
 852
 853         if (mode_is_float(mode))
 854                 set_irn_mode(n, mode_E);
 855 }
 856
 857
 858 #define _GEN_BINOP(op, rev) \
 859 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 860         exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \
 861         sim_binop(state, n, env, &tmpl); \
 862 }
 863
 864 #define GEN_BINOP(op)     _GEN_BINOP(op, op)
 865 #define GEN_BINOPR(op)  _GEN_BINOP(op, op##r)
 866
 867 #define GEN_LOAD2(op, nop) \
 868 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 869         sim_load(state, n, env, op_ia32_##nop); \
 870 }
 871
 872 #define GEN_LOAD(op)    GEN_LOAD2(op, op)
 873
 874 #define GEN_UNOP(op) \
 875 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 876         sim_unop(state, n, env, op_ia32_##op); \
 877 }
 878
 879 #define GEN_STORE(op) \
 880 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 881         sim_store(state, n, env, op_ia32_##op, op_ia32_##op##p); \
 882 }
 883
 884 /* all stubs */
 885 GEN_BINOP(fadd)
 886 GEN_BINOPR(fsub)
 887 GEN_BINOP(fmul)
 888 GEN_BINOPR(fdiv)
 889
 890 GEN_UNOP(fabs)
 891 GEN_UNOP(fchs)
 892 GEN_UNOP(fsin)
 893 GEN_UNOP(fcos)
 894 GEN_UNOP(fsqrt)
 895
 896 GEN_LOAD(fld)
 897 GEN_LOAD(fild)
 898 GEN_LOAD(fldz)
 899 GEN_LOAD(fld1)
 900 GEN_LOAD2(fConst, fldConst)
 901
 902 GEN_STORE(fst)
 903 GEN_STORE(fist)
 904
 905
 906 /**
 907  * Simulate a be_Copy.
 908  */
 909 static void sim_Copy(x87_state *state, ir_node *n, const arch_env_t *env) {
 910         ir_mode *mode = get_irn_mode(n);
 911
 912         if (mode_is_float(mode)) {
 913                 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, 0));
 914                 const arch_register_t *out = arch_get_irn_register(env, n);
 915                 ir_node *node, *next;
 916                 ia32_attr_t *attr;
 917                 int op1_idx;
 918                 unsigned live = vfp_liveness_nodes_live_at(env, n);
 919
 920                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 921
 922                 DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(n),
 923                         arch_register_get_name(op1), arch_register_get_name(out)));
 924           DEBUG_ONLY(vfp_dump_live(live));
 925
 926                 if (is_vfp_live(op1, live)) {
 927                         /* operand is still live,a real copy */
 928                         node = new_rd_ia32_fpush(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
 929                         arch_set_irn_register(env, node, out);
 930
 931                         x87_push(state, arch_register_get_index(out), node);
 932
 933                         attr = get_ia32_attr(node);
 934                         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 935                         attr->x87[2] = out = &ia32_st_regs[0];
 936
 937                         next = sched_next(n);
 938                         sched_remove(n);
 939                         exchange(n, node);
 940                         sched_add_before(next, node);
 941                         DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(node), op1->name, out->name));
 942                 }
 943                 else {
 944                         /* just a virtual copy */
 945                         x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx);
 946                         sched_remove(n);
 947                         DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n)));
 948                         exchange(n, get_unop_op(n));
 949                 }
 950         }
 951 }
 952
 953 /**
 954  * Simulate a be_Call
 955  */
 956 static void sim_Call(x87_state *state, ir_node *n, const arch_env_t *env) {
 957         ir_type *call_tp = be_Call_get_type(n);
 958
 959         /* at the begin of a call the x87 state should be empty */
 960         assert(state->depth == 0 && "stack not empty before call");
 961
 962         /*
 963          * If the called function returns a float, it is returned in st(0).
 964          * This even happens if the return value is NOT used.
 965          * Moreover, only one return result is supported.
 966          */
 967         if (get_method_n_ress(call_tp) > 0) {
 968                 ir_type *res_type = get_method_res_type(call_tp, 0);
 969                 ir_mode *mode     = get_type_mode(res_type);
 970
 971                 if (mode && mode_is_float(mode)) {
 972                         /*
 973                          * TODO: what to push here? The result might be unused and currently
 974                          * we have no possibility to detect this :-(
 975                          */
 976                         x87_push(state, 0, n);
 977                 }
 978         }
 979 }
 980
 981 /**
 982  * Simulate a be_Spill.
 983  */
 984 static void sim_Spill(x87_state *state, ir_node *n, const arch_env_t *env) {
 985         assert(0 && "Spill not lowered");
 986         sim_fst(state, n, env);
 987 }
 988
 989 /**
 990  * Simulate a be_Reload
 991  */
 992 static void sim_Reload(x87_state *state, ir_node *n, const arch_env_t *env) {
 993         assert(0 && "Reload not lowered");
 994         sim_fld(state, n, env);
 995 }
 996
 997 /**
 998  * Run a simulation and fix all virtual instructions for a block.
 999  *
1000  * @return non-zero if simulation is complete,
1001  *         zero if the simulation must be rerun
1002  */
1003 static int x87_simulate_block(x87_simulator *sim, ir_node *block) {
1004         ir_node *n, *next;
1005         blk_state *bl_state = x87_get_bl_state(sim, block);
1006         x87_state *state = bl_state->begin;
1007         const ir_edge_t *edge;
1008         ir_node *start_block;
1009
1010         /* if we have no assigned start state, we must wait ... */
1011         if (! state)
1012                 return 0;
1013
1014         assert(bl_state->end == NULL);
1015
1016         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
1017
1018         /* beware, n might changed */
1019         for (n = sched_first(block); !sched_is_end(n); n = next) {
1020                 ir_op *op = get_irn_op(n);
1021
1022                 next = sched_next(n);
1023                 if (op->ops.generic) {
1024                         sim_func func = (sim_func)op->ops.generic;
1025
1026                         /* have work to do */
1027                         if (state == bl_state->begin) {
1028                                 /* create a new state, will be changed */
1029                                 state = x87_clone_state(sim, state);
1030                         }
1031
1032                         /* simulate it */
1033                         (*func)(state, n, sim->env);
1034                 }
1035         }
1036
1037         start_block = get_irg_start_block(get_irn_irg(block));
1038
1039         /* check if the state must be shuffled */
1040         foreach_block_succ(block, edge) {
1041                 ir_node *succ = get_edge_src_irn(edge);
1042                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1043
1044                 if (succ_state->begin && succ != start_block) {
1045                         /* There is already a begin state for this block, bad.
1046                            Do the necessary permutations.
1047                            Note that critical edges are removed, so this is always possible. */
1048                         x87_shuffle(sim, block, state, succ, succ_state->begin);
1049
1050                         /* Note further, that there can be only one such situation,
1051                            so we can break here. */
1052                         break;
1053                 }
1054         }
1055         bl_state->end = state;
1056
1057         /* now propagate the state to all successor blocks */
1058         foreach_block_succ(block, edge) {
1059                 ir_node *succ = get_edge_src_irn(edge);
1060                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1061
1062                 if (! succ_state->begin)
1063                         succ_state->begin = state;
1064         }
1065
1066         return 1;
1067 }
1068
1069 /**
1070  * Create a new x87 simulator.
1071  */
1072 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env_t *env) {
1073         obstack_init(&sim->obst);
1074         sim->blk_states = pmap_create();
1075         sim->env        = env;
1076
1077         FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
1078         firm_dbg_set_mask(dbg, SET_LEVEL_2);
1079
1080         DB((dbg, LEVEL_1, "--------------------------------\n"
1081                 "x87 Simulator started for %+F\n", irg));
1082
1083   /* set the generic function pointer of instruction we must simulate */
1084         clear_irp_opcodes_generic_func();
1085
1086 #define ASSOC(op)       (op_ ## op)->ops.generic = (op_func)(sim_##op)
1087 #define ASSOC_IA32(op)  (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
1088 #define ASSOC_BE(op)    (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
1089         ASSOC_IA32(fConst);
1090         ASSOC_IA32(fld);
1091         ASSOC_IA32(fild);
1092         ASSOC_IA32(fld1);
1093         ASSOC_IA32(fldz);
1094         ASSOC_IA32(fadd);
1095         ASSOC_IA32(fsub);
1096         ASSOC_IA32(fmul);
1097         ASSOC_IA32(fdiv);
1098         ASSOC_IA32(fldz);
1099         ASSOC_IA32(fabs);
1100         ASSOC_IA32(fchs);
1101         ASSOC_IA32(fsin);
1102         ASSOC_IA32(fcos);
1103         ASSOC_IA32(fsqrt);
1104         ASSOC_IA32(fist);
1105         ASSOC_IA32(fst);
1106         ASSOC_BE(Copy);
1107         ASSOC_BE(Call);
1108         ASSOC_BE(Spill);
1109         ASSOC_BE(Reload);
1110         ASSOC(Phi);
1111 #undef ASSOC_BE
1112 #undef ASSOC_IA32
1113 #undef ASSOC
1114 }
1115
1116 /**
1117  * Destroy a x87 simulator.
1118  */
1119 static void x87_destroy_simulator(x87_simulator *sim) {
1120         pmap_destroy(sim->blk_states);
1121         obstack_free(&sim->obst, NULL);
1122         DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
1123 }
1124
1125 /**
1126  * Run a simulation and fix all virtual instructions for a graph.
1127  *
1128  * Needs a block-schedule.
1129  */
1130 void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) {
1131         ir_node *block, *start_block;
1132         pdeq *worklist;
1133         blk_state *bl_state;
1134         x87_simulator sim;
1135         int i;
1136
1137         /* we need liveness info for the current graph */
1138         be_liveness(irg);
1139
1140         /* create the simulator */
1141         x87_init_simulator(&sim, irg, env);
1142
1143         start_block = get_irg_start_block(irg);
1144         bl_state = x87_get_bl_state(&sim, start_block);
1145
1146         /* start with the empty state */
1147         bl_state->begin = empty;
1148
1149         worklist = new_pdeq();
1150
1151         /* create the worklist for the schedule. */
1152         for (i = 0; i < ARR_LEN(blk_list); ++i)
1153                 pdeq_putr(worklist, blk_list[i]);
1154
1155         /* iterate */
1156         do {
1157                 block = pdeq_getl(worklist);
1158                 if (! x87_simulate_block(&sim, block)) {
1159                         pdeq_putr(worklist, block);
1160                         continue;
1161                 }
1162         } while (! pdeq_empty(worklist));
1163
1164         /* kill it */
1165         x87_destroy_simulator(&sim);
1166 }