opt_confirms.c 22.9 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.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
/**
 * @file
 * @brief   Optimizations regarding Confirm nodes.
 * @author  Michael Beck
24
 */
Matthias Braun's avatar
Matthias Braun committed
25
#include "config.h"
26

Michael Beck's avatar
Michael Beck committed
27
28
#undef DEBUG_CONFIRM

29
#include "tv_t.h"
Michael Beck's avatar
Michael Beck committed
30
#include "irnode_t.h"
31
#include "iropt_t.h"
32
#include "iropt_dbg.h"
33
#include "iroptimize.h"
34
#include "irflag_t.h"
Michael Beck's avatar
Michael Beck committed
35
#include "irprintf.h"
36
37

enum range_tags {
Michael Beck's avatar
Michael Beck committed
38
39
40
41
	MIN_INCLUDED = 0x00,  /**< [min, ... */
	MAX_INCLUDED = 0x00,  /**< ..., max] */
	MIN_EXCLUDED = 0x01,  /**< (min, ... */
	MAX_EXCLUDED = 0x02   /**< ..., max) */
42
43
44
45
46
47
48
49
50
51
};

/**
 * An interval. We could use
 * intervals that ALWAYS include its borders, even for
 * floating point, as the precision is limited.
 * However, as our tarval module did not support
 * such kind of operation, we use border flags allowing
 * all intervals.
 */
52
typedef struct interval_t {
Matthias Braun's avatar
Matthias Braun committed
53
54
	ir_tarval     *min;   /**< lowest border */
	ir_tarval     *max;   /**< highest border */
Michael Beck's avatar
Michael Beck committed
55
	unsigned char flags;  /**< border flags */
56
57
} interval_t;

Michael Beck's avatar
Michael Beck committed
58
59
#ifdef DEBUG_CONFIRM

60
#define compare_iv(l_iv, r_iv, relation)    compare_iv_dbg(l_iv, r_iv, relation)
Michael Beck's avatar
Michael Beck committed
61
62

/* forward */
63
static tarval *compare_iv_dbg(const interval_t *l_iv, const interval_t *r_iv, ir_relation relation);
Michael Beck's avatar
Michael Beck committed
64
65

/* triangle */
66
#define DBG_OUT_TR(l_relation, l_bound, r_relation, r_bound, relation, v) \
Michael Beck's avatar
Michael Beck committed
67
68
  ir_printf("In %e:\na %= %n && b %= %n  ==>  a %= b == %s\n", \
    get_irg_entity(current_ir_graph), \
69
    l_relation, l_bound, r_relation, r_bound, relation, v)
Michael Beck's avatar
Michael Beck committed
70
71

/* right side */
72
#define DBG_OUT_R(r_relation, r_bound, left, relation, right, v) \
Michael Beck's avatar
Michael Beck committed
73
74
  ir_printf("In %e:\na %= %n ==>  %n %= %n == %s\n", \
    get_irg_entity(current_ir_graph), \
75
    r_relation, r_bound, left, relation, right, v)
Michael Beck's avatar
Michael Beck committed
76
77

/* left side */
78
#define DBG_OUT_L(l_relation, l_bound, left, relation, right, v) \
Michael Beck's avatar
Michael Beck committed
79
80
  ir_printf("In %e:\na %= %n ==>  %n %= %n == %s\n", \
    get_irg_entity(current_ir_graph), \
81
    l_relation, l_bound, left, relation, right, v)
Michael Beck's avatar
Michael Beck committed
82
83
84

#else

85
86
87
#define DBG_OUT_TR(l_relation, l_bound, r_relation, r_bound, relation, v)  (void)0
#define DBG_OUT_R(r_relation, r_bound, left, relation, right, v)  (void)0
#define DBG_OUT_L(l_relation, l_bound, left, relation, right, v)  (void)0
Michael Beck's avatar
Michael Beck committed
88

Michael Beck's avatar
Michael Beck committed
89
#endif /* DEBUG_CONFIRM */
Michael Beck's avatar
Michael Beck committed
90

Michael Beck's avatar
Michael Beck committed
91
/*
92
93
94
95
96
 * Check, if the value of a node is != 0.
 *
 * This is a often needed case, so we handle here Confirm
 * nodes too.
 */
