ia32_x87.c 53.6 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2010 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

20
/**
Christian Würdig's avatar
Christian Würdig committed
21
22
23
24
 * @file
 * @brief       This file implements the x87 support and virtual to stack
 *              register translation for the ia32 backend.
 * @author      Michael Beck
25
 */
26
#include "config.h"
27

28
29
30
31
32
33
#include <assert.h>

#include "irnode_t.h"
#include "irop_t.h"
#include "irprog.h"
#include "iredges_t.h"
34
#include "irgmod.h"
35
#include "ircons.h"
36
#include "irgwalk.h"
37
38
#include "obst.h"
#include "pmap.h"
39
#include "array_t.h"
40
41
#include "pdeq.h"
#include "irprintf.h"
42
#include "debug.h"
43
#include "error.h"
44

45
46
47
#include "belive_t.h"
#include "besched.h"
#include "benode.h"
48
#include "bearch_ia32_t.h"
49
50
51
52
#include "ia32_new_nodes.h"
#include "gen_ia32_new_nodes.h"
#include "gen_ia32_regalloc_if.h"
#include "ia32_x87.h"
53
#include "ia32_architecture.h"
54

55
/** the debug handle */
56
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
57

Sebastian Hack's avatar
Sebastian Hack committed
58
/* Forward declaration. */
59
typedef struct x87_simulator x87_simulator;
Sebastian Hack's avatar
Sebastian Hack committed
60

61
62
63
/**
 * An entry on the simulated x87 stack.
 */
64
typedef struct st_entry {
Christoph Mallon's avatar
Christoph Mallon committed
65
66
	int      reg_idx; /**< the virtual register index of this stack value */
	ir_node *node;    /**< the node that produced this value */
67
68
} st_entry;

69
70
71
/**
 * The x87 state.
 */
72
typedef struct x87_state {
Christoph Mallon's avatar
Christoph Mallon committed
73
74
75
	st_entry       st[N_ia32_st_REGS]; /**< the register stack */
	int            depth;              /**< the current stack depth */
	x87_simulator *sim;                /**< The simulator. */
76
77
78
} x87_state;

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

81
82
83
/**
 * Return values of the instruction simulator functions.
 */
Michael Beck's avatar
Michael Beck committed
84
enum {
85
86
87
	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
88
89
90
91
92
93
94
95
};

/**
 * The type of an instruction simulator function.
 *
 * @param state  the x87 state
 * @param n      the node to be simulated
 *
96
97
98
 * @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
99
 */
Michael Beck's avatar
Michael Beck committed
100
typedef int (*sim_func)(x87_state *state, ir_node *n);
101
102
103
104

/**
 * A block state: Every block has a x87 state at the beginning and at the end.
 */
105
typedef struct blk_state {
106
107
108
109
	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;

Matthias Braun's avatar
Matthias Braun committed
110
111
112
/** liveness bitset for vfp registers. */
typedef unsigned char vfp_liveness;

113
114
115
/**
 * The x87 simulator.
 */
116
struct x87_simulator {
Christoph Mallon's avatar
Christoph Mallon committed
117
118
119
120
121
122
	struct obstack obst;       /**< An obstack for fast allocating. */
	pmap          *blk_states; /**< Map blocks to states. */
	be_lv_t       *lv;         /**< intrablock liveness. */
	vfp_liveness  *live;       /**< Liveness information. */
	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
123
};
124

Michael Beck's avatar
Michael Beck committed
125
/**
Michael Beck's avatar
BugFix:    
Michael Beck committed
126
 * Returns the current stack depth.
Michael Beck's avatar
Michael Beck committed
127
128
129
130
131
 *
 * @param state  the x87 state
 *
 * @return the x87 stack depth
 */
Christoph Mallon's avatar
Christoph Mallon committed
132
133
static int x87_get_depth(const x87_state *state)
{
Michael Beck's avatar
Michael Beck committed
134
	return state->depth;
135
}
136

137
138
139
static st_entry *x87_get_entry(x87_state *const state, int const pos)
{
	assert(0 <= pos && pos < state->depth);
Christoph Mallon's avatar
Christoph Mallon committed
140
	return &state->st[N_ia32_st_REGS - state->depth + pos];
141
142
}

143
/**
144
 * Return the virtual register index at st(pos).
Michael Beck's avatar
Michael Beck committed
145
146
147
148
149
 *
 * @param state  the x87 state
 * @param pos    a stack position
 *
 * @return the vfp register index that produced the value at st(pos)
150
 */
Christoph Mallon's avatar
Christoph Mallon committed
151
152
static int x87_get_st_reg(const x87_state *state, int pos)
{
153
	return x87_get_entry((x87_state*)state, pos)->reg_idx;
154
}
155

Matthias Braun's avatar
Matthias Braun committed
156
#ifdef DEBUG_libfirm
157
158
/**
 * Dump the stack for debugging.
Michael Beck's avatar
Michael Beck committed
159
160
 *
 * @param state  the x87 state
161
 */
Christoph Mallon's avatar
Christoph Mallon committed
162
163
static void x87_dump_stack(const x87_state *state)
{
Christoph Mallon's avatar
Christoph Mallon committed
164
165
166
	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));
