ia32_x87.c 67.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 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
25
 * @file
 * @brief       This file implements the x87 support and virtual to stack
 *              register translation for the ia32 backend.
 * @author      Michael Beck
 * @version     $Id$
26
 */
27
#include "config.h"
28

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

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

46
#include "../belive_t.h"
47
#include "../besched.h"
48
#include "../benode_t.h"
49
#include "bearch_ia32_t.h"
50
51
52
53
#include "ia32_new_nodes.h"
#include "gen_ia32_new_nodes.h"
#include "gen_ia32_regalloc_if.h"
#include "ia32_x87.h"
54
#include "ia32_architecture.h"
55
56
57
58

#define N_x87_REGS 8

/* the unop index */
59
#define UNOP_IDX 0
60
61
62

#define MASK_TOS(x)		((x) & (N_x87_REGS - 1))

63
/** the debug handle */
64
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
65

Sebastian Hack's avatar
Sebastian Hack committed
66
67
68
/* Forward declaration. */
typedef struct _x87_simulator x87_simulator;

69
70
71
/**
 * An exchange template.
 * Note that our virtual functions have the same inputs
72
 * and attributes as the real ones, so we can simple exchange
73
74
75
76
 * their opcodes!
 * Further, x87 supports inverse instructions, so we can handle them.
 */
typedef struct _exchange_tmpl {
77
78
79
80
	ir_op *normal_op;       /**< the normal one */
	ir_op *reverse_op;      /**< the reverse one if exists */
	ir_op *normal_pop_op;   /**< the normal one with tos pop */
	ir_op *reverse_pop_op;  /**< the reverse one with tos pop */
81
82
} exchange_tmpl;

83
84
85
86
87
88
89
90
/**
 * An entry on the simulated x87 stack.
 */
typedef struct _st_entry {
	int     reg_idx;        /**< the virtual register index of this stack value */
	ir_node *node;          /**< the node that produced this value */
} st_entry;

91
92
93
94
/**
 * The x87 state.
 */
typedef struct _x87_state {
95
96
97
	st_entry st[N_x87_REGS];  /**< the register stack */
	int depth;                /**< the current stack depth */
	int tos;                  /**< position of the tos */
Sebastian Hack's avatar
Sebastian Hack committed
98
	x87_simulator *sim;       /**< The simulator. */
99
100
101
} x87_state;

/** An empty state, used for blocks without fp instructions. */
Matthias Braun's avatar
Matthias Braun committed
102
static x87_state _empty = { { {0, NULL}, }, 0, 0, NULL };
103
104
static x87_state *empty = (x87_state *)&_empty;

105
106
107
/**
 * Return values of the instruction simulator functions.
 */
Michael Beck's avatar
Michael Beck committed
108
enum {
109
110
111
	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
112
113
114
115
116
117
118
119
};

/**
 * The type of an instruction simulator function.
 *
 * @param state  the x87 state
 * @param n      the node to be simulated
 *
120
121
122
 * @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
123
 */
Michael Beck's avatar
Michael Beck committed
124
typedef int (*sim_func)(x87_state *state, ir_node *n);
125
126
127
128
129
130
131
132
133
134
135

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

#define PTR_TO_BLKSTATE(p)	((blk_state *)(p))

Matthias Braun's avatar
Matthias Braun committed
136
137
138
/** liveness bitset for vfp registers. */
typedef unsigned char vfp_liveness;

139
140
141
/**
 * The x87 simulator.
 */
Sebastian Hack's avatar
Sebastian Hack committed
142
struct _x87_simulator {
143
144
145
146
147
	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. */
Michael Beck's avatar
Michael Beck committed
148
	waitq *worklist;            /**< Worklist of blocks that must be processed. */
149
	ia32_isa_t *isa;            /**< the ISA object */
Sebastian Hack's avatar
Sebastian Hack committed
150
};
151

Michael Beck's avatar
Michael Beck committed
152
/**
Michael Beck's avatar
BugFix:    
Michael Beck committed
153
 * Returns the current stack depth.
Michael Beck's avatar
Michael Beck committed
154
155
156
157
158
 *
 * @param state  the x87 state
 *
 * @return the x87 stack depth
 */
Christoph Mallon's avatar
Christoph Mallon committed
159
160
static int x87_get_depth(const x87_state *state)
{
Michael Beck's avatar
Michael Beck committed
161
	return state->depth;
Michael Beck's avatar
Michael Beck committed
162
}  /* x87_get_depth */
163
164

/**
165
 * Return the virtual register index at st(pos).
Michael Beck's avatar
Michael Beck committed
166
167
168
169
170
 *
 * @param state  the x87 state
 * @param pos    a stack position
 *
 * @return the vfp register index that produced the value at st(pos)
171
 */
Christoph Mallon's avatar
Christoph Mallon committed
172
173
static int x87_get_st_reg(const x87_state *state, int pos)
{
174
175
	assert(pos < state->depth);
	return state->st[MASK_TOS(state->tos + pos)].reg_idx;
Michael Beck's avatar
Michael Beck committed
176
}  /* x87_get_st_reg */
177

