ia32_finish.c 12.1 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
 */

Christian Würdig's avatar
Christian Würdig committed
6
/**
7
8
9
 * @file
 * @brief   This file implements functions to finalize the irg for emit.
 * @author  Christian Wuerdig
Christian Würdig's avatar
Christian Würdig committed
10
 */
11
#include "debug.h"
12
#include "irnode_t.h"
Christian Würdig's avatar
Christian Würdig committed
13
14
15
#include "ircons.h"
#include "irgmod.h"
#include "irgwalk.h"
16
#include "iredges_t.h"
Christian Würdig's avatar
Christian Würdig committed
17
#include "pdeq.h"
Matthias Braun's avatar
Matthias Braun committed
18
#include "panic.h"
Christian Würdig's avatar
Christian Würdig committed
19

20
21
22
#include "bearch.h"
#include "besched.h"
#include "benode.h"
Christian Würdig's avatar
Christian Würdig committed
23
24
25
26
27
28

#include "bearch_ia32_t.h"
#include "ia32_finish.h"
#include "ia32_new_nodes.h"
#include "ia32_transform.h"
#include "ia32_optimize.h"
29
#include "gen_ia32_regalloc_if.h"
Christian Würdig's avatar
Christian Würdig committed
30

31
32
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

33
34
35
36
37
38
39
40
41
static bool reads_carry(x86_condition_code_t code)
{
	x86_condition_code_t c2 = code & ~x86_cc_negated;
	return c2 == x86_cc_below || c2 == x86_cc_below_equal
	    || c2 == x86_cc_float_below || c2 == x86_cc_float_below_equal
	    || c2 == x86_cc_float_unordered_below_equal
	    || c2 == x86_cc_float_unordered_below;
}

Christian Würdig's avatar
Christian Würdig committed
42
/**
43
 * Transforms a Sub or xSub into Neg--Add iff OUT_REG != SRC1_REG && OUT_REG == SRC2_REG.
Christian Würdig's avatar
Christian Würdig committed
44
45
 * THIS FUNCTIONS MUST BE CALLED AFTER REGISTER ALLOCATION.
 */