167
	}
168
	DB((dbg, LEVEL_2, "<-- TOS\n"));
169
}
170
#endif /* DEBUG_libfirm */
171
172

/**
Michael Beck's avatar
Michael Beck committed
173
174
175
176
177
178
 * Set a virtual register to st(pos).
 *
 * @param state    the x87 state
 * @param reg_idx  the vfp register index that should be set
 * @param node     the IR node that produces the value of the vfp register
 * @param pos      the stack position where the new value should be entered
179
 */
Christoph Mallon's avatar
Christoph Mallon committed
180
181
static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos)
{
182
183
184
	st_entry *const entry = x87_get_entry(state, pos);
	entry->reg_idx = reg_idx;
	entry->node    = node;
185

Matthias Braun's avatar
Matthias Braun committed
186
	DB((dbg, LEVEL_2, "After SET_REG: "));
187
	DEBUG_ONLY(x87_dump_stack(state);)
188
}
189
190
191

/**
 * Swap st(0) with st(pos).
Michael Beck's avatar
Michael Beck committed
192
193
194
 *
 * @param state    the x87 state
 * @param pos      the stack position to change the tos with
195
 */
Christoph Mallon's avatar
Christoph Mallon committed
196
197
static void x87_fxch(x87_state *state, int pos)
{
198
199
200
201
202
	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;
203

204
	DB((dbg, LEVEL_2, "After FXCH: "));
205
	DEBUG_ONLY(x87_dump_stack(state);)
206
}
207
208
209

/**
 * Convert a virtual register to the stack index.
Michael Beck's avatar
Michael Beck committed
210
211
212
213
214
215
 *
 * @param state    the x87 state
 * @param reg_idx  the register vfp index
 *
 * @return the stack position where the register is stacked
 *         or -1 if the virtual register was not found
216
 */
Christoph Mallon's avatar
Christoph Mallon committed
217
218
static int x87_on_stack(const x87_state *state, int reg_idx)
{
219
220
	for (int i = 0; i < state->depth; ++i) {
		if (x87_get_st_reg(state, i) == reg_idx)
221
			return i;
222
	}
223
	return -1;
224
}
225
226

/**
227
 * Push a virtual Register onto the stack, double pushes are NOT allowed.
Michael Beck's avatar
Michael Beck committed
228
 *
229
230
231
 * @param state     the x87 state
 * @param reg_idx   the register vfp index
 * @param node      the node that produces the value of the vfp register
232
 */
233
static void x87_push(x87_state *state, int reg_idx, ir_node *node)
Christoph Mallon's avatar
Christoph Mallon committed
234
{
235
	assert(x87_on_stack(state, reg_idx) == -1 && "double push");
236
	assert(state->depth < N_ia32_st_REGS && "stack overrun");
237
238

	++state->depth;
239
240
241
	st_entry *const entry = x87_get_entry(state, 0);
	entry->reg_idx = reg_idx;
	entry->node    = node;
242

243
	DB((dbg, LEVEL_2, "After PUSH: ")); DEBUG_ONLY(x87_dump_stack(state);)
244
}
245
246
247

