boolopt.c 21.8 KB
Newer Older
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
7
 */

/**
 * @file
8
 * @brief   boolean condition/control flow optimizations
Michael Beck's avatar
Michael Beck committed
9
 * @author  Matthias Braun, Christoph Mallon, Michael Beck
10
 */
11
#include <assert.h>
12
13

#include "adt/obst.h"
14
#include "../adt/array.h"
Michael Beck's avatar
Michael Beck committed
15
#include "iroptimize.h"
16
17
18
#include "ircons.h"
#include "irgmod.h"
#include "irgwalk.h"
19
#include "irnode_t.h"
20
#include "tv.h"
21
#include "debug.h"
22

23
/** Describes a pair of relative conditions lo < hi, lo rel_lo x, hi rel_hi x */
24
typedef struct cond_pair {
25
26
27
28
29
30
31
	ir_node    *cmp_lo;  /**< The lo compare node. */
	ir_node    *cmp_hi;  /**< The hi compare node. */
	ir_relation rel_lo;  /**< The lo relation node. */
	ir_relation rel_hi;  /**< The hi relation node. */
	ir_tarval  *tv_lo;   /**< The tarval of cmp_lo node. */
	ir_tarval  *tv_hi;   /**< The tarval of cmp_hi node. */
	ir_mode    *lo_mode; /**< The mode of the cmp_lo operands. */
32
33
} cond_pair;

Michael Beck's avatar
Michael Beck committed
34
35
36
37
38
/** Environment for all walker in boolopt. */
typedef struct {
	int changed;  /**< Set if the graph was changed. */
} bool_opt_env_t;

39
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
40

Michael Beck's avatar
Michael Beck committed
41
42
43
44
/**
 * Check if tho given nodes, l and r, represent two compares with
 * ... . If yes, return non-zero and fill the res struct.
 */
45
static bool find_cond_pair(ir_node *const l, ir_node *const r, cond_pair *const res)
46
{
Michael Beck's avatar
Michael Beck committed
47
48
49
50
51
52
53
	if (is_Cmp(l) && is_Cmp(r)) {
		ir_node    *const lol   = get_Cmp_left(l);
		ir_node    *const lor   = get_Cmp_right(l);
		ir_node    *const rol   = get_Cmp_left(r);
		ir_node    *const ror   = get_Cmp_right(r);
		ir_relation const pnc_l = get_Cmp_relation(l);
		ir_relation const pnc_r = get_Cmp_relation(r);
54

Michael Beck's avatar
Michael Beck committed
55
56
57
58
59
		if (is_Const(lor) && is_Const_null(lor) &&
			is_Const(ror) && is_Const_null(ror) &&
			pnc_l == pnc_r &&
			(pnc_l == ir_relation_less_greater || pnc_l == ir_relation_equal)) {
			/* l == (lol !=|== NULL) && r == (rol !=|== NULL) */
60
61
62
63
			res->cmp_lo  = l;
			res->cmp_hi  = r;
			res->rel_lo  = pnc_l;
			res->rel_hi  = pnc_l;
Michael Beck's avatar
Michael Beck committed
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
			res->tv_lo   = get_Const_tarval(lor);
			res->tv_hi   = get_Const_tarval(ror);
			res->lo_mode = get_irn_mode(lor);

			return true;
		}

		if (lol == rol && lor != ror && is_Const(lor) && is_Const(ror)) {
			/* l == (x CMP c_l), r == (x cmp c_r) */
			ir_tarval  *const tv_l  = get_Const_tarval(lor);
			ir_tarval  *const tv_r  = get_Const_tarval(ror);
			ir_relation const rel   = tarval_cmp(tv_l, tv_r);

			res->lo_mode = get_irn_mode(lol);

			if (rel == ir_relation_less) {
				/* c_l < c_r */
				res->cmp_lo  = l;
				res->cmp_hi  = r;
				res->rel_lo  = pnc_l;
				res->rel_hi  = pnc_r;
				res->tv_lo   = tv_l;
				res->tv_hi   = tv_r;
			} else if (rel == ir_relation_greater) {
				/* c_l > c_r */
				res->cmp_lo  = r;
				res->cmp_hi  = l;
				res->rel_lo  = pnc_r;
				res->rel_hi  = pnc_l;
				res->tv_lo   = tv_r;
				res->tv_hi   = tv_l;
			} else {
				/* The constants shall be unequal but comparable.
				 * Local optimizations handle the equal case. */
				return false;
			}
			return true;
101
102
		}
	}
103
	return false;
104
105
}

