ia32_x87.c 47.2 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"
Matthias Braun's avatar
Matthias Braun committed
27
#include "panic.h"
28

Matthias Braun's avatar
Matthias Braun committed
29
#include "belive.h"
30
31
#include "besched.h"
#include "benode.h"
32
#include "bessaconstr.h"
33
34
35
36
#include "ia32_new_nodes.h"
#include "gen_ia32_new_nodes.h"
#include "gen_ia32_regalloc_if.h"
#include "ia32_x87.h"
37
#include "ia32_architecture.h"
38

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

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

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

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

55
56
57
/**
 * The x87 state.
 */
58
typedef struct x87_state {
59
	st_entry       st[N_FLOAT_REGS]; /**< the register stack */
Matthias Braun's avatar
Matthias Braun committed
60
	unsigned       depth;            /**< the current stack depth */
61
	x87_simulator *sim;              /**< The simulator. */
62
63
64
} x87_state;

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

Michael Beck's avatar
Michael Beck committed
67
68
69
70
71
/**
 * The type of an instruction simulator function.
 *
 * @param state  the x87 state
 * @param n      the node to be simulated
Matthias Braun's avatar
Matthias Braun committed
72
73
 * @return true if a node was added AFTER n in schedule that MUST be simulated
 *         further
Michael Beck's avatar
Michael Beck committed
74
 */
Matthias Braun's avatar
Matthias Braun committed
75
typedef bool (*sim_func)(x87_state *state, ir_node *n);
76
77
78
79

/**
 * A block state: Every block has a x87 state at the beginning and at the end.
 */
