iropt.c 233 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

Matthias Braun's avatar
Matthias Braun committed
43
static bool imprecise_float_transforms_allowed;
44
45
46
47
48
49
50
51
52
53
54

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
{
Matthias Braun's avatar
Matthias Braun committed
266
	ir_type const *const type = get_Align_type(n);
267
268
	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
}

/**
 * Return the value of a Size.
 */
static ir_tarval *computed_value_Size(const ir_node *n)
{
Matthias Braun's avatar
Matthias Braun committed
277
	ir_type const *const type = get_Size_type(n);
278
279
	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
	if (a == b && get_mode_arithmetic(mode) == irma_twos_complement)
Matthias Braun's avatar
Matthias Braun committed
338
		return get_mode_null(mode);
Michael Beck's avatar
Michael Beck committed
339

yb9976's avatar
yb9976 committed
340
341
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
Matthias Braun's avatar
Matthias Braun committed
342
	if (ta != tarval_unknown && tb != tarval_unknown)
343
		return tarval_sub(ta, tb, mode);
344

345
	return tarval_unknown;
346
}
347

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

356
	if (ta != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
357
		return tarval_neg(ta);
358

359
	return tarval_unknown;
360
}
361

Michael Beck's avatar
Michael Beck committed
362
/**
363
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
364
 */
Matthias Braun's avatar
Matthias Braun committed
365
static ir_tarval *computed_value_Mul(const ir_node *n)
366
{
yb9976's avatar
yb9976 committed
367
368
369
370
371
	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
372

Matthias Braun's avatar
Matthias Braun committed
373
	if (ta != tarval_unknown && tb != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
374
		return tarval_mul(ta, tb);
Matthias Braun's avatar
Matthias Braun committed
375
376
377
378
379
380
381
382

	/* a * 0 != 0 if a == NaN or a == Inf */
	if (!mode_is_float(mode)) {
		/* a*0 = 0 or 0*b = 0 */
		if (tarval_is_null(ta))
			return ta;
		if (tarval_is_null(tb))
			return tb;
Michael Beck's avatar
Michael Beck committed
383
	}
384
	return tarval_unknown;
385
}
386

Michael Beck's avatar
Michael Beck committed
387
/**
388
 * Return the value of an And.
Michael Beck's avatar
Michael Beck committed
389
390
 * Special case: a & 0, 0 & b
 */
Matthias Braun's avatar
Matthias Braun committed
391
static ir_tarval *computed_value_And(const ir_node *n)
392
{
yb9976's avatar
yb9976 committed
393
394
395
396
	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
397

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

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

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

408
	return tarval_unknown;
409
}
410

Michael Beck's avatar
Michael Beck committed
411
/**
412
 * Return the value of an Or.
Michael Beck's avatar
Michael Beck committed
413
414
 * Special case: a | 1...1, 1...1 | b
 */
Matthias Braun's avatar
Matthias Braun committed
415
static ir_tarval *computed_value_Or(const ir_node *n)
416
{
yb9976's avatar
yb9976 committed
417
418
419
420
	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
421

Matthias Braun's avatar
Matthias Braun committed
422
	if (ta != tarval_unknown && tb != tarval_unknown)
yb9976's avatar
yb9976 committed
423
		return tarval_or(ta, tb);
424
425
426
427

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

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

432
	return tarval_unknown;
433
}
434

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

443
	/* a ^ a == 0 */
444
	if (a == b)
Michael Beck's avatar
Michael Beck committed
445
		return get_mode_null(get_irn_mode(n));
446

Matthias Braun's avatar
Matthias Braun committed
447
	/* x^~x => ~0 */
Christoph Mallon's avatar
Christoph Mallon committed
448
	if (complement_values(a, b))
449
		return get_mode_all_one(get_irn_mode(n));
Michael Beck's avatar
Michael Beck committed
450

yb9976's avatar
yb9976 committed
451
452
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
Matthias Braun's avatar
Matthias Braun committed
453
	if (ta != tarval_unknown && tb != tarval_unknown)
454
		return tarval_eor(ta, tb);
Matthias Braun's avatar
Matthias Braun committed
455

456
	return tarval_unknown;
457
}
458

