lower_intrinsics.c 31.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 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.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
/**
 * @file
 * @brief   lowering of Calls of intrinsic functions
 * @author  Michael Beck
24
25
26
 */
#include "config.h"

27
28
#include <stdbool.h>

29
#include "lowering.h"
Michael Beck's avatar
Michael Beck committed
30
#include "irop_t.h"
31
32
#include "irprog_t.h"
#include "irnode_t.h"
Michael Beck's avatar
Michael Beck committed
33
#include "irprog_t.h"
34
35
36
#include "irgwalk.h"
#include "ircons.h"
#include "irgmod.h"
37
#include "irgopt.h"
Michael Beck's avatar
Michael Beck committed
38
#include "trouts.h"
39
#include "irverify.h"
40
#include "pmap.h"
41
#include "array_t.h"
42
#include "irpass_t.h"
43
#include "iropt_dbg.h"
44
#include "error.h"
45
#include "be.h"
46
#include "util.h"
47
#include "firmstat_t.h"
48

49
/** Walker environment. */
50
typedef struct walker_env {
Michael Beck's avatar
Michael Beck committed
51
	pmap     *c_map;              /**< The intrinsic call map. */
52
	size_t   nr_of_intrinsics;    /**< statistics */
Michael Beck's avatar
Michael Beck committed
53
	i_instr_record **i_map;       /**< The intrinsic instruction map. */
54
55
56
} walker_env_t;

/**
Michael Beck's avatar
Michael Beck committed
57
 * walker: call all mapper functions
58
 */
59
60
static void call_mapper(ir_node *node, void *env)
{
61
	walker_env_t *wenv = (walker_env_t*)env;
Michael Beck's avatar
Michael Beck committed
62
63
64
65
66
67
68
69
	ir_op *op = get_irn_op(node);

	if (op == op_Call) {
		ir_node *symconst;
		const i_call_record *r;
		ir_entity *ent;

		symconst = get_Call_ptr(node);
70
		if (! is_SymConst_addr_ent(symconst))
Michael Beck's avatar
Michael Beck committed
71
72
			return;

73
		ent = get_SymConst_entity(symconst);
74
		r   = pmap_get(i_call_record const, wenv->c_map, ent);
Michael Beck's avatar
Michael Beck committed
75

76
		if (r != NULL) {
Michael Beck's avatar
Michael Beck committed
77
78
79
			wenv->nr_of_intrinsics += r->i_mapper(node, r->ctx) ? 1 : 0;
		}
	} else {
Matthias Braun's avatar
Matthias Braun committed
80
		if (op->code < (unsigned) ARR_LEN(wenv->i_map)) {
Michael Beck's avatar
Michael Beck committed
81
82
83
84
85
86
87
			const i_instr_record *r = wenv->i_map[op->code];
			/* run all possible mapper */
			while (r) {
				if (r->i_mapper(node, r->ctx)) {
					++wenv->nr_of_intrinsics;
					break;
				}
88
				r = (const i_instr_record*)r->link;
Michael Beck's avatar
Michael Beck committed
89
90
91
			}
		}
	}
92
}
93

94
size_t lower_intrinsics(i_record *list, size_t length, int part_block_used)
95
{
Michael Beck's avatar
Michael Beck committed
96
	size_t         i, n;
Matthias Braun's avatar
Matthias Braun committed
97
	size_t         n_ops = ir_get_n_opcodes();
Michael Beck's avatar
Michael Beck committed
98
99
100
	ir_graph       *irg;
	pmap           *c_map = pmap_create_ex(length);
	i_instr_record **i_map;
101
	size_t         nr_of_intrinsics = 0;
Michael Beck's avatar
Michael Beck committed
102
103
104
	walker_env_t   wenv;

	/* we use the ir_op generic pointers here */
Matthias Braun's avatar
Matthias Braun committed
105
	NEW_ARR_A(i_instr_record *, i_map, n_ops);
Michael Beck's avatar
Michael Beck committed
106
107
108
	memset((void *)i_map, 0, sizeof(*i_map) * n_ops);

	/* fill a map for faster search */
109
	for (i = 0; i < length; ++i) {
Michael Beck's avatar
Michael Beck committed
110
111
112
113
		if (list[i].i_call.kind == INTRINSIC_CALL) {
			pmap_insert(c_map, list[i].i_call.i_ent, (void *)&list[i].i_call);
		} else {
			ir_op *op = list[i].i_instr.op;
Matthias Braun's avatar
Matthias Braun committed
114
			assert(op->code < (unsigned) ARR_LEN(i_map));
Michael Beck's avatar
Michael Beck committed
115
116
117
118
119
120
121
122
123

			list[i].i_instr.link = i_map[op->code];
			i_map[op->code] = &list[i].i_instr;
		}
	}

	wenv.c_map = c_map;
	wenv.i_map = i_map;

Michael Beck's avatar
Michael Beck committed
124
125
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
		irg = get_irp_irg(i);
Michael Beck's avatar
Michael Beck committed
126

127
128
		if (part_block_used) {
			ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
129
			collect_phiprojs(irg);
130
		}
131

Michael Beck's avatar
Michael Beck committed
132
133
134
		wenv.nr_of_intrinsics = 0;
		irg_walk_graph(irg, NULL, call_mapper, &wenv);

135
136
137
		if (part_block_used)
			ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);

