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

6
/**
Christian Würdig's avatar
Christian Würdig committed
7
8
9
10
 * @file
 * @brief       This file implements the mapping of 64Bit intrinsic
 *              functions to code or library calls.
 * @author      Michael Beck
11
 */
12
#include "iredges.h"
13
#include "irgmod.h"
14
15
#include "irop.h"
#include "irnode_t.h"
16
#include "ircons_t.h"
17
#include "irprog_t.h"
18
#include "iroptimize.h"
19
#include "lower_dw.h"
20
#include "array.h"
Matthias Braun's avatar
Matthias Braun committed
21
#include "panic.h"
22
#include "util.h"
23
24
#include "constbits.h"
#include "tv.h"
25

26
#include "ia32_new_nodes.h"
27
28
#include "bearch_ia32_t.h"
#include "gen_ia32_regalloc_if.h"
Matthias Braun's avatar
Matthias Braun committed
29
#include "begnuas.h"
30

31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
static ir_tarval *bitinfo_max(bitinfo *info)
{
	ir_tarval *z    = info->z;
	ir_tarval *o    = info->o;
	ir_mode   *mode = get_tarval_mode(z);
	ir_tarval *min  = get_mode_min(mode);

	assert(get_mode_arithmetic(mode) == irma_twos_complement);
	return tarval_and(z, tarval_ornot(o, min));
}

static ir_tarval *bitinfo_min(bitinfo *info)
{
	ir_tarval *z    = info->z;
	ir_tarval *o    = info->o;
	ir_mode   *mode = get_tarval_mode(z);
	ir_tarval *min  = get_mode_min(mode);

	assert(get_mode_arithmetic(mode) == irma_twos_complement);
	return tarval_or(o, tarval_and(z, min));
}

static bool lower_add_can_carry(ir_node *left, ir_node *right, ir_mode *mode)
{
	bitinfo *bi_left = get_bitinfo(left);
	if (!bi_left) {
		return true;
	}
	bitinfo *bi_right = get_bitinfo(right);
	// If we have bitinfo for one node, we should also have it for
	// the other
	assert(bi_right);

	ir_tarval *lmin   = tarval_convert_to(bitinfo_min(bi_left),  mode);
	ir_tarval *rmin   = tarval_convert_to(bitinfo_min(bi_right), mode);
	ir_tarval *lmax   = tarval_convert_to(bitinfo_max(bi_left),  mode);
	ir_tarval *rmax   = tarval_convert_to(bitinfo_max(bi_right), mode);
	bool       result = false;

	tarval_int_overflow_mode_t ofm = tarval_get_integer_overflow_mode();
	tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);

	if (tarval_add(lmin, rmin) == tarval_bad ||
	    tarval_add(lmax, rmax) == tarval_bad) {
		result = true;
	}

	tarval_set_integer_overflow_mode(ofm);

	return result;
}

static bool lower_sub_can_borrow(ir_node *left, ir_node *right, ir_mode *mode)
{
	bitinfo *bi_left = get_bitinfo(left);
	if (!bi_left) {
		return true;
	}
	bitinfo *bi_right = get_bitinfo(right);
	// If we have bitinfo for one node, we should also have it for
	// the other
	assert(bi_right);

	ir_tarval *lmin   = tarval_convert_to(bitinfo_min(bi_left),  mode);
	ir_tarval *rmin   = tarval_convert_to(bitinfo_min(bi_right), mode);
	ir_tarval *lmax   = tarval_convert_to(bitinfo_max(bi_left),  mode);
	ir_tarval *rmax   = tarval_convert_to(bitinfo_max(bi_right), mode);
	bool       result = false;

	tarval_int_overflow_mode_t ofm = tarval_get_integer_overflow_mode();
	tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);

	if (tarval_sub(lmin, rmax, NULL) == tarval_bad ||
	    tarval_sub(lmax, rmin, NULL) == tarval_bad) {
		result = true;
	}

	tarval_set_integer_overflow_mode(ofm);

	return result;
}

113
/**
Matthias Braun's avatar
Matthias Braun committed
114
115
 * lower 64bit addition: an 32bit add for the lower parts, an add with
 * carry for the higher parts.
116
 */
