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     if (mode_is_float(mode)) {
 264       /* NaN could be included which we cannot handle */
 265       iv->min   = tarval_bad;
 266       iv->max   = tarval_bad;
 267       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 268       return NULL;
 269     }
 270     else {
 271       /* [-oo, +oo] */
 272       iv->min   = get_mode_min(mode);
 273       iv->max   = get_mode_max(mode);
 274       iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 275       return iv;
 276     }
 277   }
 278
 279   if (mode_is_float(mode)) {
 280     if (tv == get_mode_NAN(mode)) {
 281       /* arg, we cannot handle NaN's. */
 282       iv->min   = tarval_bad;
 283       iv->max   = tarval_bad;
 284       iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 285
 286       return NULL;
 287     }
 288   }
 289
 290   /* check which side is known */
 291   switch (pnc) {
 292   case pn_Cmp_Eq:
 293     /* [tv, tv] */
 294     iv->min   =
 295     iv->max   = tv;
 296     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 297     return iv;
 298
 299   case pn_Cmp_Le:
 300     /* [-oo, tv] */
 301     iv->min   = get_mode_min(mode);
 302     iv->max   = tv;
 303     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 304     return iv;
 305
 306   case pn_Cmp_Lt:
 307     /* [-oo, tv) */
 308     iv->min   = get_mode_min(mode);
 309     iv->max   = tv;
 310     iv->flags = MIN_INCLUDED | MAX_EXCLUDED;
 311     return iv;
 312
 313   case pn_Cmp_Gt:
 314     /* (tv, +oo] */
 315     iv->min   = tv;
 316     iv->max   = get_mode_max(mode);
 317     iv->flags = MIN_EXCLUDED | MAX_INCLUDED;
 318     return iv;
 319
 320   case pn_Cmp_Ge:
 321     /* [tv, +oo] */
 322     iv->min   = tv;
 323     iv->max   = get_mode_max(mode);
 324     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 325     return iv;
 326
 327   case pn_Cmp_Leg:
 328     /*
 329      * Ordered means, that at least neither
 330      * our bound nor our value ara NaN's
 331      */
 332     /* [-oo, +oo] */
 333     iv->min   = get_mode_min(mode);
 334     iv->max   = get_mode_max(mode);
 335     iv->flags = MIN_INCLUDED | MAX_INCLUDED;
 336     return iv;
 337
 338   default:
 339     /*
 340      * We do not handle UNORDERED, as a NaN
 341      * could be included in the interval.
 342      */
 343     iv->min   = tarval_bad;
 344     iv->max   = tarval_bad;
 345     iv->flags = MIN_EXCLUDED | MAX_EXCLUDED;
 346     return NULL;
 347   }
 348 }
 349
 350 /**
 351  * Try to evaluate l_iv pnc r_iv.
 352  *
 353  * @param l_iv   the left interval
 354  * @param r_iv   the right interval
 355  * @param pnc    the compare relation
 356  *
 357  * @return
 358  *   tarval_b_true or tarval_b_false it it can be evaluated,
 359  *   tarval_bad else
 360  */
 361 static tarval *compare_iv(const interval_t *l_iv, const interval_t *r_iv, pn_Cmp pnc)
 362 {
 363   pn_Cmp res;
 364   unsigned flags;
 365   tarval *tv_true = tarval_b_true, *tv_false = tarval_b_false;
 366
 367   /* if one interval contains NaNs, we cannot evaluate anything */
 368   if (! l_iv || ! r_iv)
 369     return tarval_bad;
 370
 371   /* we can only check ordered relations */
 372   if (pnc & pn_Cmp_Uo) {
 373     tarval *t;
 374
 375     pnc      = get_negated_pnc(pnc);
 376     t        = tv_true;
 377     tv_true  = tv_false;
 378     tv_false = t;
 379   }
 380
 381   /* if we have > or >=, we do the inverse to save some cases */
 382   if (pnc == pn_Cmp_Ge || pnc == pn_Cmp_Gt) {
 383     const interval_t *t;
 384
 385     pnc  = get_inversed_pnc(pnc);
 386     t    = l_iv;
 387     l_iv = r_iv;
 388     r_iv = t;
 389   }
 390
 391   /* now, only the following cases remains */
 392   switch (pnc) {
 393   case pn_Cmp_Eq:
 394     /* two intervals can be compared for equality only if they are a single value */
 395     if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
 396       return tarval_cmp(l_iv->min, r_iv->min) == pn_Cmp_Eq ? tv_true : tv_false;
 397     break;
 398
 399   case pn_Cmp_Lg:
 400     /* two intervals can be compared for not equality only if they are a single value */
 401     if (l_iv->min == l_iv->max && r_iv->min == r_iv->max)
 402       return tarval_cmp(l_iv->min, r_iv->min) != pn_Cmp_Eq ? tv_true : tv_false;
 403     break;
 404
 405   case pn_Cmp_Lt:
 406     res = tarval_cmp(l_iv->max, r_iv->min);
 407
 408     /* [a, b] < [c, d]  <==> b < c */
 409     if (res == pn_Cmp_Lt)
 410       return tv_true;
 411
 412     /* if one border is excluded, b <= c is enough */
 413     if ((l_iv->flags & MAX_EXCLUDED || r_iv->flags & MIN_EXCLUDED) &&
 414         res == pn_Cmp_Eq)
 415       return tv_true;
 416
 417     /* [a, b] >= [c, d] <==> a > d */
 418     res = tarval_cmp(l_iv->min, r_iv->max);
 419     if (res == pn_Cmp_Gt)
 420       return tv_false;
 421
 422     /* if one border is excluded, a >= d is enough */
 423     if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
 424       res == pn_Cmp_Eq)
 425       return tv_false;
 426     break;
 427
 428   case pn_Cmp_Le:
 429     /* [a, b) <= [c, d] or [a, b] <= (c, d]  <==> b <= c */
 430     flags = (l_iv->flags & MAX_EXCLUDED) | (r_iv->flags & MIN_EXCLUDED);
 431     if (flags) {
 432       res = tarval_cmp(l_iv->max, r_iv->min);
 433
 434       if (res == pn_Cmp_Lt || res == pn_Cmp_Eq)
 435         return tv_true;
 436     }
 437
 438     res = tarval_cmp(l_iv->min, r_iv->max);
 439
 440     /* [a, b] > [c, d] <==> a > d */
 441     if (res == pn_Cmp_Gt)
 442       return tv_false;
 443
 444     /* if one border is excluded, a >= d is enough */
 445     if ((l_iv->flags & MIN_EXCLUDED || r_iv->flags & MAX_EXCLUDED) &&
 446         res == pn_Cmp_Eq)
 447       return tv_false;
 448     break;
 449
 450   case pn_Cmp_Leg:
 451     /* Hmm. if both are intervals, we can find an order */
 452     return tv_true;
 453
 454   default:
 455     return tarval_bad;
 456   }
 457   return tarval_bad;
 458 }
 459
 460 /**
 461  * Return the value of a Cmp if one or both predecessors
 462  * are Confirm nodes.
 463  *
 464  * @param left   the left operand of the Cmp
 465  * @param right  the right operand of the Cmp
 466  */
 467 tarval *computed_value_Cmp_Confirm(ir_node *cmp, ir_node *left, ir_node *right, pn_Cmp pnc)
 468 {
 469   ir_node    *l_bound;
 470   pn_Cmp     l_pnc;
 471   interval_t l_iv, r_iv;
 472   tarval     *tv;
 473
 474   if (get_irn_op(right) == op_Confirm) {
 475     ir_node *t;
 476
 477     /* we want the Confirm on the left side */
 478     t     = left;
 479     left  = right;
 480     right = t;
 481
 482     pnc = get_inversed_pnc(pnc);
 483   }
 484   else if (get_irn_op(left) != op_Confirm) {
 485     /* no Confirm on either one side, finish */
 486     return tarval_bad;
 487   }
 488
 489   /* ok, here at least left is a Confirm, right might be */
 490   l_bound = get_Confirm_bound(left);
 491   l_pnc   = get_Confirm_cmp(left);
 492
 493   if (get_irn_op(right) == op_Confirm) {
 494     /*
 495      * both sides are Confirm's. Check some rare cases first.
 496      */
 497     ir_node *r_bound = get_Confirm_bound(right);
 498     pn_Cmp  r_pnc = get_Confirm_cmp(right);
 499
 500     /*
 501      * check for == or != can sometime be made WITHOUT constant bounds
 502      * Beware of NaN's.
 503      */
 504     if (! mode_is_float(get_irn_mode(left)) &&
 505         (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg)) {
 506       /* l == r if bound(l) == bound(r) AND pnc(l) == pnc(r) == '=' */
 507       if (r_bound == l_bound && r_pnc == l_pnc && r_pnc == pn_Cmp_Eq) {
 508         DBG_EVAL_CONFIRM(cmp);
 509         return pnc == pn_Cmp_Eq ? tarval_b_true : tarval_b_false;
 510       }
 511
 512       /*
 513        * Here, we check only the right Confirm, as the left Confirms are
 514        * checked later anyway.
 515        */
 516
 517       if (left == r_bound && (r_pnc == pn_Cmp_Eq || r_pnc == pn_Cmp_Lg)) {
 518         /* l == bound(r) AND pnc(r) == pnc */
 519         if (r_pnc == pnc) {
 520           DBG_EVAL_CONFIRM(cmp);
 521           return tarval_b_true;
 522         }
 523         /* l == bound(r) AND pnc(r) != pnc */
 524         else {
 525           DBG_EVAL_CONFIRM(cmp);
 526           return tarval_b_false;
 527         }
 528       }
 529     }
 530
 531     /* now, try interval magic */
 532     tv = compare_iv(
 533       get_interval(&l_iv, l_bound, l_pnc),
 534       get_interval(&r_iv, r_bound, r_pnc),
 535       pnc);
 536
 537     if (tv != tarval_bad) {
 538       DBG_EVAL_CONFIRM(cmp);
 539       return tv;
 540     }
 541   }
 542
 543   /* from Here, check only left Confirm */
 544
 545   /*
 546    * checks for == or != can sometime be made WITHOUT constant bounds
 547    * Beware of NaN's.
 548    */
 549   if (! mode_is_float(get_irn_mode(left)) &&
 550     (pnc == pn_Cmp_Eq || pnc == pn_Cmp_Lg)) {
 551     if (right == l_bound && (l_pnc == pn_Cmp_Eq || l_pnc == pn_Cmp_Lg)) {
 552       /* r == bound(l) AND pnc(l) == pnc */
 553       if (l_pnc == pnc) {
 554         DBG_EVAL_CONFIRM(cmp);
 555         return tarval_b_true;
 556       }
 557       /* r == bound(l) AND pnc(l) != pnc */
 558       else {
 559         DBG_EVAL_CONFIRM(cmp);
 560         return tarval_b_false;
 561       }
 562     }
 563   }
 564
 565   /* now, only right == Const can help */
 566   tv = value_of(right);
 567
 568   if (tv != tarval_bad) {
 569     tv = compare_iv(
 570       get_interval(&l_iv, l_bound, l_pnc),
 571       get_interval_from_tv(&r_iv, tv),
 572       pnc);
 573   }
 574
 575   if (tv != tarval_bad)
 576     DBG_EVAL_CONFIRM(cmp);
 577
 578   return tv;
 579 }