iropt.c 130 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * 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
 */
Boris Boesler's avatar
added    
Boris Boesler committed
26
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
27
28
29
30
# include "config.h"
#endif

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

Michael Beck's avatar
Michael Beck committed
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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 "archop.h"
#include "opt_confirms.h"
49
#include "opt_polymorphy.h"
Michael Beck's avatar
Michael Beck committed
50
#include "irtools.h"
51
#include "xmalloc.h"
Christian Schäfer's avatar
Christian Schäfer committed
52

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

56
/**
57
 * Return the value of a Constant.
58
 */
59
static tarval *computed_value_Const(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
60
	return get_Const_tarval(n);
61
}  /* computed_value_Const */
Christian Schäfer's avatar
Christian Schäfer committed
62

63
/**
Michael Beck's avatar
Michael Beck committed
64
 * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
65
 */
66
static tarval *computed_value_SymConst(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
	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;
91
}  /* computed_value_SymConst */
Christian Schäfer's avatar
Christian Schäfer committed
92

Michael Beck's avatar
Michael Beck committed
93
/**
94
 * Return the value of an Add.
Michael Beck's avatar
Michael Beck committed
95
 */
96
static tarval *computed_value_Add(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
97
98
	ir_node *a = get_Add_left(n);
	ir_node *b = get_Add_right(n);
Christian Schäfer's avatar
Christian Schäfer committed
99

Michael Beck's avatar
Michael Beck committed
100
101
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
102

Michael Beck's avatar
Michael Beck committed
103
104
	if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
		return tarval_add(ta, tb);
105

Michael Beck's avatar
Michael Beck committed
106
	return tarval_bad;
107
}  /* computed_value_Add */
Christian Schäfer's avatar
Christian Schäfer committed
108

Michael Beck's avatar
Michael Beck committed
109
/**
110
 * Return the value of a Sub.
Michael Beck's avatar
Michael Beck committed
111
112
 * Special case: a - a
 */
113
static tarval *computed_value_Sub(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
114
115
116
117
	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
118

Michael Beck's avatar
Michael Beck committed
119
120
121
	/* a - a */
	if (a == b && !is_Bad(a))
		return get_mode_null(get_irn_mode(n));
Michael Beck's avatar
Michael Beck committed
122

Michael Beck's avatar
Michael Beck committed
123
124
	ta = value_of(a);
	tb = value_of(b);
125

Michael Beck's avatar
Michael Beck committed
126
127
	if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
		return tarval_sub(ta, tb);
128

Michael Beck's avatar
Michael Beck committed
129
	return tarval_bad;
130
}  /* computed_value_Sub */
131

132
/**
133
 * Return the value of a Carry.
134
135
 * Special : a op 0, 0 op b
 */
136
static tarval *computed_value_Carry(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
	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 {
		if (   (classify_tarval(ta) == TV_CLASSIFY_NULL)
			|| (classify_tarval(tb) == TV_CLASSIFY_NULL))
			return get_mode_null(m);
	}
	return tarval_bad;
153
}  /* computed_value_Carry */
154
155

/**
156
 * Return the value of a Borrow.
157
158
 * Special : a op 0
 */
159
static tarval *computed_value_Borrow(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
160
161
162
163
164
165
166
167
168
169
170
171
172
	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);
	} else if (classify_tarval(ta) == TV_CLASSIFY_NULL) {
		return get_mode_null(m);
	}
	return tarval_bad;
173
}  /* computed_value_Borrow */
174

Michael Beck's avatar
Michael Beck committed
175
/**
176
 * Return the value of an unary Minus.
Michael Beck's avatar
Michael Beck committed
177
 */
178
static tarval *computed_value_Minus(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
179
180
	ir_node *a = get_Minus_op(n);
	tarval *ta = value_of(a);
181

Michael Beck's avatar
Michael Beck committed
182
183
	if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
		return tarval_neg(ta);
184

Michael Beck's avatar
Michael Beck committed
185
	return tarval_bad;
186
}  /* computed_value_Minus */
187

