iropt.c 183 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 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
24
/**
 * @file
 * @brief   iropt --- optimizations intertwined with IR construction.
 * @author  Christian Schaefer, Goetz Lindenmaier, Michael Beck
 * @version $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
25
 */
Matthias Braun's avatar
Matthias Braun committed
26
#include "config.h"
Michael Beck's avatar
Michael Beck committed
27
28

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

Michael Beck's avatar
Michael Beck committed
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#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"
#include "irvrfy.h"
#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"
#include "opt_confirms.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"
Christian Schäfer's avatar
Christian Schäfer committed
50

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

54
55
56
57
58
59
60
61
62
63
64
65
/**
 * Returns the tarval of a Const node or tarval_bad for all other nodes.
 */
static tarval *default_value_of(const ir_node *n) {
	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
66
/* * Set a new value_of function. */
67
68
69
70
71
72
73
void set_value_of_func(value_of_func func) {
	if (func != NULL)
		value_of_ptr = func;
	else
		value_of_ptr = default_value_of;
}

74
/**
75
 * Return the value of a Constant.
76
 */
Michael Beck's avatar
Michael Beck committed
77
static tarval *computed_value_Const(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
78
	return get_Const_tarval(n);
79
}  /* computed_value_Const */
Christian Schäfer's avatar
Christian Schäfer committed
80

81
/**
Michael Beck's avatar
Michael Beck committed
82
 * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
83
 */
Michael Beck's avatar
Michael Beck committed
84
static tarval *computed_value_SymConst(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
	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;
109
}  /* computed_value_SymConst */
Christian Schäfer's avatar
Christian Schäfer committed
110

Michael Beck's avatar
Michael Beck committed
111
/**
112
 * Return the value of an Add.
Michael Beck's avatar
Michael Beck committed
113
 */
Michael Beck's avatar
Michael Beck committed
114
static tarval *computed_value_Add(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
115
116
	ir_node *a = get_Add_left(n);
	ir_node *b = get_Add_right(n);
Christian Schäfer's avatar
Christian Schäfer committed
117

Michael Beck's avatar
Michael Beck committed
118
119
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
120

121
	if ((ta != tarval_bad) && (tb != tarval_bad))
Michael Beck's avatar
Michael Beck committed
122
		return tarval_add(ta, tb);
123

Michael Beck's avatar
Michael Beck committed
124
	return tarval_bad;
125
}  /* computed_value_Add */
Christian Schäfer's avatar
Christian Schäfer committed
126

Michael Beck's avatar
Michael Beck committed
127
/**
128
 * Return the value of a Sub.
Michael Beck's avatar
Michael Beck committed
129
130
 * Special case: a - a
 */
Michael Beck's avatar
Michael Beck committed
131
static tarval *computed_value_Sub(const ir_node *n) {
132
133
134
135
136
	ir_mode *mode = get_irn_mode(n);
	ir_node *a    = get_Sub_left(n);
	ir_node *b    = get_Sub_right(n);
	tarval  *ta;
	tarval  *tb;
Christian Schäfer's avatar
Christian Schäfer committed
137

138
139
140
141
142
143
	/* 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
144

Michael Beck's avatar
Michael Beck committed
145
146
	ta = value_of(a);
	tb = value_of(b);
147

148
149
	if ((ta != tarval_bad) && (tb != tarval_bad))
		return tarval_sub(ta, tb, mode);
150

Michael Beck's avatar
Michael Beck committed
151
	return tarval_bad;
152
}  /* computed_value_Sub */
153

154
/**
155
 * Return the value of a Carry.
156
157
 * Special : a op 0, 0 op b
 */
Michael Beck's avatar
Michael Beck committed
158
static tarval *computed_value_Carry(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
159
160
161
162
163
164
165
166
167
168
169
	ir_node *a = get_binop_left(n);
	ir_node *b = get_binop_right(n);
	ir_mode *m = get_irn_mode(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		tarval_add(ta, tb);
		return tarval_carry() ? get_mode_one(m) : get_mode_null(m);
	} else {
170
		if (tarval_is_null(ta) || tarval_is_null(tb))
Michael Beck's avatar
Michael Beck committed
171
172
173
			return get_mode_null(m);
	}
	return tarval_bad;
174
}  /* computed_value_Carry */
175
176

/**
177
 * Return the value of a Borrow.
178
179
 * Special : a op 0
 */
Michael Beck's avatar
Michael Beck committed
180
static tarval *computed_value_Borrow(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
181
182
183
184
185
186
187
188
189
	ir_node *a = get_binop_left(n);
	ir_node *b = get_binop_right(n);
	ir_mode *m = get_irn_mode(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_cmp(ta, tb) == pn_Cmp_Lt ? get_mode_one(m) : get_mode_null(m);
190
	} else if (tarval_is_null(ta)) {
Michael Beck's avatar
Michael Beck committed
191
192
193
		return get_mode_null(m);
	}
	return tarval_bad;
194
}  /* computed_value_Borrow */
195

Michael Beck's avatar
Michael Beck committed
196
/**
197
 * Return the value of an unary Minus.
Michael Beck's avatar
Michael Beck committed
198
 */
Michael Beck's avatar
Michael Beck committed
199
static tarval *computed_value_Minus(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
200
201
	ir_node *a = get_Minus_op(n);
	tarval *ta = value_of(a);
202

Michael Beck's avatar
Michael Beck committed
203
	if (ta != tarval_bad)
Michael Beck's avatar
Michael Beck committed
204
		return tarval_neg(ta);
205

Michael Beck's avatar
Michael Beck committed
206
	return tarval_bad;
207
}  /* computed_value_Minus */
208

Michael Beck's avatar
Michael Beck committed
209
/**
210
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
211
 */
Michael Beck's avatar
Michael Beck committed
212
static tarval *computed_value_Mul(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
213
214
	ir_node *a = get_Mul_left(n);
	ir_node *b = get_Mul_right(n);
Michael Beck's avatar
Michael Beck committed
215
	ir_mode *mode;
Michael Beck's avatar
Michael Beck committed
216
217
218
219

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

Michael Beck's avatar
Michael Beck committed
220
221
222
223
224
225
226
227
	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
228
229
		return tarval_mul(ta, tb);
	} else {
230
231
232
233
234
235
236
237
		/* 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
238
239
	}
	return tarval_bad;
240
}  /* computed_value_Mul */
241

Michael Beck's avatar
Michael Beck committed
242
/**
243
 * Return the value of an Abs.
Michael Beck's avatar
Michael Beck committed
244
 */
Michael Beck's avatar
Michael Beck committed
245
static tarval *computed_value_Abs(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
246
247
	ir_node *a = get_Abs_op(n);
	tarval *ta = value_of(a);
248

Michael Beck's avatar
Michael Beck committed
249
250
	if (ta != tarval_bad)
		return tarval_abs(ta);
251

Michael Beck's avatar
Michael Beck committed
252
	return tarval_bad;
253
}  /* computed_value_Abs */
254

Michael Beck's avatar
Michael Beck committed
255
/**
256
 * Return the value of an And.
Michael Beck's avatar
Michael Beck committed
257
258
 * Special case: a & 0, 0 & b
 */
Michael Beck's avatar
Michael Beck committed
259
static tarval *computed_value_And(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
260
261
262
263
264
265
266
267
268
	ir_node *a = get_And_left(n);
	ir_node *b = get_And_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_and (ta, tb);
	} else {
269
270
		if (tarval_is_null(ta)) return ta;
		if (tarval_is_null(tb)) return tb;
Michael Beck's avatar
Michael Beck committed
271
272
	}
	return tarval_bad;
273
}  /* computed_value_And */
274

Michael Beck's avatar
Michael Beck committed
275
/**
276
 * Return the value of an Or.
Michael Beck's avatar
Michael Beck committed
277
278
 * Special case: a | 1...1, 1...1 | b
 */
Michael Beck's avatar
Michael Beck committed
279
static tarval *computed_value_Or(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
280
281
282
283
284
285
286
287
288
	ir_node *a = get_Or_left(n);
	ir_node *b = get_Or_right(n);

	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_or (ta, tb);
	} else {
289
290
		if (tarval_is_all_one(ta)) return ta;
		if (tarval_is_all_one(tb)) return tb;
Michael Beck's avatar
Michael Beck committed
291
292
	}
	return tarval_bad;
293
}  /* computed_value_Or */
294

Michael Beck's avatar
Michael Beck committed
295
/**
296
 * Return the value of an Eor.
Michael Beck's avatar
Michael Beck committed
297
 */
Michael Beck's avatar
Michael Beck committed
298
static tarval *computed_value_Eor(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
299
300
	ir_node *a = get_Eor_left(n);
	ir_node *b = get_Eor_right(n);
301

Michael Beck's avatar
Michael Beck committed
302
	tarval *ta, *tb;
Michael Beck's avatar
Michael Beck committed
303

Michael Beck's avatar
Michael Beck committed
304
305
	if (a == b)
		return get_mode_null(get_irn_mode(n));
Michael Beck's avatar
Michael Beck committed
306

Michael Beck's avatar
Michael Beck committed
307
308
	ta = value_of(a);
	tb = value_of(b);
309

Michael Beck's avatar
Michael Beck committed
310
311
312
313
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_eor (ta, tb);
	}
	return tarval_bad;
314
}  /* computed_value_Eor */
315