Matthias Braun's avatar
Matthias Braun committed
178
#ifdef DEBUG_libfirm
179
180
/**
 * Return the node at st(pos).
Michael Beck's avatar
Michael Beck committed
181
182
183
184
185
 *
 * @param state  the x87 state
 * @param pos    a stack position
 *
 * @return the IR node that produced the value at st(pos)
186
 */
Christoph Mallon's avatar
Christoph Mallon committed
187
188
static ir_node *x87_get_st_node(const x87_state *state, int pos)
{
189
	assert(pos < state->depth);
190
	return state->st[MASK_TOS(state->tos + pos)].node;
Michael Beck's avatar
BugFix:    
Michael Beck committed
191
}  /* x87_get_st_node */
192
193
194

/**
 * Dump the stack for debugging.
Michael Beck's avatar
Michael Beck committed
195
196
 *
 * @param state  the x87 state
197
 */
Christoph Mallon's avatar
Christoph Mallon committed
198
199
static void x87_dump_stack(const x87_state *state)
{
200
201
202
	int i;

	for (i = state->depth - 1; i >= 0; --i) {
203
204
		DB((dbg, LEVEL_2, "vf%d(%+F) ", x87_get_st_reg(state, i),
		    x87_get_st_node(state, i)));
205
	}
206
	DB((dbg, LEVEL_2, "<-- TOS\n"));
Michael Beck's avatar
BugFix:    
Michael Beck committed
207
}  /* x87_dump_stack */
208
#endif /* DEBUG_libfirm */
209
210

/**
Michael Beck's avatar
Michael Beck committed
211
212
213
214
215
216
 * 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
217
 */
Christoph Mallon's avatar
Christoph Mallon committed
218
219
static void x87_set_st(x87_state *state, int reg_idx, ir_node *node, int pos)
{
220
	assert(0 < state->depth);
221
222
	state->st[MASK_TOS(state->tos + pos)].reg_idx = reg_idx;
	state->st[MASK_TOS(state->tos + pos)].node    = node;
223

Matthias Braun's avatar
Matthias Braun committed
224
225
	DB((dbg, LEVEL_2, "After SET_REG: "));
	DEBUG_ONLY(x87_dump_stack(state));
Michael Beck's avatar
BugFix:    
Michael Beck committed
226
}  /* x87_set_st */
227

228
/**
Michael Beck's avatar
Michael Beck committed
229
230
231
232
233
 * Set the tos virtual register.
 *
 * @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
234
 */
Christoph Mallon's avatar
Christoph Mallon committed
235
236
static void x87_set_tos(x87_state *state, int reg_idx, ir_node *node)
{
237
	x87_set_st(state, reg_idx, node, 0);
Michael Beck's avatar
BugFix:    
Michael Beck committed
238
}  /* x87_set_tos */
239
240
241

/**
 * Swap st(0) with st(pos).
Michael Beck's avatar
Michael Beck committed
242
243
244
 *
 * @param state    the x87 state
 * @param pos      the stack position to change the tos with
245
 */
Christoph Mallon's avatar
Christoph Mallon committed
246
247
static void x87_fxch(x87_state *state, int pos)
{
248
	st_entry entry;
249
250
	assert(pos < state->depth);

251
	entry = state->st[MASK_TOS(state->tos + pos)];
252
	state->st[MASK_TOS(state->tos + pos)] = state->st[MASK_TOS(state->tos)];
253
	state->st[MASK_TOS(state->tos)] = entry;
254

Matthias Braun's avatar
Matthias Braun committed
255
	DB((dbg, LEVEL_2, "After FXCH: ")); DEBUG_ONLY(x87_dump_stack(state));
Michael Beck's avatar
BugFix:    
Michael Beck committed
256
}  /* x87_fxch */
257
258
259

/**
 * Convert a virtual register to the stack index.
Michael Beck's avatar
Michael Beck committed
260
261
262
263
264
265
 *
 * @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
266
 */
Christoph Mallon's avatar
Christoph Mallon committed
267
268
static int x87_on_stack(const x87_state *state, int reg_idx)
{
269
270
271
	int i, tos = state->tos;

	for (i = 0; i < state->depth; ++i)
272
		if (state->st[MASK_TOS(tos + i)].reg_idx == reg_idx)
273
274
			return i;
	return -1;
Michael Beck's avatar
BugFix:    
Michael Beck committed
275
}  /* x87_on_stack */
276
277

/**
Michael Beck's avatar
BugFix:    
Michael Beck committed
278
 * Push a virtual Register onto the stack, double pushed allowed.
Michael Beck's avatar
Michael Beck committed
279
 *
280
281
282
 * @param state     the x87 state
 * @param reg_idx   the register vfp index
 * @param node      the node that produces the value of the vfp register
283
 */
Christoph Mallon's avatar
Christoph Mallon committed
284
285
static void x87_push_dbl(x87_state *state, int reg_idx, ir_node *node)
{
286
287
288
289
	assert(state->depth < N_x87_REGS && "stack overrun");

	++state->depth;
	state->tos = MASK_TOS(state->tos - 1);
290
291
	state->st[state->tos].reg_idx = reg_idx;
	state->st[state->tos].node    = node;
292

Matthias Braun's avatar
Matthias Braun committed
293
	DB((dbg, LEVEL_2, "After PUSH: ")); DEBUG_ONLY(x87_dump_stack(state));
Michael Beck's avatar
BugFix:    
Michael Beck committed
294
}  /* x87_push_dbl */
295