97
FIRM_API int value_not_zero(const ir_node *n, ir_node_cnst_ptr *confirm)
98
{
99
#define RET_ON(x)  if (x) { *confirm = n; return 1; } break
100

Matthias Braun's avatar
Matthias Braun committed
101
	ir_tarval *tv;
Michael Beck's avatar
Michael Beck committed
102
	ir_mode *mode = get_irn_mode(n);
103
	ir_relation relation;
Michael Beck's avatar
Michael Beck committed
104
105

	*confirm = NULL;
106
107

	/* there might be several Confirms one after other that form an interval */
Michael Beck's avatar
Michael Beck committed
108
	for (;;) {
109
110
		if (is_Minus(n)) {
			/* we can safely skip Minus when checking for != 0 */
Michael Beck's avatar
Michael Beck committed
111
112
113
114
115
116
			n = get_unop_op(n);
			continue;
		}
		if (! is_Confirm(n))
			break;

Michael Beck's avatar
Michael Beck committed
117
118
119
120
121
122
123
124
125
		/*
		 * Note: A Confirm is never after a Const. So,
		 * we simply can check the bound for being a Const
		 * without the fear that is might be hidden by a further Confirm.
		 */
		tv = value_of(get_Confirm_bound(n));
		if (tv == tarval_bad)
			return 0;

126
		relation = tarval_cmp(tv, get_mode_null(mode));
Michael Beck's avatar
Michael Beck committed
127
128
129
130
131
132
133
134
135

		/*
		 * Beware: C might by a NaN. It is not clear, what we should do
		 * than. Of course a NaN is != 0, but we might use this function
		 * to remove up Exceptions, and NaN's might generate Exception.
		 * So, we do NOT handle NaNs here for safety.
		 *
		 * Note that only the C != 0 case need additional checking.
		 */
136
137
138
139
140
141
142
143
144
145
146
147
148
		switch (get_Confirm_relation(n)) {
		case ir_relation_equal: /* n == C /\ C != 0 ==> n != 0 */
			RET_ON(relation != ir_relation_equal && relation != ir_relation_unordered);
		case ir_relation_less_greater: /* n != C /\ C == 0 ==> n != 0 */
			RET_ON(relation == ir_relation_equal);
		case ir_relation_less: /* n <  C /\ C <= 0 ==> n != 0 */
			RET_ON(relation == ir_relation_less || relation == ir_relation_equal);
		case ir_relation_less_equal: /* n <= C /\ C <  0 ==> n != 0 */
			RET_ON(relation == ir_relation_less);
		case ir_relation_greater_equal: /* n >= C /\ C >  0 ==> n != 0 */
			RET_ON(relation == ir_relation_greater);
		case ir_relation_greater: /* n >  C /\ C >= 0 ==> n != 0 */
			RET_ON(relation == ir_relation_greater || relation == ir_relation_equal);
Michael Beck's avatar
Michael Beck committed
149
150
151
		default:
			break;
		}
Michael Beck's avatar
Michael Beck committed
152
		n = get_Confirm_value(n);
Michael Beck's avatar
Michael Beck committed
153
154
155
156
157
158
	}
	tv = value_of(n);

	if (tv == tarval_bad)
		return 0;

159
	relation = tarval_cmp(tv, get_mode_null(mode));
Michael Beck's avatar
Michael Beck committed
160
161

	/* again, need check for NaN */
162
	return (relation != ir_relation_equal) && (relation != ir_relation_unordered);
163
164

#undef RET_ON
165
}  /* value_not_zero */
166

Michael Beck's avatar
Michael Beck committed
167
/*
168
 * Check, if the value of a node cannot represent a NULL pointer.
Michael Beck's avatar
Michael Beck committed
169
 *
170
 * - Casts are skipped, Sels are skipped
171
172
 * - A SymConst(entity) is NEVER a NULL pointer
 * - Confirms are evaluated
Michael Beck's avatar
Michael Beck committed
173
 */
174
FIRM_API int value_not_null(const ir_node *n, ir_node_cnst_ptr *confirm)
175
{
Matthias Braun's avatar
Matthias Braun committed
176
	ir_tarval *tv;
Michael Beck's avatar
Michael Beck committed
177
178

	*confirm = NULL;
Michael Beck's avatar
Michael Beck committed
179
	n  = skip_Cast_const(n);
180

181
182
183
184
	tv = value_of(n);
	if (tarval_is_constant(tv) && ! tarval_is_null(tv))
		return 1;

Michael Beck's avatar
Michael Beck committed
185
	assert(mode_is_reference(get_irn_mode(n)));
186
187
188
	/* skip all Sel nodes and Cast's */
	while (is_Sel(n)) {
		n = skip_Cast(get_Sel_ptr(n));
Michael Beck's avatar
Michael Beck committed
189
	}
190
191
192
193
194
195
	while (1) {
		if (is_Cast(n)) { n = get_Cast_op(n); continue; }
		if (is_Proj(n)) { n = get_Proj_pred(n); continue; }
		break;
	}

196
	if (is_SymConst_addr_ent(n)) {
197
		/* global references are never NULL */
Michael Beck's avatar
Michael Beck committed
198
		return 1;
199
	} else if (n == get_irg_frame(get_irn_irg(n))) {
200
201
		/* local references are never NULL */
		return 1;
202
203
204
	} else if (is_Alloc(n)) {
		/* alloc never returns NULL (it throws an exception instead) */
		return 1;
205
	} else {
206
		/* check for more Confirms */
207
		for (; is_Confirm(n); n = skip_Cast(get_Confirm_value(n))) {
208
			if (get_Confirm_relation(n) == ir_relation_less_greater) {
Matthias Braun's avatar
Matthias Braun committed
209
210
				ir_node   *bound = get_Confirm_bound(n);
				ir_tarval *tv    = value_of(bound);
211
212

				if (tarval_is_null(tv)) {
213
214
					*confirm = n;
					return 1;
215
				}
216
			}
Michael Beck's avatar
Michael Beck committed
217
218
219
		}
	}
	return 0;
220
}  /* value_not_null */
Michael Beck's avatar
Michael Beck committed
221