Michael Beck's avatar
Michael Beck committed
188
/**
189
 * Return the value of a Mul.
Michael Beck's avatar
Michael Beck committed
190
 */
191
static tarval *computed_value_Mul(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
192
193
	ir_node *a = get_Mul_left(n);
	ir_node *b = get_Mul_right(n);
Michael Beck's avatar
Michael Beck committed
194
	ir_mode *mode;
Michael Beck's avatar
Michael Beck committed
195
196
197
198

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

Michael Beck's avatar
Michael Beck committed
199
200
201
202
203
204
205
206
	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
207
208
		return tarval_mul(ta, tb);
	} else {
Michael Beck's avatar
Michael Beck committed
209
210
		/* a*0 = 0 or 0*b = 0 */
		if (ta == get_mode_null(mode))
Michael Beck's avatar
Michael Beck committed
211
			return ta;
Michael Beck's avatar
Michael Beck committed
212
		if (tb == get_mode_null(mode))
Michael Beck's avatar
Michael Beck committed
213
214
215
			return tb;
	}
	return tarval_bad;
216
}  /* computed_value_Mul */
217

Michael Beck's avatar
Michael Beck committed
218
/**
219
 * Return the value of a floating point Quot.
Michael Beck's avatar
Michael Beck committed
220
 */
221
static tarval *computed_value_Quot(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
222
223
224
225
226
227
228
229
230
231
232
233
	ir_node *a = get_Quot_left(n);
	ir_node *b = get_Quot_right(n);

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

	/* This was missing in original implementation. Why? */
	if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
		if (tb != get_mode_null(get_tarval_mode(tb)))   /* div by zero: return tarval_bad */
			return tarval_quo(ta, tb);
	}
	return tarval_bad;
234
}  /* computed_value_Quot */
235

Michael Beck's avatar
Michael Beck committed
236
/**
237
 * Calculate the value of an integer Div of two nodes.
Michael Beck's avatar
Michael Beck committed
238
239
 * Special case: 0 / b
 */
240
static tarval *do_computed_value_Div(ir_node *a, ir_node *b) {
Michael Beck's avatar
Michael Beck committed
241
242
243
244
245
246
247
248
249
250
251
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	/* Compute c1 / c2 or 0 / a, a != 0 */
	if (ta != tarval_bad) {
		if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b))))   /* div by zero: return tarval_bad */
			return tarval_div(ta, tb);
		else if (ta == get_mode_null(get_tarval_mode(ta)))  /* 0 / b == 0 */
			return ta;
	}
	return tarval_bad;
252
}  /* do_computed_value_Div */
253

Michael Beck's avatar
Michael Beck committed
254
/**
255
 * Return the value of an integer Div.
Michael Beck's avatar
Michael Beck committed
256
 */
257
static tarval *computed_value_Div(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
258
	return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
259
}  /* computed_value_Div */
260

Michael Beck's avatar
Michael Beck committed
261
/**
262
 * Calculate the value of an integer Mod of two nodes.
Michael Beck's avatar
Michael Beck committed
263
264
 * Special case: a % 1
 */
265
static tarval *do_computed_value_Mod(ir_node *a, ir_node *b) {
Michael Beck's avatar
Michael Beck committed
266
267
268
269
270
271
272
273
274
275
276
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);

	/* Compute c1 % c2 or a % 1 */
	if (tb != tarval_bad) {
		if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb))))   /* div by zero: return tarval_bad */
			return tarval_mod(ta, tb);
		else if (tb == get_mode_one(get_tarval_mode(tb)))    /* x mod 1 == 0 */
			return get_mode_null(get_irn_mode(a));
	}
	return tarval_bad;
277
}  /* do_computed_value_Mod */
278

Michael Beck's avatar
Michael Beck committed
279
/**
280
 * Return the value of an integer Mod.
Michael Beck's avatar
Michael Beck committed
281
 */