Michael Beck's avatar
BugFix:    
Michael Beck committed
296
/**
Michael Beck's avatar
Michael Beck committed
297
 * Push a virtual Register onto the stack, double pushes are NOT allowed.
Michael Beck's avatar
BugFix:    
Michael Beck committed
298
299
300
301
302
303
 *
 * @param state     the x87 state
 * @param reg_idx   the register vfp index
 * @param node      the node that produces the value of the vfp register
 * @param dbl_push  if != 0 double pushes are allowed
 */
Christoph Mallon's avatar
Christoph Mallon committed
304
305
static void x87_push(x87_state *state, int reg_idx, ir_node *node)
{
Michael Beck's avatar
BugFix:    
Michael Beck committed
306
307
308
	assert(x87_on_stack(state, reg_idx) == -1 && "double push");

	x87_push_dbl(state, reg_idx, node);
Michael Beck's avatar
BugFix:    
Michael Beck committed
309
}  /* x87_push */
Michael Beck's avatar
BugFix:    
Michael Beck committed
310

311
312
/**
 * Pop a virtual Register from the stack.
Michael Beck's avatar
Michael Beck committed
313
314
 *
 * @param state     the x87 state
315
 */
Christoph Mallon's avatar
Christoph Mallon committed
316
317
static void x87_pop(x87_state *state)
{
318
319
320
321
322
	assert(state->depth > 0 && "stack underrun");

	--state->depth;
	state->tos = MASK_TOS(state->tos + 1);

Matthias Braun's avatar
Matthias Braun committed
323
	DB((dbg, LEVEL_2, "After POP: ")); DEBUG_ONLY(x87_dump_stack(state));
Michael Beck's avatar
BugFix:    
Michael Beck committed
324
}  /* x87_pop */
325

326
327
328
329
330
/**
 * Empty the fpu stack
 *
 * @param state     the x87 state
 */
Christoph Mallon's avatar
Christoph Mallon committed
331
332
static void x87_emms(x87_state *state)
{
333
334
335
336
	state->depth = 0;
	state->tos   = 0;
}

337
338
/**
 * Returns the block state of a block.
Michael Beck's avatar
Michael Beck committed
339
340
341
342
343
 *
 * @param sim    the x87 simulator handle
 * @param block  the current block
 *
 * @return the block state
344
 */
Christoph Mallon's avatar
Christoph Mallon committed
345
346
static blk_state *x87_get_bl_state(x87_simulator *sim, ir_node *block)
{
347
348
349
350
351
352
353
354
355
356
357
	pmap_entry *entry = pmap_find(sim->blk_states, block);

	if (! entry) {
		blk_state *bl_state = obstack_alloc(&sim->obst, sizeof(*bl_state));
		bl_state->begin = NULL;
		bl_state->end   = NULL;

		pmap_insert(sim->blk_states, block, bl_state);
		return bl_state;
	}

Michael Beck's avatar
BugFix:    
Michael Beck committed
358
	return PTR_TO_BLKSTATE(entry->value);
Michael Beck's avatar
BugFix:    
Michael Beck committed
359
}  /* x87_get_bl_state */
360
361

/**
Michael Beck's avatar
Michael Beck committed
362
363
364
 * Creates a new x87 state.
 *
 * @param sim    the x87 simulator handle
Michael Beck's avatar
BugFix:    
Michael Beck committed
365
 *
Michael Beck's avatar
Michael Beck committed
366
 * @return a new x87 state
367
 */
Christoph Mallon's avatar
Christoph Mallon committed
368
369
static x87_state *x87_alloc_state(x87_simulator *sim)
{
370
	x87_state *res = obstack_alloc(&sim->obst, sizeof(*res));
Michael Beck's avatar
BugFix:    
Michael Beck committed
371

Sebastian Hack's avatar
Sebastian Hack committed
372
	res->sim = sim;
373
	return res;
Michael Beck's avatar
BugFix:    
Michael Beck committed
374
}  /* x87_alloc_state */
375
376
377

/**
 * Clone a x87 state.
Michael Beck's avatar
Michael Beck committed
378
379
380
381
382
 *
 * @param sim    the x87 simulator handle
 * @param src    the x87 state that will be cloned
 *
 * @return a cloned copy of the src state
383
 */
Christoph Mallon's avatar
Christoph Mallon committed
384
385
static x87_state *x87_clone_state(x87_simulator *sim, const x87_state *src)
{
386
387
	x87_state *res = x87_alloc_state(sim);

388
	*res = *src;
389
	return res;
Michael Beck's avatar
BugFix:    
Michael Beck committed
390
}  /* x87_clone_state */
391

392
393
/**
 * Patch a virtual instruction into a x87 one and return
Michael Beck's avatar
Michael Beck committed
394
 * the node representing the result value.
Michael Beck's avatar
Michael Beck committed
395
396
397
 *
 * @param n   the IR node to patch
 * @param op  the x87 opcode to patch in
398
 */
