iropt.c 201 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
 */

Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
/**
 * @file
 * @brief   iropt --- optimizations intertwined with IR construction.
 * @author  Christian Schaefer, Goetz Lindenmaier, Michael Beck
Götz Lindenmaier's avatar
Götz Lindenmaier committed
10
 */
Michael Beck's avatar
Michael Beck committed
11
#include <string.h>
12
#include <stdbool.h>
Boris Boesler's avatar
added    
Boris Boesler committed
13

yb9976's avatar
yb9976 committed
14
#include "constbits.h"
Michael Beck's avatar
Michael Beck committed
15
16
17
18
19
20
21
#include "irnode_t.h"
#include "irgraph_t.h"
#include "iredges_t.h"
#include "irmode_t.h"
#include "iropt_t.h"
#include "ircons_t.h"
#include "irgmod.h"
22
#include "irgopt.h"
23
#include "irverify.h"
24
#include "iroptimize.h"
Michael Beck's avatar
Michael Beck committed
25
26
27
28
29
30
31
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
#include "irhooks.h"
#include "irarch.h"
#include "hashptr.h"
Michael Beck's avatar
Michael Beck committed
32
#include "irtools.h"
33
#include "irhooks.h"
34
#include "array.h"
35
36
#include "vrp.h"
#include "firm_types.h"
37
#include "bitfiddle.h"
38
#include "be.h"
39
#include "error.h"
40
#include "firmstat_t.h"
Christian Schäfer's avatar
Christian Schäfer committed
41

42
#include "entity_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
43

44
45
46
47
48
49
50
51
52
53
54
55
static int imprecise_float_transforms_allowed;

void ir_allow_imprecise_float_transforms(int enable)
{
	imprecise_float_transforms_allowed = enable;
}

int ir_imprecise_float_transforms_allowed(void)
{
	return imprecise_float_transforms_allowed;
}

56
57
/** Returns true if using an Add, Eor or Or instead of @p node would produce
 * the same result. */
58
59
60
static bool is_Or_Eor_Add(const ir_node *node)
{
	if (is_Or(node) || is_Eor(node) || is_Add(node)) {
yb9976's avatar
yb9976 committed
61
62
63
64
65
66
67
68
69
		const ir_node *const left  = get_binop_left(node);
		const ir_node *const right = get_binop_right(node);
		const bitinfo *const bl    = get_bitinfo(left);
		const bitinfo *const br    = get_bitinfo(right);
		/* if each bit is guaranteed to be zero on either the left or right
		 * then an Add will have the same effect as the Eor/Or.
		 */
		if (bl && br && tarval_is_null(tarval_and(bl->z, br->z))) {
			return true;
70
71
72
73
74
		}
	}
	return false;
}

75
76
/** Returns true if using an Add or Eor instead of @p node would produce the
 * same result. */
77
78
static bool is_Eor_Add(const ir_node *node)
{
79
80
	if (is_Or_Eor_Add(node))
		return true;
81
82
	if (!is_Eor(node) && !is_Add(node))
		return false;
83

84
85
86
	const ir_node *right = get_binop_right(node);
	if (!is_Const(right))
		return false;
87

88
89
90
	const ir_mode *mode = get_irn_mode(node);
	if (get_mode_arithmetic(mode) != irma_twos_complement)
		return false;
91

92
93
	ir_tarval *tv = get_Const_tarval(right);
	return get_tarval_lowest_bit(tv) == (int)get_mode_size_bits(mode)-1;
94
95
}

96
97
98
99
100
101
102
103
104
105
106
107
108
/**
 * If node produces a left shift with a constant value return that value.
 * This matches for x << c and x * C2 with C2 being a power of 2.
 */
static ir_tarval *is_shl_const_like(const ir_node *node)
{
	if (is_Shl(node)) {
		ir_node *right = get_Shl_right(node);
		if (is_Const(right))
			return get_Const_tarval(right);
	} else if (is_Mul(node)) {
		ir_node *right = get_Mul_right(node);
		if (is_Const(right)) {
109
			const ir_tarval *tv = get_Const_tarval(right);
110
			/* is value a power of 2? */
111
112
			if (get_tarval_popcount(tv) == 1) {
				int low_bit = get_tarval_lowest_bit(tv);
113
114
115
116
117
118
119
				return new_tarval_from_long(low_bit, get_tarval_mode(tv));
			}
		}
	}
	return NULL;
}

120
/**
121
 * Returns the tarval of a Const node or tarval_unknown for all other nodes.
122
 */
Matthias Braun's avatar
Matthias Braun committed
123
static ir_tarval *default_value_of(const ir_node *n)
124
{
125
	if (is_Const(n))
126
		return get_Const_tarval(n);
127
	else
128
		return tarval_unknown;
129
130
131
132
}

value_of_func value_of_ptr = default_value_of;

133
134
void set_value_of_func(value_of_func func)
{
135
136
137
138
139
140
	if (func != NULL)
		value_of_ptr = func;
	else
		value_of_ptr = default_value_of;
}

