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 "opt_confirms.h"
  20
  21 enum range_tags {
  22   MIN_INCLUDED = 0x00,  /**< [min, ... */
  23   MAX_INCLUDED = 0x00,  /**< ..., max] */
  24   MIN_EXCLUDED = 0x01,  /**< (min, ... */
  25   MAX_EXCLUDED = 0x02   /**< ..., max) */
  26 };
  27
  28 /**
  29  * An interval. We could use
  30  * intervals that ALWAYS include its borders, even for
  31  * floating point, as the precision is limited.
  32  * However, as our tarval module did not support
  33  * such kind of operation, we use border flags allowing
  34  * all intervals.
  35  */
  36 typedef struct _interval_t {
  37   tarval        *min;   /**< lowest border */
  38   tarval        *max;   /**< highest border */
  39   unsigned char flags;  /**< border flags */
  40 } interval_t;
  41
  42 /**
  43  * Check, if the value of a node is != 0.
  44  *
  45  * This is a often needed case, so we handle here Confirm
  46  * nodes too.
  47  */
  48 int value_not_zero(ir_node *n)
  49 {
  50 #define RET_ON(x)  if (x) return 1; break
  51
  52   tarval *tv;
  53   ir_mode *mode;
  54   pn_Cmp pnc;
  55
  56   while (get_irn_op(n) == op_Confirm) {
  57     /*
  58      * Note: A Confirm is never after a Const. So,
  59      * we simply can check the bound for beeing a Const
  60      * without the fear that is might be hidden by a further Confirm.
  61      */
  62     tv = value_of(get_Confirm_bound(n));
  63     if (tv == tarval_bad)
  64       return 0;
  65
  66     mode = get_tarval_mode(tv);
  67     pnc  = tarval_cmp(tv, get_mode_null(mode));
  68
  69     switch (get_Confirm_cmp(n)) {
  70     case pn_Cmp_Eq: /* n == C /\ C != 0 ==> n != 0, should never happen, but simple */
  71       RET_ON(pnc != pn_Cmp_Eq);
  72     case pn_Cmp_Lg: /* n != C /\ C == 0 ==> n != 0 */
  73       RET_ON(pnc == pn_Cmp_Eq);
  74     case pn_Cmp_Lt: /* n <  C /\ C <= 0 ==> n != 0 */
  75       RET_ON(pnc == pn_Cmp_Lt || pnc == pn_Cmp_Eq);
  76     case pn_Cmp_Le: /* n <= C /\ C <  0 ==> n != 0 */
  77       RET_ON(pnc == pn_Cmp_Lt);
  78     case pn_Cmp_Ge: /* n >= C /\ C >  0 ==> n != 0 */
  79       RET_ON(pnc == pn_Cmp_Gt);
  80     case pn_Cmp_Gt: /* n >  C /\ C >= 0 ==> n != 0 */
  81       RET_ON(pnc == pn_Cmp_Gt || pnc == pn_Cmp_Eq);
  82     default:
  83       break;
  84         }
  85
  86     /* there might be several Confirms one after other that form an interval */
  87     n = get_Confirm_value(n);
  88   }
  89   tv = value_of(n);
  90
  91   return (tv != tarval_bad) && (classify_tarval(tv) != TV_CLASSIFY_NULL);
  92
  93 #undef RET_ON
  94 }
  95
  96 /*
  97  * Check, if the value of a node can be confirmed >= 0 or <= 0,
  98  * If the mode of the value did not honor signed zeros, else
  99  * check for >= 0 or < 0.
 100  */
 101 value_classify classify_value_sign(ir_node *n)
 102 {
 103   tarval *tv, *c;
 104   ir_mode *mode;
 105   pn_Cmp cmp, ncmp;
 106
 107   if (get_irn_op(n) != op_Confirm)
 108     return VALUE_UNKNOWN;
 109
 110   tv  = value_of(get_Confirm_bound(n));
 111   if (tv == tarval_bad)
 112     return VALUE_UNKNOWN;
 113
 114   mode = get_irn_mode(n);
 115
 116   /*
 117    * We can handle only >=, >, <, <= cases.
 118    * We could handle == too, but this will be optimized into
 119    * a constant either.
 120    *
 121    * Note that for integer modes we have a slightly better
 122    * optimization possibilities, so we handle this
 123    * different.
 124    */
 125   cmp = get_Confirm_cmp(n);
 126
 127   switch (cmp) {
 128   case pn_Cmp_Lt:
 129     /*
 130      * must be x < c <= 1 to be useful if integer mode and -0 = 0
 131      *         x < c <= 0 to be useful else
 132      */
 133   case pn_Cmp_Le:
 134     /*
 135      * must be x <= c < 1 to be useful if integer mode and -0 = 0
 136      *         x <= c < 0 to be useful else
 137      */
 138     c = mode_is_int(mode) && mode_honor_signed_zeros(mode) ?
 139       get_mode_one(mode) : get_mode_null(mode);
 140
 141     ncmp = tarval_cmp(tv, c);
 142     if (ncmp == pn_Cmp_Eq)
 143       ncmp = pn_Cmp_Le;
 144
 145     if (cmp != (ncmp ^ pn_Cmp_Eq))
 146       return VALUE_UNKNOWN;
 147
 148     /* yep, negative */
 149     return VALUE_NEGATIVE;
 150
 151   case pn_Cmp_Ge:
 152     /*
 153      * must be x >= c > -1 to be useful if integer mode
 154      *         x >= c >= 0 to be useful else
 155      */
 156   case pn_Cmp_Gt:
 157     /*
 158      * must be x > c >= -1 to be useful if integer mode
 159      *         x > c >= 0 to be useful else
 160      */
 161     if (mode_is_int(mode)) {
 162       c = get_mode_minus_one(mode);
 163
 164       ncmp = tarval_cmp(tv, c);
 165       if (ncmp == pn_Cmp_Eq)
 166         ncmp = pn_Cmp_Ge;
 167
 168       if (cmp != (ncmp ^ pn_Cmp_Eq))
 169         return VALUE_UNKNOWN;
 170     }
 171     else {
 172       c = get_mode_minus_one(mode);
 173
 174       ncmp = tarval_cmp(tv, c);
 175
 176       if (ncmp != pn_Cmp_Eq && ncmp != pn_Cmp_Gt)
 177         return VALUE_UNKNOWN;
 178     }
 179
 180     /* yep, positive */
 181     return VALUE_POSITIVE;
 182
 183   default:
 184     return VALUE_UNKNOWN;
 185   }
 186 }
 187
 188 /**
 189  * construct an interval from a value
 190  */
 191 static interval_t *get_interval_from_tv(interval_t *iv, tarval *tv)
 192 {
 193   ir_mode *mode = get_tarval_mode(tv);
 194
 195   if (tv == tarval_bad) {
 196     /* [-oo, +oo] */
 197     iv->min   = get_mode_min(mode);
 198     iv->max   = get_mode_max(mode);
 199     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 200
 201     return iv;
 202   }
 203
 204   /* [tv, tv] */
 205   iv->min   = tv;
 206   iv->max   = tv;
 207   iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 208
 209   return iv;
 210 }
 211
 212 /**
 213  * construct an interval from a Confirm
 214  */
 215 static interval_t *get_interval(interval_t *iv, ir_node *bound, pn_Cmp pnc)
 216 {
 217   ir_mode *mode = get_irn_mode(bound);
 218   tarval  *tv   = value_of(bound);
 219
 220   if (tv == tarval_bad) {
 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
 226     return iv;
 227   }
 228
 229   /* check which side is known */
 230   switch (pnc) {
 231   case pn_Cmp_Eq:
 232     /* [tv, tv] */
 233     iv->min   =
 234     iv->max   = tv;
 235     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 236     return iv;
 237
 238   case pn_Cmp_Le:
 239     /* [-oo, tv] */
 240     iv->min   = get_mode_min(mode);
 241     iv->max   = tv;
 242     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 243     return iv;
 244
 245   case pn_Cmp_Lt:
 246     /* [-oo, tv) */
 247     iv->min   = get_mode_min(mode);
 248     iv->max   = tv;
 249     iv->flags = MIN_INCLUDED | MAX_EXCLUDED;
 250     return iv;
 251
 252   case pn_Cmp_Gt:
 253     /* (tv, +oo] */
 254     iv->min   = tv;
 255     iv->max   = get_mode_max(mode);
 256     iv->flags = MIN_EXCLUDED | MAX_INCLUDED;
 257     return iv;
 258
 259   case pn_Cmp_Ge:
 260     /* [tv, +oo] */
 261     iv->min   = tv;
 262     iv->max   = get_mode_max(mode);
 263     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 264     return iv;
 265
 266   default:
 267     /*
 268      * We did not handle UNORDERED yet. It is not
 269      * clear, if this could give any gain.
 270      */
 271
 272     /* [-oo, +oo] */
 273     iv->min   = get_mode_min(mode);
 274     iv->max   = get_mode_max(mode);
 275     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 276     return iv;
 277   }
 278 }
 279
 280 /**
 281  * Try to evaluate l_iv pnc r_iv.
 282  *
 283  * @param l_iv   the left interval
 284  * @param r_iv   the right interval
 285  * @param pnc    the compare relation
 286  *
 287  * @return
 288  *   tarval_b_true or tarval_b_false it it can be evaluated,
 289  *   tarval_bad else
 290  */
 291 static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
 292 {
 293   pn_Cmp res;
 294   unsigned flags;
 295   tarval *tv_true = tarval_b_true, *tv_false = tarval_b_false;
 296
 297   /*
 298    * save some cases: we invert all cases with a >
 299    * Note that this turn Lg into Eq also (which is desired).
 300    */
 301   if (pnc & pn_Cmp_Gt) {
 302     pnc = get_inversed_pnc(pnc);
 303
 304     tv_true  = tarval_b_false;
 305     tv_false = tarval_b_true;
 306   }
 307
 308   switch (pnc) {
 309   case pn_Cmp_Eq:
 310     /* two intervals can be compared for equality only if they are a single value */
 311     if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
 312       return l_iv->min == r_iv->min ? tv_true : tv_false;
 313     break;
 314
 315   case pn_Cmp_Lt:
 316     res = tarval_cmp(l_iv->max, r_iv->min);
 317
 318     /* [a, b] < [c, d] */
 319     if (res == pn_Cmp_Lt)
 320       return tv_true;
 321     /* if one border is excluded, <= is ok */
 322     if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
 323         res == pn_Cmp_Eq)
 324       return tv_true;
 325
 326     /* [a, b) >= [c, d] or [a, b] >= (c, d] */
 327     flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
 328
 329     if (flags) {
 330       res = tarval_cmp(l_iv->max, r_iv->min);
 331
 332       if (res == pn_Cmp_Gt || res == pn_Cmp_Eq)
 333         return tv_false;
 334     }
 335     break;
 336
 337   case pn_Cmp_Le:
 338     /* [a, b) <= [c, d] or [a, b] <= (c, d] */
 339     flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
 340
 341     if (flags) {
 342       res = tarval_cmp(l_iv->max, r_iv->min);
 343
 344       if (res == pn_Cmp_Lt || res == pn_Cmp_Eq)
 345         return tv_true;
 346     }
 347
 348     res = tarval_cmp(l_iv->max, r_iv->min);
 349
 350     /* [a, b] > [c, d] */
 351     if (res == pn_Cmp_Gt)
 352       return tv_false;
 353     /* if one border is excluded, >= is ok */
 354     if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
 355         res == pn_Cmp_Eq)
 356       return tv_false;
 357     break;
 358
 359   default:
 360     return tarval_bad;
 361   }
 362   return tarval_bad;
 363 }
 364
 365 /**
 366  * Return the value of a Cmp if one or both predecessors
 367  * are Confirm nodes.
 368  *
 369  * @param left   the left operand of the Cmp
 370  * @param right  the right operand of the Cmp
 371  */
 372 tarval *computed_value_Cmp_Confirm(ir_node *left, ir_node *right, pn_Cmp pnc)
 373 {
 374   ir_node    *l_bound;
 375   pn_Cmp     l_pnc;
 376   interval_t l_iv, r_iv;
 377   tarval     *tv;
 378
 379   if (get_irn_op(right) == op_Confirm) {
 380     ir_node *t;
 381
 382     /* we want the Confirm on the left side */
 383     t     = left;
 384     left  = right;
 385     right = t;
 386
 387     pnc = get_inversed_pnc(pnc);
 388   }
 389   else if (get_irn_op(left) != op_Confirm) {
 390     /* no Confirm on either one side, finish */
 391     return tarval_bad;
 392   }
 393
 394   /* ok, here at least left is a Confirm, right might be */
 395   l_bound = get_Confirm_bound(left);
 396   l_pnc   = get_Confirm_cmp(left);
 397
 398   if (get_irn_op(right) == op_Confirm) {
 399     /*
 400      * both sides are Confirm's. Check some rare cases first.
 401      */
 402     ir_node *r_bound = get_Confirm_bound(right);
 403     pn_Cmp  r_pnc = get_Confirm_cmp(right);
 404
 405     /* check for == or != can sometime be made WITHOUT constant bounds */
 406     if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) {
 407       /* l == r if bound(l) == bound(r) AND pnc(l) == pnc(r) == '=' */
 408       if (r_bound == l_bound && r_pnc == l_pnc && r_pnc == pn_Cmp_Eq) {
 409         return pnc == pn_Cmp_Eq ? tarval_b_true : tarval_b_false;
 410       }
 411
 412       /*
 413        * Here, we check only the right Confirm, as the left Confirms are
 414        * checked later anyway.
 415        */
 416
 417       if (left == r_bound && (r_pnc == pn_Cmp_Eq || r_pnc == pn_Cmp_Lg)) {
 418         /* l == bound(r) AND pnc(r) == pnc */
 419         if (r_pnc == pnc)
 420           return tarval_b_true;
 421
 422         /* l == bound(r) AND pnc(r) != pnc */
 423         else
 424           return tarval_b_false;
 425       }
 426     }
 427
 428     /* now, try interval magic */
 429     get_interval(&r_iv, r_bound, r_pnc);
 430     get_interval(&l_iv, l_bound, l_pnc);
 431
 432     tv = compare_iv(&l_iv, &r_iv, pnc);
 433     if (tv != tarval_bad)
 434       return tv;
 435   }
 436
 437   /* from Here, check only left Confirm */
 438
 439   /* check for == or != can sometime be made WITHOUT constant bounds */
 440   if (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg) {
 441     if (right == l_bound && (l_pnc == pn_Cmp_Eq || l_pnc == pn_Cmp_Lg)) {
 442       /* r == bound(l) AND pnc(l) == pnc */
 443       if (l_pnc == pnc)
 444         return tarval_b_true;
 445
 446       /* r == bound(l) AND pnc(l) != pnc */
 447       else
 448         return tarval_b_false;
 449     }
 450   }
 451
 452   /* now, only right == Const can help */
 453   tv = value_of(right);
 454
 455   if (tv != tarval_bad) {
 456     get_interval_from_tv(&r_iv, tv);
 457     get_interval(&l_iv, l_bound, l_pnc);
 458
 459     return compare_iv(&l_iv, &r_iv, pnc);
 460   }
 461
 462   return tarval_bad;
 463 }