iropt.c 235 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
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
#include "irhooks.h"
30
#include "irarch_t.h"
Michael Beck's avatar
Michael Beck committed
31
#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"
Matthias Braun's avatar
Matthias Braun committed
39
#include "panic.h"
Christian Schäfer's avatar
Christian Schäfer committed
40

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

43
44
45
46
47
48
49
50
51
52
53
54
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;
}

55
56
/** Returns true if using an Add, Eor or Or instead of @p node would produce
 * the same result. */
57
58
59
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
60
61
62
63
64
65
66
67
68
		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;
69
70
71
72
73
		}
	}
	return false;
}

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

83
84
85
	const ir_mode *mode = get_irn_mode(node);
	if (get_mode_arithmetic(mode) != irma_twos_complement)
		return false;
86

87
88
89
90
91
92
93
94
	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);
	const int            highest_bit = (int)get_mode_size_bits(mode) - 1;

	return (bl && get_tarval_lowest_bit(bl->z) == highest_bit) ||
	       (br && get_tarval_lowest_bit(br->z) == highest_bit);
95
96
}

97
98
99
100
101
102
103
104
105
106
107
108
109
/**
 * 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)) {
110
			const ir_tarval *tv = get_Const_tarval(right);
111
			/* is value a power of 2? */
112
113
			if (get_tarval_popcount(tv) == 1) {
				int low_bit = get_tarval_lowest_bit(tv);
114
115
116
117
118
119
120
				return new_tarval_from_long(low_bit, get_tarval_mode(tv));
			}
		}
	}
	return NULL;
}

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

value_of_func value_of_ptr = default_value_of;

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

142
143
int value_not_null(const ir_node *n, const ir_node **confirm)
{
144
145
	if (confirm)
		*confirm = NULL;
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;
		}
154
		/* we can ignore Sels/Members: either the base pointer points to null or
yb9976's avatar
yb9976 committed
155
156
		 * if it does not then members addresses cannot be at NULL or we have
		 * undefined behavior because we are obviously not pointing to an
157
158
159
160
		 * object. */
		if (is_Sel(n)) {
			n = get_Sel_ptr(n);
			continue;
161
162
163
		} else if (is_Member(n)) {
			n = get_Member_ptr(n);
			continue;
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
200
201
202
203
		}

		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:
204
205
				if (confirm)
					*confirm = n;
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
				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))
226
	    && get_Proj_num(n) == pn_Start_P_frame_base)
227
228
229
230
231
232
	    return true;

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

233
234
235
236
	const bitinfo *bi = get_bitinfo(n);
	if (bi != NULL && !tarval_is_null(bi->o))
		return true;

237
238
239
240
	/* for all we know the value may be null */
	return false;
}

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

249
/**
250
 * Return the value of an Offset.
251
 */
252
static ir_tarval *computed_value_Offset(const ir_node *n)
253
{
254
255
256
257
	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));
258
	return tarval_unknown;
259
260
261
}

/**
262
 * Return the value of an Align.
263
 */
264
static ir_tarval *computed_value_Align(const ir_node *n)
265
{
266
267
268
	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));
269
	return tarval_unknown;
270
271
272
273
274
275
276
277
278
279
}

/**
 * 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));
280
	return tarval_unknown;
281
}
Christian Schäfer's avatar
Christian Schäfer committed
282

Christoph Mallon's avatar
Christoph Mallon committed
283
284
static bool complement_values(const ir_node *a, const ir_node *b)
{
285
286
287
288
	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);
	}
289
290
291
	if ((is_Not(a) && get_Not_op(a) == b) ||
	    (is_Not(b) && get_Not_op(b) == a))
		return true;
Christoph Mallon's avatar
Christoph Mallon committed
292
293
294
295
296
297
298
299
	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
300
/**
301
 * Return the value of an Add.
Michael Beck's avatar
Michael Beck committed
302
 */
Matthias Braun's avatar
Matthias Braun committed
303
static ir_tarval *computed_value_Add(const ir_node *n)
304
{
yb9976's avatar
yb9976 committed
305
306
307
308
	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);
309

