X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fopt_confirms.c;h=f005c273f14602088d899362cdc61dc9a2a35958;hb=f1a1a6092d9e4ebd9e22dd1c57d76ef8aeda74fc;hp=1416d0845de58a305f0e3255fa232b358bf730e2;hpb=98c8808ee1d34300860bb78185558e1731a99368;p=libfirm diff --git a/ir/opt/opt_confirms.c b/ir/opt/opt_confirms.c index 1416d0845..f005c273f 100644 --- a/ir/opt/opt_confirms.c +++ b/ir/opt/opt_confirms.c @@ -14,9 +14,13 @@ # include "config.h" #endif +#undef DEBUG_CONFIRM + #include "tv_t.h" #include "iropt_t.h" +#include "iropt_dbg.h" #include "opt_confirms.h" +#include "irprintf.h" enum range_tags { MIN_INCLUDED = 0x00, /**< [min, ... */ @@ -39,6 +43,39 @@ typedef struct _interval_t { unsigned char flags; /**< border flags */ } interval_t; +#ifdef DEBUG_CONFIRM + +#define compare_iv(l_iv, r_iv, pnc) compare_iv_dbg(l_iv, r_iv, pnc) + +/* forward */ +static tarval *compare_iv_dbg(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc); + +/* triangle */ +#define DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, v) \ + ir_printf("In %e:\na %= %n && b %= %n ==> a %= b == %s\n", \ + get_irg_entity(current_ir_graph), \ + l_pnc, l_bound, r_pnc, r_bound, pnc, v); + +/* right side */ +#define DBG_OUT_R(r_pnc, r_bound, left, pnc, right, v) \ + ir_printf("In %e:\na %= %n ==> %n %= %n == %s\n", \ + get_irg_entity(current_ir_graph), \ + r_pnc, r_bound, left, pnc, right, v); + +/* left side */ +#define DBG_OUT_L(l_pnc, l_bound, left, pnc, right, v) \ + ir_printf("In %e:\na %= %n ==> %n %= %n == %s\n", \ + get_irg_entity(current_ir_graph), \ + l_pnc, l_bound, left, pnc, right, v); + +#else + +#define DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, v) +#define DBG_OUT_R(r_pnc, r_bound, left, pnc, right, v) +#define DBG_OUT_L(l_pnc, l_bound, left, pnc, right, v) + +#endif + /** * Check, if the value of a node is != 0. * @@ -50,7 +87,7 @@ int value_not_zero(ir_node *n) #define RET_ON(x) if (x) return 1; break tarval *tv; - ir_mode *mode; + ir_mode *mode = get_irn_mode(n); pn_Cmp pnc; while (get_irn_op(n) == op_Confirm) { @@ -63,12 +100,19 @@ int value_not_zero(ir_node *n) if (tv == tarval_bad) return 0; - mode = get_tarval_mode(tv); pnc = tarval_cmp(tv, get_mode_null(mode)); + /* + * 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. + */ switch (get_Confirm_cmp(n)) { - case pn_Cmp_Eq: /* n == C /\ C != 0 ==> n != 0, should never happen, but simple */ - RET_ON(pnc != pn_Cmp_Eq); + case pn_Cmp_Eq: /* n == C /\ C != 0 ==> n != 0 */ + RET_ON(pnc != pn_Cmp_Eq && pnc != pn_Cmp_Uo); case pn_Cmp_Lg: /* n != C /\ C == 0 ==> n != 0 */ RET_ON(pnc == pn_Cmp_Eq); case pn_Cmp_Lt: /* n < C /\ C <= 0 ==> n != 0 */ @@ -81,14 +125,20 @@ int value_not_zero(ir_node *n) RET_ON(pnc == pn_Cmp_Gt || pnc == pn_Cmp_Eq); default: break; - } + } /* there might be several Confirms one after other that form an interval */ n = get_Confirm_value(n); } tv = value_of(n); - return (tv != tarval_bad) && (classify_tarval(tv) != TV_CLASSIFY_NULL); + if (tv == tarval_bad) + return 0; + + pnc = tarval_cmp(tv, get_mode_null(mode)); + + /* again, need check for NaN */ + return (pnc != pn_Cmp_Eq) && (pnc != pn_Cmp_Uo); #undef RET_ON } @@ -187,18 +237,39 @@ value_classify classify_value_sign(ir_node *n) /** * construct an interval from a value + * + * @return the filled interval or NULL if no interval + * can be created (happens only on floating point */ static interval_t *get_interval_from_tv(interval_t *iv, tarval *tv) { ir_mode *mode = get_tarval_mode(tv); if (tv == tarval_bad) { - /* [-oo, +oo] */ - iv->min = get_mode_min(mode); - iv->max = get_mode_max(mode); - iv->flags = MIN_INCLUDED | MAX_INCLUDED; + 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; + } + } - 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] */ @@ -211,6 +282,13 @@ static interval_t *get_interval_from_tv(interval_t *iv, tarval *tv) /** * construct an interval from a Confirm + * + * @param iv an empty interval, will be filled + * @param bound the bound value + * @param pnc the Confirm pnc relation + * + * @return the filled interval or NULL if no interval + * can be created (happens only on floating point */ static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc) { @@ -218,12 +296,26 @@ static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc) tarval *tv = value_of(bound); if (tv == tarval_bad) { - /* [-oo, +oo] */ - iv->min = get_mode_min(mode); - iv->max = get_mode_max(mode); - iv->flags = MIN_INCLUDED | MAX_INCLUDED; + /* 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; + } - 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; + } } /* check which side is known */ @@ -233,48 +325,61 @@ static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc) iv->min = iv->max = tv; iv->flags = MIN_INCLUDED | MAX_INCLUDED; - return iv; + break; case pn_Cmp_Le: /* [-oo, tv] */ iv->min = get_mode_min(mode); iv->max = tv; iv->flags = MIN_INCLUDED | MAX_INCLUDED; - return iv; + break; case pn_Cmp_Lt: /* [-oo, tv) */ iv->min = get_mode_min(mode); iv->max = tv; iv->flags = MIN_INCLUDED | MAX_EXCLUDED; - return iv; + break; case pn_Cmp_Gt: /* (tv, +oo] */ iv->min = tv; iv->max = get_mode_max(mode); iv->flags = MIN_EXCLUDED | MAX_INCLUDED; - return iv; + break; case pn_Cmp_Ge: /* [tv, +oo] */ iv->min = tv; iv->max = get_mode_max(mode); iv->flags = MIN_INCLUDED | MAX_INCLUDED; - return iv; + break; - default: + case pn_Cmp_Leg: /* - * We did not handle UNORDERED yet. It is not - * clear, if this could give any gain. + * 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; - return iv; + 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; } /** @@ -288,56 +393,99 @@ static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc) * tarval_b_true or tarval_b_false it it can be evaluated, * tarval_bad else */ -static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc) +static tarval *(compare_iv)(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc) { pn_Cmp res; unsigned flags; tarval *tv_true = tarval_b_true, *tv_false = tarval_b_false; - /* - * save some cases: we invert all cases with a > - * Note that this turn Lg into Eq also (which is desired). - */ - if (pnc & pn_Cmp_Gt) { - pnc = get_inversed_pnc(pnc); + /* if one interval contains NaNs, we cannot evaluate anything */ + if (! l_iv || ! r_iv) + return tarval_bad; + + /* we can only check ordered relations */ + if (pnc & pn_Cmp_Uo) { + tarval *t; - tv_true = tarval_b_false; - tv_false = tarval_b_true; + pnc = get_negated_pnc(pnc, get_tarval_mode(l_iv->min)); + t = tv_true; + tv_true = tv_false; + tv_false = t; } + /* if we have > or >=, we do the inverse to save some cases */ + if (pnc == pn_Cmp_Ge || pnc == pn_Cmp_Gt) { + const interval_t *t; + + pnc = get_inversed_pnc(pnc); + t = l_iv; + l_iv = r_iv; + r_iv = t; + } + + /* now, only the following cases remains */ switch (pnc) { case pn_Cmp_Eq: /* 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) - return l_iv->min == r_iv->min ? tv_true : tv_false; + return tarval_cmp(l_iv->min, r_iv->min) == pn_Cmp_Eq ? tv_true : tv_false; + + /* if both interval do not intersect, it is never equal */ + res = tarval_cmp(l_iv->max, r_iv->min); + + /* b < c ==> [a,b] != [c,d] */ + if (res == pn_Cmp_Lt) + 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) + && (res == pn_Cmp_Eq)) + return tv_false; + + res = tarval_cmp(r_iv->max, l_iv->min); + + /* d < a ==> [c,d] != [a,b] */ + if (res == pn_Cmp_Lt) + 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) + && (res == pn_Cmp_Eq)) + return tv_false; + break; + + case pn_Cmp_Lg: + /* 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) + return tarval_cmp(l_iv->min, r_iv->min) != pn_Cmp_Eq ? tv_true : tv_false; break; case pn_Cmp_Lt: res = tarval_cmp(l_iv->max, r_iv->min); - /* [a, b] < [c, d] */ + /* [a, b] < [c, d] <==> b < c */ if (res == pn_Cmp_Lt) return tv_true; - /* if one border is excluded, <= is ok */ + + /* if one border is excluded, b <= c is enough */ if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) && res == pn_Cmp_Eq) return tv_true; - /* [a, b) >= [c, d] or [a, b] >= (c, d] */ - flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED); - - if (flags) { - res = tarval_cmp(l_iv->max, r_iv->min); + /* [a, b] >= [c, d] <==> a > d */ + res = tarval_cmp(l_iv->min, r_iv->max); + if (res == pn_Cmp_Gt) + return tv_false; - if (res == pn_Cmp_Gt || res == pn_Cmp_Eq) - return tv_false; - } + /* if one border is excluded, a >= d is enough */ + if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) && + res == pn_Cmp_Eq) + return tv_false; break; case pn_Cmp_Le: - /* [a, b) <= [c, d] or [a, b] <= (c, d] */ + /* [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); @@ -345,23 +493,36 @@ static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp return tv_true; } - res = tarval_cmp(l_iv->max, r_iv->min); + res = tarval_cmp(l_iv->min, r_iv->max); - /* [a, b] > [c, d] */ + /* [a, b] > [c, d] <==> a > d */ if (res == pn_Cmp_Gt) return tv_false; - /* if one border is excluded, >= is ok */ - if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) && + + /* if one border is excluded, a >= d is enough */ + if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) && res == pn_Cmp_Eq) return tv_false; break; + case pn_Cmp_Leg: + /* Hmm. if both are intervals, we can find an order */ + return tv_true; + default: return tarval_bad; } return tarval_bad; } +/** + * Returns non-zero, if a given relation is transitive. + */ +static int is_transitive(pn_Cmp pnc) { + return (pn_Cmp_False < pnc && pnc < pn_Cmp_Lg); +} + + /** * Return the value of a Cmp if one or both predecessors * are Confirm nodes. @@ -369,12 +530,13 @@ static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp * @param left the left operand of the Cmp * @param right the right operand of the Cmp */ -tarval *computed_value_Cmp_Confirm(ir_node *left, ir_node *right, pn_Cmp pnc) +tarval *computed_value_Cmp_Confirm(ir_node *cmp, ir_node *left, ir_node *right, pn_Cmp pnc) { ir_node *l_bound; - pn_Cmp l_pnc; + pn_Cmp l_pnc, res_pnc, neg_pnc; interval_t l_iv, r_iv; tarval *tv; + ir_mode *mode; if (get_irn_op(right) == op_Confirm) { ir_node *t; @@ -402,50 +564,116 @@ tarval *computed_value_Cmp_Confirm(ir_node *left, ir_node *right, pn_Cmp pnc) ir_node *r_bound = get_Confirm_bound(right); pn_Cmp r_pnc = get_Confirm_cmp(right); - /* check for == or != can sometime be made WITHOUT constant bounds */ - if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) { - /* l == r if bound(l) == bound(r) AND pnc(l) == pnc(r) == '=' */ - if (r_bound == l_bound && r_pnc == l_pnc && r_pnc == pn_Cmp_Eq) { - return pnc == pn_Cmp_Eq ? tarval_b_true : tarval_b_false; + /* + * some check can be made WITHOUT constant bounds + */ + if (r_bound == l_bound) { + if (is_transitive(l_pnc)) { + pn_Cmp r_inc_pnc = get_inversed_pnc(r_pnc); + + /* + * triangle inequality: + * + * a CMP B && B CMP b => a CMP b, !(a ~CMP b) + * + * We handle correctly cases with some <=/>= here + */ + if ((l_pnc & ~pn_Cmp_Eq) == (r_inc_pnc & ~pn_Cmp_Eq)) { + res_pnc = (l_pnc & ~pn_Cmp_Eq) | (l_pnc & r_inc_pnc & pn_Cmp_Eq); + + if ((pnc == res_pnc) || ((pnc & ~pn_Cmp_Eq) == res_pnc)) { + DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, "true"); + DBG_EVAL_CONFIRM(cmp); + return tarval_b_true; + } + else { + pn_Cmp neg_pnc = get_negated_pnc(pnc, get_irn_mode(left)); + + if ((neg_pnc == res_pnc) || ((neg_pnc & ~pn_Cmp_Eq) == res_pnc)) { + DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, "false"); + 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) { /* - * Here, we check only the right Confirm, as the left Confirms are - * checked later anyway. + * l == bound(r) AND pnc(r) == pnc: + * + * We know that a CMP b and check for that */ + if ((r_pnc == pnc) || (r_pnc == (pnc & ~pn_Cmp_Eq))) { + DBG_OUT_R(r_pnc, r_bound, left, pnc, right, "true"); + DBG_EVAL_CONFIRM(cmp); + return tarval_b_true; + } + /* + * l == bound(r) AND pnc(r) != pnc: + * + * We know that a CMP b and check for a ~CMP b + */ + else { + mode = get_irn_mode(left); + neg_pnc = get_negated_pnc(pnc, mode); - if (left == r_bound && (r_pnc == pn_Cmp_Eq || r_pnc == pn_Cmp_Lg)) { - /* l == bound(r) AND pnc(r) == pnc */ - if (r_pnc == pnc) - return tarval_b_true; - - /* l == bound(r) AND pnc(r) != pnc */ - else + if ((r_pnc == neg_pnc) || (r_pnc == (neg_pnc & ~pn_Cmp_Eq))) { + DBG_OUT_R(r_pnc, r_bound, left, pnc, right, "false"); + DBG_EVAL_CONFIRM(cmp); return tarval_b_false; + } } } /* now, try interval magic */ - get_interval(&r_iv, r_bound, r_pnc); - get_interval(&l_iv, l_bound, l_pnc); + tv = compare_iv( + get_interval(&l_iv, l_bound, l_pnc), + get_interval(&r_iv, r_bound, r_pnc), + pnc); - tv = compare_iv(&l_iv, &r_iv, pnc); - if (tv != tarval_bad) + if (tv != tarval_bad) { + DBG_EVAL_CONFIRM(cmp); return tv; + } } /* from Here, check only left Confirm */ - /* check for == or != can sometime be made WITHOUT constant bounds */ - if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) { - if (right == l_bound && (l_pnc == pn_Cmp_Eq || l_pnc == pn_Cmp_Lg)) { - /* r == bound(l) AND pnc(l) == pnc */ - if (l_pnc == pnc) - return tarval_b_true; + /* + * some checks can be made WITHOUT constant bounds + */ + if (right == l_bound) { + /* + * r == bound(l) AND pnc(l) == pnc: + * + * We know that a CMP b and check for that + */ + if ((l_pnc == pnc) || (l_pnc == (pnc & ~pn_Cmp_Eq))) { + DBG_OUT_L(l_pnc, l_bound, left, pnc, right, "true"); + DBG_EVAL_CONFIRM(cmp); + return tarval_b_true; + } + /* + * r == bound(l) AND pnc(l) is Not(pnc): + * + * We know that a CMP b and check for a ~CMP b + */ + else { + mode = get_irn_mode(left); + neg_pnc = get_negated_pnc(pnc, mode); - /* r == bound(l) AND pnc(l) != pnc */ - else + if ((l_pnc == neg_pnc) || (l_pnc == (neg_pnc & ~pn_Cmp_Eq))) { + DBG_OUT_L(l_pnc, l_bound, left, pnc, right, "false"); + DBG_EVAL_CONFIRM(cmp); return tarval_b_false; + } } } @@ -453,11 +681,70 @@ tarval *computed_value_Cmp_Confirm(ir_node *left, ir_node *right, pn_Cmp pnc) tv = value_of(right); if (tv != tarval_bad) { - get_interval_from_tv(&r_iv, tv); - get_interval(&l_iv, l_bound, l_pnc); + tv = compare_iv( + get_interval(&l_iv, l_bound, l_pnc), + get_interval_from_tv(&r_iv, tv), + pnc); + } + + if (tv != tarval_bad) + DBG_EVAL_CONFIRM(cmp); + + return tv; +} + +/** + * For debugging. Prints an interval into a string. + */ +static int iv_snprintf(char *buf, size_t len, const interval_t *iv) { + char smin[64], smax[64]; + + if (iv) { + tarval_snprintf(smin, sizeof(smin), iv->min); - return compare_iv(&l_iv, &r_iv, pnc); + 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, ""); +} - return tarval_bad; +#ifdef DEBUG_CONFIRM +/** + * For debugging. Prints an interval compare + */ +static void print_iv_cmp(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc) +{ + char sl[128], sr[128]; + + iv_snprintf(sl, sizeof(sl), l_iv); + iv_snprintf(sr, sizeof(sr), r_iv); + + ir_printf("%s %= %s", sl, pnc, sr); } + +/** + * For debugging. call *compare_iv() and prints inputs and result + */ +static tarval *compare_iv_dbg(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc) +{ + tarval *tv = (compare_iv)(l_iv, r_iv, pnc); + + if (tv == tarval_bad) + return tv; + + ir_printf("In %e:\n", get_irg_entity(current_ir_graph)); + print_iv_cmp(l_iv, r_iv, pnc); + ir_printf(" = %T\n", tv); + return tv; +} + +#endif /* DEBUG_CONFIRM */