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

Michael Beck's avatar
Michael Beck committed
14
15
16
17
18
19
20
#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"
21
#include "irgopt.h"
22
#include "irverify.h"
23
#include "iroptimize.h"
Michael Beck's avatar
Michael Beck committed
24
25
26
27
28
29
30
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
#include "irhooks.h"
#include "irarch.h"
#include "hashptr.h"
Michael Beck's avatar
Michael Beck committed
31
#include "irtools.h"
32
#include "irhooks.h"
33
#include "array.h"
34
35
#include "vrp.h"
#include "firm_types.h"
36
#include "bitfiddle.h"
37
#include "be.h"
38
#include "error.h"
39
#include "firmstat_t.h"
Christian Schäfer's avatar
Christian Schäfer committed
40

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

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

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

int ir_imprecise_float_transforms_allowed(void)
{
	return imprecise_float_transforms_allowed;
}

55
56
57
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
58
59
60
61
		const ir_node  *left      = get_binop_left(node);
		const ir_node  *right     = get_binop_right(node);
		const vrp_attr *vrp_left  = vrp_get_info(left);
		const vrp_attr *vrp_right = vrp_get_info(right);
62
63
64
65
66
67
68
69
70
		if (vrp_left != NULL && vrp_right != NULL) {
			ir_tarval *vrp_val
				= tarval_and(vrp_left->bits_not_set, vrp_right->bits_not_set);
			return tarval_is_null(vrp_val);
		}
	}
	return false;
}

71
72
73
/**
 * Returns the tarval of a Const node or tarval_bad for all other nodes.
 */
Matthias Braun's avatar
Matthias Braun committed
74
static ir_tarval *default_value_of(const ir_node *n)
75
{
76
77
78
79
80
81
82
83
	if (is_Const(n))
		return get_Const_tarval(n); /* might return tarval_bad */
	else
		return tarval_bad;
}

value_of_func value_of_ptr = default_value_of;

84
85
void set_value_of_func(value_of_func func)
{
86
87
88
89
90
91
	if (func != NULL)
		value_of_ptr = func;
	else
		value_of_ptr = default_value_of;
}

92
/**
93
 * Return the value of a Constant.
94
 */
Matthias Braun's avatar
Matthias Braun committed
95
static ir_tarval *computed_value_Const(const ir_node *n)
96
{
Michael Beck's avatar
Michael Beck committed
97
	return get_Const_tarval(n);
98
}
Christian Schäfer's avatar
Christian Schäfer committed
99

100
/**
Michael Beck's avatar
Michael Beck committed
101
 * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
102
 */
Matthias Braun's avatar
Matthias Braun committed
103
static ir_tarval *computed_value_SymConst(const ir_node *n)
104
{
Michael Beck's avatar
Michael Beck committed
105
	switch (get_SymConst_kind(n)) {
yb9976's avatar
yb9976 committed
106
107
	case symconst_type_size: {
		const ir_type *type = get_SymConst_type(n);
Michael Beck's avatar
Michael Beck committed
108
109
110
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_type_size_bytes(type), get_irn_mode(n));
		break;
yb9976's avatar
yb9976 committed
111
112
113
	}
	case symconst_type_align: {
		ir_type *type = get_SymConst_type(n);
Michael Beck's avatar
Michael Beck committed
114
115
116
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_type_alignment_bytes(type), get_irn_mode(n));
		break;
yb9976's avatar
yb9976 committed
117
118
119
120
	}
	case symconst_ofs_ent: {
		const ir_entity *ent  = get_SymConst_entity(n);
		const ir_type   *type = get_entity_owner(ent);
Michael Beck's avatar
Michael Beck committed
121
122
123
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_entity_offset(ent), get_irn_mode(n));
		break;
yb9976's avatar
yb9976 committed
124
	}
Michael Beck's avatar
Michael Beck committed
125
126
127
128
	default:
		break;
	}
	return tarval_bad;
129
}
Christian Schäfer's avatar
Christian Schäfer committed
130

Michael Beck's avatar
Michael Beck committed
131
/**
132
 * Return the value of an Add.
Michael Beck's avatar
Michael Beck committed
133
 */
