iropt.c 188 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"
Michael Beck's avatar
Michael Beck committed
46
#include "irtools.h"
47
#include "irhooks.h"
48
#include "array_t.h"
49
50
#include "vrp.h"
#include "firm_types.h"
51
#include "bitfiddle.h"
52
#include "be.h"
Christian Schäfer's avatar
Christian Schäfer committed
53

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

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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;
}

73
74
75
/**
 * Returns the tarval of a Const node or tarval_bad for all other nodes.
 */
Matthias Braun's avatar
Matthias Braun committed
76
static ir_tarval *default_value_of(const ir_node *n)
77
{
78
79
80
81
82
83
84
85
	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
86
/* * Set a new value_of function. */
87
88
void set_value_of_func(value_of_func func)
{
89
90
91
92
93
94
	if (func != NULL)
		value_of_ptr = func;
	else
		value_of_ptr = default_value_of;
}

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

103
/**
Michael Beck's avatar
Michael Beck committed
104
 * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
105
 */
Matthias Braun's avatar
Matthias Braun committed
106
static ir_tarval *computed_value_SymConst(const ir_node *n)
107
{
Michael Beck's avatar
Michael Beck committed
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
	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;
132
}
Christian Schäfer's avatar
Christian Schäfer committed
133

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

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

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

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

Michael Beck's avatar
Michael Beck committed
157
/**
158
 * Return the value of a Sub.
Michael Beck's avatar
Michael Beck committed
159
160
 * Special case: a - a
 */
Matthias Braun's avatar
Matthias Braun committed
161
static ir_tarval *computed_value_Sub(const ir_node *n)
162
{
Matthias Braun's avatar
Matthias Braun committed
163
164
165
166
167
	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
168

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

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

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

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

185
186
187
188
/**
 * Return the value of a Carry.
 * Special : a op 0, 0 op b
 */
Matthias Braun's avatar
Matthias Braun committed
189
static ir_tarval *computed_value_Carry(const ir_node *n)
190
{
Matthias Braun's avatar
Matthias Braun committed
191
192
193
194
195
	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);
196
197
198
199
200
201
202
203
204

	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;
205
}
206
207
208
209
210

/**
 * Return the value of a Borrow.
 * Special : a op 0
 */
Matthias Braun's avatar
Matthias Braun committed
211
static ir_tarval *computed_value_Borrow(const ir_node *n)
212
{
Matthias Braun's avatar
Matthias Braun committed
213
214
215
216
217
	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);
218
219

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

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

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

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

Michael Beck's avatar
Michael Beck committed
241
/**
242
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
243
 */
Matthias Braun's avatar
Matthias Braun committed
244
static ir_tarval *computed_value_Mul(const ir_node *n)
245
{
Matthias Braun's avatar
Matthias Braun committed
246
247
248
249
250
	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
251

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

368
/**
yb9976's avatar
yb9976 committed
369
 * Tests whether a shift shifts more bits than available in the mode
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
 */
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
390
/**
391
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
392
 */
Matthias Braun's avatar
Matthias Braun committed
393
static ir_tarval *computed_value_Shl(const ir_node *n)
394
{
Michael Beck's avatar
Michael Beck committed
395
396
	ir_node *a = get_Shl_left(n);
	ir_node *b = get_Shl_right(n);
397

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

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

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

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

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

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

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

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

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

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

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

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

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

Michael Beck's avatar
Michael Beck committed
459
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
460
		return tarval_rotl(ta, tb);
Michael Beck's avatar
Michael Beck committed
461
462
	}
	return tarval_bad;
463
}
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
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
496
/**
497
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
498
 */
Matthias Braun's avatar
Matthias Braun committed
499
static ir_tarval *computed_value_Conv(const ir_node *n)
500
{
501
502
503
	ir_node   *a    = get_Conv_op(n);
	ir_tarval *ta   = value_of(a);
	ir_mode   *mode = get_irn_mode(n);
504

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

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

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

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

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

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

548
/**
549
550
 * gives a (conservative) estimation of possible relation when comparing
 * left+right
551
 */
552
553
ir_relation ir_get_possible_cmp_relations(const ir_node *left,
                                          const ir_node *right)
554
{
555
556
557
558
559
560
	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);
561

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

	return possible;
}
601

602
static ir_tarval *compute_cmp(const ir_node *cmp)
603
604
605
{
	ir_node    *left     = get_Cmp_left(cmp);
	ir_node    *right    = get_Cmp_right(cmp);
606
	ir_relation possible = ir_get_possible_cmp_relations(left, right);
607
608
609
610
611
612
613
614
615
616
617
	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);
}
618

619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
/**
 * 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);
}

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

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

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

	/* 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
670
	if (ta != tarval_bad && tb != tarval_bad)
671
672
		return tarval_mod(ta, tb);
	return tarval_bad;
673
}
674

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

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

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

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

Michael Beck's avatar
Michael Beck committed
701
/**
Michael Beck's avatar
Michael Beck committed
702
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
703
 */
Matthias Braun's avatar
Matthias Braun committed
704
static ir_tarval *computed_value_Proj(const ir_node *proj)
705
{
Michael Beck's avatar
Michael Beck committed
706
707
708
709
710
	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;
711
}
Michael Beck's avatar
Michael Beck committed
712

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

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

