iropt.c 190 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
/**
 * @file
 * @brief   iropt --- optimizations intertwined with IR construction.
 * @author  Christian Schaefer, Goetz Lindenmaier, Michael Beck
Götz Lindenmaier's avatar
Götz Lindenmaier committed
24
 */
Matthias Braun's avatar
Matthias Braun committed
25
#include "config.h"
Michael Beck's avatar
Michael Beck committed
26
27

#include <string.h>
28
#include <stdbool.h>
Boris Boesler's avatar
added    
Boris Boesler committed
29

Michael Beck's avatar
Michael Beck committed
30
31
32
33
34
35
36
#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"
37
#include "irverify.h"
38
#include "iroptimize.h"
Michael Beck's avatar
Michael Beck committed
39
40
41
42
43
44
45
#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"
46
#include "opt_polymorphy.h"
Michael Beck's avatar
Michael Beck committed
47
#include "irtools.h"
48
#include "irhooks.h"
49
#include "array_t.h"
50
51
#include "vrp.h"
#include "firm_types.h"
52
#include "bitfiddle.h"
53
#include "be.h"
Christian Schäfer's avatar
Christian Schäfer committed
54

Götz Lindenmaier's avatar
Götz Lindenmaier committed
55
/* Make types visible to allow most efficient access */
56
#include "entity_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
57

58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
static bool is_Or_Eor_Add(const ir_node *node)
{
	if (is_Or(node) || is_Eor(node) || is_Add(node)) {
		ir_node  *left      = get_binop_left(node);
		ir_node  *right     = get_binop_right(node);
		vrp_attr *vrp_left  = vrp_get_info(left);
		vrp_attr *vrp_right = vrp_get_info(right);
		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;
}

74
75
76
/**
 * Returns the tarval of a Const node or tarval_bad for all other nodes.
 */
Matthias Braun's avatar
Matthias Braun committed
77
static ir_tarval *default_value_of(const ir_node *n)
78
{
79
80
81
82
83
84
85
86
	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;

Michael Beck's avatar
Michael Beck committed
87
/* * Set a new value_of function. */
88
89
void set_value_of_func(value_of_func func)
{
90
91
92
93
94
95
	if (func != NULL)
		value_of_ptr = func;
	else
		value_of_ptr = default_value_of;
}

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

104
/**
Michael Beck's avatar
Michael Beck committed
105
 * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
106
 */
Matthias Braun's avatar
Matthias Braun committed
107
static ir_tarval *computed_value_SymConst(const ir_node *n)
108
{
Michael Beck's avatar
Michael Beck committed
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
	ir_type   *type;
	ir_entity *ent;

	switch (get_SymConst_kind(n)) {
	case symconst_type_size:
		type = get_SymConst_type(n);
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_type_size_bytes(type), get_irn_mode(n));
		break;
	case symconst_type_align:
		type = get_SymConst_type(n);
		if (get_type_state(type) == layout_fixed)
			return new_tarval_from_long(get_type_alignment_bytes(type), get_irn_mode(n));
		break;
	case symconst_ofs_ent:
		ent  = get_SymConst_entity(n);
		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));
		break;
	default:
		break;
	}
	return tarval_bad;
133
}
Christian Schäfer's avatar
Christian Schäfer committed
134

Michael Beck's avatar
Michael Beck committed
135
/**
136
 * Return the value of an Add.
Michael Beck's avatar
Michael Beck committed
137
 */
