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);
142 if (ncmp == pn_Cmp_Eq)
145 if (cmp != (ncmp ^ pn_Cmp_Eq))
146 return VALUE_UNKNOWN;
149 return VALUE_NEGATIVE;
153 * must be x >= c > -1 to be useful if integer mode
154 * x >= c >= 0 to be useful else
158 * must be x > c >= -1 to be useful if integer mode
159 * x > c >= 0 to be useful else
161 if (mode_is_int(mode)) {
162 c = get_mode_minus_one(mode);
164 ncmp = tarval_cmp(tv, c);
165 if (ncmp == pn_Cmp_Eq)
168 if (cmp != (ncmp ^ pn_Cmp_Eq))
169 return VALUE_UNKNOWN;
172 c = get_mode_minus_one(mode);
174 ncmp = tarval_cmp(tv, c);
176 if (ncmp != pn_Cmp_Eq && ncmp != pn_Cmp_Gt)
177 return VALUE_UNKNOWN;
181 return VALUE_POSITIVE;
184 return VALUE_UNKNOWN;
189 * construct an interval from a value
191 static interval_t *get_interval_from_tv(interval_t *iv, tarval *tv)
193 ir_mode *mode = get_tarval_mode(tv);
195 if (tv == tarval_bad) {
197 iv->min = get_mode_min(mode);
198 iv->max = get_mode_max(mode);
199 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
207 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
213 * construct an interval from a Confirm
215 static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc)
217 ir_mode *mode = get_irn_mode(bound);
218 tarval *tv = value_of(bound);
220 if (tv == tarval_bad) {
222 iv->min = get_mode_min(mode);
223 iv->max = get_mode_max(mode);
224 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
229 /* check which side is known */
235 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
240 iv->min = get_mode_min(mode);
242 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
247 iv->min = get_mode_min(mode);
249 iv->flags = MIN_INCLUDED | MAX_EXCLUDED;
255 iv->max = get_mode_max(mode);
256 iv->flags = MIN_EXCLUDED | MAX_INCLUDED;
262 iv->max = get_mode_max(mode);
263 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
268 * We did not handle UNORDERED yet. It is not
269 * clear, if this could give any gain.
273 iv->min = get_mode_min(mode);
274 iv->max = get_mode_max(mode);
275 iv->flags = MIN_INCLUDED | MAX_INCLUDED;
281 * Try to evaluate l_iv pnc r_iv.
283 * @param l_iv the left interval
284 * @param r_iv the right interval
285 * @param pnc the compare relation
288 * tarval_b_true or tarval_b_false it it can be evaluated,
291 static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
295 tarval *tv_true = tarval_b_true, *tv_false = tarval_b_false;
298 * save some cases: we invert all cases with a >
299 * Note that this turn Lg into Eq also (which is desired).
301 if (pnc & pn_Cmp_Gt) {
302 pnc = get_inversed_pnc(pnc);
304 tv_true = tarval_b_false;
305 tv_false = tarval_b_true;
310 /* two intervals can be compared for equality only if they are a single value */
311 if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
312 return l_iv->min == r_iv->min ? tv_true : tv_false;
316 res = tarval_cmp(l_iv->max, r_iv->min);
318 /* [a, b] < [c, d] */
319 if (res == pn_Cmp_Lt)
321 /* if one border is excluded, <= is ok */
322 if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
326 /* [a, b) >= [c, d] or [a, b] >= (c, d] */
327 flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
330 res = tarval_cmp(l_iv->max, r_iv->min);
332 if (res == pn_Cmp_Gt || res == pn_Cmp_Eq)
338 /* [a, b) <= [c, d] or [a, b] <= (c, d] */
339 flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
342 res = tarval_cmp(l_iv->max, r_iv->min);
344 if (res == pn_Cmp_Lt || res == pn_Cmp_Eq)
348 res = tarval_cmp(l_iv->max, r_iv->min);
350 /* [a, b] > [c, d] */
351 if (res == pn_Cmp_Gt)
353 /* if one border is excluded, >= is ok */
354 if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
366 * Return the value of a Cmp if one or both predecessors
369 * @param left the left operand of the Cmp
370 * @param right the right operand of the Cmp
372 tarval *computed_value_Cmp_Confirm(ir_node *left, ir_node *right, pn_Cmp pnc)
376 interval_t l_iv, r_iv;
379 if (get_irn_op(right) == op_Confirm) {
382 /* we want the Confirm on the left side */
387 pnc = get_inversed_pnc(pnc);
389 else if (get_irn_op(left) != op_Confirm) {
390 /* no Confirm on either one side, finish */
394 /* ok, here at least left is a Confirm, right might be */
395 l_bound = get_Confirm_bound(left);
396 l_pnc = get_Confirm_cmp(left);
398 if (get_irn_op(right) == op_Confirm) {
400 * both sides are Confirm's. Check some rare cases first.
402 ir_node *r_bound = get_Confirm_bound(right);
403 pn_Cmp r_pnc = get_Confirm_cmp(right);
405 /* check for == or != can sometime be made WITHOUT constant bounds */
406 if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) {
407 /* l == r if bound(l) == bound(r) AND pnc(l) == pnc(r) == '=' */
408 if (r_bound == l_bound && r_pnc == l_pnc && r_pnc == pn_Cmp_Eq) {
409 return pnc == pn_Cmp_Eq ? tarval_b_true : tarval_b_false;
413 * Here, we check only the right Confirm, as the left Confirms are
414 * checked later anyway.
417 if (left == r_bound && (r_pnc == pn_Cmp_Eq || r_pnc == pn_Cmp_Lg)) {
418 /* l == bound(r) AND pnc(r) == pnc */
420 return tarval_b_true;
422 /* l == bound(r) AND pnc(r) != pnc */
424 return tarval_b_false;
428 /* now, try interval magic */
429 get_interval(&r_iv, r_bound, r_pnc);
430 get_interval(&l_iv, l_bound, l_pnc);
432 tv = compare_iv(&l_iv, &r_iv, pnc);
433 if (tv != tarval_bad)
437 /* from Here, check only left Confirm */
439 /* check for == or != can sometime be made WITHOUT constant bounds */
440 if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) {
441 if (right == l_bound && (l_pnc == pn_Cmp_Eq || l_pnc == pn_Cmp_Lg)) {
442 /* r == bound(l) AND pnc(l) == pnc */
444 return tarval_b_true;
446 /* r == bound(l) AND pnc(l) != pnc */
448 return tarval_b_false;
452 /* now, only right == Const can help */
453 tv = value_of(right);
455 if (tv != tarval_bad) {
456 get_interval_from_tv(&r_iv, tv);
457 get_interval(&l_iv, l_bound, l_pnc);
459 return compare_iv(&l_iv, &r_iv, pnc);