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