222
223
224
225
226
227
228
229
#ifdef __cplusplus
extern "C++" {
	static inline ir_value_classify_sign operator *(ir_value_classify_sign sign, int mul) {
	return (ir_value_classify_sign) (sign*mul);
	}
}
#endif

230
231
232
233
234
/*
 * Check, if the value of a node can be confirmed >= 0 or <= 0,
 * If the mode of the value did not honor signed zeros, else
 * check for >= 0 or < 0.
 */
235
FIRM_API ir_value_classify_sign classify_value_sign(ir_node *n)
236
{
Matthias Braun's avatar
Matthias Braun committed
237
	ir_tarval *tv, *c;
Michael Beck's avatar
Michael Beck committed
238
	ir_mode *mode;
239
	ir_relation cmp, ncmp;
Michael Beck's avatar
Michael Beck committed
240
	int negate = 1;
Michael Beck's avatar
Michael Beck committed
241

Michael Beck's avatar
Michael Beck committed
242
	for (;;) {
243
		unsigned code = get_irn_opcode(n);
Michael Beck's avatar
Michael Beck committed
244
245
246
247
248
249
250
251
252
253
254
255
256

		switch (code) {
		case iro_Minus:
			negate *= -1;
			n = get_Minus_op(n);
			continue;
		case iro_Confirm:
			break;
		default:
			return value_classified_unknown;
		}
		break;
	}
257
	if (!is_Confirm(n))
Michael Beck's avatar
Michael Beck committed
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
		return value_classified_unknown;

	tv  = value_of(get_Confirm_bound(n));
	if (tv == tarval_bad)
		return value_classified_unknown;

	mode = get_irn_mode(n);

	/*
	 * We can handle only >=, >, <, <= cases.
	 * We could handle == too, but this will be optimized into
	 * a constant either.
	 *
	 * Note that for integer modes we have a slightly better
	 * optimization possibilities, so we handle this
	 * different.
	 */
275
	cmp = get_Confirm_relation(n);
Michael Beck's avatar
Michael Beck committed
276
277

	switch (cmp) {
278
	case ir_relation_less:
Michael Beck's avatar
Michael Beck committed
279
280
281
282
		/*
		 * must be x < c <= 1 to be useful if integer mode and -0 = 0
		 *         x < c <= 0 to be useful else
		 */
283
	case ir_relation_less_equal:
Michael Beck's avatar
Michael Beck committed
284
285
286
287
288
289
290
291
		/*
		 * must be x <= c < 1 to be useful if integer mode and -0 = 0
		 *         x <= c < 0 to be useful else
		 */
		c = mode_is_int(mode) && mode_honor_signed_zeros(mode) ?
			get_mode_one(mode) : get_mode_null(mode);

		ncmp = tarval_cmp(tv, c);
292
293
		if (ncmp == ir_relation_equal)
			ncmp = ir_relation_less_equal;
Michael Beck's avatar
Michael Beck committed
294

295
		if (cmp != (ncmp ^ ir_relation_equal))
Michael Beck's avatar
Michael Beck committed
296
297
298
			return value_classified_unknown;

		/* yep, negative */
Michael Beck's avatar
Michael Beck committed
299
		return value_classified_negative * negate;
Michael Beck's avatar
Michael Beck committed
300

301
	case ir_relation_greater_equal:
Michael Beck's avatar
Michael Beck committed
302
303
304
305
		/*
		 * must be x >= c > -1 to be useful if integer mode
		 *         x >= c >= 0 to be useful else
		 */
306
	case ir_relation_greater:
Michael Beck's avatar
Michael Beck committed
307
308
309
310
311
312
313
314
		/*
		 * must be x > c >= -1 to be useful if integer mode
		 *         x > c >= 0 to be useful else
		 */
		if (mode_is_int(mode)) {
			c = get_mode_minus_one(mode);

			ncmp = tarval_cmp(tv, c);
315
316
			if (ncmp == ir_relation_equal)
				ncmp = ir_relation_greater_equal;
Michael Beck's avatar
Michael Beck committed
317

318
			if (cmp != (ncmp ^ ir_relation_equal))
Michael Beck's avatar
Michael Beck committed
319
320
321
322
323
324
				return value_classified_unknown;
		} else {
			c = get_mode_minus_one(mode);

			ncmp = tarval_cmp(tv, c);

325
			if (ncmp != ir_relation_equal && ncmp != ir_relation_greater)
Michael Beck's avatar
Michael Beck committed
326
327
328
329
				return value_classified_unknown;
		}

		/* yep, positive */
Michael Beck's avatar
Michael Beck committed
330
		return value_classified_positive * negate;
Michael Beck's avatar
Michael Beck committed
331
332
333
334

	default:
		return value_classified_unknown;
	}
335
}  /* classify_value_sign */
336
337
338

