ia32_x87.c 48.6 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       This file implements the x87 support and virtual to stack
 *              register translation for the ia32 backend.
 * @author      Michael Beck
11
12
13
 */
#include <assert.h>

14
#include "beirg.h"
15
16
17
18
#include "irnode_t.h"
#include "irop_t.h"
#include "irprog.h"
#include "iredges_t.h"
19
#include "irgmod.h"
20
#include "ircons.h"
21
#include "irgwalk.h"
22
23
#include "obst.h"
#include "pmap.h"
24
#include "array.h"
25
#include "pdeq.h"
26
#include "debug.h"
27
#include "error.h"
28

29
30
31
#include "belive_t.h"
#include "besched.h"
#include "benode.h"
32
33
34
35
#include "ia32_new_nodes.h"
#include "gen_ia32_new_nodes.h"
#include "gen_ia32_regalloc_if.h"
#include "ia32_x87.h"
36
#include "ia32_architecture.h"
37

38
39
#define N_FLOAT_REGS  (N_ia32_fp_REGS-1)  // exclude NOREG

40
/** the debug handle */
41
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
42

Sebastian Hack's avatar
Sebastian Hack committed
43
/* Forward declaration. */
44
typedef struct x87_simulator x87_simulator;
Sebastian Hack's avatar
Sebastian Hack committed
45

46
47
48
/**
 * An entry on the simulated x87 stack.
 */
49
typedef struct st_entry {
Christoph Mallon's avatar
Christoph Mallon committed
50
51
	int      reg_idx; /**< the virtual register index of this stack value */
	ir_node *node;    /**< the node that produced this value */
52
53
} st_entry;

54
55
56
/**
 * The x87 state.
 */
57
typedef struct x87_state {
58
59
60
	st_entry       st[N_FLOAT_REGS]; /**< the register stack */
	int            depth;            /**< the current stack depth */
	x87_simulator *sim;              /**< The simulator. */
61
62
63
} x87_state;

/** An empty state, used for blocks without fp instructions. */
64
static x87_state empty = { { {0, NULL}, }, 0, NULL };
65

66
67
68
/**
 * Return values of the instruction simulator functions.
 */
Michael Beck's avatar
Michael Beck committed
69
enum {
70
71
72
	NO_NODE_ADDED = 0,  /**< No node that needs simulation was added. */
	NODE_ADDED    = 1   /**< A node that must be simulated was added by the simulator
	                         in the schedule AFTER the current node. */
Michael Beck's avatar
Michael Beck committed
73
74
75
76
77
78
79
80
};

/**
 * The type of an instruction simulator function.
 *
 * @param state  the x87 state
 * @param n      the node to be simulated
 *
81
82
83
 * @return NODE_ADDED    if a node was added AFTER n in schedule that MUST be
 *                       simulated further
 *         NO_NODE_ADDED otherwise
Michael Beck's avatar
Michael Beck committed
84
 */
Michael Beck's avatar
Michael Beck committed
85
typedef int (*sim_func)(x87_state *state, ir_node *n);
86
87
88
89

/**
 * A block state: Every block has a x87 state at the beginning and at the end.
 */
90
typedef struct blk_state {
91
92
93
94
	x87_state *begin;   /**< state at the begin or NULL if not assigned */
	x87_state *end;     /**< state at the end or NULL if not assigned */
} blk_state;

95
96
/** liveness bitset for fp registers. */
typedef unsigned char fp_liveness;
Matthias Braun's avatar
Matthias Braun committed
97

98
99
100
/**
 * The x87 simulator.
 */
101
struct x87_simulator {
Christoph Mallon's avatar
Christoph Mallon committed
102
103
104
	struct obstack obst;       /**< An obstack for fast allocating. */
	pmap          *blk_states; /**< Map blocks to states. */
	be_lv_t       *lv;         /**< intrablock liveness. */
105
	fp_liveness   *live;       /**< Liveness information. */
Christoph Mallon's avatar
Christoph Mallon committed
106
107
	unsigned       n_idx;      /**< The cached get_irg_last_idx() result. */
	waitq         *worklist;   /**< Worklist of blocks that must be processed. */
Sebastian Hack's avatar
Sebastian Hack committed
108
};
109

Michael Beck's avatar
Michael Beck committed
110
/**
Michael Beck's avatar
BugFix:    
Michael Beck committed
111
 * Returns the current stack depth.
Michael Beck's avatar
Michael Beck committed
112
113
114
115
116
 *
 * @param state  the x87 state
 *
 * @return the x87 stack depth
 */