Matthias Braun's avatar
Matthias Braun committed
117
static void ia32_lower_add64(ir_node *node, ir_mode *mode)
118
{
Matthias Braun's avatar
Matthias Braun committed
119
120
121
122
123
124
125
126
	dbg_info *dbg        = get_irn_dbg_info(node);
	ir_node  *block      = get_nodes_block(node);
	ir_node  *left       = get_Add_left(node);
	ir_node  *right      = get_Add_right(node);
	ir_node  *left_low   = get_lowered_low(left);
	ir_node  *left_high  = get_lowered_high(left);
	ir_node  *right_low  = get_lowered_low(right);
	ir_node  *right_high = get_lowered_high(right);
127
128
129
130
	ir_mode  *low_mode   = get_irn_mode(left_low);

	assert(get_irn_mode(left_low)  == get_irn_mode(right_low));
	assert(get_irn_mode(left_high) == get_irn_mode(right_high));
131

132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
	if (!lower_add_can_carry(left, right, low_mode)) {
		ir_node *add_low  = new_rd_Add(dbg, block, left_low,  right_low, low_mode);
		ir_node *add_high = new_rd_Add(dbg, block, left_high, right_high, get_irn_mode(left_high));
		ir_set_dw_lowered(node, add_low, add_high);
	} else {
		/* l_res = a_l + b_l */
		ir_node  *add_low    = new_bd_ia32_l_Add(dbg, block, left_low, right_low);
		ir_mode  *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
		ir_node  *res_low    = new_r_Proj(add_low, ia32_mode_gp, pn_ia32_l_Add_res);
		ir_node  *flags      = new_r_Proj(add_low, mode_flags, pn_ia32_l_Add_flags);

		/* h_res = a_h + b_h + carry */
		ir_node  *add_high
			= new_bd_ia32_l_Adc(dbg, block, left_high, right_high, flags, mode);
		ir_set_dw_lowered(node, res_low, add_high);
	}
148
149
150
}

/**
Matthias Braun's avatar
Matthias Braun committed
151
152
 * lower 64bit subtraction: a 32bit sub for the lower parts, a sub borrow
 * for the higher parts.
153
 */
Matthias Braun's avatar
Matthias Braun committed
154
static void ia32_lower_sub64(ir_node *node, ir_mode *mode)
155
{
Matthias Braun's avatar
Matthias Braun committed
156
157
158
159
160
161
162
163
	dbg_info *dbg        = get_irn_dbg_info(node);
	ir_node  *block      = get_nodes_block(node);
	ir_node  *left       = get_Sub_left(node);
	ir_node  *right      = get_Sub_right(node);
	ir_node  *left_low   = get_lowered_low(left);
	ir_node  *left_high  = get_lowered_high(left);
	ir_node  *right_low  = get_lowered_low(right);
	ir_node  *right_high = get_lowered_high(right);
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
	ir_mode  *low_mode   = get_irn_mode(left_low);

	assert(get_irn_mode(left_low)  == get_irn_mode(right_low));
	assert(get_irn_mode(left_high) == get_irn_mode(right_high));

	if (!lower_sub_can_borrow(left, right, low_mode)) {
		ir_node *sub_low  = new_rd_Sub(dbg, block, left_low,  right_low, low_mode);
		ir_node *sub_high = new_rd_Sub(dbg, block, left_high, right_high, get_irn_mode(left_high));
		ir_set_dw_lowered(node, sub_low, sub_high);
	} else {
		/* l_res = a_l - b_l */
		ir_node  *sub_low    = new_bd_ia32_l_Sub(dbg, block, left_low, right_low);
		ir_mode  *mode_flags = ia32_reg_classes[CLASS_ia32_flags].mode;
		ir_node  *res_low    = new_r_Proj(sub_low, ia32_mode_gp, pn_ia32_l_Sub_res);
		ir_node  *flags      = new_r_Proj(sub_low, mode_flags, pn_ia32_l_Sub_flags);
179

180
181
182
183
184
		/* h_res = a_h - b_h - carry */
		ir_node  *sub_high
			= new_bd_ia32_l_Sbb(dbg, block, left_high, right_high, flags, mode);
		ir_set_dw_lowered(node, res_low, sub_high);
	}
185
186
}

187
/**
Matthias Braun's avatar
Matthias Braun committed
188
 * Checks whether node high is a sign extension of low.
189
 */