80
typedef struct blk_state {
81
82
83
84
	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;

85
86
/** liveness bitset for fp registers. */
typedef unsigned char fp_liveness;
Matthias Braun's avatar
Matthias Braun committed
87

88
89
90
/**
 * The x87 simulator.
 */
91
struct x87_simulator {
Christoph Mallon's avatar
Christoph Mallon committed
92
93
94
	struct obstack obst;       /**< An obstack for fast allocating. */
	pmap          *blk_states; /**< Map blocks to states. */
	be_lv_t       *lv;         /**< intrablock liveness. */
95
	fp_liveness   *live;       /**< Liveness information. */
Christoph Mallon's avatar
Christoph Mallon committed
96
97
	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
98
};
99

Michael Beck's avatar
Michael Beck committed
100
/**
Michael Beck's avatar
BugFix:    
Michael Beck committed
101
 * Returns the current stack depth.
Michael Beck's avatar
Michael Beck committed
102
103
104
105
 *
 * @param state  the x87 state
 * @return the x87 stack depth
 */
Matthias Braun's avatar
Matthias Braun committed
106
static unsigned x87_get_depth(const x87_state *state)
Christoph Mallon's avatar
Christoph Mallon committed
107
{
Michael Beck's avatar
Michael Beck committed
108
	return state->depth;
109
}
110

Matthias Braun's avatar
Matthias Braun committed
111
static st_entry *x87_get_entry(x87_state *const state, unsigned const pos)
112
{
Matthias Braun's avatar
Matthias Braun committed
113
	assert(pos < state->depth);
114
	return &state->st[N_FLOAT_REGS - state->depth + pos];
115
116
}

117
/**
118
 * Return the virtual register index at st(pos).
Michael Beck's avatar
Michael Beck committed
119
120
121
 *
 * @param state  the x87 state
 * @param pos    a stack position
122
 * @return the fp register index that produced the value at st(pos)
123
 */
Matthias Braun's avatar
Matthias Braun committed
124
static unsigned x87_get_st_reg(const x87_state *state, unsigned pos)
Christoph Mallon's avatar
Christoph Mallon committed
125
{
126
	return x87_get_entry((x87_state*)state, pos)->reg_idx;
127
}
128

Matthias Braun's avatar
Matthias Braun committed
129
#ifdef DEBUG_libfirm
130
131
/**
 * Dump the stack for debugging.
Michael Beck's avatar
Michael Beck committed
132
133
 *
 * @param state  the x87 state
134
 */
Christoph Mallon's avatar
Christoph Mallon committed
135
136
static void x87_dump_stack(const x87_state *state)
{
Matthias Braun's avatar
Matthias Braun committed
137
	for (unsigned i = state->depth; i-- > 0;) {
Christoph Mallon's avatar
Christoph Mallon committed
138
139
		st_entry const *const entry = x87_get_entry((x87_state*)state, i);
		DB((dbg, LEVEL_2, "vf%d(%+F) ", entry->reg_idx, entry->node));
140
	}
141
	DB((dbg, LEVEL_2, "<-- TOS\n"));
142
}
143
#endif /* DEBUG_libfirm */
144
145

/**
Michael Beck's avatar
Michael Beck committed
146
147
148
 * Set a virtual register to st(pos).
 *
 * @param state    the x87 state
149
150
 * @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
151
 * @param pos      the stack position where the new value should be entered
152
 */
Matthias Braun's avatar
Matthias Braun committed
153
154
static void x87_set_st(x87_state *state, unsigned reg_idx, ir_node *node,
                       unsigned pos)
Christoph Mallon's avatar
Christoph Mallon committed
155
{
156
157
158
	st_entry *const entry = x87_get_entry(state, pos);
	entry->reg_idx = reg_idx;
	entry->node    = node;
159

Matthias Braun's avatar
Matthias Braun committed
160
	DB((dbg, LEVEL_2, "After SET_REG: "));
161
	DEBUG_ONLY(x87_dump_stack(state);)
162
}
163
164
165

/**
 * Swap st(0) with st(pos).
Michael Beck's avatar
Michael Beck committed
166
167
168
 *
 * @param state    the x87 state
 * @param pos      the stack position to change the tos with
169
 */
Matthias Braun's avatar
Matthias Braun committed
170
static void x87_fxch(x87_state *state, unsigned pos)
Christoph Mallon's avatar
Christoph Mallon committed
171
{
172
173
174
175
176
	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;
177

178
	DB((dbg, LEVEL_2, "After FXCH: "));
179
	DEBUG_ONLY(x87_dump_stack(state);)
180
}
181
182
183

/**
 * Convert a virtual register to the stack index.
Michael Beck's avatar
Michael Beck committed
184
185
 *
 * @param state    the x87 state
186
 * @param reg_idx  the register fp index
Michael Beck's avatar
Michael Beck committed
187
188
 * @return the stack position where the register is stacked
 *         or -1 if the virtual register was not found
189
 */
Matthias Braun's avatar
Matthias Braun committed
190
static unsigned x87_on_stack(const x87_state *state, unsigned reg_idx)
Christoph Mallon's avatar
Christoph Mallon committed
191
{
Matthias Braun's avatar
Matthias Braun committed
192
	for (unsigned i = 0; i < state->depth; ++i) {
193
		if (x87_get_st_reg(state, i) == reg_idx)
194
			return i;
195
	}
Matthias Braun's avatar
Matthias Braun committed
196
	return (unsigned)-1;
197
}
198
199

/**
200
 * Push a virtual Register onto the stack, double pushes are NOT allowed.
Michael Beck's avatar
Michael Beck committed
201
 *
202
 * @param state     the x87 state
203
204
 * @param reg_idx   the register fp index
 * @param node      the node that produces the value of the fp register
205
 */
Matthias Braun's avatar
Matthias Braun committed
206
static void x87_push(x87_state *state, unsigned reg_idx, ir_node *node)
Christoph Mallon's avatar
Christoph Mallon committed
207
{
Matthias Braun's avatar
Matthias Braun committed
208
	assert(x87_on_stack(state, reg_idx) == (unsigned)-1 && "double push");
209
	assert(state->depth < N_FLOAT_REGS && "stack overrun");
210
211

	++state->depth;
212
213
214
	st_entry *const entry = x87_get_entry(state, 0);
	entry->reg_idx = reg_idx;
	entry->node    = node;
215

Matthias Braun's avatar
Matthias Braun committed
216
217
	DB((dbg, LEVEL_2, "After PUSH: "));
	DEBUG_ONLY(x87_dump_stack(state);)
218
}
219
220
221

/**
 * Pop a virtual Register from the stack.
Michael Beck's avatar
Michael Beck committed
222
223
 *
 * @param state     the x87 state
224
 */
Christoph Mallon's avatar
Christoph Mallon committed
225
226
static void x87_pop(x87_state *state)
{
227
228
	assert(state->depth > 0 && "stack underrun");
	--state->depth;
Matthias Braun's avatar
Matthias Braun committed
229
230
	DB((dbg, LEVEL_2, "After POP: "));
	DEBUG_ONLY(x87_dump_stack(state);)
231
}
232

233
234
235
236
237
/**
 * Empty the fpu stack
 *
 * @param state     the x87 state
 */
Christoph Mallon's avatar
Christoph Mallon committed
238
239
static void x87_emms(x87_state *state)
{
240
241
242
	state->depth = 0;
}

243
244
/**
 * Returns the block state of a block.
Michael Beck's avatar
Michael Beck committed
245
246
247
248
 *
 * @param sim    the x87 simulator handle
 * @param block  the current block
 * @return the block state
249
 */
Christoph Mallon's avatar
Christoph Mallon committed
250
251
static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block)
{
252
	blk_state *res = pmap_get(blk_state, sim->blk_states, block);
253
254
255
256
	if (res == NULL) {
		res = OALLOC(&sim->obst, blk_state);
		res->begin = NULL;
		res->end   = NULL;
257

258
		pmap_insert(sim->blk_states, block, res);
259
	}
260
	return res;
261
}
262
263
264