46
static void ia32_transform_sub_to_neg_add(ir_node *irn)
Christoph Mallon's avatar
Christoph Mallon committed
47
{
48
	/* fix_am will solve this for AddressMode variants */
49
	if (get_ia32_op_type(irn) != ia32_Normal)
Christian Würdig's avatar
Christian Würdig committed
50
51
		return;

Matthias Braun's avatar
Matthias Braun committed
52
53
54
55
56
57
58
59
60
	ir_graph              *irg      = get_irn_irg(irn);
	ir_node               *noreg    = ia32_new_NoReg_gp(irg);
	ir_node               *noreg_fp = ia32_new_NoReg_xmm(irg);
	ir_node               *nomem    = get_irg_no_mem(irg);
	ir_node               *in1      = get_irn_n(irn, n_ia32_binary_left);
	ir_node               *in2      = get_irn_n(irn, n_ia32_binary_right);
	const arch_register_t *in1_reg  = arch_get_irn_register(in1);
	const arch_register_t *in2_reg  = arch_get_irn_register(in2);
	const arch_register_t *out_reg  = arch_get_irn_register_out(irn, 0);
Christian Würdig's avatar
Christian Würdig committed
61

62
63
64
	if (out_reg == in1_reg)
		return;

Christian Würdig's avatar
Christian Würdig committed
65
	/* in case of sub and OUT == SRC2 we can transform the sequence into neg src2 -- add */
66
	if (out_reg != in2_reg)
67
68
		return;

Matthias Braun's avatar
Matthias Braun committed
69
70
	ir_node  *block = get_nodes_block(irn);
	dbg_info *dbgi  = get_irn_dbg_info(irn);
71

72
	/* generate the neg src2 */
Matthias Braun's avatar
Matthias Braun committed
73
	ir_node *res;
74
	if (is_ia32_xSub(irn)) {
75
		ir_mode *op_mode = get_ia32_ls_mode(irn);
76
77
		assert(get_irn_mode(irn) != mode_T);

78
		res = new_bd_ia32_xXor(dbgi, block, noreg, noreg, nomem, in2, noreg_fp);
Matthias Braun's avatar
Matthias Braun committed
79
		int        size   = get_mode_size_bits(op_mode);
80
		ir_entity *entity = ia32_gen_fp_known_const(size == 32 ? ia32_SSIGN : ia32_DSIGN);
81
		set_ia32_am_ent(res, entity);
82
		set_ia32_op_type(res, ia32_AddrModeS);
83
		set_ia32_ls_mode(res, op_mode);
Christian Würdig's avatar
Christian Würdig committed
84

85
		arch_set_irn_register(res, in2_reg);
Christian Würdig's avatar
Christian Würdig committed
86

87
88
89
90
		/* add to schedule */
		sched_add_before(irn, res);

		/* generate the add */
91
		res = new_bd_ia32_xAdd(dbgi, block, noreg, noreg, nomem, res, in1);
92
		set_ia32_ls_mode(res, get_ia32_ls_mode(irn));
93
	} else {
94
95
96
		ir_node *flags_proj  = NULL;
		bool     needs_carry = false;
		/** See if someone is interested in a correctly set carry flag */
97
		if (get_irn_mode(irn) == mode_T) {
Christoph Mallon's avatar
Christoph Mallon committed
98
99
100
101
102
103
104
105
			flags_proj = get_Proj_for_pn(irn, pn_ia32_flags);
			if (flags_proj) {
				foreach_out_edge(flags_proj, edge) {
					ir_node *user = get_edge_src_irn(edge);
					x86_condition_code_t cc = get_ia32_condcode(user);
					if (reads_carry(cc)) {
						needs_carry = true;
						break;
106
					}
107
108
109
				}
			}
		}
Christian Würdig's avatar
Christian Würdig committed
110

Matthias Braun's avatar
Matthias Braun committed
111
		ir_node *carry;
112
113
114
115
116
		if (is_ia32_Sbb(irn)) {
			/* Feed borrow (in CF) as carry (via CMC) into NOT+ADC. */
			carry = get_irn_n(irn, n_ia32_Sbb_eflags);
			carry = new_bd_ia32_Cmc(dbgi, block, carry);
			goto carry;
117
		} else if (flags_proj != NULL && needs_carry) {
Michael Beck's avatar
Michael Beck committed
118
119
120
121
122
123
124
			/*
			 * ARG, the above technique does NOT set the flags right.
			 * So, we must produce the following code:
			 * t1 = ~b
			 * t2 = a + ~b + Carry
			 * Complement Carry
			 *
125
			 * a + -b = a + (~b + 1)  would set the carry flag wrong IFF both a and b are zero.
Michael Beck's avatar
Michael Beck committed
126
			 */
127
128
			carry = new_bd_ia32_Stc(dbgi, block);

Matthias Braun's avatar
Matthias Braun committed
129
130
carry:;
			ir_node *nnot = new_bd_ia32_Not(dbgi, block, in2);
131
132
			arch_set_irn_register(nnot, in2_reg);
			sched_add_before(irn, nnot);
133

134
135
			arch_set_irn_register(carry, &ia32_registers[REG_EFLAGS]);
			sched_add_before(irn, carry);
136

Matthias Braun's avatar
Matthias Braun committed
137
			ir_node *adc = new_bd_ia32_Adc(dbgi, block, noreg, noreg, nomem, nnot, in1, carry);
138
			arch_set_irn_register(adc, out_reg);
139
			set_ia32_commutative(adc);
140

141
			if (flags_proj != NULL) {
yb9976's avatar
yb9976 committed
142
				set_irn_mode(adc, mode_T);
143
144
				arch_register_t const *const reg_flags = &ia32_registers[REG_EFLAGS];
				ir_node               *const adc_flags = be_new_Proj_reg(adc, pn_ia32_Adc_flags, reg_flags);
145

Matthias Braun's avatar
Matthias Braun committed
146
				ir_node *cmc = new_bd_ia32_Cmc(dbgi, block, adc_flags);
147
				arch_set_irn_register(cmc, reg_flags);
148
				sched_add_after(irn, cmc);
149
150
				exchange(flags_proj, cmc);
			}
151
152

			res = adc;
153
154
155
156
157
158
159
160
161
		} else {
			res = new_bd_ia32_Neg(dbgi, block, in2);
			arch_set_irn_register(res, in2_reg);

			/* add to schedule */
			sched_add_before(irn, res);

			/* generate the add */
			res = new_bd_ia32_Add(dbgi, block, noreg, noreg, nomem, res, in1);
162
163
164
165
166
167
			if (flags_proj != NULL) {
				arch_set_irn_register_out(res, pn_ia32_res, out_reg);
				arch_set_irn_register_out(res, pn_ia32_flags, &ia32_registers[REG_EFLAGS]);
			} else {
				arch_set_irn_register(res, out_reg);
			}
168
			set_ia32_commutative(res);
169
170
171
		}
	}

172
	set_irn_mode(res, get_irn_mode(irn));
173
	SET_IA32_ORIG_NODE(res, irn);
174

175
176
177
	/* exchange the add and the sub */
	sched_replace(irn, res);
	exchange(irn, res);
Christian Würdig's avatar
Christian Würdig committed
178
179
}