/**
 * construct an interval from a value
339
340
341
 *
 * @return the filled interval or NULL if no interval
 *         can be created (happens only on floating point
342
 */
Matthias Braun's avatar
Matthias Braun committed
343
static interval_t *get_interval_from_tv(interval_t *iv, ir_tarval *tv)
344
{
Michael Beck's avatar
Michael Beck committed
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
	ir_mode *mode = get_tarval_mode(tv);

	if (tv == tarval_bad) {
		if (mode_is_float(mode)) {
			/* NaN could be included which we cannot handle */
			iv->min   = tarval_bad;
			iv->max   = tarval_bad;
			iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
			return NULL;
		} else {
			/* [-oo, +oo] */
			iv->min   = get_mode_min(mode);
			iv->max   = get_mode_max(mode);
			iv->flags = MIN_INCLUDED | MAX_INCLUDED;
			return iv;
		}
	}

	if (mode_is_float(mode)) {
		if (tv == get_mode_NAN(mode)) {
			/* arg, we cannot handle NaN's. */
			iv->min   = tarval_bad;
			iv->max   = tarval_bad;
			iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
			return NULL;
		}
	}

	/* [tv, tv] */
	iv->min   = tv;
	iv->max   = tv;
	iv->flags = MIN_INCLUDED | MAX_INCLUDED;

	return iv;
379
}  /* get_interval_from_tv */
380
381
382

/**
 * construct an interval from a Confirm
383
 *
384
385
386
 * @param iv       an empty interval, will be filled
 * @param bound    the bound value
 * @param relation the Confirm compare relation
387
388
389
 *
 * @return the filled interval or NULL if no interval
 *         can be created (happens only on floating point
390
 */
391
static interval_t *get_interval(interval_t *iv, ir_node *bound, ir_relation relation)
392
{
Matthias Braun's avatar
Matthias Braun committed
393
394
	ir_mode   *mode = get_irn_mode(bound);
	ir_tarval *tv   = value_of(bound);
Michael Beck's avatar
Michael Beck committed
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419

	if (tv == tarval_bad) {
		/* There is nothing we could do here. For integer
		 * modes we could return [-oo, +oo], but there is
		 * nothing we could deduct from such an interval.
		 * So, speed things up and return unknown.
		 */
		iv->min   = tarval_bad;
		iv->max   = tarval_bad;
		iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
		return NULL;
	}

	if (mode_is_float(mode)) {
		if (tv == get_mode_NAN(mode)) {
			/* arg, we cannot handle NaN's. */
			iv->min   = tarval_bad;
			iv->max   = tarval_bad;
			iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;

			return NULL;
		}
	}

	/* check which side is known */
420
421
	switch (relation) {
	case ir_relation_equal:
Michael Beck's avatar
Michael Beck committed
422
423
424
425
426
427
		/* [tv, tv] */
		iv->min   =
			iv->max   = tv;
		iv->flags = MIN_INCLUDED | MAX_INCLUDED;
		break;

428
	case ir_relation_less_equal:
Michael Beck's avatar
Michael Beck committed
429
430
431
432
433
434
		/* [-oo, tv] */
		iv->min   = get_mode_min(mode);
		iv->max   = tv;
		iv->flags = MIN_INCLUDED | MAX_INCLUDED;
		break;

435
	case ir_relation_less:
Michael Beck's avatar
Michael Beck committed
436
437
438
439
440
441
		/* [-oo, tv) */
		iv->min   = get_mode_min(mode);
		iv->max   = tv;
		iv->flags = MIN_INCLUDED | MAX_EXCLUDED;
		break;

442
	case ir_relation_greater:
Michael Beck's avatar
Michael Beck committed
443
444
445
446
447
448
		/* (tv, +oo] */
		iv->min   = tv;
		iv->max   = get_mode_max(mode);
		iv->flags = MIN_EXCLUDED | MAX_INCLUDED;
		break;

449
	case ir_relation_greater_equal:
Michael Beck's avatar
Michael Beck committed
450
451
452
453
454
455
		/* [tv, +oo] */
		iv->min   = tv;
		iv->max   = get_mode_max(mode);
		iv->flags = MIN_INCLUDED | MAX_INCLUDED;
		break;

456
	case ir_relation_less_equal_greater:
Michael Beck's avatar
Michael Beck committed
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
		/*
		 * Ordered means, that at least neither
		 * our bound nor our value ara NaN's
		 */
		/* [-oo, +oo] */
		iv->min   = get_mode_min(mode);
		iv->max   = get_mode_max(mode);
		iv->flags = MIN_INCLUDED | MAX_INCLUDED;
		break;

	default:
		/*
		 * We do not handle UNORDERED, as a NaN
		 * could be included in the interval.
		 */
		iv->min   = tarval_bad;
		iv->max   = tarval_bad;
		iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
		return NULL;
	}

	if (iv->min != tarval_bad && iv->max != tarval_bad)
		return iv;
	return NULL;
481
}  /* get_interval */
482
483

