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