282
static tarval *computed_value_Mod(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
283
	return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
284
}  /* computed_value_Mod */
Michael Beck's avatar
Michael Beck committed
285
286

/**
287
 * Return the value of an Abs.
Michael Beck's avatar
Michael Beck committed
288
 */
289
static tarval *computed_value_Abs(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
290
291
	ir_node *a = get_Abs_op(n);
	tarval *ta = value_of(a);
292

Michael Beck's avatar
Michael Beck committed
293
294
	if (ta != tarval_bad)
		return tarval_abs(ta);
295

Michael Beck's avatar
Michael Beck committed
296
	return tarval_bad;
297
}  /* computed_value_Abs */
298

Michael Beck's avatar
Michael Beck committed
299
/**
300
 * Return the value of an And.
Michael Beck's avatar
Michael Beck committed
301
302
 * Special case: a & 0, 0 & b
 */
303
static tarval *computed_value_And(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
	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 {
		tarval *v;

		if (   (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
			|| (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
			return v;
		}
	}
	return tarval_bad;
321
}  /* computed_value_And */
322

Michael Beck's avatar
Michael Beck committed
323
/**
324
 * Return the value of an Or.
Michael Beck's avatar
Michael Beck committed
325
326
 * Special case: a | 1...1, 1...1 | b
 */
327
static tarval *computed_value_Or(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
	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 {
		tarval *v;
		if (   (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
			|| (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
			return v;
		}
	}
	return tarval_bad;
344
}  /* computed_value_Or */
345

Michael Beck's avatar
Michael Beck committed
346
/**
347
 * Return the value of an Eor.
Michael Beck's avatar
Michael Beck committed
348
 */
349
static tarval *computed_value_Eor(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
350
351
	ir_node *a = get_Eor_left(n);
	ir_node *b = get_Eor_right(n);
352

Michael Beck's avatar
Michael Beck committed
353
	tarval *ta, *tb;
Michael Beck's avatar
Michael Beck committed
354

Michael Beck's avatar
Michael Beck committed
355
356
	if (a == b)
		return get_mode_null(get_irn_mode(n));
Michael Beck's avatar
Michael Beck committed
357

Michael Beck's avatar
Michael Beck committed
358
359
	ta = value_of(a);
	tb = value_of(b);
360

Michael Beck's avatar
Michael Beck committed
361
362
363
364
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_eor (ta, tb);
	}
	return tarval_bad;
365
}  /* computed_value_Eor */
366

Michael Beck's avatar
Michael Beck committed
367
/**
368
 * Return the value of a Not.
Michael Beck's avatar
Michael Beck committed
369
 */
370
static tarval *computed_value_Not(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
371
372
	ir_node *a = get_Not_op(n);
	tarval *ta = value_of(a);
373

Michael Beck's avatar
Michael Beck committed
374
375
	if (ta != tarval_bad)
		return tarval_not(ta);
376

Michael Beck's avatar
Michael Beck committed
377
	return tarval_bad;
378
}  /* computed_value_Not */
379

Michael Beck's avatar
Michael Beck committed
380
/**
381
 * Return the value of a Shl.
Michael Beck's avatar
Michael Beck committed
382
 */
383
static tarval *computed_value_Shl(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
384
385
	ir_node *a = get_Shl_left(n);
	ir_node *b = get_Shl_right(n);
386

Michael Beck's avatar
Michael Beck committed
387
388
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
389

Michael Beck's avatar
Michael Beck committed
390
391
392
393
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shl (ta, tb);
	}
	return tarval_bad;
394
}  /* computed_value_Shl */
395

Michael Beck's avatar
Michael Beck committed
396
/**
397
 * Return the value of a Shr.
Michael Beck's avatar
Michael Beck committed
398
 */
399
static tarval *computed_value_Shr(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
400
401
	ir_node *a = get_Shr_left(n);
	ir_node *b = get_Shr_right(n);
402

Michael Beck's avatar
Michael Beck committed
403
404
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
405

Michael Beck's avatar
Michael Beck committed
406
407
408
409
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shr (ta, tb);
	}
	return tarval_bad;
410
}  /* computed_value_Shr */
411

Michael Beck's avatar
Michael Beck committed
412
/**
413
 * Return the value of a Shrs.
Michael Beck's avatar
Michael Beck committed
414
 */
415
static tarval *computed_value_Shrs(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
416
417
	ir_node *a = get_Shrs_left(n);
	ir_node *b = get_Shrs_right(n);
418

Michael Beck's avatar
Michael Beck committed
419
420
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
421

Michael Beck's avatar
Michael Beck committed
422
423
424
425
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_shrs (ta, tb);
	}
	return tarval_bad;
426
}  /* computed_value_Shrs */
427