Christoph Mallon's avatar
Christoph Mallon committed
106
107
108
109
110
111
112
static ir_node *make_Cmp(ir_node *const block, ir_node *const cmp, ir_relation const rel)
{
	ir_node *const l = get_Cmp_left(cmp);
	ir_node *const r = get_Cmp_right(cmp);
	return new_r_Cmp(block, l, r, rel);
}

Michael Beck's avatar
Michael Beck committed
113
/**
114
 * Handle (lo rel_lo x) AND (hi rel_hi x)
Michael Beck's avatar
Michael Beck committed
115
 */
Michael Beck's avatar
Michael Beck committed
116
static ir_node *bool_and(cond_pair* const cpair, ir_node *dst_block)
117
{
118
119
120
121
122
123
124
125
	ir_node *const cmp_lo = cpair->cmp_lo;
	ir_node *const cmp_hi = cpair->cmp_hi;
	if (is_Const(cmp_lo))
		return is_Const_null(cmp_lo) ? cmp_hi : cmp_lo;

	if (is_Const(cmp_hi))
		return is_Const_null(cmp_hi) ? cmp_lo : cmp_hi;

sebastian.buchwald1's avatar
sebastian.buchwald1 committed
126
127
128
129
130
131
	ir_relation        rel_lo = cpair->rel_lo;
	ir_relation  const rel_hi = cpair->rel_hi;
	ir_tarval   *      tv_lo  = cpair->tv_lo;
	ir_tarval   *      tv_hi  = cpair->tv_hi;
	ir_mode     *      mode   = cpair->lo_mode;
	ir_graph    *      irg    = get_irn_irg(cmp_lo);
132
	if ((rel_lo & ~ir_relation_unordered) == ir_relation_equal
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
133
134
135
	    && (rel_hi & ~ir_relation_unordered) == rel_lo
	    && tarval_is_null(tv_lo) && tarval_is_null(tv_hi)
	    && mode == get_tarval_mode(tv_hi)) {
136
		/* p == NULL && q == NULL ==> (p&q) == NULL) */
Michael Beck's avatar
Michael Beck committed
137
		ir_node *lol, *hil, *cmp, *c, *p;
138

Michael Beck's avatar
Michael Beck committed
139
140
		if (mode_is_reference(mode)) {
			mode = find_unsigned_mode(mode);
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
141
			if (!mode)
Michael Beck's avatar
Michael Beck committed
142
143
144
145
146
147
				return NULL;
			tv_lo = tarval_convert_to(tv_lo, mode);
			if (tv_lo == tarval_bad)
				return NULL;
		}
		if (mode_is_int(mode)) {
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
148
149
150
151
			lol = get_Cmp_left(cmp_lo);
			lol = new_r_Conv(dst_block, lol, mode);
			hil = get_Cmp_left(cmp_hi);
			hil = new_r_Conv(dst_block, hil, mode);
152
			p   = new_r_And(dst_block, lol, hil);
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
153
154
			c   = new_r_Const(irg, tv_lo);
			cmp = new_r_Cmp(dst_block, p, c, ir_relation_equal);
155
			return cmp;
Michael Beck's avatar
Michael Beck committed
156
		}
157
158
	}

Michael Beck's avatar
Michael Beck committed
159
	/* the following tests expect one common operand */
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
160
	if (get_Cmp_left(cmp_lo) != get_Cmp_left(cmp_hi))
161
		return NULL;
Michael Beck's avatar
Michael Beck committed
162

163
	/* TODO: for now reject float modes */
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
164
	if (!mode_is_int(mode))
165
		return NULL;
166

167
	/* Beware of NaN's, we can only check for (ordered) != here (which is Lg, not Ne) */
168
169
	if ((rel_lo == ir_relation_less || rel_lo == ir_relation_less_equal || rel_lo == ir_relation_equal) &&
	    (rel_hi == ir_relation_equal || rel_hi == ir_relation_greater_equal || rel_hi == ir_relation_greater)) {
170
		/* x <|<=|== lo && x ==|>=|> hi ==> false */
171
		ir_node *const t = new_r_Const(irg, tarval_b_false);
172
		return t;
173
174
	} else if ((rel_lo == ir_relation_less || rel_lo == ir_relation_less_equal || rel_lo == ir_relation_equal) &&
	           (rel_hi == ir_relation_less || rel_hi == ir_relation_less_equal || rel_hi == ir_relation_less_greater)) {
175
		/* x <|<=|== lo && x <|<=|!= hi ==> x <|<=|== lo */
176
177
178
		return cmp_lo;
	} else if ((rel_lo == ir_relation_greater_equal || rel_lo == ir_relation_greater || rel_lo == ir_relation_less_greater) &&
	           (rel_hi == ir_relation_equal || rel_hi == ir_relation_greater_equal || rel_hi == ir_relation_greater)) {
179
		/* x >=|>|!= lo && x ==|>=|> hi ==> x ==|>=|> hi */
180
		return cmp_hi;
181
	} else if (tarval_is_one(tarval_sub(tv_hi, tv_lo))) { /* lo + 1 == hi */
182
		if (rel_lo == ir_relation_greater_equal && rel_hi == ir_relation_less) {
183
			/* x >= c && x < c + 1 ==> x == c */
Christoph Mallon's avatar
Christoph Mallon committed
184
			return make_Cmp(dst_block, cmp_lo, ir_relation_equal);
185
186
		} else if (rel_lo == ir_relation_greater) {
			if (rel_hi == ir_relation_less_greater) {
187
				/* x > c && x != c + 1 ==> x > c + 1 */
Christoph Mallon's avatar
Christoph Mallon committed
188
				return make_Cmp(dst_block, cmp_hi, ir_relation_greater);
189
			} else if (rel_hi == ir_relation_less) {
190
				/* x > c && x < c + 1 ==> false */
191
				ir_node *const t = new_r_Const(irg, tarval_b_false);
192
				return t;
193
			} else if (rel_hi == ir_relation_less_equal) {
Christoph Mallon's avatar
Christoph Mallon committed
194
195
				/* x > c && x <= c + 1 ==> x == c + 1 */
				return make_Cmp(dst_block, cmp_hi, ir_relation_equal);
196
			}
197
		} else if (rel_lo == ir_relation_less_greater && rel_hi == ir_relation_less) {
198
			/* x != c && c < c + 1 ==> x < c */
Christoph Mallon's avatar
Christoph Mallon committed
199
			return make_Cmp(dst_block, cmp_lo, ir_relation_less);
200
		}
201
	} else if ((rel_lo == ir_relation_greater || rel_lo == ir_relation_greater_equal) &&
202
	           (rel_hi == ir_relation_less || rel_hi == ir_relation_less_equal) &&
203
204
205
	           get_mode_arithmetic(mode) == irma_twos_complement) {
		/* works for two-complements only */
		/* x >|\= lo && x <|<= hi ==> (x - lo) <u|<=u (hi-lo) */
206
		if (rel_lo == ir_relation_greater) {
207
			/* must convert to >= */
Matthias Braun's avatar
Matthias Braun committed
208
209
			ir_mode   *mode = get_tarval_mode(tv_lo);
			ir_tarval *n    = tarval_add(tv_lo, get_mode_one(mode));
210
			if (n != tarval_bad && tarval_cmp(n, tv_lo) == ir_relation_greater) {
211
212
				/* no overflow */
				tv_lo = n;
213
				rel_lo = ir_relation_greater_equal;
214
215
			}
		}
216
		if (rel_lo == ir_relation_greater_equal) {
217
218
219
220
			/* all fine */
			ir_node *const block = get_nodes_block(cmp_hi);
			ir_node *      x     = get_Cmp_left(cmp_hi);
			ir_mode *      mode  = get_irn_mode(x);
221
			ir_node *sub, *cmp, *c, *subc;
222
223
224
225
226
227
228
229
230
231
232
233

			if (mode_is_signed(mode)) {
				/* convert to unsigned */
				mode = find_unsigned_mode(mode);
				if (mode == NULL)
					return NULL;
				x     = new_r_Conv(block, x, mode);
				tv_lo = tarval_convert_to(tv_lo, mode);
				tv_hi = tarval_convert_to(tv_hi, mode);
				if (tv_lo == tarval_bad || tv_hi == tarval_bad)
					return NULL;
			}
234
			c    = new_r_Const(irg, tv_lo);
235
			sub  = new_r_Sub(block, x, c);
236
			subc = new_r_Const(irg, tarval_sub(tv_hi, tv_lo));
237
238
			cmp  = new_r_Cmp(block, sub, subc, rel_hi);
			return cmp;
239
		}
240
	}
241
	return NULL;
242
243
}

