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