/**
 * Pop a virtual Register from the stack.
Michael Beck's avatar
Michael Beck committed
248
249
 *
 * @param state     the x87 state
250
 */
Christoph Mallon's avatar
Christoph Mallon committed
251
252
static void x87_pop(x87_state *state)
{
253
254
255
256
	assert(state->depth > 0 && "stack underrun");

	--state->depth;

257
	DB((dbg, LEVEL_2, "After POP: ")); DEBUG_ONLY(x87_dump_stack(state);)
258
}
259

260
261
262
263
264
/**
 * Empty the fpu stack
 *
 * @param state     the x87 state
 */
Christoph Mallon's avatar
Christoph Mallon committed
265
266
static void x87_emms(x87_state *state)
{
267
268
269
	state->depth = 0;
}

270
271
/**
 * Returns the block state of a block.
Michael Beck's avatar
Michael Beck committed
272
273
274
275
276
 *
 * @param sim    the x87 simulator handle
 * @param block  the current block
 *
 * @return the block state
277
 */
Christoph Mallon's avatar
Christoph Mallon committed
278
279
static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block)
{
280
	blk_state *res = pmap_get(blk_state, sim->blk_states, block);
281

282
283
284
285
	if (res == NULL) {
		res = OALLOC(&sim->obst, blk_state);
		res->begin = NULL;
		res->end   = NULL;
286

287
		pmap_insert(sim->blk_states, block, res);
288
289
	}

290
	return res;
291
}
292
293
294

/**
 * Clone a x87 state.
Michael Beck's avatar
Michael Beck committed
295
296
297
298
299
 *
 * @param sim    the x87 simulator handle
 * @param src    the x87 state that will be cloned
 *
 * @return a cloned copy of the src state
300
 */
Christoph Mallon's avatar
Christoph Mallon committed
301
302
static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src)
{
303
	x87_state *const res = OALLOC(&sim->obst, x87_state);
304
	*res = *src;
305
	return res;
306
}
307

308
309
/**
 * Patch a virtual instruction into a x87 one and return
Michael Beck's avatar
Michael Beck committed
310
 * the node representing the result value.
Michael Beck's avatar
Michael Beck committed
311
312
313
 *
 * @param n   the IR node to patch
 * @param op  the x87 opcode to patch in
314
 */
Christoph Mallon's avatar
Christoph Mallon committed
315
316
static ir_node *x87_patch_insn(ir_node *n, ir_op *op)
{
317
318
319
320
321
322
323
324
325
326
327
328
329
	ir_mode *mode = get_irn_mode(n);
	ir_node *res = n;

	set_irn_op(n, op);

	if (mode == mode_T) {
		/* patch all Proj's */
		foreach_out_edge(n, edge) {
			ir_node *proj = get_edge_src_irn(edge);
			if (is_Proj(proj)) {
				mode = get_irn_mode(proj);
				if (mode_is_float(mode)) {
					res = proj;
330
					set_irn_mode(proj, ia32_reg_classes[CLASS_ia32_st].mode);
331
332
333
				}
			}
		}
Michael Beck's avatar
Michael Beck committed
334
	} else if (mode_is_float(mode))
335
		set_irn_mode(n, ia32_reg_classes[CLASS_ia32_st].mode);
336
	return res;
337
}
338

339
340
341
342
343
/**
 * 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
344
 * @return The first Proj of mode @p m found.
345
 */
Christoph Mallon's avatar
Christoph Mallon committed
346
347
static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m)
{
348
349
350
351
352
353
354
355
	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;
	}

356
	panic("Proj not found");
357
}
358

Michael Beck's avatar
Michael Beck committed
359
360
361
/**
 * Wrap the arch_* function here so we can check for errors.
 */
362
static inline const arch_register_t *x87_get_irn_register(const ir_node *irn)
Christoph Mallon's avatar
Christoph Mallon committed
363
{
364
	const arch_register_t *res = arch_get_irn_register(irn);
Michael Beck's avatar
Michael Beck committed
365

366
	assert(res->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]);