Michael Beck's avatar
Michael Beck committed
428
/**
429
 * Return the value of a Rot.
Michael Beck's avatar
Michael Beck committed
430
 */
Michael Beck's avatar
Michael Beck committed
431
432
433
static tarval *computed_value_Rot(ir_node *n) {
	ir_node *a = get_Rot_left(n);
	ir_node *b = get_Rot_right(n);
434

Michael Beck's avatar
Michael Beck committed
435
436
	tarval *ta = value_of(a);
	tarval *tb = value_of(b);
437

Michael Beck's avatar
Michael Beck committed
438
439
440
441
	if ((ta != tarval_bad) && (tb != tarval_bad)) {
		return tarval_rot (ta, tb);
	}
	return tarval_bad;
442
}  /* computed_value_Rot */
443

Michael Beck's avatar
Michael Beck committed
444
/**
445
 * Return the value of a Conv.
Michael Beck's avatar
Michael Beck committed
446
 */
Michael Beck's avatar
Michael Beck committed
447
448
449
static tarval *computed_value_Conv(ir_node *n) {
	ir_node *a = get_Conv_op(n);
	tarval *ta = value_of(a);
450

Michael Beck's avatar
Michael Beck committed
451
452
	if (ta != tarval_bad)
		return tarval_convert_to(ta, get_irn_mode(n));
453

Michael Beck's avatar
Michael Beck committed
454
	return tarval_bad;
455
}  /* computed_value_Conv */
456

457
/**
458
 * Return the value of a Proj(Cmp).
459
460
461
462
463
464
465
 *
 * 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
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
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
static tarval *computed_value_Proj_Cmp(ir_node *n) {
	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 {
			ir_node *aaa = skip_Id(skip_Proj(aa));
			ir_node *aba = skip_Id(skip_Proj(ab));

			if (   (   (/* aa is ProjP and aaa is Alloc */
			               (get_irn_op(aa) == op_Proj)
			            && (mode_is_reference(get_irn_mode(aa)))
			            && (get_irn_op(aaa) == op_Alloc))
			        && (   (/* ab is NULL */
			                   (get_irn_op(ab) == op_Const)
			                && (mode_is_reference(get_irn_mode(ab)))
			                && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
			            || (/* ab is other Alloc */
			                   (get_irn_op(ab) == op_Proj)
			                && (mode_is_reference(get_irn_mode(ab)))
			                && (get_irn_op(aba) == op_Alloc)
			                && (aaa != aba))))
			    || (/* aa is NULL and aba is Alloc */
			           (get_irn_op(aa) == op_Const)
			        && (mode_is_reference(get_irn_mode(aa)))
			        && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
			        && (get_irn_op(ab) == op_Proj)
			        && (mode_is_reference(get_irn_mode(ab)))
			        && (get_irn_op(aba) == op_Alloc)))
				/* 3.: */
			return new_tarval_from_long(proj_nr & pn_Cmp_Ne, mode_b);
		}
	}
	return computed_value_Cmp_Confirm(a, aa, ab, proj_nr);
569
}  /* computed_value_Proj_Cmp */
570