Michael Beck's avatar
Michael Beck committed
244
/**
245
 * Handle (lo rel_lo x) OR (hi rel_hi x)
Michael Beck's avatar
Michael Beck committed
246
 */
Michael Beck's avatar
Michael Beck committed
247
static ir_node *bool_or(cond_pair *const cpair, ir_node *dst_block)
248
{
249
250
251
252
253
254
255
256
	ir_node *const cmp_lo = cpair->cmp_lo;
	ir_node *const cmp_hi = cpair->cmp_hi;
	if (is_Const(cmp_lo))
		return is_Const_null(cmp_lo) ? cmp_hi : cmp_lo;

	if (is_Const(cmp_hi))
		return is_Const_null(cmp_hi) ? cmp_lo : cmp_hi;

sebastian.buchwald1's avatar
sebastian.buchwald1 committed
257
258
259
260
261
262
	ir_relation        rel_lo = cpair->rel_lo;
	ir_relation  const rel_hi = cpair->rel_hi;
	ir_tarval   *      tv_lo  = cpair->tv_lo;
	ir_tarval   *      tv_hi  = cpair->tv_hi;
	ir_mode     *      mode   = cpair->lo_mode;
	ir_graph    *      irg    = get_irn_irg(cmp_lo);
263
264
265
266
	if ((rel_lo & ~ir_relation_unordered) == ir_relation_less_greater
	    && (rel_hi & ~ir_relation_unordered) == ir_relation_less_greater
	    && tarval_is_null(tv_lo) && tarval_is_null(tv_hi)
	    && mode == get_tarval_mode(tv_hi)) {
267
		/* p != NULL || q != NULL ==> (p|q) != NULL) */
Michael Beck's avatar
Michael Beck committed
268
		ir_node *lol, *hil, *cmp, *c, *p;
269

Michael Beck's avatar
Michael Beck committed
270
271
		if (mode_is_reference(mode)) {
			mode = find_unsigned_mode(mode);
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
272
			if (!mode)
Michael Beck's avatar
Michael Beck committed
273
274
275
276
277
278
				return NULL;
			tv_lo = tarval_convert_to(tv_lo, mode);
			if (tv_lo == tarval_bad)
				return NULL;
		}
		if (mode_is_int(mode)) {
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
279
280
281
282
			lol = get_Cmp_left(cmp_lo);
			lol = new_r_Conv(dst_block, lol, mode);
			hil = get_Cmp_left(cmp_hi);
			hil = new_r_Conv(dst_block, hil, mode);
283
			p   = new_r_Or(dst_block, lol, hil);
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
284
285
			c   = new_r_Const(irg, tv_lo);
			cmp = new_r_Cmp(dst_block, p, c, ir_relation_less_greater);
286
			return cmp;
Michael Beck's avatar
Michael Beck committed
287
		}
288
289
	}

Michael Beck's avatar
Michael Beck committed
290
	/* the following tests expect one common operand */
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
291
	if (get_Cmp_left(cmp_lo) != get_Cmp_left(cmp_hi))
292
		return NULL;
Michael Beck's avatar
Michael Beck committed
293

294
	/* TODO: for now reject float modes */
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
295
	if (!mode_is_int(mode))
296
		return NULL;
297

298
	/* Beware of NaN's, we can only check for (ordered) != here (which is Lg, not Ne) */
299
300
	if ((rel_lo == ir_relation_greater_equal || rel_lo == ir_relation_greater || rel_lo == ir_relation_less_greater) &&
	    (rel_hi == ir_relation_less || rel_hi == ir_relation_less_equal || rel_hi == ir_relation_less_greater)) {
301
		/* x >=|>|!= lo | x <|<=|!= hi ==> true */
302
		ir_node *const t = new_r_Const(irg, tarval_b_true);
303
		return t;
304
305
	} else if ((rel_lo == ir_relation_less || rel_lo == ir_relation_less_equal || rel_lo == ir_relation_equal) &&
	           (rel_hi == ir_relation_less || rel_hi == ir_relation_less_equal || rel_hi == ir_relation_less_greater)) {
306
		/* x <|<=|== lo || x <|<=|!= hi ==> x <|<=|!= hi */
307
308
309
		return cmp_hi;
	} else if ((rel_lo == ir_relation_greater_equal || rel_lo == ir_relation_greater || rel_lo == ir_relation_less_greater) &&
	           (rel_hi == ir_relation_equal || rel_hi == ir_relation_greater_equal || rel_hi == ir_relation_greater)) {
310
		/* x >=|>|!= lo || x ==|>=|> hi ==> x >=|>|!= lo */
311
		return cmp_lo;
312
	} else if (tarval_is_one(tarval_sub(tv_hi, tv_lo))) { /* lo + 1 == hi */
313
		if (rel_lo == ir_relation_less && rel_hi == ir_relation_greater_equal) {
314
			/* x < c || x >= c + 1 ==> x != c */
Christoph Mallon's avatar
Christoph Mallon committed
315
			return make_Cmp(dst_block, cmp_lo, ir_relation_less_greater);
316
317
		} else if (rel_lo == ir_relation_less_equal) {
			if (rel_hi == ir_relation_equal) {
318
				/* x <= c || x == c + 1 ==> x <= c + 1 */
Christoph Mallon's avatar
Christoph Mallon committed
319
				return make_Cmp(dst_block, cmp_hi, ir_relation_less_equal);
320
			} else if (rel_hi == ir_relation_greater_equal) {
321
				/* x <= c || x >= c + 1 ==> true */
322
				ir_node *const t = new_r_Const(irg, tarval_b_true);
323
				return t;
324
			} else if (rel_hi == ir_relation_greater) {
325
				/* x <= c || x > c + 1 ==> x != c + 1 */
Christoph Mallon's avatar
Christoph Mallon committed
326
				return make_Cmp(dst_block, cmp_hi, ir_relation_less_greater);
327
			}
328
		} else if (rel_lo == ir_relation_equal && rel_hi == ir_relation_greater_equal) {
329
			/* x == c || x >= c + 1 ==> x >= c */
Christoph Mallon's avatar
Christoph Mallon committed
330
			return make_Cmp(dst_block, cmp_lo, ir_relation_greater_equal);
331
		}
332
	} else if ((rel_lo == ir_relation_less || rel_lo == ir_relation_less_equal) &&
333
	           (rel_hi == ir_relation_greater || rel_hi == ir_relation_greater_equal) &&
334
	           get_mode_arithmetic(mode) == irma_twos_complement) {
335
		/* works for two-complements only */
336
		/* x <|<= lo  || x >|>= hi ==> (x - lo) >u|>=u (hi-lo) */
337
		if (rel_lo == ir_relation_less_equal) {
338
			/* must convert to < */
Matthias Braun's avatar
Matthias Braun committed
339
340
			ir_mode   *mode = get_tarval_mode(tv_lo);
			ir_tarval *n    = tarval_add(tv_lo, get_mode_one(mode));
341
			if (n != tarval_bad && tarval_cmp(n, tv_lo) == ir_relation_greater) {
342
343
				/* no overflow */
				tv_lo = n;
344
				rel_lo = ir_relation_less;
345
346
			}
		}
347
		if (rel_lo == ir_relation_less) {
348
349
350
351
			/* all fine */
			ir_node *const block = get_nodes_block(cmp_hi);
			ir_node *      x     = get_Cmp_left(cmp_hi);
			ir_mode *      mode  = get_irn_mode(x);
352
			ir_node *sub, *cmp, *c, *subc;
353
354
355
356
357
358
359
360
361
362
363
364

			if (mode_is_signed(mode)) {
				/* convert to unsigned */
				mode = find_unsigned_mode(mode);
				if (mode == NULL)
					return NULL;
				x     = new_r_Conv(block, x, mode);
				tv_lo = tarval_convert_to(tv_lo, mode);
				tv_hi = tarval_convert_to(tv_hi, mode);
				if (tv_lo == tarval_bad || tv_hi == tarval_bad)
					return NULL;
			}
365
			c    = new_r_Const(irg, tv_lo);
366
			sub  = new_r_Sub(block, x, c);
367
			subc = new_r_Const(irg, tarval_sub(tv_hi, tv_lo));
368
369
			cmp  = new_r_Cmp(block, sub, subc, rel_hi);
			return cmp;
370
		}
371
	}
372
	return NULL;
373
374
}