Michael Beck's avatar
Michael Beck committed
367
	return res;
368
}
Michael Beck's avatar
Michael Beck committed
369

370
371
372
static inline const arch_register_t *x87_irn_get_register(const ir_node *irn,
                                                          int pos)
{
373
	const arch_register_t *res = arch_get_irn_register_out(irn, pos);
374

375
	assert(res->reg_class == &ia32_reg_classes[CLASS_ia32_vfp]);
376
	return res;
377
}
378

379
380
381
382
383
static inline const arch_register_t *get_st_reg(int index)
{
	return &ia32_registers[REG_ST0 + index];
}

384
/**
385
 * Create a fxch node before another node.
386
 *
387
388
389
 * @param state   the x87 state
 * @param n       the node after the fxch
 * @param pos     exchange st(pos) with st(0)
390
 */
391
static void x87_create_fxch(x87_state *state, ir_node *n, int pos)
Christoph Mallon's avatar
Christoph Mallon committed
392
{
393
	x87_fxch(state, pos);
394

395
396
397
	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);
398
	attr->reg = get_st_reg(pos);
399

Michael Beck's avatar
Michael Beck committed
400
	keep_alive(fxch);
401

402
	sched_add_before(n, fxch);
403
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fxch), attr->reg->name));
404
}
405

406
407
/* -------------- x87 perm --------------- */

408
409
/**
 * Calculate the necessary permutations to reach dst_state.
410
411
412
413
414
415
416
417
418
419
420
421
 *
 * 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
422
 */
423
static x87_state *x87_shuffle(ir_node *block, x87_state *state, const x87_state *dst_state)
Matthias Braun's avatar
Matthias Braun committed
424
{
Michael Beck's avatar
Michael Beck committed
425
	int      i, n_cycles, k, ri;
Michael Beck's avatar
Michael Beck committed
426
	unsigned cycles[4], all_mask;
Michael Beck's avatar
Michael Beck committed
427
	char     cycle_idx[4][8];
428

429
430
	assert(state->depth == dst_state->depth);

431
	/* Some mathematics here:
Christoph Mallon's avatar
Christoph Mallon committed
432
433
434
435
436
437
438
439
440
441
442
443
	 * 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). */
444
445
	all_mask = (1 << (state->depth)) - 1;

Michael Beck's avatar
Michael Beck committed
446
	for (n_cycles = 0; all_mask; ++n_cycles) {
447
448
449
450
451
452
453
454
		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 */
455
				if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
456
457
458
459
460
					break;
			}
		}

		if (! all_mask) {
Michael Beck's avatar
Michael Beck committed
461
			/* no more cycles found */
462
463
464
465
			break;
		}

		k = 0;
Michael Beck's avatar
Michael Beck committed
466
467
		cycles[n_cycles] = (1 << i);
		cycle_idx[n_cycles][k++] = i;
468
		for (src_idx = i; ; src_idx = dst_idx) {
469
			dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
470
471
472
473

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

Michael Beck's avatar
Michael Beck committed
474
475
			cycle_idx[n_cycles][k++] = dst_idx;
			cycles[n_cycles] |=  (1 << dst_idx);
476
477
			all_mask       &= ~(1 << dst_idx);
		}
Michael Beck's avatar
Michael Beck committed
478
		cycle_idx[n_cycles][k] = -1;
479
480
	}

Michael Beck's avatar
Michael Beck committed
481
	if (n_cycles <= 0) {
482
483
484
485
486
		/* no permutation needed */
		return state;
	}

	/* Hmm: permutation needed */
487
	DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
488
	DEBUG_ONLY(x87_dump_stack(state);)
489
	DB((dbg, LEVEL_2, "                  to\n"));
490
	DEBUG_ONLY(x87_dump_stack(dst_state);)
491
492
493


