iropt.c 183 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"
53
#include "error.h"
Christian Schäfer's avatar
Christian Schäfer committed
54

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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	return possible;
}
600

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

618
619
620
621
622
623
624
625
626
627
628
/**
 * 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);
}

629
630
631
632
633
634
635
636
637
/**
 * 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 */
638
	if (irg_is_constrained(get_irn_irg(cmp), IR_GRAPH_CONSTRAINT_MODEB_LOWERED))
639
640
641
642
643
		return tarval_bad;

	return compute_cmp(cmp);
}

644
/**
Michael Beck's avatar
Michael Beck committed
645
 * Calculate the value of an integer Div.
646
647
 * Special case: 0 / b
 */
648
static ir_tarval *do_computed_value_Div(const ir_node *div)
649
{
650
651
652
653
	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
654
	ir_tarval     *tb;
Michael Beck's avatar
Michael Beck committed
655
	const ir_node *dummy;
656

Michael Beck's avatar
Michael Beck committed
657
	/* cannot optimize 0 / b = 0 because of NaN */
658
659
	if (!mode_is_float(mode)) {
		if (tarval_is_null(ta) && value_not_zero(b, &dummy))
Michael Beck's avatar
Michael Beck committed
660
			return ta;  /* 0 / b == 0 if b != 0 */
661
	}
662
663
664
665
	tb = value_of(b);
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_div(ta, tb);
	return tarval_bad;
666
}
Michael Beck's avatar
Michael Beck committed
667

668
669
670
671
/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Matthias Braun's avatar
Matthias Braun committed
672
static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
673
{
Matthias Braun's avatar
Matthias Braun committed
674
675
	ir_tarval *ta = value_of(a);
	ir_tarval *tb = value_of(b);
676
677
678
679

	/* 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
680
	if (ta != tarval_bad && tb != tarval_bad)
681
682
		return tarval_mod(ta, tb);
	return tarval_bad;
683
}
684

Michael Beck's avatar
Michael Beck committed
685
686
687
/**
 * Return the value of a Proj(Div).
 */
Matthias Braun's avatar
Matthias Braun committed
688
static ir_tarval *computed_value_Proj_Div(const ir_node *n)
689
{
Michael Beck's avatar
Michael Beck committed
690
	long proj_nr = get_Proj_proj(n);
691
692
	if (proj_nr != pn_Div_res)
		return tarval_bad;
Michael Beck's avatar
Michael Beck committed
693

694
	return do_computed_value_Div(get_Proj_pred(n));
695
}
696

697
/**
Michael Beck's avatar
Michael Beck committed
698
 * Return the value of a Proj(Mod).
699
 */
Matthias Braun's avatar
Matthias Braun committed
700
static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
701
{
Michael Beck's avatar
Michael Beck committed
702
	long proj_nr = get_Proj_proj(n);
Michael Beck's avatar
Michael Beck committed
703

Michael Beck's avatar
Michael Beck committed
704
	if (proj_nr == pn_Mod_res) {
Michael Beck's avatar
Michael Beck committed
705
706
		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
707
708
	}
	return tarval_bad;
709
}
710

Michael Beck's avatar
Michael Beck committed
711
/**
Michael Beck's avatar
Michael Beck committed
712
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
713
 */
Matthias Braun's avatar
Matthias Braun committed
714
static ir_tarval *computed_value_Proj(const ir_node *proj)
715
{
Michael Beck's avatar
Michael Beck committed
716
717
718
719
720
	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;
721
}
Michael Beck's avatar
Michael Beck committed
722

723
724
725
/**
 * If the parameter n can be computed, return its value, else tarval_bad.
 * Performs constant folding.
726
727
 *
 * @param n  The node this should be evaluated
728
 */
Matthias Braun's avatar
Matthias Braun committed
729
ir_tarval *computed_value(const ir_node *n)
730
{
731
	vrp_attr *vrp = vrp_get_info(n);
732
	if (vrp != NULL && vrp->bits_set == vrp->bits_not_set)
733
		return vrp->bits_set;
734

Michael Beck's avatar
Michael Beck committed
735
736
737
	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
	return tarval_bad;
738
}
Christian Schäfer's avatar
Christian Schäfer committed
739

740
/**
741
 * Optimize operations that are commutative and have neutral 0,
742
 * so a op 0 = 0 op a = a.
743
 */
744
745
static ir_node *equivalent_node_neutral_zero(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
746
747
748
749
750
	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
751
	ir_tarval *tv;
Michael Beck's avatar
Michael Beck committed
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
	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.
	 */
770
771
	if (tarval_is_null(tv) && get_irn_mode(on) == get_irn_mode(n)) {
		n = on;
Michael Beck's avatar
Michael Beck committed
772

773
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
Michael Beck's avatar
Michael Beck committed
774
775
776
	}

	return n;
777
}
778

779
780
781
/**
 * Eor is commutative and has neutral 0.
 */
782
783
static ir_node *equivalent_node_Eor(ir_node *n)
{
784
785
786
787
788
789
790
791
792
793
	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);

794
795
796
	if (is_Eor(a) || is_Or_Eor_Add(a)) {
		ir_node *aa = get_binop_left(a);
		ir_node *ab = get_binop_right(a);
797
798
799
800

		if (aa == b) {
			/* (a ^ b) ^ a -> b */
			n = ab;
Michael Beck's avatar
Michael Beck committed
801
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
802
			return n;
803
804
805
		} else if (ab == b) {
			/* (a ^ b) ^ b -> a */
			n = aa;
Michael Beck's avatar
Michael Beck committed
806
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
807
			return n;
808
		}
809
	}
810
811
812
	if (is_Eor(b) || is_Or_Eor_Add(b)) {
		ir_node *ba = get_binop_left(b);
		ir_node *bb = get_binop_right(b);
813
814
815
816

		if (ba == a) {
			/* a ^ (a ^ b) -> b */
			n = bb;
Michael Beck's avatar
Michael Beck committed
817
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
818
			return n;
819
820
821
		} else if (bb == a) {
			/* a ^ (b ^ a) -> b */
			n = ba;
Michael Beck's avatar
Michael Beck committed
822
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
823
			return n;
824
825
826
827
		}
	}
	return n;
}
828