Matthias Braun's avatar
Matthias Braun committed
138
static ir_tarval *computed_value_Add(const ir_node *n)
139
{
Michael Beck's avatar
Michael Beck committed
140
141
	ir_node *a = get_Add_left(n);
	ir_node *b = get_Add_right(n);
Christian Schäfer's avatar
Christian Schäfer committed
142

Matthias Braun's avatar
Matthias Braun committed
143
144
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
145

146
	if ((ta != tarval_bad) && (tb != tarval_bad))
Michael Beck's avatar
Michael Beck committed
147
		return tarval_add(ta, tb);
148

149
150
151
152
153
154
	/* 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
155
	return tarval_bad;
156
}
Christian Schäfer's avatar
Christian Schäfer committed
157

Michael Beck's avatar
Michael Beck committed
158
/**
159
 * Return the value of a Sub.
Michael Beck's avatar
Michael Beck committed
160
161
 * Special case: a - a
 */
Matthias Braun's avatar
Matthias Braun committed
162
static ir_tarval *computed_value_Sub(const ir_node *n)
163
{
Matthias Braun's avatar
Matthias Braun committed
164
165
166
167
168
	ir_mode   *mode = get_irn_mode(n);
	ir_node   *a    = get_Sub_left(n);
	ir_node   *b    = get_Sub_right(n);
	ir_tarval *ta;
	ir_tarval *tb;
Christian Schäfer's avatar
Christian Schäfer committed
169

170
171
172
173
174
175
	/* 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
176

Michael Beck's avatar
Michael Beck committed
177
178
	ta = value_of(a);
	tb = value_of(b);
179

180
181
	if ((ta != tarval_bad) && (tb != tarval_bad))
		return tarval_sub(ta, tb, mode);
182

Michael Beck's avatar
Michael Beck committed
183
	return tarval_bad;
184
}
185

186
187
188
189
/**
 * Return the value of a Carry.
 * Special : a op 0, 0 op b
 */
Matthias Braun's avatar
Matthias Braun committed
190
static ir_tarval *computed_value_Carry(const ir_node *n)
191
{
Matthias Braun's avatar
Matthias Braun committed
192
193
194
195
196
	ir_node   *a  = get_binop_left(n);
	ir_node   *b  = get_binop_right(n);
	ir_mode   *m  = get_irn_mode(n);
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
197
198
199
200
201
202
203
204
205

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		tarval_add(ta, tb);
		return tarval_carry() ? get_mode_one(m) : get_mode_null(m);
	} else {
		if (tarval_is_null(ta) || tarval_is_null(tb))
			return get_mode_null(m);
	}
	return tarval_bad;
206
}
207
208
209
210
211

/**
 * Return the value of a Borrow.
 * Special : a op 0
 */
Matthias Braun's avatar
Matthias Braun committed
212
static ir_tarval *computed_value_Borrow(const ir_node *n)
213
{
Matthias Braun's avatar
Matthias Braun committed
214
215
216
217
218
	ir_node   *a  = get_binop_left(n);
	ir_node   *b  = get_binop_right(n);
	ir_mode   *m  = get_irn_mode(n);
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
219
220

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
221
		return tarval_cmp(ta, tb) == ir_relation_less ? get_mode_one(m) : get_mode_null(m);
222
223
224
225
	} else if (tarval_is_null(ta)) {
		return get_mode_null(m);
	}
	return tarval_bad;
226
}
227

Michael Beck's avatar
Michael Beck committed
228
/**
229
 * Return the value of an unary Minus.
Michael Beck's avatar
Michael Beck committed
230
 */
Matthias Braun's avatar
Matthias Braun committed
231
static ir_tarval *computed_value_Minus(const ir_node *n)
232
{
Matthias Braun's avatar
Matthias Braun committed
233
234
	ir_node   *a  = get_Minus_op(n);
	ir_tarval *ta = value_of(a);
235

Michael Beck's avatar
Michael Beck committed
236
	if (ta != tarval_bad)
Michael Beck's avatar
Michael Beck committed
237
		return tarval_neg(ta);
238

Michael Beck's avatar
Michael Beck committed
239
	return tarval_bad;
240
}
241

Michael Beck's avatar
Michael Beck committed
242
/**
243
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
244
 */
Matthias Braun's avatar
Matthias Braun committed
245
static ir_tarval *computed_value_Mul(const ir_node *n)
246
{
Matthias Braun's avatar
Matthias Braun committed
247
248
249
250
251
	ir_node   *a  = get_Mul_left(n);
	ir_node   *b  = get_Mul_right(n);
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
	ir_mode   *mode;
Michael Beck's avatar
Michael Beck committed
252

Michael Beck's avatar
Michael Beck committed
253
254
255
256
257
258
259
260
	mode = get_irn_mode(n);
	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
261
262
		return tarval_mul(ta, tb);
	} else {
263
264
265
266
267
268
269
270
		/* 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
271
272
	}
	return tarval_bad;
273
}
274

Michael Beck's avatar
Michael Beck committed
275
/**
276
 * Return the value of an And.
Michael Beck's avatar
Michael Beck committed
277
278
 * Special case: a & 0, 0 & b
 */
Matthias Braun's avatar
Matthias Braun committed
279
static ir_tarval *computed_value_And(const ir_node *n)
280
{
Matthias Braun's avatar
Matthias Braun committed
281
282
283
284
	ir_node   *a  = get_And_left(n);
	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
285
286
287
288

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_and (ta, tb);
	}
289
290
291
292
293
294
295
296
297
298

	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
299
	return tarval_bad;
300
}
301