Michael Beck's avatar
Michael Beck committed
571
/**
572
573
 * Return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod),
 * Proj(DivMod) and Proj(Quot).
Michael Beck's avatar
Michael Beck committed
574
 */
575
static tarval *computed_value_Proj(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
	ir_node *a = get_Proj_pred(n);
	long proj_nr;

	switch (get_irn_opcode(a)) {
	case iro_Cmp:
		return computed_value_Proj_Cmp(n);

	case iro_DivMod:
		/* compute either the Div or the Mod part */
		proj_nr = get_Proj_proj(n);
		if (proj_nr == pn_DivMod_res_div)
			return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
		else if (proj_nr == pn_DivMod_res_mod)
			return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
		break;

	case iro_Div:
		if (get_Proj_proj(n) == pn_Div_res)
			return computed_value(a);
		break;

	case iro_Mod:
		if (get_Proj_proj(n) == pn_Mod_res)
			return computed_value(a);
		break;

	case iro_Quot:
		if (get_Proj_proj(n) == pn_Quot_res)
			return computed_value(a);
		break;

	default:
		return tarval_bad;
	}
	return tarval_bad;
611
}  /* computed_value_Proj */
612

613
/**
614
615
 * Calculate the value of a Mux: can be evaluated, if the
 * sel and the right input are known.
616
 */
617
static tarval *computed_value_Mux(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
618
619
620
621
622
623
624
625
626
627
628
629
	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;
630
}  /* computed_value_Mux */
631

Michael Beck's avatar
BugFix:    
Michael Beck committed
632
633
634
635
636
/**
 * Calculate the value of a Psi: can be evaluated, if a condition is true
 * and all previous conditions are false. If all conditions are false
 * we evaluate to the default one.
 */
637
static tarval *computed_value_Psi(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
638
639
640
	if (is_Mux(n))
		return computed_value_Mux(n);
	return tarval_bad;
641
}  /* computed_value_Psi */
Michael Beck's avatar
BugFix:    
Michael Beck committed
642

Michael Beck's avatar
Michael Beck committed
643
/**
644
 * Calculate the value of a Confirm: can be evaluated,
Michael Beck's avatar
Michael Beck committed
645
646
 * if it has the form Confirm(x, '=', Const).
 */
647
static tarval *computed_value_Confirm(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
648
649
	return get_Confirm_cmp(n) == pn_Cmp_Eq ?
		value_of(get_Confirm_bound(n)) : tarval_bad;
650
}  /* computed_value_Confirm */
Michael Beck's avatar
Michael Beck committed
651

652
653
654
/**
 * If the parameter n can be computed, return its value, else tarval_bad.
 * Performs constant folding.
655
656
 *
 * @param n  The node this should be evaluated
657
 */
658
tarval *computed_value(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
659
660
661
	if (n->op->ops.computed_value)
		return n->op->ops.computed_value(n);
	return tarval_bad;
662
}  /* computed_value */
Christian Schäfer's avatar
Christian Schäfer committed
663

664
/**
665
 * Set the default computed_value evaluator in an ir_op_ops.
Michael Beck's avatar
Michael Beck committed
666
667
668
669
670
671
 *
 * @param code   the opcode for the default operation
 * @param ops    the operations initialized
 *
 * @return
 *    The operations.
672
 */
673
674
static ir_op_ops *firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops)
{
Michael Beck's avatar
Michael Beck committed
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
#define CASE(a)                                    \
	case iro_##a:                                  \
		ops->computed_value  = computed_value_##a; \
		break

	switch (code) {
	CASE(Const);
	CASE(SymConst);
	CASE(Add);
	CASE(Sub);
	CASE(Minus);
	CASE(Mul);
	CASE(Quot);
	CASE(Div);
	CASE(Mod);
	CASE(Abs);
	CASE(And);
	CASE(Or);
	CASE(Eor);
	CASE(Not);
	CASE(Shl);
	CASE(Shr);
	CASE(Shrs);
	CASE(Rot);
	CASE(Carry);
	CASE(Borrow);
	CASE(Conv);
	CASE(Proj);
	CASE(Mux);
	CASE(Psi);
	CASE(Confirm);
	default:
		/* leave NULL */;
	}

	return ops;
711
#undef CASE
712
}  /* firm_set_default_computed_value */
Christian Schäfer's avatar
Christian Schäfer committed
713