138
		if (wenv.nr_of_intrinsics > 0) {
139
			confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
Michael Beck's avatar
Michael Beck committed
140
141
142
143
144
145
			nr_of_intrinsics += wenv.nr_of_intrinsics;
		}
	}
	pmap_destroy(c_map);

	return nr_of_intrinsics;
146
}
147

148
typedef struct pass_t {
149
150
	ir_prog_pass_t pass;

151
152
	int      part_block_used;
	size_t   length;
153
	i_record list[1];
154
} pass_t;
155
156

/**
Michael Beck's avatar
Michael Beck committed
157
 * Wrapper for running lower_intrinsics() as an ir_prog pass.
158
 */
159
static int pass_wrapper(ir_prog *irp, void *context)
160
{
161
	pass_t *pass = (pass_t*)context;
162
	(void) irp; /* TODO: set current irp, or remove parameter */
163
164
	lower_intrinsics(pass->list, pass->length, pass->part_block_used);
	/* probably this pass should not run again */
165
166
	return 0;
}
167
168

/**
Michael Beck's avatar
Michael Beck committed
169
 * Creates an ir_prog pass for lower_intrinsics.
170
171
172
173
174
175
176
177
 *
 * @param name             the name of this pass or NULL
 * @param list             an array of intrinsic map records
 * @param length           the length of the array
 * @param part_block_used  set to true if part_block() must be using during lowering
 */
ir_prog_pass_t *lower_intrinsics_pass(
	const char *name,
178
	i_record *list, size_t length, int part_block_used)
179
{
Christoph Mallon's avatar
Christoph Mallon committed
180
	pass_t *const pass = XMALLOCF(pass_t, list, length);
Michael Beck's avatar
Michael Beck committed
181
182
183
184
	memcpy(pass->list, list, sizeof(list[0]) * length);
	pass->length          = length;
	pass->part_block_used = part_block_used;

Michael Beck's avatar
Michael Beck committed
185
186
	return def_prog_pass_constructor(
		&pass->pass, name ? name : "lower_intrinsics", pass_wrapper);
187
}
188

189
190
191
192
193
194
195
196
197
/**
 * Helper function, replace the call by the given node.
 *
 * @param irn      the result node
 * @param call     the call to replace
 * @param mem      the new mem result
 * @param reg_jmp  new regular control flow, if NULL, a Jmp will be used
 * @param exc_jmp  new exception control flow, if reg_jmp == NULL, a Bad will be used
 */
198
199
static void replace_call(ir_node *irn, ir_node *call, ir_node *mem,
                         ir_node *reg_jmp, ir_node *exc_jmp)
200
{
201
202
	ir_node  *block = get_nodes_block(call);
	ir_graph *irg   = get_irn_irg(block);
203
	ir_node  *rest  = new_r_Tuple(block, 1, &irn);
Matthias Braun's avatar
Matthias Braun committed
204

205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
	if (ir_throws_exception(call)) {
		turn_into_tuple(call, pn_Call_max+1);
		if (reg_jmp == NULL) {
			reg_jmp = new_r_Jmp(block);
		}
		if (exc_jmp == NULL) {
			exc_jmp = new_r_Bad(irg, mode_X);
		}
		set_Tuple_pred(call, pn_Call_X_regular, reg_jmp);
		set_Tuple_pred(call, pn_Call_X_except, exc_jmp);
	} else {
		assert(reg_jmp == NULL);
		assert(exc_jmp == NULL);
		turn_into_tuple(call, pn_Call_T_result+1);
		assert(pn_Call_M <= pn_Call_T_result);
		assert(pn_Call_X_regular > pn_Call_T_result);
		assert(pn_Call_X_except > pn_Call_T_result);
222
	}
223
	set_Tuple_pred(call, pn_Call_M, mem);
224
225
	set_Tuple_pred(call, pn_Call_T_result, rest);
}
226

227
228
int i_mapper_abs(ir_node *call, void *ctx)
{
229
230
231
232
233
234
235
	ir_node  *mem      = get_Call_mem(call);
	ir_node  *block    = get_nodes_block(call);
	ir_node  *op       = get_Call_param(call, 0);
	ir_graph *irg      = get_irn_irg(call);
	ir_mode  *mode     = get_irn_mode(op);
	dbg_info *dbg      = get_irn_dbg_info(call);
	ir_node  *zero     = new_r_Const(irg, get_mode_null(mode));
236
	ir_node  *cmp      = new_rd_Cmp(dbg, block, op, zero, ir_relation_less);
237
238
239
	ir_node  *minus_op = new_rd_Minus(dbg, block, op, mode);
	ir_node  *mux;
	arch_allow_ifconv_func allow_ifconv = be_get_backend_param()->allow_ifconv;
Matthias Braun's avatar
Matthias Braun committed
240
	(void) ctx;
Michael Beck's avatar
Michael Beck committed
241

242
	/* mux allowed by backend? */
243
	if (!allow_ifconv(cmp, op, minus_op))
244
245
246
		return 0;

	/* construct Mux */
247
	mux = new_rd_Mux(dbg, block, cmp, op, minus_op, mode);
248
249
	DBG_OPT_ALGSIM0(call, mux, FS_OPT_RTS_ABS);
	replace_call(mux, call, mem, NULL, NULL);
Michael Beck's avatar
Michael Beck committed
250
	return 1;
251
}
252