/**
 * Clone a x87 state.
Michael Beck's avatar
Michael Beck committed
265
266
267
268
 *
 * @param sim    the x87 simulator handle
 * @param src    the x87 state that will be cloned
 * @return a cloned copy of the src state
269
 */
Christoph Mallon's avatar
Christoph Mallon committed
270
271
static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src)
{
272
	x87_state *const res = OALLOC(&sim->obst, x87_state);
273
	*res = *src;
274
	return res;
275
}
276

277
278
279
280
281
/**
 * 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
282
 * @return The first Proj of mode @p m found.
283
 */
Christoph Mallon's avatar
Christoph Mallon committed
284
285
static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m)
{
Matthias Braun's avatar
Matthias Braun committed
286
	assert(get_irn_mode(n) == mode_T);
287
288
289
290
291
	foreach_out_edge(n, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (get_irn_mode(proj) == m)
			return proj;
	}
292
	panic("Proj not found");
293
}
294

Matthias Braun's avatar
Matthias Braun committed
295
static inline const arch_register_t *get_st_reg(unsigned index)
296
297
298
299
{
	return &ia32_registers[REG_ST0 + index];
}

300
/**
301
 * Create a fxch node before another node.
302
 *
303
304
305
 * @param state   the x87 state
 * @param n       the node after the fxch
 * @param pos     exchange st(pos) with st(0)
306
 */
Matthias Braun's avatar
Matthias Braun committed
307
static void x87_create_fxch(x87_state *state, ir_node *n, unsigned pos)
Christoph Mallon's avatar
Christoph Mallon committed
308
{
309
	x87_fxch(state, pos);
310

311
312
313
	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);
314
	attr->reg = get_st_reg(pos);
315

Michael Beck's avatar
Michael Beck committed
316
	keep_alive(fxch);
317

318
	sched_add_before(n, fxch);
319
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fxch), attr->reg->name));
320
}
321

322
323
/* -------------- x87 perm --------------- */

324
325
/**
 * Calculate the necessary permutations to reach dst_state.
326
327
328
329
330
331
332
333
334
335
336
 *
 * 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
337
 */