Matthias Braun's avatar
Matthias Braun committed
190
static bool is_sign_extend(ir_node *low, ir_node *high)
191
192
{
	if (is_Shrs(high)) {
Matthias Braun's avatar
Matthias Braun committed
193
194
		ir_node *high_r = get_Shrs_right(high);
		if (!is_Const(high_r)) return false;
195

Matthias Braun's avatar
Matthias Braun committed
196
197
198
		ir_tarval *shift_count = get_Const_tarval(high_r);
		if (!tarval_is_long(shift_count))       return false;
		if (get_tarval_long(shift_count) != 31) return false;
199

Matthias Braun's avatar
Matthias Braun committed
200
		ir_node *high_l = get_Shrs_left(high);
201

Matthias Braun's avatar
Matthias Braun committed
202
203
		if (is_Conv(low)    && get_Conv_op(low)    == high_l) return true;
		if (is_Conv(high_l) && get_Conv_op(high_l) == low)    return true;
204
	} else if (is_Const(low) && is_Const(high)) {
Matthias Braun's avatar
Matthias Braun committed
205
206
		ir_tarval *tl = get_Const_tarval(low);
		ir_tarval *th = get_Const_tarval(high);
207
208
209
210
211
212
213
214
215

		if (tarval_is_long(th) && tarval_is_long(tl)) {
			long l = get_tarval_long(tl);
			long h = get_tarval_long(th);

			return (h == 0  && l >= 0) || (h == -1 && l <  0);
		}
	}

Matthias Braun's avatar
Matthias Braun committed
216
	return false;
217
218
}

219
/**
Matthias Braun's avatar
Matthias Braun committed
220
 * lower 64bit Mul operation.
221
 */
Matthias Braun's avatar
Matthias Braun committed
222
static void ia32_lower_mul64(ir_node *node, ir_mode *mode)
223
{
Matthias Braun's avatar
Matthias Braun committed
224
225
226
227
228
229
230
231
	dbg_info *dbg        = get_irn_dbg_info(node);
	ir_node  *block      = get_nodes_block(node);
	ir_node  *left       = get_Mul_left(node);
	ir_node  *right      = get_Mul_right(node);
	ir_node  *left_low   = get_lowered_low(left);
	ir_node  *left_high  = get_lowered_high(left);
	ir_node  *right_low  = get_lowered_low(right);
	ir_node  *right_high = get_lowered_high(right);
232
233

	/*
Matthias Braun's avatar
Matthias Braun committed
234
		EDX:EAX = left_low * right_low
235
236
		l_res   = EAX

Matthias Braun's avatar
Matthias Braun committed
237
		t1 = right_low * left_high
238
		t2 = t1 + EDX
Matthias Braun's avatar
Matthias Braun committed
239
		t3 = left_low * right_high
240
241
		h_res = t2 + t3
	*/
Michael Beck's avatar
Michael Beck committed
242

243
	/* handle the often used case of 32x32=64 mul */
Matthias Braun's avatar
Matthias Braun committed
244
245
246
247
248
249
	ir_node *h_res;
	ir_node *l_res;
	if (is_sign_extend(left_low, left_high)
	    && is_sign_extend(right_low, right_high)) {
		ir_node *mul = new_bd_ia32_l_IMul(dbg, block, left_low, right_low);
		h_res = new_rd_Proj(dbg, mul, mode, pn_ia32_l_IMul_res_high);
250
		l_res = new_rd_Proj(dbg, mul, ia32_mode_gp, pn_ia32_l_IMul_res_low);
251
252
	} else {
		/* note that zero extension is handled hare efficiently */
Matthias Braun's avatar
Matthias Braun committed
253
254
		ir_node *mul  = new_bd_ia32_l_Mul(dbg, block, left_low, right_low);
		ir_node *pEDX = new_rd_Proj(dbg, mul, mode, pn_ia32_l_Mul_res_high);
255
		l_res = new_rd_Proj(dbg, mul, ia32_mode_gp, pn_ia32_l_Mul_res_low);
Matthias Braun's avatar
Matthias Braun committed
256
257
258
259
260
261
262

		ir_node *right_lowc = new_rd_Conv(dbg, block, right_low, mode);
		ir_node *mul1 = new_rd_Mul(dbg, block, left_high, right_lowc, mode);
		ir_node *add        = new_rd_Add(dbg, block, mul1, pEDX, mode);
		ir_node *left_lowc  = new_rd_Conv(dbg, block, left_low, mode);
		ir_node *mul2 = new_rd_Mul(dbg, block, left_lowc, right_high, mode);
		h_res = new_rd_Add(dbg, block, add, mul2, mode);
263
	}
Matthias Braun's avatar
Matthias Braun committed
264
	ir_set_dw_lowered(node, l_res, h_res);
265
266
}

267
/**
Matthias Braun's avatar
Matthias Braun committed
268
 * lower 64bit minus operation
269
 */