253
254
int i_mapper_bswap(ir_node *call, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
255
256
257
258
259
260
261
262
	ir_node *mem   = get_Call_mem(call);
	ir_node *block = get_nodes_block(call);
	ir_node *op    = get_Call_param(call, 0);
	ir_type *tp    = get_Call_type(call);
	dbg_info *dbg  = get_irn_dbg_info(call);
	ir_node *irn;
	(void) ctx;

263
264
	ir_graph *const irg = get_Block_irg(block);
	irn = new_rd_Builtin(dbg, block, get_irg_no_mem(irg), 1, &op, ir_bk_bswap, tp);
Michael Beck's avatar
Michael Beck committed
265
	set_irn_pinned(irn, op_pin_state_floats);
266
	irn = new_r_Proj(irn, get_irn_mode(op), pn_Builtin_max+1);
Michael Beck's avatar
Michael Beck committed
267
268
	replace_call(irn, call, mem, NULL, NULL);
	return 1;
269
}
Michael Beck's avatar
Michael Beck committed
270

271
272
int i_mapper_alloca(ir_node *call, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
273
274
275
276
277
	ir_node *mem   = get_Call_mem(call);
	ir_node *block = get_nodes_block(call);
	ir_node *op    = get_Call_param(call, 0);
	ir_node *irn, *exc, *no_exc;
	dbg_info *dbg  = get_irn_dbg_info(call);
Matthias Braun's avatar
Matthias Braun committed
278
	(void) ctx;
Michael Beck's avatar
Michael Beck committed
279

Matthias Braun's avatar
Matthias Braun committed
280
	if (mode_is_signed(get_irn_mode(op))) {
281
282
283
284
285
		ir_mode *mode = get_irn_mode(op);
		mode = find_unsigned_mode(mode);
		if (mode == NULL) {
			panic("Cannot find unsigned mode for %M", mode);
		}
286
		op = new_rd_Conv(dbg, block, op, mode);
Matthias Braun's avatar
Matthias Braun committed
287
288
	}

289
	irn    = new_rd_Alloc(dbg, block, mem, op, get_unknown_type(), stack_alloc);
290
291
	mem    = new_rd_Proj(dbg, irn, mode_M, pn_Alloc_M);
	irn    = new_rd_Proj(dbg, irn, get_modeP_data(), pn_Alloc_res);
292
293
294
295
296
297
298
299
	if (ir_throws_exception(call)) {
		no_exc = new_rd_Proj(dbg, irn, mode_X, pn_Alloc_X_regular);
		exc    = new_rd_Proj(dbg, irn, mode_X, pn_Alloc_X_except);
		ir_set_throws_exception(irn, true);
	} else {
		no_exc = NULL;
		exc    = NULL;
	}
300

301
	DBG_OPT_ALGSIM0(call, irn, FS_OPT_RTS_ALLOCA);
302
	replace_call(irn, call, mem, no_exc, exc);
303
	return 1;
304
}
305

306
307
int i_mapper_sqrt(ir_node *call, void *ctx)
{
Matthias Braun's avatar
Matthias Braun committed
308
309
310
	ir_node   *mem;
	ir_tarval *tv;
	ir_node   *op = get_Call_param(call, 0);
311
312
313
314
315
316
317
318
319
	(void) ctx;

	if (!is_Const(op))
		return 0;

	tv = get_Const_tarval(op);
	if (! tarval_is_null(tv) && !tarval_is_one(tv))
		return 0;

320
	mem = get_Call_mem(call);
321
322

	/* sqrt(0) = 0, sqrt(1) = 1 */
323
	DBG_OPT_ALGSIM0(call, op, FS_OPT_RTS_SQRT);
324
	replace_call(op, call, mem, NULL, NULL);
325
	return 1;
326
}
327

328
329
int i_mapper_cbrt(ir_node *call, void *ctx)
{
Matthias Braun's avatar
Matthias Braun committed
330
331
332
	ir_node   *mem;
	ir_tarval *tv;
	ir_node   *op = get_Call_param(call, 0);
Michael Beck's avatar
Michael Beck committed
333
334
335
336
337
338
339
340
341
342
343
344
	(void) ctx;

	if (!is_Const(op))
		return 0;

	tv = get_Const_tarval(op);
	if (! tarval_is_null(tv) && !tarval_is_one(tv) && !tarval_is_minus_one(tv))
		return 0;

	mem = get_Call_mem(call);

	/* cbrt(0) = 0, cbrt(1) = 1, cbrt(-1) = -1 */
345
	DBG_OPT_ALGSIM0(call, op, FS_OPT_RTS_CBRT);
Michael Beck's avatar
Michael Beck committed
346
347
	replace_call(op, call, mem, NULL, NULL);
	return 1;
348
}
Michael Beck's avatar
Michael Beck committed
349