Michael Beck's avatar
Michael Beck committed
459
/**
460
 * Return the value of a Not.
Michael Beck's avatar
Michael Beck committed
461
 */
Matthias Braun's avatar
Matthias Braun committed
462
static ir_tarval *computed_value_Not(const ir_node *n)
463
{
yb9976's avatar
yb9976 committed
464
465
	const ir_node *a  = get_Not_op(n);
	ir_tarval     *ta = value_of(a);
466

467
	if (ta != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
468
		return tarval_not(ta);
469

470
	return tarval_unknown;
471
}
472

473
/**
yb9976's avatar
yb9976 committed
474
 * Tests whether a shift shifts more bits than available in the mode
475
476
477
 */
static bool is_oversize_shift(const ir_node *n)
{
478
479
	const ir_node *count = get_binop_right(n);
	ir_tarval     *tv    = value_of(count);
480
	if (!tarval_is_constant(tv))
481
		return false;
482
483
484
485
486
487
488
489
490
491
	/* 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);
	}
492
493
494
	if (!tarval_is_long(tv))
		return false;

495
496
	long shiftval = get_tarval_long(tv);
	return shiftval < 0 || shiftval >= (long)get_mode_size_bits(mode);
497
498
}

Michael Beck's avatar
Michael Beck committed
499
/**
500
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
501
 */
Matthias Braun's avatar
Matthias Braun committed
502
static ir_tarval *computed_value_Shl(const ir_node *n)
503
{
yb9976's avatar
yb9976 committed
504
505
506
507
	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);
508

Matthias Braun's avatar
Matthias Braun committed
509
	if (ta != tarval_unknown && tb != tarval_unknown)
510
		return tarval_shl(ta, tb);
511
512
513
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

514
	return tarval_unknown;
515
}
516

Michael Beck's avatar
Michael Beck committed
517
/**
518
 * Return the value of a Shr.
Michael Beck's avatar
Michael Beck committed
519
 */
Matthias Braun's avatar
Matthias Braun committed
520
static ir_tarval *computed_value_Shr(const ir_node *n)
521
{
yb9976's avatar
yb9976 committed
522
523
524
525
	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);
526

Matthias Braun's avatar
Matthias Braun committed
527
	if (ta != tarval_unknown && tb != tarval_unknown)
528
		return tarval_shr(ta, tb);
529
530
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));
531
	return tarval_unknown;
532
}
533

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

Matthias Braun's avatar
Matthias Braun committed
544
	if (ta != tarval_unknown && tb != tarval_unknown)
545
		return tarval_shrs(ta, tb);
546
	return tarval_unknown;
547
}
548

549
550
bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
{
yb9976's avatar
yb9976 committed
551
	const ir_mode *mode = get_irn_mode(node);
552
553
554
555
	if (get_mode_arithmetic(mode) != irma_twos_complement
	    || get_mode_arithmetic(dest_mode) != irma_twos_complement)
	    return false;

556
557
558
559
560
561
562
	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;
563
564
565
566
567
568
569
570
571
572
573
574
	}
	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
575
/**
576
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
577
 */
Matthias Braun's avatar
Matthias Braun committed
578
static ir_tarval *computed_value_Conv(const ir_node *n)
579
{
yb9976's avatar
yb9976 committed
580
581
582
	const ir_node *a    = get_Conv_op(n);
	ir_tarval     *ta   = value_of(a);
	ir_mode       *mode = get_irn_mode(n);
583

584
	if (ta != tarval_unknown)
yb9976's avatar
yb9976 committed
585
		return tarval_convert_to(ta, mode);
586
587
588
	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

589
	return tarval_unknown;
590
}
591