Matthias Braun's avatar
Matthias Braun committed
270
static void ia32_lower_minus64(ir_node *node, ir_mode *mode)
271
{
Matthias Braun's avatar
Matthias Braun committed
272
273
274
275
276
277
	dbg_info *dbg     = get_irn_dbg_info(node);
	ir_node  *block   = get_nodes_block(node);
	ir_node  *op      = get_Minus_op(node);
	ir_node  *op_low  = get_lowered_low(op);
	ir_node  *op_high = get_lowered_high(op);
	ir_node  *minus   = new_bd_ia32_l_Minus64(dbg, block, op_low, op_high);
278
	ir_node  *l_res   = new_r_Proj(minus, ia32_mode_gp, pn_ia32_Minus64_res_low);
Matthias Braun's avatar
Matthias Braun committed
279
280
	ir_node  *h_res   = new_r_Proj(minus, mode, pn_ia32_Minus64_res_high);
	ir_set_dw_lowered(node, l_res, h_res);
281
282
283
}

/**
Matthias Braun's avatar
Matthias Braun committed
284
 * lower 64bit conversions
285
 */
Matthias Braun's avatar
Matthias Braun committed
286
static void ia32_lower_conv64(ir_node *node, ir_mode *mode)
287
{
Matthias Braun's avatar
Matthias Braun committed
288
289
290
291
	dbg_info  *dbg       = get_irn_dbg_info(node);
	ir_node   *op        = get_Conv_op(node);
	ir_mode   *mode_from = get_irn_mode(op);
	ir_mode   *mode_to   = get_irn_mode(node);
292

Matthias Braun's avatar
Matthias Braun committed
293
294
	if (mode_is_float(mode_from) && get_mode_size_bits(mode_to) == 64
	    && get_mode_arithmetic(mode_to) == irma_twos_complement) {
295
		/* We have a Conv float -> long long here */
Matthias Braun's avatar
Matthias Braun committed
296
297
298
299
		ir_node *float_to_ll;
		ir_node *l_res;
		ir_node *h_res;
		if (mode_is_signed(mode)) {
300
			/* convert from float to signed 64bit */
Matthias Braun's avatar
Matthias Braun committed
301
302
			ir_node *block = get_nodes_block(node);
			float_to_ll = new_bd_ia32_l_FloattoLL(dbg, block, op);
303
			l_res = new_r_Proj(float_to_ll, ia32_mode_gp,
304
			                   pn_ia32_l_FloattoLL_res_low);
Matthias Braun's avatar
Matthias Braun committed
305
			h_res = new_r_Proj(float_to_ll, mode,
306
307
							   pn_ia32_l_FloattoLL_res_high);
		} else {
Christoph Mallon's avatar
Christoph Mallon committed
308
			/* Convert from float to unsigned 64bit. */
Matthias Braun's avatar
Matthias Braun committed
309
310
311
312
313
314
315
			ir_graph  *irg = get_irn_irg(node);
			ir_tarval *flt_tv
				= new_tarval_from_str("9223372036854775808", 19, ia32_mode_E);
			ir_node   *flt_corr  = new_r_Const(irg, flt_tv);

			ir_node *lower_blk = part_block_dw(node);
			ir_node *upper_blk = get_nodes_block(node);
316
			set_dw_control_flow_changed();
Matthias Braun's avatar
Matthias Braun committed
317
318
319
320
321
322
323
324
325
326

			ir_node *opc  = new_rd_Conv(dbg, upper_blk, op, ia32_mode_E);
			ir_node *cmp  = new_rd_Cmp(dbg, upper_blk, opc, flt_corr,
			                           ir_relation_less);
			ir_node *cond = new_rd_Cond(dbg, upper_blk, cmp);
			ir_node *in[] = {
				new_r_Proj(cond, mode_X, pn_Cond_true),
				new_r_Proj(cond, mode_X, pn_Cond_false)
			};
			ir_node *blk   = new_r_Block(irg, 1, &in[1]);
327
			in[1] = new_r_Jmp(blk);
328
329
330
331

			set_irn_in(lower_blk, 2, in);

			/* create to Phis */
Matthias Braun's avatar
Matthias Braun committed
332
			ir_node *phi_in[] = {
333
				new_r_Const_null(irg, mode),
Matthias Braun's avatar
Matthias Braun committed
334
335
336
337
338
339
340
341
342
343
344
345
				new_r_Const_long(irg, mode, 0x80000000)
			};
			ir_node *int_phi
				= new_r_Phi(lower_blk, ARRAY_SIZE(phi_in), phi_in, mode);

			ir_node *fphi_in[] = {
				opc,
				new_rd_Sub(dbg, upper_blk, opc, flt_corr, ia32_mode_E)
			};
			ir_node *flt_phi
				= new_r_Phi(lower_blk, ARRAY_SIZE(fphi_in), fphi_in,
				            ia32_mode_E);
346

347
			/* fix Phi links for next part_block() */
348
349
350
351
			if (is_Phi(int_phi))
				add_Block_phi(lower_blk, int_phi);
			if (is_Phi(flt_phi))
				add_Block_phi(lower_blk, flt_phi);
352
353

			float_to_ll = new_bd_ia32_l_FloattoLL(dbg, lower_blk, flt_phi);
354
			l_res = new_r_Proj(float_to_ll, ia32_mode_gp,
355
							   pn_ia32_l_FloattoLL_res_low);
Matthias Braun's avatar
Matthias Braun committed
356
			h_res = new_r_Proj(float_to_ll, mode,
357
							   pn_ia32_l_FloattoLL_res_high);
Matthias Braun's avatar
Matthias Braun committed
358
			h_res = new_rd_Add(dbg, lower_blk, h_res, int_phi, mode);
359
360

			/* move the call and its Proj's to the lower block */
Matthias Braun's avatar
Matthias Braun committed
361
362
			set_nodes_block(node, lower_blk);
			for (ir_node *proj = (ir_node*)get_irn_link(node); proj != NULL;
363
			     proj = (ir_node*)get_irn_link(proj)) {
364
				set_nodes_block(proj, lower_blk);
365
			}
366
		}
Matthias Braun's avatar
Matthias Braun committed
367
368
369
370
		ir_set_dw_lowered(node, l_res, h_res);
	} else if (get_mode_size_bits(mode_from) == 64
	           && get_mode_arithmetic(mode_from) == irma_twos_complement
	           && mode_is_float(mode_to)) {
371
		/* We have a Conv long long -> float here */
Matthias Braun's avatar
Matthias Braun committed
372
373
374
375
376
		ir_node *op_low  = get_lowered_low(op);
		ir_node *op_high = get_lowered_high(op);
		ir_node *block   = get_nodes_block(node);
		ir_node *ll_to_float
			= new_bd_ia32_l_LLtoFloat(dbg, block, op_high, op_low, mode_to);
377

Matthias Braun's avatar
Matthias Braun committed
378
		exchange(node, ll_to_float);
379
	} else {
Matthias Braun's avatar
Matthias Braun committed
380
		ir_default_lower_dw_Conv(node, mode);
381
382
383
	}
}