Michael Beck's avatar
Michael Beck committed
316
/**
317
 * Return the value of a Not.
Michael Beck's avatar
Michael Beck committed
318
 */
Michael Beck's avatar
Michael Beck committed
319
static tarval *computed_value_Not(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
320
321
	ir_node *a = get_Not_op(n);
	tarval *ta = value_of(a);
322

Michael Beck's avatar
Michael Beck committed
323
324
	if (ta != tarval_bad)
		return tarval_not(ta);
325

Michael Beck's avatar
Michael Beck committed
326
	return tarval_bad;
327
}  /* computed_value_Not */
328

Michael Beck's avatar
Michael Beck committed
329
/**
330
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
331
 */
Michael Beck's avatar
Michael Beck committed
332
static tarval *computed_value_Shl(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
333
334
	ir_node *a = get_Shl_left(n);
	ir_node *b = get_Shl_right(n);
335

Michael Beck's avatar
Michael Beck committed
336
337
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
338

Michael Beck's avatar
Michael Beck committed
339
340
341
342
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shl (ta, tb);
	}
	return tarval_bad;
343
}  /* computed_value_Shl */
344

Michael Beck's avatar
Michael Beck committed
345
/**
346
 * Return the value of a Shr.
Michael Beck's avatar
Michael Beck committed
347
 */