/**
484
 * Try to evaluate l_iv relation r_iv.
485
 *
486
487
488
 * @param l_iv      the left interval
 * @param r_iv      the right interval
 * @param relation  the compare relation
489
490
491
492
493
 *
 * @return
 *   tarval_b_true or tarval_b_false it it can be evaluated,
 *   tarval_bad else
 */
494
static ir_tarval *(compare_iv)(const interval_t *l_iv, const interval_t *r_iv, ir_relation relation)
495
{
496
497
498
	ir_relation res;
	unsigned    flags;
	ir_tarval  *tv_true = tarval_b_true, *tv_false = tarval_b_false;
Michael Beck's avatar
Michael Beck committed
499
500
501
502
503
504

	/* if one interval contains NaNs, we cannot evaluate anything */
	if (! l_iv || ! r_iv)
		return tarval_bad;

	/* we can only check ordered relations */
505
	if (relation & ir_relation_unordered) {
Matthias Braun's avatar
Matthias Braun committed
506
		ir_tarval *t;
Michael Beck's avatar
Michael Beck committed
507

508
		relation = get_negated_relation(relation);
Michael Beck's avatar
Michael Beck committed
509
510
511
512
513
514
		t        = tv_true;
		tv_true  = tv_false;
		tv_false = t;
	}

	/* if we have > or >=, we do the inverse to save some cases */
515
	if (relation == ir_relation_greater_equal || relation == ir_relation_greater) {
Michael Beck's avatar
Michael Beck committed
516
517
		const interval_t *t;

518
519
520
521
		relation = get_inversed_relation(relation);
		t        = l_iv;
		l_iv     = r_iv;
		r_iv     = t;
Michael Beck's avatar
Michael Beck committed
522
523
524
	}

	/* now, only the following cases remains */
525
526
	switch (relation) {
	case ir_relation_equal:
Michael Beck's avatar
Michael Beck committed
527
528
		/* two intervals can be compared for equality only if they are a single value */
		if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
529
			return tarval_cmp(l_iv->min, r_iv->min) == ir_relation_equal ? tv_true : tv_false;
Michael Beck's avatar
Michael Beck committed
530
531
532
533
534

		/* if both intervals do not intersect, it is never equal */
		res = tarval_cmp(l_iv->max, r_iv->min);

		/* b < c ==> [a,b] != [c,d] */
535
		if (res == ir_relation_less)
Michael Beck's avatar
Michael Beck committed
536
537
538
539
			return tv_false;

		/* b <= c ==> [a,b) != [c,d]  AND [a,b] != (c,d] */
		if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED)
540
			&& (res == ir_relation_equal))
Michael Beck's avatar
Michael Beck committed
541
542
543
544
545
			return tv_false;

		res = tarval_cmp(r_iv->max, l_iv->min);

		/* d < a ==> [c,d] != [a,b] */
546
		if (res == ir_relation_less)
Michael Beck's avatar
Michael Beck committed
547
548
549
550
			return tv_false;

		/* d <= a ==> [c,d) != [a,b]  AND [c,d] != (a,b] */
		if ((r_iv->flags & MAX_EXCLUDED || l_iv->flags & MIN_EXCLUDED)
551
			&& (res == ir_relation_equal))
Michael Beck's avatar
Michael Beck committed
552
553
554
			return tv_false;
		break;

555
	case ir_relation_less_greater:
Michael Beck's avatar
Michael Beck committed
556
557
		/* two intervals can be compared for not equality only if they are a single value */
		if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
558
			return tarval_cmp(l_iv->min, r_iv->min) != ir_relation_equal ? tv_true : tv_false;
Michael Beck's avatar
Michael Beck committed
559
560
		break;

561
	case ir_relation_less:
Michael Beck's avatar
Michael Beck committed
562
563
564
		res = tarval_cmp(l_iv->max, r_iv->min);

		/* [a, b] < [c, d]  <==> b < c */
565
		if (res == ir_relation_less)