Matthias Braun's avatar
Matthias Braun committed
310
	if (ta != tarval_unknown && tb != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
311
		return tarval_add(ta, tb);
312

313
	/* x+~x => -1 */
Christoph Mallon's avatar
Christoph Mallon committed
314
	if (complement_values(a, b))
315
		return get_mode_all_one(get_irn_mode(n));
Matthias Braun's avatar
Matthias Braun committed
316
317
318
319
320
321
	/* 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);
	}
322

323
	return tarval_unknown;
324
}
Christian Schäfer's avatar
Christian Schäfer committed
325

Michael Beck's avatar
Michael Beck committed
326
/**
327
 * Return the value of a Sub.
Michael Beck's avatar
Michael Beck committed
328
329
 * Special case: a - a
 */
Matthias Braun's avatar
Matthias Braun committed
330
static ir_tarval *computed_value_Sub(const ir_node *n)
331
{
yb9976's avatar
yb9976 committed
332
333
334
	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
335

Matthias Braun's avatar
Matthias Braun committed
336
	/* a - a == 0 (not possible for float because NaN - NaN == NaN */
337
338
339
340
341
342
343
	if (get_mode_arithmetic(mode) == irma_twos_complement &&
	    (a == b ||
	     (is_Confirm(a) && is_Confirm(b) &&
	      get_Confirm_relation(a) == ir_relation_equal &&
	      get_Confirm_relation(b) == ir_relation_equal &&
	      get_Confirm_bound(a) == get_Confirm_value(b) &&
	      get_Confirm_bound(b) == get_Confirm_value(a)))) {
Matthias Braun's avatar
Matthias Braun committed
344
		return get_mode_null(mode);
345
	}
Michael Beck's avatar
Michael Beck committed
346

yb9976's avatar
yb9976 committed
347
348
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
Matthias Braun's avatar
Matthias Braun committed
349
	if (ta != tarval_unknown && tb != tarval_unknown)
350
		return tarval_sub(ta, tb, mode);
351

352
	return tarval_unknown;
353
}
354

Michael Beck's avatar
Michael Beck committed
355
/**
356
 * Return the value of an unary Minus.
Michael Beck's avatar
Michael Beck committed
357
 */
Matthias Braun's avatar
Matthias Braun committed
358
static ir_tarval *computed_value_Minus(const ir_node *n)
359
{
yb9976's avatar
yb9976 committed
360
361
	const ir_node *a  = get_Minus_op(n);
	ir_tarval     *ta = value_of(a);
362

363
	if (ta != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
364
		return tarval_neg(ta);
365

366
	return tarval_unknown;
367
}
368

Michael Beck's avatar
Michael Beck committed
369
/**
370
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
371
 */
Matthias Braun's avatar
Matthias Braun committed
372
static ir_tarval *computed_value_Mul(const ir_node *n)
373
{
yb9976's avatar
yb9976 committed
374
375
376
377
378
	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
379

380
	if (ta != tarval_unknown && tb != tarval_unknown) {
Michael Beck's avatar
Michael Beck committed
381
382
		return tarval_mul(ta, tb);
	} else {
383
384
385
		/* a * 0 != 0 if a == NaN or a == Inf */
		if (!mode_is_float(mode)) {
			/* a*0 = 0 or 0*b = 0 */
386
			if (tarval_is_null(ta))
387
				return ta;
388
			if (tarval_is_null(tb))
389
390
				return tb;
		}
Michael Beck's avatar
Michael Beck committed
391
	}
392
	return tarval_unknown;
393
}
394

Michael Beck's avatar
Michael Beck committed
395
/**
396
 * Return the value of an And.
Michael Beck's avatar
Michael Beck committed
397
398
 * Special case: a & 0, 0 & b
 */
Matthias Braun's avatar
Matthias Braun committed
399
static ir_tarval *computed_value_And(const ir_node *n)
400
{
yb9976's avatar
yb9976 committed
401
402
403
404
	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
405

Matthias Braun's avatar
Matthias Braun committed
406
	if (ta != tarval_unknown && tb != tarval_unknown)
yb9976's avatar
yb9976 committed
407
		return tarval_and(ta, tb);
408
409
410
411
412

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

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

416
	return tarval_unknown;
417
}
418

Michael Beck's avatar
Michael Beck committed
419
/**
420
 * Return the value of an Or.
Michael Beck's avatar
Michael Beck committed
421
422
 * Special case: a | 1...1, 1...1 | b
 */
Matthias Braun's avatar
Matthias Braun committed
423
static ir_tarval *computed_value_Or(const ir_node *n)
424
{
yb9976's avatar
yb9976 committed
425
426
427
428
	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
429

Matthias Braun's avatar
Matthias Braun committed
430
	if (ta != tarval_unknown && tb != tarval_unknown)
yb9976's avatar
yb9976 committed
431
		return tarval_or(ta, tb);
432
433
434
435

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

Matthias Braun's avatar
Matthias Braun committed
436
	/* x|~x => ~0 */
Christoph Mallon's avatar
Christoph Mallon committed
437
	if (complement_values(a, b))
438
		return get_mode_all_one(get_irn_mode(n));
Christoph Mallon's avatar
Christoph Mallon committed
439

440
	return tarval_unknown;
441
}
442

Michael Beck's avatar
Michael Beck committed
443
/**
444
 * Return the value of an Eor.
Michael Beck's avatar
Michael Beck committed
445
 */
Matthias Braun's avatar
Matthias Braun committed
446
static ir_tarval *computed_value_Eor(const ir_node *n)
447
{
yb9976's avatar
yb9976 committed
448
449
	const ir_node *a = get_Eor_left(n);
	const ir_node *b = get_Eor_right(n);
Michael Beck's avatar
Michael Beck committed
450

451
452
453
454
455
456
457
	/* a ^ a == 0 */
	if (a == b ||
	    (is_Confirm(a) && is_Confirm(b) &&
	     get_Confirm_relation(a) == ir_relation_equal &&
	     get_Confirm_relation(b) == ir_relation_equal &&
	     get_Confirm_bound(a) == get_Confirm_value(b) &&
	     get_Confirm_bound(b) == get_Confirm_value(a))) {
Michael Beck's avatar
Michael Beck committed
458
		return get_mode_null(get_irn_mode(n));
459
460
	}

Matthias Braun's avatar
Matthias Braun committed
461
	/* x^~x => ~0 */
Christoph Mallon's avatar
Christoph Mallon committed
462
	if (complement_values(a, b))
463
		return get_mode_all_one(get_irn_mode(n));
Michael Beck's avatar
Michael Beck committed
464

yb9976's avatar
yb9976 committed
465
466
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
467

Matthias Braun's avatar
Matthias Braun committed
468
	if (ta != tarval_unknown && tb != tarval_unknown)
469
		return tarval_eor(ta, tb);
470
	return tarval_unknown;
471
}
472

Michael Beck's avatar
Michael Beck committed
473
/**
474
 * Return the value of a Not.
Michael Beck's avatar
Michael Beck committed
475
 */
Matthias Braun's avatar
Matthias Braun committed
476
static ir_tarval *computed_value_Not(const ir_node *n)
477
{
yb9976's avatar
yb9976 committed
478
479
	const ir_node *a  = get_Not_op(n);
	ir_tarval     *ta = value_of(a);
480

481
	if (ta != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
482
		return tarval_not(ta);
483

484
	return tarval_unknown;
485
}
486

487
/**
yb9976's avatar
yb9976 committed
488
 * Tests whether a shift shifts more bits than available in the mode
489
490
491
 */
static bool is_oversize_shift(const ir_node *n)
{
492
493
	const ir_node *count = get_binop_right(n);
	ir_tarval     *tv    = value_of(count);
494
	if (!tarval_is_constant(tv))
495
		return false;
496
497
498
499
500
501
502
503
504
505
	/* adjust for modulo shift */
	ir_mode *mode         = get_irn_mode(n);
	unsigned modulo_shift = get_mode_modulo_shift(mode);
	if (modulo_shift > 0) {
		if (modulo_shift <= get_mode_size_bits(mode))
			return false;
		ir_tarval *modulo_shift_val
			= new_tarval_from_long(modulo_shift, get_tarval_mode(tv));
		tv = tarval_mod(tv, modulo_shift_val);
	}
506
507
508
	if (!tarval_is_long(tv))
		return false;

509
510
	long shiftval = get_tarval_long(tv);
	return shiftval < 0 || shiftval >= (long)get_mode_size_bits(mode);
511
512
}

Michael Beck's avatar
Michael Beck committed
513
/**
514
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
515
 */
Matthias Braun's avatar
Matthias Braun committed
516
static ir_tarval *computed_value_Shl(const ir_node *n)
517
{
yb9976's avatar
yb9976 committed
518
519
520
521
	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);
522

Matthias Braun's avatar
Matthias Braun committed
523
	if (ta != tarval_unknown && tb != tarval_unknown)
524
		return tarval_shl(ta, tb);
525
526
527
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

528
	return tarval_unknown;
529
}
530

Michael Beck's avatar
Michael Beck committed
531
/**
532
 * Return the value of a Shr.
Michael Beck's avatar
Michael Beck committed
533
 */
Matthias Braun's avatar
Matthias Braun committed
534
static ir_tarval *computed_value_Shr(const ir_node *n)
535
{
yb9976's avatar
yb9976 committed
536
537
538
539
	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);
540

Matthias Braun's avatar
Matthias Braun committed
541
	if (ta != tarval_unknown && tb != tarval_unknown)
542
		return tarval_shr(ta, tb);
543
544
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));
545
	return tarval_unknown;