180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
static void ia32_transform_ShlD_to_ShrD_imm(ir_node *const irn)
{
	ir_node               *const in0     = get_irn_n(irn, n_ia32_ShlD_val_high);
	arch_register_t const *const in0_reg = arch_get_irn_register(in0);
	arch_register_t const *const out_reg = arch_get_irn_register_out(irn, pn_ia32_ShlD_res);
	if (out_reg == in0_reg)
		return; /* should_be_same fulfilled. */

	ir_node               *const in1     = get_irn_n(irn, n_ia32_ShlD_val_low);
	arch_register_t const *const in1_reg = arch_get_irn_register(in1);
	if (out_reg != in1_reg)
		return; /* res uses third register. Must be resolved with a Copy. */

	/* a = ShlD(b, a, c) -> a = ShrD(a, b, 32 - c) */
	ir_node                     *const lcount = get_irn_n(irn, n_ia32_ShlD_count);
	ia32_immediate_attr_t const *const attr   = get_ia32_immediate_attr_const(lcount);
	ir_graph                    *const irg    = get_irn_irg(irn);
197
	ir_node                     *const count  = ia32_create_Immediate(irg, 32 - attr->imm.offset);
198
199
200
201
202
203
204
205
	dbg_info                    *const dbgi   = get_irn_dbg_info(irn);
	ir_node                     *const block  = get_nodes_block(irn);
	ir_node                     *const res    = new_bd_ia32_ShrD_imm(dbgi, block, in1, in0, count);
	arch_set_irn_register_out(res, pn_ia32_ShrD_res, out_reg);
	sched_replace(irn, res);
	exchange(irn, res);
}

206
static inline int need_constraint_copy(ir_node *irn)
207
208
209
210
{
	/* TODO this should be determined from the node specification */
	switch (get_ia32_irn_opcode(irn)) {
		case iro_ia32_Lea:
Matthias Braun's avatar
Matthias Braun committed
211
		case iro_ia32_Minus64:
Matthias Braun's avatar
Matthias Braun committed
212
213
			return 0;

214
215
216
		default:
			return 1;
	}
Christian Würdig's avatar
Christian Würdig committed
217
218
}

Michael Beck's avatar
Michael Beck committed
219
220
221
222
/**
 * Returns the index of the "same" register.
 * On the x86, we should have only one.
 */