Christoph Mallon's avatar
Christoph Mallon committed
117
118
static int x87_get_depth(const x87_state *state)
{
Michael Beck's avatar
Michael Beck committed
119
	return state->depth;
120
}
121

122
123
124
static st_entry *x87_get_entry(x87_state *const state, int const pos)
{
	assert(0 <= pos && pos < state->depth);
125
	return &state->st[N_FLOAT_REGS - state->depth + pos];
126
127
}

128
/**
129
 * Return the virtual register index at st(pos).
Michael Beck's avatar
Michael Beck committed
130
131
132
133
 *
 * @param state  the x87 state
 * @param pos    a stack position
 *
134
 * @return the fp register index that produced the value at st(pos)
135
 */
Christoph Mallon's avatar
Christoph Mallon committed
136
137
static int x87_get_st_reg(const x87_state *state, int pos)
{
138
	return x87_get_entry((x87_state*)state, pos)->reg_idx;
139
}
140

Matthias Braun's avatar
Matthias Braun committed
141
#ifdef DEBUG_libfirm
142
143
/**
 * Dump the stack for debugging.
Michael Beck's avatar
Michael Beck committed
144
145
 *
 * @param state  the x87 state
146
 */
Christoph Mallon's avatar
Christoph Mallon committed
147
148
static void x87_dump_stack(const x87_state *state)
{
Christoph Mallon's avatar
Christoph Mallon committed
149
150
151
	for (int i = state->depth; i-- != 0;) {
		st_entry const *const entry = x87_get_entry((x87_state*)state, i);
		DB((dbg, LEVEL_2, "vf%d(%+F) ", entry->reg_idx, entry->node));
152
	}
153
	DB((dbg, LEVEL_2, "<-- TOS\n"));
154
}
155
#endif /* DEBUG_libfirm */
156
157

/**
Michael Beck's avatar
Michael Beck committed
158
159
160
 * Set a virtual register to st(pos).
 *
 * @param state    the x87 state
161
162
 * @param reg_idx  the fp register index that should be set
 * @param node     the IR node that produces the value of the fp register
Michael Beck's avatar
Michael Beck committed
163
 * @param pos      the stack position where the new value should be entered
164
 */
Christoph Mallon's avatar
Christoph Mallon committed
165
166
static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos)
{
167
168
169
	st_entry *const entry = x87_get_entry(state, pos);
	entry->reg_idx = reg_idx;
	entry->node    = node;
170

Matthias Braun's avatar
Matthias Braun committed
171
	DB((dbg, LEVEL_2, "After SET_REG: "));
172
	DEBUG_ONLY(x87_dump_stack(state);)
173
}
174
175
176

/**
 * Swap st(0) with st(pos).
Michael Beck's avatar
Michael Beck committed
177
178
179
 *
 * @param state    the x87 state
 * @param pos      the stack position to change the tos with
180
 */
Christoph Mallon's avatar
Christoph Mallon committed
181
182
static void x87_fxch(x87_state *state, int pos)
{
183
184
185
186
187
	st_entry *const a = x87_get_entry(state, pos);
	st_entry *const b = x87_get_entry(state, 0);
	st_entry  const t = *a;
	*a = *b;
	*b = t;
188

189
	DB((dbg, LEVEL_2, "After FXCH: "));
190
	DEBUG_ONLY(x87_dump_stack(state);)
191
}
192
193
194

/**
 * Convert a virtual register to the stack index.
Michael Beck's avatar
Michael Beck committed
195
196
 *
 * @param state    the x87 state
197
 * @param reg_idx  the register fp index
Michael Beck's avatar
Michael Beck committed
198
199
200
 *
 * @return the stack position where the register is stacked
 *         or -1 if the virtual register was not found
201
 */
Christoph Mallon's avatar
Christoph Mallon committed
202
203
static int x87_on_stack(const x87_state *state, int reg_idx)
{
204
205
	for (int i = 0; i < state->depth; ++i) {
		if (x87_get_st_reg(state, i) == reg_idx)
206
			return i;
207
	}
208
	return -1;
209
}
210
211

/**
212
 * Push a virtual Register onto the stack, double pushes are NOT allowed.
Michael Beck's avatar
Michael Beck committed
213
 *
214
 * @param state     the x87 state
215
216
 * @param reg_idx   the register fp index
 * @param node      the node that produces the value of the fp register
217
 */