Michael Beck's avatar
Michael Beck committed
566
567
568
569
			return tv_true;

		/* if one border is excluded, b <= c is enough */
		if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
570
			res == ir_relation_equal)
Michael Beck's avatar
Michael Beck committed
571
572
573
574
			return tv_true;

		/* [a, b] >= [c, d] <==> a > d */
		res = tarval_cmp(l_iv->min, r_iv->max);
575
		if (res == ir_relation_greater)
Michael Beck's avatar
Michael Beck committed
576
577
578
579
			return tv_false;

		/* if one border is excluded, a >= d is enough */
		if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
580
			res == ir_relation_equal)
Michael Beck's avatar
Michael Beck committed
581
582
583
			return tv_false;
		break;

584
	case ir_relation_less_equal:
Michael Beck's avatar
Michael Beck committed
585
586
587
588
589
		/* [a, b) <= [c, d] or [a, b] <= (c, d]  <==> b <= c */
		flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
		if (flags) {
			res = tarval_cmp(l_iv->max, r_iv->min);

590
			if (res == ir_relation_less || res == ir_relation_equal)
Michael Beck's avatar
Michael Beck committed
591
592
593
594
595
596
				return tv_true;
		}

		res = tarval_cmp(l_iv->min, r_iv->max);

		/* [a, b] > [c, d] <==> a > d */
597
		if (res == ir_relation_greater)
Michael Beck's avatar
Michael Beck committed
598
599
600
601
			return tv_false;

		/* if one border is excluded, a >= d is enough */
		if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
602
			res == ir_relation_equal)
Michael Beck's avatar
Michael Beck committed
603
604
605
			return tv_false;
		break;

606
	case ir_relation_less_equal_greater:
Michael Beck's avatar
Michael Beck committed
607
608
609
610
611
612
613
		/* Hmm. if both are intervals, we can find an order */
		return tv_true;

	default:
		return tarval_bad;
	}
	return tarval_bad;
614
}  /* compare_iv */
615

Michael Beck's avatar
Michael Beck committed
616
617
618
/**
 * Returns non-zero, if a given relation is transitive.
 */
619
static int is_transitive(ir_relation relation)
620
{
621
	return (ir_relation_false < relation && relation < ir_relation_less_greater);
622
}  /* is_transitive */
Michael Beck's avatar
Michael Beck committed
623

624
625
626
627
/**
 * Return the value of a Cmp if one or both predecessors
 * are Confirm nodes.
 *
628
629
630
631
 * @param cmp      the Cmp node
 * @param left     the left operand of the Cmp
 * @param right    the right operand of the Cmp
 * @param relation the compare relation
632
 */