Matthias Braun's avatar
Matthias Braun committed
134
static ir_tarval *computed_value_Add(const ir_node *n)
135
{
yb9976's avatar
yb9976 committed
136
137
138
139
	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);
140

141
	if ((ta != tarval_bad) && (tb != tarval_bad))
Michael Beck's avatar
Michael Beck committed
142
		return tarval_add(ta, tb);
143

144
145
146
147
148
149
	/* x+~x => -1 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_all_one(get_irn_mode(n));
	}

Michael Beck's avatar
Michael Beck committed
150
	return tarval_bad;
151
}
Christian Schäfer's avatar
Christian Schäfer committed
152

Michael Beck's avatar
Michael Beck committed
153
/**
154
 * Return the value of a Sub.
Michael Beck's avatar
Michael Beck committed
155
156
 * Special case: a - a
 */
Matthias Braun's avatar
Matthias Braun committed
157
static ir_tarval *computed_value_Sub(const ir_node *n)
158
{
yb9976's avatar
yb9976 committed
159
160
161
	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
162

163
164
165
166
167
168
	/* NaN - NaN != 0 */
	if (! mode_is_float(mode)) {
		/* a - a = 0 */
		if (a == b)
			return get_mode_null(mode);
	}
Michael Beck's avatar
Michael Beck committed
169

yb9976's avatar
yb9976 committed
170
171
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
172

173
174
	if ((ta != tarval_bad) && (tb != tarval_bad))
		return tarval_sub(ta, tb, mode);
175

Michael Beck's avatar
Michael Beck committed
176
	return tarval_bad;
177
}
178

Michael Beck's avatar
Michael Beck committed
179
/**
180
 * Return the value of an unary Minus.
Michael Beck's avatar
Michael Beck committed
181
 */
Matthias Braun's avatar
Matthias Braun committed
182
static ir_tarval *computed_value_Minus(const ir_node *n)
183
{
yb9976's avatar
yb9976 committed
184
185
	const ir_node *a  = get_Minus_op(n);
	ir_tarval     *ta = value_of(a);
186

Michael Beck's avatar
Michael Beck committed
187
	if (ta != tarval_bad)
Michael Beck's avatar
Michael Beck committed
188
		return tarval_neg(ta);
189

Michael Beck's avatar
Michael Beck committed
190
	return tarval_bad;
191
}
192

Michael Beck's avatar
Michael Beck committed
193
/**
194
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
195
 */
Matthias Braun's avatar
Matthias Braun committed
196
static ir_tarval *computed_value_Mul(const ir_node *n)
197
{
yb9976's avatar
yb9976 committed
198
199
200
201
202
	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
203

Michael Beck's avatar
Michael Beck committed
204
205
206
207
208
209
210
	if (mode != get_irn_mode(a)) {
		/* n * n = 2n bit multiplication */
		ta = tarval_convert_to(ta, mode);
		tb = tarval_convert_to(tb, mode);
	}

	if (ta != tarval_bad && tb != tarval_bad) {
Michael Beck's avatar
Michael Beck committed
211
212
		return tarval_mul(ta, tb);
	} else {
213
214
215
216
217
218
219
220
		/* a * 0 != 0 if a == NaN or a == Inf */
		if (!mode_is_float(mode)) {
			/* a*0 = 0 or 0*b = 0 */
			if (ta == get_mode_null(mode))
				return ta;
			if (tb == get_mode_null(mode))
				return tb;
		}
Michael Beck's avatar
Michael Beck committed
221
222
	}
	return tarval_bad;
223
}
224

Michael Beck's avatar
Michael Beck committed
225
/**
226
 * Return the value of an And.
Michael Beck's avatar
Michael Beck committed
227
228
 * Special case: a & 0, 0 & b
 */
Matthias Braun's avatar
Matthias Braun committed
229
static ir_tarval *computed_value_And(const ir_node *n)
230
{
yb9976's avatar
yb9976 committed
231
232
233
234
	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
235
236

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
yb9976's avatar
yb9976 committed
237
		return tarval_and(ta, tb);
Michael Beck's avatar
Michael Beck committed
238
	}