546
}
547

Michael Beck's avatar
Michael Beck committed
548
/**
549
 * Return the value of a Shrs.
Michael Beck's avatar
Michael Beck committed
550
 */
Matthias Braun's avatar
Matthias Braun committed
551
static ir_tarval *computed_value_Shrs(const ir_node *n)
552
{
yb9976's avatar
yb9976 committed
553
554
555
556
	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);
557

Matthias Braun's avatar
Matthias Braun committed
558
	if (ta != tarval_unknown && tb != tarval_unknown)
559
		return tarval_shrs(ta, tb);
560
	return tarval_unknown;
561
}
562

563
564
bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
{
yb9976's avatar
yb9976 committed
565
	const ir_mode *mode = get_irn_mode(node);
566
567
568
569
	if (get_mode_arithmetic(mode) != irma_twos_complement
	    || get_mode_arithmetic(dest_mode) != irma_twos_complement)
	    return false;

570
571
572
573
574
575
576
	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;
577
578
579
580
581
582
583
584
585
586
587
588
	}
	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
589
/**
590
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
591
 */
Matthias Braun's avatar
Matthias Braun committed
592
static ir_tarval *computed_value_Conv(const ir_node *n)
593
{
yb9976's avatar
yb9976 committed
594
595
596
	const ir_node *a    = get_Conv_op(n);
	ir_tarval     *ta   = value_of(a);
	ir_mode       *mode = get_irn_mode(n);
597

598
	if (ta != tarval_unknown)
yb9976's avatar
yb9976 committed
599
		return tarval_convert_to(ta, mode);
600
601
602
	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

603
	return tarval_unknown;
604
}
605