350
351
int i_mapper_pow(ir_node *call, void *ctx)
{
352
353
354
355
356
357
358
	ir_node  *left    = get_Call_param(call, 0);
	ir_node  *right   = get_Call_param(call, 1);
	ir_node  *block   = get_nodes_block(call);
	ir_graph *irg     = get_irn_irg(block);
	ir_node  *reg_jmp = NULL;
	ir_node  *exc_jmp = NULL;
	ir_node  *irn;
359
	dbg_info *dbg;
360
	ir_node  *mem;
361
362
363
364
365
366
	(void) ctx;

	if (is_Const(left) && is_Const_one(left)) {
		/* pow (1.0, x) = 1.0 */
		irn = left;
	} else if (is_Const(right)) {
Matthias Braun's avatar
Matthias Braun committed
367
		ir_tarval *tv = get_Const_tarval(right);
368
369
370
		if (tarval_is_null(tv)) {
			/* pow(x, 0.0) = 1.0 */
			ir_mode *mode = get_tarval_mode(tv);
371
			irn = new_r_Const(irg, get_mode_one(mode));
372
373
374
375
376
377
378
379
		} else if (tarval_is_one(tv)) {
			/* pow(x, 1.0) = x */
			irn = left;
		} else if (tarval_is_minus_one(tv)) {
			/* pow(x, -1.0) = 1/x */
			irn = NULL;
		} else
			return 0;
380
381
	} else {
		return 0;
382
383
384
385
386
387
	}

	mem = get_Call_mem(call);
	dbg = get_irn_dbg_info(call);

	if (irn == NULL) {
388
		ir_mode *result_mode = get_irn_mode(left);
389
		ir_node *div;
390

391
392
393
394
395
396
397
		ir_mode *mode             = result_mode;
		ir_mode *float_arithmetic = be_get_backend_param()->mode_float_arithmetic;
		if (float_arithmetic != NULL) {
			left = new_r_Conv(block, left, float_arithmetic);
			mode = float_arithmetic;
		}

398
		irn  = new_r_Const(irg, get_mode_one(mode));
399
400
401
		div  = new_rd_Div(dbg, block, mem, irn, left, mode, op_pin_state_pinned);
		mem  = new_r_Proj(div, mode_M, pn_Div_M);
		irn  = new_r_Proj(div, mode, pn_Div_res);
402
403
404
405
406
		if (ir_throws_exception(call)) {
			reg_jmp = new_r_Proj(div, mode_X, pn_Div_X_regular);
			exc_jmp = new_r_Proj(div, mode_X, pn_Div_X_except);
			ir_set_throws_exception(div, true);
		}
407
408
409
		if (result_mode != mode) {
			irn = new_r_Conv(block, irn, result_mode);
		}
410
	}
411
	DBG_OPT_ALGSIM0(call, irn, FS_OPT_RTS_POW);
412
413
	replace_call(irn, call, mem, reg_jmp, exc_jmp);
	return 1;
414
}
415

416
417
int i_mapper_exp(ir_node *call, void *ctx)
{
418
419
420
421
422
	ir_node *val  = get_Call_param(call, 0);
	(void) ctx;

	if (is_Const(val) && is_Const_null(val)) {
		/* exp(0.0) = 1.0 */
423
		ir_graph *irg  = get_irn_irg(val);
424
		ir_mode *mode  = get_irn_mode(val);
425
		ir_node *irn   = new_r_Const(irg, get_mode_one(mode));
426
		ir_node *mem   = get_Call_mem(call);
427
		DBG_OPT_ALGSIM0(call, irn, FS_OPT_RTS_EXP);
428
		replace_call(irn, call, mem, NULL, NULL);
Michael Beck's avatar
Michael Beck committed
429
430
431
		return 1;
	}
	return 0;
432
}
Michael Beck's avatar
Michael Beck committed
433

434
435
436
437
438
439
440
441
442
443
int i_mapper_exp2(ir_node *call, void *ctx)
{
	return i_mapper_exp(call, ctx);
}

int i_mapper_exp10(ir_node *call, void *ctx)
{
	return i_mapper_exp(call, ctx);
}

444
445
446
/**
 * A mapper for mapping f(0.0) to 0.0.
 */
447
448
static int i_mapper_zero_to_zero(ir_node *call, void *ctx, int reason)
{
449
450
451
452
	ir_node *val  = get_Call_param(call, 0);
	(void) ctx;

	if (is_Const(val) && is_Const_null(val)) {
453
		/* f(0.0) = 0.0 */
454
		ir_node *mem = get_Call_mem(call);
455
		DBG_OPT_ALGSIM0(call, val, reason);
456
457
458
459
		replace_call(val, call, mem, NULL, NULL);
		return 1;
	}
	return 0;
460
}
461

462
463
464
/**
 * A mapper for mapping f(1.0) to 0.0.
 */
465
466
static int i_mapper_one_to_zero(ir_node *call, void *ctx, int reason)
{
467
468
469
470
471
	ir_node *val  = get_Call_param(call, 0);
	(void) ctx;

	if (is_Const(val) && is_Const_one(val)) {
		/* acos(1.0) = 0.0 */
472
473
474
475
		ir_graph *irg = get_irn_irg(val);
		ir_mode *mode = get_irn_mode(val);
		ir_node *irn  = new_r_Const(irg, get_mode_null(mode));
		ir_node *mem  = get_Call_mem(call);
476
		DBG_OPT_ALGSIM0(call, irn, reason);
477
478
479
480
		replace_call(irn, call, mem, NULL, NULL);
		return 1;
	}
	return 0;
481
}
482
483
484
485
486
487

/**
 * A mapper for mapping a functions with the following characteristics:
 * f(-x)  = f(x).
 * f(0.0) = 1.0
 */