730
void firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops)
731
{
Michael Beck's avatar
Michael Beck committed
732
733
734
735
736
737
738
#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
739
740
741
742
		break

	switch (code) {
	CASE(Add);
743
	CASE(And);
744
	CASE(Borrow);
745
746
747
748
749
750
	CASE(Carry);
	CASE(Cmp);
	CASE(Confirm);
	CASE(Const);
	CASE(Conv);
	CASE(Eor);
Michael Beck's avatar
Michael Beck committed
751
752
	CASE(Minus);
	CASE(Mul);
753
	CASE(Mux);
Michael Beck's avatar
Michael Beck committed
754
	CASE(Not);
755
756
757
	CASE(Or);
	CASE(Proj);
	CASE(Rotl);
Michael Beck's avatar
Michael Beck committed
758
759
760
	CASE(Shl);
	CASE(Shr);
	CASE(Shrs);
761
762
	CASE(Sub);
	CASE(SymConst);
Michael Beck's avatar
Michael Beck committed
763
764
	CASE_PROJ(Div);
	CASE_PROJ(Mod);
Michael Beck's avatar
Michael Beck committed
765
	default:
766
767
		/* leave NULL */
		break;
Michael Beck's avatar
Michael Beck committed
768
	}
Michael Beck's avatar
Michael Beck committed
769
#undef CASE_PROJ
770
#undef CASE
771
}
Christian Schäfer's avatar
Christian Schäfer committed
772

773
/**
774
 * Optimize operations that are commutative and have neutral 0,
775
 * so a op 0 = 0 op a = a.
776
 */
777
778
static ir_node *equivalent_node_neutral_zero(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
779
780
781
782
783
	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
784
	ir_tarval *tv;
Michael Beck's avatar
Michael Beck committed
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
	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.
	 */
803
804
	if (tarval_is_null(tv) && get_irn_mode(on) == get_irn_mode(n)) {
		n = on;
Michael Beck's avatar
Michael Beck committed
805

806
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
Michael Beck's avatar
Michael Beck committed
807
808
809
	}

	return n;
810
}
811

812
813
814
/**
 * Eor is commutative and has neutral 0.
 */
815
816
static ir_node *equivalent_node_Eor(ir_node *n)
{
817
818
819
820
821
822
823
824
825
826
	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);

827
828
829
	if (is_Eor(a) || is_Or_Eor_Add(a)) {
		ir_node *aa = get_binop_left(a);
		ir_node *ab = get_binop_right(a);
830
831
832
833

		if (aa == b) {
			/* (a ^ b) ^ a -> b */
			n = ab;
Michael Beck's avatar
Michael Beck committed
834
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
835
			return n;
836
837
838
		} else if (ab == b) {
			/* (a ^ b) ^ b -> a */
			n = aa;
Michael Beck's avatar
Michael Beck committed
839
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
840
			return n;
841
		}
842
	}
843
844
845
	if (is_Eor(b) || is_Or_Eor_Add(b)) {
		ir_node *ba = get_binop_left(b);
		ir_node *bb = get_binop_right(b);
846
847
848
849

		if (ba == a) {
			/* a ^ (a ^ b) -> b */
			n = bb;
Michael Beck's avatar
Michael Beck committed
850
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
851
			return n;
852
853
854
		} else if (bb == a) {
			/* a ^ (b ^ a) -> b */
			n = ba;
Michael Beck's avatar
Michael Beck committed
855
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
856
			return n;
857
858
859
860
		}
	}
	return n;
}
861

862
863
864
865
866
/*
 * 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 :-).
867
868
869
 *
 * 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.
870
 */
871
872
static ir_node *equivalent_node_Add(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
873
874
875
876
877
878
879
880
	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;

881
	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
882
883
884
885
886
	if (mode_is_float(mode)) {
		ir_graph *irg = get_irn_irg(n);
		if (get_irg_fp_model(irg) & fp_strict_algebraic)
			return n;
	}
887

Michael Beck's avatar
Michael Beck committed
888
889
890
	left  = get_Add_left(n);
	right = get_Add_right(n);

891
	if (is_Sub(left)) {
Michael Beck's avatar
Michael Beck committed
892
893
894
895
896
897
898
899
900
901
		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;
			}
		}
	}
902
	if (is_Sub(right)) {
Michael Beck's avatar
Michael Beck committed
903
904
905
906
907
908
909
910
911
912
913
		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;
914
}
915

916
/**
917
918
 * optimize operations that are not commutative but have neutral 0 on left,
 * so a op 0 = a.
919
 */
920
921
static ir_node *equivalent_node_left_zero(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
922
	ir_node *oldn = n;
923

Matthias Braun's avatar
Matthias Braun committed
924
925
926
	ir_node   *a  = get_binop_left(n);
	ir_node   *b  = get_binop_right(n);
	ir_tarval *tb = value_of(b);
927

928
	if (tarval_is_null(tb)) {
Michael Beck's avatar
Michael Beck committed
929
		n = a;
930

Michael Beck's avatar
Michael Beck committed
931
932
933
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
	}
	return n;
934
}
935

936
937
938
#define equivalent_node_Shl   equivalent_node_left_zero
#define equivalent_node_Shr   equivalent_node_left_zero
#define equivalent_node_Shrs  equivalent_node_left_zero
939
#define equivalent_node_Rotl  equivalent_node_left_zero
940

941
942
943
944
945
/**
 * 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 :-).
946
947
948
 *
 * 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.
949
 */
950
951
static ir_node *equivalent_node_Sub(ir_node *n)
{
Matthias Braun's avatar
Matthias Braun committed
952
953
954
955
	ir_node   *oldn = n;
	ir_node   *b;
	ir_mode   *mode = get_irn_mode(n);
	ir_tarval *tb;
Michael Beck's avatar
Michael Beck committed
956
957

	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
958
959
960
961
962
	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
963

964
965
	b  = get_Sub_right(n);
	tb = value_of(b);
Michael Beck's avatar
Michael Beck committed
966
967

	/* Beware: modes might be different */
968
	if (tarval_is_null(tb)) {
969
		ir_node