Michael Beck's avatar
Michael Beck committed
348
static tarval *computed_value_Shr(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
349
350
	ir_node *a = get_Shr_left(n);
	ir_node *b = get_Shr_right(n);
351

Michael Beck's avatar
Michael Beck committed
352
353
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
354

Michael Beck's avatar
Michael Beck committed
355
356
357
358
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shr (ta, tb);
	}
	return tarval_bad;
359
}  /* computed_value_Shr */
360

Michael Beck's avatar
Michael Beck committed
361
/**
362
 * Return the value of a Shrs.
Michael Beck's avatar
Michael Beck committed
363
 */
Michael Beck's avatar
Michael Beck committed
364
static tarval *computed_value_Shrs(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
365
366
	ir_node *a = get_Shrs_left(n);
	ir_node *b = get_Shrs_right(n);
367

Michael Beck's avatar
Michael Beck committed
368
369
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
370

Michael Beck's avatar
Michael Beck committed
371
372
373
374
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shrs (ta, tb);
	}
	return tarval_bad;
375
}  /* computed_value_Shrs */
376

Michael Beck's avatar
Michael Beck committed
377
/**
378
 * Return the value of a Rotl.
Michael Beck's avatar
Michael Beck committed
379
 */
Michael Beck's avatar
Michael Beck committed
380
static tarval *computed_value_Rotl(const ir_node *n) {
381
382
	ir_node *a = get_Rotl_left(n);
	ir_node *b = get_Rotl_right(n);
383

Michael Beck's avatar
Michael Beck committed
384
385
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
386

Michael Beck's avatar
Michael Beck committed
387
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
388
		return tarval_rotl(ta, tb);
Michael Beck's avatar
Michael Beck committed
389
390
	}
	return tarval_bad;
391
}  /* computed_value_Rotl */
392

Michael Beck's avatar
Michael Beck committed
393
/**
394
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
395
 */
Michael Beck's avatar
Michael Beck committed
396
static tarval *computed_value_Conv(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
397
398
	ir_node *a = get_Conv_op(n);
	tarval *ta = value_of(a);
399

Michael Beck's avatar
Michael Beck committed
400
401
	if (ta != tarval_bad)
		return tarval_convert_to(ta, get_irn_mode(n));
402

Michael Beck's avatar
Michael Beck committed
403
	return tarval_bad;
404
}  /* computed_value_Conv */
405