218
static void x87_push(x87_state *state, int reg_idx, ir_node *node)
Christoph Mallon's avatar
Christoph Mallon committed
219
{
220
	assert(x87_on_stack(state, reg_idx) == -1 && "double push");
221
	assert(state->depth < N_FLOAT_REGS && "stack overrun");
222
223

	++state->depth;
224
225
226
	st_entry *const entry = x87_get_entry(state, 0);
	entry->reg_idx = reg_idx;
	entry->node    = node;
227

228
	DB((dbg, LEVEL_2, "After PUSH: ")); DEBUG_ONLY(x87_dump_stack(state);)
229
}
230
231
232

/**
 * Pop a virtual Register from the stack.
Michael Beck's avatar
Michael Beck committed
233
234
 *
 * @param state     the x87 state
235
 */
Christoph Mallon's avatar
Christoph Mallon committed
236
237
static void x87_pop(x87_state *state)
{
238
239
240
241
	assert(state->depth > 0 && "stack underrun");

	--state->depth;

242
	DB((dbg, LEVEL_2, "After POP: ")); DEBUG_ONLY(x87_dump_stack(state);)
243
}
244

245
246
247
248
249
/**
 * Empty the fpu stack
 *
 * @param state     the x87 state
 */
Christoph Mallon's avatar
Christoph Mallon committed
250
251
static void x87_emms(x87_state *state)
{
252
253
254
	state->depth = 0;
}

255
256
/**
 * Returns the block state of a block.
Michael Beck's avatar
Michael Beck committed
257
258
259
260
261
 *
 * @param sim    the x87 simulator handle
 * @param block  the current block
 *
 * @return the block state
262
 */
Christoph Mallon's avatar
Christoph Mallon committed
263
264
static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block)
{
265
	blk_state *res = pmap_get(blk_state, sim->blk_states, block);
266

267
268
269
270
	if (res == NULL) {
		res = OALLOC(&sim->obst, blk_state);
		res->begin = NULL;
		res->end   = NULL;
271

272
		pmap_insert(sim->blk_states, block, res);
273
274
	}

275
	return res;
276
}
277
278
279

/**
 * Clone a x87 state.
Michael Beck's avatar
Michael Beck committed
280
281
282
283
284
 *
 * @param sim    the x87 simulator handle
 * @param src    the x87 state that will be cloned
 *
 * @return a cloned copy of the src state
285
 */
Christoph Mallon's avatar
Christoph Mallon committed
286
287
static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src)
{
288
	x87_state *const res = OALLOC(&sim->obst, x87_state);
289
	*res = *src;
290
	return res;
291
}
292

293
294
295
296
297
/**
 * Returns the first Proj of a mode_T node having a given mode.
 *
 * @param n  the mode_T node
 * @param m  the desired mode of the Proj
298
 * @return The first Proj of mode @p m found.
299
 */
Christoph Mallon's avatar
Christoph Mallon committed
300
301
static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m)
{
302
303
304
305
306
307
308
309
	assert(get_irn_mode(n) == mode_T && "Need mode_T node");

	foreach_out_edge(n, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (get_irn_mode(proj) == m)
			return proj;
	}

310
	panic("Proj not found");
311
}
312

Michael Beck's avatar
Michael Beck committed
313
314
315
/**
 * Wrap the arch_* function here so we can check for errors.
 */
316
static inline const arch_register_t *x87_get_irn_register(const ir_node *irn)
Christoph Mallon's avatar
Christoph Mallon committed
317
{
318
	const arch_register_t *res = arch_get_irn_register(irn);
Michael Beck's avatar
Michael Beck committed
319

320
	assert(res->reg_class == &ia32_reg_classes[CLASS_ia32_fp]);
Michael Beck's avatar
Michael Beck committed
321
	return res;
322
}
Michael Beck's avatar
Michael Beck committed
323

324
325
326
static inline const arch_register_t *x87_irn_get_register(const ir_node *irn,
                                                          int pos)
{
327
	const arch_register_t *res = arch_get_irn_register_out(irn, pos);
328

329
	assert(res->reg_class == &ia32_reg_classes[CLASS_ia32_fp]);
330
	return res;
331
}
332

333
334
335
336
337
static inline const arch_register_t *get_st_reg(int index)
{
	return &ia32_registers[REG_ST0 + index];
}

338
/**
339
 * Create a fxch node before another node.
340
 *
341
342
343
 * @param state   the x87 state
 * @param n       the node after the fxch
 * @param pos     exchange st(pos) with st(0)
344
 */