488
489
static int i_mapper_symmetric_zero_to_one(ir_node *call, void *ctx, int reason)
{
490
491
	int      changed = 0;
	ir_node *val     = get_Call_param(call, 0);
492
493
	(void) ctx;

494
	if (is_Conv(val)) {
495
496
		ir_node *op = get_Conv_op(val);
		if (is_Minus(op)) {
497
			/* f(-x) = f(x) with strictConv */
498
499
500
501
502
			ir_node *block = get_nodes_block(call);
			ir_mode *mode  = get_irn_mode(val);
			dbg_info *dbg  = get_irn_dbg_info(val);

			op = get_Minus_op(op);
503
			val = new_rd_Conv(dbg, block, op, mode);
504
			DBG_OPT_ALGSIM2(call, op, call, FS_OPT_RTS_SYMMETRIC);
505
			set_Call_param(call, 0, val);
506
			changed = 1;
507
508
		}
	} else if (is_Minus(val)) {
509
		/* f(-x) = f(x) */
510
		val = get_Minus_op(val);
511
		DBG_OPT_ALGSIM2(call, val, call, FS_OPT_RTS_SYMMETRIC);
512
		set_Call_param(call, 0, val);
513
		changed = 1;
514
515
516
	}

	if (is_Const(val) && is_Const_null(val)) {
517
		/* f(0.0) = 1.0 */
518
		ir_graph *irg  = get_irn_irg(val);
519
		ir_mode *mode  = get_irn_mode(val);
520
		ir_node *irn   = new_r_Const(irg, get_mode_one(mode));
521
		ir_node *mem   = get_Call_mem(call);
522
		DBG_OPT_ALGSIM0(call, irn, reason);
523
		replace_call(irn, call, mem, NULL, NULL);
524
		changed = 1;
525
	}
526
	return changed;
527
}
528

529
530
int i_mapper_log(ir_node *call, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
531
532
	/* log(1.0) = 0.0 */
	return i_mapper_one_to_zero(call, ctx, FS_OPT_RTS_LOG);
533
}
Michael Beck's avatar
Michael Beck committed
534

535
536
537
538
539
540
541
542
543
544
545
546
int i_mapper_log2(ir_node *call, void *ctx)
{
	/* log2(1.0) = 0.0 */
	return i_mapper_one_to_zero(call, ctx, FS_OPT_RTS_LOG);
}

int i_mapper_log10(ir_node *call, void *ctx)
{
	/* log10(1.0) = 0.0 */
	return i_mapper_one_to_zero(call, ctx, FS_OPT_RTS_LOG);
}

547
548
int i_mapper_sin(ir_node *call, void *ctx)
{
549
	/* sin(0.0) = 0.0 */
550
	return i_mapper_zero_to_zero(call, ctx, FS_OPT_RTS_SIN);
551
}
552

553
554
int i_mapper_cos(ir_node *call, void *ctx)
{
555
	/* cos(0.0) = 1.0, cos(-x) = x */
556
	return i_mapper_symmetric_zero_to_one(call, ctx, FS_OPT_RTS_COS);
557
}
558

559
560
int i_mapper_tan(ir_node *call, void *ctx)
{
561
	/* tan(0.0) = 0.0 */
562
	return i_mapper_zero_to_zero(call, ctx, FS_OPT_RTS_TAN);
563
}
564

565
566
int i_mapper_asin(ir_node *call, void *ctx)
{
567
	/* asin(0.0) = 0.0 */
568
	return i_mapper_zero_to_zero(call, ctx, FS_OPT_RTS_ASIN);
569
}
570

571
572
int i_mapper_acos(ir_node *call, void *ctx)
{
573
	/* acos(1.0) = 0.0 */
574
	return i_mapper_one_to_zero(call, ctx, FS_OPT_RTS_ACOS);
575
}
576

577
578
int i_mapper_atan(ir_node *call, void *ctx)
{
579
	/* atan(0.0) = 0.0 */
580
	return i_mapper_zero_to_zero(call, ctx, FS_OPT_RTS_ATAN);
581
}
582

583
584
int i_mapper_sinh(ir_node *call, void *ctx)
{
585
	/* sinh(0.0) = 0.0 */
586
	return i_mapper_zero_to_zero(call, ctx, FS_OPT_RTS_SINH);
587
}
588

589
590
int i_mapper_cosh(ir_node *call, void *ctx)
{
591
	/* cosh(0.0) = 1.0, cosh(-x) = x */
592
	return i_mapper_symmetric_zero_to_one(call, ctx, FS_OPT_RTS_COSH);
593
}
594

595
596
int i_mapper_tanh(ir_node *call, void *ctx)
{
597
	/* tanh(0.0) = 0.0 */
598
	return i_mapper_zero_to_zero(call, ctx, FS_OPT_RTS_TANH);
599
}
600

Michael Beck's avatar
Michael Beck committed
601
602
603
604
605
606
/**
 * Return the const entity that is accessed through the pointer ptr or
 * NULL if there is no entity (or the entity is not constant).
 *
 * @param ptr  the pointer
 */
Matthias Braun's avatar
Matthias Braun committed
607
608
static ir_entity *get_const_entity(ir_node *ptr)
{
609
610
	if (is_SymConst_addr_ent(ptr)) {
		ir_entity *ent = get_SymConst_entity(ptr);
611

Matthias Braun's avatar
Matthias Braun committed
612
		if (get_entity_linkage(ent) & IR_LINKAGE_CONSTANT) {
Michael Beck's avatar
Michael Beck committed
613
614
615
			/* a constant entity */
			return ent;
		}
616
	}
Michael Beck's avatar
Michael Beck committed
617
	return NULL;
618
}
619