Christoph Mallon's avatar
Christoph Mallon committed
399
400
static ir_node *x87_patch_insn(ir_node *n, ir_op *op)
{
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
	ir_mode *mode = get_irn_mode(n);
	ir_node *res = n;

	set_irn_op(n, op);

	if (mode == mode_T) {
		/* patch all Proj's */
		const ir_edge_t *edge;

		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;
416
					set_irn_mode(proj, ia32_reg_classes[CLASS_ia32_st].mode);
417
418
419
				}
			}
		}
Michael Beck's avatar
Michael Beck committed
420
	} else if (mode_is_float(mode))
421
		set_irn_mode(n, ia32_reg_classes[CLASS_ia32_st].mode);
422
	return res;
Michael Beck's avatar
BugFix:    
Michael Beck committed
423
}  /* x87_patch_insn */
424

425
426
427
428
429
430
431
/**
 * 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
 * @return The first Proj of mode @p m found or NULL.
 */
Christoph Mallon's avatar
Christoph Mallon committed
432
433
static ir_node *get_irn_Proj_for_mode(ir_node *n, ir_mode *m)
{
434
435
436
437
438
439
440
441
442
443
444
	const ir_edge_t *edge;

	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;
	}

	return NULL;
Michael Beck's avatar
BugFix:    
Michael Beck committed
445
}  /* get_irn_Proj_for_mode */
446

Michael Beck's avatar
Michael Beck committed
447
448
449
/**
 * Wrap the arch_* function here so we can check for errors.
 */
450
static inline const arch_register_t *x87_get_irn_register(const ir_node *irn)
Christoph Mallon's avatar
Christoph Mallon committed
451
{
452
	const arch_register_t *res = arch_get_irn_register(irn);
Michael Beck's avatar
Michael Beck committed
453
454
455

	assert(res->reg_class->regs == ia32_vfp_regs);
	return res;
Michael Beck's avatar
Michael Beck committed
456
}  /* x87_get_irn_register */
Michael Beck's avatar
Michael Beck committed
457

458
459
460
461
462
463
464
static inline const arch_register_t *x87_irn_get_register(const ir_node *irn,
                                                          int pos)
{
	const arch_register_t *res = arch_irn_get_register(irn, pos);

	assert(res->reg_class->regs == ia32_vfp_regs);
	return res;
465
}  /* x87_irn_get_register */
466

467
468
/* -------------- x87 perm --------------- */

469
470
471
472
473
/**
 * Creates a fxch for shuffle.
 *
 * @param state     the x87 state
 * @param pos       parameter for fxch
Michael Beck's avatar
Michael Beck committed
474
 * @param block     the block were fxch is inserted
475
476
477
478
479
480
 *
 * Creates a new fxch node and reroute the user of the old node
 * to the fxch.
 *
 * @return the fxch node
 */
Christoph Mallon's avatar
Christoph Mallon committed
481
482
static ir_node *x87_fxch_shuffle(x87_state *state, int pos, ir_node *block)
{
Michael Beck's avatar
Michael Beck committed
483
	ir_node         *fxch;
484
	ia32_x87_attr_t *attr;
485

486
	fxch = new_bd_ia32_fxch(NULL, block);
487
	attr = get_ia32_x87_attr(fxch);
488
489
490
	attr->x87[0] = &ia32_st_regs[pos];
	attr->x87[2] = &ia32_st_regs[0];

Michael Beck's avatar
Michael Beck committed
491
	keep_alive(fxch);
492
493
494

	x87_fxch(state, pos);
	return fxch;
Michael Beck's avatar
BugFix:    
Michael Beck committed
495
}  /* x87_fxch_shuffle */
496

497
498
/**
 * Calculate the necessary permutations to reach dst_state.
499
500
501
502
503
504
505
506
507
508
509
510
511
512
 *
 * 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 sim        the simulator handle
 * @param block      the current block
 * @param state      the current x87 stack state, might be modified
 * @param dst_block  the destination block
 * @param dst_state  destination state
 *
 * @return state
513
 */