239
240
241
242
243
244
245
246
247
248

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

	/* x&~x => 0 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_null(get_irn_mode(n));
	}

Michael Beck's avatar
Michael Beck committed
249
	return tarval_bad;
250
}
251

Michael Beck's avatar
Michael Beck committed
252
/**
253
 * Return the value of an Or.
Michael Beck's avatar
Michael Beck committed
254
255
 * Special case: a | 1...1, 1...1 | b
 */
Matthias Braun's avatar
Matthias Braun committed
256
static ir_tarval *computed_value_Or(const ir_node *n)
257
{
yb9976's avatar
yb9976 committed
258
259
260
261
	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
262
263
264

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_or (ta, tb);
265
266
267
268
269
270
271
272
273
	}

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

	/* x|~x => -1 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_all_one(get_irn_mode(n));
Michael Beck's avatar
Michael Beck committed
274
275
	}
	return tarval_bad;
276
}
277

Michael Beck's avatar
Michael Beck committed
278
/**
279
 * Return the value of an Eor.
Michael Beck's avatar
Michael Beck committed
280
 */
Matthias Braun's avatar
Matthias Braun committed
281
static ir_tarval *computed_value_Eor(const ir_node *n)
282
{
yb9976's avatar
yb9976 committed
283
284
	const ir_node *a = get_Eor_left(n);
	const ir_node *b = get_Eor_right(n);
Michael Beck's avatar
Michael Beck committed
285

Michael Beck's avatar
Michael Beck committed
286
287
	if (a == b)
		return get_mode_null(get_irn_mode(n));
288
289
290
291
292
	/* x^~x => -1 */
	if ((is_Not(a) && get_Not_op(a) == b)
	    || (is_Not(b) && get_Not_op(b) == a)) {
		return get_mode_all_one(get_irn_mode(n));
	}
Michael Beck's avatar
Michael Beck committed
293

yb9976's avatar
yb9976 committed
294
295
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
296

Michael Beck's avatar
Michael Beck committed
297
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
298
		return tarval_eor(ta, tb);
Michael Beck's avatar
Michael Beck committed
299
300
	}
	return tarval_bad;
301
}
302

Michael Beck's avatar
Michael Beck committed
303
/**
304
 * Return the value of a Not.
Michael Beck's avatar
Michael Beck committed
305
 */
Matthias Braun's avatar
Matthias Braun committed
306
static ir_tarval *computed_value_Not(const ir_node *n)
307
{
yb9976's avatar
yb9976 committed
308
309
	const ir_node *a  = get_Not_op(n);
	ir_tarval     *ta = value_of(a);
310

Michael Beck's avatar
Michael Beck committed
311
312
	if (ta != tarval_bad)
		return tarval_not(ta);
313

Michael Beck's avatar
Michael Beck committed
314
	return tarval_bad;
315
}
316

317
/**
yb9976's avatar
yb9976 committed
318
 * Tests whether a shift shifts more bits than available in the mode
319
320
321
 */
static bool is_oversize_shift(const ir_node *n)
{
yb9976's avatar
yb9976 committed
322
323
324
	const ir_node   *count = get_binop_right(n);
	const ir_mode   *mode  = get_irn_mode(n);
	const ir_tarval *tv    = value_of(count);
325
326
327
328
	if (tv == tarval_bad)
		return false;
	if (!tarval_is_long(tv))
		return false;
yb9976's avatar
yb9976 committed
329
330
	long shiftval     = get_tarval_long(tv);
	long modulo_shift = get_mode_modulo_shift(mode);
331
332
333
334
335
336
	if (shiftval < 0 || (modulo_shift > 0 && shiftval >= modulo_shift))
		return false;

	return shiftval >= (long)get_mode_size_bits(mode);
}

Michael Beck's avatar
Michael Beck committed
337
/**
338
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
339
 */
Matthias Braun's avatar
Matthias Braun committed
340
static ir_tarval *computed_value_Shl(const ir_node *n)
341
{
yb9976's avatar
yb9976 committed
342
343
344
345
	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);