Michael Beck's avatar
Michael Beck committed
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
/**
 * Calculate the value of a Mux: can be evaluated, if the
 * sel and the right input are known.
 */
static tarval *computed_value_Mux(const ir_node *n) {
	ir_node *sel = get_Mux_sel(n);
	tarval *ts = value_of(sel);

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

/**
 * Calculate the value of a Confirm: can be evaluated,
 * if it has the form Confirm(x, '=', Const).
 */
static tarval *computed_value_Confirm(const ir_node *n) {
	/*
	 * Beware: we might produce Phi(Confirm(x == true), Confirm(x == false)).
	 * Do NOT optimize them away (CondEval wants them), so wait until
	 * remove_confirm is activated.
	 */
	if (get_opt_remove_confirm()) {
		if (get_Confirm_cmp(n) == pn_Cmp_Eq) {
			tarval *tv = value_of(get_Confirm_bound(n));
			if (tv != tarval_bad)
				return tv;
		}
	}
	return value_of(get_Confirm_value(n));
}  /* computed_value_Confirm */

445
/**
446
 * Return the value of a Proj(Cmp).
447
448
449
450
451
452
453
 *
 * This performs a first step of unreachable code elimination.
 * Proj can not be computed, but folding a Cmp above the Proj here is
 * not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
 * only 1 is used.
 * There are several case where we can evaluate a Cmp node, see later.
 */
Michael Beck's avatar
Michael Beck committed
454
static tarval *computed_value_Proj_Cmp(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
455
456
457
458
459
460
461
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
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
	ir_node *a   = get_Proj_pred(n);
	ir_node *aa  = get_Cmp_left(a);
	ir_node *ab  = get_Cmp_right(a);
	long proj_nr = get_Proj_proj(n);

	/*
	 * BEWARE: a == a is NOT always True for floating Point values, as
	 * NaN != NaN is defined, so we must check this here.
	 */
	if (aa == ab && (
		!mode_is_float(get_irn_mode(aa)) || proj_nr == pn_Cmp_Lt ||  proj_nr == pn_Cmp_Gt)
		) { /* 1.: */

		/* This is a trick with the bits used for encoding the Cmp
		   Proj numbers, the following statement is not the same:
		return new_tarval_from_long (proj_nr == pn_Cmp_Eq, mode_b) */
		return new_tarval_from_long (proj_nr & pn_Cmp_Eq, mode_b);
	}
	else {
		tarval *taa = value_of(aa);
		tarval *tab = value_of(ab);
		ir_mode *mode = get_irn_mode(aa);

		/*
		 * The predecessors of Cmp are target values.  We can evaluate
		 * the Cmp.
		 */
		if ((taa != tarval_bad) && (tab != tarval_bad)) {
			/* strange checks... */
			pn_Cmp flags = tarval_cmp(taa, tab);
			if (flags != pn_Cmp_False) {
				return new_tarval_from_long (proj_nr & flags, mode_b);
			}
		}
		/* for integer values, we can check against MIN/MAX */
		else if (mode_is_int(mode)) {
			/* MIN <=/> x.  This results in true/false. */
			if (taa == get_mode_min(mode)) {
				/* a compare with the MIN value */
				if (proj_nr == pn_Cmp_Le)
					return get_tarval_b_true();
				else if (proj_nr == pn_Cmp_Gt)
					return get_tarval_b_false();
			}
			/* x >=/< MIN.  This results in true/false. */
			else
				if (tab == get_mode_min(mode)) {
					/* a compare with the MIN value */
					if (proj_nr == pn_Cmp_Ge)
						return get_tarval_b_true();
					else if (proj_nr == pn_Cmp_Lt)
						return get_tarval_b_false();
				}
				/* MAX >=/< x.  This results in true/false. */
				else if (taa == get_mode_max(mode)) {
					if (proj_nr == pn_Cmp_Ge)
						return get_tarval_b_true();
					else if (proj_nr == pn_Cmp_Lt)
						return get_tarval_b_false();
				}
				/* x <=/> MAX.  This results in true/false. */
				else if (tab == get_mode_max(mode)) {
					if (proj_nr == pn_Cmp_Le)
						return get_tarval_b_true();
					else if (proj_nr == pn_Cmp_Gt)
						return get_tarval_b_false();
				}
		}
		/*
		 * The predecessors are Allocs or (void*)(0) constants.  Allocs never
		 * return NULL, they raise an exception.   Therefore we can predict
		 * the Cmp result.
		 */
		else {
529
530
			ir_node *aaa = skip_Proj(aa);
			ir_node *aba = skip_Proj(ab);
Michael Beck's avatar
Michael Beck committed
531
532

			if (   (   (/* aa is ProjP and aaa is Alloc */
533
534
535
			               is_Proj(aa)
			            && mode_is_reference(get_irn_mode(aa))
			            && is_Alloc(aaa))
Michael Beck's avatar
Michael Beck committed
536
			        && (   (/* ab is NULL */
537
538
			                mode_is_reference(get_irn_mode(ab))
			                && tarval_is_null(tab))
Michael Beck's avatar
Michael Beck committed
539
			            || (/* ab is other Alloc */
540
541
542
			                   is_Proj(ab)
			                && mode_is_reference(get_irn_mode(ab))
			                && is_Alloc(aba)
Michael Beck's avatar
Michael Beck committed
543
544
			                && (aaa != aba))))
			    || (/* aa is NULL and aba is Alloc */
545
546
			        mode_is_reference(get_irn_mode(aa))
			        && tarval_is_null(taa)
547
548
549
			        && is_Proj(ab)
			        && mode_is_reference(get_irn_mode(ab))
			        && is_Alloc(aba)))
Michael Beck's avatar
Michael Beck committed
550
				/* 3.: */
551
			return new_tarval_from_long(proj_nr & pn_Cmp_Lg, mode_b);
Michael Beck's avatar
Michael Beck committed
552
553
554
		}
	}
	return computed_value_Cmp_Confirm(a, aa, ab, proj_nr);
555
}  /* computed_value_Proj_Cmp */
556

557
558
559
/**
 * Return the value of a floating point Quot.
 */
Michael Beck's avatar
Michael Beck committed
560
static tarval *do_computed_value_Quot(const ir_node *a, const ir_node *b) {
561
562
563
564
565
566
567
568
569
570
571
572
573
	tarval  *ta = value_of(a);
	tarval  *tb = value_of(b);

	/* cannot optimize 0 / b = 0 because of NaN */
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_quo(ta, tb);
	return tarval_bad;
}  /* do_computed_value_Quot */

/**
 * Calculate the value of an integer Div of two nodes.
 * Special case: 0 / b
 */
Michael Beck's avatar
Michael Beck committed
574
static tarval *do_computed_value_Div(const ir_node *a, const ir_node *b) {
Michael Beck's avatar
Michael Beck committed
575
576
577
	tarval        *ta = value_of(a);
	tarval        *tb;
	const ir_node *dummy;
578
579
580
581
582
583
584
585
586
587
588
589
590
591

	/* Compute c1 / c2 or 0 / a, a != 0 */
	if (tarval_is_null(ta) && value_not_zero(b, &dummy))
		return ta;  /* 0 / b == 0 */
	tb = value_of(b);
	if (ta != tarval_bad && tb != tarval_bad)
		return tarval_div(ta, tb);
	return tarval_bad;
}  /* do_computed_value_Div */

/**
 * Calculate the value of an integer Mod of two nodes.
 * Special case: a % 1
 */
Michael Beck's avatar
Michael Beck committed
592
static tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b) {
593
594
595
596
597
598
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	/* 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
599
	if (ta != tarval_bad && tb != tarval_bad)
600
601
602
603
		return tarval_mod(ta, tb);
	return tarval_bad;
}  /* do_computed_value_Mod */

Michael Beck's avatar
Michael Beck committed
604
/**
Michael Beck's avatar
Michael Beck committed
605
 * Return the value of a Proj(DivMod).
Michael Beck's avatar
Michael Beck committed
606
 */
Michael Beck's avatar
Michael Beck committed
607
608
static tarval *computed_value_Proj_DivMod(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);
Michael Beck's avatar
Michael Beck committed
609

Michael Beck's avatar
Michael Beck committed
610
611
612
613
614
615
616
617
618
619
	/* compute either the Div or the Mod part */
	if (proj_nr == pn_DivMod_res_div) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
	} else if (proj_nr == pn_DivMod_res_mod) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
	}
	return tarval_bad;
}  /* computed_value_Proj_DivMod */
Michael Beck's avatar
Michael Beck committed
620

