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         if (user) {
 341                 DB((dbg, LEVEL_2, "%+F replaced input %d of %+F\n", fxch, node_idx, user));
 342                 set_irn_n(user, node_idx, fxch);
 343         }
 344         else {
 345                 /*
 346                  * This is a node from a dominator block. Changing it's user might be wrong,
 347                  * so just keep it alive.
 348                  * The "right" solution would require a new Phi, but we don't care here.
 349                  */
 350                 keep_alive(fxch);
 351         }
 352
 353         x87_fxch(state, pos);
 354         return fxch;
 355 }
 356
 357 /**
 358  * Calculate the necessary permutations to reach dst_state.
 359  *
 360  * These permutations are done with fxch instructions and placed
 361  * at the end of the block.
 362  *
 363  * Note that critical edges are removed here, so we need only
 364  * a shuffle if the current block has only one successor.
 365  *
 366  * @param sim        the simulator handle
 367  * @param block      the current block
 368  * @param state      the current x87 stack state, might be modified
 369  * @param dst_block  the destination block
 370  * @param dst_state  destination state
 371  *
 372  * @return state
 373  */
 374 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, ir_node *dst_block, const x87_state *dst_state) {
 375         int i, n_rings, k, ri;
 376         unsigned rings[4], all_mask;
 377         char ring_idx[4][8];
 378         ir_node *fxch;
 379         ir_node *before, *after;
 380
 381         assert(state->depth == dst_state->depth);
 382
 383         /* Some mathematics here:
 384            If we have a ring of lenght n that includes the tos,
 385            we need n-1 exchange operations.
 386            We can always add the tos and restore it, so we need
 387            n+1 exchange operations for a ring not containing the tos.
 388            So, the maximum of needed operations is for a ring of 7
 389            not including the tos == 8.
 390            This is so same number of ops we would need for store,
 391            so exchange is cheaper (we save the loads).
 392            On the other hand, we might need an additional exchange
 393            in the next block to bring one operand on top, so the
 394            number of ops in the first case is identical.
 395                  Further, no more than 4 rings can exists.
 396         */
 397         all_mask = (1 << (state->depth)) - 1;
 398
 399         for (n_rings = 0; all_mask; ++n_rings) {
 400                 int src_idx, dst_idx;
 401
 402                 /* find the first free slot */
 403                 for (i = 0; i < state->depth; ++i) {
 404                         if (all_mask & (1 << i)) {
 405                                 all_mask &= ~(1 << i);
 406
 407                                 /* check if there are differences here */
 408                                 if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
 409                                         break;
 410                         }
 411                 }
 412
 413                 if (! all_mask) {
 414                         /* no more rings found */
 415                         break;
 416                 }
 417
 418                 k = 0;
 419                 rings[n_rings] = (1 << i);
 420                 ring_idx[n_rings][k++] = i;
 421                 for (src_idx = i; ; src_idx = dst_idx) {
 422                         dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
 423
 424                         if ((all_mask & (1 << dst_idx)) == 0)
 425                                 break;
 426
 427                         ring_idx[n_rings][k++] = dst_idx;
 428                         rings[n_rings] |=  (1 << dst_idx);
 429                         all_mask       &= ~(1 << dst_idx);
 430                 }
 431                 ring_idx[n_rings][k] = -1;
 432         }
 433
 434         if (n_rings <= 0) {
 435                 /* no permutation needed */
 436                 return state;
 437         }
 438
 439         /* Hmm: permutation needed */
 440         DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
 441         DEBUG_ONLY(x87_dump_stack(state));
 442         DB((dbg, LEVEL_2, "                  to\n"));
 443         DEBUG_ONLY(x87_dump_stack(dst_state));
 444
 445
 446 #ifdef DEBUG_libfirm
 447         DB((dbg, LEVEL_2, "Need %d rings\n", n_rings));
 448         for (ri = 0; ri < n_rings; ++ri) {
 449                 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
 450                 for (k = 0; ring_idx[ri][k] != -1; ++k)
 451                         DB((dbg, LEVEL_2, " st%d ->", ring_idx[ri][k]));
 452                 DB((dbg, LEVEL_2, "\n"));
 453         }
 454 #endif
 455
 456         after = NULL;
 457
 458         /*
 459          * Find the place node must be insert.
 460          * We have only one successor block, so the last instruction should
 461          * be a jump.
 462          */
 463         before = sched_last(block);
 464         assert(is_cfop(before));
 465
 466         /* now do the permutations */
 467         for (ri = 0; ri < n_rings; ++ri) {
 468                 if ((rings[ri] & 1) == 0) {
 469                         /* this ring does not include the tos */
 470                         fxch = x87_fxch_shuffle(state, ring_idx[ri][0], block, dst_block);
 471                         if (after)
 472                                 sched_add_after(after, fxch);
 473                         else
 474                                 sched_add_before(before, fxch);
 475                         after = fxch;
 476                 }
 477                 for (k = 1; ring_idx[ri][k] != -1; ++k) {
 478                         fxch = x87_fxch_shuffle(state, ring_idx[ri][k], block, dst_block);
 479                         if (after)
 480                                 sched_add_after(after, fxch);
 481                         else
 482                                 sched_add_before(before, fxch);
 483                         after = fxch;
 484                 }
 485                 if ((rings[ri] & 1) == 0) {
 486                         /* this ring does not include the tos */
 487                         fxch = x87_fxch_shuffle(state, ring_idx[ri][0], block, dst_block);
 488                         sched_add_after(after, fxch);
 489                 }
 490         }
 491         return state;
 492 }
 493
 494 /**
 495  * Create a fxch before node n.
 496  */
 497 static void x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) {
 498         ir_node *fxch, *pred;
 499         ia32_attr_t *attr;
 500
 501         x87_fxch(state, pos);
 502
 503         pred = get_irn_n(n, op_idx);
 504         fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 505         attr = get_ia32_attr(fxch);
 506         attr->x87[0] = &ia32_st_regs[pos];
 507         attr->x87[2] = &ia32_st_regs[0];
 508         set_irn_n(n, op_idx, fxch);
 509
 510         sched_add_before(n, fxch);
 511         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
 512 }
 513
 514 /**
 515  * Create a fpush before node n.
 516  */
 517 static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n, int pos, int op_idx) {
 518         ir_node *fpush, *pred;
 519         ia32_attr_t *attr;
 520         const arch_register_t *out = arch_get_irn_register(env, n);
 521
 522         x87_push(state, arch_register_get_index(out), n);
 523
 524         pred = get_irn_n(n, op_idx);
 525         fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
 526         attr = get_ia32_attr(fpush);
 527         attr->x87[0] = &ia32_st_regs[pos];
 528         attr->x87[2] = &ia32_st_regs[0];
 529         set_irn_n(n, op_idx, fpush);
 530
 531         sched_add_before(n, fpush);
 532         DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
 533 }
 534
 535 /* --------------------------------- liveness ------------------------------------------ */
 536
 537 /**
 538  * The liveness transfer function.
 539  * Updates a live set over a single step from a given node to its predecessor.
 540  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 541  * @param arch_env The architecture environment.
 542  * @param irn      The node at which liveness should be computed.
 543  * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 544  *                 the registers live after irn.
 545  * @return live.
 546  */
 547 static unsigned vfp_liveness_transfer(const arch_env_t *arch_env, ir_node *irn, unsigned live)
 548 {
 549         int i, n;
 550         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 551
 552         if(arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 553                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 554                         live &= ~(1 << reg->index);
 555         }
 556
 557         for(i = 0, n = get_irn_arity(irn); i < n; ++i) {
 558                 ir_node *op = get_irn_n(irn, i);
 559
 560                 if (mode_is_float(get_irn_mode(op)) && arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
 561                         const arch_register_t *reg = arch_get_irn_register(arch_env, op);
 562                         live |= 1 << reg->index;
 563                 }
 564         }
 565
 566         return live;
 567 }
 568
 569 /**
 570  * Put all live virtual registers at the end of a block into a bitset.
 571  * @param arch_env The architecture environment.
 572  * @param bl       The block.
 573  * @return The live bitset.
 574  */
 575 static unsigned vfp_liveness_end_of_block(const arch_env_t *arch_env, const ir_node *bl)
 576 {
 577         irn_live_t *li;
 578         unsigned live = 0;
 579         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 580
 581         live_foreach(bl, li) {
 582                 ir_node *irn = (ir_node *) li->irn;
 583                 if (live_is_end(li) && arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
 584                         const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
 585                         live |= 1 << reg->index;
 586                 }
 587         }
 588
 589         return live;
 590 }
 591
 592 /**
 593  * Compute a bitset of registers which are live at another node.
 594  * @param arch_env The architecture environment.
 595  * @param pos      The node.
 596  * @return The live bitset.
 597  */
 598 static unsigned vfp_liveness_nodes_live_at(const arch_env_t *arch_env, const ir_node *pos)
 599 {
 600         const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
 601         const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
 602         ir_node *irn;
 603         unsigned live;
 604
 605         live = vfp_liveness_end_of_block(arch_env, bl);
 606
 607         sched_foreach_reverse(bl, irn) {
 608                 /*
 609                  * If we encounter the node we want to insert the Perm after,
 610                  * exit immediately, so that this node is still live
 611                  */
 612                 if (irn == pos)
 613                         return live;
 614
 615                 live = vfp_liveness_transfer(arch_env, irn, live);
 616         }
 617
 618         return live;
 619 }
 620
 621 /**
 622  * Returns true if a register is live in a set.
 623  */
 624 static unsigned is_vfp_live(const arch_register_t *reg, unsigned live) {
 625         return live & (1 << reg->index);
 626 }
 627
 628 #ifdef DEBUG_libfirm
 629 /**
 630  * dump liveness info.
 631  */
 632 static vfp_dump_live(unsigned live) {
 633         int i;
 634
 635         DB((dbg, LEVEL_2, "Live registers here: \n"));
 636         for (i = 0; i < 8; ++i) {
 637                 if (live & (1 << i)) {
 638                         DB((dbg, LEVEL_2, " vf%d", i));
 639                 }
 640         }
 641         DB((dbg, LEVEL_2, "\n"));
 642 }
 643 #endif /* DEBUG_libfirm */
 644
 645 /* --------------------------------- simulators ---------------------------------------- */
 646
 647 #define XCHG(a, b) do { int t =(a); (a) = (b); (b) = t; } while (0)
 648
 649 /**
 650  * Simulate a virtual binop
 651  */
 652 static void sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const exchange_tmpl *tmpl) {
 653         int op2_idx, op1_idx = -1;
 654         int out_idx, do_pop =0;
 655         ia32_attr_t *attr;
 656         ir_op *dst;
 657         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
 658         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
 659         const arch_register_t *out = arch_get_irn_register(env, n);
 660         unsigned live = vfp_liveness_nodes_live_at(env, n);
 661
 662         DB((dbg, LEVEL_1, ">>> %s %s, %s -> %s\n", get_irn_opname(n),
 663                 arch_register_get_name(op2), arch_register_get_name(op1),
 664                 arch_register_get_name(out)));
 665   DEBUG_ONLY(vfp_dump_live(live));
 666
 667         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 668
 669         if (op1->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]) {
 670                 /* first operand is a vfp register */
 671                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 672
 673                 if (is_vfp_live(op2, live)) {
 674                         /* second operand is live */
 675
 676                         if (is_vfp_live(op1, live)) {
 677                                 /* both operands are live: push the first one */
 678                                 x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
 679                                 out_idx = op2_idx = 0;
 680                                 ++op1_idx;
 681                                 dst = tmpl->normal_op;
 682                                 do_pop = 0;
 683                         }
 684                         else {
 685                                 /* second live, first operand is dead here, bring it to tos */
 686                                 if (op1_idx != 0) {
 687                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 688                                         if (op2_idx == 0)
 689                                                 op2_idx = op1_idx;
 690                                 }
 691                                 op1_idx = out_idx = 0;
 692                                 dst = tmpl->normal_op;
 693                                 do_pop = 0;
 694                         }
 695                 }
 696                 else {
 697                         /* second operand is dead */
 698                         if (is_vfp_live(op1, live)) {
 699                                 /* first operand is live: bring second to tos */
 700                                 if (op2_idx != 0) {
 701                                         x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 702                                         if (op1_idx == 0)
 703                                                 op1_idx = op2_idx;
 704                                 }
 705                                 op2_idx = out_idx = 0;
 706                                 dst = tmpl->normal_op;
 707                                 do_pop = 0;
 708                         }
 709                         else {
 710                                 /* both operands are dead here, pop them from the stack */
 711                                 if (op2_idx == 0) {
 712                                         out_idx = op1_idx;
 713                                         XCHG(op2_idx, op1_idx);
 714                                         dst = tmpl->reverse_pop_op;
 715                                         do_pop = 1;
 716                                 }
 717                                 else if (op1_idx == 0) {
 718                                         out_idx = op2_idx;
 719                                         dst = tmpl->normal_pop_op;
 720                                         do_pop = 1;
 721                                 }
 722                                 else {
 723                                         /* bring the first on top */
 724                                         x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
 725                                         op1_idx = 0;
 726                                         out_idx = op2_idx;
 727                                         dst = tmpl->normal_pop_op;
 728                                         do_pop = 1;
 729                                 }
 730                         }
 731                 }
 732         }
 733         else {
 734                 /* first operand is an address mode */
 735                 if (is_vfp_live(op2, live)) {
 736                         /* second operand is live: push it here */
 737                         x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
 738                 }
 739                 else {
 740                         /* second operand is dead: bring it to tos */
 741                         if (op2_idx != 0)
 742                                 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
 743                 }
 744                 op2_idx = out_idx = 0;
 745                 dst = tmpl->normal_op;
 746                 do_pop = 0;
 747         }
 748
 749         x87_set_st(state, arch_register_get_index(out), x87_patch_insn(n, dst), out_idx);
 750         if (do_pop)
 751                 x87_pop(state);
 752
 753         /* patch the operation */
 754         attr = get_ia32_attr(n);
 755         if (op1_idx >= 0)
 756                 attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 757         attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
 758         attr->x87[2] = out = &ia32_st_regs[out_idx];
 759
 760         DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
 761                 arch_register_get_name(op2), arch_register_get_name(op1),
 762                 arch_register_get_name(out)));
 763 }
 764
 765 /**
 766  * Simulate a virtual Unop
 767  */
 768 static void sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 769         int op1_idx, out_idx;
 770         const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, UNOP_IDX));
 771         const arch_register_t *out = arch_get_irn_register(env, n);
 772         ia32_attr_t *attr;
 773         unsigned live = vfp_liveness_nodes_live_at(env, n);
 774
 775         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name));
 776   DEBUG_ONLY(vfp_dump_live(live));
 777
 778         op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 779
 780         if (is_vfp_live(op1, live)) {
 781                 /* push the operand here */
 782                 x87_create_fpush(env, state, n, op1_idx, UNOP_IDX);
 783         }
 784         else {
 785                 /* operand is dead, bring it to tos */
 786                 if (op1_idx != 0)
 787                         x87_create_fxch(state, n, op1_idx, UNOP_IDX);
 788         }
 789
 790         x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op));
 791         op1_idx = out_idx = 0;
 792         attr = get_ia32_attr(n);
 793         attr->x87[0] = op1 = &ia32_st_regs[0];
 794         attr->x87[2] = out = &ia32_st_regs[0];
 795         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
 796 }
 797
 798 /**
 799  * Simulate a virtual Load instructions
 800  */
 801 static void sim_load(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
 802         const arch_register_t *out = arch_get_irn_register(env, n);
 803         ia32_attr_t *attr;
 804
 805         DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 806         x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
 807         attr = get_ia32_attr(n);
 808         attr->x87[2] = out = &ia32_st_regs[0];
 809         DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
 810 }
 811
 812 /**
 813  * Simulate a virtual Store
 814  */
 815 static void sim_fst(x87_state *state, ir_node *n, const arch_env_t *env) {
 816         int op2_idx;
 817         const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, STORE_VAL_IDX));
 818         ia32_attr_t *attr;
 819         unsigned live = vfp_liveness_nodes_live_at(env, n);
 820
 821         op2_idx = x87_on_stack(state, arch_register_get_index(op2));
 822
 823         DB((dbg, LEVEL_1, ">>> %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
 824
 825         /* we can only store the tos to memory */
 826         if (op2_idx != 0)
 827                 x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX);
 828
 829         if (is_vfp_live(op2, live))
 830                 x87_patch_insn(n, op_ia32_fst);
 831         else {
 832                 x87_pop(state);
 833                 x87_patch_insn(n, op_ia32_fstp);
 834         }
 835
 836         attr = get_ia32_attr(n);
 837         attr->x87[1] = op2 = &ia32_st_regs[0];
 838         DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
 839 }
 840
 841 /**
 842  * Simulate a virtual Phi.
 843  * Just for cosmetic reasons change the mode of Phi nodes to mode_E.
 844  */
 845 static void sim_Phi(x87_state *state, ir_node *n, const arch_env_t *env) {
 846         ir_mode *mode = get_irn_mode(n);
 847
 848         if (mode_is_float(mode))
 849                 set_irn_mode(n, mode_E);
 850 }
 851
 852
 853 #define _GEN_BINOP(op, rev) \
 854 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 855         exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \
 856         sim_binop(state, n, env, &tmpl); \
 857 }
 858
 859 #define GEN_BINOP(op)     _GEN_BINOP(op, op)
 860 #define GEN_BINOPR(op)  _GEN_BINOP(op, op##r)
 861
 862 #define GEN_LOAD2(op, nop) \
 863 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 864         sim_load(state, n, env, op_ia32_##nop); \
 865 }
 866
 867 #define GEN_LOAD(op)    GEN_LOAD2(op, op)
 868
 869 #define GEN_UNOP(op) \
 870 static void sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
 871         sim_unop(state, n, env, op_ia32_##op); \
 872 }
 873
 874 /* all stubs */
 875 GEN_BINOP(fadd)
 876 GEN_BINOPR(fsub)
 877 GEN_BINOP(fmul)
 878 GEN_BINOPR(fdiv)
 879
 880 GEN_LOAD(fld)
 881 GEN_LOAD(fldz)
 882 GEN_LOAD(fld1)
 883 GEN_LOAD2(fConst, fldConst)
 884
 885 GEN_UNOP(fabs)
 886 GEN_UNOP(fchs)
 887 GEN_UNOP(fsin)
 888 GEN_UNOP(fcos)
 889 GEN_UNOP(fsqrt)
 890
 891 /**
 892  * Simulate a virtual Copy
 893  */
 894 static void sim_Copy(x87_state *state, ir_node *n, const arch_env_t *env) {
 895         ir_mode *mode = get_irn_mode(n);
 896
 897         if (mode_is_float(mode)) {
 898                 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, 0));
 899                 const arch_register_t *out = arch_get_irn_register(env, n);
 900                 ir_node *node, *next;
 901                 ia32_attr_t *attr;
 902                 int op1_idx;
 903                 unsigned live = vfp_liveness_nodes_live_at(env, n);
 904
 905                 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
 906
 907                 DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(n),
 908                         arch_register_get_name(op1), arch_register_get_name(out)));
 909           DEBUG_ONLY(vfp_dump_live(live));
 910
 911                 if (is_vfp_live(op1, live)) {
 912                         /* operand is still live,a real copy */
 913                         node = new_rd_ia32_fpush(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
 914                         arch_set_irn_register(env, node, out);
 915
 916                         x87_push(state, arch_register_get_index(out), node);
 917
 918                         attr = get_ia32_attr(node);
 919                         attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
 920                         attr->x87[2] = out = &ia32_st_regs[0];
 921
 922                         next = sched_next(n);
 923                         sched_remove(n);
 924                         exchange(n, node);
 925                         sched_add_before(next, node);
 926                         DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(node), op1->name, out->name));
 927                 }
 928                 else {
 929                         /* just a virtual copy */
 930                         x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx);
 931                         sched_remove(n);
 932                         DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n)));
 933                         exchange(n, get_unop_op(n));
 934                 }
 935         }
 936 }
 937
 938 /**
 939  * Run a simulation and fix all virtual instructions for a block.
 940  *
 941  * @return non-zero if simulation is complete,
 942  *         zero if the simulation must be rerun
 943  */
 944 static int x87_simulate_block(x87_simulator *sim, ir_node *block) {
 945         ir_node *n, *next;
 946         blk_state *bl_state = x87_get_bl_state(sim, block);
 947         x87_state *state = bl_state->begin;
 948         const ir_edge_t *edge;
 949         ir_node *start_block;
 950
 951         /* if we have no assigned start state, we must wait ... */
 952         if (! state)
 953                 return 0;
 954
 955         assert(bl_state->end == NULL);
 956
 957         DB((dbg, LEVEL_1, "Simulate %+F\n", block));
 958
 959         /* beware, n might changed */
 960         for (n = sched_first(block); !sched_is_end(n); n = next) {
 961                 ir_op *op = get_irn_op(n);
 962
 963                 next = sched_next(n);
 964                 if (op->ops.generic) {
 965                         sim_func func = (sim_func)op->ops.generic;
 966
 967                         /* have work to do */
 968                         if (state == bl_state->begin) {
 969                                 /* create a new state, will be changed */
 970                                 state = x87_clone_state(sim, state);
 971                         }
 972
 973                         /* simulate it */
 974                         (*func)(state, n, sim->env);
 975                 }
 976         }
 977
 978         start_block = get_irg_start_block(get_irn_irg(block));
 979
 980         /* check if the state must be shuffled */
 981         foreach_block_succ(block, edge) {
 982                 ir_node *succ = get_edge_src_irn(edge);
 983                 blk_state *succ_state = x87_get_bl_state(sim, succ);
 984
 985                 if (succ_state->begin && succ != start_block) {
 986                         /* There is already a begin state for this block, bad.
 987                            Do the necessary permutations.
 988                            Note that critical edges are removed, so this is always possible. */
 989                         x87_shuffle(sim, block, state, succ, succ_state->begin);
 990
 991                         /* Note further, that there can be only one such situation,
 992                            so we can break here. */
 993                         break;
 994                 }
 995         }
 996         bl_state->end = state;
 997
 998         /* now propagate the state to all successor blocks */
 999         foreach_block_succ(block, edge) {
1000                 ir_node *succ = get_edge_src_irn(edge);
1001                 blk_state *succ_state = x87_get_bl_state(sim, succ);
1002
1003                 if (! succ_state->begin)
1004                         succ_state->begin = state;
1005         }
1006
1007         return 1;
1008 }
1009
1010 /**
1011  * Create a new x87 simulator.
1012  */
1013 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env_t *env) {
1014         obstack_init(&sim->obst);
1015         sim->blk_states = pmap_create();
1016         sim->env        = env;
1017
1018   FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
1019         firm_dbg_set_mask(dbg, SET_LEVEL_2);
1020
1021         DB((dbg, LEVEL_1, "--------------------------------\n"
1022                 "x87 Simulator started for %+F\n", irg));
1023
1024   /* set the generic function pointer of instruction we must simulate */
1025         clear_irp_opcodes_generic_func();
1026
1027 #define ASSOC(op)       (op_ ## op)->ops.generic = (op_func)(sim_##op)
1028 #define ASSOC_IA32(op)  (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
1029 #define ASSOC_BE(op)    (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
1030         ASSOC_IA32(fConst);
1031         ASSOC_IA32(fld);
1032         ASSOC_IA32(fld1);
1033         ASSOC_IA32(fldz);
1034         ASSOC_IA32(fadd);
1035         ASSOC_IA32(fsub);
1036         ASSOC_IA32(fmul);
1037         ASSOC_IA32(fdiv);
1038         ASSOC_IA32(fldz);
1039         ASSOC_IA32(fabs);
1040         ASSOC_IA32(fchs);
1041         ASSOC_IA32(fsin);
1042         ASSOC_IA32(fcos);
1043         ASSOC_IA32(fsqrt);
1044         ASSOC_IA32(fst);
1045         ASSOC_BE(Copy);
1046         ASSOC(Phi);
1047 #undef ASSOC_BE
1048 #undef ASSOC_IA32
1049 #undef ASSOC
1050 }
1051
1052 /**
1053  * Destroy a x87 simulator.
1054  */
1055 static void x87_destroy_simulator(x87_simulator *sim) {
1056         pmap_destroy(sim->blk_states);
1057         obstack_free(&sim->obst, NULL);
1058         DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
1059 }
1060
1061 /**
1062  * Run a simulation and fix all virtual instructions for a graph.
1063  *
1064  * Needs a block-schedule.
1065  */
1066 void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) {
1067         ir_node *block, *start_block;
1068         pdeq *worklist;
1069         blk_state *bl_state;
1070         x87_simulator sim;
1071         int i;
1072
1073   /* we need liveness info for the current graph */
1074         be_liveness(irg);
1075
1076   /* create the simulator */
1077         x87_init_simulator(&sim, irg, env);
1078
1079         start_block = get_irg_start_block(irg);
1080         bl_state = x87_get_bl_state(&sim, start_block);
1081
1082         /* start with the empty state */
1083         bl_state->begin = empty;
1084
1085         worklist = new_pdeq();
1086
1087         /* create the worklist for the schedule. */
1088         for (i = 0; i < ARR_LEN(blk_list); ++i)
1089                 pdeq_putr(worklist, blk_list[i]);
1090
1091         /* iterate */
1092         do {
1093                 block = pdeq_getl(worklist);
1094                 if (! x87_simulate_block(&sim, block)) {
1095                         pdeq_putr(worklist, block);
1096                         continue;
1097                 }
1098         } while (! pdeq_empty(worklist));
1099
1100   /* kill it */
1101         x87_destroy_simulator(&sim);
1102 }