2 * This file implements the x87 support and virtual to stack
3 * register translation for the ia32 backend.
5 * @author: Michael Beck
12 #endif /* HAVE_CONFIG_H */
19 #include "iredges_t.h"
28 #include "../belive_t.h"
29 #include "../besched_t.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"
38 /* first and second binop index */
45 /* the store val index */
46 #define STORE_VAL_IDX 2
48 #define MASK_TOS(x) ((x) & (N_x87_REGS - 1))
50 /** the debug handle */
51 DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
53 /* Forward declaration. */
54 typedef struct _x87_simulator x87_simulator;
57 * An exchange template.
58 * Note that our virtual functions have the same inputs
59 * and attributes as the real ones, so we can simple exchange
61 * Further, x87 supports inverse instructions, so we can handle them.
63 typedef struct _exchange_tmpl {
64 ir_op *normal_op; /**< the normal one */
65 ir_op *reverse_op; /**< the reverse one if exists */
66 ir_op *normal_pop_op; /**< the normal one with tos pop */
67 ir_op *reverse_pop_op; /**< the reverse one with tos pop */
71 * An entry on the simulated x87 stack.
73 typedef struct _st_entry {
74 int reg_idx; /**< the virtual register index of this stack value */
75 ir_node *node; /**< the node that produced this value */
81 typedef struct _x87_state {
82 st_entry st[N_x87_REGS]; /**< the register stack */
83 int depth; /**< the current stack depth */
84 int tos; /**< position of the tos */
85 x87_simulator *sim; /**< The simulator. */
88 /** An empty state, used for blocks without fp instructions. */
89 static x87_state _empty = { { {0, NULL}, }, 0, 0 };
90 static x87_state *empty = (x87_state *)&_empty;
92 /** The type of an instruction simulator function. */
93 typedef int (*sim_func)(x87_state *state, ir_node *n, const arch_env_t *env);
96 * A block state: Every block has a x87 state at the beginning and at the end.
98 typedef struct _blk_state {
99 x87_state *begin; /**< state at the begin or NULL if not assigned */
100 x87_state *end; /**< state at the end or NULL if not assigned */
103 #define PTR_TO_BLKSTATE(p) ((blk_state *)(p))
108 struct _x87_simulator {
109 struct obstack obst; /**< an obstack for fast allocating */
110 pmap *blk_states; /**< map blocks to states */
111 const arch_env_t *env; /**< architecture environment */
112 be_lv_t *lv; /**< Liveness information. */
116 * Returns the current stack depth.
118 * @param state the x87 state
120 * @return the x87 stack depth
122 static int x87_get_depth(const x87_state *state) {
127 * Check if the state is empty.
129 * @param state the x87 state
131 * returns non-zero if the x87 stack is empty
133 static int x87_state_is_empty(const x87_state *state) {
134 return state->depth == 0;
138 * Return the virtual register index at st(pos).
140 * @param state the x87 state
141 * @param pos a stack position
143 * @return the vfp register index that produced the value at st(pos)
145 static int x87_get_st_reg(const x87_state *state, int pos) {
146 assert(pos < state->depth);
147 return state->st[MASK_TOS(state->tos + pos)].reg_idx;
151 * Return the node at st(pos).
153 * @param state the x87 state
154 * @param pos a stack position
156 * @return the IR node that produced the value at st(pos)
158 static ir_node *x87_get_st_node(const x87_state *state, int pos) {
159 assert(pos < state->depth);
160 return state->st[MASK_TOS(state->tos + pos)].node;
165 * Dump the stack for debugging.
167 * @param state the x87 state
169 static void x87_dump_stack(const x87_state *state) {
172 for (i = state->depth - 1; i >= 0; --i) {
173 DB((dbg, LEVEL_2, "vf%d ", x87_get_st_reg(state, i)));
175 DB((dbg, LEVEL_2, "<-- TOS\n"));
177 #endif /* DEBUG_libfirm */
180 * Set a virtual register to st(pos).
182 * @param state the x87 state
183 * @param reg_idx the vfp register index that should be set
184 * @param node the IR node that produces the value of the vfp register
185 * @param pos the stack position where the new value should be entered
187 static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos) {
188 assert(0 < state->depth);
189 state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx;
190 state->st[MASK_TOS(state->tos + pos)].node = node;
192 DB((dbg, LEVEL_2, "After SET_REG:\n ")); DEBUG_ONLY(x87_dump_stack(state));
196 * Set the tos virtual register.
198 * @param state the x87 state
199 * @param reg_idx the vfp register index that should be set
200 * @param node the IR node that produces the value of the vfp register
202 static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node) {
203 x87_set_st(state, reg_idx, node, 0);
207 * Flush the x87 stack.
209 * @param state the x87 state
211 static void x87_flush(x87_state *state) {
217 * Swap st(0) with st(pos).
219 * @param state the x87 state
220 * @param pos the stack position to change the tos with
222 static void x87_fxch(x87_state *state, int pos) {
224 assert(pos < state->depth);
226 entry = state->st[MASK_TOS(state->tos + pos)];
227 state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
228 state->st[MASK_TOS(state->tos)] = entry;
230 DB((dbg, LEVEL_2, "After FXCH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
234 * Convert a virtual register to the stack index.
236 * @param state the x87 state
237 * @param reg_idx the register vfp index
239 * @return the stack position where the register is stacked
240 * or -1 if the virtual register was not found
242 static int x87_on_stack(const x87_state *state, int reg_idx) {
243 int i, tos = state->tos;
245 for (i = 0; i < state->depth; ++i)
246 if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx)
252 * Push a virtual Register onto the stack, double pushed allowed.
254 * @param state the x87 state
255 * @param reg_idx the register vfp index
256 * @param node the node that produces the value of the vfp register
258 static void x87_push_dbl(x87_state *state, int reg_idx, ir_node *node) {
259 assert(state->depth < N_x87_REGS && "stack overrun");
262 state->tos = MASK_TOS(state->tos - 1);
263 state->st[state->tos].reg_idx = reg_idx;
264 state->st[state->tos].node = node;
266 DB((dbg, LEVEL_2, "After PUSH:\n ")); DEBUG_ONLY(x87_dump_stack(state));
270 * Push a virtual Register onto the stack, double pushes are NOT allowed..
272 * @param state the x87 state
273 * @param reg_idx the register vfp index
274 * @param node the node that produces the value of the vfp register
275 * @param dbl_push if != 0 double pushes are allowed
277 static void x87_push(x87_state *state, int reg_idx, ir_node *node) {
278 assert(x87_on_stack(state, reg_idx) == -1 && "double push");
280 x87_push_dbl(state, reg_idx, node);
284 * Pop a virtual Register from the stack.
286 static void x87_pop(x87_state *state) {
287 assert(state->depth > 0 && "stack underrun");
290 state->tos = MASK_TOS(state->tos + 1);
292 DB((dbg, LEVEL_2, "After POP:\n ")); DEBUG_ONLY(x87_dump_stack(state));
296 * Returns the block state of a block.
298 * @param sim the x87 simulator handle
299 * @param block the current block
301 * @return the block state
303 static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block) {
304 pmap_entry *entry = pmap_find(sim->blk_states, block);
307 blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
308 bl_state->begin = NULL;
309 bl_state->end = NULL;
311 pmap_insert(sim->blk_states, block, bl_state);
315 return PTR_TO_BLKSTATE(entry->value);
319 * Creates a new x87 state.
321 * @param sim the x87 simulator handle
323 * @return a new x87 state
325 static x87_state *x87_alloc_state(x87_simulator *sim) {
326 x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
332 * Create a new empty x87 state.
334 * @param sim the x87 simulator handle
336 * @return a new empty x87 state
338 static x87_state *x87_alloc_empty_state(x87_simulator *sim) {
339 x87_state *res = x87_alloc_state(sim);
348 * @param sim the x87 simulator handle
349 * @param src the x87 state that will be cloned
351 * @return a cloned copy of the src state
353 static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src) {
354 x87_state *res = x87_alloc_state(sim);
356 memcpy(res, src, sizeof(*res));
361 * Patch a virtual instruction into a x87 one and return
364 * @param n the IR node to patch
365 * @param op the x87 opcode to patch in
367 static ir_node *x87_patch_insn(ir_node *n, ir_op *op) {
368 ir_mode *mode = get_irn_mode(n);
373 if (mode == mode_T) {
374 /* patch all Proj's */
375 const ir_edge_t *edge;
377 foreach_out_edge(n, edge) {
378 ir_node *proj = get_edge_src_irn(edge);
380 mode = get_irn_mode(proj);
381 if (mode_is_float(mode)) {
383 set_irn_mode(proj, mode_E);
388 else if (mode_is_float(mode))
389 set_irn_mode(n, mode_E);
394 * Returns the first Proj of a mode_T node having a given mode.
396 * @param n the mode_T node
397 * @param m the desired mode of the Proj
398 * @return The first Proj of mode @p m found or NULL.
400 static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m) {
401 const ir_edge_t *edge;
403 assert(get_irn_mode(n) == mode_T && "Need mode_T node");
405 foreach_out_edge(n, edge) {
406 ir_node *proj = get_edge_src_irn(edge);
407 if (get_irn_mode(proj) == m)
414 /* -------------- x87 perm --------------- */
417 * Creates a fxch for shuffle.
419 * @param state the x87 state
420 * @param pos parameter for fxch
421 * @param dst_block the block of the user
423 * Creates a new fxch node and reroute the user of the old node
426 * @return the fxch node
428 static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block, ir_node *dst_block)
430 const ir_edge_t *edge;
431 ir_node *n = x87_get_st_node(state, pos);
432 ir_node *user = NULL;
437 if (block == get_nodes_block(n)) {
438 /* this is a node from out block: change it's user */
439 foreach_out_edge(n, edge) {
440 ir_node *succ = get_edge_src_irn(edge);
442 if (is_Phi(succ) && get_nodes_block(succ) == dst_block) {
444 node_idx = get_edge_src_pos(edge);
451 fxch = new_rd_ia32_fxch(NULL, get_irn_irg(block), block, n, get_irn_mode(n));
452 attr = get_ia32_attr(fxch);
453 attr->x87[0] = &ia32_st_regs[pos];
454 attr->x87[2] = &ia32_st_regs[0];
457 DB((dbg, LEVEL_2, "%+F replaced input %d of %+F\n", fxch, node_idx, user));
458 set_irn_n(user, node_idx, fxch);
462 * This is a node from a dominator block. Changing it's user might be wrong,
463 * so just keep it alive.
464 * The "right" solution would require a new Phi, but we don't care here.
469 x87_fxch(state, pos);
474 * Calculate the necessary permutations to reach dst_state.
476 * These permutations are done with fxch instructions and placed
477 * at the end of the block.
479 * Note that critical edges are removed here, so we need only
480 * a shuffle if the current block has only one successor.
482 * @param sim the simulator handle
483 * @param block the current block
484 * @param state the current x87 stack state, might be modified
485 * @param dst_block the destination block
486 * @param dst_state destination state
490 static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block, x87_state *state, ir_node *dst_block, const x87_state *dst_state) {
491 int i, n_cycles, k, ri;
492 unsigned cycles[4], all_mask;
493 char cycle_idx[4][8];
495 ir_node *before, *after;
497 assert(state->depth == dst_state->depth);
499 /* Some mathematics here:
500 If we have a cycle of length n that includes the tos,
501 we need n-1 exchange operations.
502 We can always add the tos and restore it, so we need
503 n+1 exchange operations for a cycle not containing the tos.
504 So, the maximum of needed operations is for a cycle of 7
505 not including the tos == 8.
506 This is the same number of ops we would need for using stores,
507 so exchange is cheaper (we save the loads).
508 On the other hand, we might need an additional exchange
509 in the next block to bring one operand on top, so the
510 number of ops in the first case is identical.
511 Further, no more than 4 cycles can exists (4 x 2).
513 all_mask = (1 << (state->depth)) - 1;
515 for (n_cycles = 0; all_mask; ++n_cycles) {
516 int src_idx, dst_idx;
518 /* find the first free slot */
519 for (i = 0; i < state->depth; ++i) {
520 if (all_mask & (1 << i)) {
521 all_mask &= ~(1 << i);
523 /* check if there are differences here */
524 if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
530 /* no more cycles found */
535 cycles[n_cycles] = (1 << i);
536 cycle_idx[n_cycles][k++] = i;
537 for (src_idx = i; ; src_idx = dst_idx) {
538 dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
540 if ((all_mask & (1 << dst_idx)) == 0)
543 cycle_idx[n_cycles][k++] = dst_idx;
544 cycles[n_cycles] |= (1 << dst_idx);
545 all_mask &= ~(1 << dst_idx);
547 cycle_idx[n_cycles][k] = -1;
551 /* no permutation needed */
555 /* Hmm: permutation needed */
556 DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
557 DEBUG_ONLY(x87_dump_stack(state));
558 DB((dbg, LEVEL_2, " to\n"));
559 DEBUG_ONLY(x87_dump_stack(dst_state));
563 DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
564 for (ri = 0; ri < n_cycles; ++ri) {
565 DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
566 for (k = 0; cycle_idx[ri][k] != -1; ++k)
567 DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
568 DB((dbg, LEVEL_2, "\n"));
575 * Find the place node must be insert.
576 * We have only one successor block, so the last instruction should
579 before = sched_last(block);
580 assert(is_cfop(before));
582 /* now do the permutations */
583 for (ri = 0; ri < n_cycles; ++ri) {
584 if ((cycles[ri] & 1) == 0) {
585 /* this cycle does not include the tos */
586 fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block);
588 sched_add_after(after, fxch);
590 sched_add_before(before, fxch);
593 for (k = 1; cycle_idx[ri][k] != -1; ++k) {
594 fxch = x87_fxch_shuffle(state, cycle_idx[ri][k], block, dst_block);
596 sched_add_after(after, fxch);
598 sched_add_before(before, fxch);
601 if ((cycles[ri] & 1) == 0) {
602 /* this cycle does not include the tos */
603 fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block, dst_block);
604 sched_add_after(after, fxch);
611 * Create a fxch node before another node.
613 * @param state the x87 state
614 * @param n the node before the fxch
615 * @param pos exchange st(pos) with st(0)
616 * @param op_idx if >= 0, replace input op_idx of n with the fxch result
620 static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos, int op_idx) {
621 ir_node *fxch, *pred;
624 x87_fxch(state, pos);
627 pred = get_irn_n(n, op_idx);
629 pred = x87_get_st_node(state, pos);
631 fxch = new_rd_ia32_fxch(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
632 attr = get_ia32_attr(fxch);
633 attr->x87[0] = &ia32_st_regs[pos];
634 attr->x87[2] = &ia32_st_regs[0];
637 set_irn_n(n, op_idx, fxch);
639 sched_add_before(n, fxch);
640 DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
645 * Create a fpush before node n.
647 * @param state the x87 state
648 * @param n the node before the fpush
649 * @param pos push st(pos) on stack
650 * @param op_idx if >= 0, replace input op_idx of n with the fpush result
652 static void x87_create_fpush(const arch_env_t *env, x87_state *state, ir_node *n, int pos, int op_idx) {
653 ir_node *fpush, *pred = get_irn_n(n, op_idx);
655 const arch_register_t *out = arch_get_irn_register(env, pred);
657 x87_push_dbl(state, arch_register_get_index(out), pred);
659 fpush = new_rd_ia32_fpush(NULL, get_irn_irg(n), get_nodes_block(n), pred, get_irn_mode(pred));
660 attr = get_ia32_attr(fpush);
661 attr->x87[0] = &ia32_st_regs[pos];
662 attr->x87[2] = &ia32_st_regs[0];
664 set_irn_n(n, op_idx, fpush);
666 sched_add_before(n, fpush);
667 DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
671 * Create a fpop before node n.
673 * @param state the x87 state
674 * @param n the node before the fpop
675 * @param num pop 1 or 2 values
676 * @param pred node to use as predecessor of the fpop
678 * @return the fpop node
680 static ir_node *x87_create_fpop(const arch_env_t *env, x87_state *state, ir_node *n, int num, ir_node *pred) {
686 fpop = new_rd_ia32_fpop(NULL, get_irn_irg(n), get_nodes_block(n), pred, mode_E);
687 attr = get_ia32_attr(fpop);
688 attr->x87[0] = &ia32_st_regs[0];
689 attr->x87[1] = &ia32_st_regs[0];
690 attr->x87[2] = &ia32_st_regs[0];
692 sched_add_before(n, fpop);
693 DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->x87[0]->name));
701 /* --------------------------------- liveness ------------------------------------------ */
704 * The liveness transfer function.
705 * Updates a live set over a single step from a given node to its predecessor.
706 * Everything defined at the node is removed from the set, the uses of the node get inserted.
707 * @param arch_env The architecture environment.
708 * @param irn The node at which liveness should be computed.
709 * @param live The bitset of registers live before @p irn. This set gets modified by updating it to
710 * the registers live after irn.
713 static unsigned vfp_liveness_transfer(const arch_env_t *arch_env, ir_node *irn, unsigned live)
716 const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
718 if (arch_irn_consider_in_reg_alloc(arch_env, cls, irn)) {
719 const arch_register_t *reg = arch_get_irn_register(arch_env, irn);
720 live &= ~(1 << reg->index);
723 for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
724 ir_node *op = get_irn_n(irn, i);
726 if (mode_is_float(get_irn_mode(op)) && arch_irn_consider_in_reg_alloc(arch_env, cls, op)) {
727 const arch_register_t *reg = arch_get_irn_register(arch_env, op);
728 live |= 1 << reg->index;
736 * Put all live virtual registers at the end of a block into a bitset.
737 * @param arch_env The architecture environment.
738 * @param bl The block.
739 * @return The live bitset.
741 static unsigned vfp_liveness_end_of_block(x87_simulator *sim, const ir_node *bl)
745 const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
747 be_lv_foreach(sim->lv, bl, be_lv_state_end, i) {
748 ir_node *irn = be_lv_get_irn(sim->lv, bl, i);
749 if (arch_irn_consider_in_reg_alloc(sim->env, cls, irn)) {
750 const arch_register_t *reg = arch_get_irn_register(sim->env, irn);
751 live |= 1 << reg->index;
759 * Compute a bitset of registers which are live at another node.
760 * @param arch_env The architecture environment.
761 * @param pos The node.
762 * @return The live bitset.
764 static unsigned vfp_liveness_nodes_live_at(x87_simulator *sim, const ir_node *pos)
766 const ir_node *bl = is_Block(pos) ? pos : get_nodes_block(pos);
770 live = vfp_liveness_end_of_block(sim, bl);
772 sched_foreach_reverse(bl, irn) {
774 * If we encounter the node we want to insert the Perm after,
775 * exit immediately, so that this node is still live
780 live = vfp_liveness_transfer(sim->env, irn, live);
787 * Returns true if a register is live in a set.
789 * @param reg_idx the vfp register index
790 * @param live a live bitset
792 static unsigned is_vfp_live(int reg_idx, unsigned live) {
793 return live & (1 << reg_idx);
798 * Dump liveness info.
800 * @param live the live bitset
802 static void vfp_dump_live(unsigned live) {
805 DB((dbg, LEVEL_2, "Live registers here: \n"));
806 for (i = 0; i < 8; ++i) {
807 if (live & (1 << i)) {
808 DB((dbg, LEVEL_2, " vf%d", i));
811 DB((dbg, LEVEL_2, "\n"));
813 #endif /* DEBUG_libfirm */
815 /* --------------------------------- simulators ---------------------------------------- */
817 #define XCHG(a, b) do { int t = (a); (a) = (b); (b) = t; } while (0)
820 * Simulate a virtual binop.
822 * @param state the x87 state
823 * @param n the node that should be simulated (and patched)
824 * @param env the architecture environment
825 * @param tmpl the template containing the 4 possible x87 opcodes
827 static int sim_binop(x87_state *state, ir_node *n, const arch_env_t *env, const exchange_tmpl *tmpl) {
828 int op2_idx, op1_idx = -1;
829 int out_idx, do_pop =0;
832 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
833 const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
834 const arch_register_t *out = arch_get_irn_register(env, n);
835 unsigned live = vfp_liveness_nodes_live_at(state->sim, n);
837 DB((dbg, LEVEL_1, ">>> %s %s, %s -> %s\n", get_irn_opname(n),
838 arch_register_get_name(op1), arch_register_get_name(op2),
839 arch_register_get_name(out)));
840 DEBUG_ONLY(vfp_dump_live(live));
842 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
843 op2_idx = x87_on_stack(state, arch_register_get_index(op2));
845 if (op2->index != REG_VFP_NOREG) {
846 /* second operand is a vfp register */
848 if (is_vfp_live(op2->index, live)) {
849 /* Second operand is live. */
851 if (is_vfp_live(op1->index, live)) {
852 /* Both operands are live: push the first one.
853 This works even for op1 == op2. */
854 x87_create_fpush(env, state, n, op2_idx, BINOP_IDX_2);
855 out_idx = op2_idx = 0;
857 dst = tmpl->normal_op;
861 /* Second live, first operand is dead here, bring it to tos. */
863 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
867 op1_idx = out_idx = 0;
868 dst = tmpl->normal_op;
873 /* Second operand is dead. */
874 if (is_vfp_live(op1->index, live)) {
875 /* First operand is live: bring second to tos. */
877 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
881 op2_idx = out_idx = 0;
882 dst = tmpl->normal_op;
886 /* Both operands are dead here, pop them from the stack. */
889 XCHG(op2_idx, op1_idx);
890 if (op1_idx == op2_idx) {
891 /* Both are identically, no pop needed. */
892 dst = tmpl->reverse_op;
896 dst = tmpl->reverse_pop_op;
900 else if (op1_idx == 0) {
902 if (op1_idx == op2_idx) {
903 /* Both are identically, no pop needed. */
904 dst = tmpl->normal_op;
908 dst = tmpl->normal_pop_op;
913 /* Bring the first on top. */
914 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
915 if (op1_idx == op2_idx) {
916 /* Both are identically, no pop needed. */
917 out_idx = op1_idx = op2_idx = 0;
918 dst = tmpl->normal_op;
924 dst = tmpl->normal_pop_op;
932 /* second operand is an address mode */
933 if (is_vfp_live(op1->index, live)) {
934 /* first operand is live: push it here */
935 x87_create_fpush(env, state, n, op1_idx, BINOP_IDX_1);
938 /* first operand is dead: bring it to tos */
940 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
942 op1_idx = out_idx = 0;
943 dst = tmpl->normal_op;
947 x87_set_st(state, arch_register_get_index(out), x87_patch_insn(n, dst), out_idx);
951 /* patch the operation */
952 attr = get_ia32_attr(n);
953 attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
955 attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
956 attr->x87[2] = out = &ia32_st_regs[out_idx];
959 DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n),
960 arch_register_get_name(op1), arch_register_get_name(op2),
961 arch_register_get_name(out)));
963 DB((dbg, LEVEL_1, "<<< %s %s, [AM] -> %s\n", get_irn_opname(n),
964 arch_register_get_name(op1),
965 arch_register_get_name(out)));
971 * Simulate a virtual Unop.
973 * @param state the x87 state
974 * @param n the node that should be simulated (and patched)
975 * @param env the architecture environment
976 * @param op the x87 opcode that will replace n's opcode
978 static int sim_unop(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
979 int op1_idx, out_idx;
980 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, UNOP_IDX));
981 const arch_register_t *out = arch_get_irn_register(env, n);
983 unsigned live = vfp_liveness_nodes_live_at(state->sim, n);
985 DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), out->name));
986 DEBUG_ONLY(vfp_dump_live(live));
988 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
990 if (is_vfp_live(op1->index, live)) {
991 /* push the operand here */
992 x87_create_fpush(env, state, n, op1_idx, UNOP_IDX);
995 /* operand is dead, bring it to tos */
997 x87_create_fxch(state, n, op1_idx, UNOP_IDX);
1000 x87_set_tos(state, arch_register_get_index(out), x87_patch_insn(n, op));
1001 op1_idx = out_idx = 0;
1002 attr = get_ia32_attr(n);
1003 attr->x87[0] = op1 = &ia32_st_regs[0];
1004 attr->x87[2] = out = &ia32_st_regs[0];
1005 DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), out->name));
1011 * Simulate a virtual Load instruction.
1013 * @param state the x87 state
1014 * @param n the node that should be simulated (and patched)
1015 * @param env the architecture environment
1016 * @param op the x87 opcode that will replace n's opcode
1018 static int sim_load(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op) {
1019 const arch_register_t *out = arch_get_irn_register(env, n);
1022 DB((dbg, LEVEL_1, ">>> %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
1023 x87_push(state, arch_register_get_index(out), x87_patch_insn(n, op));
1024 attr = get_ia32_attr(n);
1025 attr->x87[2] = out = &ia32_st_regs[0];
1026 DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), arch_register_get_name(out)));
1032 * Rewire all users of @p old_val to @new_val iff they are scheduled after @p store.
1034 * @param store The store
1035 * @param old_val The former value
1036 * @param new_val The new value
1038 static void collect_and_rewire_users(ir_node *store, ir_node *old_val, ir_node *new_val) {
1039 const ir_edge_t *edge, *ne;
1041 foreach_out_edge_safe(old_val, edge, ne) {
1042 ir_node *user = get_edge_src_irn(edge);
1044 if (! user || user == store)
1047 /* if the user is scheduled after the store: rewire */
1048 if (sched_is_scheduled(user) && sched_comes_after(store, user)) {
1050 /* find the input of the user pointing to the old value */
1051 for (i = get_irn_arity(user) - 1; i >= 0; i--) {
1052 if (get_irn_n(user, i) == old_val)
1053 set_irn_n(user, i, new_val);
1060 * Simulate a virtual Store.
1062 * @param state the x87 state
1063 * @param n the node that should be simulated (and patched)
1064 * @param env the architecture environment
1065 * @param op the x87 store opcode
1066 * @param op_p the x87 store and pop opcode
1068 static int sim_store(x87_state *state, ir_node *n, const arch_env_t *env, ir_op *op, ir_op *op_p) {
1069 ir_node *val = get_irn_n(n, STORE_VAL_IDX);
1070 const arch_register_t *op2 = arch_get_irn_register(env, val);
1071 unsigned live = vfp_liveness_nodes_live_at(state->sim, n);
1077 op2_idx = x87_on_stack(state, arch_register_get_index(op2));
1078 assert(op2_idx >= 0);
1080 DB((dbg, LEVEL_1, ">>> %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
1082 mode = get_ia32_ls_mode(n);
1083 depth = x87_get_depth(state);
1086 We can only store the tos to memory.
1087 A store of mode_E with free registers
1088 pushes value to tos, so skip it here.
1090 if (! (mode == mode_E && depth < N_x87_REGS) && op2_idx != 0)
1091 x87_create_fxch(state, n, op2_idx, STORE_VAL_IDX);
1093 if (is_vfp_live(op2->index, live)) {
1095 Problem: fst doesn't support mode_E (spills), only fstp does
1097 - stack not full: push value and fstp
1098 - stack full: fstp value and load again
1100 if (mode == mode_E) {
1101 if (depth < N_x87_REGS) {
1102 /* ok, we have a free register: push + fstp */
1103 x87_create_fpush(env, state, n, op2_idx, STORE_VAL_IDX);
1105 x87_patch_insn(n, op_p);
1108 ir_node *vfld, *mem, *block, *rproj, *mproj;
1111 /* stack full here: need fstp + load */
1113 x87_patch_insn(n, op_p);
1115 block = get_nodes_block(n);
1116 irg = get_irn_irg(n);
1117 vfld = new_rd_ia32_vfld(NULL, irg, block, get_irn_n(n, 0), get_irn_n(n, 1), new_rd_NoMem(irg));
1119 /* copy all attributes */
1120 set_ia32_frame_ent(vfld, get_ia32_frame_ent(n));
1121 if (is_ia32_use_frame(n))
1122 set_ia32_use_frame(vfld);
1123 set_ia32_am_flavour(vfld, get_ia32_am_flavour(n));
1124 set_ia32_op_type(vfld, ia32_am_Source);
1125 add_ia32_am_offs(vfld, get_ia32_am_offs(n));
1126 set_ia32_am_sc(vfld, get_ia32_am_sc(n));
1127 set_ia32_ls_mode(vfld, get_ia32_ls_mode(n));
1129 rproj = new_r_Proj(irg, block, vfld, get_ia32_ls_mode(vfld), pn_ia32_vfld_res);
1130 mproj = new_r_Proj(irg, block, vfld, mode_M, pn_ia32_vfld_M);
1131 mem = get_irn_Proj_for_mode(n, mode_M);
1133 assert(mem && "Store memory not found");
1135 arch_set_irn_register(env, rproj, op2);
1137 /* reroute all former users of the store memory to the load memory */
1138 edges_reroute(mem, mproj, irg);
1139 /* set the memory input of the load to the store memory */
1140 set_irn_n(vfld, 2, mem);
1142 sched_add_after(n, vfld);
1143 sched_add_after(vfld, rproj);
1145 /* rewire all users, scheduled after the store, to the loaded value */
1146 collect_and_rewire_users(n, val, rproj);
1152 /* mode != mode_E -> use normal fst */
1153 x87_patch_insn(n, op);
1158 x87_patch_insn(n, op_p);
1161 attr = get_ia32_attr(n);
1162 attr->x87[1] = op2 = &ia32_st_regs[0];
1163 DB((dbg, LEVEL_1, "<<< %s %s ->\n", get_irn_opname(n), arch_register_get_name(op2)));
1169 * Simulate a virtual Phi.
1170 * Just for cosmetic reasons change the mode of Phi nodes to mode_E.
1172 * @param state the x87 state
1173 * @param n the node that should be simulated (and patched)
1174 * @param env the architecture environment
1176 static int sim_Phi(x87_state *state, ir_node *n, const arch_env_t *env) {
1177 ir_mode *mode = get_irn_mode(n);
1179 if (mode_is_float(mode))
1180 set_irn_mode(n, mode_E);
1186 #define _GEN_BINOP(op, rev) \
1187 static int sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1188 exchange_tmpl tmpl = { op_ia32_##op, op_ia32_##rev, op_ia32_##op##p, op_ia32_##rev##p }; \
1189 return sim_binop(state, n, env, &tmpl); \
1192 #define GEN_BINOP(op) _GEN_BINOP(op, op)
1193 #define GEN_BINOPR(op) _GEN_BINOP(op, op##r)
1195 #define GEN_LOAD2(op, nop) \
1196 static int sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1197 return sim_load(state, n, env, op_ia32_##nop); \
1200 #define GEN_LOAD(op) GEN_LOAD2(op, op)
1202 #define GEN_UNOP(op) \
1203 static int sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1204 return sim_unop(state, n, env, op_ia32_##op); \
1207 #define GEN_STORE(op) \
1208 static int sim_##op(x87_state *state, ir_node *n, const arch_env_t *env) { \
1209 return sim_store(state, n, env, op_ia32_##op, op_ia32_##op##p); \
1228 GEN_LOAD2(fConst, fldConst)
1234 * Simulate a fCondJmp.
1236 * @param state the x87 state
1237 * @param n the node that should be simulated (and patched)
1238 * @param env the architecture environment
1240 static int sim_fCondJmp(x87_state *state, ir_node *n, const arch_env_t *env) {
1241 int op2_idx, op1_idx = -1, pop_cnt = 0;
1244 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_1));
1245 const arch_register_t *op2 = arch_get_irn_register(env, get_irn_n(n, BINOP_IDX_2));
1246 unsigned live = vfp_liveness_nodes_live_at(state->sim, n);
1248 DB((dbg, LEVEL_1, ">>> %s %s, %s\n", get_irn_opname(n),
1249 arch_register_get_name(op1), arch_register_get_name(op2)));
1250 DEBUG_ONLY(vfp_dump_live(live));
1252 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1253 op2_idx = x87_on_stack(state, arch_register_get_index(op2));
1255 /* BEWARE: check for comp a,a cases, they might happen */
1256 if (op2->index != REG_VFP_NOREG) {
1257 /* second operand is a vfp register */
1259 if (is_vfp_live(op2->index, live)) {
1260 /* second operand is live */
1262 if (is_vfp_live(op1->index, live)) {
1263 /* both operands are live: move one of them to tos */
1265 XCHG(op2_idx, op1_idx);
1266 dst = op_ia32_fcomrJmp;
1268 else if (op1_idx == 0) {
1269 dst = op_ia32_fcomJmp;
1272 /* bring the first on top */
1273 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1274 if (op1_idx == op2_idx)
1277 dst = op_ia32_fcomJmp;
1281 /* second live, first operand is dead here, bring it to tos.
1282 This means further, op1_idx != op2_idx. */
1284 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1289 dst = op_ia32_fcompJmp;
1294 /* second operand is dead */
1295 if (is_vfp_live(op1->index, live)) {
1296 /* first operand is live: bring second to tos.
1297 This means further, op1_idx != op2_idx. */
1299 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1304 dst = op_ia32_fcomrpJmp;
1308 /* both operands are dead here, check first for identity. */
1309 if (op1_idx == op2_idx) {
1310 /* identically, one one needed */
1312 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1313 op1_idx = op2_idx = 0;
1315 dst = op_ia32_fcompJmp;
1318 /* different, move them to st and st(1) and pop both.
1319 The tricky part is to get one into st(1).*/
1320 else if (op2_idx == 1) {
1321 /* good, second operand is already in the right place, move the first */
1323 /* bring the first on top */
1324 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1327 dst = op_ia32_fcomppJmp;
1330 else if (op1_idx == 1) {
1331 /* good, first operand is already in the right place, move the second */
1333 /* bring the first on top */
1334 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1337 dst = op_ia32_fcomrppJmp;
1341 /* if one is already the TOS, we need two fxch */
1343 /* first one is TOS, move to st(1) */
1344 x87_create_fxch(state, n, 1, BINOP_IDX_1);
1346 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1348 dst = op_ia32_fcomrppJmp;
1351 else if (op2_idx == 0) {
1352 /* second one is TOS, move to st(1) */
1353 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1355 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1357 dst = op_ia32_fcomrppJmp;
1361 /* none of them is either TOS or st(1), 3 fxch needed */
1362 x87_create_fxch(state, n, op2_idx, BINOP_IDX_2);
1363 x87_create_fxch(state, n, 1, BINOP_IDX_2);
1364 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1367 dst = op_ia32_fcomppJmp;
1375 /* second operand is an address mode */
1376 if (is_vfp_live(op1->index, live)) {
1377 /* first operand is live: bring it to TOS */
1379 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1382 dst = op_ia32_fcomJmp;
1385 /* first operand is dead: bring it to tos */
1387 x87_create_fxch(state, n, op1_idx, BINOP_IDX_1);
1391 dst = op_ia32_fcompJmp;
1395 x87_patch_insn(n, dst);
1401 /* patch the operation */
1402 attr = get_ia32_attr(n);
1403 attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
1405 attr->x87[1] = op2 = &ia32_st_regs[op2_idx];
1408 DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(n),
1409 arch_register_get_name(op1), arch_register_get_name(op2)));
1411 DB((dbg, LEVEL_1, "<<< %s %s, [AM]\n", get_irn_opname(n),
1412 arch_register_get_name(op1)));
1418 * Simulate a be_Copy.
1420 * @param state the x87 state
1421 * @param n the node that should be simulated (and patched)
1422 * @param env the architecture environment
1424 static int sim_Copy(x87_state *state, ir_node *n, const arch_env_t *env) {
1425 ir_mode *mode = get_irn_mode(n);
1427 if (mode_is_float(mode)) {
1428 const arch_register_t *op1 = arch_get_irn_register(env, get_irn_n(n, 0));
1429 const arch_register_t *out = arch_get_irn_register(env, n);
1430 ir_node *node, *next;
1432 int op1_idx, out_idx;
1433 unsigned live = vfp_liveness_nodes_live_at(state->sim, n);
1435 op1_idx = x87_on_stack(state, arch_register_get_index(op1));
1437 DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(n),
1438 arch_register_get_name(op1), arch_register_get_name(out)));
1439 DEBUG_ONLY(vfp_dump_live(live));
1441 if (is_vfp_live(op1->index, live)) {
1442 /* operand is still live,a real copy */
1443 node = new_rd_ia32_fpush(get_irn_dbg_info(n), get_irn_irg(n), get_nodes_block(n), get_irn_n(n, 0), mode);
1444 arch_set_irn_register(env, node, out);
1446 x87_push(state, arch_register_get_index(out), node);
1448 attr = get_ia32_attr(node);
1449 attr->x87[0] = op1 = &ia32_st_regs[op1_idx];
1450 attr->x87[2] = out = &ia32_st_regs[0];
1452 next = sched_next(n);
1455 sched_add_before(next, node);
1456 DB((dbg, LEVEL_1, ">>> %s %s -> %s\n", get_irn_opname(node), op1->name, out->name));
1459 out_idx = x87_on_stack(state, arch_register_get_index(out));
1461 if (out_idx >= 0 && out_idx != op1_idx) {
1462 /* op1 must be killed and placed where out is */
1464 /* best case, simple remove and rename */
1465 x87_patch_insn(n, op_ia32_Pop);
1466 attr = get_ia32_attr(n);
1467 attr->x87[0] = op1 = &ia32_st_regs[0];
1470 x87_set_st(state, arch_register_get_index(out), n, op1_idx - 1);
1473 /* move op1 to tos, store and pop it */
1475 x87_create_fxch(state, n, op1_idx, 0);
1478 x87_patch_insn(n, op_ia32_Pop);
1479 attr = get_ia32_attr(n);
1480 attr->x87[0] = op1 = &ia32_st_regs[out_idx];
1483 x87_set_st(state, arch_register_get_index(out), n, out_idx - 1);
1485 DB((dbg, LEVEL_1, ">>> %s %s\n", get_irn_opname(n), op1->name));
1488 /* just a virtual copy */
1489 x87_set_st(state, arch_register_get_index(out), get_unop_op(n), op1_idx);
1491 DB((dbg, LEVEL_1, ">>> KILLED %s\n", get_irn_opname(n)));
1492 exchange(n, get_unop_op(n));
1501 * Simulate a be_Call.
1503 * @param state the x87 state
1504 * @param n the node that should be simulated
1505 * @param env the architecture environment
1507 static int sim_Call(x87_state *state, ir_node *n, const arch_env_t *env) {
1508 ir_type *call_tp = be_Call_get_type(n);
1510 /* at the begin of a call the x87 state should be empty */
1511 assert(state->depth == 0 && "stack not empty before call");
1514 * If the called function returns a float, it is returned in st(0).
1515 * This even happens if the return value is NOT used.
1516 * Moreover, only one return result is supported.
1518 if (get_method_n_ress(call_tp) > 0) {
1519 ir_type *res_type = get_method_res_type(call_tp, 0);
1520 ir_mode *mode = get_type_mode(res_type);
1522 if (mode && mode_is_float(mode)) {
1524 * TODO: what to push here? The result might be unused and currently
1525 * we have no possibility to detect this :-(
1527 x87_push(state, 0, n);
1535 * Simulate a be_Spill.
1537 * @param state the x87 state
1538 * @param n the node that should be simulated (and patched)
1539 * @param env the architecture environment
1541 * Should not happen, spills are lowered before x87 simulator see them.
1543 static int sim_Spill(x87_state *state, ir_node *n, const arch_env_t *env) {
1544 assert(0 && "Spill not lowered");
1545 return sim_fst(state, n, env);
1549 * Simulate a be_Reload.
1551 * @param state the x87 state
1552 * @param n the node that should be simulated (and patched)
1553 * @param env the architecture environment
1555 * Should not happen, reloads are lowered before x87 simulator see them.
1557 static int sim_Reload(x87_state *state, ir_node *n, const arch_env_t *env) {
1558 assert(0 && "Reload not lowered");
1559 return sim_fld(state, n, env);
1563 * Simulate a be_Return.
1565 * @param state the x87 state
1566 * @param n the node that should be simulated (and patched)
1567 * @param env the architecture environment
1569 static int sim_Return(x87_state *state, ir_node *n, const arch_env_t *env) {
1570 int n_res = be_Return_get_n_rets(n);
1571 int i, n_float_res = 0;
1573 /* only floating point return values must resist on stack */
1574 for (i = 0; i < n_res; ++i) {
1575 ir_node *res = get_irn_n(n, be_pos_Return_val + i);
1577 if (mode_is_float(get_irn_mode(res)))
1580 assert(x87_get_depth(state) == n_float_res);
1582 /* pop them virtually */
1583 for (i = n_float_res - 1; i >= 0; --i)
1590 * Kill any dead registers at block start by popping them from the stack.
1592 * @param sim the simulator handle
1593 * @param block the current block
1594 * @param start_state the x87 state at the begin of the block
1596 static x87_state *x87_kill_deads(x87_simulator *sim, ir_node *block, x87_state *start_state) {
1597 x87_state *state = start_state;
1598 ir_node *first_insn = sched_first(block);
1599 ir_node *keep = NULL;
1600 unsigned live = vfp_liveness_nodes_live_at(sim, block);
1602 int i, depth, num_pop;
1605 depth = x87_get_depth(state);
1606 for (i = depth - 1; i >= 0; --i) {
1607 int reg = x87_get_st_reg(state, i);
1609 if (! is_vfp_live(reg, live))
1610 kill_mask |= (1 << i);
1614 /* create a new state, will be changed */
1615 state = x87_clone_state(sim, state);
1617 DB((dbg, LEVEL_1, "Killing deads:\n"));
1618 DEBUG_ONLY(vfp_dump_live(live));
1619 DEBUG_ONLY(x87_dump_stack(state));
1621 /* now kill registers */
1623 /* we can only kill from TOS, so bring them up */
1624 if (! (kill_mask & 1)) {
1625 /* search from behind, because we can to a double-pop */
1626 for (i = depth - 1; i >= 0; --i) {
1627 if (kill_mask & (1 << i)) {
1628 kill_mask &= ~(1 << i);
1635 x87_set_st(state, -1, keep, i);
1636 keep = x87_create_fxch(state, first_insn, i, -1);
1639 keep = x87_get_st_node(state, 0);
1641 if ((kill_mask & 3) == 3) {
1642 /* we can do a double-pop */
1646 /* only a single pop */
1651 kill_mask >>= num_pop;
1652 keep = x87_create_fpop(sim->env, state, first_insn, num_pop, keep);
1654 add_End_keepalive(get_irg_end(get_irn_irg(block)), keep);
1660 * Run a simulation and fix all virtual instructions for a block.
1662 * @param sim the simulator handle
1663 * @param block the current block
1665 * @return non-zero if simulation is complete,
1666 * zero if the simulation must be rerun
1668 static int x87_simulate_block(x87_simulator *sim, ir_node *block) {
1670 blk_state *bl_state = x87_get_bl_state(sim, block);
1671 x87_state *state = bl_state->begin;
1672 const ir_edge_t *edge;
1673 ir_node *start_block;
1675 /* if we have no assigned start state, we must wait ... */
1679 assert(bl_state->end == NULL);
1681 DB((dbg, LEVEL_1, "Simulate %+F\n", block));
1683 /* at block begin, kill all dead registers */
1684 state = x87_kill_deads(sim, block, state);
1686 /* beware, n might changed */
1687 for (n = sched_first(block); !sched_is_end(n); n = next) {
1688 ir_op *op = get_irn_op(n);
1690 next = sched_next(n);
1691 if (op->ops.generic) {
1693 sim_func func = (sim_func)op->ops.generic;
1695 /* have work to do */
1696 if (state == bl_state->begin) {
1697 /* create a new state, will be changed */
1698 state = x87_clone_state(sim, state);
1702 node_inserted = (*func)(state, n, sim->env);
1705 sim_func might have added additional nodes after n,
1707 beware: n must not be changed by sim_func
1708 (i.e. removed from schedule) in this case
1711 next = sched_next(n);
1715 start_block = get_irg_start_block(get_irn_irg(block));
1717 /* check if the state must be shuffled */
1718 foreach_block_succ(block, edge) {
1719 ir_node *succ = get_edge_src_irn(edge);
1720 blk_state *succ_state = x87_get_bl_state(sim, succ);
1722 if (succ_state->begin && succ != start_block) {
1723 /* There is already a begin state for this block, bad.
1724 Do the necessary permutations.
1725 Note that critical edges are removed, so this is always possible. */
1726 x87_shuffle(sim, block, state, succ, succ_state->begin);
1728 /* Note further, that there can be only one such situation,
1729 so we can break here. */
1733 bl_state->end = state;
1735 /* now propagate the state to all successor blocks */
1736 foreach_block_succ(block, edge) {
1737 ir_node *succ = get_edge_src_irn(edge);
1738 blk_state *succ_state = x87_get_bl_state(sim, succ);
1740 if (! succ_state->begin)
1741 succ_state->begin = state;
1748 * Create a new x87 simulator.
1750 * @param sim a simulator handle, will be initialized
1751 * @param irg the current graph
1752 * @param env the architecture environment
1754 static void x87_init_simulator(x87_simulator *sim, ir_graph *irg, const arch_env_t *env) {
1755 obstack_init(&sim->obst);
1756 sim->blk_states = pmap_create();
1758 sim->lv = be_liveness(irg);
1760 FIRM_DBG_REGISTER(dbg, "firm.be.ia32.x87");
1762 DB((dbg, LEVEL_1, "--------------------------------\n"
1763 "x87 Simulator started for %+F\n", irg));
1765 /* set the generic function pointer of instruction we must simulate */
1766 clear_irp_opcodes_generic_func();
1768 #define ASSOC(op) (op_ ## op)->ops.generic = (op_func)(sim_##op)
1769 #define ASSOC_IA32(op) (op_ia32_v ## op)->ops.generic = (op_func)(sim_##op)
1770 #define ASSOC_BE(op) (op_be_ ## op)->ops.generic = (op_func)(sim_##op)
1788 ASSOC_IA32(fCondJmp);
1801 * Destroy a x87 simulator.
1803 * @param sim the simulator handle
1805 static void x87_destroy_simulator(x87_simulator *sim) {
1806 pmap_destroy(sim->blk_states);
1807 obstack_free(&sim->obst, NULL);
1808 be_liveness_free(sim->lv);
1809 DB((dbg, LEVEL_1, "x87 Simulator stopped\n\n"));
1813 * Run a simulation and fix all virtual instructions for a graph.
1815 * @param env the architecture environment
1816 * @param irg the current graph
1817 * @param blk_list the block schedule list
1819 * Needs a block-schedule.
1821 void x87_simulate_graph(const arch_env_t *env, ir_graph *irg, ir_node **blk_list) {
1822 ir_node *block, *start_block;
1824 blk_state *bl_state;
1828 /* create the simulator */
1829 x87_init_simulator(&sim, irg, env);
1831 start_block = get_irg_start_block(irg);
1832 bl_state = x87_get_bl_state(&sim, start_block);
1834 /* start with the empty state */
1835 bl_state->begin = empty;
1838 worklist = new_pdeq();
1840 /* create the worklist for the schedule. */
1841 for (i = 0; i < ARR_LEN(blk_list); ++i)
1842 pdeq_putr(worklist, blk_list[i]);
1846 block = pdeq_getl(worklist);
1847 if (! x87_simulate_block(&sim, block)) {
1848 pdeq_putr(worklist, block);
1851 } while (! pdeq_empty(worklist));
1854 x87_destroy_simulator(&sim);