Michael Beck's avatar
Michael Beck committed
621
622
623
624
625
/**
 * Return the value of a Proj(Div).
 */
static tarval *computed_value_Proj_Div(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);
Michael Beck's avatar
Michael Beck committed
626

Michael Beck's avatar
Michael Beck committed
627
628
629
	if (proj_nr == pn_Div_res) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Div(get_Div_left(a), get_Div_right(a));
Michael Beck's avatar
Michael Beck committed
630
631
	}
	return tarval_bad;
Michael Beck's avatar
Michael Beck committed
632
}  /* computed_value_Proj_Div */
633

634
/**
Michael Beck's avatar
Michael Beck committed
635
 * Return the value of a Proj(Mod).
636
 */
Michael Beck's avatar
Michael Beck committed
637
638
static tarval *computed_value_Proj_Mod(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);
Michael Beck's avatar
Michael Beck committed
639

Michael Beck's avatar
Michael Beck committed
640
641
642
	if (proj_nr == pn_Mod_res) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Mod(get_Mod_left(a), get_Mod_right(a));
Michael Beck's avatar
Michael Beck committed
643
644
	}
	return tarval_bad;
Michael Beck's avatar
Michael Beck committed
645
}  /* computed_value_Proj_Mod */
646

Michael Beck's avatar
BugFix:    
Michael Beck committed
647
/**
Michael Beck's avatar
Michael Beck committed
648
 * Return the value of a Proj(Quot).
Michael Beck's avatar
BugFix:    
Michael Beck committed
649
 */