338
static x87_state *x87_shuffle(ir_node *block, x87_state *state, const x87_state *dst_state)
Matthias Braun's avatar
Matthias Braun committed
339
{
340
341
	assert(state->depth == dst_state->depth);

342
	/* Some mathematics here:
Christoph Mallon's avatar
Christoph Mallon committed
343
344
345
346
347
348
349
350
351
352
353
354
	 * 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). */
Matthias Braun's avatar
Matthias Braun committed
355
	unsigned all_mask = (1 << (state->depth)) - 1;
356

Matthias Braun's avatar
Matthias Braun committed
357
358
359
360
	unsigned      cycles[4];
	unsigned char cycle_idx[4][8];
	unsigned      n_cycles;
	for (n_cycles = 0; all_mask != 0; ++n_cycles) {
361
		/* find the first free slot */
Matthias Braun's avatar
Matthias Braun committed
362
		unsigned i;
363
364
365
366
367
		for (i = 0; i < state->depth; ++i) {
			if (all_mask & (1 << i)) {
				all_mask &= ~(1 << i);

				/* check if there are differences here */
368
				if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
369
370
371
372
					break;
			}
		}

Matthias Braun's avatar
Matthias Braun committed
373
		if (all_mask == 0) {
Michael Beck's avatar
Michael Beck committed
374
			/* no more cycles found */
375
376
377
			break;
		}

Matthias Braun's avatar
Matthias Braun committed
378
		unsigned k = 0;
Michael Beck's avatar
Michael Beck committed
379
380
		cycles[n_cycles] = (1 << i);
		cycle_idx[n_cycles][k++] = i;
Matthias Braun's avatar
Matthias Braun committed
381
		for (unsigned src_idx = i, dst_idx; ; src_idx = dst_idx) {
382
			dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
383
384
385
386

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

Michael Beck's avatar
Michael Beck committed
387
388
			cycle_idx[n_cycles][k++] = dst_idx;
			cycles[n_cycles] |=  (1 << dst_idx);
389
390
			all_mask       &= ~(1 << dst_idx);
		}
Matthias Braun's avatar
Matthias Braun committed
391
		cycle_idx[n_cycles][k] = (unsigned char)-1;
392
393
	}

Matthias Braun's avatar
Matthias Braun committed
394
	if (n_cycles == 0) {
395
396
397
398
399
		/* no permutation needed */
		return state;
	}

	/* Hmm: permutation needed */
400
	DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
401
	DEBUG_ONLY(x87_dump_stack(state);)
402
	DB((dbg, LEVEL_2, "                  to\n"));
403
	DEBUG_ONLY(x87_dump_stack(dst_state);)
404
405

#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
406
	DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
Matthias Braun's avatar
Matthias Braun committed
407
	for (unsigned ri = 0; ri < n_cycles; ++ri) {
408
		DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
Matthias Braun's avatar
Matthias Braun committed
409
		for (unsigned k = 0; cycle_idx[ri][k] != (unsigned char)-1; ++k)
Michael Beck's avatar
Michael Beck committed
410
			DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
411
412
413
414
		DB((dbg, LEVEL_2, "\n"));
	}
#endif

Matthias Braun's avatar
Matthias Braun committed
415
	/* Find the place node must be insert.
416
	 * We have only one successor block, so the last instruction should
Matthias Braun's avatar
Matthias Braun committed
417
	 * be a jump. */
418
	ir_node *const before = sched_last(block);
419
420
	assert(is_cfop(before));

421
	/* now do the permutations */
Matthias Braun's avatar
Matthias Braun committed
422
423
	for (unsigned ri = 0; ri < n_cycles; ++ri) {
		if ((cycles[ri] & 1) == 0)
424
			x87_create_fxch(state, before, cycle_idx[ri][0]);
Matthias Braun's avatar
Matthias Braun committed
425
		for (unsigned k = 1; cycle_idx[ri][k] != (unsigned char)-1; ++k) {
426
			x87_create_fxch(state, before, cycle_idx[ri][k]);
427
		}
Matthias Braun's avatar
Matthias Braun committed
428
		if ((cycles[ri] & 1) == 0)
429
			x87_create_fxch(state, before, cycle_idx[ri][0]);
430
	}
431
	return state;
432
}
433
434
435