Matthias Braun's avatar
Matthias Braun committed
514
515
516
517
static x87_state *x87_shuffle(x87_simulator *sim, ir_node *block,
                              x87_state *state, ir_node *dst_block,
                              const x87_state *dst_state)
{
Michael Beck's avatar
Michael Beck committed
518
	int      i, n_cycles, k, ri;
Michael Beck's avatar
Michael Beck committed
519
	unsigned cycles[4], all_mask;
Michael Beck's avatar
Michael Beck committed
520
521
	char     cycle_idx[4][8];
	ir_node  *fxch, *before, *after;
Matthias Braun's avatar
Matthias Braun committed
522
523
	(void) sim;
	(void) dst_block;
524

525
526
	assert(state->depth == dst_state->depth);

527
	/* Some mathematics here:
Michael Beck's avatar
BugFix:    
Michael Beck committed
528
	   If we have a cycle of length n that includes the tos,
529
530
	   we need n-1 exchange operations.
	   We can always add the tos and restore it, so we need
Michael Beck's avatar
Michael Beck committed
531
532
	   n+1 exchange operations for a cycle not containing the tos.
	   So, the maximum of needed operations is for a cycle of 7
533
	   not including the tos == 8.
Michael Beck's avatar
BugFix:    
Michael Beck committed
534
	   This is the same number of ops we would need for using stores,
535
536
537
538
	   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.
Michael Beck's avatar
BugFix:    
Michael Beck committed
539
	   Further, no more than 4 cycles can exists (4 x 2).
540
541
542
	*/
	all_mask = (1 << (state->depth)) - 1;

Michael Beck's avatar
Michael Beck committed
543
	for (n_cycles = 0; all_mask; ++n_cycles) {
544
545
546
547
548
549
550
551
		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 */
552
				if (x87_get_st_reg(state, i) != x87_get_st_reg(dst_state, i))
553
554
555
556
557
					break;
			}
		}

		if (! all_mask) {
Michael Beck's avatar
Michael Beck committed
558
			/* no more cycles found */
559
560
561
562
			break;
		}

		k = 0;
Michael Beck's avatar
Michael Beck committed
563
564
		cycles[n_cycles] = (1 << i);
		cycle_idx[n_cycles][k++] = i;
565
		for (src_idx = i; ; src_idx = dst_idx) {
566
			dst_idx = x87_on_stack(dst_state, x87_get_st_reg(state, src_idx));
567
568
569
570

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

Michael Beck's avatar
Michael Beck committed
571
572
			cycle_idx[n_cycles][k++] = dst_idx;
			cycles[n_cycles] |=  (1 << dst_idx);
573
574
			all_mask       &= ~(1 << dst_idx);
		}
Michael Beck's avatar
Michael Beck committed
575
		cycle_idx[n_cycles][k] = -1;
576
577
	}

Michael Beck's avatar
Michael Beck committed
578
	if (n_cycles <= 0) {
579
580
581
582
583
		/* no permutation needed */
		return state;
	}

	/* Hmm: permutation needed */
584
	DB((dbg, LEVEL_2, "\n%+F needs permutation: from\n", block));
585
586
587
588
589
590
	DEBUG_ONLY(x87_dump_stack(state));
	DB((dbg, LEVEL_2, "                  to\n"));
	DEBUG_ONLY(x87_dump_stack(dst_state));


#ifdef DEBUG_libfirm
Michael Beck's avatar
Michael Beck committed
591
592
	DB((dbg, LEVEL_2, "Need %d cycles\n", n_cycles));
	for (ri = 0; ri < n_cycles; ++ri) {
593
		DB((dbg, LEVEL_2, " Ring %d:\n ", ri));
Michael Beck's avatar
Michael Beck committed
594
595
		for (k = 0; cycle_idx[ri][k] != -1; ++k)
			DB((dbg, LEVEL_2, " st%d ->", cycle_idx[ri][k]));
596
597
598
599
		DB((dbg, LEVEL_2, "\n"));
	}
#endif

600
601
602
603
604
605
606
607
608
609
	after = NULL;

	/*
	 * Find the place node must be insert.
	 * We have only one successor block, so the last instruction should
	 * be a jump.
	 */
	before = sched_last(block);
	assert(is_cfop(before));

610
	/* now do the permutations */
Michael Beck's avatar
Michael Beck committed
611
612
613
	for (ri = 0; ri < n_cycles; ++ri) {
		if ((cycles[ri] & 1) == 0) {
			/* this cycle does not include the tos */
Michael Beck's avatar
Michael Beck committed
614
			fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block);
615
616
617
618
619
			if (after)
				sched_add_after(after, fxch);
			else
				sched_add_before(before, fxch);
			after = fxch;
620
		}
Michael Beck's avatar
Michael Beck committed
621
		for (k = 1; cycle_idx[ri][k] != -1; ++k) {
Michael Beck's avatar
Michael Beck committed
622
			fxch = x87_fxch_shuffle(state, cycle_idx[ri][k], block);
623
624
625
626
627
			if (after)
				sched_add_after(after, fxch);
			else
				sched_add_before(before, fxch);
			after = fxch;
628
		}
Michael Beck's avatar
Michael Beck committed
629
630
		if ((cycles[ri] & 1) == 0) {
			/* this cycle does not include the tos */
Michael Beck's avatar
Michael Beck committed
631
			fxch = x87_fxch_shuffle(state, cycle_idx[ri][0], block);
632
			sched_add_after(after, fxch);
633
634
		}
	}
635
	return state;
Michael Beck's avatar
BugFix:    
Michael Beck committed
636
}  /* x87_shuffle */
637
638

/**
Michael Beck's avatar
Michael Beck committed
639
640
641
 * Create a fxch node before another node.
 *
 * @param state   the x87 state
Michael Beck's avatar
Michael Beck committed
642
 * @param n       the node after the fxch
Michael Beck's avatar
Michael Beck committed
643
644
645
 * @param pos     exchange st(pos) with st(0)
 *
 * @return the fxch
646
 */