Michael Beck's avatar
Michael Beck committed
650
651
652
653
654
655
656
static tarval *computed_value_Proj_Quot(const ir_node *n) {
	long proj_nr = get_Proj_proj(n);

	if (proj_nr == pn_Quot_res) {
		const ir_node *a = get_Proj_pred(n);
		return do_computed_value_Quot(get_Quot_left(a), get_Quot_right(a));
	}
Michael Beck's avatar
Michael Beck committed
657
	return tarval_bad;
Michael Beck's avatar
Michael Beck committed
658
}  /* computed_value_Proj_Quot */
Michael Beck's avatar
BugFix:    
Michael Beck committed
659

Michael Beck's avatar
Michael Beck committed
660
/**
Michael Beck's avatar
Michael Beck committed
661
 * Return the value of a Proj.
Michael Beck's avatar
Michael Beck committed
662
 */
Michael Beck's avatar
Michael Beck committed
663
664
665
666
667
668
669
static tarval *computed_value_Proj(const ir_node *proj) {
	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;
}  /* computed_value_Proj */
Michael Beck's avatar
Michael Beck committed
670

671
672
673
/**
 * If the parameter n can be computed, return its value, else tarval_bad.
 * Performs constant folding.
674
675
 *
 * @param n  The node this should be evaluated
676
 */
Michael Beck's avatar
Michael Beck committed
677
tarval *computed_value(const ir_node *n) {
Michael Beck's avatar
Michael Beck committed
678
679
680
	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
	return tarval_bad;
681
}  /* computed_value */
Christian Schäfer's avatar
Christian Schäfer committed
682

683
/**
684
 * Set the default computed_value evaluator in an ir_op_ops.
Michael Beck's avatar
Michael Beck committed
685
686
687
688
689
690
 *
 * @param code   the opcode for the default operation
 * @param ops    the operations initialized
 *
 * @return
 *    The operations.
691
 */
692
693
static ir_op_ops *firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops)
{
Michael Beck's avatar
Michael Beck committed
694
695
696
697
698
699
700
#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
701
702
703
704
705
706
707
		break

	switch (code) {
	CASE(Const);
	CASE(SymConst);
	CASE(Add);
	CASE(Sub);
Michael Beck's avatar
Michael Beck committed
708
709
	CASE(Carry);
	CASE(Borrow);
Michael Beck's avatar
Michael Beck committed
710
711
712
713
714
715
716
717
718
719
	CASE(Minus);
	CASE(Mul);
	CASE(Abs);
	CASE(And);
	CASE(Or);
	CASE(Eor);
	CASE(Not);
	CASE(Shl);
	CASE(Shr);
	CASE(Shrs);
720
	CASE(Rotl);
Michael Beck's avatar
Michael Beck committed
721
722
723
	CASE(Conv);
	CASE(Mux);
	CASE(Confirm);
Michael Beck's avatar
Michael Beck committed
724
725
726
727
728
729
	CASE_PROJ(Cmp);
	CASE_PROJ(DivMod);
	CASE_PROJ(Div);
	CASE_PROJ(Mod);
	CASE_PROJ(Quot);
	CASE(Proj);
Michael Beck's avatar
Michael Beck committed
730
731
732
733
734
	default:
		/* leave NULL */;
	}

	return ops;
Michael Beck's avatar
Michael Beck committed
735
#undef CASE_PROJ
736
#undef CASE
737
}  /* firm_set_default_computed_value */
Christian Schäfer's avatar
Christian Schäfer committed
738