606
607
608
609
610
611
612
613
614
615
616
static ir_tarval *computed_value_Bitcast(const ir_node *n)
{
	const ir_node *op = get_Bitcast_op(n);
	ir_tarval     *ta = value_of(op);
	if (ta == tarval_unknown)
		return tarval_unknown;

	ir_mode *mode = get_irn_mode(n);
	return tarval_bitcast(ta, mode);
}

Michael Beck's avatar
Michael Beck committed
617
618
619
620
/**
 * 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
621
static ir_tarval *computed_value_Mux(const ir_node *n)
622
{
yb9976's avatar
yb9976 committed
623
624
	const ir_node   *sel = get_Mux_sel(n);
	const ir_tarval *ts  = value_of(sel);
Michael Beck's avatar
Michael Beck committed
625
626
627
628

	if (ts == get_tarval_b_true()) {
		ir_node *v = get_Mux_true(n);
		return value_of(v);
Matthias Braun's avatar
Matthias Braun committed
629
	} else if (ts == get_tarval_b_false()) {
Michael Beck's avatar
Michael Beck committed
630
631
632
		ir_node *v = get_Mux_false(n);
		return value_of(v);
	}
633
	return tarval_unknown;
634
}
Michael Beck's avatar
Michael Beck committed
635
636
637
638
639

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
Matthias Braun's avatar
Matthias Braun committed
640
static ir_tarval *computed_value_Confirm(const ir_node *n)
641
{
yb9976's avatar
yb9976 committed
642
643
644
645
	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);
646

647
648
649
650
651
	switch (possible & relation) {
	case ir_relation_false:
		return tarval_bad;

	case ir_relation_equal: {
652
		ir_tarval *tv = value_of(bound);
653
		if (tarval_is_constant(tv))
654
			return tv;
655
656
		break;
	}
Michael Beck's avatar
Michael Beck committed
657
	}
658

659
	return value_of(value);
660
}
Michael Beck's avatar
Michael Beck committed
661

662
663
664
665
666
667
668
669
670
671
672
673
static ir_node *get_commutative_other_op(const ir_node *const node, const 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;
}

674
/**
675
676
 * gives a (conservative) estimation of possible relation when comparing
 * left+right
677
 */
