3 * File name: ir/opt/opt_confirms.c
4 * Purpose: Optimizations regarding Confirm nodes
9 * Copyright: (c) 1998-2005 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
19 #include "opt_confirms.h"
22 MIN_INCLUDED = 0x00, /**< [min, ... */
23 MAX_INCLUDED = 0x00, /**< ..., max] */
24 MIN_EXCLUDED = 0x01, /**< (min, ... */
25 MAX_EXCLUDED = 0x02 /**< ..., max) */
29 * An interval. We could use
30 * intervals that ALWAYS include its borders, even for
31 * floating point, as the precision is limited.
32 * However, as our tarval module did not support
33 * such kind of operation, we use border flags allowing
36 typedef struct _interval_t {
37 tarval *min; /**< lowest border */
38 tarval *max; /**< highest border */
39 unsigned char flags; /**< border flags */
43 * Check, if the value of a node is != 0.
45 * This is a often needed case, so we handle here Confirm
48 int value_not_zero(ir_node *n)
50 #define RET_ON(x) if (x) return 1; break
56 while (get_irn_op(n) == op_Confirm) {
58 * Note: A Confirm is never after a Const. So,
59 * we simply can check the bound for beeing a Const
60 * without the fear that is might be hidden by a further Confirm.
62 tv = value_of(get_Confirm_bound(n));
66 mode = get_tarval_mode(tv);
67 pnc = tarval_cmp(tv, get_mode_null(mode));
69 switch (get_Confirm_cmp(n)) {
70 case pn_Cmp_Eq: /* n == C /\ C != 0 ==> n != 0, should never happen, but simple */
71 RET_ON(pnc != pn_Cmp_Eq);
72 case pn_Cmp_Lg: /* n != C /\ C == 0 ==> n != 0 */
73 RET_ON(pnc == pn_Cmp_Eq);
74 case pn_Cmp_Lt: /* n < C /\ C <= 0 ==> n != 0 */
75 RET_ON(pnc == pn_Cmp_Lt || pnc == pn_Cmp_Eq);
76 case pn_Cmp_Le: /* n <= C /\ C < 0 ==> n != 0 */
77 RET_ON(pnc == pn_Cmp_Lt);
78 case pn_Cmp_Ge: /* n >= C /\ C > 0 ==> n != 0 */
79 RET_ON(pnc == pn_Cmp_Gt);
80 case pn_Cmp_Gt: /* n > C /\ C >= 0 ==> n != 0 */
81 RET_ON(pnc == pn_Cmp_Gt || pnc == pn_Cmp_Eq);
86 /* there might be several Confirms one after other that form an interval */
87 n = get_Confirm_value(n);
91 return (tv != tarval_bad) && (classify_tarval(tv) != TV_CLASSIFY_NULL);
97 * Check, if the value of a node can be confirmed >= 0 or <= 0,
98 * If the mode of the value did not honor signed zeros, else
99 * check for >= 0 or < 0.
101 value_classify classify_value_sign(ir_node *n)
107 if (get_irn_op(n) != op_Confirm)
108 return VALUE_UNKNOWN;
110 tv = value_of(get_Confirm_bound(n));
111 if (tv == tarval_bad)
112 return VALUE_UNKNOWN;
114 mode = get_irn_mode(n);
117 * We can handle only >=, >, <, <= cases.
118 * We could handle == too, but this will be optimized into
121 * Note that for integer modes we have a slightly better
122 * optimization possibilities, so we handle this
125 cmp = get_Confirm_cmp(n);
130 * must be x < c <= 1 to be useful if integer mode and -0 = 0
131 * x < c <= 0 to be useful else
135 * must be x <= c < 1 to be useful if integer mode and -0 = 0
136 * x <= c < 0 to be useful else
138 c = mode_is_int(mode) && mode_honor_signed_zeros(mode) ?
139 get_mode_one(mode) : get_mode_null(mode);
141 ncmp = tarval_cmp(tv, c) ^ pn_Cmp_Eq;
143 return VALUE_UNKNOWN;
146 return VALUE_NEGATIVE;
150 * must be x >= c > -1 to be useful if integer mode
151 * x >= c >= 0 to be useful else
155 * must be x > c >= -1 to be useful if integer mode
156 * x > c >= 0 to be useful else
158 if (mode_is_int(mode)) {
159 c = get_mode_minus_one(mode);
161 ncmp = tarval_cmp(tv, c) ^ pn_Cmp_Eq;
163 return VALUE_UNKNOWN;
166 c = get_mode_minus_one(mode);
168 ncmp = tarval_cmp(tv, c);
170 if (ncmp != pn_Cmp_Eq && ncmp != pn_Cmp_Gt)
171 return VALUE_UNKNOWN;
175 return VALUE_POSITIVE;
178 return VALUE_UNKNOWN;
183 * construct an interval from a value
185 static interval_t *get_interval_from_tv(interval_t *iv, tarval *tv)
187 ir_mode *mode = get_tarval_mode(tv);
189 if (tv == tarval_bad) {
191 iv->min = get_mode_min(mode);
192 iv->max = get_mode_max(mode);
193 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
201 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
207 * construct an interval from a Confirm
209 static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc)
211 ir_mode *mode = get_irn_mode(bound);
212 tarval *tv = value_of(bound);
214 if (tv == tarval_bad) {
216 iv->min = get_mode_min(mode);
217 iv->max = get_mode_max(mode);
218 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
223 /* check which side is known */
229 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
234 iv->min = get_mode_min(mode);
236 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
241 iv->min = get_mode_min(mode);
243 iv->flags = MIN_INCLUDED | MAX_EXCLUDED;
249 iv->max = get_mode_max(mode);
250 iv->flags = MIN_EXCLUDED | MAX_INCLUDED;
256 iv->max = get_mode_max(mode);
257 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
262 * We did not handle UNORDERED yet. It is not
263 * clear, if this could give any gain.
267 iv->min = get_mode_min(mode);
268 iv->max = get_mode_max(mode);
269 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
275 * Try to evaluate l_iv pnc r_iv.
277 * @param l_iv the left interval
278 * @param r_iv the right interval
279 * @param pnc the compare relation
282 * tarval_b_true or tarval_b_false it it can be evaluated,
285 static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
289 tarval *tv_true = tarval_b_true, *tv_false = tarval_b_false;
292 * save some cases: we invert all cases with a >
293 * Note that this turn Lg into Eq also (which is desired).
295 if (pnc & pn_Cmp_Gt) {
296 pnc = get_inversed_pnc(pnc);
298 tv_true = tarval_b_false;
299 tv_false = tarval_b_true;
304 /* two intervals can be compared for equality only if they are a single value */
305 if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
306 return l_iv->min == r_iv->min ? tv_true : tv_false;
310 res = tarval_cmp(l_iv->max, r_iv->min);
312 /* [a, b] < [c, d] */
313 if (res == pn_Cmp_Lt)
315 /* if one border is excluded, <= is ok */
316 if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
320 /* [a, b) >= [c, d] or [a, b] >= (c, d] */
321 flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
324 res = tarval_cmp(l_iv->max, r_iv->min);
326 if (res == pn_Cmp_Gt || res == pn_Cmp_Eq)
332 /* [a, b) <= [c, d] or [a, b] <= (c, d] */
333 flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
336 res = tarval_cmp(l_iv->max, r_iv->min);
338 if (res == pn_Cmp_Lt || res == pn_Cmp_Eq)
342 res = tarval_cmp(l_iv->max, r_iv->min);
344 /* [a, b] > [c, d] */
345 if (res == pn_Cmp_Gt)
347 /* if one border is excluded, >= is ok */
348 if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
360 * Return the value of a Cmp if one or both predecessors
363 * @param left the left operand of the Cmp
364 * @param right the right operand of the Cmp
366 tarval *computed_value_Cmp_Confirm(ir_node *left, ir_node *right, pn_Cmp pnc)
370 interval_t l_iv, r_iv;
373 if (get_irn_op(right) == op_Confirm) {
376 /* we want the Confirm on the left side */
381 pnc = get_inversed_pnc(pnc);
383 else if (get_irn_op(left) != op_Confirm) {
384 /* no Confirm on either one side, finish */
388 /* ok, here at least left is a Confirm, right might be */
389 l_bound = get_Confirm_bound(left);
390 l_pnc = get_Confirm_cmp(left);
392 if (get_irn_op(right) == op_Confirm) {
394 * both sides are Confirm's. Check some rare cases first.
396 ir_node *r_bound = get_Confirm_bound(right);
397 pn_Cmp r_pnc = get_Confirm_cmp(right);
399 /* check for == or != can sometime be made WITHOUT constant bounds */
400 if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) {
401 /* l == r if bound(l) == bound(r) AND pnc(l) == pnc(r) == '=' */
402 if (r_bound == l_bound && r_pnc == l_pnc && r_pnc == pn_Cmp_Eq) {
403 return pnc == pn_Cmp_Eq ? tarval_b_true : tarval_b_false;
407 * Here, we check only the right Confirm, as the left Confirms are
408 * checked later anyway.
411 if (left == r_bound && (r_pnc == pn_Cmp_Eq || r_pnc == pn_Cmp_Lg)) {
412 /* l == bound(r) AND pnc(r) == pnc */
414 return tarval_b_true;
416 /* l == bound(r) AND pnc(r) != pnc */
418 return tarval_b_false;
422 /* now, try interval magic */
423 get_interval(&r_iv, r_bound, r_pnc);
424 get_interval(&l_iv, l_bound, l_pnc);
426 tv = compare_iv(&l_iv, &r_iv, pnc);
427 if (tv != tarval_bad)
431 /* from Here, check only left Confirm */
433 /* check for == or != can sometime be made WITHOUT constant bounds */
434 if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) {
435 if (right == l_bound && (l_pnc == pn_Cmp_Eq || l_pnc == pn_Cmp_Lg)) {
436 /* r == bound(l) AND pnc(l) == pnc */
438 return tarval_b_true;
440 /* r == bound(l) AND pnc(l) != pnc */
442 return tarval_b_false;
446 /* now, only right == Const can help */
447 tv = value_of(right);
449 if (tv != tarval_bad) {
450 get_interval_from_tv(&r_iv, tv);
451 get_interval(&l_iv, l_bound, l_pnc);
453 return compare_iv(&l_iv, &r_iv, pnc);