Michael Beck's avatar
Michael Beck committed
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
/**
 * 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).
 */
730
731
static ir_node *equivalent_node_Block(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
	ir_node *oldn = n;
	int n_preds   = get_Block_n_cfgpreds(n);

	/* The Block constructor does not call optimize, but mature_immBlock
	calls the optimization. */
	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. */
	if ((n_preds == 1) && (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
		ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
		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 ((n_preds == 1) &&
	           (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
		ir_node *predblock = get_Block_cfgpred_block(n, 0);
		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 ((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);

		if ((get_irn_op(a) == op_Proj) &&
		    (get_irn_op(b) == op_Proj) &&
		    (get_Proj_pred(a) == get_Proj_pred(b)) &&
		    (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
		    (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == 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(get_Proj_pred(a));
			DBG_OPT_IFSIM1(oldn, a, b, n);
		}
	} 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;
811
}  /* equivalent_node_Block */
812

813
814
/**
 * Returns a equivalent node for a Jmp, a Bad :-)
815
 * Of course this only happens if the Block of the Jmp is dead.
816
 */
817
static ir_node *equivalent_node_Jmp(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
818
819
820
	/* unreachable code elimination */
	if (is_Block_dead(get_nodes_block(n)))
		n = new_Bad();
821

Michael Beck's avatar
Michael Beck committed
822
	return n;
823
}  /* equivalent_node_Jmp */
824

825
/** Raise is handled in the same way as Jmp. */
826
827
828
#define equivalent_node_Raise   equivalent_node_Jmp


829
830
/* We do not evaluate Cond here as we replace it by a new node, a Jmp.
   See transform_node_Proj_Cond(). */
831

832
/**
833
 * Optimize operations that are commutative and have neutral 0,
834
 * so a op 0 = 0 op a = a.
835
 */
836
837
static ir_node *equivalent_node_neutral_zero(ir_node *n)
{
Michael Beck's avatar
Michael Beck committed
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
	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.
	 */
	if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
		if (get_irn_mode(on) == get_irn_mode(n)) {
			n = on;

			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
		}
	}

	return n;
871
}  /* equivalent_node_neutral_zero */
872

873
874
875
/**
 * Eor is commutative and has neutral 0.
 */
876
#define equivalent_node_Eor  equivalent_node_neutral_zero
877

878
879
880
881
882
/*
 * 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 :-).
883
884
885
 *
 * 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.
886
 */
Michael Beck's avatar
Michael Beck committed
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
static ir_node *equivalent_node_Add(ir_node *n) {
	ir_node *oldn = n;
	ir_node *left, *right;
	ir_mode *mode = get_irn_mode(n);

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

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

	left  = get_Add_left(n);
	right = get_Add_right(n);

	if (get_irn_op(left) == op_Sub) {
		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;
			}
		}
	}
	if (get_irn_op(right) == op_Sub) {
		if (get_Sub_right(right) == left) {
			/* x + (a - x) */

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

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

Michael Beck's avatar
Michael Beck committed
935
936
	ir_node *a = get_binop_left(n);
	ir_node *b = get_binop_right(n);
937

Michael Beck's avatar
Michael Beck committed
938
939
	if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
		n = a;
940

Michael Beck's avatar
Michael Beck committed
941
942
943
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
	}
	return n;
944
}  /* equivalent_node_left_zero */
945

946
947
948
949
#define equivalent_node_Shl   equivalent_node_left_zero
#define equivalent_node_Shr   equivalent_node_left_zero
#define equivalent_node_Shrs  equivalent_node_left_zero
#define equivalent_node_Rot   equivalent_node_left_zero
950

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

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

	b = get_Sub_right(n);

	/* Beware: modes might be different */
	if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
973
		ir_node *a = get_Sub_left(n);
Michael Beck's avatar
Michael Beck committed
974
975
976
977
978
979
980
		if (mode == get_irn_mode(a)) {
			n = a;

			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
		}
	}
	return n;
981
}  /* equivalent_node_Sub */
982
983


984
/**
Michael Beck's avatar
Michael Beck committed
985
 * Optimize an "idempotent unary op", ie op(op(n)) = n.
986
 *
987
988
989
990
 * @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.
991
 */
Michael Beck's avatar
Michael Beck committed
992
993
994
static ir_node *equivalent_node_idempotent_unop(ir_node *n) {
	ir_node *oldn = n;
	ir_node *pred = get_unop_op(n);
995

Michael Beck's avatar
Michael Beck committed
996
997
998
	/* optimize symmetric unop */
	if (get_irn_op(pred) == get_irn_op(n)) {
		n = get_unop_op(pred);
999
		DBG_OPT_ALGSIM2(oldn, pred, n, FS_OPT_IDEM_UNARY);
Michael Beck's avatar
Michael Beck committed
1000
1001
	}
	return n;
1002
}  /* equivalent_node_idempotent_unop */
1003

1004
/** Optimize Not(Not(x)) == x. */
Michael Beck's avatar
Michael Beck committed
1005
#define equivalent_node_Not    equivalent_node_idempotent_unop
1006

Christoph Mallon's avatar
Christoph Mallon committed
1007
/** -(-x) == x       ??? Is this possible or can --x raise an
1008
                       out of bounds exception if min =! max? */
Michael Beck's avatar
Michael Beck committed
1009
#define equivalent_node_Minus  equivalent_node_idempotent_unop
1010

1011
1012
1013
/**
 * Optimize a * 1 = 1 * a = a.
 */
Michael Beck's avatar
Michael Beck committed
1014
1015
1016
1017
static ir_node *equivalent_node_Mul(ir_node *n) {
	ir_node *oldn = n;
	ir_node *a = get_Mul_left(n);

Michael Beck's avatar
Michael Beck committed
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
	/* we can handle here only the n * n = n bit cases */
	if (get_irn_mode(n) == get_irn_mode(a)) {
		ir_node *b = get_Mul_right(n);

		/* Mul is commutative and has again an other neutral element. */
		if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
			n = b;
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
		} else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
			n = a;
			DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
		}
Michael Beck's avatar
Michael Beck committed
1030
1031
	}
	return n;
1032
}  /* equivalent_node_Mul */
1033