Michael Beck's avatar
Michael Beck committed
375
376
377
378
/**
 * Walker, tries to optimize Andb and Orb nodes.
 */
static void bool_walk(ir_node *n, void *ctx)
379
{
380
	bool_opt_env_t *env = (bool_opt_env_t*)ctx;
381

382
383
	if (get_irn_mode(n) != mode_b)
		return;
384
385

	if (is_And(n)) {
386
387
388
389
390
391
		ir_node *const l = get_And_left(n);
		ir_node *const r = get_And_right(n);
		ir_node *      replacement;
		cond_pair      cpair;
		if (!find_cond_pair(l, r, &cpair))
			return;
Michael Beck's avatar
Michael Beck committed
392
		replacement = bool_and(&cpair, get_nodes_block(n));
Michael Beck's avatar
Michael Beck committed
393
		if (replacement) {
394
			exchange(n, replacement);
Michael Beck's avatar
Michael Beck committed
395
396
			env->changed = 1;
		}
397
	} else if (is_Or(n)) {
398
399
400
401
402
403
		ir_node *const l = get_Or_left(n);
		ir_node *const r = get_Or_right(n);
		ir_node *      replacement;
		cond_pair      cpair;
		if (!find_cond_pair(l, r, &cpair))
			return;
Michael Beck's avatar
Michael Beck committed
404
		replacement = bool_or(&cpair, get_nodes_block(n));
Michael Beck's avatar
Michael Beck committed
405
		if (replacement) {
406
			exchange(n, replacement);
Michael Beck's avatar
Michael Beck committed
407
408
			env->changed = 1;
		}
409
410
411
	}
}