Michael Beck's avatar
Michael Beck committed
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
/**
 * Returns a equivalent block for another block.
 * If the block has only one predecessor, this is
 * the equivalent one. If the only predecessor of a block is
 * the block itself, this is a dead block.
 *
 * If both predecessors of a block are the branches of a binary
 * Cond, the equivalent block is Cond's block.
 *
 * If all predecessors of a block are bad or lies in a dead
 * block, the current block is dead as well.
 *
 * Note, that blocks are NEVER turned into Bad's, instead
 * the dead_block flag is set. So, never test for is_Bad(block),
 * always use is_dead_Block(block).
 */
755
756
static ir_node *equivalent_node_Block(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
757
	ir_node *oldn = n;
758
	int     n_preds;
Michael Beck's avatar
Michael Beck committed
759

760
761
	/* don't optimize dead or labeled blocks */
	if (is_Block_dead(n) || has_Block_label(n))
762
763
764
765
766
767
		return n;

	n_preds = get_Block_n_cfgpreds(n);

	/* The Block constructor does not call optimize, but mature_immBlock()
	   calls the optimization. */
Michael Beck's avatar
Michael Beck committed
768
769
770
771
772
773
774
775
	assert(get_Block_matured(n));

	/* Straightening: a single entry Block following a single exit Block
	   can be merged, if it is not the Start block. */
	/* !!! Beware, all Phi-nodes of n must have been optimized away.
	   This should be true, as the block is matured before optimize is called.
	   But what about Phi-cycles with the Phi0/Id that could not be resolved?
	   Remaining Phi nodes are just Ids. */
Michael Beck's avatar
Michael Beck committed
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
	if (n_preds == 1) {
		ir_node *pred = skip_Proj(get_Block_cfgpred(n, 0));

		if (is_Jmp(pred)) {
			ir_node *predblock = get_nodes_block(pred);
			if (predblock == oldn) {
				/* Jmp jumps into the block it is in -- deal self cycle. */
				n = set_Block_dead(n);
				DBG_OPT_DEAD_BLOCK(oldn, n);
			} else if (get_opt_control_flow_straightening()) {
				n = predblock;
				DBG_OPT_STG(oldn, n);
			}
		} else if (is_Cond(pred)) {
			ir_node *predblock = get_nodes_block(pred);
			if (predblock == oldn) {
				/* Jmp jumps into the block it is in -- deal self cycle. */
				n = set_Block_dead(n);
				DBG_OPT_DEAD_BLOCK(oldn, n);
			}
Michael Beck's avatar
Michael Beck committed
796
797
798
799
800
801
802
803
804
805
		}
	} else if ((n_preds == 2) &&
	           (get_opt_control_flow_weak_simplification())) {
		/* Test whether Cond jumps twice to this block
		 * The more general case which more than 2 predecessors is handles
		 * in optimize_cf(), we handle only this special case for speed here.
		 */
		ir_node *a = get_Block_cfgpred(n, 0);
		ir_node *b = get_Block_cfgpred(n, 1);

Michael Beck's avatar
Michael Beck committed
806
807
808
809
810
811
812
813
814
815
		if (is_Proj(a) && is_Proj(b)) {
			ir_node *cond = get_Proj_pred(a);

		    if (cond == get_Proj_pred(b) && is_Cond(cond) &&
		        get_irn_mode(get_Cond_selector(cond)) == mode_b) {
				/* Also a single entry Block following a single exit Block.  Phis have
				   twice the same operand and will be optimized away. */
				n = get_nodes_block(cond);
				DBG_OPT_IFSIM1(oldn, a, b, n);
			}
Michael Beck's avatar
Michael Beck committed
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
		}
	} else if (get_opt_unreachable_code() &&
	           (n != get_irg_start_block(current_ir_graph)) &&
	           (n != get_irg_end_block(current_ir_graph))    ) {
		int i;

		/* If all inputs are dead, this block is dead too, except if it is
		   the start or end block.  This is one step of unreachable code
		   elimination */
		for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
			ir_node *pred = get_Block_cfgpred(n, i);
			ir_node *pred_blk;

			if (is_Bad(pred)) continue;
			pred_blk = get_nodes_block(skip_Proj(pred));

			if (is_Block_dead(pred_blk)) continue;

			if (pred_blk != n) {
				/* really found a living input */
				break;
			}
		}
		if (i < 0) {
			n = set_Block_dead(n);
			DBG_OPT_DEAD_BLOCK(oldn, n);
		}
	}

	return n;