829
830
831
832
833
/*
 * 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 :-).
834
835
836
 *
 * 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.
837
 */
838
839
static ir_node *equivalent_node_Add(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
840
841
842
843
844
845
846
847
	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;

848
	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
849
850
851
852
853
	if (mode_is_float(mode)) {
		ir_graph *irg = get_irn_irg(n);
		if (get_irg_fp_model(irg) & fp_strict_algebraic)
			return n;
	}
854

Michael Beck's avatar
Michael Beck committed
855
856
857
	left  = get_Add_left(n);
	right = get_Add_right(n);

858
	if (is_Sub(left)) {
Michael Beck's avatar
Michael Beck committed
859
860
861
862
863
864
865
866
867
868
		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;
			}
		}
	}
869
	if (is_Sub(right)) {
Michael Beck's avatar
Michael Beck committed
870
871
872
873
874
875
876
877
878
879
880
		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;
881
}
882

883
/**
884
885
 * optimize operations that are not commutative but have neutral 0 on left,
 * so a op 0 = a.
886
 */
887
888
static ir_node *equivalent_node_left_zero(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
889
	ir_node *oldn = n;
890

Matthias Braun's avatar
Matthias Braun committed
891
892
893
	ir_node   *a  = get_binop_left(n);
	ir_node   *b  = get_binop_right(n);
	ir_tarval *tb = value_of(b);
894

895
	if (tarval_is_null(tb)) {
Michael Beck's avatar
Michael Beck committed
896
		n = a;
897

Michael Beck's avatar
Michael Beck committed
898
899
900
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
	}
	return n;
901
}
902

903
904
905
906
907
/**
 * 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 :-).
908
909
910
 *
 * 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.
911
 */
912
913
static ir_node *equivalent_node_Sub(ir_node *n)
{
Matthias Braun's avatar
Matthias Braun committed
914
915
916
917
	ir_node   *oldn = n;
	ir_node   *b;
	ir_mode   *mode = get_irn_mode(n);
	ir_tarval *tb;
Michael Beck's avatar
Michael Beck committed
918
919

	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
920
921
922
923
924
	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
925

926
927
	b  = get_Sub_right(n);
	tb = value_of(b);
Michael Beck's avatar
Michael Beck committed
928
929

	/* Beware: modes might be different */
930
	if (tarval_is_null(tb)) {
931
		ir_node *a = get_Sub_left(n);
Michael Beck's avatar
Michael Beck committed
932
933
934
935
936
937
938
		if (mode == get_irn_mode(a)) {
			n = a;

			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
		}
	}
	return n;
939
}
940
941


942
/**
yb9976's avatar
yb9976 committed
943
 * Optimize an "self-inverse unary op", i.e. op(op(n)) = n.
944
 *
945
946
947
948
 * @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.
949
 */
950
static ir_node *equivalent_node_involution(ir_node *n)
951
{
Michael Beck's avatar
Michael Beck committed
952
953
954
955
	ir_node *oldn = n;
	ir_node *pred = get_unop_op(n);
	if (get_irn_op(pred) == get_irn_op(n)) {
		n = get_unop_op(pred);
956
		DBG_OPT_ALGSIM2(oldn, pred, n, FS_OPT_INVOLUTION);
Michael Beck's avatar
Michael Beck committed
957
958
	}
	return n;
959
}
960

961
962
963
/**
 * Optimize a * 1 = 1 * a = a.
 */
964
965
static ir_node *equivalent_node_Mul(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
966
967
968
	ir_node *oldn = n;
	ir_node *a = get_Mul_left(n);

Michael Beck's avatar
Michael Beck committed
969
970
	/* we can handle here only the n * n = n bit cases */
	if (get_irn_mode(n