#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
494
495
	DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
	for (ri = 0; ri < n_cycles; ++ri) {
496
		DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
Michael Beck's avatar
Michael Beck committed
497
498
		for (k = 0; cycle_idx[ri][k] != -1; ++k)
			DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
499
500
501
502
		DB((dbg, LEVEL_2, "\n"));
	}
#endif

503
504
505
506
507
	/*
	 * Find the place node must be insert.
	 * We have only one successor block, so the last instruction should
	 * be a jump.
	 */
508
	ir_node *const before = sched_last(block);
509
510
	assert(is_cfop(before));

511
	/* now do the permutations */
Michael Beck's avatar
Michael Beck committed
512
513
514
	for (ri = 0; ri < n_cycles; ++ri) {
		if ((cycles[ri] & 1) == 0) {
			/* this cycle does not include the tos */
515
			x87_create_fxch(state, before, cycle_idx[ri][0]);
516
		}
Michael Beck's avatar
Michael Beck committed
517
		for (k = 1; cycle_idx[ri][k] != -1; ++k) {
518
			x87_create_fxch(state, before, cycle_idx[ri][k]);
519
		}
Michael Beck's avatar
Michael Beck committed
520
521
		if ((cycles[ri] & 1) == 0) {
			/* this cycle does not include the tos */
522
			x87_create_fxch(state, before, cycle_idx[ri][0]);
523
524
		}
	}
525
	return state;
526
}
527
528
529

/**
 * Create a fpush before node n.
Michael Beck's avatar
Michael Beck committed
530
 *
531
 * @param state     the x87 state
Michael Beck's avatar
Michael Beck committed
532
 * @param n         the node after the fpush
533
 * @param pos       push st(pos) on stack
534
 * @param val       the value to push
535
 */
536
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
537
{
538
	x87_push(state, out_reg_idx, val);
539

Christoph Mallon's avatar
Christoph Mallon committed
540
541
	ir_node         *const fpush = new_bd_ia32_fpush(NULL, get_nodes_block(n));
	ia32_x87_attr_t *const attr  = get_ia32_x87_attr(fpush);
542
	attr->reg = get_st_reg(pos);
543

Michael Beck's avatar
Michael Beck committed
544
	keep_alive(fpush);
545
	sched_add_before(n, fpush);
Michael Beck's avatar
Michael Beck committed
546

547
	DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpush), attr->reg->name));
548
}
549

Michael Beck's avatar
Michael Beck committed
550
551
552
553
/**
 * Create a fpop before node n.
 *
 * @param state   the x87 state
Michael Beck's avatar
Michael Beck committed
554
 * @param n       the node after the fpop
Michael Beck's avatar
Michael Beck committed
555
556
557
558
 * @param num     pop 1 or 2 values
 *
 * @return the fpop node
 */
Matthias Braun's avatar
Matthias Braun committed
559
560
static ir_node *x87_create_fpop(x87_state *state, ir_node *n, int num)
{
561
	ir_node         *fpop = NULL;
562
	ia32_x87_attr_t *attr;
Michael Beck's avatar
Michael Beck committed
563

Matthias Braun's avatar
Matthias Braun committed
564
	assert(num > 0);
565
	do {
Michael Beck's avatar
Michael Beck committed
566
		x87_pop(state);
567
		if (ia32_cg_config.use_ffreep)
568
			fpop = new_bd_ia32_ffreep(NULL, get_nodes_block(n));
569
		else
570
			fpop = new_bd_ia32_fpop(NULL, get_nodes_block(n));
571
		attr = get_ia32_x87_attr(fpop);
572
		attr->reg = get_st_reg(0);
Michael Beck's avatar
Michael Beck committed
573

574
		keep_alive(fpop);
Michael Beck's avatar
Michael Beck committed
575
		sched_add_before(n, fpop);
576
		DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->reg->name));
577
	} while (--num > 0);
Michael Beck's avatar
Michael Beck committed
578
	return fpop;
579
}
Michael Beck's avatar
Michael Beck committed
580

581
582
583
584
585
586
/* --------------------------------- 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
587
 *
588
589
590
 * @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
591
592
 *
 * @return The live bitset.
593
 */