223
224
static int get_first_same(const arch_register_req_t* req)
{
225
	const unsigned other = req->should_be_same;
Matthias Braun's avatar
Matthias Braun committed
226
227
228
	for (int i = 0; i < 32; ++i) {
		if (other & (1U << i))
			return i;
229
	}
230
	panic("same position not found");
231
232
}

Christian Würdig's avatar
Christian Würdig committed
233
234
235
236
237
/**
 * Insert copies for all ia32 nodes where the should_be_same requirement
 * is not fulfilled.
 * Transform Sub into Neg -- Add if IN2 == OUT
 */
238
static void assure_should_be_same_requirements(ir_node *node)
239
240
{
	/* check all OUT requirements, if there is a should_be_same */
241
	be_foreach_out(node, i) {
242
		arch_register_req_t const *const req = arch_get_irn_register_req_out(node, i);
243
		if (req->should_be_same == 0)
244
245
246
			continue;

		/* get in and out register */
247
248
249
250
		int                    const same_pos = get_first_same(req);
		ir_node               *const in_node  = get_irn_n(node, same_pos);
		arch_register_t const *const in_reg   = arch_get_irn_register(in_node);
		arch_register_t const *const out_reg  = arch_get_irn_register_out(node, i);
251
252
253
254
255
256

		/* requirement already fulfilled? */
		if (in_reg == out_reg)
			continue;

		/* check if any other input operands uses the out register */
257
		int uses_out_reg_pos = -1;
258
		foreach_irn_in(node, i2, in) {
259
260
261
262
			arch_register_t const *const other_in_reg = arch_get_irn_register(in);
			if (other_in_reg == out_reg) {
				if (uses_out_reg_pos >= 0)
					panic("unresolved should_be_same constraint");
263
				uses_out_reg_pos = i2;
264
			}
Christian Würdig's avatar
Christian Würdig committed
265
266
		}

267
268
269
270
		if (uses_out_reg_pos < 0) {
			/* no-one else is using the out reg, we can simply copy it
			 * (the register can't be live since the operation will override it
			 *  anyway) */
271
			ir_node *const copy = be_new_Copy_before_reg(in_node, node, out_reg);
272
273
274
			/* set copy as in */
			set_irn_n(node, same_pos, copy);

275
276
277
			DBG((dbg, LEVEL_1, "created copy %+F for should be same argument at input %d of %+F\n", copy, same_pos, node));
		} else if (uses_out_reg_pos == n_ia32_binary_right && is_ia32_commutative(node)) {
			/* for commutative nodes we can simply swap the left/right */
278
			ia32_swap_left_right(node);
279
280
281
			DBG((dbg, LEVEL_1, "swapped left/right input of %+F to resolve should be same constraint\n", node));
		} else {
			panic("unresolved should_be_same constraint");
282
283
		}
	}
Christian Würdig's avatar
Christian Würdig committed
284
285
}

286
287
288
/**
 * Following Problem:
 * We have a source address mode node with base or index register equal to
289
290
291
 * result register and unfulfilled should_be_same requirement. The constraint
 * handler will insert a copy from the remaining input operand to the result
 * register -> base or index is broken then.
292
293
 * Solution: Turn back this address mode into explicit Load + Operation.
 */