846
}  /* equivalent_node_Block */
847

848
849
/**
 * Returns a equivalent node for a Jmp, a Bad :-)
850
 * Of course this only happens if the Block of the Jmp is dead.
851
 */
852
static ir_node *equivalent_node_Jmp(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
853
	ir_node *oldn = n;
854

Michael Beck's avatar
Michael Beck committed
855
856
857
858
859
	/* unreachable code elimination */
	if (is_Block_dead(get_nodes_block(n))) {
		n = get_irg_bad(current_ir_graph);
		DBG_OPT_DEAD_BLOCK(oldn, n);
	}
Michael Beck's avatar
Michael Beck committed
860
	return n;
861
}  /* equivalent_node_Jmp */
862

863
/** Raise is handled in the same way as Jmp. */
864
865
866
#define equivalent_node_Raise   equivalent_node_Jmp


867
868
/* We do not evaluate Cond here as we replace it by a new node, a Jmp.
   See transform_node_Proj_Cond(). */
869

870
/**
871
 * Optimize operations that are commutative and have neutral 0,
872
 * so a op 0 = 0 op a = a.
873
 */
Michael Beck's avatar
Michael Beck committed
874
static ir_node *equivalent_node_neutral_zero(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
	ir_node *oldn = n;

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

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

902
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
Michael Beck's avatar
Michael Beck committed
903
904
905
	}

	return n;
906
}  /* equivalent_node_neutral_zero */
907

908
909
910
/**
 * Eor is commutative and has neutral 0.
 */
Michael Beck's avatar
Michael Beck committed
911
static ir_node *equivalent_node_Eor(ir_node *n) {
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
	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);

	if (is_Eor(a)) {
		ir_node *aa = get_Eor_left(a);
		ir_node *ab = get_Eor_right(a);

		if (aa == b) {
			/* (a ^ b) ^ a -> b */
			n = ab;
Michael Beck's avatar
Michael Beck committed
929
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
930
			return n;
931
932
933
		} else if (ab == b) {
			/* (a ^ b) ^ b -> a */
			n = aa;
Michael Beck's avatar
Michael Beck committed
934
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
935
			return n;
936
		}
937
938
	}
	if (is_Eor(b)) {
939
940
941
942
943
944
		ir_node *ba = get_Eor_left(b);
		ir_node *bb = get_Eor_right(b);

		if (ba == a) {
			/* a ^ (a ^ b) -> b */
			n = bb;
Michael Beck's avatar
Michael Beck committed
945
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
946
			return n;
947
948
949
		} else if (bb == a) {
			/* a ^ (b ^ a) -> b */
			n = ba;
Michael Beck's avatar
Michael Beck committed
950
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
Michael Beck's avatar
Michael Beck committed
951
			return n;
952
953
954
955
		}
	}
	return n;
}
956

957
958
959
960
961
/*
 * 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 :-).
962
963
964
 *
 * 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.
965
 */
Michael Beck's avatar
Michael Beck committed
966
967
968
969
970
971
972
973
974
static ir_node *equivalent_node_Add(ir_node *n) {
	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;

975
976
977
978
	/* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
	if (mode_is_float(mode) && (get_irg_fp_model(current_ir_graph) & fp_strict_algebraic))
		return n;

Michael Beck's avatar
Michael Beck committed
979
980
981
	left  = get_Add_left(n);
	right = get_Add_right(n);

982
	if (is_Sub(left)) {
Michael Beck's avatar
Michael Beck committed
983
984
985
986
987
988
989
990
991
992
		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;
			}
		}
	}
993
	if (is_Sub(right)) {
Michael Beck's avatar
Michael Beck committed
994
995
996
997
998
999
1000
		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;