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"
40
#include "firmstat_t.h"
Christian Schäfer's avatar
Christian Schäfer committed
41

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

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

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

int ir_imprecise_float_transforms_allowed(void)
{
	return imprecise_float_transforms_allowed;
}

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

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

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

88
89
90
91
92
93
94
95
	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);
96
97
}

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

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

value_of_func value_of_ptr = default_value_of;

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

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

	/* walk confirm sequence and look for matching confirms */
	for (;;) {
		/* -x != 0  =>  x != 0 */
		if (is_Minus(n)) {
			n = get_Minus_op(n);
			continue;
		}
155
		/* we can ignore Sels/Members: either the base pointer points to null or
yb9976's avatar
yb9976 committed
156
157
		 * if it does not then members addresses cannot be at NULL or we have
		 * undefined behavior because we are obviously not pointing to an
158
159
160
161
		 * object. */
		if (is_Sel(n)) {
			n = get_Sel_ptr(n);
			continue;
162
163
164
		} else if (is_Member(n)) {
			n = get_Member_ptr(n);
			continue;
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
204
		}

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

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

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

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

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

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

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

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

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
337
	/* a - a == 0 (not possible for float because NaN - NaN == NaN */
338
339
340
341
342
343
344
	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
345
		return get_mode_null(mode);
346
	}
Michael Beck's avatar
Michael Beck committed
347

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

353
	return tarval_unknown;
354
}
355

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

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

367
	return tarval_unknown;
368
}
369

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

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

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

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

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

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

417
	return tarval_unknown;
418
}
419

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

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

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

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

441
	return tarval_unknown;
442
}
443

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

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

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

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

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

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

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

485
	return tarval_unknown;
486
}
487

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

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

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

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

529
	return tarval_unknown;
530
}
531

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

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

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

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

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

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

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

604
	return tarval_unknown;
605
}
606

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

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

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

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

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

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

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

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

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

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

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

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

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

	return possible;
}
768

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

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

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

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

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

831
832
	return computed_value_Cmp_Confirm(cmp, left, right, relation);
}
833

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

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

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

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

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

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

900
	return tarval_unknown;
901
}
902

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

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

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

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

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

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

944
/**
945
 * If the parameter n can be computed, return its value, else tarval_unknown.
946
 * Performs constant folding.
947
948
 *
 * @param n  The node this should be evaluated
949
 */