1034
1035
1036
/**
 * Optimize a / 1 = a.
 */
1037
static ir_node *equivalent_node_Div(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
1038
1039
1040
1041
1042
1043
1044
	ir_node *a = get_Div_left(n);
	ir_node *b = get_Div_right(n);

	/* Div is not commutative. */
	if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
		/* Turn Div into a tuple (mem, bad, a) */
		ir_node *mem = get_Div_mem(n);
1045
		ir_node *blk = get_irn_n(n, -1);
Michael Beck's avatar
Michael Beck committed
1046
		turn_into_tuple(n, pn_Div_max);
1047
1048
1049
1050
		set_Tuple_pred(n, pn_Div_M,         mem);
		set_Tuple_pred(n, pn_Div_X_regular, new_r_Jmp(current_ir_graph, blk));
		set_Tuple_pred(n, pn_Div_X_except,  new_Bad());        /* no exception */
		set_Tuple_pred(n, pn_Div_res,       a);
Michael Beck's avatar
Michael Beck committed
1051
1052
	}
	return n;
1053
}  /* equivalent_node_Div */
1054

1055
1056
1057
1058
/**
 * Optimize a / 1.0 = a.
 */
static ir_node *equivalent_node_Quot(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
1059
1060
1061
1062
1063
	ir_node *a = get_Quot_left(n);
	ir_node *b = get_Quot_right(n);

	/* Div is not commutative. */
	if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* Quot(x, 1) == x */
1064
		/* Turn Quot into a tuple (mem, jmp, bad, a) */
Michael Beck's avatar
Michael Beck committed
1065
		ir_node *mem = get_Quot_mem(n);
1066
		ir_node *blk = get_irn_n(n, -1);
Michael Beck's avatar
Michael Beck committed
1067
		turn_into_tuple(n, pn_Quot_max);
1068
1069
1070
1071
		set_Tuple_pred(n, pn_Quot_M,         mem);
		set_Tuple_pred(n, pn_Quot_X_regular, new_r_Jmp(current_ir_graph, blk));
		set_Tuple_pred(n, pn_Quot_X_except,  new_Bad());        /* no exception */
		set_Tuple_pred(n, pn_Quot_res,       a);
Michael Beck's avatar
Michael Beck committed
1072
1073
	}
	return n;