620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
static ir_tarval *get_initializer_value(ir_initializer_t *const init, ir_mode *const mode)
{
	switch (get_initializer_kind(init)) {
	case IR_INITIALIZER_NULL:
		return get_mode_null(mode);

	case IR_INITIALIZER_TARVAL:
		return get_initializer_tarval_value(init);

	case IR_INITIALIZER_CONST: {
		ir_node *const irn = get_initializer_const_value(init);
		if (is_Const(irn))
			return get_Const_tarval(irn);
		break;
	}

	case IR_INITIALIZER_COMPOUND:
		break;
	}

	return get_tarval_undefined();
}

643
644
static bool initializer_val_is_null(ir_initializer_t *init)
{
Matthias Braun's avatar
Matthias Braun committed
645
	ir_tarval *tv;
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663

	if (get_initializer_kind(init) == IR_INITIALIZER_NULL)
		return true;

	if (get_initializer_kind(init) == IR_INITIALIZER_TARVAL) {
		tv = get_initializer_tarval_value(init);
	} else if (get_initializer_kind(init) == IR_INITIALIZER_CONST) {
		ir_node *irn = get_initializer_const_value(init);
		if (!is_Const(irn))
			return false;
		tv = get_Const_tarval(irn);
	} else {
		return false;
	}

	return tarval_is_null(tv);
}

Michael Beck's avatar
Michael Beck committed
664
665
666
667
668
/**
 * Calculate the value of strlen if possible.
 *
 * @param ent     the entity
 * @param res_tp  the result type
Michael Beck's avatar
Michael Beck committed
669
670
671
 *
 * @return a Const node containing the strlen() result or NULL
 *         if the evaluation fails
Michael Beck's avatar
Michael Beck committed
672
 */
673
static ir_node *eval_strlen(ir_graph *irg, ir_entity *ent, ir_type *res_tp)
674
{
Michael Beck's avatar
Michael Beck committed
675
676
	ir_type *tp = get_entity_type(ent);
	ir_mode *mode;
677
	ir_initializer_t *initializer;
678
679
	size_t            size;
	size_t            i;
Michael Beck's avatar
Michael Beck committed
680
681
682
683
684
685
686
687
688

	if (! is_Array_type(tp))
		return NULL;
	tp = get_array_element_type(tp);
	if (! is_Primitive_type(tp))
		return NULL;
	mode = get_type_mode(tp);

	/* FIXME: This is too restrict, as the type char might be more the 8bits */
689
	if (!mode_is_int(mode) || get_mode_size_bits(mode) != 8)
Michael Beck's avatar
Michael Beck committed
690
691
		return NULL;

692
693
694
695
696
697
698
699
	initializer = get_entity_initializer(ent);
	if (get_initializer_kind(initializer) != IR_INITIALIZER_COMPOUND)
		return NULL;

	size = get_initializer_compound_n_entries(initializer);
	for (i = 0; i < size; ++i) {
		ir_initializer_t *val = get_initializer_compound_value(initializer, i);
		if (initializer_val_is_null(val)) {
Matthias Braun's avatar
Matthias Braun committed
700
			ir_tarval *tv = new_tarval_from_long(i, get_type_mode(res_tp));
701
			return new_r_Const(irg, tv);
702
		}
Michael Beck's avatar
Michael Beck committed
703
	}
704

Michael Beck's avatar
Michael Beck committed
705
	return NULL;
706
}
Michael Beck's avatar
Michael Beck committed
707

708
709
int i_mapper_strlen(ir_node *call, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
710
711
	ir_node *s     = get_Call_param(call, 0);
	ir_entity *ent = get_const_entity(s);
Michael Beck's avatar
Michael Beck committed
712

Michael Beck's avatar
Michael Beck committed
713
714
	(void) ctx;

Michael Beck's avatar
Michael Beck committed
715
	/* FIXME: this cannot handle constant strings inside struct initializers yet */
Michael Beck's avatar
Michael Beck committed
716
717
718
719
720
721
	if (ent != NULL) {
		/* a constant entity */
		ir_type *tp = get_Call_type(call);
		ir_node *irn;

		tp  = get_method_res_type(tp, 0);
722
		irn = eval_strlen(get_irn_irg(call), ent, tp);
Michael Beck's avatar
Michael Beck committed
723
724
725
726
727
728
729
730
731

		if (irn) {
			ir_node *mem = get_Call_mem(call);
			DBG_OPT_ALGSIM0(call, irn, FS_OPT_RTS_STRLEN);
			replace_call(irn, call, mem, NULL, NULL);
			return 1;
		}
	}
	return 0;
732
}
Michael Beck's avatar
Michael Beck committed
733

Michael Beck's avatar
Michael Beck committed
734
735
736
737
738
739
740
741
742
743
/**
 * Calculate the value of strlen if possible.
 *
 * @param left    the left entity
 * @param right   the right entity
 * @param res_tp  the result type
 *
 * @return a Const node containing the strcmp() result or NULL
 *         if the evaluation fails
 */
744
745
static ir_node *eval_strcmp(ir_graph *irg, ir_entity *left, ir_entity *right,
                            ir_type *res_tp)