Michael Beck's avatar
Michael Beck committed
302
/**
303
 * Return the value of an Or.
Michael Beck's avatar
Michael Beck committed
304
305
 * Special case: a | 1...1, 1...1 | b
 */
Matthias Braun's avatar
Matthias Braun committed
306
static ir_tarval *computed_value_Or(const ir_node *n)
307
{
Matthias Braun's avatar
Matthias Braun committed
308
309
310
311
	ir_node   *a  = get_Or_left(n);
	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
312
313
314

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_or (ta, tb);
315
316
317
318
319
320
321
322
323
	}

	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
324
325
	}
	return tarval_bad;
326
}
327

Michael Beck's avatar
Michael Beck committed
328
/**
329
 * Return the value of an Eor.
Michael Beck's avatar
Michael Beck committed
330
 */
Matthias Braun's avatar
Matthias Braun committed
331
static ir_tarval *computed_value_Eor(const ir_node *n)
332
{
Michael Beck's avatar
Michael Beck committed
333
334
	ir_node *a = get_Eor_left(n);
	ir_node *b = get_Eor_right(n);
335

Matthias Braun's avatar
Matthias Braun committed
336
	ir_tarval *ta, *tb;
Michael Beck's avatar
Michael Beck committed
337

Michael Beck's avatar
Michael Beck committed
338
339
	if (a == b)
		return get_mode_null(get_irn_mode(n));
340
341
342
343
344
	/* 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
345

Michael Beck's avatar
Michael Beck committed
346
347
	ta = value_of(a);
	tb = value_of(b);
348

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

Michael Beck's avatar
Michael Beck committed
355
/**
356
 * Return the value of a Not.
Michael Beck's avatar
Michael Beck committed
357
 */
Matthias Braun's avatar
Matthias Braun committed
358
static ir_tarval *computed_value_Not(const ir_node *n)
359
{
Matthias Braun's avatar
Matthias Braun committed
360
361
	ir_node   *a  = get_Not_op(n);
	ir_tarval *ta = value_of(a);
362

Michael Beck's avatar
Michael Beck committed
363
364
	if (ta != tarval_bad)
		return tarval_not(ta);
365

Michael Beck's avatar
Michael Beck committed
366
	return tarval_bad;
367
}
368

369
/**
yb9976's avatar
yb9976 committed
370
 * Tests whether a shift shifts more bits than available in the mode
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
 */
static bool is_oversize_shift(const ir_node *n)
{
	ir_node   *count = get_binop_right(n);
	ir_mode   *mode  = get_irn_mode(n);
	ir_tarval *tv    = value_of(count);
	long       modulo_shift;
	long       shiftval;
	if (tv == tarval_bad)
		return false;
	if (!tarval_is_long(tv))
		return false;
	shiftval     = get_tarval_long(tv);
	modulo_shift = get_mode_modulo_shift(mode);
	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
391
/**
392
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
393
 */
Matthias Braun's avatar
Matthias Braun committed
394
static ir_tarval *computed_value_Shl(const ir_node *n)
395
{
Michael Beck's avatar
Michael Beck committed
396
397
	ir_node *a = get_Shl_left(n);
	ir_node *b = get_Shl_right(n);
398

Matthias Braun's avatar
Matthias Braun committed
399
400
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
401

Michael Beck's avatar
Michael Beck committed
402
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
403
		return tarval_shl(ta, tb);
Michael Beck's avatar
Michael Beck committed
404
	}
405
406
407
408

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

Michael Beck's avatar
Michael Beck committed
409
	return tarval_bad;
410
}
411

Michael Beck's avatar
Michael Beck committed
412
/**
413
 * Return the value of a Shr.
Michael Beck's avatar
Michael Beck committed
414
 */
Matthias Braun's avatar
Matthias Braun committed
415
static ir_tarval *computed_value_Shr(const ir_node *n)
416
{
Michael Beck's avatar
Michael Beck committed
417
418
	ir_node *a = get_Shr_left(n);
	ir_node *b = get_Shr_right(n);
419

Matthias Braun's avatar
Matthias Braun committed
420
421
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
422

Michael Beck's avatar
Michael Beck committed
423
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
424
		return tarval_shr(ta, tb);
Michael Beck's avatar
Michael Beck committed
425
	}
426
427
428
	if (is_oversize_shift(n))
		return get_mode_null(get_irn_mode(n));

Michael Beck's avatar
Michael Beck committed
429
	return tarval_bad;
430
}
431