Matthias Braun's avatar
Matthias Braun committed
647
648
static ir_node *x87_create_fxch(x87_state *state, ir_node *n, int pos)
{
649
650
651
	ir_node         *fxch;
	ia32_x87_attr_t *attr;
	ir_node         *block = get_nodes_block(n);
652
653
654

	x87_fxch(state, pos);

655
	fxch = new_bd_ia32_fxch(NULL, block);
656
	attr = get_ia32_x87_attr(fxch);
657
658
	attr->x87[0] = &ia32_st_regs[pos];
	attr->x87[2] = &ia32_st_regs[0];
Michael Beck's avatar
Michael Beck committed
659

Michael Beck's avatar
Michael Beck committed
660
	keep_alive(fxch);
661
662

	sched_add_before(n, fxch);
663
	DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fxch), attr->x87[0]->name, attr->x87[2]->name));
Michael Beck's avatar
Michael Beck committed
664
	return fxch;
Michael Beck's avatar
BugFix:    
Michael Beck committed
665
}  /* x87_create_fxch */
666
667
668

/**
 * Create a fpush before node n.
Michael Beck's avatar
Michael Beck committed
669
 *
670
 * @param state     the x87 state
Michael Beck's avatar
Michael Beck committed
671
 * @param n         the node after the fpush
672
 * @param pos       push st(pos) on stack
Michael Beck's avatar
Michael Beck committed
673
 * @param op_idx    replace input op_idx of n with the fpush result
674
 */
Christoph Mallon's avatar
Christoph Mallon committed
675
676
static void x87_create_fpush(x87_state *state, ir_node *n, int pos, int op_idx)
{
Michael Beck's avatar
Michael Beck committed
677
	ir_node               *fpush, *pred = get_irn_n(n, op_idx);
678
	ia32_x87_attr_t       *attr;
679
	const arch_register_t *out = x87_get_irn_register(pred);
680

Michael Beck's avatar
BugFix:    
Michael Beck committed
681
	x87_push_dbl(state, arch_register_get_index(out), pred);
682

683
	fpush = new_bd_ia32_fpush(NULL, get_nodes_block(n));
684
	attr  = get_ia32_x87_attr(fpush);
685
686
687
	attr->x87[0] = &ia32_st_regs[pos];
	attr->x87[2] = &ia32_st_regs[0];

Michael Beck's avatar
Michael Beck committed
688
	keep_alive(fpush);
689
	sched_add_before(n, fpush);
Michael Beck's avatar
Michael Beck committed
690

691
	DB((dbg, LEVEL_1, "<<< %s %s, %s\n", get_irn_opname(fpush), attr->x87[0]->name, attr->x87[2]->name));
Michael Beck's avatar
BugFix:    
Michael Beck committed
692
}  /* x87_create_fpush */
693

Michael Beck's avatar
Michael Beck committed
694
695
696
697
/**
 * Create a fpop before node n.
 *
 * @param state   the x87 state
Michael Beck's avatar
Michael Beck committed
698
 * @param n       the node after the fpop
Michael Beck's avatar
Michael Beck committed
699
700
701
702
 * @param num     pop 1 or 2 values
 *
 * @return the fpop node
 */
Matthias Braun's avatar
Matthias Braun committed
703
704
static ir_node *x87_create_fpop(x87_state *state, ir_node *n, int num)
{
705
	ir_node         *fpop = NULL;
706
	ia32_x87_attr_t *attr;
Michael Beck's avatar
Michael Beck committed
707

Matthias Braun's avatar
Matthias Braun committed
708
	assert(num > 0);
Michael Beck's avatar
Michael Beck committed
709
710
	while (num > 0) {
		x87_pop(state);
711
		if (ia32_cg_config.use_ffreep)
712
			fpop = new_bd_ia32_ffreep(NULL, get_nodes_block(n));
713
		else
714
			fpop = new_bd_ia32_fpop(NULL, get_nodes_block(n));
715
		attr = get_ia32_x87_attr(fpop);
Michael Beck's avatar
Michael Beck committed
716
717
718
719
		attr->x87[0] = &ia32_st_regs[0];
		attr->x87[1] = &ia32_st_regs[0];
		attr->x87[2] = &ia32_st_regs[0];

720
		keep_alive(fpop);
Michael Beck's avatar
Michael Beck committed
721
722
723
724
725
726
		sched_add_before(n, fpop);
		DB((dbg, LEVEL_1, "<<< %s %s\n", get_irn_opname(fpop), attr->x87[0]->name));

		--num;
	}
	return fpop;
Michael Beck's avatar
BugFix:    
Michael Beck committed
727
}  /* x87_create_fpop */
Michael Beck's avatar
Michael Beck committed
728

729
730
731
732
733
734
735
736
/**
 * Creates an fldz before node n
 *
 * @param state   the x87 state
 * @param n       the node after the fldz
 *
 * @return the fldz node
 */
