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 #include "tv_t.h"
  18 #include "iropt_t.h"
  19 #include "iropt_dbg.h"
  20 #include "opt_confirms.h"
  21
  22 enum range_tags {
  23   MIN_INCLUDED = 0x00,  /**< [min, ... */
  24   MAX_INCLUDED = 0x00,  /**< ..., max] */
  25   MIN_EXCLUDED = 0x01,  /**< (min, ... */
  26   MAX_EXCLUDED = 0x02   /**< ..., max) */
  27 };
  28
  29 /**
  30  * An interval. We could use
  31  * intervals that ALWAYS include its borders, even for
  32  * floating point, as the precision is limited.
  33  * However, as our tarval module did not support
  34  * such kind of operation, we use border flags allowing
  35  * all intervals.
  36  */
  37 typedef struct _interval_t {
  38   tarval        *min;   /**< lowest border */
  39   tarval        *max;   /**< highest border */
  40   unsigned char flags;  /**< border flags */
  41 } interval_t;
  42
  43 /**
  44  * Check, if the value of a node is != 0.
  45  *
  46  * This is a often needed case, so we handle here Confirm
  47  * nodes too.
  48  */
  49 int value_not_zero(ir_node *n)
  50 {
  51 #define RET_ON(x)  if (x) return 1; break
  52
  53   tarval *tv;
  54   ir_mode *mode = get_irn_mode(n);
  55   pn_Cmp pnc;
  56
  57   while (get_irn_op(n) == op_Confirm) {
  58     /*
  59      * Note: A Confirm is never after a Const. So,
  60      * we simply can check the bound for beeing a Const
  61      * without the fear that is might be hidden by a further Confirm.
  62      */
  63     tv = value_of(get_Confirm_bound(n));
  64     if (tv == tarval_bad)
  65       return 0;
  66
  67     pnc  = tarval_cmp(tv, get_mode_null(mode));
  68
  69     /*
  70      * Beware: C might by a NaN. It is not clear, what we should do
  71      * than. Of course a NaN is != 0, but we might use this function
  72      * to remove up Exceptions, and NaN's might generate Exception.
  73      * So, we do NOT handle NaNs here for safety.
  74      *
  75      * Note that only the C != 0 case need additional checking.
  76      */
  77     switch (get_Confirm_cmp(n)) {
  78     case pn_Cmp_Eq: /* n == C /\ C != 0 ==> n != 0 */
  79       RET_ON(pnc != pn_Cmp_Eq && pnc != pn_Cmp_Uo);
  80     case pn_Cmp_Lg: /* n != C /\ C == 0 ==> n != 0 */
  81       RET_ON(pnc == pn_Cmp_Eq);
  82     case pn_Cmp_Lt: /* n <  C /\ C <= 0 ==> n != 0 */
  83       RET_ON(pnc == pn_Cmp_Lt || pnc == pn_Cmp_Eq);
  84     case pn_Cmp_Le: /* n <= C /\ C <  0 ==> n != 0 */
  85       RET_ON(pnc == pn_Cmp_Lt);
  86     case pn_Cmp_Ge: /* n >= C /\ C >  0 ==> n != 0 */
  87       RET_ON(pnc == pn_Cmp_Gt);
  88     case pn_Cmp_Gt: /* n >  C /\ C >= 0 ==> n != 0 */
  89       RET_ON(pnc == pn_Cmp_Gt || pnc == pn_Cmp_Eq);
  90     default:
  91       break;
  92     }
  93
  94     /* there might be several Confirms one after other that form an interval */
  95     n = get_Confirm_value(n);
  96   }
  97   tv = value_of(n);
  98
  99   if (tv == tarval_bad)
 100     return 0;
 101
 102   pnc = tarval_cmp(tv, get_mode_null(mode));
 103
 104   /* again, need check for NaN */
 105   return (pnc != pn_Cmp_Eq) && (pnc != pn_Cmp_Uo);
 106
 107 #undef RET_ON
 108 }
 109
 110 /*
 111  * Check, if the value of a node can be confirmed >= 0 or <= 0,
 112  * If the mode of the value did not honor signed zeros, else
 113  * check for >= 0 or < 0.
 114  */
 115 value_classify classify_value_sign(ir_node *n)
 116 {
 117   tarval *tv, *c;
 118   ir_mode *mode;
 119   pn_Cmp cmp, ncmp;
 120
 121   if (get_irn_op(n) != op_Confirm)
 122     return VALUE_UNKNOWN;
 123
 124   tv  = value_of(get_Confirm_bound(n));
 125   if (tv == tarval_bad)
 126     return VALUE_UNKNOWN;
 127
 128   mode = get_irn_mode(n);
 129
 130   /*
 131    * We can handle only >=, >, <, <= cases.
 132    * We could handle == too, but this will be optimized into
 133    * a constant either.
 134    *
 135    * Note that for integer modes we have a slightly better
 136    * optimization possibilities, so we handle this
 137    * different.
 138    */
 139   cmp = get_Confirm_cmp(n);
 140
 141   switch (cmp) {
 142   case pn_Cmp_Lt:
 143     /*
 144      * must be x < c <= 1 to be useful if integer mode and -0 = 0
 145      *         x < c <= 0 to be useful else
 146      */
 147   case pn_Cmp_Le:
 148     /*
 149      * must be x <= c < 1 to be useful if integer mode and -0 = 0
 150      *         x <= c < 0 to be useful else
 151      */
 152     c = mode_is_int(mode) && mode_honor_signed_zeros(mode) ?
 153       get_mode_one(mode) : get_mode_null(mode);
 154
 155     ncmp = tarval_cmp(tv, c);
 156     if (ncmp == pn_Cmp_Eq)
 157       ncmp = pn_Cmp_Le;
 158
 159     if (cmp != (ncmp ^ pn_Cmp_Eq))
 160       return VALUE_UNKNOWN;
 161
 162     /* yep, negative */
 163     return VALUE_NEGATIVE;
 164
 165   case pn_Cmp_Ge:
 166     /*
 167      * must be x >= c > -1 to be useful if integer mode
 168      *         x >= c >= 0 to be useful else
 169      */
 170   case pn_Cmp_Gt:
 171     /*
 172      * must be x > c >= -1 to be useful if integer mode
 173      *         x > c >= 0 to be useful else
 174      */
 175     if (mode_is_int(mode)) {
 176       c = get_mode_minus_one(mode);
 177
 178       ncmp = tarval_cmp(tv, c);
 179       if (ncmp == pn_Cmp_Eq)
 180         ncmp = pn_Cmp_Ge;
 181
 182       if (cmp != (ncmp ^ pn_Cmp_Eq))
 183         return VALUE_UNKNOWN;
 184     }
 185     else {
 186       c = get_mode_minus_one(mode);
 187
 188       ncmp = tarval_cmp(tv, c);
 189
 190       if (ncmp != pn_Cmp_Eq && ncmp != pn_Cmp_Gt)
 191         return VALUE_UNKNOWN;
 192     }
 193
 194     /* yep, positive */
 195     return VALUE_POSITIVE;
 196
 197   default:
 198     return VALUE_UNKNOWN;
 199   }
 200 }
 201
 202 /**
 203  * construct an interval from a value
 204  *
 205  * @return the filled interval or NULL if no interval
 206  *         can be created (happens only on floating point
 207  */
 208 static interval_t *get_interval_from_tv(interval_t *iv, tarval *tv)
 209 {
 210   ir_mode *mode = get_tarval_mode(tv);
 211
 212   if (tv == tarval_bad) {
 213     if (mode_is_float(mode)) {
 214       /* NaN could be included which we cannot handle */
 215       iv->min   = tarval_bad;
 216       iv->max   = tarval_bad;
 217       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 218       return NULL;
 219     }
 220     else {
 221       /* [-oo, +oo] */
 222       iv->min   = get_mode_min(mode);
 223       iv->max   = get_mode_max(mode);
 224       iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 225       return iv;
 226     }
 227   }
 228
 229   if (mode_is_float(mode)) {
 230     if (tv == get_mode_NAN(mode)) {
 231       /* arg, we cannot handle NaN's. */
 232       iv->min   = tarval_bad;
 233       iv->max   = tarval_bad;
 234       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 235       return NULL;
 236     }
 237   }
 238
 239   /* [tv, tv] */
 240   iv->min   = tv;
 241   iv->max   = tv;
 242   iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 243
 244   return iv;
 245 }
 246
 247 /**
 248  * construct an interval from a Confirm
 249  *
 250  * @param iv     an empty interval, will be filled
 251  * @param bound  the bound value
 252  * @param pnc    the Confirm pnc relation
 253  *
 254  * @return the filled interval or NULL if no interval
 255  *         can be created (happens only on floating point
 256  */
 257 static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc)
 258 {
 259   ir_mode *mode = get_irn_mode(bound);
 260   tarval  *tv   = value_of(bound);
 261
 262   if (tv == tarval_bad) {
 263     /* There is nothing we could do here. For integer
 264      * modes we could return [-oo, +oo], but there is
 265      * nothing we could deduct from such an interval.
 266      * So, speed things up and return unknown.
 267      */
 268     iv->min   = tarval_bad;
 269     iv->max   = tarval_bad;
 270     iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 271     return NULL;
 272   }
 273
 274   if (mode_is_float(mode)) {
 275     if (tv == get_mode_NAN(mode)) {
 276       /* arg, we cannot handle NaN's. */
 277       iv->min   = tarval_bad;
 278       iv->max   = tarval_bad;
 279       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 280
 281       return NULL;
 282     }
 283   }
 284
 285   /* check which side is known */
 286   switch (pnc) {
 287   case pn_Cmp_Eq:
 288     /* [tv, tv] */
 289     iv->min   =
 290     iv->max   = tv;
 291     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 292     break;
 293
 294   case pn_Cmp_Le:
 295     /* [-oo, tv] */
 296     iv->min   = get_mode_min(mode);
 297     iv->max   = tv;
 298     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 299     break;
 300
 301   case pn_Cmp_Lt:
 302     /* [-oo, tv) */
 303     iv->min   = get_mode_min(mode);
 304     iv->max   = tv;
 305     iv->flags = MIN_INCLUDED | MAX_EXCLUDED;
 306     break;
 307
 308   case pn_Cmp_Gt:
 309     /* (tv, +oo] */
 310     iv->min   = tv;
 311     iv->max   = get_mode_max(mode);
 312     iv->flags = MIN_EXCLUDED | MAX_INCLUDED;
 313     break;
 314
 315   case pn_Cmp_Ge:
 316     /* [tv, +oo] */
 317     iv->min   = tv;
 318     iv->max   = get_mode_max(mode);
 319     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 320     break;
 321
 322   case pn_Cmp_Leg:
 323     /*
 324      * Ordered means, that at least neither
 325      * our bound nor our value ara NaN's
 326      */
 327     /* [-oo, +oo] */
 328     iv->min   = get_mode_min(mode);
 329     iv->max   = get_mode_max(mode);
 330     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 331     break;
 332
 333   default:
 334     /*
 335      * We do not handle UNORDERED, as a NaN
 336      * could be included in the interval.
 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 (iv->min != tarval_bad && iv->max != tarval_bad)
 345     return iv;
 346   return NULL;
 347 }
 348
 349 /**
 350  * Try to evaluate l_iv pnc r_iv.
 351  *
 352  * @param l_iv   the left interval
 353  * @param r_iv   the right interval
 354  * @param pnc    the compare relation
 355  *
 356  * @return
 357  *   tarval_b_true or tarval_b_false it it can be evaluated,
 358  *   tarval_bad else
 359  */
 360 static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
 361 {
 362   pn_Cmp res;
 363   unsigned flags;
 364   tarval *tv_true = tarval_b_true, *tv_false = tarval_b_false;
 365
 366   /* if one interval contains NaNs, we cannot evaluate anything */
 367   if (! l_iv || ! r_iv)
 368     return tarval_bad;
 369
 370   /* we can only check ordered relations */
 371   if (pnc & pn_Cmp_Uo) {
 372     tarval *t;
 373
 374     pnc      = get_negated_pnc(pnc, get_tarval_mode(l_iv->min));
 375     t        = tv_true;
 376     tv_true  = tv_false;
 377     tv_false = t;
 378   }
 379
 380   /* if we have > or >=, we do the inverse to save some cases */
 381   if (pnc == pn_Cmp_Ge || pnc == pn_Cmp_Gt) {
 382     const interval_t *t;
 383
 384     pnc  = get_inversed_pnc(pnc);
 385     t    = l_iv;
 386     l_iv = r_iv;
 387     r_iv = t;
 388   }
 389
 390   /* now, only the following cases remains */
 391   switch (pnc) {
 392   case pn_Cmp_Eq:
 393     /* two intervals can be compared for equality only if they are a single value */
 394     if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
 395       return tarval_cmp(l_iv->min, r_iv->min) == pn_Cmp_Eq ? tv_true : tv_false;
 396     break;
 397
 398   case pn_Cmp_Lg:
 399     /* two intervals can be compared for not equality only if they are a single value */
 400     if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
 401       return tarval_cmp(l_iv->min, r_iv->min) != pn_Cmp_Eq ? tv_true : tv_false;
 402     break;
 403
 404   case pn_Cmp_Lt:
 405     res = tarval_cmp(l_iv->max, r_iv->min);
 406
 407     /* [a, b] < [c, d]  <==> b < c */
 408     if (res == pn_Cmp_Lt)
 409       return tv_true;
 410
 411     /* if one border is excluded, b <= c is enough */
 412     if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
 413         res == pn_Cmp_Eq)
 414       return tv_true;
 415
 416     /* [a, b] >= [c, d] <==> a > d */
 417     res = tarval_cmp(l_iv->min, r_iv->max);
 418     if (res == pn_Cmp_Gt)
 419       return tv_false;
 420
 421     /* if one border is excluded, a >= d is enough */
 422     if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
 423       res == pn_Cmp_Eq)
 424       return tv_false;
 425     break;
 426
 427   case pn_Cmp_Le:
 428     /* [a, b) <= [c, d] or [a, b] <= (c, d]  <==> b <= c */
 429     flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
 430     if (flags) {
 431       res = tarval_cmp(l_iv->max, r_iv->min);
 432
 433       if (res == pn_Cmp_Lt || res == pn_Cmp_Eq)
 434         return tv_true;
 435     }
 436
 437     res = tarval_cmp(l_iv->min, r_iv->max);
 438
 439     /* [a, b] > [c, d] <==> a > d */
 440     if (res == pn_Cmp_Gt)
 441       return tv_false;
 442
 443     /* if one border is excluded, a >= d is enough */
 444     if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
 445         res == pn_Cmp_Eq)
 446       return tv_false;
 447     break;
 448
 449   case pn_Cmp_Leg:
 450     /* Hmm. if both are intervals, we can find an order */
 451     return tv_true;
 452
 453   default:
 454     return tarval_bad;
 455   }
 456   return tarval_bad;
 457 }
 458
 459 /**
 460  * Return the value of a Cmp if one or both predecessors
 461  * are Confirm nodes.
 462  *
 463  * @param left   the left operand of the Cmp
 464  * @param right  the right operand of the Cmp
 465  */
 466 tarval *computed_value_Cmp_Confirm(ir_node *cmp, ir_node *left, ir_node *right, pn_Cmp pnc)
 467 {
 468   ir_node    *l_bound;
 469   pn_Cmp     l_pnc;
 470   interval_t l_iv, r_iv;
 471   tarval     *tv;
 472
 473   if (get_irn_op(right) == op_Confirm) {
 474     ir_node *t;
 475
 476     /* we want the Confirm on the left side */
 477     t     = left;
 478     left  = right;
 479     right = t;
 480
 481     pnc = get_inversed_pnc(pnc);
 482   }
 483   else if (get_irn_op(left) != op_Confirm) {
 484     /* no Confirm on either one side, finish */
 485     return tarval_bad;
 486   }
 487
 488   /* ok, here at least left is a Confirm, right might be */
 489   l_bound = get_Confirm_bound(left);
 490   l_pnc   = get_Confirm_cmp(left);
 491
 492   if (get_irn_op(right) == op_Confirm) {
 493     /*
 494      * both sides are Confirm's. Check some rare cases first.
 495      */
 496     ir_node *r_bound = get_Confirm_bound(right);
 497     pn_Cmp  r_pnc = get_Confirm_cmp(right);
 498
 499     /*
 500      * check for == or != can sometime be made WITHOUT constant bounds
 501      * Beware of NaN's.
 502      */
 503     if (! mode_is_float(get_irn_mode(left)) &&
 504         (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg)) {
 505       /* l == r if bound(l) == bound(r) AND pnc(l) == pnc(r) == '=' */
 506       if (r_bound == l_bound && r_pnc == l_pnc && r_pnc == pn_Cmp_Eq) {
 507         DBG_EVAL_CONFIRM(cmp);
 508         return pnc == pn_Cmp_Eq ? tarval_b_true : tarval_b_false;
 509       }
 510
 511       /*
 512        * Here, we check only the right Confirm, as the left Confirms are
 513        * checked later anyway.
 514        */
 515
 516       if (left == r_bound && (r_pnc == pn_Cmp_Eq || r_pnc == pn_Cmp_Lg)) {
 517         /* l == bound(r) AND pnc(r) == pnc */
 518         if (r_pnc == pnc) {
 519           DBG_EVAL_CONFIRM(cmp);
 520           return tarval_b_true;
 521         }
 522         /* l == bound(r) AND pnc(r) != pnc */
 523         else {
 524           DBG_EVAL_CONFIRM(cmp);
 525           return tarval_b_false;
 526         }
 527       }
 528     }
 529
 530     /* now, try interval magic */
 531     tv = compare_iv(
 532       get_interval(&l_iv, l_bound, l_pnc),
 533       get_interval(&r_iv, r_bound, r_pnc),
 534       pnc);
 535
 536     if (tv != tarval_bad) {
 537       DBG_EVAL_CONFIRM(cmp);
 538       return tv;
 539     }
 540   }
 541
 542   /* from Here, check only left Confirm */
 543
 544   /*
 545    * checks for == or != can sometime be made WITHOUT constant bounds
 546    * Beware of NaN's.
 547    */
 548   if (! mode_is_float(get_irn_mode(left)) &&
 549     (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg)) {
 550     if (right == l_bound && (l_pnc == pn_Cmp_Eq || l_pnc == pn_Cmp_Lg)) {
 551       /* r == bound(l) AND pnc(l) == pnc */
 552       if (l_pnc == pnc) {
 553         DBG_EVAL_CONFIRM(cmp);
 554         return tarval_b_true;
 555       }
 556       /* r == bound(l) AND pnc(l) != pnc */
 557       else {
 558         DBG_EVAL_CONFIRM(cmp);
 559         return tarval_b_false;
 560       }
 561     }
 562   }
 563
 564   /* now, only right == Const can help */
 565   tv = value_of(right);
 566
 567   if (tv != tarval_bad) {
 568     tv = compare_iv(
 569       get_interval(&l_iv, l_bound, l_pnc),
 570       get_interval_from_tv(&r_iv, tv),
 571       pnc);
 572   }
 573
 574   if (tv != tarval_bad)
 575     DBG_EVAL_CONFIRM(cmp);
 576
 577   return tv;
 578 }
 579
 580 /** For debugging. Prints an interval */
 581 static void print_iv(const interval_t *iv) {
 582   char smin[64], smax[64];
 583
 584   tarval_snprintf(smin, sizeof(smin), iv->min);
 585   tarval_snprintf(smax, sizeof(smax), iv->max);
 586
 587   printf("%c%s, %s%c\n",
 588     iv->flags & MIN_EXCLUDED ? '(' : '[',
 589     smin, smax,
 590     iv->flags & MAX_EXCLUDED ? ')' : ']'
 591   );
 592 }