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

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
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

Matthias Braun's avatar
Matthias Braun committed
380
	if (ta != tarval_unknown && tb != tarval_unknown)
Michael Beck's avatar
Michael Beck committed
381
		return tarval_mul(ta, tb);
Matthias Braun's avatar
Matthias Braun committed
382
383
384
385
386
387
388
389

	/* 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
390
	}
391
	return tarval_unknown;
392
}
393

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

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

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

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

415
	return tarval_unknown;
416
}
417

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

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

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

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

439
	return tarval_unknown;
440
}
441

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

450
451
452
453
454
455
456
	/* 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
457
		return get_mode_null(get_irn_mode(n));
458
459
	}

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

yb9976's avatar
yb9976 committed
464
465
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
Matthias Braun's avatar
Matthias Braun committed
466
	if (ta != tarval_unknown && tb != tarval_unknown)
467
		return tarval_eor(ta, tb);
Matthias Braun's avatar
Matthias Braun committed
468

469
	return tarval_unknown;
470
}
471

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

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

483
	return tarval_unknown;
484
}
485

486
/**
yb9976's avatar
yb9976 committed
487
 * Tests whether a shift shifts more bits than available in the mode
488
489
490
 */
static bool is_oversize_shift(const ir_node *n)
{
491
492
	const ir_node *count = get_binop_right(n);
	ir_tarval     *tv    = value_of(count);
493
	if (!tarval_is_constant(tv))
494
		return false;
495
496
497
498
499
500
501
502
503
504
	/* 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);
	}
505
506
507
	if (!tarval_is_long(tv))
		return false;

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

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

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

527
	return tarval_unknown;
528
}
529

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

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

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

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

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

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

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

602
	return tarval_unknown;
603
}
604

605
606
607
608
609
610
611
612
613
614
615
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
616
617
618
619
/**
 * 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
620
static ir_tarval *computed_value_Mux(const ir_node *n)
621
{
yb9976's avatar
yb9976 committed
622
623
	const ir_node   *sel = get_Mux_sel(n);
	const ir_tarval *ts  = value_of(sel);
Michael Beck's avatar
Michael Beck committed
624
625
626
627

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

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

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

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

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

661
662
663
664
665
666
667
668
669
670
671
672
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;
}

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

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

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

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

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

745
746
747
748
749
	/* 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;
750
751
752
753
	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;
754
755
756
757
758
759
760
761
762
	/* 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;
	}
763
764
765

	return possible;
}
766

yb9976's avatar
yb9976 committed
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
/**
 * 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;
}

783
784
/**
 * Check whether we can use @p relation or its ordered complement instead of @p
yb9976's avatar
yb9976 committed
785
 * cmp_relation, if only some relations are @p possible.
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
 *
 * @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;
}

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

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

824
	/* we have some special rules for == 0 and != 0 */
825
826
827
	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;
828

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

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

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

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

871
872
873
874
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
875
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
876
{
Matthias Braun's avatar
Matthias Braun committed
877
	ir_tarval *tb = value_of(b);
878
879
880
881
882
883
	/* 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);
884

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

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

898
	return tarval_unknown;
899
}
900

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

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

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

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

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

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

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