678
679
ir_relation ir_get_possible_cmp_relations(const ir_node *left,
                                          const ir_node *right)
680
{
yb9976's avatar
yb9976 committed
681
682
683
	ir_relation      possible = ir_relation_true;
	const ir_tarval *tv_l     = value_of(left);
	const ir_tarval *tv_r     = value_of(right);
684

685
	/* both values known - evaluate them */
Matthias Braun's avatar
Matthias Braun committed
686
	if (tv_l != tarval_unknown && tv_r != tarval_unknown) {
687
688
689
690
		possible = tarval_cmp(tv_l, tv_r);
		/* we can return now, won't get any better */
		return possible;
	}
yb9976's avatar
yb9976 committed
691

692
693
694
695
696
	/* NaN never compares successfully to anything */
	if (tarval_is_nan(tv_l) || tarval_is_nan(tv_r)) {
		return ir_relation_unordered;
	}

697
698
699
700
	/* 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
701
	const ir_mode *mode = get_irn_mode(left);
702
703
704
705
	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
706
707
	ir_tarval       *min = get_mode_min(mode);
	const ir_tarval *max = get_mode_max(mode);
708
709
710
711
712
713
714
715
	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
716
717
718
719
720
721
722
723
724
725
726

	/* 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
727
			ir_tarval *l_max = tarval_and(l_z, tarval_ornot(l_o, min));
yb9976's avatar
yb9976 committed
728
			ir_tarval *l_min = tarval_or(l_o, tarval_and(l_z, min));
yb9976's avatar
yb9976 committed
729
			ir_tarval *r_max = tarval_and(r_z, tarval_ornot(r_o, min));
yb9976's avatar
yb9976 committed
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
			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;
		}
	}

746
747
748
749
750
	/* 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;
751
752
753
754
	if (is_And(left) && !mode_is_signed(mode) && get_commutative_other_op(left, right))
		possible &= ~ir_relation_greater;
	if (is_And(right) && !mode_is_signed(mode) && get_commutative_other_op(right, left))
		possible &= ~ir_relation_less;
755
756
757
758
759
760
761
762
763
	/* 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;
	}
764
765
766

	return possible;
}
767

yb9976's avatar
yb9976 committed
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
/**
 * Checks whether we can use @p relation instead of @p cmp_relation,
 * if only some relations are @p possible.
 *
 * @param relation      The relation to check for
 * @param cmp_relation  The current relation of the Cmp
 * @param possible      The possible relations of the Cmp
 */
static bool is_relation(ir_relation relation, ir_relation cmp_relation, ir_relation possible)
{
	ir_relation min           = cmp_relation & possible;
	ir_relation possible_bits = relation & ~possible;

	return (min | possible_bits) == relation;
}

784
785
/**
 * Check whether we can use @p relation or its ordered complement instead of @p
yb9976's avatar
yb9976 committed
786
 * cmp_relation, if only some relations are @p possible.
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
 *
 * @param relation      The relation to check for
 * @param cmp_relation  The current relation of the Cmp
 * @param possible      The possible relations of the Cmp
 * @return The replacement relation or ir_relation_false, if neither is
 *         possible.
 */
static ir_relation get_complementary_relations(ir_relation const relation, ir_relation const cmp_relation, ir_relation const possible)
{
	assert(possible != ir_relation_false);
	if (is_relation(relation, cmp_relation, possible))
		return relation;
	ir_relation const compl = relation ^ ir_relation_less_equal_greater;
	if (is_relation(compl, cmp_relation, possible))
		return compl;
	return ir_relation_false;
}

805
806
807
808
809
810
811
/**
 * 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)
812
{
yb9976's avatar
yb9976 committed
813
814
815
816
	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);
817
818
819
820
821
822
823
824

	/* 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;

825
	/* we have some special rules for == 0 and != 0 */
826
827
828
	ir_relation const rel_eq = get_complementary_relations(ir_relation_equal, relation, possible);
	if (rel_eq != ir_relation_false && is_Const(right) && is_Const_null(right) && value_not_null(left, NULL))
		return rel_eq != ir_relation_equal ? tarval_b_true : tarval_b_false;
829

Matthias Braun's avatar
Matthias Braun committed
830
	return computed_value_Cmp_Confirm(left, right, relation);
831
}
832