345
static void x87_create_fxch(x87_state *state, ir_node *n, int pos)
Christoph Mallon's avatar
Christoph Mallon committed
346
{
347
	x87_fxch(state, pos);
348

349
350
351
	ir_node         *const block = get_nodes_block(n);
	ir_node         *const fxch  = new_bd_ia32_fxch(NULL, block);
	ia32_x87_attr_t *const attr  = get_ia32_x87_attr(fxch);
352
	attr->reg = get_st_reg(pos);
353

Michael Beck's avatar
Michael Beck committed
354
	keep_alive(fxch);
355

356
	sched_add_before(n, fxch);
357
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fxch), attr->reg->name));
358
}
359

360
361
/* -------------- x87 perm --------------- */

362
363
/**
 * Calculate the necessary permutations to reach dst_state.
364
365
366
367
368
369
370
371
372
373
374
375
 *
 * These permutations are done with fxch instructions and placed
 * at the end of the block.
 *
 * Note that critical edges are removed here, so we need only
 * a shuffle if the current block has only one successor.
 *
 * @param block      the current block
 * @param state      the current x87 stack state, might be modified
 * @param dst_state  destination state
 *
 * @return state
376
 */
377
static x87_state *x87_shuffle(ir_node *block, x87_state *state, const x87_state *dst_state)
Matthias Braun's avatar
Matthias Braun committed
378
{
Michael Beck's avatar
Michael Beck committed
379
	int      i, n_cycles, k, ri;
Michael Beck's avatar
Michael Beck committed
380
	unsigned cycles[4], all_mask;
Michael Beck's avatar
Michael Beck committed
381
	char     cycle_idx[4][8];
382

383
384
	assert(state->depth == dst_state->depth);

385
	/* Some mathematics here:
Christoph Mallon's avatar
Christoph Mallon committed
386
387
388
389
390
391
392
393
394
395
396
397
	 * If we have a cycle of length n that includes the tos,
	 * we need n-1 exchange operations.
	 * We can always add the tos and restore it, so we need
	 * n+1 exchange operations for a cycle not containing the tos.
	 * So, the maximum of needed operations is for a cycle of 7
	 * not including the tos == 8.
	 * This is the same number of ops we would need for using stores,
	 * so exchange is cheaper (we save the loads).
	 * On the other hand, we might need an additional exchange
	 * in the next block to bring one operand on top, so the
	 * number of ops in the first case is identical.
	 * Further, no more than 4 cycles can exists (4 x 2). */
398
399
	all_mask = (1 << (state->depth)) - 1;

Michael Beck's avatar
Michael Beck committed
400
	for (n_cycles = 0; all_mask; ++n_cycles) {
401
402
403
404
405
406
407
408
		int src_idx, dst_idx;

		/* find the first free slot */
		for (i = 0; i < state->depth; ++i) {
			if (all_mask & (1 << i)) {
				all_mask &= ~(1 << i);

				/* check if there are differences here */
409
				if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
410
411
412
413
414
					break;
			}
		}

		if (! all_mask) {
Michael Beck's avatar
Michael Beck committed
415
			/* no more cycles found */
416
417
418
419
			break;
		}

		k = 0;
Michael Beck's avatar
Michael Beck committed
420
421
		cycles[n_cycles] = (1 << i);
		cycle_idx[n_cycles][k++] = i;
422
		for (src_idx = i; ; src_idx = dst_idx) {
423
			dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
424
425
426
427

			if ((all_mask & (1 << dst_idx)) == 0)
				break;

Michael Beck's avatar
Michael Beck committed
428
429
			cycle_idx[n_cycles][k++] = dst_idx;
			cycles[n_cycles] |=  (1 << dst_idx);
430
431
			all_mask       &= ~(1 << dst_idx);
		}
Michael Beck's avatar
Michael Beck committed
432
		cycle_idx[n_cycles][k] = -1;
433
434
	}

Michael Beck's avatar
Michael Beck committed
435
	if (n_cycles <= 0) {
436
437
438
439
440
		/* no permutation needed */
		return state;
	}

	/* Hmm: permutation needed */
441
	DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
442
	DEBUG_ONLY(x87_dump_stack(state);)
443
	DB((dbg, LEVEL_2, "                  to\n"));
444
	DEBUG_ONLY(x87_dump_stack(dst_state);)
445
446
447


#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
448
449
	DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
	for (ri = 0; ri < n_cycles; ++ri) {
450
		DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
Michael Beck's avatar
Michael Beck committed
451
452
		for (k = 0; cycle_idx[ri][k] != -1; ++k)
			DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
453
454
455
456
		DB((dbg, LEVEL_2, "\n"));
	}
#endif

457
458
459
460
461
	/*
	 * Find the place node must be insert.
	 * We have only one successor block, so the last instruction should
	 * be a jump.
	 */
462
	ir_node *const before = sched_last(block);
463
464
	assert(is_cfop(before));

465
	/* now do the permutations */
Michael Beck's avatar
Michael Beck committed
466
467
468
	for (ri = 0; ri < n_cycles; ++ri) {
		if ((cycles[ri] & 1) == 0) {
			/* this cycle does not include the tos */
469
			x87_create_fxch(state, before, cycle_idx[ri][0]);
470
		}
Michael Beck's avatar
Michael Beck committed
471
		for (k = 1; cycle_idx[ri][k] != -1; ++k) {
472
			x87_create_fxch(state, before, cycle_idx[ri][k]);
473
		}
Michael Beck's avatar
Michael Beck committed
474
475
		if ((cycles[ri] & 1) == 0) {
			/* this cycle does not include the tos */
476
			x87_create_fxch(state, before, cycle_idx[ri][0]);
477
478
		}
	}
479
	return state;
480
}
481
482
483