Matthias Braun's avatar
Matthias Braun committed
384
385
386
static ir_entity *ia32_create_intrinsic_fkt(ir_type *method, const ir_op *op,
                                            const ir_mode *imode,
                                            const ir_mode *omode, void *context)
387
{
Matthias Braun's avatar
Matthias Braun committed
388
389
390
391
392
393
394
395
396
397
	(void)omode;
	(void)context;

	const char *name;
	if (op == op_Div) {
		name = mode_is_signed(imode) ? "__divdi3" : "__udivdi3";
	} else if (op == op_Mod) {
		name = mode_is_signed(imode) ? "__moddi3" : "__umoddi3";
	} else {
		panic("ia32: Unexpected lowering of 64bit op %s", get_op_name(op));
398
	}
Matthias Braun's avatar
Matthias Braun committed
399
400
	return create_compilerlib_entity(new_id_from_str(name), method);
}
401

Matthias Braun's avatar
Matthias Braun committed
402
403
404
void ia32_lower64(void)
{
	/* perform doubleword lowering */
405
406
	ir_mode *word_unsigned = ia32_reg_classes[CLASS_ia32_gp].mode;
	ir_mode *word_signed   = find_signed_mode(word_unsigned);
Matthias Braun's avatar
Matthias Braun committed
407
408
	lwrdw_param_t lower_dw_params = {
		ia32_create_intrinsic_fkt,
Matthias Braun's avatar
Matthias Braun committed
409
		NULL,
410
411
		word_unsigned,
		word_signed,
Matthias Braun's avatar
Matthias Braun committed
412
413
		64,    /* doubleword size */
		be_is_big_endian(),
Matthias Braun's avatar
Matthias Braun committed
414
415
416
417
418
419
420
421
422
	};

	ir_prepare_dw_lowering(&lower_dw_params);
	ir_register_dw_lower_function(op_Add,   ia32_lower_add64);
	ir_register_dw_lower_function(op_Sub,   ia32_lower_sub64);
	ir_register_dw_lower_function(op_Mul,   ia32_lower_mul64);
	ir_register_dw_lower_function(op_Minus, ia32_lower_minus64);
	ir_register_dw_lower_function(op_Conv,  ia32_lower_conv64);
	ir_lower_dw_ops();
423
}