833
834
835
836
837
838
839
/**
 * 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())
840
		return tarval_unknown;
841
	return computed_value_Cmp(cmp);
842
843
}

844
/**
Michael Beck's avatar
Michael Beck committed
845
 * Calculate the value of an integer Div.
846
847
 * Special case: 0 / b
 */
848
static ir_tarval *do_computed_value_Div(const ir_node *a, const ir_node *b)
849
{
850
	ir_tarval *ta = value_of(a);
851

Michael Beck's avatar
Michael Beck committed
852
	/* cannot optimize 0 / b = 0 because of NaN */
853
854
855
	if (tarval_is_null(ta)) {
		ir_mode *mode = get_irn_mode(a);
		if (get_mode_arithmetic(mode) == irma_twos_complement
856
		    && value_not_null(b, NULL)) {
Michael Beck's avatar
Michael Beck committed
857
			return ta;  /* 0 / b == 0 if b != 0 */
858
859
860
861
862
863
864
		}
	}
	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);
865
	}
yb9976's avatar
yb9976 committed
866
	ir_tarval *tb = value_of(b);
867
	if (ta != tarval_unknown && tb != tarval_unknown)
868
		return tarval_div(ta, tb);
869
	return tarval_unknown;
870
}
Michael Beck's avatar
Michael Beck committed
871

872
873
874
875
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
876
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
877
{
Matthias Braun's avatar
Matthias Braun committed
878
	ir_tarval *tb = value_of(b);
879
880
881
882
883
884
	/* a % 1 == 0 */
	/* a % -1 == 0 */
	ir_mode *mode = get_irn_mode(a);
	if (tarval_is_one(tb)
	    || (mode_is_signed(mode) && tarval_is_all_one(tb)))
		return get_mode_null(mode);
885

886
	/* constant folding */
yb9976's avatar
yb9976 committed
887
	ir_tarval *ta = value_of(a);
888
889
890
	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_mod(ta, tb);

891
	/* 0 % b == 0 if b != 0 */
892
893
894
	/* a % a == 0 if a != 0 */
	if (tarval_is_null(ta) || a == b) {
		assert(get_mode_arithmetic(mode) == irma_twos_complement);
895
		if (value_not_null(b, NULL))
896
			return get_mode_null(mode);
897
	}
898

899
	return tarval_unknown;
900
}
901

Michael Beck's avatar
Michael Beck committed
902
903
904
/**
 * Return the value of a Proj(Div).
 */
Matthias Braun's avatar
Matthias Braun committed
905
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
906
{
907
	unsigned proj_nr = get_Proj_num(n);
908
	if (proj_nr != pn_Div_res)
909
		return tarval_unknown;
Michael Beck's avatar
Michael Beck committed
910

911
912
913
914
	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);
915
}
916

917
/**
Michael Beck's avatar
Michael Beck committed
918
 * Return the value of a Proj(Mod).
919
 */
Matthias Braun's avatar
Matthias Braun committed
920
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
921
{
922
	unsigned proj_nr = get_Proj_num(n);
Michael Beck's avatar
Michael Beck committed
923

Michael Beck's avatar
Michael Beck committed
924
	if (proj_nr == pn_Mod_res) {
Michael Beck's avatar
Michael Beck committed
925
926
		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
927
	}
928
	return tarval_unknown;
929
}
930

Michael Beck's avatar
Michael Beck committed
931
/**
Michael Beck's avatar
Michael Beck committed
932
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
933
 */
Matthias Braun's avatar
Matthias Braun committed
934
static ir_tarval *computed_value_Proj(const ir_node *proj)
935
{
yb9976's avatar
yb9976 committed
936
	const ir_node *n = get_Proj_pred(proj);
Michael Beck's avatar
Michael Beck committed
937
938
939

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

943
/**
944
 * If the parameter n can be computed, return its value, else tarval_unknown.
945
 * Performs constant folding.
946
947
 *
 * @param n  The node this should be evaluated
948
 */
Matthias Braun's avatar
Matthias Braun committed
949
ir_tarval *computed_value(const ir_node *n)