/**
 * Create a fpush before node n.
Michael Beck's avatar
Michael Beck committed
484
 *
485
 * @param state     the x87 state
Michael Beck's avatar
Michael Beck committed
486
 * @param n         the node after the fpush
487
 * @param pos       push st(pos) on stack
488
 * @param val       the value to push
489
 */
490
static void x87_create_fpush(x87_state *state, ir_node *n, int pos, int const out_reg_idx, ir_node *const val)
Christoph Mallon's avatar
Christoph Mallon committed
491
{
492
	x87_push(state, out_reg_idx, val);
493

Christoph Mallon's avatar
Christoph Mallon committed
494
495
	ir_node         *const fpush = new_bd_ia32_fpush(NULL, get_nodes_block(n));
	ia32_x87_attr_t *const attr  = get_ia32_x87_attr(fpush);
496
	attr->reg = get_st_reg(pos);
497

Michael Beck's avatar
Michael Beck committed
498
	keep_alive(fpush);
499
	sched_add_before(n, fpush);
Michael Beck's avatar
Michael Beck committed
500

501
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpush), attr->reg->name));
502
}
503

Michael Beck's avatar
Michael Beck committed
504
505
/**
 * Create a fpop before node n.
506
 * This overwrites st(pos) with st(0) and pops st(0).
Michael Beck's avatar
Michael Beck committed
507
508
 *
 * @param state   the x87 state
Michael Beck's avatar
Michael Beck committed
509
 * @param n       the node after the fpop
510
 * @param pos     the index of the entry to remove the register stack
Michael Beck's avatar
Michael Beck committed
511
512
513
 *
 * @return the fpop node
 */
514
static ir_node *x87_create_fpop(x87_state *const state, ir_node *const n, int const pos)
Matthias Braun's avatar
Matthias Braun committed
515
{
516
517
518
519
520
	if (pos != 0) {
		st_entry *const dst = x87_get_entry(state, pos);
		st_entry *const src = x87_get_entry(state, 0);
		*dst = *src;
	}
521
522
	x87_pop(state);
	ir_node *const block = get_nodes_block(n);
523
	ir_node *const fpop  = pos == 0 && ia32_cg_config.use_ffreep ?
524
525
526
		new_bd_ia32_ffreep(NULL, block) :
		new_bd_ia32_fpop(  NULL, block);
	ia32_x87_attr_t *const attr = get_ia32_x87_attr(fpop);
527
	attr->reg = get_st_reg(pos);
528
529
530
531

	keep_alive(fpop);
	sched_add_before(n, fpop);
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->reg->name));
Michael Beck's avatar
Michael Beck committed
532
	return fpop;
533
}
Michael Beck's avatar
Michael Beck committed
534

535
536
537
538
539
540
/* --------------------------------- liveness ------------------------------------------ */