592
593
594
595
596
597
598
599
600
601
602
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
603
604
605
606
/**
 * 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
607
static ir_tarval *computed_value_Mux(const ir_node *n)
608
{
yb9976's avatar
yb9976 committed
609
610
	const ir_node   *sel = get_Mux_sel(n);
	const ir_tarval *ts  = value_of(sel);
Michael Beck's avatar
Michael Beck committed
611
612
613
614

	if (ts == get_tarval_b_true()) {
		ir_node *v = get_Mux_true(n);
		return value_of(v);
Matthias Braun's avatar
Matthias Braun committed
615
	} else if (ts == get_tarval_b_false()) {
Michael Beck's avatar
Michael Beck committed
616
617
618
		ir_node *v = get_Mux_false(n);
		return value_of(v);
	}
619
	return tarval_unknown;
620
}
Michael Beck's avatar
Michael Beck committed
621
622
623
624
625

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
Matthias Braun's avatar
Matthias Braun committed
626
static ir_tarval *computed_value_Confirm(const ir_node *n)
627
{
yb9976's avatar
yb9976 committed
628
629
630
631
	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);
632

633
634
635
636
637
	switch (possible & relation) {
	case ir_relation_false:
		return tarval_bad;

	case ir_relation_equal: {
638
		ir_tarval *tv = value_of(bound);
639
		if (tarval_is_constant(tv))
640
			return tv;
641
642
		break;
	}
Michael Beck's avatar
Michael Beck committed
643
	}
644

645
	return value_of(value);
646
}
Michael Beck's avatar
Michael Beck committed
647

648
649
650
651
652
653
654
655
656
657
658
659
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;
}

660
/**
661
662
 * gives a (conservative) estimation of possible relation when comparing
 * left+right
663
 */
664
665
ir_relation ir_get_possible_cmp_relations(const ir_node *left,
                                          const ir_node *right)
666
{
yb9976's avatar
yb9976 committed
667
668
669
	ir_relation      possible = ir_relation_true;
	const ir_tarval *tv_l     = value_of(left);
	const ir_tarval *tv_r     = value_of(right);
670

671
	/* both values known - evaluate them */
Matthias Braun's avatar
Matthias Braun committed
672
	if (tv_l != tarval_unknown && tv_r != tarval_unknown) {
673
674
675
676
		possible = tarval_cmp(tv_l, tv_r);
		/* we can return now, won't get any better */
		return possible;
	}
yb9976's avatar
yb9976 committed
677

678
679
680
681
682
	/* NaN never compares successfully to anything */
	if (tarval_is_nan(tv_l) || tarval_is_nan(tv_r)) {
		return ir_relation_unordered;
	}

683
684
685
686
	/* 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
687
	const ir_mode *mode = get_irn_mode(left);
688
689
690
691
	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
692
693
	ir_tarval       *min = get_mode_min(mode);
	const ir_tarval *max = get_mode_max(mode);
694
695
696
697
698
699
700
701
	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
702
703
704
705
706
707
708
709
710
711
712

	/* 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
713
			ir_tarval *l_max = tarval_and(l_z, tarval_ornot(l_o, min));
yb9976's avatar
yb9976 committed
714
			ir_tarval *l_min = tarval_or(l_o, tarval_and(l_z, min));
yb9976's avatar
yb9976 committed
715
			ir_tarval *r_max = tarval_and(r_z, tarval_ornot(r_o, min));
yb9976's avatar
yb9976 committed
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
			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;
		}
	}

732
733
734
735
736
	/* 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;
737
738
739
740
	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;
741
742
743
744
745
746
747
748
749
	/* 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;
	}
750
751
752

	return possible;
}
753

yb9976's avatar
yb9976 committed
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
/**
 * 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;
}

770
771
/**
 * Check whether we can use @p relation or its ordered complement instead of @p
yb9976's avatar
yb9976 committed
772
 * cmp_relation, if only some relations are @p possible.
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
 *
 * @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;
}

791
792
793
794
795
796
797
/**
 * 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)
798
{
yb9976's avatar
yb9976 committed
799
800
801
802
	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);
803
804
805
806
807
808
809
810

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

811
	/* we have some special rules for == 0 and != 0 */
812
813
814
	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;
815

Matthias Braun's avatar
Matthias Braun committed
816
	return computed_value_Cmp_Confirm(left, right, relation);
817
}
818