633
FIRM_API ir_tarval *computed_value_Cmp_Confirm(const ir_node *cmp, ir_node *left, ir_node *right, ir_relation relation)
634
{
Matthias Braun's avatar
Matthias Braun committed
635
	ir_node    *l_bound;
636
	ir_relation l_relation, res_relation, neg_relation;
Matthias Braun's avatar
Matthias Braun committed
637
638
	interval_t  l_iv, r_iv;
	ir_tarval  *tv;
Michael Beck's avatar
Michael Beck committed
639

640
	if (is_Confirm(right)) {
Michael Beck's avatar
Michael Beck committed
641
		/* we want the Confirm on the left side */
642
		ir_node *t = right;
643
		right = left;
Michael Beck's avatar
Michael Beck committed
644
		left  = t;
Michael Beck's avatar
Michael Beck committed
645

646
		relation = get_inversed_relation(relation);
647
	} else if (! is_Confirm(left)) {
648
649
650
		/* nothing more found */
		tv = tarval_bad;
		goto check_null_case;
Michael Beck's avatar
Michael Beck committed
651
652
653
	}

	/* ok, here at least left is a Confirm, right might be */
654
655
	l_bound    = get_Confirm_bound(left);
	l_relation = get_Confirm_relation(left);
Michael Beck's avatar
Michael Beck committed
656

657
	if (is_Confirm(right)) {
Michael Beck's avatar
Michael Beck committed
658
		/*
659
660
		 * both sides are Confirm's. Check some rare cases first.
		 */
661
662
		ir_node    *r_bound    = get_Confirm_bound(right);
		ir_relation r_relation = get_Confirm_relation(right);
Michael Beck's avatar
Michael Beck committed
663
664

		/*
665
666
		 * some check can be made WITHOUT constant bounds
		 */
Michael Beck's avatar
Michael Beck committed
667
		if (r_bound == l_bound) {
668
669
			if (is_transitive(l_relation)) {
				ir_relation r_inc_relation = get_inversed_relation(r_relation);
Michael Beck's avatar
Michael Beck committed
670
671
672
673
674
675
676
677

				/*
				 * triangle inequality:
				 *
				 * a CMP B && B CMP b => a CMP b, !(a ~CMP b)
				 *
				 * We handle correctly cases with some <=/>= here
				 */
678
679
				if ((l_relation & ~ir_relation_equal) == (r_inc_relation & ~ir_relation_equal)) {
					res_relation = (l_relation & ~ir_relation_equal) | (l_relation & r_inc_relation & ir_relation_equal);
Michael Beck's avatar
Michael Beck committed
680

681
682
					if ((relation == res_relation) || ((relation & ~ir_relation_equal) == res_relation)) {
						DBG_OUT_TR(l_relation, l_bound, r_relation, r_bound, relation, "true");
Michael Beck's avatar
Michael Beck committed
683
684
685
						DBG_EVAL_CONFIRM(cmp);
						return tarval_b_true;
					} else {
686
						ir_relation neg_relation = get_negated_relation(relation);
Michael Beck's avatar
Michael Beck committed
687

688
689
						if ((neg_relation == res_relation) || ((neg_relation & ~ir_relation_equal) == res_relation)) {
							DBG_OUT_TR(l_relation, l_bound, r_relation, r_bound, relation, "false");
Michael Beck's avatar
Michael Beck committed
690
691
692
693
694
695
696
697
698
699
700
701
702
703
							DBG_EVAL_CONFIRM(cmp);
							return tarval_b_false;
						}
					}
				}
			}
		}

		/*
		 * Here, we check only the right Confirm, as the left Confirms are
		 * checked later anyway.
		 */
		if (left == r_bound) {
			/*
704
			 * l == bound(r) AND relation(r) == relation:
Michael Beck's avatar
Michael Beck committed
705
706
707
			 *
			 * We know that a CMP b and check for that
			 */
708
709
			if ((r_relation == relation) || (r_relation == (relation & ~ir_relation_equal))) {
				DBG_OUT_R(r_relation, r_bound, left, relation, right, "true");
Michael Beck's avatar
Michael Beck committed
710
711
712
713
				DBG_EVAL_CONFIRM(cmp);
				return tarval_b_true;
			}
			/*
714
			 * l == bound(r) AND relation(r) != relation:
Michael Beck's avatar
Michael Beck committed
715
716
717
718
			 *
			 * We know that a CMP b and check for a ~CMP b
			 */
			else {
719
				neg_relation = get_negated_relation(relation);
Michael Beck's avatar
Michael Beck committed
720

721
722
				if ((r_relation == neg_relation) || (r_relation == (neg_relation & ~ir_relation_equal))) {
					DBG_OUT_R(r_relation, r_bound, left, relation, right, "false");
Michael Beck's avatar
Michael Beck committed
723
724
725
726
727
728
729
730
					DBG_EVAL_CONFIRM(cmp);
					return tarval_b_false;
				}
			}
		}

		/* now, try interval magic */
		tv = compare_iv(
731
732
733
			get_interval(&l_iv, l_bound, l_relation),
			get_interval(&r_iv, r_bound, r_relation),
			relation);
Michael Beck's avatar
Michael Beck committed
734
735
736
737
738
739
740
741
742
743
744
745
746
747

		if (tv != tarval_bad) {
			DBG_EVAL_CONFIRM(cmp);
			return tv;
		}
	}

	/* from Here, check only left Confirm */

	/*
	 * some checks can be made WITHOUT constant bounds
	 */
	if (right == l_bound) {
		/*
748
		 * r == bound(l) AND relation(l) == relation:
Michael Beck's avatar
Michael Beck committed
749
750
751
		 *
		 * We know that a CMP b and check for that
		 */
752
753
		if ((l_relation == relation) || (l_relation == (relation & ~ir_relation_equal))) {
			DBG_OUT_L(l_relation, l_bound, left, relation, right, "true");
Michael Beck's avatar
Michael Beck committed
754
755
756
757
			DBG_EVAL_CONFIRM(cmp);
			return tarval_b_true;
		}
		/*
758
		 * r == bound(l) AND relation(l) is Not(relation):
Michael Beck's avatar
Michael Beck committed
759
760
761
762
		 *
		 * We know that a CMP b and check for a ~CMP b
		 */
		else {
763
			neg_relation = get_negated_relation(relation);
Michael Beck's avatar
Michael Beck committed
764

765
766
			if ((l_relation == neg_relation) || (l_relation == (neg_relation & ~ir_relation_equal))) {
				DBG_OUT_L(l_relation, l_bound, left, relation, right, "false");
Michael Beck's avatar
Michael Beck committed
767
768
769
770
771
772
773
774
775
776
777
				DBG_EVAL_CONFIRM(cmp);
				return tarval_b_false;
			}
		}
	}

	/* now, only right == Const can help */
	tv = value_of(right);

	if (tv != tarval_bad) {
		tv = compare_iv(
778
			get_interval(&l_iv, l_bound, l_relation),
Michael Beck's avatar
Michael Beck committed
779
			get_interval_from_tv(&r_iv, tv),
780
			relation);
781
782
783
	} else {
check_null_case:
		/* check some other cases */
784
		if ((relation == ir_relation_equal || relation == ir_relation_less_greater) &&
785
786
			is_Const(right) && is_Const_null(right)) {
			/* for == 0 or != 0 we have some special tools */
Michael Beck's avatar
Michael Beck committed
787
788
			ir_mode       *mode = get_irn_mode(left);
			const ir_node *dummy;
789
790
			if (mode_is_reference(mode)) {
				if (value_not_null(left, &dummy)) {
791
					tv = relation == ir_relation_equal ? tarval_b_false : tarval_b_true;
792
793
794
				}
			} else {
				if (value_not_zero(left, &dummy)) {
795
					tv = relation == ir_relation_equal ? tarval_b_false : tarval_b_true;
796
797
798
				}
			}
		}
Michael Beck's avatar
Michael Beck committed
799
800
801
802
803
804
	}

	if (tv != tarval_bad)
		DBG_EVAL_CONFIRM(cmp);

	return tv;
805
}  /* computed_value_Cmp_Confirm */
Michael Beck's avatar
Michael Beck committed
806