/**
 * The liveness transfer function.
 * Updates a live set over a single step from a given node to its predecessor.
 * Everything defined at the node is removed from the set, the uses of the node get inserted.
Michael Beck's avatar
BugFix:    
Michael Beck committed
541
 *
542
543
544
 * @param irn      The node at which liveness should be computed.
 * @param live     The bitset of registers live before @p irn. This set gets modified by updating it to
 *                 the registers live after irn.
Michael Beck's avatar
BugFix:    
Michael Beck committed
545
546
 *
 * @return The live bitset.
547
 */
548
static fp_liveness fp_liveness_transfer(ir_node *irn, fp_liveness live)
549
{
550
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_fp];
551

552
	be_foreach_definition(irn, cls, def, req,
553
		const arch_register_t *reg = x87_get_irn_register(def);
554
		live &= ~(1 << reg->index);
555
	);
556
557
558
559
	be_foreach_use(irn, cls, in_req_, op, op_req_,
		const arch_register_t *reg = x87_get_irn_register(op);
		live |= 1 << reg->index;
	);
560
	return live;
561
}
562
563
564

/**
 * Put all live virtual registers at the end of a block into a bitset.
Michael Beck's avatar
BugFix:    
Michael Beck committed
565
 *
Michael Beck's avatar
Michael Beck committed
566
 * @param sim      the simulator handle
Michael Beck's avatar
BugFix:    
Michael Beck committed
567
568
569
 * @param bl       the block
 *
 * @return The live bitset at the end of this block
570
 */
571
static fp_liveness fp_liveness_end_of_block(x87_simulator *sim, const ir_node *block)
572
{
573
574
	fp_liveness live = 0;
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_fp];
Matthias Braun's avatar
Matthias Braun committed
575
	const be_lv_t *lv = sim->lv;
576

577
578
	be_lv_foreach_cls(lv, block, be_lv_state_end, cls, node) {
		const arch_register_t *reg = x87_get_irn_register(node);
579
		live |= 1 << reg->index;
580
581
582
	}

	return live;
583
}
584

585
/** get the register mask from an arch_register */
586
#define REGMASK(reg)    (1 << (reg->index))
587

588
/**
589
 * Return a bitset of argument registers which are live at the end of a node.
Michael Beck's avatar
BugFix:    
Michael Beck committed
590
591
592
 *
 * @param sim    the simulator handle
 * @param pos    the node
593
 * @param kill   kill mask for the output registers
Michael Beck's avatar
BugFix:    
Michael Beck committed
594
 *
595
596
 * @return The live bitset.
 */
597
static unsigned fp_live_args_after(x87_simulator *sim, const ir_node *pos, unsigned kill)
598
{
Michael Beck's avatar
BugFix:    
Michael Beck committed
599
	unsigned idx = get_irn_idx(pos);
600

Michael Beck's avatar
BugFix:    
Michael Beck committed
601
	assert(idx < sim->n_idx);
602
	return sim->live[idx] & ~kill;
603
}
604

Michael Beck's avatar
BugFix:    
Michael Beck committed
605
606
607
/**
 * Calculate the liveness for a whole block and cache it.
 *
Matthias Braun's avatar
Matthias Braun committed
608
609
 * @param sim   the simulator handle
 * @param block the block
Michael Beck's avatar
BugFix:    
Michael Beck committed
610
 */