141
142
int value_not_null(const ir_node *n, const ir_node **confirm)
{
143
144
	if (confirm)
		*confirm = NULL;
145
146
147
148
149
150
151
152
153

	/* walk confirm sequence and look for matching confirms */
	for (;;) {
		/* -x != 0  =>  x != 0 */
		if (is_Minus(n)) {
			n = get_Minus_op(n);
			continue;
		}
		/* we can ignore Sels: either the base pointer points to null or
yb9976's avatar
yb9976 committed
154
155
		 * if it does not then members addresses cannot be at NULL or we have
		 * undefined behavior because we are obviously not pointing to an
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
		 * object. */
		if (is_Sel(n)) {
			n = get_Sel_ptr(n);
			continue;
		}

		if (!is_Confirm(n))
			break;

		ir_node *bound = get_Confirm_bound(n);
		if (!is_Const(bound)) {
			n = get_Confirm_value(n);
			continue;
		}
		ir_tarval  *tv       = get_Const_tarval(bound);
		ir_mode    *mode     = get_irn_mode(n);
		ir_tarval  *null     = get_mode_null(mode);
		ir_relation relation = tarval_cmp(tv, null);

		switch (get_Confirm_relation(n)) {
		case ir_relation_equal: /* n == C && C != 0 ==> n != 0 */
			if (relation != ir_relation_equal)
				goto confirmed;
			break;
		case ir_relation_less_greater: /* n != C /\ C == 0 ==> n != 0 */
			if (relation == ir_relation_equal)
				goto confirmed;
			break;
		case ir_relation_less: /* n <  C /\ C <= 0 ==> n != 0 */
			if (relation == ir_relation_less || relation == ir_relation_equal)
				goto confirmed;
			break;
		case ir_relation_less_equal: /* n <= C /\ C <  0 ==> n != 0 */
			if (relation == ir_relation_less)
				goto confirmed;
			break;
		case ir_relation_greater_equal: /* n >= C /\ C >  0 ==> n != 0 */
			if (relation == ir_relation_greater)
				goto confirmed;
			break;
		case ir_relation_greater: /* n >  C /\ C >= 0 ==> n != 0 */
			if (relation == ir_relation_greater
			    || relation == ir_relation_equal) {
confirmed:
200
201
				if (confirm)
					*confirm = n;
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
				return true;
			}
			break;
		default:
			break;
		}
		n = get_Confirm_value(n);
	}

	if (is_Const(n)) {
		ir_tarval *tv = get_Const_tarval(n);
		return !tarval_is_null(tv);
	}

	/* global entities are never NULL */
	if (is_Address(n))
		return true;

	/* the frame pointer is never NULL */
	if (is_Proj(n) && is_Start(get_Proj_pred(n))
	    && get_Proj_proj(n) == pn_Start_P_frame_base)
	    return true;

	/* alloc never returns NULL (but throws an exception in the error case) */
	if (is_Alloc(n))
		return true;

229
230
231
232
	const bitinfo *bi = get_bitinfo(n);
	if (bi != NULL && !tarval_is_null(bi->o))
		return true;

233
234
235
236
	/* for all we know the value may be null */
	return false;
}

237
/**
238
 * Return the value of a Constant.
239
 */
Matthias Braun's avatar
Matthias Braun committed
240
static ir_tarval *computed_value_Const(const ir_node *n)
241
{
Michael Beck's avatar
Michael Beck committed
242
	return get_Const_tarval(n);
243
}
Christian Schäfer's avatar
Christian Schäfer committed
244

245
/**
246
 * Return the value of an Offset.
247
 */
248
static ir_tarval *computed_value_Offset(const ir_node *n)
249
{
250
251
252
253
	const ir_entity *ent  = get_Offset_entity(n);
	const ir_type   *type = get_entity_owner(ent);
	if (get_type_state(type) == layout_fixed)
		return new_tarval_from_long(get_entity_offset(ent), get_irn_mode(n));
254
	return tarval_unknown;
255
256
257
}

/**
258
 * Return the value of an Align.
259
 */
260
static ir_tarval *computed_value_Align(const ir_node *n)
261
{
262
263
264
	ir_type *const type = get_Align_type(n);
	if (get_type_state(type) == layout_fixed)
		return new_tarval_from_long(get_type_alignment_bytes(type), get_irn_mode(n));
265
	return tarval_unknown;
266
267
268
269
270
271
272
273
274
275
}

/**
 * Return the value of a Size.
 */
static ir_tarval *computed_value_Size(const ir_node *n)
{
	ir_type *const type = get_Size_type(n);
	if (get_type_state(type) == layout_fixed)
		return new_tarval_from_long(get_type_size_bytes(type), get_irn_mode(n));
276
	return tarval_unknown;
277
}
Christian Schäfer's avatar
Christian Schäfer committed
278

