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