746
{
747
748
749
750
751
752
753
754
	ir_type          *tp;
	ir_mode          *mode;
	ir_initializer_t *init_l;
	ir_initializer_t *init_r;
	size_t            size_l;
	size_t            size_r;
	size_t            size;
	size_t            i;
Michael Beck's avatar
Michael Beck committed
755
756
757
758
759
760
761
762
763
764

	tp = get_entity_type(left);
	if (! is_Array_type(tp))
		return NULL;
	tp = get_array_element_type(tp);
	if (! is_Primitive_type(tp))
		return NULL;
	mode = get_type_mode(tp);

	/* FIXME: This is too restrict, as the type char might be more the 8bits */
765
	if (!mode_is_int(mode) || get_mode_size_bits(mode) != 8)
Michael Beck's avatar
Michael Beck committed
766
767
768
769
770
771
772
773
774
775
776
		return NULL;

	tp = get_entity_type(right);
	if (! is_Array_type(tp))
		return NULL;
	tp = get_array_element_type(tp);
	if (! is_Primitive_type(tp))
		return NULL;
	mode = get_type_mode(tp);

	/* FIXME: This is too restrict, as the type char might be more the 8bits */
777
	if (!mode_is_int(mode) || get_mode_size_bits(mode) != 8)
Michael Beck's avatar
Michael Beck committed
778
		return NULL;
Michael Beck's avatar
Michael Beck committed
779

780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
	init_l = get_entity_initializer(left);
	init_r = get_entity_initializer(right);
	if (get_initializer_kind(init_l) != IR_INITIALIZER_COMPOUND ||
	    get_initializer_kind(init_r) != IR_INITIALIZER_COMPOUND)
		return NULL;

	size_l = get_initializer_compound_n_entries(init_l);
	size_r = get_initializer_compound_n_entries(init_r);
	size   = size_l < size_r ? size_l : size_r;

	for (i = 0; i != size; ++i) {
		ir_initializer_t *const val_l = get_initializer_compound_value(init_l, i);
		ir_tarval        *const tv_l  = get_initializer_value(val_l, mode);
		ir_initializer_t *const val_r = get_initializer_compound_value(init_r, i);
		ir_tarval        *const tv_r  = get_initializer_value(val_r, mode);

		if (!tarval_is_constant(tv_l) || !tarval_is_constant(tv_r))
			return NULL;

		if (tv_l != tv_r) {
			ir_mode   *const res_mode = get_type_mode(res_tp);
			ir_tarval *const res_l    = tarval_convert_to(tv_l, res_mode);
			ir_tarval *const res_r    = tarval_convert_to(tv_r, res_mode);
			ir_tarval *const tv       = tarval_sub(res_l, res_r, res_mode);
			return new_r_Const(irg, tv);
		}

		if (tarval_is_null(tv_l)) {
			ir_tarval *const tv = get_mode_null(get_type_mode(res_tp));
			return new_r_Const(irg, tv);
		}
	}
812

Michael Beck's avatar
Michael Beck committed
813
	return NULL;
814
}
Michael Beck's avatar
Michael Beck committed
815
816
817
818
819
820
821
822

/**
 * Checks if an entity represents the empty string.
 *
 * @param ent     the entity
 *
 * @return non-zero if ent represents the empty string
 */
823
824
static int is_empty_string(ir_entity *ent)
{
825
826
827
828
	ir_type          *tp = get_entity_type(ent);
	ir_mode          *mode;
	ir_initializer_t *initializer;
	ir_initializer_t *init0;
Michael Beck's avatar
Michael Beck committed
829
830
831
832
833
834
835
836
837

	if (! is_Array_type(tp))
		return 0;
	tp = get_array_element_type(tp);
	if (! is_Primitive_type(tp))
		return 0;
	mode = get_type_mode(tp);

	/* FIXME: This is too restrict, as the type char might be more the 8bits */
838
	if (!mode_is_int(mode) || get_mode_size_bits(mode) != 8)
Michael Beck's avatar
Michael Beck committed
839
840
		return 0;

841
842
843
844
845
	initializer = get_entity_initializer(ent);
	if (get_initializer_kind(initializer) != IR_INITIALIZER_COMPOUND)
		return 0;

	if (get_initializer_compound_n_entries(initializer) < 1)
Michael Beck's avatar
Michael Beck committed
846
847
		return 0;

848
	init0 = get_initializer_compound_value(initializer, 0);
849
	return initializer_val_is_null(init0);
850
}
Michael Beck's avatar
Michael Beck committed
851