Christoph Mallon's avatar
Christoph Mallon committed
279
280
281
282
283
static bool complement_values(const ir_node *a, const ir_node *b)
{
	if ((is_Not(a) && get_Not_op(a) == b) ||
	    (is_Not(b) && get_Not_op(b) == a))
		return true;
284
285
286
287
	if (is_Eor(a) && is_Eor(b) && get_Eor_left(a) == get_Eor_left(b)) {
		a = get_Eor_right(a);
		b = get_Eor_right(b);
	}
Christoph Mallon's avatar
Christoph Mallon committed
288
289
290
291
292
293
294
295
	if (is_Const(a) && is_Const(b)) {
		ir_tarval *const tv_a = get_Const_tarval(a);
		ir_tarval *const tv_b = get_Const_tarval(b);
		return tarval_is_all_one(tarval_eor(tv_a, tv_b));
	}
	return false;
}

Michael Beck's avatar
Michael Beck committed
296
/**
297
 * Return the value of an Add.
Michael Beck's avatar
Michael Beck committed
298
 */
Matthias Braun's avatar
Matthias Braun committed
299
static ir_tarval *computed_value_Add(const ir_node *n)
300
{
yb9976's avatar
yb9976 committed
301
302
303
304
	const ir_node *a  = get_Add_left(n);
	const ir_node *b  = get_Add_right(n);
	ir_tarval     *ta = value_of(a);
	ir_tarval     *tb = value_of(b);
305

Matthias Braun's avatar
Matthias Braun committed
306
	if (ta != tarval_unknown && tb != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
307
		return tarval_add(ta, tb);
308

309
	/* x+~x => -1 */
Christoph Mallon's avatar
Christoph Mallon committed
310
	if (complement_values(a, b))
311
		return get_mode_all_one(get_irn_mode(n));
Matthias Braun's avatar
Matthias Braun committed
312
313
314
315
316
317
	/* x + -x => 0 */
	if (ir_is_negated_value(a, b)) {
		ir_mode *mode = get_irn_mode(n);
		if (get_mode_arithmetic(mode) == irma_twos_complement)
			return get_mode_null(mode);
	}
318

319
	return tarval_unknown;
320
}
Christian Schäfer's avatar
Christian Schäfer committed
321

Michael Beck's avatar
Michael Beck committed
322
/**
323
 * Return the value of a Sub.
Michael Beck's avatar
Michael Beck committed
324
325
 * Special case: a - a
 */
Matthias Braun's avatar
Matthias Braun committed
326
static ir_tarval *computed_value_Sub(const ir_node *n)
327
{
yb9976's avatar
yb9976 committed
328
329
330
	ir_mode       *mode = get_irn_mode(n);
	const ir_node *a    = get_Sub_left(n);
	const ir_node *b    = get_Sub_right(n);
Christian Schäfer's avatar
Christian Schäfer committed
331

Matthias Braun's avatar
Matthias Braun committed
332
333
334
	/* a - a == 0 (not possible for float because NaN - NaN == NaN */
	if (a == b && get_mode_arithmetic(mode) == irma_twos_complement)
		return get_mode_null(mode);
Michael Beck's avatar
Michael Beck committed
335

yb9976's avatar
yb9976 committed
336
337
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
Matthias Braun's avatar
Matthias Braun committed
338
	if (ta != tarval_unknown && tb != tarval_unknown)
339
		return tarval_sub(ta, tb, mode);
340

341
	return tarval_unknown;
342
}
343

Michael Beck's avatar
Michael Beck committed
344
/**
345
 * Return the value of an unary Minus.
Michael Beck's avatar
Michael Beck committed
346
 */
Matthias Braun's avatar
Matthias Braun committed
347
static ir_tarval *computed_value_Minus(const ir_node *n)
348
{
yb9976's avatar
yb9976 committed
349
350
	const ir_node *a  = get_Minus_op(n);
	ir_tarval     *ta = value_of(a);
351

352
	if (ta != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
353
		return tarval_neg(ta);
354

355
	return tarval_unknown;
356
}
357

Michael Beck's avatar
Michael Beck committed
358
/**
359
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
360
 */
Matthias Braun's avatar
Matthias Braun committed
361
static ir_tarval *computed_value_Mul(const ir_node *n)
362
{
yb9976's avatar
yb9976 committed
363
364
365
366
367
	const ir_node *a    = get_Mul_left(n);
	const ir_node *b    = get_Mul_right(n);
	ir_tarval     *ta   = value_of(a);
	ir_tarval     *tb   = value_of(b);
	ir_mode       *mode = get_irn_mode(n);
Michael Beck's avatar
Michael Beck committed
368

369
	if (ta != tarval_unknown && tb != tarval_unknown) {
Michael Beck's avatar
Michael Beck committed
370
371
		return tarval_mul(ta, tb);
	} else {
372
373
374
		/* a * 0 != 0 if a == NaN or a == Inf */
		if (!mode_is_float(mode)) {
			/* a*0 = 0 or 0*b = 0 */
375
			if (tarval_is_null(ta))
376
				return ta;
377
			if (tarval_is_null(tb))
378
379
				return tb;
		}
Michael Beck's avatar
Michael Beck committed
380
	}
381
	return tarval_unknown;
382
}
383

Michael Beck's avatar
Michael Beck committed
384
/**
385
 * Return the value of an And.
Michael Beck's avatar
Michael Beck committed
386
387
 * Special case: a & 0, 0 & b
 */
Matthias Braun's avatar
Matthias Braun committed
388
static ir_tarval *computed_value_And(const ir_node *n)
389
{
yb9976's avatar
yb9976 committed
390
391
392
393
	const ir_node *a  = get_And_left(n);
	const ir_node *b  = get_And_right(n);
	ir_tarval     *ta = value_of(a);
	ir_tarval     *tb = value_of(b);
Michael Beck's avatar
Michael Beck committed
394

Matthias Braun's avatar
Matthias Braun committed
395
	if (ta != tarval_unknown && tb != tarval_unknown)
yb9976's avatar
yb9976 committed
396
		return tarval_and(ta, tb);
397
398
399
400
401

	if (tarval_is_null(ta)) return ta;
	if (tarval_is_null(tb)) return tb;

	/* x&~x => 0 */
Christoph Mallon's avatar
Christoph Mallon committed
402
	if (complement_values(a, b))
403
404
		return get_mode_null(get_irn_mode(n));

405
	return tarval_unknown;
406
}
407

Michael Beck's avatar
Michael Beck committed
408
/**
409
 * Return the value of an Or.
Michael Beck's avatar
Michael Beck committed
410
411
 * Special case: a | 1...1, 1...1 | b
 */
Matthias Braun's avatar
Matthias Braun committed
412
static ir_tarval *computed_value_Or(const ir_node *n)
413
{
yb9976's avatar
yb9976 committed
414
415
416
417
	const ir_node *a  = get_Or_left(n);
	const ir_node *b  = get_Or_right(n);
	ir_tarval     *ta = value_of(a);
	ir_tarval     *tb = value_of(b);
Michael Beck's avatar
Michael Beck committed
418

Matthias Braun's avatar
Matthias Braun committed
419
	if (ta != tarval_unknown && tb != tarval_unknown)
yb9976's avatar
yb9976 committed
420
		return tarval_or(ta, tb);
421
422
423
424

	if (tarval_is_all_one(ta)) return ta;
	if (tarval_is_all_one(tb)) return tb;

Matthias Braun's avatar
Matthias Braun committed
425
	/* x|~x => ~0 */
Christoph Mallon's avatar
Christoph Mallon committed
426
	if (complement_values(a, b))
427
		return get_mode_all_one(get_irn_mode(n));
Christoph Mallon's avatar
Christoph Mallon committed
428

429
	return tarval_unknown;
430
}
431

Michael Beck's avatar
Michael Beck committed
432
/**
433
 * Return the value of an Eor.
Michael Beck's avatar
Michael Beck committed
434
 */
Matthias Braun's avatar
Matthias Braun committed
435
static ir_tarval *computed_value_Eor(const ir_node *n)
436
{
yb9976's avatar
yb9976 committed
437
438
	const ir_node *a = get_Eor_left(n);
	const ir_node *b = get_Eor_right(n);
Michael Beck's avatar
Michael Beck committed
439

Michael Beck's avatar
Michael Beck committed
440
441
	if (a == b)
		return get_mode_null(get_irn_mode(n));
Matthias Braun's avatar
Matthias Braun committed
442
	/* x^~x => ~0 */
Christoph Mallon's avatar
Christoph Mallon committed
443
	if (complement_values(a, b))
444
		return get_mode_all_one(get_irn_mode(n));
Michael Beck's avatar
Michael Beck committed
445

yb9976's avatar
yb9976 committed
446
447
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
448

Matthias Braun's avatar
Matthias Braun committed
449
	if (ta != tarval_unknown && tb != tarval_unknown)
450
		return tarval_eor(ta, tb);
451
	return tarval_unknown;
452
}
453

Michael Beck's avatar
Michael Beck committed
454
/**
455
 * Return the value of a Not.
Michael Beck's avatar
Michael Beck committed
456
 */
Matthias Braun's avatar
Matthias Braun committed
457
static ir_tarval *computed_value_Not(const ir_node *n)
458
{
yb9976's avatar
yb9976 committed
459
460
	const ir_node *a  = get_Not_op(n);
	ir_tarval     *ta = value_of(a);
461

462
	if (ta != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
463
		return tarval_not(ta);
464

465
	return tarval_unknown;
466
}
467

468
/**
yb9976's avatar
yb9976 committed
469
 * Tests whether a shift shifts more bits than available in the mode
470
471
472
 */
static bool is_oversize_shift(const ir_node *n)
{
yb9976's avatar
yb9976 committed
473
474
475
	const ir_node   *count = get_binop_right(n);
	const ir_mode   *mode  = get_irn_mode(n);
	const ir_tarval *tv    = value_of(count);
476
	if (!tarval_is_constant(tv))
477
478
479
		return false;
	if (!tarval_is_long(tv))
		return false;
yb9976's avatar
yb9976 committed
480
481
	long shiftval     = get_tarval_long(tv);
	long modulo_shift = get_mode_modulo_shift(mode);
482
483
484
485
486
487
	if (shiftval < 0 || (modulo_shift > 0 && shiftval >= modulo_shift))
		return false;

	return shiftval >= (long)get_mode_size_bits(mode);
}

Michael Beck's avatar
Michael Beck committed
488
/**
489
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
490
 */
Matthias Braun's avatar
Matthias Braun committed
491
static ir_tarval *computed_value_Shl(const ir_node *n)
492
{
yb9976's avatar
yb9976 committed
493
494
495
496
	const ir_node *a  = get_Shl_left(n);
	const ir_node *b  = get_Shl_right(n);
	ir_tarval     *ta = value_of(a);
	ir_tarval     *tb = value_of(b);
497

Matthias Braun's avatar
Matthias Braun committed
498
	if (ta != tarval_unknown && tb != tarval_unknown)
499
		return tarval_shl(ta, tb);
500
501
502
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

503
	return tarval_unknown;
504
}
505

Michael Beck's avatar
Michael Beck committed
506
/**
507
 * Return the value of a Shr.
Michael Beck's avatar
Michael Beck committed
508
 */
Matthias Braun's avatar
Matthias Braun committed
509
static ir_tarval *computed_value_Shr(const ir_node *n)
510
{
yb9976's avatar
yb9976 committed
511
512
513
514
	const ir_node *a  = get_Shr_left(n);
	const ir_node *b  = get_Shr_right(n);
	ir_tarval     *ta = value_of(a);
	ir_tarval     *tb = value_of(b);
515

Matthias Braun's avatar
Matthias Braun committed
516
	if (ta != tarval_unknown && tb != tarval_unknown)
517
		return tarval_shr(ta, tb);
518
519
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));
520
	return tarval_unknown;
521
}
522

Michael Beck's avatar
Michael Beck committed
523
/**
524
 * Return the value of a Shrs.
Michael Beck's avatar
Michael Beck committed
525
 */
Matthias Braun's avatar
Matthias Braun committed
526
static ir_tarval *computed_value_Shrs(const ir_node *n)
527
{
yb9976's avatar
yb9976 committed
528
529
530
531
	const ir_node *a  = get_Shrs_left(n);
	const ir_node *b  = get_Shrs_right(n);
	ir_tarval     *ta = value_of(a);
	ir_tarval     *tb = value_of(b);
532

Matthias Braun's avatar
Matthias Braun committed
533
	if (ta != tarval_unknown && tb != tarval_unknown)
534
		return tarval_shrs(ta, tb);
535
	return tarval_unknown;
536
}
537

538
539
bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
{
yb9976's avatar
yb9976 committed
540
	const ir_mode *mode = get_irn_mode(node);
541
542
543
544
	if (get_mode_arithmetic(mode) != irma_twos_complement
	    || get_mode_arithmetic(dest_mode) != irma_twos_complement)
	    return false;

545
546
547
548
549
550
551
	ir_tarval *tv = is_shl_const_like(node);
	if (tv != NULL && tarval_is_long(tv)) {
		long shiftval = get_tarval_long(tv);
		long destbits = get_mode_size_bits(dest_mode);
		if (shiftval >= destbits
			&& shiftval < (long)get_mode_modulo_shift(mode))
			return true;
552
553
554
555
556
557
558
559
560
561
562
563
	}
	if (is_And(node)) {
		ir_node *right = get_And_right(node);
		if (is_Const(right)) {
			ir_tarval *tv     = get_Const_tarval(right);
			ir_tarval *conved = tarval_convert_to(tv, dest_mode);
			return tarval_is_null(conved);
		}
	}
	return false;
}

Michael Beck's avatar
Michael Beck committed
564
/**
565
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
566
 */
Matthias Braun's avatar
Matthias Braun committed
567
static ir_tarval *computed_value_Conv(const ir_node *n)
568
{
yb9976's avatar
yb9976 committed
569
570
571
	const ir_node *a    = get_Conv_op(n);
	ir_tarval     *ta   = value_of(a);
	ir_mode       *mode = get_irn_mode(n);
572

573
	if (ta != tarval_unknown)
yb9976's avatar
yb9976 committed
574
		return tarval_convert_to(ta, mode);
575
576
577
	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

578
	return tarval_unknown;
579
}
580

Michael Beck's avatar
Michael Beck committed
581
582
583
584
/**
 * Calculate the value of a Mux: can be evaluated, if the
 * sel and the right input are known.
 */
Matthias Braun's avatar
Matthias Braun committed
585
static ir_tarval *computed_value_Mux(const ir_node *n)
586
{
yb9976's avatar
yb9976 committed
587
588
	const ir_node   *sel = get_Mux_sel(n);
	const ir_tarval *ts  = value_of(sel);
Michael Beck's avatar
Michael Beck committed
589
590
591
592

	if (ts == get_tarval_b_true()) {
		ir_node *v = get_Mux_true(n);
		return value_of(v);
Matthias Braun's avatar
Matthias Braun committed
593
	} else if (ts == get_tarval_b_false()) {
Michael Beck's avatar
Michael Beck committed
594
595
596
		ir_node *v = get_Mux_false(n);
		return value_of(v);
	}
597
	return tarval_unknown;
598
}
Michael Beck's avatar
Michael Beck committed
599
600
601
602
603

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
Matthias Braun's avatar
Matthias Braun committed
604
static ir_tarval *computed_value_Confirm(const ir_node *n)
605
{
yb9976's avatar
yb9976 committed
606
607
608
609
	const ir_node     *bound    = get_Confirm_bound(n);
	const ir_node     *value    = get_Confirm_value(n);
	const ir_relation  possible = ir_get_possible_cmp_relations(value, bound);
	const ir_relation  relation = get_Confirm_relation(n);
610
611
612

	if ((possible & relation) == ir_relation_equal) {
		ir_tarval *tv = value_of(bound);
613
		if (tarval_is_constant(tv))
614
			return tv;
Michael Beck's avatar
Michael Beck committed
615
	}
616
	return value_of(value);
617
}
Michael Beck's avatar
Michael Beck committed
618

619
/**
620
621
 * gives a (conservative) estimation of possible relation when comparing
 * left+right
622
 */
623
624
ir_relation ir_get_possible_cmp_relations(const ir_node *left,
                                          const ir_node *right)
625
{
yb9976's avatar
yb9976 committed
626
627
628
	ir_relation      possible = ir_relation_true;
	const ir_tarval *tv_l     = value_of(left);
	const ir_tarval *tv_r     = value_of(right);
629

630
	/* both values known - evaluate them */
Matthias Braun's avatar
Matthias Braun committed
631
	if (tv_l != tarval_unknown && tv_r != tarval_unknown) {
632
633
634
635
		possible = tarval_cmp(tv_l, tv_r);
		/* we can return now, won't get any better */
		return possible;
	}
yb9976's avatar
yb9976 committed
636

637
638
639
640
	/* a == a is never less or greater (but might be equal or unordered) */
	if (left == right)
		possible &= ~ir_relation_less_greater;
	/* unordered results only happen for float compares */
yb9976's avatar
yb9976 committed
641
	const ir_mode *mode = get_irn_mode(left);
642
643
644
645
	if (!mode_is_float(mode))
		possible &= ~ir_relation_unordered;
	/* values can never be less than the least representable number or
	 * greater than the greatest representable number */
yb9976's avatar
yb9976 committed
646
647
	ir_tarval       *min = get_mode_min(mode);
	const ir_tarval *max = get_mode_max(mode);
648
649
650
651
652
653
654
655
	if (tv_l == min)
		possible &= ~ir_relation_greater;
	if (tv_l == max)
		possible &= ~ir_relation_less;
	if (tv_r == max)
		possible &= ~ir_relation_greater;
	if (tv_r == min)
		possible &= ~ir_relation_less;
yb9976's avatar
yb9976 committed
656
657
658
659
660
661
662
663
664
665
666

	/* Try to use bit information. */
	const bitinfo *const bl = get_bitinfo(left);
	const bitinfo *const br = get_bitinfo(right);
	if (bl != NULL && br != NULL) {
		ir_tarval *const l_o   = bl->o;
		ir_tarval *const l_z   = bl->z;
		ir_tarval *const r_o   = br->o;
		ir_tarval *const r_z   = br->z;
		if (get_mode_arithmetic(mode) == irma_twos_complement) {
			/* Compute min/max values of operands. */
yb9976's avatar
yb9976 committed
667
			ir_tarval *l_max = tarval_and(l_z, tarval_ornot(l_o, min));
yb9976's avatar
yb9976 committed
668
			ir_tarval *l_min = tarval_or(l_o, tarval_and(l_z, min));
yb9976's avatar
yb9976 committed
669
			ir_tarval *r_max = tarval_and(r_z, tarval_ornot(r_o, min));
yb9976's avatar
yb9976 committed
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
			ir_tarval *r_min = tarval_or(r_o, tarval_and(r_z, min));

			if (!(tarval_cmp(l_max, r_min) & ir_relation_greater)) {
				possible &= ~ir_relation_greater;
			}
			if (!(tarval_cmp(l_min, r_max) & ir_relation_less)) {
				possible &= ~ir_relation_less;
			}
		}

		if (!tarval_is_null(tarval_andnot(l_o, r_z))
		    || !tarval_is_null(tarval_andnot(r_o, l_z))) {
			possible &= ~ir_relation_equal;
		}
	}

686
687
688
689
690
	/* maybe vrp can tell us more */
	possible &= vrp_cmp(left, right);
	/* Alloc nodes never return null (but throw an exception) */
	if (is_Alloc(left) && tarval_is_null(tv_r))
		possible &= ~ir_relation_equal;
691
692
693
694
695
696
697
698
699
	/* stuff known through confirm nodes */
	if (is_Confirm(left) && get_Confirm_bound(left) == right) {
		possible &= get_Confirm_relation(left);
	}
	if (is_Confirm(right) && get_Confirm_bound(right) == left) {
		ir_relation relation = get_Confirm_relation(right);
		relation = get_inversed_relation(relation);
		possible &= relation;
	}
700
701
702

	return possible;
}
703

704
static ir_tarval *compute_cmp(const ir_node *cmp)
705
{
yb9976's avatar
yb9976 committed
706
707
708
709
	ir_node     *left     = get_Cmp_left(cmp);
	ir_node     *right    = get_Cmp_right(cmp);
	ir_relation  possible = ir_get_possible_cmp_relations(left, right);
	ir_relation  relation = get_Cmp_relation(cmp);
710
711
712
713
714
715
716
717

	/* if none of the requested relations is possible, return false */
	if ((possible & relation) == ir_relation_false)
		return tarval_b_false;
	/* if possible relations are a subset of the requested ones return true */
	if ((possible & ~relation) == ir_relation_false)
		return tarval_b_true;

718
719
720
721
722
	/* we have some special rules for == 0 and != 0 */
	if ((relation == ir_relation_equal
		 || relation == ir_relation_less_greater
		 || (relation == ir_relation_greater && !mode_is_signed(get_irn_mode(left)))) &&
		is_Const(right) && is_Const_null(right)) {
723
		if (value_not_null(left, NULL)) {
724
725
726
727
728
			return relation == ir_relation_equal
			     ? tarval_b_false : tarval_b_true;
		}
	}

729
730
	return computed_value_Cmp_Confirm(cmp, left, right, relation);
}
731

732
733
734
735
736
737
738
/**
 * some people want to call compute_cmp directly, in this case we have to
 * test the constant folding flag again
 */
static ir_tarval *compute_cmp_ext(const ir_node *cmp)
{
	if (!get_opt_constant_folding())
739
		return tarval_unknown;
740
741
742
	return compute_cmp(cmp);
}

743
744
745
746
747
748
749
750
751
/**
 * Return the value of a Cmp.
 *
 * The basic idea here is to determine which relations are possible and which
 * one are definitely impossible.
 */
static ir_tarval *computed_value_Cmp(const ir_node *cmp)
{
	/* we can't construct Constb after lowering mode_b nodes */
752
	if (irg_is_constrained(get_irn_irg(cmp), IR_GRAPH_CONSTRAINT_MODEB_LOWERED))
753
		return tarval_unknown;
754
755
756
757

	return compute_cmp(cmp);
}

758
/**
Michael Beck's avatar
Michael Beck committed
759
 * Calculate the value of an integer Div.
760
761
 * Special case: 0 / b
 */
762
static ir_tarval *do_computed_value_Div(const ir_node *a, const ir_node *b)
763
{
764
	ir_tarval *ta = value_of(a);
765

Michael Beck's avatar
Michael Beck committed
766
	/* cannot optimize 0 / b = 0 because of NaN */
767
768
769
	if (tarval_is_null(ta)) {
		ir_mode *mode = get_irn_mode(a);
		if (get_mode_arithmetic(mode) == irma_twos_complement
770
		    && value_not_null(b, NULL)) {
Michael Beck's avatar
Michael Beck committed
771
			return ta;  /* 0 / b == 0 if b != 0 */
772
773
774
775
776
777
778
		}
	}
	if (a == b) {
		ir_mode *mode = get_irn_mode(a);
		/* a/a => 1 */
		if (get_mode_arithmetic(mode) == irma_twos_complement)
			return get_mode_one(mode);
779
	}
yb9976's avatar
yb9976 committed
780
	ir_tarval *tb = value_of(b);
781
	if (ta != tarval_unknown && tb != tarval_unknown)
782
		return tarval_div(ta, tb);
783
	return tarval_unknown;
784
}
Michael Beck's avatar
Michael Beck committed
785

786
787
788
789
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
790
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
791
{
Matthias Braun's avatar
Matthias Braun committed
792
	ir_tarval *tb = value_of(b);
793
794
795
	/* Compute a % 1 or c1 % c2 */
	if (tarval_is_one(tb))
		return get_mode_null(get_irn_mode(a));
796

yb9976's avatar
yb9976 committed
797
	ir_tarval *ta = value_of(a);
798
799
800
	/* 0 % b == 0 if b != 0 */
	if (tarval_is_null(ta)) {
		assert(get_mode_arithmetic(get_irn_mode(a)) == irma_twos_complement);
801
		if (value_not_null(b, NULL))
802
803
			return ta;
	}
804
	if (ta != tarval_unknown && tb != tarval_unknown)
805
		return tarval_mod(ta, tb);
806
	return tarval_unknown;
807
}
808

Michael Beck's avatar
Michael Beck committed
809
810
811
/**
 * Return the value of a Proj(Div).
 */
Matthias Braun's avatar
Matthias Braun committed
812
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
813
{
Michael Beck's avatar
Michael Beck committed
814
	long proj_nr = get_Proj_proj(n);
815
	if (proj_nr != pn_Div_res)
816
		return tarval_unknown;
Michael Beck's avatar
Michael Beck committed
817

818
819
820
821
	const ir_node *div   = get_Proj_pred(n);
	const ir_node *left  = get_Div_left(div);
	const ir_node *right = get_Div_right(div);
	return do_computed_value_Div(left, right);
822
}
823

824
/**
Michael Beck's avatar
Michael Beck committed
825
 * Return the value of a Proj(Mod).
826
 */
Matthias Braun's avatar
Matthias Braun committed
827
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
828
{
Michael Beck's avatar
Michael Beck committed
829
	long proj_nr = get_Proj_proj(n);
Michael Beck's avatar
Michael Beck committed
830

Michael Beck's avatar
Michael Beck committed
831
	if (proj_nr == pn_Mod_res) {
Michael Beck's avatar
Michael Beck committed
832
833
		const ir_node *mod = get_Proj_pred(n);
		return do_computed_value_Mod(get_Mod_left(mod), get_Mod_right(mod));
Michael Beck's avatar
Michael Beck committed
834
	}
835
	return tarval_unknown;
836
}
837

Michael Beck's avatar
Michael Beck committed
838
/**
Michael Beck's avatar
Michael Beck committed
839
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
840
 */
Matthias Braun's avatar
Matthias Braun committed
841
static ir_tarval *computed_value_Proj(const ir_node *proj)
842
{
yb9976's avatar
yb9976 committed
843
	const ir_node *n = get_Proj_pred(proj);
Michael Beck's avatar
Michael Beck committed
844
845
846

	if (n->op->ops.computed_value_Proj != NULL)
		return n->op->ops.computed_value_Proj(proj);
847
	return tarval_unknown;
848
}
Michael Beck's avatar
Michael Beck committed
849

850
/**
851
 * If the parameter n can be computed, return its value, else tarval_unknown.
852
 * Performs constant folding.
853
854
 *
 * @param n  The node this should be evaluated
855
 */
Matthias Braun's avatar
Matthias Braun committed
856
ir_tarval *computed_value(const ir_node *n)
857
{
yb9976's avatar
yb9976 committed
858
	const vrp_attr *vrp = vrp_get_info(n);
859
	if (vrp != NULL && vrp->bits_set == vrp->bits_not_set)
860
		return vrp->bits_set;
861

Michael Beck's avatar
Michael Beck committed
862
863
	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
864
	return tarval_unknown;
865
}
Christian Schäfer's avatar
Christian Schäfer committed
866

867
/**
868
 * Optimize operations that are commutative and have neutral 0,
869
 * so a op 0 = 0 op a = a.
870
 */
871
872
static ir_node *equivalent_node_neutral_zero(ir_node *n)
{
yb9976's avatar
yb9976 committed
873
874
875
876
877
	ir_node         *oldn = n;
	ir_node         *a    = get_binop_left(n);
	ir_node         *b    = get_binop_right(n);
	const ir_tarval *tv;
	ir_node         *on;
Michael Beck's avatar
Michael Beck committed
878
879
880

	/* After running compute_node there is only one constant predecessor.
	   Find this predecessors value and remember the other node: */
881
	if (tarval_is_constant( (tv = value_of(a)) )) {
Michael Beck's avatar
Michael Beck committed
882
		on = b;
883
	} else if (tarval_is_constant( (tv = value_of(b)) )) {
Michael Beck's avatar
Michael Beck committed
884
885
886
887
888
889
890
891
892
893
894
		on = a;
	} else
		return n;

	/* If this predecessors constant value is zero, the operation is
	 * unnecessary. Remove it.
	 *
	 * Beware: If n is a Add, the mode of on and n might be different
	 * which happens in this rare construction: NULL + 3.
	 * Then, a Conv would be needed which we cannot include here.
	 */
895
896
	if (tarval_is_null(tv) && get_irn_mode(on) == get_irn_mode(n)) {
		n = on;
Michael Beck's avatar
Michael Beck committed
897

898
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
Michael Beck's avatar
Michael Beck committed
899
900
901
	}

	return n;
902
}
903

904
905
906
907
908
909
910
911
912
913
914
915
static ir_node *get_commutative_other_op(ir_node *const node, ir_node *const op)
{
	assert(is_op_commutative(get_irn_op(node)));
	ir_node *const l = get_binop_left(node);
	ir_node *const r = get_binop_right(node);
	if (l == op)
		return r;
	if (r == op)
		return l;
	return NULL;
}

916
917
918
/**
 * Eor is commutative and has neutral 0.
 */
919
920
static ir_node *equivalent_node_Eor(ir_node *n)
{
921
922
923
924
925
	ir_node *oldn = n;

	n = equivalent_node_neutral_zero(n);
	if (n != oldn) return n;

yb9976's avatar
yb9976 committed
926
927
	ir_node *a = get_Eor_left(n);
	ir_node *b = get_Eor_right(n);
928

929
930