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