Michael Beck's avatar
Michael Beck committed
432
/**
433
 * Return the value of a Shrs.
Michael Beck's avatar
Michael Beck committed
434
 */
Matthias Braun's avatar
Matthias Braun committed
435
static ir_tarval *computed_value_Shrs(const ir_node *n)
436
{
Michael Beck's avatar
Michael Beck committed
437
438
	ir_node *a = get_Shrs_left(n);
	ir_node *b = get_Shrs_right(n);
439

Matthias Braun's avatar
Matthias Braun committed
440
441
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
442

Michael Beck's avatar
Michael Beck committed
443
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
444
		return tarval_shrs(ta, tb);
Michael Beck's avatar
Michael Beck committed
445
446
	}
	return tarval_bad;
447
}
448

Michael Beck's avatar
Michael Beck committed
449
/**
450
 * Return the value of a Rotl.
Michael Beck's avatar
Michael Beck committed
451
 */
Matthias Braun's avatar
Matthias Braun committed
452
static ir_tarval *computed_value_Rotl(const ir_node *n)
453
{
454
455
	ir_node *a = get_Rotl_left(n);
	ir_node *b = get_Rotl_right(n);
456

Matthias Braun's avatar
Matthias Braun committed
457
458
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
459

Michael Beck's avatar
Michael Beck committed
460
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
461
		return tarval_rotl(ta, tb);
Michael Beck's avatar
Michael Beck committed
462
463
	}
	return tarval_bad;
464
}
465

