nsz Git - libfirm/blob - ir/opt/opt_confirms.c

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/opt/opt_confirms.c
   4  * Purpose:     Optimizations regarding Confirm nodes
   5  * Author:      Michael Beck
   6  * Modified by:
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1998-2005 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include "config.h"
  15 #endif
  16
  17 #undef DEBUG_CONFIRM
  18
  19 #include "tv_t.h"
  20 #include "iropt_t.h"
  21 #include "iropt_dbg.h"
  22 #include "opt_confirms.h"
  23 #include "irprintf.h"
  24
  25 enum range_tags {
  26   MIN_INCLUDED = 0x00,  /**< [min, ... */
  27   MAX_INCLUDED = 0x00,  /**< ..., max] */
  28   MIN_EXCLUDED = 0x01,  /**< (min, ... */
  29   MAX_EXCLUDED = 0x02   /**< ..., max) */
  30 };
  31
  32 /**
  33  * An interval. We could use
  34  * intervals that ALWAYS include its borders, even for
  35  * floating point, as the precision is limited.
  36  * However, as our tarval module did not support
  37  * such kind of operation, we use border flags allowing
  38  * all intervals.
  39  */
  40 typedef struct _interval_t {
  41   tarval        *min;   /**< lowest border */
  42   tarval        *max;   /**< highest border */
  43   unsigned char flags;  /**< border flags */
  44 } interval_t;
  45
  46 #ifdef DEBUG_CONFIRM
  47
  48 #define compare_iv(l_iv, r_iv, pnc)             compare_iv_dbg(l_iv, r_iv, pnc)
  49
  50 /* forward */
  51 static tarval *compare_iv_dbg(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc);
  52
  53 /* triangle */
  54 #define DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, v) \
  55   ir_printf("In %e:\na %= %n && b %= %n  ==>  a %= b == %s\n", \
  56     get_irg_entity(current_ir_graph), \
  57     l_pnc, l_bound, r_pnc, r_bound, pnc, v);
  58
  59 /* right side */
  60 #define DBG_OUT_R(r_pnc, r_bound, left, pnc, right, v) \
  61   ir_printf("In %e:\na %= %n ==>  %n %= %n == %s\n", \
  62     get_irg_entity(current_ir_graph), \
  63     r_pnc, r_bound, left, pnc, right, v);
  64
  65 /* left side */
  66 #define DBG_OUT_L(l_pnc, l_bound, left, pnc, right, v) \
  67   ir_printf("In %e:\na %= %n ==>  %n %= %n == %s\n", \
  68     get_irg_entity(current_ir_graph), \
  69     l_pnc, l_bound, left, pnc, right, v);
  70
  71 #else
  72
  73 #define DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, v)
  74 #define DBG_OUT_R(r_pnc, r_bound, left, pnc, right, v)
  75 #define DBG_OUT_L(l_pnc, l_bound, left, pnc, right, v)
  76
  77 #endif /* DEBUG_CONFIRM */
  78
  79 /**
  80  * Check, if the value of a node is != 0.
  81  *
  82  * This is a often needed case, so we handle here Confirm
  83  * nodes too.
  84  */
  85 int value_not_zero(ir_node *n)
  86 {
  87 #define RET_ON(x)  if (x) return 1; break
  88
  89   tarval *tv;
  90   ir_mode *mode = get_irn_mode(n);
  91   pn_Cmp pnc;
  92
  93   while (get_irn_op(n) == op_Confirm) {
  94     /*
  95      * Note: A Confirm is never after a Const. So,
  96      * we simply can check the bound for beeing a Const
  97      * without the fear that is might be hidden by a further Confirm.
  98      */
  99     tv = value_of(get_Confirm_bound(n));
 100     if (tv == tarval_bad)
 101       return 0;
 102
 103     pnc  = tarval_cmp(tv, get_mode_null(mode));
 104
 105     /*
 106      * Beware: C might by a NaN. It is not clear, what we should do
 107      * than. Of course a NaN is != 0, but we might use this function
 108      * to remove up Exceptions, and NaN's might generate Exception.
 109      * So, we do NOT handle NaNs here for safety.
 110      *
 111      * Note that only the C != 0 case need additional checking.
 112      */
 113     switch (get_Confirm_cmp(n)) {
 114     case pn_Cmp_Eq: /* n == C /\ C != 0 ==> n != 0 */
 115       RET_ON(pnc != pn_Cmp_Eq && pnc != pn_Cmp_Uo);
 116     case pn_Cmp_Lg: /* n != C /\ C == 0 ==> n != 0 */
 117       RET_ON(pnc == pn_Cmp_Eq);
 118     case pn_Cmp_Lt: /* n <  C /\ C <= 0 ==> n != 0 */
 119       RET_ON(pnc == pn_Cmp_Lt || pnc == pn_Cmp_Eq);
 120     case pn_Cmp_Le: /* n <= C /\ C <  0 ==> n != 0 */
 121       RET_ON(pnc == pn_Cmp_Lt);
 122     case pn_Cmp_Ge: /* n >= C /\ C >  0 ==> n != 0 */
 123       RET_ON(pnc == pn_Cmp_Gt);
 124     case pn_Cmp_Gt: /* n >  C /\ C >= 0 ==> n != 0 */
 125       RET_ON(pnc == pn_Cmp_Gt || pnc == pn_Cmp_Eq);
 126     default:
 127       break;
 128     }
 129
 130     /* there might be several Confirms one after other that form an interval */
 131     n = get_Confirm_value(n);
 132   }
 133   tv = value_of(n);
 134
 135   if (tv == tarval_bad)
 136     return 0;
 137
 138   pnc = tarval_cmp(tv, get_mode_null(mode));
 139
 140   /* again, need check for NaN */
 141   return (pnc != pn_Cmp_Eq) && (pnc != pn_Cmp_Uo);
 142
 143 #undef RET_ON
 144 }
 145
 146 /*
 147  * Check, if the value of a node can be confirmed >= 0 or <= 0,
 148  * If the mode of the value did not honor signed zeros, else
 149  * check for >= 0 or < 0.
 150  */
 151 value_classify classify_value_sign(ir_node *n)
 152 {
 153   tarval *tv, *c;
 154   ir_mode *mode;
 155   pn_Cmp cmp, ncmp;
 156
 157   if (get_irn_op(n) != op_Confirm)
 158     return VALUE_UNKNOWN;
 159
 160   tv  = value_of(get_Confirm_bound(n));
 161   if (tv == tarval_bad)
 162     return VALUE_UNKNOWN;
 163
 164   mode = get_irn_mode(n);
 165
 166   /*
 167    * We can handle only >=, >, <, <= cases.
 168    * We could handle == too, but this will be optimized into
 169    * a constant either.
 170    *
 171    * Note that for integer modes we have a slightly better
 172    * optimization possibilities, so we handle this
 173    * different.
 174    */
 175   cmp = get_Confirm_cmp(n);
 176
 177   switch (cmp) {
 178   case pn_Cmp_Lt:
 179     /*
 180      * must be x < c <= 1 to be useful if integer mode and -0 = 0
 181      *         x < c <= 0 to be useful else
 182      */
 183   case pn_Cmp_Le:
 184     /*
 185      * must be x <= c < 1 to be useful if integer mode and -0 = 0
 186      *         x <= c < 0 to be useful else
 187      */
 188     c = mode_is_int(mode) && mode_honor_signed_zeros(mode) ?
 189       get_mode_one(mode) : get_mode_null(mode);
 190
 191     ncmp = tarval_cmp(tv, c);
 192     if (ncmp == pn_Cmp_Eq)
 193       ncmp = pn_Cmp_Le;
 194
 195     if (cmp != (ncmp ^ pn_Cmp_Eq))
 196       return VALUE_UNKNOWN;
 197
 198     /* yep, negative */
 199     return VALUE_NEGATIVE;
 200
 201   case pn_Cmp_Ge:
 202     /*
 203      * must be x >= c > -1 to be useful if integer mode
 204      *         x >= c >= 0 to be useful else
 205      */
 206   case pn_Cmp_Gt:
 207     /*
 208      * must be x > c >= -1 to be useful if integer mode
 209      *         x > c >= 0 to be useful else
 210      */
 211     if (mode_is_int(mode)) {
 212       c = get_mode_minus_one(mode);
 213
 214       ncmp = tarval_cmp(tv, c);
 215       if (ncmp == pn_Cmp_Eq)
 216         ncmp = pn_Cmp_Ge;
 217
 218       if (cmp != (ncmp ^ pn_Cmp_Eq))
 219         return VALUE_UNKNOWN;
 220     }
 221     else {
 222       c = get_mode_minus_one(mode);
 223
 224       ncmp = tarval_cmp(tv, c);
 225
 226       if (ncmp != pn_Cmp_Eq && ncmp != pn_Cmp_Gt)
 227         return VALUE_UNKNOWN;
 228     }
 229
 230     /* yep, positive */
 231     return VALUE_POSITIVE;
 232
 233   default:
 234     return VALUE_UNKNOWN;
 235   }
 236 }
 237
 238 /**
 239  * construct an interval from a value
 240  *
 241  * @return the filled interval or NULL if no interval
 242  *         can be created (happens only on floating point
 243  */
 244 static interval_t *get_interval_from_tv(interval_t *iv, tarval *tv)
 245 {
 246   ir_mode *mode = get_tarval_mode(tv);
 247
 248   if (tv == tarval_bad) {
 249     if (mode_is_float(mode)) {
 250       /* NaN could be included which we cannot handle */
 251       iv->min   = tarval_bad;
 252       iv->max   = tarval_bad;
 253       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 254       return NULL;
 255     }
 256     else {
 257       /* [-oo, +oo] */
 258       iv->min   = get_mode_min(mode);
 259       iv->max   = get_mode_max(mode);
 260       iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 261       return iv;
 262     }
 263   }
 264
 265   if (mode_is_float(mode)) {
 266     if (tv == get_mode_NAN(mode)) {
 267       /* arg, we cannot handle NaN's. */
 268       iv->min   = tarval_bad;
 269       iv->max   = tarval_bad;
 270       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 271       return NULL;
 272     }
 273   }
 274
 275   /* [tv, tv] */
 276   iv->min   = tv;
 277   iv->max   = tv;
 278   iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 279
 280   return iv;
 281 }
 282
 283 /**
 284  * construct an interval from a Confirm
 285  *
 286  * @param iv     an empty interval, will be filled
 287  * @param bound  the bound value
 288  * @param pnc    the Confirm compare relation
 289  *
 290  * @return the filled interval or NULL if no interval
 291  *         can be created (happens only on floating point
 292  */
 293 static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc)
 294 {
 295   ir_mode *mode = get_irn_mode(bound);
 296   tarval  *tv   = value_of(bound);
 297
 298   if (tv == tarval_bad) {
 299     /* There is nothing we could do here. For integer
 300      * modes we could return [-oo, +oo], but there is
 301      * nothing we could deduct from such an interval.
 302      * So, speed things up and return unknown.
 303      */
 304     iv->min   = tarval_bad;
 305     iv->max   = tarval_bad;
 306     iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 307     return NULL;
 308   }
 309
 310   if (mode_is_float(mode)) {
 311     if (tv == get_mode_NAN(mode)) {
 312       /* arg, we cannot handle NaN's. */
 313       iv->min   = tarval_bad;
 314       iv->max   = tarval_bad;
 315       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 316
 317       return NULL;
 318     }
 319   }
 320
 321   /* check which side is known */
 322   switch (pnc) {
 323   case pn_Cmp_Eq:
 324     /* [tv, tv] */
 325     iv->min   =
 326     iv->max   = tv;
 327     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 328     break;
 329
 330   case pn_Cmp_Le:
 331     /* [-oo, tv] */
 332     iv->min   = get_mode_min(mode);
 333     iv->max   = tv;
 334     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 335     break;
 336
 337   case pn_Cmp_Lt:
 338     /* [-oo, tv) */
 339     iv->min   = get_mode_min(mode);
 340     iv->max   = tv;
 341     iv->flags = MIN_INCLUDED | MAX_EXCLUDED;
 342     break;
 343
 344   case pn_Cmp_Gt:
 345     /* (tv, +oo] */
 346     iv->min   = tv;
 347     iv->max   = get_mode_max(mode);
 348     iv->flags = MIN_EXCLUDED | MAX_INCLUDED;
 349     break;
 350
 351   case pn_Cmp_Ge:
 352     /* [tv, +oo] */
 353     iv->min   = tv;
 354     iv->max   = get_mode_max(mode);
 355     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 356     break;
 357
 358   case pn_Cmp_Leg:
 359     /*
 360      * Ordered means, that at least neither
 361      * our bound nor our value ara NaN's
 362      */
 363     /* [-oo, +oo] */
 364     iv->min   = get_mode_min(mode);
 365     iv->max   = get_mode_max(mode);
 366     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 367     break;
 368
 369   default:
 370     /*
 371      * We do not handle UNORDERED, as a NaN
 372      * could be included in the interval.
 373      */
 374     iv->min   = tarval_bad;
 375     iv->max   = tarval_bad;
 376     iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 377     return NULL;
 378   }
 379
 380   if (iv->min != tarval_bad && iv->max != tarval_bad)
 381     return iv;
 382   return NULL;
 383 }
 384
 385 /**
 386  * Try to evaluate l_iv pnc r_iv.
 387  *
 388  * @param l_iv   the left interval
 389  * @param r_iv   the right interval
 390  * @param pnc    the compare relation
 391  *
 392  * @return
 393  *   tarval_b_true or tarval_b_false it it can be evaluated,
 394  *   tarval_bad else
 395  */
 396 static tarval *(compare_iv)(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
 397 {
 398   pn_Cmp res;
 399   unsigned flags;
 400   tarval *tv_true = tarval_b_true, *tv_false = tarval_b_false;
 401
 402   /* if one interval contains NaNs, we cannot evaluate anything */
 403   if (! l_iv || ! r_iv)
 404     return tarval_bad;
 405
 406   /* we can only check ordered relations */
 407   if (pnc & pn_Cmp_Uo) {
 408     tarval *t;
 409
 410     pnc      = get_negated_pnc(pnc, get_tarval_mode(l_iv->min));
 411     t        = tv_true;
 412     tv_true  = tv_false;
 413     tv_false = t;
 414   }
 415
 416   /* if we have > or >=, we do the inverse to save some cases */
 417   if (pnc == pn_Cmp_Ge || pnc == pn_Cmp_Gt) {
 418     const interval_t *t;
 419
 420     pnc  = get_inversed_pnc(pnc);
 421     t    = l_iv;
 422     l_iv = r_iv;
 423     r_iv = t;
 424   }
 425
 426   /* now, only the following cases remains */
 427   switch (pnc) {
 428   case pn_Cmp_Eq:
 429     /* two intervals can be compared for equality only if they are a single value */
 430     if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
 431       return tarval_cmp(l_iv->min, r_iv->min) == pn_Cmp_Eq ? tv_true : tv_false;
 432
 433     /* if both interval do not intersect, it is never equal */
 434     res = tarval_cmp(l_iv->max, r_iv->min);
 435
 436     /* b < c ==> [a,b] != [c,d] */
 437     if (res == pn_Cmp_Lt)
 438             return tv_false;
 439
 440     /* b <= c ==> [a,b) != [c,d]  AND [a,b] != (c,d] */
 441     if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED)
 442               && (res == pn_Cmp_Eq))
 443             return tv_false;
 444
 445     res = tarval_cmp(r_iv->max, l_iv->min);
 446
 447     /* d < a ==> [c,d] != [a,b] */
 448     if (res == pn_Cmp_Lt)
 449             return tv_false;
 450
 451     /* d <= a ==> [c,d) != [a,b]  AND [c,d] != (a,b] */
 452     if ((r_iv->flags & MAX_EXCLUDED || l_iv->flags & MIN_EXCLUDED)
 453             && (res == pn_Cmp_Eq))
 454             return tv_false;
 455     break;
 456
 457   case pn_Cmp_Lg:
 458     /* two intervals can be compared for not equality only if they are a single value */
 459     if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
 460       return tarval_cmp(l_iv->min, r_iv->min) != pn_Cmp_Eq ? tv_true : tv_false;
 461     break;
 462
 463   case pn_Cmp_Lt:
 464     res = tarval_cmp(l_iv->max, r_iv->min);
 465
 466     /* [a, b] < [c, d]  <==> b < c */
 467     if (res == pn_Cmp_Lt)
 468       return tv_true;
 469
 470     /* if one border is excluded, b <= c is enough */
 471     if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
 472         res == pn_Cmp_Eq)
 473       return tv_true;
 474
 475     /* [a, b] >= [c, d] <==> a > d */
 476     res = tarval_cmp(l_iv->min, r_iv->max);
 477     if (res == pn_Cmp_Gt)
 478       return tv_false;
 479
 480     /* if one border is excluded, a >= d is enough */
 481     if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
 482       res == pn_Cmp_Eq)
 483       return tv_false;
 484     break;
 485
 486   case pn_Cmp_Le:
 487     /* [a, b) <= [c, d] or [a, b] <= (c, d]  <==> b <= c */
 488     flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
 489     if (flags) {
 490       res = tarval_cmp(l_iv->max, r_iv->min);
 491
 492       if (res == pn_Cmp_Lt || res == pn_Cmp_Eq)
 493         return tv_true;
 494     }
 495
 496     res = tarval_cmp(l_iv->min, r_iv->max);
 497
 498     /* [a, b] > [c, d] <==> a > d */
 499     if (res == pn_Cmp_Gt)
 500       return tv_false;
 501
 502     /* if one border is excluded, a >= d is enough */
 503     if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
 504         res == pn_Cmp_Eq)
 505       return tv_false;
 506     break;
 507
 508   case pn_Cmp_Leg:
 509     /* Hmm. if both are intervals, we can find an order */
 510     return tv_true;
 511
 512   default:
 513     return tarval_bad;
 514   }
 515   return tarval_bad;
 516 }
 517
 518 /**
 519  * Returns non-zero, if a given relation is transitive.
 520  */
 521 static int is_transitive(pn_Cmp pnc) {
 522   return (pn_Cmp_False < pnc && pnc < pn_Cmp_Lg);
 523 }
 524
 525
 526 /**
 527  * Return the value of a Cmp if one or both predecessors
 528  * are Confirm nodes.
 529  *
 530  * @param cmp    the Cmp node
 531  * @param left   the left operand of the Cmp
 532  * @param right  the right operand of the Cmp
 533  * @param pnc    the compare relation
 534  */
 535 tarval *computed_value_Cmp_Confirm(ir_node *cmp, ir_node *left, ir_node *right, pn_Cmp pnc)
 536 {
 537   ir_node    *l_bound;
 538   pn_Cmp     l_pnc, res_pnc, neg_pnc;
 539   interval_t l_iv, r_iv;
 540   tarval     *tv;
 541   ir_mode    *mode;
 542
 543   if (get_irn_op(right) == op_Confirm) {
 544     ir_node *t;
 545
 546     /* we want the Confirm on the left side */
 547     t     = left;
 548     left  = right;
 549     right = t;
 550
 551     pnc = get_inversed_pnc(pnc);
 552   }
 553   else if (get_irn_op(left) != op_Confirm) {
 554     /* no Confirm on either one side, finish */
 555     return tarval_bad;
 556   }
 557
 558   /* ok, here at least left is a Confirm, right might be */
 559   l_bound = get_Confirm_bound(left);
 560   l_pnc   = get_Confirm_cmp(left);
 561
 562   if (get_irn_op(right) == op_Confirm) {
 563     /*
 564      * both sides are Confirm's. Check some rare cases first.
 565      */
 566     ir_node *r_bound = get_Confirm_bound(right);
 567     pn_Cmp  r_pnc = get_Confirm_cmp(right);
 568
 569     /*
 570      * some check can be made WITHOUT constant bounds
 571      */
 572     if (r_bound == l_bound) {
 573       if (is_transitive(l_pnc)) {
 574         pn_Cmp r_inc_pnc = get_inversed_pnc(r_pnc);
 575
 576         /*
 577          * triangle inequality:
 578          *
 579          * a CMP B && B CMP b => a CMP b, !(a ~CMP b)
 580          *
 581          * We handle correctly cases with some <=/>= here
 582          */
 583         if ((l_pnc & ~pn_Cmp_Eq) == (r_inc_pnc & ~pn_Cmp_Eq)) {
 584           res_pnc = (l_pnc & ~pn_Cmp_Eq) | (l_pnc & r_inc_pnc & pn_Cmp_Eq);
 585
 586           if ((pnc == res_pnc) || ((pnc & ~pn_Cmp_Eq) == res_pnc)) {
 587             DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, "true");
 588             DBG_EVAL_CONFIRM(cmp);
 589             return tarval_b_true;
 590           }
 591           else {
 592             pn_Cmp neg_pnc = get_negated_pnc(pnc, get_irn_mode(left));
 593
 594             if ((neg_pnc == res_pnc) || ((neg_pnc & ~pn_Cmp_Eq) == res_pnc)) {
 595               DBG_OUT_TR(l_pnc, l_bound, r_pnc, r_bound, pnc, "false");
 596               DBG_EVAL_CONFIRM(cmp);
 597               return tarval_b_false;
 598             }
 599           }
 600         }
 601       }
 602     }
 603
 604     /*
 605      * Here, we check only the right Confirm, as the left Confirms are
 606      * checked later anyway.
 607      */
 608
 609     if (left == r_bound) {
 610       /*
 611        * l == bound(r) AND pnc(r) == pnc:
 612        *
 613        * We know that a CMP b and check for that
 614        */
 615       if ((r_pnc == pnc) || (r_pnc == (pnc & ~pn_Cmp_Eq))) {
 616         DBG_OUT_R(r_pnc, r_bound, left, pnc, right, "true");
 617         DBG_EVAL_CONFIRM(cmp);
 618         return tarval_b_true;
 619       }
 620       /*
 621        * l == bound(r) AND pnc(r) != pnc:
 622        *
 623        * We know that a CMP b and check for a ~CMP b
 624        */
 625       else {
 626         mode    = get_irn_mode(left);
 627         neg_pnc = get_negated_pnc(pnc, mode);
 628
 629         if ((r_pnc == neg_pnc) || (r_pnc == (neg_pnc & ~pn_Cmp_Eq))) {
 630           DBG_OUT_R(r_pnc, r_bound, left, pnc, right, "false");
 631           DBG_EVAL_CONFIRM(cmp);
 632           return tarval_b_false;
 633         }
 634       }
 635     }
 636
 637     /* now, try interval magic */
 638     tv = compare_iv(
 639       get_interval(&l_iv, l_bound, l_pnc),
 640       get_interval(&r_iv, r_bound, r_pnc),
 641       pnc);
 642
 643     if (tv != tarval_bad) {
 644       DBG_EVAL_CONFIRM(cmp);
 645       return tv;
 646     }
 647   }
 648
 649   /* from Here, check only left Confirm */
 650
 651   /*
 652    * some checks can be made WITHOUT constant bounds
 653    */
 654   if (right == l_bound) {
 655     /*
 656      * r == bound(l) AND pnc(l) == pnc:
 657      *
 658      * We know that a CMP b and check for that
 659      */
 660     if ((l_pnc == pnc) || (l_pnc == (pnc & ~pn_Cmp_Eq))) {
 661       DBG_OUT_L(l_pnc, l_bound, left, pnc, right, "true");
 662       DBG_EVAL_CONFIRM(cmp);
 663       return tarval_b_true;
 664     }
 665     /*
 666      * r == bound(l) AND pnc(l) is Not(pnc):
 667      *
 668      * We know that a CMP b and check for a ~CMP b
 669      */
 670     else {
 671       mode = get_irn_mode(left);
 672       neg_pnc = get_negated_pnc(pnc, mode);
 673
 674       if ((l_pnc == neg_pnc) || (l_pnc == (neg_pnc & ~pn_Cmp_Eq))) {
 675         DBG_OUT_L(l_pnc, l_bound, left, pnc, right, "false");
 676         DBG_EVAL_CONFIRM(cmp);
 677         return tarval_b_false;
 678       }
 679     }
 680   }
 681
 682   /* now, only right == Const can help */
 683   tv = value_of(right);
 684
 685   if (tv != tarval_bad) {
 686     tv = compare_iv(
 687       get_interval(&l_iv, l_bound, l_pnc),
 688       get_interval_from_tv(&r_iv, tv),
 689       pnc);
 690   }
 691
 692   if (tv != tarval_bad)
 693     DBG_EVAL_CONFIRM(cmp);
 694
 695   return tv;
 696 }
 697
 698 #ifdef DEBUG_CONFIRM
 699 /**
 700  * For debugging. Prints an interval into a string.
 701  *
 702  * @param buf   address of a string buffer
 703  * @param len   length of the string buffer
 704  * @param iv    the interval
 705  */
 706 static int iv_snprintf(char *buf, size_t len, const interval_t *iv) {
 707   char smin[64], smax[64];
 708
 709   if (iv) {
 710     tarval_snprintf(smin, sizeof(smin), iv->min);
 711
 712     if (iv->min != iv->max || (iv->flags & (MIN_EXCLUDED|MAX_EXCLUDED))) {
 713       tarval_snprintf(smax, sizeof(smax), iv->max);
 714
 715       return snprintf(buf, len, "%c%s, %s%c",
 716               iv->flags & MIN_EXCLUDED ? '(' : '[',
 717               smin, smax,
 718               iv->flags & MAX_EXCLUDED ? ')' : ']'
 719       );
 720     }
 721     else
 722       return snprintf(buf, len, "%s", smin);
 723   }
 724   return snprintf(buf, len, "<UNKNOWN>");
 725 }
 726
 727 /**
 728  * For debugging. Prints an interval compare.
 729  *
 730  * @param l_iv  the left interval
 731  * @param r_iv  the right interval
 732  * @param pnc   the compare relation
 733  */
 734 static void print_iv_cmp(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
 735 {
 736   char sl[128], sr[128];
 737
 738   iv_snprintf(sl, sizeof(sl), l_iv);
 739   iv_snprintf(sr, sizeof(sr), r_iv);
 740
 741   ir_printf("%s %= %s", sl, pnc, sr);
 742 }
 743
 744 /**
 745  * For debugging. call *compare_iv() and prints inputs and result.
 746  *
 747  * @param l_iv  the left interval
 748  * @param r_iv  the right interval
 749  * @param pnc   the compare relation
 750  */
 751 static tarval *compare_iv_dbg(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
 752 {
 753   tarval *tv = (compare_iv)(l_iv, r_iv, pnc);
 754
 755   if (tv == tarval_bad)
 756     return tv;
 757
 758   ir_printf("In %e:\n", get_irg_entity(current_ir_graph));
 759   print_iv_cmp(l_iv, r_iv, pnc);
 760   ir_printf(" = %T\n", tv);
 761         return tv;
 762 }
 763
 764 #endif /* DEBUG_CONFIRM */