594
static vfp_liveness vfp_liveness_transfer(ir_node *irn, vfp_liveness live)
595
596
597
598
{
	int i, n;
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];

599
600
601
602
	if (get_irn_mode(irn) == mode_T) {
		foreach_out_edge(irn, edge) {
			ir_node *proj = get_edge_src_irn(edge);

603
			if (arch_irn_consider_in_reg_alloc(cls, proj)) {
604
				const arch_register_t *reg = x87_get_irn_register(proj);
605
				live &= ~(1 << reg->index);
606
607
			}
		}
608
	} else if (arch_irn_consider_in_reg_alloc(cls, irn)) {
609
		const arch_register_t *reg = x87_get_irn_register(irn);
610
		live &= ~(1 << reg->index);
611
612
	}

Michael Beck's avatar
Michael Beck committed
613
	for (i = 0, n = get_irn_arity(irn); i < n; ++i) {
614
615
		ir_node *op = get_irn_n(irn, i);

616
617
		if (mode_is_float(get_irn_mode(op)) &&
				arch_irn_consider_in_reg_alloc(cls, op)) {
618
			const arch_register_t *reg = x87_get_irn_register(op);
619
			live |= 1 << reg->index;
620
621
622
		}
	}
	return live;
623
}
624
625
626

/**
 * Put all live virtual registers at the end of a block into a bitset.
Michael Beck's avatar
BugFix:    
Michael Beck committed
627
 *
Michael Beck's avatar
Michael Beck committed
628
 * @param sim      the simulator handle
Michael Beck's avatar
BugFix:    
Michael Beck committed
629
630
631
 * @param bl       the block
 *
 * @return The live bitset at the end of this block
632
 */
Matthias Braun's avatar
Matthias Braun committed
633
static vfp_liveness vfp_liveness_end_of_block(x87_simulator *sim, const ir_node *block)
634
{
Matthias Braun's avatar
Matthias Braun committed
635
	vfp_liveness live = 0;
636
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
Matthias Braun's avatar
Matthias Braun committed
637
	const be_lv_t *lv = sim->lv;
638

639
	be_lv_foreach(lv, block, be_lv_state_end, node) {
Matthias Braun's avatar
Matthias Braun committed
640
		const arch_register_t *reg;
641
		if (!arch_irn_consider_in_reg_alloc(cls, node))
Matthias Braun's avatar
Matthias Braun committed
642
643
			continue;

644
		reg = x87_get_irn_register(node);
645
		live |= 1 << reg->index;
646
647
648
	}

	return live;
649
}
650

651
/** get the register mask from an arch_register */
652
#define REGMASK(reg)    (1 << (reg->index))
653

654
/**
655
 * Return a bitset of argument registers which are live at the end of a node.
Michael Beck's avatar
BugFix:    
Michael Beck committed
656
657
658
 *
 * @param sim    the simulator handle
 * @param pos    the node
659
 * @param kill   kill mask for the output registers
Michael Beck's avatar
BugFix:    
Michael Beck committed
660
 *
661
662
 * @return The live bitset.
 */
663
static unsigned vfp_live_args_after(x87_simulator *sim, const ir_node *pos, unsigned kill)
664
{
Michael Beck's avatar
BugFix:    
Michael Beck committed
665
	unsigned idx = get_irn_idx(pos);
666

Michael Beck's avatar
BugFix:    
Michael Beck committed
667
	assert(idx < sim->n_idx);
668
	return sim->live[idx] & ~kill;
669
}
670

Michael Beck's avatar
BugFix:    
Michael Beck committed
671
672
673
/**
 * Calculate the liveness for a whole block and cache it.
 *
Matthias Braun's avatar
Matthias Braun committed
674
675
 * @param sim   the simulator handle
 * @param block the block
Michael Beck's avatar
BugFix:    
Michael Beck committed
676
 */