412
/**
Michael Beck's avatar
Michael Beck committed
413
 * Walker, clear Block marker and Phi lists.
414
415
 */
static void clear_block_infos(ir_node *node, void *env)
416
{
Matthias Braun's avatar
cleanup    
Matthias Braun committed
417
	(void)env;
418
419
420
421
422

	/* we visit blocks before any other nodes (from the block) */
	if (!is_Block(node))
		return;

423
424
425
	/* clear the PHI list */
	set_Block_phis(node, NULL);
	set_Block_mark(node, 0);
426
427
}

428
/**
Michael Beck's avatar
Michael Beck committed
429
 * Walker: collect Phi nodes and mark
430
 */
431
432
static void collect_phis(ir_node *node, void *env)
{
Matthias Braun's avatar
cleanup    
Matthias Braun committed
433
	(void)env;
434
435

	if (is_Phi(node)) {
436
437
		ir_node *block = get_nodes_block(node);
		add_Block_phi(block, node);
438
		return;
439
	}
440
441

	/* Ignore control flow nodes, these will be removed. */
Matthias Braun's avatar
Matthias Braun committed
442
443
	if (get_irn_pinned(node) && !is_Block(node) && !is_cfop(node)) {
		/* found a pinned non-cf node, mark its block */
444
445
		ir_node *block = get_nodes_block(node);
		set_Block_mark(block, 1);
446
447
448
	}
}

