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

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)) {
60
61
62
63
64
65
66
		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.
		 */
Matthias Braun's avatar
Matthias Braun committed
67
		if (bl && br && tarval_is_null(tarval_and(bl->z, br->z)))
68
			return true;
69
70
71
72
	}
	return false;
}

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

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

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

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

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

value_of_func value_of_ptr = default_value_of;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

344
	return tarval_unknown;
345
}
346

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

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

358
	return tarval_unknown;
359
}
360

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

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

	/* 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
382
	}
383
	return tarval_unknown;
384
}
385

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

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

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

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

407
	return tarval_unknown;
408
}
409

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

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

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

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

431
	return tarval_unknown;
432
}
433

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

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

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

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

455
	return tarval_unknown;
456
}
457

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

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

469
	return tarval_unknown;
470
}
471

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

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

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

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

513
	return tarval_unknown;
514
}
515

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

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

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

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

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

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

583
	if (ta != tarval_unknown)
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
584
		return tarval_convert_to(ta, mode);
585
586
587
	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

588
	return tarval_unknown;
589
}
590

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

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

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

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

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

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

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

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

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

677
	/* NaN never compares successfully to anything */
Matthias Braun's avatar
Matthias Braun committed
678
	if (tarval_is_nan(tv_l) || tarval_is_nan(tv_r))
679
680
		return ir_relation_unordered;

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

	/* 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. */
711
			ir_tarval *l_max = tarval_and(l_z, tarval_ornot(l_o, min));
712
			ir_tarval *l_min = tarval_or(l_o, tarval_and(l_z, min));
713
			ir_tarval *r_max = tarval_and(r_z, tarval_ornot(r_o, min));
714
715
			ir_tarval *r_min = tarval_or(r_o, tarval_and(r_z, min));

Matthias Braun's avatar
Matthias Braun committed
716
			if (!(tarval_cmp(l_max, r_min) & ir_relation_greater))
717
				possible &= ~ir_relation_greater;
Matthias Braun's avatar
Matthias Braun committed
718
			if (!(tarval_cmp(l_min, r_max) & ir_relation_less))
719
720
721
722
723
724
725
726
727
				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;
		}
	}

728
729
730
731
732
	/* 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;
733
734
735
736
	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;
737
	/* stuff known through confirm nodes */
Matthias Braun's avatar
Matthias Braun committed
738
	if (is_Confirm(left) && get_Confirm_bound(left) == right)
739
740
741
742
743
744
		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;
	}
745
746
747

	return possible;
}
748

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

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

786
787
788
789
790
791
792
/**
 * 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)
793
{
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
794
795
796
797
	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);
798
799
800
801
802
803
804
805

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

806
	/* we have some special rules for == 0 and != 0 */
807
808
809
	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;
810

Matthias Braun's avatar
Matthias Braun committed
811
	return computed_value_Cmp_Confirm(left, right, relation);
812
}
813

814
815
816
817
818
819
820
/**
 * 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())
821
		return tarval_unknown;
822
	return computed_value_Cmp(cmp);
823
824
}

825
826
827
828
829
830
831
832
833
834
835
static ir_tarval *computed_value_Proj_Builtin(ir_node const *const proj)
{
	long           val;
	ir_node *const builtin = get_Proj_pred(proj);
	switch (get_Builtin_kind(builtin)) {
	case ir_bk_clz: {
		ir_node const *const op = get_Builtin_param(builtin, 0);
		bitinfo const *const b  = get_bitinfo(op);
		if (b) {
			val = get_tarval_highest_bit(b->z);
			if (val != -1 && tarval_get_bit(b->o, val)) {
836
				val = get_mode_size_bits(get_irn_mode(op)) - val - 1;
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
				goto make_val;
			}
		}
		break;
	}

	case ir_bk_ctz: {
		ir_node const *const op = get_Builtin_param(builtin, 0);
		bitinfo const *const b  = get_bitinfo(op);
		if (b) {
			val = get_tarval_lowest_bit(b->z);
			if (val != -1 && tarval_get_bit(b->o, val))
				goto make_val;
		}
		break;
	}

	case ir_bk_ffs: {
		ir_node const *const op = get_Builtin_param(builtin, 0);
		bitinfo const *const b  = get_bitinfo(op);
		if (b) {
			val = get_tarval_lowest_bit(b->z);
			if (val == -1 || tarval_get_bit(b->o, val)) {
				++val;
				goto make_val;
			}
		}
		break;
	}

	case ir_bk_parity: {
		ir_node *const op = get_Builtin_param(builtin, 0);
		if (is_Const(op)) {
			ir_tarval *const tv = get_Const_tarval(op);
			val = get_tarval_popcount(tv) & 1;
			goto make_val;
		}
		break;
	}

	case ir_bk_popcount: {
		ir_node *const op = get_Builtin_param(builtin, 0);
		if (is_Const(op)) {
			ir_tarval *const tv = get_Const_tarval(op);
			val = get_tarval_popcount(tv);
			goto make_val;
		}
		break;
	}

	default:
		break;
	}

	return tarval_unknown;

make_val:;
	ir_mode *const mode = get_irn_mode(proj);
	return new_tarval_from_long(val, mode);
}

898
/**
Michael Beck's avatar
Michael Beck committed
899
 * Calculate the value of an integer Div.
900
901
 * Special case: 0 / b
 */