852
853
int i_mapper_strcmp(ir_node *call, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
854
855
856
857
858
	ir_node   *left    = get_Call_param(call, 0);
	ir_node   *right   = get_Call_param(call, 1);
	ir_node   *irn     = NULL;
	ir_node   *exc     = NULL;
	ir_node   *reg     = NULL;
859
	ir_type   *call_tp = get_Call_type(call);
Michael Beck's avatar
Michael Beck committed
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
	ir_type   *res_tp  = get_method_res_type(call_tp, 0);
	ir_entity *ent_l, *ent_r;
	ir_type   *char_tp;
	ir_node   *v;

	(void) ctx;

	/* do some type checks first */
	if (! is_Primitive_type(res_tp))
		return 0;
	char_tp = get_method_param_type(call_tp, 0);
	if (char_tp != get_method_param_type(call_tp, 1))
		return 0;
	if (! is_Pointer_type(char_tp))
		return 0;
	char_tp = get_pointer_points_to_type(char_tp);

877
	ir_node *mem = get_Call_mem(call);
Michael Beck's avatar
Michael Beck committed
878
879
	if (left == right) {
		/* a strcmp(s, s) ==> 0 */
880
881
		ir_graph *irg = get_irn_irg(call);
		ir_mode *mode = get_type_mode(res_tp);
Michael Beck's avatar
Michael Beck committed
882

883
		irn = new_r_Const(irg, get_mode_null(mode));
Michael Beck's avatar
Michael Beck committed
884
885
886
887
888
889
890
891
892
		DBG_OPT_ALGSIM0(call, irn, FS_OPT_RTS_STRCMP);
		replace_call(irn, call, mem, NULL, NULL);
		return 1;
	}
	ent_l = get_const_entity(left);
	ent_r = get_const_entity(right);

	if (ent_l != NULL && ent_r != NULL) {
		/* both entities are const, try to evaluate */
893
		irn = eval_strcmp(get_irn_irg(call), ent_l, ent_r, res_tp);
Michael Beck's avatar
Michael Beck committed
894
895
896
897
898
899
900
901
902
	} else if (ent_l != NULL) {
		if (is_empty_string(ent_l)) {
			/* s strcmp("", s) ==> -(*s)*/
			v = right;
			goto replace_by_call;
		}
	} else if (ent_r != NULL) {
		if (is_empty_string(ent_r)) {
			/* s strcmp(s, "") ==> (*s) */
903
			ir_node  *block;
Michael Beck's avatar
Michael Beck committed
904
905
906
907
908
909
910
911
912
913
914
			dbg_info *dbg;
			ir_mode  *mode;

			v = left;
replace_by_call:
			mem   = get_Call_mem(call);
			block = get_nodes_block(call);
			dbg   = get_irn_dbg_info(call);
			mode  = get_type_mode(char_tp);

			/* replace the strcmp by (*x) */
915
			irn = new_rd_Load(dbg, block, mem, v, mode, cons_none);
916
917
			mem = new_r_Proj(irn, mode_M, pn_Load_M);
			irn = new_r_Proj(irn, mode, pn_Load_res);
918
919
920
921
922
923
924
925
			if (ir_throws_exception(call)) {
				exc = new_r_Proj(irn, mode_X, pn_Load_X_except);
				reg = new_r_Proj(irn, mode_X, pn_Load_X_regular);
				ir_set_throws_exception(irn, true);
			} else {
				exc = NULL;
				reg = NULL;
			}
Michael Beck's avatar
Michael Beck committed
926
927
928

			/* conv to the result mode */
			mode = get_type_mode(res_tp);
929
			irn  = new_rd_Conv(dbg, block, irn, mode);
Michael Beck's avatar
Michael Beck committed
930
931
932

			if (v == right) {
				/* negate in the ("", s) case */
933
				irn = new_rd_Minus(dbg, block, irn, mode);
Michael Beck's avatar
Michael Beck committed
934
935
936
			}
		}
	}
Michael Beck's avatar
Michael Beck committed
937
938
939
940
941
942
943

	if (irn != NULL) {
		DBG_OPT_ALGSIM0(call, irn, FS_OPT_RTS_STRCMP);
		replace_call(irn, call, mem, reg, exc);
		return 1;
	}

Michael Beck's avatar
Michael Beck committed
944
	return 0;
945
}
Michael Beck's avatar
Michael Beck committed
946

947
948
int i_mapper_strncmp(ir_node *call, void *ctx)
{
Michael Beck's avatar
Michael Beck committed
949
950
951
952
953
954
955
956
957
	ir_node *left  = get_Call_param(call, 0);
	ir_node *right = get_Call_param(call, 1);
	ir_node *len   = get_Call_param(call, 2);
	ir_node *irn;
	(void) ctx;

	if (left == right || (is_Const(len) && is_Const_null(len))) {
		/* a strncmp(s, s, len) ==> 0 OR
		   a strncmp(a, b, 0) ==> 0 */
958
		ir_graph  *irg     = get_irn_irg(call);
Michael Beck's avatar
Michael Beck committed
959
960
961
962
963
964
965
		ir_node   *mem     = get_Call_mem(call);
		ir_node   *adr     = get_Call_ptr(call);
		ir_entity *ent     = get_SymConst_entity(adr);
		ir_type   *call_tp = get_entity_type(ent);
		ir_type   *res_tp  = get_method_res_type(call_tp, 0);
		ir_mode   *mode    = get_type_mode(res_tp);

966
		irn = new_r_Const(irg, get_mode_null(mode));
Michael Beck's avatar
Michael Beck committed
967
968
969
970
971
		DBG_OPT_ALGSIM0(call, irn, FS_OPT_RTS_STRNCMP);
		replace_call(irn, call, mem, NULL, NULL);
		return 1;
	}
	return 0;
972
}
Michael Beck's avatar
Michael Beck committed
973

974
975
int i_mapper_strcpy(ir_node *call, void *ctx)
{
976
977
978
979
980
981
982
983
984
985
986
987
988
989
	ir_node *dst = get_Call_param(call, 0);
	ir_node *src = get_Call_param(call, 1);
	(void) ctx;

	if (dst == src) {
		/* a strcpy(d, s) ==> d */
		ir_node *mem = get_Call_mem(call);
		ir_node *dst = get_Call_param(call, 0);

		DBG_OPT_ALGSIM0(call, dst, FS_OPT_RTS_STRCPY);
		replace_call(dst, call, mem, NULL, NULL);
		return 1;
	}
	return 0;
990
}
991

992
993
int i_mapper_memcpy(ir_node *call, void *ctx)
{
994
995
	ir_node *dst = get_Call_param(call, 0);
	ir_node *src = get_Call_param(call, 1);
996
	ir_node *len = get_Call_param(call, 2);
997
998
	(void) ctx;

999
1000
	if (dst == src || (is_Const(len) && is_Const_null(len))) {
		/* a memcpy(d, d, len) ==> d OR