1074
}  /* equivalent_node_Quot */
1075

Michael Beck's avatar
Michael Beck committed
1076
1077
1078
/**
 * Optimize a / 1 = a.
 */
1079
static ir_node *equivalent_node_DivMod(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
1080
1081
1082
1083
	ir_node *b = get_DivMod_right(n);

	/* Div is not commutative. */
	if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
1084
		/* Turn DivMod into a tuple (mem, jmp, bad, a, 0) */
1085
		ir_node *a = get_DivMod_left(n);
Michael Beck's avatar
Michael Beck committed
1086
		ir_node *mem = get_Div_mem(n);
1087
		ir_node *blk = get_irn_n(n, -1);
1088
		ir_mode *mode = get_DivMod_resmode(n);
Michael Beck's avatar
Michael Beck committed
1089
1090

		turn_into_tuple(n, pn_DivMod_max);
1091
1092
1093
1094
1095
		set_Tuple_pred(n, pn_DivMod_M,         mem);
		set_Tuple_pred(n, pn_DivMod_X_regular, new_r_Jmp(current_ir_graph, blk));
		set_Tuple_pred(n, pn_DivMod_X_except,  new_Bad());        /* no exception */
		set_Tuple_pred(n, pn_DivMod_res_div,   a);
		set_Tuple_pred(n, pn_DivMod_res_mod,   new_Const(mode, get_mode_null(mode)));
Michael Beck's avatar
Michael Beck committed
1096
1097
	}
	return n;
1098
}  /* equivalent_node_DivMod */
Michael Beck's avatar
Michael Beck committed
1099

Michael Beck's avatar
Michael Beck committed
1100
1101
1102
/**
 * Use algebraic simplification a | a = a | 0 = 0 | a = a.
 */
1103
static ir_node *equivalent_node_Or(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
	ir_node *oldn = n;

	ir_node *a = get_Or_left(n);
	ir_node *b = get_Or_right(n);

	if (a == b) {
		n = a;    /* Or has it's own neutral element */
		DBG_OPT_ALGSIM0(oldn, n, FS_OPT_OR);
	} else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
		n = b;
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_OR);
	} else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
		n = a;
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_OR);
	}

	return n;
1121
}  /* equivalent_node_Or */
Michael Beck's avatar
Michael Beck committed
1122

1123
1124
1125
/**
 * Optimize a & 0b1...1 = 0b1...1 & a =  a & a = a.
 */
1126
static ir_node *equivalent_node_And(ir_node *n) {
Michael Beck's avatar
Michael Beck committed
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
	ir_node *oldn = n;

	ir_node *a = get_And_left(n);
	ir_node *b = get_And_right(n);

	if (a == b) {
		n = a;    /* And has it's own neutral element */
		DBG_OPT_ALGSIM0(oldn, n, FS_OPT_AND);
	} else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
		n = b;
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
	} else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
		n = a;
		DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
	}
	return n;
1143
}  /* equivalent_node_And */