Christoph Mallon's avatar
Christoph Mallon committed
737
738
static ir_node *x87_create_fldz(x87_state *state, ir_node *n, int regidx)
{
739
740
741
	ir_node *block = get_nodes_block(n);
	ir_node *fldz;

742
	fldz = new_bd_ia32_fldz(NULL, block, ia32_reg_classes[CLASS_ia32_st].mode);
743
744
745
746
747
748
749
750
751
752

	sched_add_before(n, fldz);
	DB((dbg, LEVEL_1, "<<< %s\n", get_irn_opname(fldz)));
	keep_alive(fldz);

	x87_push(state, regidx, fldz);

	return fldz;
}

753
754
755
756
757
758
/* --------------------------------- 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
759
 *
760
761
762
 * @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
763
764
 *
 * @return The live bitset.
765
 */
766
static vfp_liveness vfp_liveness_transfer(ir_node *irn, vfp_liveness live)
767
768
769
770
{
	int i, n;
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];

771
772
773
774
775
776
	if (get_irn_mode(irn) == mode_T) {
		const ir_edge_t *edge;

		foreach_out_edge(irn, edge) {
			ir_node *proj = get_edge_src_irn(edge);

777
			if (arch_irn_consider_in_reg_alloc(cls, proj)) {
778
				const arch_register_t *reg = x87_get_irn_register(proj);
779
780
781
782
783
				live &= ~(1 << arch_register_get_index(reg));
			}
		}
	}

784
	if (arch_irn_consider_in_reg_alloc(cls, irn)) {
785
		const arch_register_t *reg = x87_get_irn_register(irn);
786
		live &= ~(1 << arch_register_get_index(reg));
787
788
	}

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

792
793
		if (mode_is_float(get_irn_mode(op)) &&
				arch_irn_consider_in_reg_alloc(cls, op)) {
794
			const arch_register_t *reg = x87_get_irn_register(op);
Michael Beck's avatar
Michael Beck committed
795
			live |= 1 << arch_register_get_index(reg);
796
797
798
		}
	}
	return live;
Michael Beck's avatar
BugFix:    
Michael Beck committed
799
}  /* vfp_liveness_transfer */
800
801
802

/**
 * Put all live virtual registers at the end of a block into a bitset.
Michael Beck's avatar
BugFix:    
Michael Beck committed
803
 *
Michael Beck's avatar
Michael Beck committed
804
 * @param sim      the simulator handle
Michael Beck's avatar
BugFix:    
Michael Beck committed
805
806
807
808
 * @param lv       the liveness information
 * @param bl       the block
 *
 * @return The live bitset at the end of this block
809
 */
Matthias Braun's avatar
Matthias Braun committed
810
static vfp_liveness vfp_liveness_end_of_block(x87_simulator *sim, const ir_node *block)
811
{
Sebastian Hack's avatar
Sebastian Hack committed
812
	int i;
Matthias Braun's avatar
Matthias Braun committed
813
	vfp_liveness live = 0;
814
	const arch_register_class_t *cls = &ia32_reg_classes[CLASS_ia32_vfp];
Matthias Braun's avatar
Matthias Braun committed
815
	const be_lv_t *lv = sim->lv;
816

Matthias Braun's avatar
Matthias Braun committed
817
818
819
	be_lv_foreach(lv, block, be_lv_state_end, i) {
		const arch_register_t *reg;
		const ir_node *node = be_lv_get_irn(lv, block, i);
820
		if (!arch_irn_consider_in_reg_alloc(cls, node))
Matthias Braun's avatar
Matthias Braun committed
821
822
			continue;

823
		reg = x87_get_irn_register(node);
Matthias Braun's avatar
Matthias Braun committed
824
		live |= 1 << arch_register_get_index(reg);
825
826
827
	}

	return live;
Michael Beck's avatar
BugFix:    
Michael Beck committed
828
}  /* vfp_liveness_end_of_block */
829

830
/** get the register mask from an arch_register */
Michael Beck's avatar
Michael Beck committed
831
#define REGMASK(reg)	(1 << (arch_register_get_index(reg)))
832

833
/**
834
 * Return a bitset of argument registers which are live at the end of a node.
Michael Beck's avatar
BugFix:    
Michael Beck committed
835
836
837
 *
 * @param sim    the simulator handle
 * @param pos    the node
838
 * @param kill   kill mask for the output registers
Michael Beck's avatar
BugFix:    
Michael Beck committed
839
 *
840
841
 * @return The live bitset.
 */
842
static unsigned vfp_live_args_after(x87_simulator *sim, const ir_node *pos, unsigned kill)
843
{
Michael Beck's avatar
BugFix:    
Michael Beck committed
844
	unsigned idx = get_irn_idx(pos);
845

Michael Beck's avatar
BugFix:    
Michael Beck committed
846
	assert(idx < sim->n_idx);
847
848
	return sim->live[idx] & ~kill;
}  /* vfp_live_args_after */
849

Michael Beck's avatar
BugFix:    
Michael Beck committed
850
851
852
/**
 * Calculate the liveness for a whole block and cache it.
 *
Matthias Braun's avatar
Matthias Braun committed
853
854
855
 * @param sim   the simulator handle
 * @param lv    the liveness handle
 * @param block the block
Michael Beck's avatar
BugFix:    
Michael Beck committed
856
 */