Christoph Mallon's avatar
Christoph Mallon committed
611
612
static void update_liveness(x87_simulator *sim, ir_node *block)
{
613
	fp_liveness live = fp_liveness_end_of_block(sim, block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
614
615
616
	unsigned idx;

	/* now iterate through the block backward and cache the results */
Matthias Braun's avatar
Matthias Braun committed
617
	sched_foreach_reverse(block, irn) {
618
619
620
621
		/* stop at the first Phi: this produces the live-in */
		if (is_Phi(irn))
			break;

Michael Beck's avatar
BugFix:    
Michael Beck committed
622
623
		idx = get_irn_idx(irn);
		sim->live[idx] = live;
624

625
		live = fp_liveness_transfer(irn, live);
626
	}
Matthias Braun's avatar
Matthias Braun committed
627
	idx = get_irn_idx(block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
628
	sim->live[idx] = live;
629
}
630
631
632

/**
 * Returns true if a register is live in a set.
Michael Beck's avatar
Michael Beck committed
633
 *
634
 * @param reg_idx  the fp register index
Michael Beck's avatar
Michael Beck committed
635
 * @param live     a live bitset
636
 */
637
#define is_fp_live(reg_idx, live) ((live) & (1 << (reg_idx)))
638

639
640
#ifdef DEBUG_libfirm
/**
Michael Beck's avatar
Michael Beck committed
641
642
643
 * Dump liveness info.
 *
 * @param live  the live bitset
644
 */
645
static void fp_dump_live(fp_liveness live)
Christoph Mallon's avatar
Christoph Mallon committed
646
{
647
648
	int i;

Matthias Braun's avatar
Matthias Braun committed
649
	DB((dbg, LEVEL_2, "Live after: "));
650
651
	for (i = 0; i < 8; ++i) {
		if (live & (1 << i)) {
Matthias Braun's avatar
Matthias Braun committed
652
			DB((dbg, LEVEL_2, "vf%d ", i));
653
654
		}
	}
655
	DB((dbg, LEVEL_2, "\n"));
656
}
657
#endif /* DEBUG_libfirm */
658
659
660

/* --------------------------------- simulators ---------------------------------------- */

661
/**
Michael Beck's avatar
Michael Beck committed
662
663
664
665
 * Simulate a virtual binop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
Michael Beck's avatar
Michael Beck committed
666
667
 *
 * @return NO_NODE_ADDED
668
 */
669
static int sim_binop(x87_state *const state, ir_node *const n)
Christoph Mallon's avatar
Christoph Mallon committed
670
{
671
	x87_simulator         *sim     = state->sim;
672
673
	ir_node               *op1     = get_irn_n(n, n_ia32_binary_left);
	ir_node               *op2     = get_irn_n(n, n_ia32_binary_right);
674
675
	const arch_register_t *op1_reg = x87_get_irn_register(op1);
	const arch_register_t *op2_reg = x87_get_irn_register(op2);
676
	const arch_register_t *out     = x87_irn_get_register(n, pn_ia32_res);
677
678
	int reg_index_1                = op1_reg->index;
	int reg_index_2                = op2_reg->index;
679
	fp_liveness            live    = fp_live_args_after(sim, n, REGMASK(out));
680
681
	int                    op1_live_after;
	int                    op2_live_after;
682

683
	DB((dbg, LEVEL_1, ">>> %+F %s, %s -> %s\n", n, op1_reg->name, op2_reg->name, out->name));
684
	DEBUG_ONLY(fp_dump_live(live);)
Matthias Braun's avatar
Matthias Braun committed
685
	DB((dbg, LEVEL_1, "Stack before: "));
686
	DEBUG_ONLY(x87_dump_stack(state);)
687

688
	int op1_idx = x87_on_stack(state, reg_index_1);
689
	assert(op1_idx >= 0);
690
	op1_live_after = is_fp_live(reg_index_1, live);
691

692
693
694
695
696
	int                    op2_idx;
	int                    out_idx;
	bool                   pop         = false;
	int              const out_reg_idx = out->index;
	ia32_x87_attr_t *const attr        = get_ia32_x87_attr(n);
697
698
	if (reg_index_2 != REG_FP_FP_NOREG) {
		/* second operand is a fp register */
699
700
		op2_idx = x87_on_stack(state, reg_index_2);
		assert(op2_idx >= 0);
701
		op2_live_after = is_fp_live(reg_index_2, live);
702

703
		if (op2_live_after) {
Michael Beck's avatar
Michael Beck committed
704
			/* Second operand is live. */
705

706
			if (op1_live_after) {
Michael Beck's avatar
Michael Beck committed
707
				/* Both operands are live: push the first one.
708
709
				 * This works even for op1 == op2. */
				x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
Matthias Braun's avatar
Matthias Braun committed
710
711
712
713
714
				/* now do fxxx (tos=tos X op) */
				op1_idx = 0;
				op2_idx += 1;
				out_idx = 0;
			} else {
715
716
717
				/* Second live, first operand is dead: Overwrite first. */
				if (op1_idx != 0 && op2_idx != 0) {
					/* Bring one operand to tos. */
Matthias Braun's avatar
Matthias Braun committed
718
					x87_create_fxch(state, n, op1_idx);
Matthias Braun's avatar
Matthias Braun committed
719
					op1_idx = 0;
720
				}
721
				out_idx = op1_idx;
722
			}
723
		} else {
Michael Beck's avatar
Michael Beck committed
724
			/* Second operand is dead. */
725
			if (op1_live_after) {
726
727
728
				/* First operand is live, second is dead: Overwrite second. */
				if (op1_idx != 0 && op2_idx != 0) {
					/* Bring one operand to tos. */
Matthias Braun's avatar
Matthias Braun committed
729
					x87_create_fxch(state, n, op2_idx);
Matthias Braun's avatar
Matthias Braun committed
730
					op2_idx = 0;
731
				}
732
				out_idx = op2_idx;
733
			} else {
734
				/* Both operands are dead. */
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
				if (op1_idx == op2_idx) {
					/* Operands are identical: no pop. */
					if (op1_idx != 0) {
						x87_create_fxch(state, n, op1_idx);
						op1_idx = 0;
						op2_idx = 0;
					}
				} else {
					if (op1_idx != 0 && op2_idx != 0) {
						/* Bring one operand to tos. Heuristically swap the operand not at
						 * st(1) to tos. This way, if any operand was at st(1), the result
						 * will end up in the new st(0) after the implicit pop. If the next
						 * operation uses the result, then no fxch will be necessary. */
						if (op1_idx != 1) {
							x87_create_fxch(state, n, op1_idx);
							op1_idx = 0;
						} else {
							x87_create_fxch(state, n, op2_idx);
							op2_idx = 0;
						}
					}
					pop = true;
757
				}
758
				out_idx = op1_idx != 0 ? op1_idx : op2_idx;
759
			}
760
		}
761
	} else {
762
		/* second operand is an address mode */
763
		if (op1_live_after) {
764
			/* first operand is live: push it here */
765
			x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
766
		} else {
767
			/* first operand is dead: bring it to tos */
768
			if (op1_idx != 0)
Matthias Braun's avatar
Matthias Braun committed
769
				x87_create_fxch(state, n, op1_idx);
770
		}
771

772
773
		op1_idx = attr->attr.data.ins_permuted ? -1 :  0;
		op2_idx = attr->attr.data.ins_permuted ?  0 : -1;
774
		out_idx = 0;
775
	}
776
777
	assert(op1_idx == 0       || op2_idx == 0);
	assert(out_idx == op1_idx || out_idx == op2_idx);
778

779
	x87_set_st(state, out_reg_idx, n, out_idx);
780
	if (pop)
781
782
783
		x87_pop(state);

	/* patch the operation */
784
785
786
787
788
789
790
791
792
793
794
	int const reg_idx = op1_idx != 0 ? op1_idx : op2_idx;
	attr->reg                    = reg_idx >= 0 ? get_st_reg(reg_idx) : NULL;
	attr->attr.data.ins_permuted = op1_idx != 0;
	attr->res_in_reg             = out_idx != 0;
	attr->pop                    = pop;

	DEBUG_ONLY(
		char const *const l = op1_idx >= 0 ? get_st_reg(op1_idx)->name : "[AM]";
		char const *const r = op2_idx >= 0 ? get_st_reg(op2_idx)->name : "[AM]";
		char const *const o = get_st_reg(out_idx)->name;
		DB((dbg, LEVEL_1, "<<< %s %s, %s -> %s\n", get_irn_opname(n), l, r, o));
795
	)
796

Michael Beck's avatar
Michael Beck committed
797
	return NO_NODE_ADDED;
798
}
799
800

/**
Michael Beck's avatar
Michael Beck committed
801
802
803
804
 * Simulate a virtual Unop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
Michael Beck's avatar
Michael Beck committed
805
806
 *
 * @return NO_NODE_ADDED
807
 */
808
static int sim_unop(x87_state *state, ir_node *n)
Christoph Mallon's avatar
Christoph Mallon committed
809
{
Christoph Mallon's avatar
Christoph Mallon committed
810
	arch_register_t const *const out  = x87_get_irn_register(n);
811
	unsigned               const live = fp_live_args_after(state->sim, n, REGMASK(out));
812
	DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name));
813
	DEBUG_ONLY(fp_dump_live(live);)
814

815
816
	ir_node               *const op1         = get_irn_n(n, 0);
	arch_register_t const *const op1_reg     = x87_get_irn_register(op1);
817
	int                    const op1_reg_idx = op1_reg->index;
Christoph Mallon's avatar
Christoph Mallon committed
818
	int                    const op1_idx     = x87_on_stack(state, op1_reg_idx);
819
	int                    const out_reg_idx = out->index;
820
	if (is_fp_live(op1_reg_idx, live)) {
821
		/* push the operand here */
822
		x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
823
	} else {
824
		/* operand is dead, bring it to tos */
Matthias Braun's avatar
Matthias Braun committed
825
		if (op1_idx != 0) {
Matthias Braun's avatar
Matthias Braun committed
826
			x87_create_fxch(state, n, op1_idx);