294
static void fix_am_source(ir_node *irn)
295
{
296
	/* check only ia32 nodes with source address mode */
297
	if (!is_ia32_irn(irn) || get_ia32_op_type(irn) != ia32_AddrModeS)
298
		return;
299
	/* only need to fix binary operations */
300
	if (get_ia32_am_support(irn) != ia32_am_binary)
301
		return;
302

303
	be_foreach_out(irn, i) {
304
		const arch_register_req_t *req = arch_get_irn_register_req_out(irn, i);
305
		if (req->should_be_same == 0)
306
			continue;
307

308
		/* get in and out register */
Matthias Braun's avatar
Matthias Braun committed
309
310
311
312
		const arch_register_t *out_reg   = arch_get_irn_register_out(irn, i);
		int                    same_pos  = get_first_same(req);
		ir_node               *same_node = get_irn_n(irn, same_pos);
		const arch_register_t *same_reg  = arch_get_irn_register(same_node);
313

314
315
316
		/* should_be same constraint is fullfilled, nothing to do */
		if (out_reg == same_reg)
			continue;
317

318
319
		/* we only need to do something if the out reg is the same as base
			 or index register */
320
321
		if (out_reg != arch_get_irn_register(get_irn_n(irn, n_ia32_base)) &&
				out_reg != arch_get_irn_register(get_irn_n(irn, n_ia32_index)))
322
			continue;
323

Matthias Braun's avatar
Matthias Braun committed
324
		ir_node *load_res = ia32_turn_back_am(irn);
325
		arch_set_irn_register(load_res, out_reg);
326

327
328
		DBG((dbg, LEVEL_3,
			"irg %+F: build back AM source for node %+F, inserted load %+F\n",
329
			get_irn_irg(irn), irn, get_Proj_pred(load_res)));
330
		break;
331
332
333
	}
}

334
335
336
/**
 * Block walker: finishes a block
 */
Christoph Mallon's avatar
Christoph Mallon committed
337
338
static void ia32_finish_irg_walker(ir_node *block, void *env)
{
339
	(void) env;
Christian Würdig's avatar
Christian Würdig committed
340

341
	/* first: turn back AM source if necessary */
342
	sched_foreach_safe(block, irn) {
343
		fix_am_source(irn);
344
345
	}

346
	sched_foreach_safe(block, irn) {
347
		/* check if there is a sub which need to be transformed */
348
		if (is_ia32_Sub(irn) || is_ia32_Sbb(irn) || is_ia32_xSub(irn)) {
349
			ia32_transform_sub_to_neg_add(irn);
350
351
		} else if (is_ia32_ShlD(irn)) {
			ia32_transform_ShlD_to_ShrD_imm(irn);
352
		}
353
354
	}

355
	/* second: insert copies and finish irg */
356
	sched_foreach_safe(block, irn) {
Michael Beck's avatar
Michael Beck committed
357
358
359
360
		if (is_ia32_irn(irn)) {
			/* some nodes are just a bit less efficient, but need no fixing if the
			 * should be same requirement is not fulfilled */
			if (need_constraint_copy(irn))
361
				assure_should_be_same_requirements(irn);
Michael Beck's avatar
Michael Beck committed
362
		}
Christian Würdig's avatar
Christian Würdig committed
363
364
365
	}
}

366
367
368
/**
 * Block walker: pushes all blocks on a wait queue
 */
Christoph Mallon's avatar
Christoph Mallon committed
369
370
static void ia32_push_on_queue_walker(ir_node *block, void *env)
{
371
372
	pdeq *wq = (pdeq*)env;
	pdeq_putr(wq, block);
Christian Würdig's avatar
Christian Würdig committed
373
374
375
376
377
378
}


/**
 * Add Copy nodes for not fulfilled should_be_equal constraints
 */
379
void ia32_finish_irg(ir_graph *irg)
Christoph Mallon's avatar
Christoph Mallon committed
380
{
381
	pdeq *wq = new_pdeq();
Christian Würdig's avatar
Christian Würdig committed
382

383
	/* Push the blocks on the pdeq because ia32_finish_irg_walker starts more
Matthias Braun's avatar
Matthias Braun committed
384
	 * walks ... */
Christian Würdig's avatar
Christian Würdig committed
385
386
	irg_block_walk_graph(irg, NULL, ia32_push_on_queue_walker, wq);

387
388
	while (!pdeq_empty(wq)) {
		ir_node *block = (ir_node*)pdeq_getl(wq);
389
		ia32_finish_irg_walker(block, NULL);
Christian Würdig's avatar
Christian Würdig committed
390
	}
391
	del_pdeq(wq);
Christian Würdig's avatar
Christian Würdig committed
392
}
393
394
395
396
397

void ia32_init_finish(void)
{
	FIRM_DBG_REGISTER(dbg, "firm.be.ia32.finish");
}