449
450
451
452
453
/**
 * If node is a Jmp in a block containing no pinned instruction
 * and having only one predecessor, skip the block and return its
 * cf predecessor, else the node itself.
 */
Michael Beck's avatar
Michael Beck committed
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
static ir_node *skip_empty_blocks(ir_node *node)
{
	while (is_Jmp(node)) {
		ir_node *block = get_nodes_block(node);

		if (get_Block_n_cfgpreds(block) != 1)
			break;

		if (get_Block_mark(block))
			break;

		node = get_Block_cfgpred(block, 0);
	}
	return node;
}

/**
 * Check if two block inputs can be fused.
 * This can be done, if block contains no Phi node that depends on
 * different inputs idx_i and idx_j.
 */
475
476
static int can_fuse_block_inputs(const ir_node *block, int idx_i, int idx_j)
{
Michael Beck's avatar
Michael Beck committed
477
478
479
480
481
482
483
484
485
486
487
488
489
	const ir_node *phi;

	for (phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) {
		if (get_Phi_pred(phi, idx_i) != get_Phi_pred(phi, idx_j))
			return 0;
	}
	return 1;
}

/**
 * Remove block input with given index.
 */
static void remove_block_input(ir_node *block, int idx)
490
{
Michael Beck's avatar
Michael Beck committed
491
	int i, j, n = get_Block_n_cfgpreds(block) - 1;
492
	ir_node *phi;
493

494
	ir_node **ins = ALLOCAN(ir_node*, n);
495

Michael Beck's avatar
Michael Beck committed
496
497
498
499
500
501
	if (n == 1) {
		/* all Phis will be deleted */
		ir_node *next_phi;

		for (phi = get_Block_phis(block); phi != NULL; phi = next_phi) {
			next_phi = get_Phi_next(phi);
502
503
504
505
			if (get_Phi_loop(phi)) {
				remove_keep_alive(phi);
				set_Phi_loop(phi, false);
			}
Michael Beck's avatar
Michael Beck committed
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
			exchange(phi, get_Phi_pred(phi, idx ^ 1));
		}
		set_Block_phis(block, NULL);
	} else {
		for (phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) {
			for (i = j = 0; i <= n; ++i) {
				if (i != idx)
					ins[j++] = get_Phi_pred(phi, i);
			}
			set_irn_in(phi, n, ins);
		}
	}
	for (i = j = 0; i <= n; ++i) {
		if (i != idx)
			ins[j++] = get_Block_cfgpred(block, i);
	}
	set_irn_in(block, n, ins);
}
524

Michael Beck's avatar
Michael Beck committed
525
526
527
528
/**
 * Under the preposition that we have a chain of blocks from
 * from_block to to_block, collapse them all into to_block.
 */