Michael Beck's avatar
Michael Beck committed
807
#ifdef DEBUG_CONFIRM
Michael Beck's avatar
Michael Beck committed
808
809
/**
 * For debugging. Prints an interval into a string.
Michael Beck's avatar
Michael Beck committed
810
811
812
813
 *
 * @param buf   address of a string buffer
 * @param len   length of the string buffer
 * @param iv    the interval
Michael Beck's avatar
Michael Beck committed
814
 */
815
816
static int iv_snprintf(char *buf, size_t len, const interval_t *iv)
{
Michael Beck's avatar
Michael Beck committed
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
	char smin[64], smax[64];

	if (iv) {
		tarval_snprintf(smin, sizeof(smin), iv->min);

		if (iv->min != iv->max || (iv->flags & (MIN_EXCLUDED|MAX_EXCLUDED))) {
			tarval_snprintf(smax, sizeof(smax), iv->max);

			return snprintf(buf, len, "%c%s, %s%c",
				iv->flags & MIN_EXCLUDED ? '(' : '[',
				smin, smax,
				iv->flags & MAX_EXCLUDED ? ')' : ']'
				);
		} else
			return snprintf(buf, len, "%s", smin);
	}
	return snprintf(buf, len, "<UNKNOWN>");
834
}  /* iv_snprintf */
Michael Beck's avatar
Michael Beck committed
835
836

/**
Michael Beck's avatar
Michael Beck committed
837
838
 * For debugging. Prints an interval compare.
 *
839
840
841
 * @param l_iv      the left interval
 * @param r_iv      the right interval
 * @param relation  the compare relation
Michael Beck's avatar
Michael Beck committed
842
 */
843
static void print_iv_cmp(const interval_t *l_iv, const interval_t *r_iv, ir_relation relation)
844
{
Michael Beck's avatar
Michael Beck committed
845
	char sl[128], sr[128];
Michael Beck's avatar
Michael Beck committed
846

Michael Beck's avatar
Michael Beck committed
847
848
	iv_snprintf(sl, sizeof(sl), l_iv);
	iv_snprintf(sr, sizeof(sr), r_iv);
Michael Beck's avatar
Michael Beck committed
849

850
	ir_printf("%s %= %s", sl, relation, sr);
851
}  /* print_iv_cmp */
Michael Beck's avatar
Michael Beck committed
852
853

/**
Michael Beck's avatar
Michael Beck committed
854
855
 * For debugging. call *compare_iv() and prints inputs and result.
 *
856
857
858
 * @param l_iv     the left interval
 * @param r_iv     the right interval
 * @param relation the compare relation
Michael Beck's avatar
Michael Beck committed
859
 */
860
static tarval *compare_iv_dbg(const interval_t *l_iv, const interval_t *r_iv, ir_relation relation)
861
{
862
	tarval *tv = (compare_iv)(l_iv, r_iv, relation);
Michael Beck's avatar
Michael Beck committed
863

Michael Beck's avatar
Michael Beck committed
864
865
	if (tv == tarval_bad)
	return tv;
Michael Beck's avatar
Michael Beck committed
866

Michael Beck's avatar
Michael Beck committed
867
	ir_printf("In %e:\n", get_irg_entity(current_ir_graph));
868
	print_iv_cmp(l_iv, r_iv, relation);
Michael Beck's avatar
Michael Beck committed
869
870
	ir_printf(" = %T\n", tv);
	return tv;
871
}  /* compare_iv_dbg */
Michael Beck's avatar
Michael Beck committed
872
873

#endif /* DEBUG_CONFIRM */