Christoph Mallon's avatar
Christoph Mallon committed
677
678
static void update_liveness(x87_simulator *sim, ir_node *block)
{
Matthias Braun's avatar
Matthias Braun committed
679
	vfp_liveness live = vfp_liveness_end_of_block(sim, block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
680
681
682
	unsigned idx;

	/* now iterate through the block backward and cache the results */
Matthias Braun's avatar
Matthias Braun committed
683
	sched_foreach_reverse(block, irn) {
684
685
686
687
		/* stop at the first Phi: this produces the live-in */
		if (is_Phi(irn))
			break;

Michael Beck's avatar
BugFix:    
Michael Beck committed
688
689
		idx = get_irn_idx(irn);
		sim->live[idx] = live;
690

691
		live = vfp_liveness_transfer(irn, live);
692
	}
Matthias Braun's avatar
Matthias Braun committed
693
	idx = get_irn_idx(block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
694
	sim->live[idx] = live;
695
}
696
697
698

/**
 * Returns true if a register is live in a set.
Michael Beck's avatar
Michael Beck committed
699
700
701
 *
 * @param reg_idx  the vfp register index
 * @param live     a live bitset
702
 */
Michael Beck's avatar
BugFix:    
Michael Beck committed
703
#define is_vfp_live(reg_idx, live) ((live) & (1 << (reg_idx)))
704

705
706
#ifdef DEBUG_libfirm
/**
Michael Beck's avatar
Michael Beck committed
707
708
709
 * Dump liveness info.
 *
 * @param live  the live bitset
710
 */
Christoph Mallon's avatar
Christoph Mallon committed
711
712
static void vfp_dump_live(vfp_liveness live)
{
713
714
	int i;

Matthias Braun's avatar
Matthias Braun committed
715
	DB((dbg, LEVEL_2, "Live after: "));
716
717
	for (i = 0; i < 8; ++i) {
		if (live & (1 << i)) {
Matthias Braun's avatar
Matthias Braun committed
718
			DB((dbg, LEVEL_2, "vf%d ", i));
719
720
		}
	}
721
	DB((dbg, LEVEL_2, "\n"));
722
}
723
#endif /* DEBUG_libfirm */
724
725
726

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

727
/**
Michael Beck's avatar
Michael Beck committed
728
729
730
731
 * 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
732
733
 *
 * @return NO_NODE_ADDED
734
 */
735
static int sim_binop(x87_state *const state, ir_node *const n, ir_op *const op)
Christoph Mallon's avatar
Christoph Mallon committed
736
{
737
	ir_node *patched_insn;
738
	x87_simulator         *sim     = state->sim;
739
740
	ir_node               *op1     = get_irn_n(n, n_ia32_binary_left);
	ir_node               *op2     = get_irn_n(n, n_ia32_binary_right);
741
742
	const arch_register_t *op1_reg = x87_get_irn_register(op1);
	const arch_register_t *op2_reg = x87_get_irn_register(op2);
743
	const arch_register_t *out     = x87_irn_get_register(n, pn_ia32_res);
744
745
	int reg_index_1                = op1_reg->index;
	int reg_index_2                = op2_reg->index;
746
747
748
	vfp_liveness           live    = vfp_live_args_after(sim, n, REGMASK(out));
	int                    op1_live_after;
	int                    op2_live_after;
749

750
	DB((dbg, LEVEL_1, ">>> %+F %s, %s -> %s\n", n, op1_reg->name, op2_reg->name, out->name));
751
	DEBUG_ONLY(vfp_dump_live(live);)
Matthias Braun's avatar
Matthias Braun committed
752
	DB((dbg, LEVEL_1, "Stack before: "));
753
	DEBUG_ONLY(x87_dump_stack(state);)
754

755
	int op1_idx = x87_on_stack(state, reg_index_1);
756
	assert(op1_idx >= 0);
757
	op1_live_after = is_vfp_live(reg_index_1, live);
758

759
760
761
762
763
	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);
764
	if (reg_index_2 != REG_VFP_VFP_NOREG) {
765
766
767
		/* second operand is a vfp register */
		op2_idx = x87_on_stack(state, reg_index_2);
		assert(op2_idx >= 0);
768
		op2_live_after = is_vfp_live(reg_index_2, live);
769

770
		if (op2_live_after) {
Michael Beck's avatar
Michael Beck committed
771
			/* Second operand is live. */
772

773
			if (op1_live_after) {
Michael Beck's avatar
Michael Beck committed
774
775
				/* Both operands are live: push the first one.
				   This works even for op1 == op2. */
776
				x87_create_fpush(state, n, op1_idx, out_reg_idx, op2);
Matthias Braun's avatar
Matthias Braun committed
777
778
779
780
781
				/* now do fxxx (tos=tos X op) */
				op1_idx = 0;
				op2_idx += 1;
				out_idx = 0;
			} else {
Michael Beck's avatar
Michael Beck committed
782
				/* Second live, first operand is dead here, bring it to tos. */
783
				if (op1_idx != 0) {
Matthias Braun's avatar
Matthias Braun committed
784
					x87_create_fxch(state, n, op1_idx);
785
786
					if (op2_idx == 0)
						op2_idx = op1_idx;
Matthias Braun's avatar
Matthias Braun committed
787
					op1_idx = 0;
788
				}
Matthias Braun's avatar
Matthias Braun committed
789
790
				/* now do fxxx (tos=tos X op) */
				out_idx = 0;
791
			}
792
		} else {
Michael Beck's avatar
Michael Beck committed
793
			/* Second operand is dead. */
794
			if (op1_live_after) {
Michael Beck's avatar
Michael Beck committed
795
				/* First operand is live: bring second to tos. */
796
				if (op2_idx != 0) {
Matthias Braun's avatar
Matthias Braun committed
797
					x87_create_fxch(state, n, op2_idx);
798
799
					if (op1_idx == 0)
						op1_idx = op2_idx;
Matthias Braun's avatar
Matthias Braun committed
800
					op2_idx = 0;
801
				}
Matthias Braun's avatar
Matthias Braun committed
802
803
				/* now do fxxxr (tos = op X tos) */
				out_idx = 0;
804
			} else {
Michael Beck's avatar
Michael Beck committed
805
				/* Both operands are dead here, pop them from the stack. */
806
				if (op2_idx == 0) {
Matthias Braun's avatar
Matthias Braun committed
807
808
809
810
					if (op1_idx == 0) {
						/* Both are identically and on tos, no pop needed. */
						/* here fxxx (tos = tos X tos) */
						out_idx = 0;
811
					} else {
Matthias Braun's avatar
Matthias Braun committed
812
813
						/* now do fxxxp (op = op X tos, pop) */
						out_idx = op1_idx;
814
						pop     = true;
Michael Beck's avatar
Michael Beck committed
815
					}
816
				} else if (op1_idx == 0) {
Matthias Braun's avatar
Matthias Braun committed
817
818
					assert(op1_idx != op2_idx);
					/* now do fxxxrp (op = tos X op, pop) */
819
					out_idx = op2_idx;
820
					pop     = true;
821
				} else {
Michael Beck's avatar
BugFix:    
Michael Beck committed
822
					/* Bring the second on top. */
Matthias Braun's avatar
Matthias Braun committed
823
					x87_create_fxch(state, n, op2_idx);
Michael Beck's avatar
Michael Beck committed
824
					if (op1_idx == op2_idx) {
Matthias Braun's avatar
Matthias Braun committed
825
826
827
828
829
						/* Both are identically and on tos now, no pop needed. */
						op1_idx = 0;
						op2_idx = 0;
						/* use fxxx (tos = tos X tos) */
						out_idx = 0;
830
					} else {
Matthias Braun's avatar
Matthias Braun committed
831
						/* op2 is on tos now */
Michael Beck's avatar
BugFix:    
Michael Beck committed
832
						op2_idx = 0;
Matthias Braun's avatar
Matthias Braun committed
833
834
						/* use fxxxp (op = op X tos, pop) */
						out_idx = op1_idx;
835
						pop     = true;
Michael Beck's avatar
Michael Beck committed
836
					}
837
				}
838
			}
839
		}
840
	} else {
841
		/* second operand is an address mode */
842
		if (op1_live_after) {
843
			/* first operand is live: push it here */