/**
 * Create a fpush before node n.
Michael Beck's avatar
Michael Beck committed
436
 *
437
 * @param state     the x87 state
Michael Beck's avatar
Michael Beck committed
438
 * @param n         the node after the fpush
439
 * @param pos       push st(pos) on stack
440
 * @param val       the value to push
441
 */
Matthias Braun's avatar
Matthias Braun committed
442
443
static void x87_create_fpush(x87_state *state, ir_node *n, unsigned pos,
                             unsigned const out_reg_idx, ir_node *const val)
Christoph Mallon's avatar
Christoph Mallon committed
444
{
445
	x87_push(state, out_reg_idx, val);
446

Christoph Mallon's avatar
Christoph Mallon committed
447
448
	ir_node         *const fpush = new_bd_ia32_fpush(NULL, get_nodes_block(n));
	ia32_x87_attr_t *const attr  = get_ia32_x87_attr(fpush);
449
	attr->reg = get_st_reg(pos);
450

Michael Beck's avatar
Michael Beck committed
451
	keep_alive(fpush);
452
	sched_add_before(n, fpush);
Michael Beck's avatar
Michael Beck committed
453

454
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpush), attr->reg->name));
455
}
456

Michael Beck's avatar
Michael Beck committed
457
458
/**
 * Create a fpop before node n.
459
 * This overwrites st(pos) with st(0) and pops st(0).
Michael Beck's avatar
Michael Beck committed
460
461
 *
 * @param state   the x87 state
Michael Beck's avatar
Michael Beck committed
462
 * @param n       the node after the fpop
463
 * @param pos     the index of the entry to remove the register stack
Michael Beck's avatar
Michael Beck committed
464
465
 * @return the fpop node
 */
Matthias Braun's avatar
Matthias Braun committed
466
467
static ir_node *x87_create_fpop(x87_state *const state, ir_node *const n,
                                unsigned const pos)
Matthias Braun's avatar
Matthias Braun committed
468
{
469
470
471
472
473
	if (pos != 0) {
		st_entry *const dst = x87_get_entry(state, pos);
		st_entry *const src = x87_get_entry(state, 0);
		*dst = *src;
	}
474
475
	x87_pop(state);
	ir_node *const block = get_nodes_block(n);
476
	ir_node *const fpop  = pos == 0 && ia32_cg_config.use_ffreep ?
477
478
479
		new_bd_ia32_ffreep(NULL, block) :
		new_bd_ia32_fpop(  NULL, block);
	ia32_x87_attr_t *const attr = get_ia32_x87_attr(fpop);
480
	attr->reg = get_st_reg(pos);
481
482
483
484

	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
485
	return fpop;
486
}
Michael Beck's avatar
Michael Beck committed
487

488
489
490
491
492
493
/* --------------------------------- 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
494
 *
495
496
497
 * @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
498
 * @return The live bitset.
499
 */
500
static fp_liveness fp_liveness_transfer(ir_node *irn, fp_liveness live)
501
{
502
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_fp];
503
	be_foreach_definition(irn, cls, def, req,
Matthias Braun's avatar
Matthias Braun committed
504
		const arch_register_t *reg = arch_get_irn_register(def);
505
		live &= ~(1 << reg->index);
506
	);
507
	be_foreach_use(irn, cls, in_req_, op, op_req_,
Matthias Braun's avatar
Matthias Braun committed
508
		const arch_register_t *reg = arch_get_irn_register(op);
509
510
		live |= 1 << reg->index;
	);
511
	return live;
512
}
513
514
515

/**
 * Put all live virtual registers at the end of a block into a bitset.
Michael Beck's avatar
BugFix:    
Michael Beck committed
516
 *
Michael Beck's avatar
Michael Beck committed
517
 * @param sim      the simulator handle
Michael Beck's avatar
BugFix:    
Michael Beck committed
518
519
 * @param bl       the block
 * @return The live bitset at the end of this block
520
 */