346

Michael Beck's avatar
Michael Beck committed
347
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
348
		return tarval_shl(ta, tb);
Michael Beck's avatar
Michael Beck committed
349
	}
350
351
352
353

	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

Michael Beck's avatar
Michael Beck committed
354
	return tarval_bad;
355
}
356

Michael Beck's avatar
Michael Beck committed
357
/**
358
 * Return the value of a Shr.
Michael Beck's avatar
Michael Beck committed
359
 */
Matthias Braun's avatar
Matthias Braun committed
360
static ir_tarval *computed_value_Shr(const ir_node *n)
361
{
yb9976's avatar
yb9976 committed
362
363
364
365
	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);
366

Michael Beck's avatar
Michael Beck committed
367
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
368
		return tarval_shr(ta, tb);
Michael Beck's avatar
Michael Beck committed
369
	}
370
371
372
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

Michael Beck's avatar
Michael Beck committed
373
	return tarval_bad;
374
}
375

Michael Beck's avatar
Michael Beck committed
376
/**
377
 * Return the value of a Shrs.
Michael Beck's avatar
Michael Beck committed
378
 */
Matthias Braun's avatar
Matthias Braun committed
379
static ir_tarval *computed_value_Shrs(const ir_node *n)
380
{
yb9976's avatar
yb9976 committed
381
382
383
384
	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);
385

Michael Beck's avatar
Michael Beck committed
386
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
387
		return tarval_shrs(ta, tb);
Michael Beck's avatar
Michael Beck committed
388
389
	}
	return tarval_bad;
390
}
391