Christoph Mallon's avatar
Christoph Mallon committed
857
858
static void update_liveness(x87_simulator *sim, ir_node *block)
{
Matthias Braun's avatar
Matthias Braun committed
859
	vfp_liveness live = vfp_liveness_end_of_block(sim, block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
860
861
862
863
	unsigned idx;
	ir_node *irn;

	/* now iterate through the block backward and cache the results */
Matthias Braun's avatar
Matthias Braun committed
864
	sched_foreach_reverse(block, irn) {
865
866
867
868
		/* stop at the first Phi: this produces the live-in */
		if (is_Phi(irn))
			break;

Michael Beck's avatar
BugFix:    
Michael Beck committed
869
870
		idx = get_irn_idx(irn);
		sim->live[idx] = live;
871

872
		live = vfp_liveness_transfer(irn, live);
873
	}
Matthias Braun's avatar
Matthias Braun committed
874
	idx = get_irn_idx(block);
Michael Beck's avatar
BugFix:    
Michael Beck committed
875
876
	sim->live[idx] = live;
}  /* update_liveness */
877
878
879

/**
 * Returns true if a register is live in a set.
Michael Beck's avatar
Michael Beck committed
880
881
882
 *
 * @param reg_idx  the vfp register index
 * @param live     a live bitset
883
 */
Michael Beck's avatar
BugFix:    
Michael Beck committed
884
#define is_vfp_live(reg_idx, live) ((live) & (1 << (reg_idx)))
885

886
887
#ifdef DEBUG_libfirm
/**
Michael Beck's avatar
Michael Beck committed
888
889
890
 * Dump liveness info.
 *
 * @param live  the live bitset
891
 */
Christoph Mallon's avatar
Christoph Mallon committed
892
893
static void vfp_dump_live(vfp_liveness live)
{
894
895
	int i;

Matthias Braun's avatar
Matthias Braun committed
896
	DB((dbg, LEVEL_2, "Live after: "));
897
898
	for (i = 0; i < 8; ++i) {
		if (live & (1 << i)) {
Matthias Braun's avatar
Matthias Braun committed
899
			DB((dbg, LEVEL_2, "vf%d ", i));
900
901
		}
	}
902
	DB((dbg, LEVEL_2, "\n"));
Michael Beck's avatar
BugFix:    
Michael Beck committed
903
}  /* vfp_dump_live */
904
#endif /* DEBUG_libfirm */
905
906
907

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

908
/**
Michael Beck's avatar
Michael Beck committed
909
910
911
912
913
 * Simulate a virtual binop.
 *
 * @param state  the x87 state
 * @param n      the node that should be simulated (and patched)
 * @param tmpl   the template containing the 4 possible x87 opcodes
Michael Beck's avatar
Michael Beck committed
914
915
 *
 * @return NO_NODE_ADDED
916
 */
Christoph Mallon's avatar
Christoph Mallon committed
917
918
static int sim_binop(x87_state *state, ir_node *n, const exchange_tmpl *tmpl)
{
919
	int op2_idx = 0, op1_idx;
Matthias Braun's avatar
Matthias Braun committed
920
	int out_idx, do_pop = 0;
921
	ia32_x87_attr_t *attr;
922
	int permuted;
923
	ir_node *patched_insn;
924
	ir_op *dst;
925
	x87_simulator         *sim     = state->sim;
926
927
	ir_node               *op1     = get_irn_n(n, n_ia32_binary_left);
	ir_node               *op2     = get_irn_n(n, n_ia32_binary_right);
928
929
	const arch_register_t *op1_reg = x87_get_irn_register(op1);
	const arch_register_t *op2_reg = x87_get_irn_register(op2);
930
	const arch_register_t *out     = x87_irn_get_register(n, pn_ia32_res);
931
932
933
934
935
	int reg_index_1                = arch_register_get_index(op1_reg);
	int reg_index_2                = arch_register_get_index(op2_reg);
	vfp_liveness           live    = vfp_live_args_after(sim, n, REGMASK(out));
	int                    op1_live_after;
	int                    op2_live_after;
936

937
	DB((dbg, LEVEL_1, ">>> %+F %s, %s -> %s\n", n,
938
		arch_register_get_name(op1_reg), arch_register_get_name(op2_reg),
939
		arch_register_get_name(out)));
940
	DEBUG_ONLY(vfp_dump_live(live));
Matthias Braun's avatar
Matthias Braun committed
941
942
	DB((dbg, LEVEL_1, "Stack before: "));
	DEBUG_ONLY(x87_dump_stack(state));
943

Christoph Mallon's avatar
Christoph Mallon committed
944
	if (reg_index_1 == REG_VFP_UKNWN) {
945
946
947
948
949
950
951
		op1_idx        = 0;
		op1_live_after = 1;
	} else {
		op1_idx = x87_on_stack(state, reg_index_1);
		assert(op1_idx >= 0);
		op1_live_after = is_vfp_live(arch_register_get_index(op1_reg), live);
	}
952

953
954
955
	attr     = get_ia32_x87_attr(n);
	permuted = attr->attr.data.ins_permuted;

Matthias Braun's avatar
Matthias Braun committed
956
	if (reg_index_2 != REG_VFP_NOREG) {
Christoph Mallon's avatar