521
static fp_liveness fp_liveness_end_of_block(x87_simulator *sim, const ir_node *block)
522
{
Matthias Braun's avatar
Matthias Braun committed
523
524
525
	fp_liveness                  live = 0;
	const arch_register_class_t *cls  = &ia32_reg_classes[CLASS_ia32_fp];
	const be_lv_t               *lv   = sim->lv;
526

527
	be_lv_foreach_cls(lv, block, be_lv_state_end, cls, node) {
Matthias Braun's avatar
Matthias Braun committed
528
		const arch_register_t *reg = arch_get_irn_register(node);
529
		live |= 1 << reg->index;
530
531
532
	}

	return live;
533
}
534

535
/** get the register mask from an arch_register */
536
#define REGMASK(reg)    (1 << (reg->index))
537

538
/**
539
 * Return a bitset of argument registers which are live at the end of a node.
Michael Beck's avatar
BugFix:    
Michael Beck committed
540
541
542
 *
 * @param sim    the simulator handle
 * @param pos    the node
543
 * @param kill   kill mask for the output registers
544
545
 * @return The live bitset.
 */
Matthias Braun's avatar
Matthias Braun committed
546
547
static fp_liveness fp_live_args_after(x87_simulator *sim, const ir_node *pos,
                                      fp_liveness kill)
548
{
Michael Beck's avatar
BugFix:    
Michael Beck committed
549
550
	unsigned idx = get_irn_idx(pos);
	assert(idx < sim->n_idx);
551
	return sim->live[idx] & ~kill;
552
}
553

Michael Beck's avatar
BugFix:    
Michael Beck committed
554
555
556
/**
 * Calculate the liveness for a whole block and cache it.
 *
Matthias Braun's avatar
Matthias Braun committed
557
558
 * @param sim   the simulator handle
 * @param block the block
Michael Beck's avatar
BugFix:    
Michael Beck committed
559
 */