902
static ir_tarval *do_computed_value_Div(const ir_node *a, const ir_node *b)
903
{
904
	ir_tarval *ta = value_of(a);
905

Michael Beck's avatar
Michael Beck committed
906
	/* cannot optimize 0 / b = 0 because of NaN */
907
908
909
	if (tarval_is_null(ta)) {
		ir_mode *mode = get_irn_mode(a);
		if (get_mode_arithmetic(mode) == irma_twos_complement
910
		    && value_not_null(b, NULL)) {
Michael Beck's avatar
Michael Beck committed
911
			return ta;  /* 0 / b == 0 if b != 0 */
912
913
914
915
916
917
918
		}
	}
	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);
919
	}
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
920
	ir_tarval *tb = value_of(b);
921
	if (ta != tarval_unknown && tb != tarval_unknown)
922
		return tarval_div(ta, tb);
923
	return tarval_unknown;
924
}
Michael Beck's avatar
Michael Beck committed
925

926
927
928
929
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
930
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
931
{
Matthias Braun's avatar
Matthias Braun committed
932
	ir_tarval *tb = value_of(b);
933
934
935
	/* a % 1 == 0 */
	/* a % -1 == 0 */
	ir_mode *mode = get_irn_mode(a);
Matthias Braun's avatar
Matthias Braun committed
936
	if (tarval_is_one(tb) || (mode_is_signed(mode) && tarval_is_all_one(tb)))
937
		return get_mode_null(mode);
938

939
	/* constant folding */
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
940
	ir_tarval *ta = value_of(a);
941
942
943
	if (ta != tarval_unknown && tb != tarval_unknown)
		return tarval_mod(ta, tb);

944
	/* 0 % b == 0 if b != 0 */
945
946
947
	/* a % a == 0 if a != 0 */
	if (tarval_is_null(ta) || a == b) {
		assert(get_mode_arithmetic(mode) == irma_twos_complement);
948
		if (value_not_null(b, NULL))
949
			return get_mode_null(mode);
950
	}
951

952
	return tarval_unknown;
953
}
954

Michael Beck's avatar
Michael Beck committed
955
956
957
/**
 * Return the value of a Proj(Div).
 */
Matthias Braun's avatar
Matthias Braun committed
958
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
959
{
960
	unsigned proj_nr = get_Proj_num(n);
961
	if (proj_nr != pn_Div_res)
962
		return tarval_unknown;
Michael Beck's avatar
Michael Beck committed
963

964
965
966
967
	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);
968
}
969

970
/**
Michael Beck's avatar
Michael Beck committed
971
 * Return the value of a Proj(Mod).
972
 */
Matthias Braun's avatar
Matthias Braun committed
973
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
974
{
975
	unsigned proj_nr = get_Proj_num(n);
Michael Beck's avatar
Michael Beck committed
976

Michael Beck's avatar
Michael Beck committed
977
	if (proj_nr == pn_Mod_res) {
Michael Beck's avatar
Michael Beck committed
978
979
		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
980
	}
981
	return tarval_unknown;
982
}
983

Michael Beck's avatar
Michael Beck committed
984
/**
Michael Beck's avatar
Michael Beck committed
985
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
986
 */
Matthias Braun's avatar
Matthias Braun committed
987
static ir_tarval *computed_value_Proj(const ir_node *proj)
988
{
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
989
	const ir_node *n = get_Proj_pred(proj);
Michael Beck's avatar
Michael Beck committed
990
991
992

	if (n->op->ops.computed_value_Proj != NULL)
		return n->op->ops.computed_value_Proj(proj);
993
	return tarval_unknown;
994
}