529
530
static void move_nodes_to_block(ir_node *jmp, ir_node *to_block)
{
531
	ir_node *new_jmp = NULL;
Michael Beck's avatar
Michael Beck committed
532
	ir_node *block, *next_block;
533

534
535
536
	for (block = get_nodes_block(jmp); block != to_block; block = next_block) {
		new_jmp = get_Block_cfgpred(block, 0);
		next_block = get_nodes_block(new_jmp);
Michael Beck's avatar
Michael Beck committed
537
538
		exchange(block, to_block);
	}
539
540
	if (new_jmp)
		exchange(jmp, new_jmp);
541
542
}

543
544
545
546
547
548
549
550
551
552
static void normalize_cmp(ir_node **io_cmp, ir_relation *io_rel, ir_tarval **io_tv)
{
	ir_node     *cmp   = *io_cmp;
	ir_relation  rel   = *io_rel;
	ir_node     *block = get_nodes_block(cmp);
	dbg_info    *dbgi  = get_irn_dbg_info(cmp);
	ir_node     *left  = get_Cmp_left(cmp);
	ir_node     *right = get_Cmp_right(cmp);
	*io_rel = get_negated_relation(rel);
	*io_cmp = new_rd_Cmp(dbgi, block, left, right, *io_rel);
553
554
555
	if (is_Cmp(*io_cmp)) {
		*io_tv  = get_Const_tarval(get_Cmp_right(*io_cmp));
	}
556
557
}

Michael Beck's avatar
Michael Beck committed
558
559
560
561
562
563
564
565
566
567
568
569
570
571
/**
 * Block walker:
 *
 * if we can find the following structure,
 *
 *        upper_block
 *         /       |
 *        /        |
 *   lower_block   |
 *     /  \        |
 *   ... low_idx up_idx
 *          \      |
 *            block
 *
572
 * try to convert it into a (x rel_lo c_lo) || (x rel_hi c_hi)
Michael Beck's avatar
Michael Beck committed
573
574
575
 * and optimize.
 */