Christoph Mallon's avatar
Christoph Mallon committed
560
561
static void update_liveness(x87_simulator *sim, ir_node *block)
{
562
	fp_liveness live = fp_liveness_end_of_block(sim, block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
563
	/* now iterate through the block backward and cache the results */
Matthias Braun's avatar
Matthias Braun committed
564
	sched_foreach_reverse(block, irn) {
565
566
567
568
		/* stop at the first Phi: this produces the live-in */
		if (is_Phi(irn))
			break;

Matthias Braun's avatar
Matthias Braun committed
569
		unsigned idx = get_irn_idx(irn);
Michael Beck's avatar
BugFix:    
Michael Beck committed
570
		sim->live[idx] = live;
571

572
		live = fp_liveness_transfer(irn, live);
573
	}
Matthias Braun's avatar
Matthias Braun committed
574
	unsigned idx = get_irn_idx(block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
575
	sim->live[idx] = live;
576
}
577
578
579

/**
 * Returns true if a register is live in a set.
Michael Beck's avatar
Michael Beck committed
580
 *
581
 * @param reg_idx  the fp register index
Michael Beck's avatar
Michael Beck committed
582
 * @param live     a live bitset
583
 */
Matthias Braun's avatar
Matthias Braun committed
584
585
586
587
static inline bool is_fp_live(unsigned reg_idx, fp_liveness live)
{
	return live & (1 << reg_idx);
}
588

589
590
#ifdef DEBUG_libfirm
/**
Michael Beck's avatar
Michael Beck committed
591
592
593
 * Dump liveness info.
 *
 * @param live  the live bitset
594
 */
595
static void fp_dump_live(fp_liveness live)
Christoph Mallon's avatar
Christoph Mallon committed
596
{
Matthias Braun's avatar
Matthias Braun committed
597
	DB((dbg, LEVEL_2, "Live after: "));
Matthias Braun's avatar
Matthias Braun committed
598
	for (unsigned i = 0; i < N_FLOAT_REGS; ++i) {
599
		if (live & (1 << i)) {
Matthias Braun's avatar
Matthias Braun committed
600
			DB((dbg, LEVEL_2, "vf%d ", i));
601
602
		}
	}
603
	DB((dbg, LEVEL_2, "\n"));
604
}
605
#endif /* DEBUG_libfirm */
606
607
608

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

609
/**
Michael Beck's avatar
Michael Beck committed
610
611
612
613
 * Simulate a virtual binop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
614
 */
Matthias Braun's avatar
Matthias Braun committed
615
static bool sim_binop(x87_state *const state, ir_node *const n)
Christoph Mallon's avatar
Christoph Mallon committed
616
{
617
	x87_simulator         *sim     = state->sim;
618
619
	ir_node               *op1     = get_irn_n(n, n_ia32_binary_left);
	ir_node               *op2     = get_irn_n(n, n_ia32_binary_right);
Matthias Braun's avatar
Matthias Braun committed
620
621
622
623
624
	const arch_register_t *op1_reg = arch_get_irn_register(op1);
	const arch_register_t *op2_reg = arch_get_irn_register(op2);
	const arch_register_t *out     = arch_get_irn_register_out(n, pn_ia32_res);
	unsigned reg_index_1           = op1_reg->index;
	unsigned reg_index_2           = op2_reg->index;
625
	fp_liveness            live    = fp_live_args_after(sim, n, REGMASK(out));
626

627
	DB((dbg, LEVEL_1, ">>> %+F %s, %s -> %s\n", n, op1_reg->name, op2_reg->name, out->name));
628
	DEBUG_ONLY(fp_dump_live(live);)
Matthias Braun's avatar
Matthias Braun committed
629
	DB((dbg, LEVEL_1, "Stack before: "));
630
	DEBUG_ONLY(x87_dump_stack(state);)
631

Matthias Braun's avatar
Matthias Braun committed
632
633
634
	unsigned op1_idx = x87_on_stack(state, reg_index_1);
	assert(op1_idx != (unsigned)-1);
	bool op1_live_after = is_fp_live(reg_index_1, live);
635

Matthias Braun's avatar
Matthias Braun committed
636
637
	unsigned               op2_idx;
	unsigned               out_idx;
638
	bool                   pop         = false;
Matthias Braun's avatar
Matthias Braun committed
639
	unsigned         const out_reg_idx = out->index;
640
	ia32_x87_attr_t *const attr        = get_ia32_x87_attr(n);
641
642
	if (reg_index_2 != REG_FP_FP_NOREG) {
		/* second operand is a fp register */
643
		op2_idx = x87_on_stack(state, reg_index_2);
Matthias Braun's avatar
Matthias Braun committed
644
645
		assert(op2_idx != (unsigned)-1);
		bool op2_live_after = is_fp_live(reg_index_2, live);
646

647
		if (op2_live_after) {
Michael Beck's avatar
Michael Beck committed
648
			/* Second operand is live. */
649

650
			if (op1_live_after) {
Michael Beck's avatar
Michael Beck committed
651
				/* Both operands are live: push the first one.
652
653
				 * This works even for op1 == op2. */
				x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
Matthias Braun's avatar
Matthias Braun committed
654
655
656
657
658
				/* now do fxxx (tos=tos X op) */
				op1_idx = 0;
				op2_idx += 1;
				out_idx = 0;
			} else {
659
660
661
				/* 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
662
					x87_create_fxch(state, n, op1_idx);
Matthias Braun's avatar
Matthias Braun committed
663
					op1_idx = 0;
664
				}
665
				out_idx = op1_idx;
666
			}
667
		} else {
Michael Beck's avatar
Michael Beck committed
668
			/* Second operand is dead. */
669
			if (op1_live_after) {
670
671
672
				/* 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
673
					x87_create_fxch(state, n, op2_idx);
Matthias Braun's avatar
Matthias Braun committed
674
					op2_idx = 0;
675
				}
676
				out_idx = op2_idx;
677
			} else {
678
				/* Both operands are dead. */
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
				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;
701
				}
702
				out_idx = op1_idx != 0 ? op1_idx : op2_idx;
703
			}
704
		}
705
	} else {
706
		/* second operand is an address mode */
707
		if (op1_live_after) {
708
			/* first operand is live: push it here */
709
			x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
710
		} else {
711
			/* first operand is dead: bring it to tos */
712
			if (op1_idx != 0)
Matthias Braun's avatar
Matthias Braun committed
713
				x87_create_fxch(state, n, op1_idx);
714
		}
715

716
		op1_idx = attr->attr.data.ins_permuted ? -1 :  0;
Matthias Braun's avatar
Matthias Braun committed
717
		op2_idx = attr->attr.data.ins_permuted ?  0 : (unsigned)-1;
718
		out_idx = 0;
719
	}
720
721
	assert(op1_idx == 0       || op2_idx == 0);
	assert(out_idx == op1_idx || out_idx == op2_idx);
722

723
	x87_set_st(state, out_reg_idx, n, out_idx);
724
	if (pop)
725
726
727
		x87_pop(state);

	/* patch the operation */
Matthias Braun's avatar
Matthias Braun committed
728
729
	unsigned const reg_idx = op1_idx != 0 ? op1_idx : op2_idx;
	attr->reg                    = reg_idx != (unsigned)-1 ? get_st_reg(reg_idx) : NULL;
730
731
732
733
734
	attr->attr.data.ins_permuted = op1_idx != 0;
	attr->res_in_reg             = out_idx != 0;
	attr->pop                    = pop;

	DEBUG_ONLY(
Matthias Braun's avatar
Matthias Braun committed
735
736
		char const *const l = op1_idx != (unsigned)-1 ? get_st_reg(op1_idx)->name : "[AM]";
		char const *const r = op2_idx != (unsigned)-1 ? get_st_reg(op2_idx)->name : "[AM]";
737
738
		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));
739
	)
Matthias Braun's avatar
Matthias Braun committed
740
	return false;
741
}
742
743

