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

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