392
393
bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
{
yb9976's avatar
yb9976 committed
394
	const ir_mode *mode = get_irn_mode(node);
395
396
397
398
399
	if (get_mode_arithmetic(mode) != irma_twos_complement
	    || get_mode_arithmetic(dest_mode) != irma_twos_complement)
	    return false;

	if (is_Shl(node)) {
yb9976's avatar
yb9976 committed
400
		const ir_node *count = get_Shl_right(node);
401
		if (is_Const(count)) {
yb9976's avatar
yb9976 committed
402
			const ir_tarval *tv = get_Const_tarval(count);
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
			if (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;
			}
		}
	}
	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
423
/**
424
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
425
 */
Matthias Braun's avatar
Matthias Braun committed
426
static ir_tarval *computed_value_Conv(const ir_node *n)
427
{
yb9976's avatar
yb9976 committed
428
429
430
	const ir_node *a    = get_Conv_op(n);
	ir_tarval     *ta   = value_of(a);
	ir_mode       *mode = get_irn_mode(n);
431

Michael Beck's avatar
Michael Beck committed
432
	if (ta != tarval_bad)
yb9976's avatar
yb9976 committed
433
		return tarval_convert_to(ta, mode);
434

435
436
437
	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

Michael Beck's avatar
Michael Beck committed
438
	return tarval_bad;
439
}
440

Michael Beck's avatar
Michael Beck committed
441
442
443
444
/**
 * 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
445
static ir_tarval *computed_value_Mux(const ir_node *n)
446
{
yb9976's avatar
yb9976 committed
447
448
	const ir_node   *sel = get_Mux_sel(n);
	const ir_tarval *ts  = value_of(sel);
Michael Beck's avatar
Michael Beck committed
449
450
451
452
453
454
455
456
457
458

	if (ts == get_tarval_b_true()) {
		ir_node *v = get_Mux_true(n);
		return value_of(v);
	}
	else if (ts == get_tarval_b_false()) {
		ir_node *v = get_Mux_false(n);
		return value_of(v);
	}
	return tarval_bad;
459
}
Michael Beck's avatar
Michael Beck committed
460
461
462
463
464

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
Matthias Braun's avatar
Matthias Braun committed
465
static ir_tarval *computed_value_Confirm(const ir_node *n)
466
{
yb9976's avatar
yb9976 committed
467
468
469
470
	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);
471
472
473

	if ((possible & relation) == ir_relation_equal) {
		ir_tarval *tv = value_of(bound);
474
475
		if (tv != tarval_bad)
			return tv;
Michael Beck's avatar
Michael Beck committed
476
	}
477
	return value_of(value);
478
}
Michael Beck's avatar
Michael Beck committed
479

480
/**
481
482
 * gives a (conservative) estimation of possible relation when comparing
 * left+right
483
 */
484
485
ir_relation ir_get_possible_cmp_relations(const ir_node *left,
                                          const ir_node *right)
486
{
yb9976's avatar
yb9976 committed
487
488
489
490
491
492
	ir_relation      possible = ir_relation_true;
	const ir_tarval *tv_l     = value_of(left);
	const ir_tarval *tv_r     = value_of(right);
	const ir_mode   *mode     = get_irn_mode(left);
	const ir_tarval *min      = mode == mode_b ? tarval_b_false : get_mode_min(mode);
	const ir_tarval *max      = mode == mode_b ? tarval_b_true : get_mode_max(mode);
493

494
	/* both values known - evaluate them */
495
	if ((tv_l != tarval_bad) && (tv_r != tarval_bad)) {
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
		possible = tarval_cmp(tv_l, tv_r);
		/* we can return now, won't get any better */
		return possible;
	}
	/* 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 */
	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 */
	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;
	/* 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;
521
522
523
524
525
526
527
528
529
	/* 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;
	}
530
531
532

	return possible;
}
533

534
static ir_tarval *compute_cmp(const ir_node *cmp)
535
{
yb9976's avatar
yb9976 committed
536
537
538
539
	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);
540
541
542
543
544
545
546
547
548
549

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

	return computed_value_Cmp_Confirm(cmp, left, right, relation);
}
550

551
552
553
554
555
556
557
558
559
560
561
/**
 * 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())
		return tarval_bad;
	return compute_cmp(cmp);
}

562
563
564
565
566
567
568
569
570
/**
 * 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)
{
	/* we can't construct Constb after lowering mode_b nodes */
571
	if (irg_is_constrained(get_irn_irg(cmp), IR_GRAPH_CONSTRAINT_MODEB_LOWERED))
572
573
574
575
576
		return tarval_bad;

	return compute_cmp(cmp);
}

577
/**
Michael Beck's avatar
Michael Beck committed
578
 * Calculate the value of an integer Div.
579
580
 * Special case: 0 / b
 */
581
static ir_tarval *do_computed_value_Div(const ir_node *div)
582
{
583
584
585
586
	const ir_node *a    = get_Div_left(div);
	const ir_node *b    = get_Div_right(div);
	const ir_mode *mode = get_Div_resmode(div);
	ir_tarval     *ta   = value_of(a);
Michael Beck's avatar
Michael Beck committed
587
	const ir_node *dummy;
588

Michael Beck's avatar
Michael Beck committed
589
	/* cannot optimize 0 / b = 0 because of NaN */
590
591
	if (!mode_is_float(mode)) {
		if (tarval_is_null(ta) && value_not_zero(b, &dummy))
Michael Beck's avatar
Michael Beck committed
592
			return ta;  /* 0 / b == 0 if b != 0 */
593
	}
yb9976's avatar
yb9976 committed
594
	ir_tarval *tb = value_of(b);
595
596
597
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_div(ta, tb);
	return tarval_bad;
598
}
Michael Beck's avatar
Michael Beck committed
599

600
601
602
603
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
604
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
605
{
Matthias Braun's avatar
Matthias Braun committed
606
	ir_tarval *tb = value_of(b);
607
608
609
610

	/* Compute a % 1 or c1 % c2 */
	if (tarval_is_one(tb))
		return get_mode_null(get_irn_mode(a));
yb9976's avatar
yb9976 committed
611
	ir_tarval *ta = value_of(a);
Michael Beck's avatar
Michael Beck committed
612
	if (ta != tarval_bad && tb != tarval_bad)
613
614
		return tarval_mod(ta, tb);
	return tarval_bad;
615
}
616

Michael Beck's avatar
Michael Beck committed
617
618
619
/**
 * Return the value of a Proj(Div).
 */
Matthias Braun's avatar
Matthias Braun committed
620
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
621
{
Michael Beck's avatar
Michael Beck committed
622
	long proj_nr = get_Proj_proj(n);
623
624
	if (proj_nr != pn_Div_res)
		return tarval_bad;
Michael Beck's avatar
Michael Beck committed
625

626
	return do_computed_value_Div(get_Proj_pred(n));
627
}
628

629
/**
Michael Beck's avatar
Michael Beck committed
630
 * Return the value of a Proj(Mod).
631
 */
Matthias Braun's avatar
Matthias Braun committed
632
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
633
{
Michael Beck's avatar
Michael Beck committed
634
	long proj_nr = get_Proj_proj(n);
Michael Beck's avatar
Michael Beck committed
635

Michael Beck's avatar
Michael Beck committed
636
	if (proj_nr == pn_Mod_res) {
Michael Beck's avatar
Michael Beck committed
637
638
		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
639
640
	}
	return tarval_bad;
641
}
642

Michael Beck's avatar
Michael Beck committed
643
/**
Michael Beck's avatar
Michael Beck committed
644
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
645
 */
Matthias Braun's avatar
Matthias Braun committed
646
static ir_tarval *computed_value_Proj(const ir_node *proj)
647
{
yb9976's avatar
yb9976 committed
648
	const ir_node *n = get_Proj_pred(proj);
Michael Beck's avatar
Michael Beck committed
649
650
651
652

	if (n->op->ops.computed_value_Proj != NULL)
		return n->op->ops.computed_value_Proj(proj);
	return tarval_bad;
653
}
Michael Beck's avatar
Michael Beck committed
654

655
656
657
/**
 * If the parameter n can be computed, return its value, else tarval_bad.
 * Performs constant folding.
658
659
 *
 * @param n  The node this should be evaluated
660
 */
Matthias Braun's avatar
Matthias Braun committed
661
ir_tarval *computed_value(const ir_node *n)
662
{
yb9976's avatar
yb9976 committed
663
	const vrp_attr *vrp = vrp_get_info(n);
664
	if (vrp != NULL && vrp->bits_set == vrp->bits_not_set)
665
		return vrp->bits_set;
666

Michael Beck's avatar
Michael Beck committed
667
668
669
	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
	return tarval_bad;
670
}
Christian Schäfer's avatar
Christian Schäfer committed
671

672
/**
673
 * Optimize operations that are commutative and have neutral 0,
674
 * so a op 0 = 0 op a = a.
675
 */
676
677
static ir_node *equivalent_node_neutral_zero(ir_node *n)
{
yb9976's avatar
yb9976 committed
678
679
680
681
682
	ir_node         *oldn = n;
	ir_node         *a    = get_binop_left(n);
	ir_node         *b    = get_binop_right(n);
	const ir_tarval *tv;
	ir_node         *on;
Michael Beck's avatar
Michael Beck committed
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699

	/* After running compute_node there is only one constant predecessor.
	   Find this predecessors value and remember the other node: */
	if ((tv = value_of(a)) != tarval_bad) {
		on = b;
	} else if ((tv = value_of(b)) != tarval_bad) {
		on = a;
	} else
		return n;

	/* If this predecessors constant value is zero, the operation is
	 * unnecessary. Remove it.
	 *
	 * Beware: If n is a Add, the mode of on and n might be different
	 * which happens in this rare construction: NULL + 3.
	 * Then, a Conv would be needed which we cannot include here.
	 */
700
701
	if (tarval_is_null(tv) && get_irn_mode(on) == get_irn_mode(n)) {
		n = on;
Michael Beck's avatar
Michael Beck committed
702

703
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
Michael Beck's avatar
Michael Beck committed
704
705
706
	}

	return n;
707
}
708

709
710
711
/**
 * Eor is commutative and has neutral 0.
 */
712
713
static ir_node *equivalent_node_Eor(ir_node *n)
{
714
715
716
717
718
	ir_node *oldn = n;

	n = equivalent_node_neutral_zero(n);
	if (n != oldn) return n;

yb9976's avatar
yb9976 committed
719
720
	ir_node *a = get_Eor_left(n);
	ir_node *b = get_Eor_right(n);
721

722
723
724
	if (is_Eor(a) || is_Or_Eor_Add(a)) {
		ir_node *aa = get_binop_left(a);
		ir_node *ab = get_binop_right(a);
725
726
727
728

		if (aa == b) {
			/* (a ^ b) ^ a -> b */
			n = ab;
Michael Beck's avatar
Michael Beck committed
729
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
730
			return n;
731
732
733
		} else if (ab == b) {
			/* (a ^ b) ^ b -> a */
			n = aa;
Michael Beck's avatar
Michael Beck committed
734
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
735
			return n;
736
		}
737
	}
738
739
740
	if (is_Eor(b) || is_Or_Eor_Add(b)) {
		ir_node *ba = get_binop_left(b);
		ir_node *bb = get_binop_right(b);
741
742
743
744

		if (ba == a) {
			/* a ^ (a ^ b) -> b */
			n = bb;
Michael Beck's avatar
Michael Beck committed
745
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
746
			return n;
747
748
749
		} else if (bb == a) {
			/* a ^ (b ^ a) -> b */
			n = ba;
Michael Beck's avatar
Michael Beck committed
750
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
751
			return n;
752
753
754
755
		}
	}
	return n;
}
756

757
758
759
760
761
/*
 * Optimize a - 0 and (a - x) + x (for modes with wrap-around).
 *
 * The second one looks strange, but this construct
 * is used heavily in the LCC sources :-).
762
763
764
 *
 * Beware: The Mode of an Add may be different than the mode of its
 * predecessors, so we could not return a predecessors in all cases.
765
 */
766
767
static ir_node *equivalent_node_Add(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
768
769
770
771
772
773
	ir_node *oldn = n;

	n = equivalent_node_neutral_zero(n);
	if (n != oldn)
		return n;

yb9976's avatar
yb9976 committed
774
775
	/* these optimizations are imprecise for floating point ops */
	ir_mode *mode = get_irn_mode(n);
776
777
	if (mode_is_float(mode) && !ir_imprecise_float_transforms_allowed())
		return n;
778

yb9976's avatar
yb9976 committed
779
780
	ir_node *left  = get_Add_left(n);
	ir_node *right = get_Add_right(n);
Michael Beck's avatar
Michael Beck committed
781

yb9976's avatar
yb9976 committed
782
783
	if (is_Sub(left) && get_Sub_right(left) == right) {
		/* (a - x) + x */
Michael Beck's avatar
Michael Beck committed
784

yb9976's avatar
yb9976 committed
785
786
787
788
		n = get_Sub_left(left);
		if (mode == get_irn_mode(n)) {
			DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
			return n;
Michael Beck's avatar
Michael Beck committed
789
790
		}
	}
yb9976's avatar
yb9976 committed
791
792
	if (is_Sub(right) && get_Sub_right(right) == left) {
		/* x + (a - x) */
Michael Beck's avatar
Michael Beck committed
793

yb9976's avatar
yb9976 committed
794
795
796
797
		n = get_Sub_left(right);
		if (mode == get_irn_mode(n)) {
			DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
			return n;
Michael Beck's avatar
Michael Beck committed
798
799
800
		}
	}
	return n;
801
}
802

803
/**
804
805
 * optimize operations that are not commutative but have neutral 0 on left,
 * so a op 0 = a.
806
 */
807
808
static ir_node *equivalent_node_left_zero(ir_node *n)
{
yb9976's avatar
yb9976 committed
809
810
811
	ir_node         *oldn = n;
	ir_node         *b    = get_binop_right(n);
	const ir_tarval *tb   = value_of(b);
812

813
	if (tarval_is_null(tb)) {
yb9976's avatar
yb9976 committed
814
		ir_node *a = get_binop_left(n);
Michael Beck's avatar
Michael Beck committed
815
		n = a;
816

Michael Beck's avatar
Michael Beck committed
817
818
819
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
	}
	return n;
820
}
821

822
823
824
825
826
/**
 * Optimize a - 0 and (a + x) - x (for modes with wrap-around).
 *
 * The second one looks strange, but this construct
 * is used heavily in the LCC sources :-).
827
828
829
 *
 * Beware: The Mode of a Sub may be different than the mode of its
 * predecessors, so we could not return a predecessors in all cases.
830
 */
831
832
static ir_node *equivalent_node_Sub(ir_node *n)
{
yb9976's avatar
yb9976 committed
833
834
	ir_node *oldn = n;
	ir_mode *mode = get_irn_mode(n);
Michael Beck's avatar
Michael Beck committed
835

yb9976's avatar
yb9976 committed
836
	/* these optimizations are imprecise for floating point ops */
837
838
	if (mode_is_float(mode) && !ir_imprecise_float_transforms_allowed())
		return n;
Michael Beck's avatar
Michael Beck committed
839

yb9976's avatar
yb9976 committed
840
841
	ir_node         *b  = get_Sub_right(n);
	const ir_tarval *tb = value_of(b);
Michael Beck's avatar
Michael Beck committed
842
843

	/* Beware: modes might be different */
844
	if (tarval_is_null(tb)) {
845
		ir_node *a = get_Sub_left(n);
Michael Beck's avatar
Michael Beck committed
846
847
848
849
850
851
852
		if (mode == get_irn_mode(a)) {
			n = a;

			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
		}
	}
	return n;
853
}
854
855


856
/**
yb9976's avatar
yb9976 committed
857
 * Optimize an "self-inverse unary op", i.e. op(op(n)) = n.
858
 *
859
860
861
862
 * @todo
 *   -(-a) == a, but might overflow two times.
 *   We handle it anyway here but the better way would be a
 *   flag. This would be needed for Pascal for instance.
863
 */
864
static ir_node *equivalent_node_involution(ir_node *n, int input)
865
{
Michael Beck's avatar
Michael Beck committed
866
	ir_node *oldn = n;
867
	ir_node *pred = get_irn_n(n, input);
Michael Beck's avatar
Michael Beck committed
868
	if (get_irn_op(pred) == get_irn_op(n)) {
869
		n = get_irn_n(pred, input);
870
		DBG_OPT_ALGSIM2(oldn, pred, n, FS_OPT_INVOLUTION);
Michael Beck's avatar
Michael Beck committed
871
872
	}
	return n;
873
}
874

875
876
877
878
879
880
881
882
883
884
static ir_node *equivalent_node_Minus(ir_node *n)
{
	return equivalent_node_involution(n, n_Minus_op);
}

static ir_node *equivalent_node_Not(ir_node *n)
{
	return equivalent_node_involution(n, n_Not_op);
}

885
886
887
/**
 * Optimize a * 1 = 1 * a = a.
 */
888
889
static ir_node *equivalent_node_Mul(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
890
	ir_node *oldn = n;
yb9976's avatar
yb9976 committed
891
	ir_node *a    = get_Mul_left(n);
Michael Beck's avatar
Michael Beck committed
892

Michael Beck's avatar
Michael Beck committed
893
894
	/* we can handle here only the n * n = n bit cases */
	if (get_irn_mode(n) == get_irn_mode(a)) {
895
896
897
898
		/*
		 * Mul is commutative and has again an other neutral element.
		 * Constants are place right, so check this case first.
		 */
yb9976's avatar
yb9976 committed
899
900
901
		ir_node         *b  = get_Mul_right(n);
		const ir_tarval *tb = value_of(b);
		if (tarval_is_one(tb)) {
Michael Beck's avatar
Michael Beck committed
902
903
			n = a;
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
904
		} else {
yb9976's avatar
yb9976 committed
905
906
			const ir_tarval *ta = value_of(a);
			if (tarval_is_one(ta)) {
907
908
909
				n = b;
				DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
			}
Michael Beck's avatar
Michael Beck committed
910
		}
Michael Beck's avatar
Michael Beck committed
911
912
	}
	return n;
913
}
914

Michael Beck's avatar
Michael Beck committed
915
916
917
/**
 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
 */
918
919