466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
bool ir_zero_when_converted(const ir_node *node, ir_mode *dest_mode)
{
	ir_mode *mode = get_irn_mode(node);
	if (get_mode_arithmetic(mode) != irma_twos_complement
	    || get_mode_arithmetic(dest_mode) != irma_twos_complement)
	    return false;

	if (is_Shl(node)) {
		ir_node *count = get_Shl_right(node);
		if (is_Const(count)) {
			ir_tarval *tv = get_Const_tarval(count);
			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
497
/**
498
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
499
 */
Matthias Braun's avatar
Matthias Braun committed
500
static ir_tarval *computed_value_Conv(const ir_node *n)
501
{
502
503
504
	ir_node   *a    = get_Conv_op(n);
	ir_tarval *ta   = value_of(a);
	ir_mode   *mode = get_irn_mode(n);
505

Michael Beck's avatar
Michael Beck committed
506
507
	if (ta != tarval_bad)
		return tarval_convert_to(ta, get_irn_mode(n));
508

509
510
511
	if (ir_zero_when_converted(a, mode))
		return get_mode_null(mode);

Michael Beck's avatar
Michael Beck committed
512
	return tarval_bad;
513
}
514

Michael Beck's avatar
Michael Beck committed
515
516
517
518
/**
 * 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
519
static ir_tarval *computed_value_Mux(const ir_node *n)
520
{
Michael Beck's avatar
Michael Beck committed
521
	ir_node *sel = get_Mux_sel(n);
Matthias Braun's avatar
Matthias Braun committed
522
	ir_tarval *ts = value_of(sel);
Michael Beck's avatar
Michael Beck committed
523
524
525
526
527
528
529
530
531
532

	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;
533
}
Michael Beck's avatar
Michael Beck committed
534
535
536
537
538

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
Matthias Braun's avatar
Matthias Braun committed
539
static ir_tarval *computed_value_Confirm(const ir_node *n)
540
{
541
	if (get_Confirm_relation(n) == ir_relation_equal) {
Matthias Braun's avatar
Matthias Braun committed
542
		ir_tarval *tv = value_of(get_Confirm_bound(n));
543
544
		if (tv != tarval_bad)
			return tv;
Michael Beck's avatar
Michael Beck committed
545
546
	}
	return value_of(get_Confirm_value(n));
547
}
Michael Beck's avatar
Michael Beck committed
548

549
/**
550
551
 * gives a (conservative) estimation of possible relation when comparing
 * left+right
552
 */
553
554
ir_relation ir_get_possible_cmp_relations(const ir_node *left,
                                          const ir_node *right)
555
{
556
557
558
559
560
561
	ir_relation possible = ir_relation_true;
	ir_tarval  *tv_l     = value_of(left);
	ir_tarval  *tv_r     = value_of(right);
	ir_mode    *mode     = get_irn_mode(left);
	ir_tarval  *min      = mode == mode_b ? tarval_b_false : get_mode_min(mode);
	ir_tarval  *max      = mode == mode_b ? tarval_b_true  : get_mode_max(mode);
562

563
	/* both values known - evaluate them */
564
	if ((tv_l != tarval_bad) && (tv_r != tarval_bad)) {
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
		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;
590
591
592
593
594
595
596
597
598
	/* 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;
	}
599
600
601

	return possible;
}
602

603
static ir_tarval *compute_cmp(const ir_node *cmp)
604
605
606
{
	ir_node    *left     = get_Cmp_left(cmp);
	ir_node    *right    = get_Cmp_right(cmp);
607
	ir_relation possible = ir_get_possible_cmp_relations(left, right);
608
609
610
611
612
613
614
615
616
617
618
	ir_relation relation = get_Cmp_relation(cmp);

	/* 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);
}
619

620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
/**
 * 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 */
	if (is_irg_state(get_irn_irg(cmp), IR_GRAPH_STATE_MODEB_LOWERED))
		return tarval_bad;

	return compute_cmp(cmp);
}

635
/**
Michael Beck's avatar
Michael Beck committed
636
 * Calculate the value of an integer Div.
637
638
 * Special case: 0 / b
 */
639
static ir_tarval *do_computed_value_Div(const ir_node *div)
640
{
641
642
643
644
	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);
Matthias Braun's avatar
Matthias Braun committed
645
	ir_tarval     *tb;
Michael Beck's avatar
Michael Beck committed
646
	const ir_node *dummy;
647

Michael Beck's avatar
Michael Beck committed
648
	/* cannot optimize 0 / b = 0 because of NaN */
649
650
	if (!mode_is_float(mode)) {
		if (tarval_is_null(ta) && value_not_zero(b, &dummy))
Michael Beck's avatar
Michael Beck committed
651
			return ta;  /* 0 / b == 0 if b != 0 */
652
	}
653
654
655
656
	tb = value_of(b);
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_div(ta, tb);
	return tarval_bad;
657
}
Michael Beck's avatar
Michael Beck committed
658

659
660
661
662
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
663
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
664
{
Matthias Braun's avatar
Matthias Braun committed
665
666
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
667
668
669
670

	/* Compute a % 1 or c1 % c2 */
	if (tarval_is_one(tb))
		return get_mode_null(get_irn_mode(a));
Michael Beck's avatar
Michael Beck committed
671
	if (ta != tarval_bad && tb != tarval_bad)
672
673
		return tarval_mod(ta, tb);
	return tarval_bad;
674
}
675

Michael Beck's avatar
Michael Beck committed
676
677
678
/**
 * Return the value of a Proj(Div).
 */
Matthias Braun's avatar
Matthias Braun committed
679
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
680
{
Michael Beck's avatar
Michael Beck committed
681
	long proj_nr = get_Proj_proj(n);
682
683
	if (proj_nr != pn_Div_res)
		return tarval_bad;
Michael Beck's avatar
Michael Beck committed
684

685
	return do_computed_value_Div(get_Proj_pred(n));
686
}
687

688
/**
Michael Beck's avatar
Michael Beck committed
689
 * Return the value of a Proj(Mod).
690
 */
Matthias Braun's avatar
Matthias Braun committed
691
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
692
{
Michael Beck's avatar
Michael Beck committed
693
	long proj_nr = get_Proj_proj(n);
Michael Beck's avatar
Michael Beck committed
694

Michael Beck's avatar
Michael Beck committed
695
	if (proj_nr == pn_Mod_res) {
Michael Beck's avatar
Michael Beck committed
696
697
		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
698
699
	}
	return tarval_bad;
700
}
701

Michael Beck's avatar
Michael Beck committed
702
/**
Michael Beck's avatar
Michael Beck committed
703
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
704
 */
Matthias Braun's avatar
Matthias Braun committed
705
static ir_tarval *computed_value_Proj(const ir_node *proj)
706
{
Michael Beck's avatar
Michael Beck committed
707
708
709
710
711
	ir_node *n = get_Proj_pred(proj);

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

714
715
716
/**
 * If the parameter n can be computed, return its value, else tarval_bad.
 * Performs constant folding.
717
718
 *
 * @param n  The node this should be evaluated
719
 */
Matthias Braun's avatar
Matthias Braun committed
720
ir_tarval *computed_value(const ir_node *n)
721
{
722
	vrp_attr *vrp = vrp_get_info(n);
723
	if (vrp != NULL && vrp->bits_set == vrp->bits_not_set)
724
		return vrp->bits_set;
725

Michael Beck's avatar
Michael Beck committed
726
727
728
	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
	return tarval_bad;
729
}
Christian Schäfer's avatar
Christian Schäfer committed
730

731
/**
732
 * Set the default computed_value evaluator in an ir_op_ops.
Michael Beck's avatar
Michael Beck committed
733
734
735
736
737
738
 *
 * @param code   the opcode for the default operation
 * @param ops    the operations initialized
 *
 * @return
 *    The operations.
739
 */
740
741
static ir_op_ops *firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops)
{
Michael Beck's avatar
Michael Beck committed
742
743
744
745
746
747
748
#define CASE(a)                                        \
	case iro_##a:                                      \
		ops->computed_value      = computed_value_##a; \
		break
#define CASE_PROJ(a)                                        \
	case iro_##a:                                           \
		ops->computed_value_Proj = computed_value_Proj_##a; \
Michael Beck's avatar
Michael Beck committed
749
750
751
752
		break

	switch (code) {
	CASE(Add);
753
	CASE(And);
754
	CASE(Borrow);
755
756
757
758
759
760
	CASE(Carry);
	CASE(Cmp);
	CASE(Confirm);
	CASE(Const);
	CASE(Conv);
	CASE(Eor);
Michael Beck's avatar
Michael Beck committed
761
762
	CASE(Minus);
	CASE(Mul);
763
	CASE(Mux);
Michael Beck's avatar
Michael Beck committed
764
	CASE(Not);
765
766
767
	CASE(Or);
	CASE(Proj);
	CASE(Rotl);
Michael Beck's avatar
Michael Beck committed
768
769
770
	CASE(Shl);
	CASE(Shr);
	CASE(Shrs);
771
772
	CASE(Sub);
	CASE(SymConst);
Michael Beck's avatar
Michael Beck committed
773
774
	CASE_PROJ(Div);
	CASE_PROJ(Mod);
Michael Beck's avatar
Michael Beck committed
775
	default:
776
777
		/* leave NULL */
		break;
Michael Beck's avatar
Michael Beck committed
778
779
780
	}

	return ops;
Michael Beck's avatar
Michael Beck committed
781
#undef CASE_PROJ
782
#undef CASE
783
}
Christian Schäfer's avatar
Christian Schäfer committed
784

785
/**
786
 * Optimize operations that are commutative and have neutral 0,
787
 * so a op 0 = 0 op a = a.
788
 */
789
790
static ir_node *equivalent_node_neutral_zero(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
791
792
793
794
795
	ir_node *oldn = n;

	ir_node *a = get_binop_left(n);
	ir_node *b = get_binop_right(n);

Matthias Braun's avatar
Matthias Braun committed
796
	ir_tarval *tv;
Michael Beck's avatar
Michael Beck committed
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
	ir_node *on;

	/* 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.
	 */
815
816
	if (tarval_is_null(tv) && get_irn_mode(on) == get_irn_mode(n)) {
		n = on;
Michael Beck's avatar
Michael Beck committed
817

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

	return n;
822
}
823

824
825
826
/**
 * Eor is commutative and has neutral 0.
 */
827
828
static ir_node *equivalent_node_Eor(ir_node *n)
{
829
830
831
832
833
834
835
836
837
838
	ir_node *oldn = n;
	ir_node *a;
	ir_node *b;

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

	a = get_Eor_left(n);
	b = get_Eor_right(n);

839
840
841
	if (is_Eor(a) || is_Or_Eor_Add(a)) {
		ir_node *aa = get_binop_left(a);
		ir_node *ab = get_binop_right(a);
842
843
844
845

		if (aa == b) {
			/* (a ^ b) ^ a -> b */
			n = ab;
Michael Beck's avatar
Michael Beck committed
846
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
847
			return n;
848
849
850
		} else if (ab == b) {
			/* (a ^ b) ^ b -> a */
			n = aa;
Michael Beck's avatar
Michael Beck committed
851
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
852
			return n;
853
		}
854
	}
855
856
857
	if (is_Eor(b) || is_Or_Eor_Add(b)) {
		ir_node *ba = get_binop_left(b);
		ir_node *bb = get_binop_right(b);
858
859
860
861

		if (ba == a) {
			/* a ^ (a ^ b) -> b */
			n = bb;
Michael Beck's avatar
Michael Beck committed
862
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
863
			return n;
864
865
866
		} else if (bb == a) {
			/* a ^ (b ^ a) -> b */
			n = ba;
Michael Beck's avatar
Michael Beck committed
867
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
868
			return n;
869
870
871
872
		}
	}
	return n;
}
873

874
875
876
877
878
/*
 * 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 :-).
879
880
881
 *
 * 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.
882
 */
883
884
static ir_node *equivalent_node_Add(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
885
886
887
888
889
890
891
892
	ir_node *oldn = n;
	ir_node *left, *right;
	ir_mode *mode = get_irn_mode(n);

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

893
	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
894
895
896
897
898
	if (mode_is_float(mode)) {
		ir_graph *irg = get_irn_irg(n);
		if (get_irg_fp_model(irg) & fp_strict_algebraic)
			return n;
	}
899

Michael Beck's avatar
Michael Beck committed
900
901
902
	left  = get_Add_left(n);
	right = get_Add_right(n);

903
	if (is_Sub(left)) {
Michael Beck's avatar
Michael Beck committed
904
905
906
907
908
909
910
911
912
913
		if (get_Sub_right(left) == right) {
			/* (a - x) + x */

			n = get_Sub_left(left);
			if (mode == get_irn_mode(n)) {
				DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
				return n;
			}
		}
	}
914
	if (is_Sub(right)) {
Michael Beck's avatar
Michael Beck committed
915
916
917
918
919
920
921
922
923
924
925
		if (get_Sub_right(right) == left) {
			/* x + (a - x) */

			n = get_Sub_left(right);
			if (mode == get_irn_mode(n)) {
				DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
				return n;
			}
		}
	}
	return n;
926
}
927

928
/**
929
930
 * optimize operations that are not commutative but have neutral 0 on left,
 * so a op 0 = a.
931
 */
932
933
static ir_node *equivalent_node_left_zero(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
934
	ir_node *oldn = n;
935

Matthias Braun's avatar
Matthias Braun committed
936
937
938
	ir_node   *a  = get_binop_left(n);
	ir_node   *b  = get_binop_right(n);
	ir_tarval *tb = value_of(b);
939

940
	if (tarval_is_null(tb)) {
Michael Beck's avatar
Michael Beck committed
941
		n = a;
942

Michael Beck's avatar
Michael Beck committed
943
944
945
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
	}
	return n;
946
}
947

948
949
950
#define equivalent_node_Shl   equivalent_node_left_zero
#define equivalent_node_Shr   equivalent_node_left_zero
#define equivalent_node_Shrs  equivalent_node_left_zero
951
#define equivalent_node_Rotl  equivalent_node_left_zero
952

953
954
955
956
957
/**
 * 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 :-).
958
959
960
 *
 * 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.
961
 */
962
963
static ir_node *equivalent_node_Sub(ir_node *n)
{
Matthias Braun's avatar
Matthias Braun committed
964
965
966
967
	ir_node   *oldn = n;
	ir_node   *b;
	ir_mode   *mode = get_irn_mode(n);
	ir_tarval *tb;
Michael Beck's avatar
Michael Beck committed
968
969

	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
970
971
972
973
974
	if (mode_is_float(mode)) {
		ir_graph *irg = get_irn_irg(n);
		if (get_irg_fp_model(irg) & fp_strict_algebraic)
			return n;
	}
Michael Beck's avatar
Michael Beck committed