/**
Michael Beck's avatar
Michael Beck committed
744
745
746
747
 * Simulate a virtual Unop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
748
 */
Matthias Braun's avatar
Matthias Braun committed
749
static bool sim_unop(x87_state *state, ir_node *n)
Christoph Mallon's avatar
Christoph Mallon committed
750
{
Matthias Braun's avatar
Matthias Braun committed
751
752
	arch_register_t const *const out  = arch_get_irn_register(n);
	fp_liveness            const live = fp_live_args_after(state->sim, n, REGMASK(out));
753
	DB((dbg, LEVEL_1, ">>> %+F -> %s\n", n, out->name));
754
	DEBUG_ONLY(fp_dump_live(live);)
755

756
	ir_node               *const op1         = get_irn_n(n, 0);
Matthias Braun's avatar
Matthias Braun committed
757
758
759
760
	arch_register_t const *const op1_reg     = arch_get_irn_register(op1);
	unsigned               const op1_reg_idx = op1_reg->index;
	unsigned               const op1_idx     = x87_on_stack(state, op1_reg_idx);
	unsigned               const out_reg_idx = out->index;
761
	if (is_fp_live(op1_reg_idx, live)) {
762
		/* push the operand here */
763
		x87_create_fpush(state, n, op1_idx, out_reg_idx, op1);
764
	} else {
765
		/* operand is dead, bring it to tos */
Matthias Braun's avatar
Matthias Braun committed
766
		if (op1_idx != 0)
Matthias Braun's avatar
Matthias Braun committed
767
			x87_create_fxch(state, n, op1_idx);
768
	}
769

770
	x87_set_st(state, out_reg_idx, n, 0);
771
	DB((dbg, LEVEL_1, "<<< %s -> %s\n", get_irn_opname(n), get_st_reg(0)->name));
Matthias Braun's avatar
Matthias Braun committed
772
	return false;
773
}
774
775

/**
Michael Beck's avatar
Michael Beck committed
776
777
778
779
 * Simulate a virtual Load instruction.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
780
 */
Matthias Braun's avatar
Matthias Braun committed
781
static bool sim_load(x87_state *state, ir_node *n)
Christoph Mallon's avatar
Christoph Mallon committed
782
{
Matthias Braun's avatar
Matthias Braun committed
783
784
785
786
	assert((unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fild_res
	    && (unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fld1_res
	    && (unsigned)pn_ia32_fld_res == (unsigned)pn_ia32_fldz_res);
	const arch_register_t *out = arch_get_irn_register_out(n, pn_ia32_fld_res);
787