static void find_cf_and_or_walker(ir_node *block, void *ctx)
576
{
577
	bool_opt_env_t *env = (bool_opt_env_t*)ctx;
Michael Beck's avatar
Michael Beck committed
578
	int low_idx, up_idx;
579
	int n_cfgpreds;
580

581
582
583
584
585
586
587
	/* because we modify the graph in regions we might not visited yet,
	 * Id nodes might arise here. Ignore them.
	 */
	if (is_Id(block))
		return;

	n_cfgpreds = get_Block_n_cfgpreds(block);
588
restart:
Michael Beck's avatar
Michael Beck committed
589
	if (n_cfgpreds < 2)
590
591
		return;

Michael Beck's avatar
Michael Beck committed
592
	for (low_idx = 0; low_idx < n_cfgpreds; ++low_idx) {
593
594
595
596
		ir_node      *lower_block;
		ir_node      *lower_cf;
		ir_node      *cond;

Michael Beck's avatar
Michael Beck committed
597
598
599
		lower_cf = get_Block_cfgpred(block, low_idx);
		lower_cf = skip_empty_blocks(lower_cf);
		if (!is_Proj(lower_cf))
600
601
602
			continue;

		cond = get_Proj_pred(lower_cf);
Michael Beck's avatar
Michael Beck committed
603
		if (!is_Cond(cond))
604
605
			continue;

606
		lower_block = get_nodes_block(cond);
Michael Beck's avatar
Michael Beck committed
607
		if (get_Block_n_cfgpreds(lower_block) != 1)
608
609
610
			continue;

		/* the block must not produce any side-effects */
Michael Beck's avatar
Michael Beck committed
611
		if (get_Block_mark(lower_block))
612
613
			continue;

614
		ir_node *const cond_selector = get_Cond_selector(cond);
615
616
617
618
		if (!is_Cond(cond))
			continue;

		ir_node *const lower_pred = get_Block_cfgpred_block(lower_block, 0);
619
620
		if (lower_pred == NULL)
			continue;
Michael Beck's avatar
Michael Beck committed
621
		for (up_idx = 0; up_idx < n_cfgpreds; ++up_idx) {
622
623
624
625
626
			ir_node   *upper_block;
			ir_node   *upper_cf;
			ir_node   *replacement;
			cond_pair  cpair;

627
628
			upper_cf = get_Block_cfgpred(block, up_idx);
			upper_cf = skip_empty_blocks(upper_cf);
Michael Beck's avatar
Michael Beck committed
629
			if (is_Bad(upper_cf))
630
631
				continue;
			upper_block = get_nodes_block(upper_cf);
Michael Beck's avatar
Michael Beck committed
632
			if (upper_block != lower_pred)
633
				continue;
Michael Beck's avatar
BugFix:    
Michael Beck committed
634
635
			if (!block_dominates(upper_block, block))
				continue;
636
637

			/* we have found the structure */
Michael Beck's avatar
Michael Beck committed
638
639
640
641
642
643
			/* check Phis: There must be NO Phi in block that
			   depends on the existence of low block */
			if (!can_fuse_block_inputs(block, low_idx, up_idx))
				continue;

			/* all fine, try it */
644
645
646
647
			ir_node *const upper_cond = get_Proj_pred(upper_cf);
			if (!is_Cond(upper_cond))
				continue;

648
			ir_node *const upper_cond_selector = get_Cond_selector(upper_cond);
Michael Beck's avatar
Michael Beck committed
649
			if (!find_cond_pair(cond_selector, upper_cond_selector, &cpair))
650
651
652
				continue;

			/* normalize pncs: we need the true case to jump into the
sebastian.buchwald1's avatar
sebastian.buchwald1 committed
653
			 * common block (i.e. conjunctive normal form) */
654
			if (get_Proj_num(lower_cf) == pn_Cond_false) {
655
				if (cpair.cmp_lo == cond_selector) {
656
					normalize_cmp(&cpair.cmp_lo, &cpair.rel_lo, &cpair.tv_lo);
657
				} else {
658
					normalize_cmp(&cpair.cmp_hi, &cpair.rel_hi, &cpair.tv_hi);
659
660
				}
			}
661
			if (get_Proj_num(upper_cf) == pn_Cond_false) {
662
				if (cpair.cmp_lo == upper_cond_selector) {
663
					normalize_cmp(&cpair.cmp_lo, &cpair.rel_lo, &cpair.tv_lo);
664
				} else {
665
					normalize_cmp(&cpair.cmp_hi, &cpair.rel_hi, &cpair.tv_hi);
666
667
668
669
				}
			}

			/* can we optimize the case? */
Michael Beck's avatar
Michael Beck committed
670
			replacement = bool_or(&cpair, upper_block);
Michael Beck's avatar
Michael Beck committed
671
			if (replacement == NULL)
672
673
				continue;

Michael Beck's avatar
Michael Beck committed
674
675
			env->changed = 1;

Michael Beck's avatar
BugFix:    
Michael Beck committed
676
			DB((dbg, LEVEL_1, "boolopt: %+F: fusing (ub %+F lb %+F)\n",
677
				get_irn_irg(upper_block), upper_block, lower_block));
Michael Beck's avatar
BugFix:    
Michael Beck committed
678

Michael Beck's avatar
Michael Beck committed
679
680
681
682
			/* move all expressions on the path to lower/upper block */
			move_nodes_to_block(get_Block_cfgpred(block, up_idx), upper_block);
			move_nodes_to_block(get_Block_cfgpred(block, low_idx), lower_block);

683
684
685
			/* move all nodes from lower block to upper block */
			exchange(lower_block, upper_block);

Michael Beck's avatar
Michael Beck committed
686
			remove_block_input(block, up_idx);
687
			--n_cfgpreds;
688

689
			/* the optimizations expected the true case to jump */
690
			if (get_Proj_num(lower_cf) == pn_Cond_false) {
691
				ir_node *block = get_nodes_block(replacement);
692
				replacement    = new_r_Not(block, replacement);
693
694
695
696
697
698
699
700
			}
			set_Cond_selector(cond, replacement);

			goto restart;
		}
	}
}

701
void opt_bool(ir_graph *const irg)
702
{
Michael Beck's avatar
Michael Beck committed
703
704
	bool_opt_env_t env;

705
706
707
	/* register a debug mask */
	FIRM_DBG_REGISTER(dbg, "firm.opt.bool");

Michael Beck's avatar
Michael Beck committed
708
709
710
711
	env.changed = 0;

	/* optimize simple Andb and Orb cases */
	irg_walk_graph(irg, NULL, bool_walk, &env);
712

Michael Beck's avatar
Michael Beck committed
713
	/* now more complicated cases: find control flow And/Or and optimize. */
714
	ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
715
	irg_walk_graph(irg, clear_block_infos, collect_phis, NULL);
Michael Beck's avatar
Michael Beck committed
716
	irg_block_walk_graph(irg, NULL, find_cf_and_or_walker, &env);
717
	ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
718

719
720
	confirm_irg_properties(irg,
		env.changed ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
721
}