819
820
821
822
823
824
825
/**
 * 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())
826
		return tarval_unknown;
827
	return computed_value_Cmp(cmp);
828
829
}

830
/**
Michael Beck's avatar
Michael Beck committed
831
 * Calculate the value of an integer Div.
832
833
 * Special case: 0 / b
 */
834
static ir_tarval *do_computed_value_Div(const ir_node *a, const ir_node *b)
835
{
836
	ir_tarval *ta = value_of(a);
837

Michael Beck's avatar
Michael Beck committed
838
	/* cannot optimize 0 / b = 0 because of NaN */
839
840
841
	if (tarval_is_null(ta)) {
		ir_mode *mode = get_irn_mode(a);
		if (get_mode_arithmetic(mode) == irma_twos_complement
842
		    && value_not_null(b, NULL)) {
Michael Beck's avatar
Michael Beck committed
843
			return ta;  /* 0 / b == 0 if b != 0 */
844
845
846
847
848
849
850
		}
	}
	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);
851
	}
yb9976's avatar
yb9976 committed
852
	ir_tarval *tb = value_of(b);
853
	if (ta != tarval_unknown && tb != tarval_unknown)
854
		return tarval_div(ta, tb);
855
	return tarval_unknown;
856
}
Michael Beck's avatar
Michael Beck committed
857

858
859
860
861
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
862
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
863
{
Matthias Braun's avatar
Matthias Braun committed
864
	ir_tarval *tb = value_of(b);
865
866
867
868
869
870
	/* 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);
871

872
	/* constant folding */
yb9976's avatar
yb9976 committed
873
	ir_tarval *ta = value_of(a);
874
875
876
	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_mod(ta, tb);

877
	/* 0 % b == 0 if b != 0 */
878
879
880
	/* a % a == 0 if a != 0 */
	if (tarval_is_null(ta) || a == b) {
		assert(get_mode_arithmetic(mode) == irma_twos_complement);
881
		if (value_not_null(b, NULL))
882
			return get_mode_null(mode);
883
	}
884

885
	return tarval_unknown;
886
}
887

Michael Beck's avatar
Michael Beck committed
888
889
890
/**
 * Return the value of a Proj(Div).
 */
Matthias Braun's avatar
Matthias Braun committed
891
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
892
{
893
	unsigned proj_nr = get_Proj_num(n);
894
	if (proj_nr != pn_Div_res)
895
		return tarval_unknown;
Michael Beck's avatar
Michael Beck committed
896

897
898
899
900
	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);
901
}
902

903
/**
Michael Beck's avatar
Michael Beck committed
904
 * Return the value of a Proj(Mod).
905
 */
Matthias Braun's avatar
Matthias Braun committed
906
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
907
{
908
	unsigned proj_nr = get_Proj_num(n);
Michael Beck's avatar
Michael Beck committed
909

Michael Beck's avatar
Michael Beck committed
910
	if (proj_nr == pn_Mod_res) {
Michael Beck's avatar
Michael Beck committed
911
912
		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
913
	}
914
	return tarval_unknown;
915
}
916

Michael Beck's avatar
Michael Beck committed
917
/**
Michael Beck's avatar
Michael Beck committed
918
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
919
 */
Matthias Braun's avatar
Matthias Braun committed
920
static ir_tarval *computed_value_Proj(const ir_node *proj)
921
{
yb9976's avatar
yb9976 committed
922
	const ir_node *n = get_Proj_pred(proj);
Michael Beck's avatar
Michael Beck committed
923
924
925

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

929
/**
930
 * If the parameter n can be computed, return its value, else tarval_unknown.
931
 * Performs constant folding.
932
933
 *
 * @param n  The node this should be evaluated
934
 */
Matthias Braun's avatar
Matthias Braun committed
935
ir_tarval *computed_value(const ir_node *n)
936
{
yb9976's avatar
yb9976 committed
937
	const vrp_attr *vrp = vrp_get_info(n);
938
	if (vrp != NULL && vrp->bits_set == vrp->bits_not_set)
939
		return vrp->bits_set