nsz Git - libfirm/blob - ir/opt/fp-vrp.c

   1 /*
   2  * Copyright (C) 1995-2010 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  * @file
  22  * @brief   Data-flow driven minimal fixpoint value range propagation
  23  * @author  Christoph Mallon
  24  * @version $Id$
  25  */
  26
  27 #include "config.h"
  28
  29 #include "adt/pdeq.h"
  30 #include "adt/obst.h"
  31 #include "adt/xmalloc.h"
  32 #include "debug.h"
  33 #include "ircons.h"
  34 #include "irdom.h"
  35 #include "iredges.h"
  36 #include "irgmod.h"
  37 #include "irgraph.h"
  38 #include "irgwalk.h"
  39 #include "irnode.h"
  40 #include "iroptimize.h"
  41 #include "irtools.h"
  42 #include "tv.h"
  43
  44 /* TODO:
  45  * - Implement cleared/set bit calculation for Add, Sub, Minus, Mul, Div, Mod, Shl, Shr, Shrs, Rotl
  46  * - Implement min/max calculation for And, Eor, Or, Not, Conv, Shl, Shr, Shrs, Rotl, Mux
  47  * - Implement min/max calculation for Add, Sub, Minus, Mul, Div, Mod, Conv, Shl, Shr, Shrs, Rotl, Mux
  48  */
  49
  50 /* Tables of the cleared/set bit lattice
  51  *
  52  * Encoding of the lattice
  53  * zo
  54  * 00 0 zero
  55  * 01 - impossible state, is zero /and/ one
  56  * 10 T top, may be either zero or one
  57  * 11 1 one
  58  *
  59  * S = Sum
  60  * c = Carry
  61  * D = Difference
  62  * b = Borrow
  63  *
  64  * Not
  65  * A ~
  66  * 0 1
  67  * 1 0
  68  * T T
  69  *
  70  * Half adder, half subtractor, and, xor, or, Mux
  71  * AB  Sc  Db  &  ^  |  M
  72  * 00  00  00  0  0  0  0
  73  * 01  10  11  0  1  1  T
  74  * 0T  T0  TT  0  T  T  T
  75  * 10  10  10  0  1  1  T
  76  * 11  01  00  1  0  1  1
  77  * 1T  TT  T0  T  T  1  T
  78  * T0  T0  T0  0  T  T  T
  79  * T1  TT  TT  T  T  1  T
  80  * TT  TT  TT  T  T  T  T
  81  *
  82  * Full adder, full subtractor
  83  * ABc-1  Sc  Db
  84  * 000    00  00
  85  * 001    10  11
  86  * 00T    T0  TT
  87  * 010    10  11
  88  * 011    01  01
  89  * 01T    TT  T1
  90  * 0T0    T0  TT
  91  * 0T1    TT  T1
  92  * 0TT    TT  TT
  93  * 100    10  10
  94  * 101    01  00
  95  * 10T    TT  T0
  96  * 110    01  00
  97  * 111    11  11
  98  * 11T    T1  TT
  99  * 1T0    TT  T0
 100  * 1T1    T1  TT
 101  * 1TT    TT  TT
 102  * T00    T0  T0
 103  * T01    TT  TT
 104  * T0T    TT  TT
 105  * T10    TT  TT
 106  * T11    T1  T1
 107  * T1T    TT  TT
 108  * TT0    TT  TT
 109  * TT1    TT  TT
 110  * TTT    TT  TT
 111  *
 112  *
 113  * Assume: Xmin <= Xmax and no overflow
 114  * A + B = (Amin + Bmin, Amax + Bmax)
 115  *    -A = (-Amax, -Amin)
 116  * A - B = A + -B = (Amin (-B)min, Amax + (-B)max) = (Amin - Bmax, Amax - Bmin)
 117  */
 118
 119 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
 120
 121 static struct obstack obst;
 122
 123 typedef struct bitinfo
 124 {
 125         tarval* z; // safe zeroes, 0 = bit is zero,       1 = bit maybe is 1
 126         tarval* o; // safe ones,   0 = bit maybe is zero, 1 = bit is 1
 127 } bitinfo;
 128
 129 static inline bitinfo* get_bitinfo(ir_node const* const irn)
 130 {
 131         return get_irn_link(irn);
 132 }
 133
 134 static int set_bitinfo(ir_node* const irn, tarval* const z, tarval* const o)
 135 {
 136         bitinfo* b = get_bitinfo(irn);
 137         if (b == NULL) {
 138                 b = OALLOCZ(&obst, bitinfo);
 139                 set_irn_link(irn, b);
 140         } else if (z == b->z && o == b->o) {
 141                 return 0;
 142         }
 143         b->z = z;
 144         b->o = o;
 145         DB((dbg, LEVEL_3, "%+F: 0:%T 1:%T\n", irn, z, o));
 146         return 1;
 147 }
 148
 149 static int mode_is_intb(ir_mode const* const m)
 150 {
 151         return mode_is_int(m) || m == mode_b;
 152 }
 153
 154 static int transfer(ir_node* const irn)
 155 {
 156         ir_mode* const m = get_irn_mode(irn);
 157         tarval*        z;
 158         tarval*        o;
 159
 160         if (m == mode_X) {
 161                 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
 162                 switch (get_irn_opcode(irn)) {
 163                         case iro_Proj: {
 164                                 ir_node* const pred = get_Proj_pred(irn);
 165                                 if (is_Start(pred)) {
 166                                         z = get_tarval_b_true();
 167                                         o = get_tarval_b_false();
 168                                 } else if (is_Cond(pred)) {
 169                                         ir_node* const selector = get_Cond_selector(pred);
 170                                         bitinfo* const b        = get_bitinfo(selector);
 171                                         tarval*  const bz       = b->z;
 172                                         tarval*  const bo       = b->o;
 173                                         if (get_irn_mode(selector) == mode_b) {
 174                                                 if (bz == bo) {
 175                                                         if ((bz == get_tarval_b_true()) == get_Proj_proj(irn)) {
 176                                                                 z = o = get_tarval_b_true();
 177                                                         } else {
 178                                                                 z = o = get_tarval_b_false();
 179                                                         }
 180                                                 } else {
 181                                                         goto result_unknown_X;
 182                                                 }
 183                                         } else {
 184                                                 long const val = get_Proj_proj(irn);
 185                                                 if (val != get_Cond_default_proj(pred)) {
 186                                                         tarval* const tv = new_tarval_from_long(val, get_irn_mode(selector));
 187                                                         if (!tarval_is_null(tarval_andnot(tv, bz)) ||
 188                                                                         !tarval_is_null(tarval_andnot(bo, tv))) {
 189                                                                 // At least one bit differs.
 190                                                                 z = o = get_tarval_b_false();
 191 #if 0 // TODO must handle default Proj
 192                                                         } else if (bz == bo && bz == tv) {
 193                                                                 z = o = get_tarval_b_true();
 194 #endif
 195                                                         } else {
 196                                                                 goto result_unknown_X;
 197                                                         }
 198                                                 } else {
 199                                                         goto cannot_analyse_X;
 200                                                 }
 201                                         }
 202                                 } else {
 203                                         goto cannot_analyse_X;
 204                                 }
 205                                 break;
 206                         }
 207
 208                         case iro_Jmp: {
 209                                 bitinfo* const b = get_bitinfo(get_nodes_block(irn));
 210                                 z = b->z;
 211                                 o = b->o;
 212                                 break;
 213                         }
 214
 215                         default:
 216 cannot_analyse_X:
 217                                 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
 218 result_unknown_X:
 219                                 z = get_tarval_b_true();
 220                                 o = get_tarval_b_false();
 221                                 break;
 222                 }
 223         } else if (is_Block(irn)) {
 224                 int       reachable = 0;
 225                 int const arity     = get_Block_n_cfgpreds(irn);
 226                 int       i;
 227
 228                 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
 229                 for (i = 0; i != arity; ++i) {
 230                         bitinfo* const b = get_bitinfo(get_Block_cfgpred(irn, i));
 231                         if (b != NULL && b->z == get_tarval_b_true()) {
 232                                 reachable = 1;
 233                                 break;
 234                         }
 235                 }
 236
 237                 o = get_tarval_b_false();
 238                 z = reachable || irn == get_irg_start_block(get_irn_irg(irn)) ? get_tarval_b_true() : o;
 239         } else if (mode_is_intb(m)) {
 240                 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
 241                 switch (get_irn_opcode(irn)) {
 242                         case iro_Const: {
 243                                 z = o = get_Const_tarval(irn);
 244                                 break;
 245                         }
 246
 247                         case iro_Shl: {
 248                                 bitinfo* const l  = get_bitinfo(get_Shl_left(irn));
 249                                 bitinfo* const r  = get_bitinfo(get_Shl_right(irn));
 250                                 tarval*  const rz = r->z;
 251                                 if (rz == r->o) {
 252                                         z = tarval_shl(l->z, rz);
 253                                         o = tarval_shl(l->o, rz);
 254                                 } else {
 255                                         goto cannot_analyse;
 256                                 }
 257                                 break;
 258                         }
 259
 260                         case iro_Shr: {
 261                                 bitinfo* const l  = get_bitinfo(get_Shr_left(irn));
 262                                 bitinfo* const r  = get_bitinfo(get_Shr_right(irn));
 263                                 tarval*  const rz = r->z;
 264                                 if (rz == r->o) {
 265                                         z = tarval_shr(l->z, rz);
 266                                         o = tarval_shr(l->o, rz);
 267                                 } else {
 268                                         goto cannot_analyse;
 269                                 }
 270                                 break;
 271                         }
 272
 273                         case iro_Shrs: {
 274                                 bitinfo* const l  = get_bitinfo(get_Shrs_left(irn));
 275                                 bitinfo* const r  = get_bitinfo(get_Shrs_right(irn));
 276                                 tarval*  const rz = r->z;
 277                                 if (rz == r->o) {
 278                                         z = tarval_shrs(l->z, rz);
 279                                         o = tarval_shrs(l->o, rz);
 280                                 } else {
 281                                         goto cannot_analyse;
 282                                 }
 283                                 break;
 284                         }
 285
 286                         case iro_Rotl: {
 287                                 bitinfo* const l  = get_bitinfo(get_Rotl_left(irn));
 288                                 bitinfo* const r  = get_bitinfo(get_Rotl_right(irn));
 289                                 tarval*  const rz = r->z;
 290                                 if (rz == r->o) {
 291                                         z = tarval_rotl(l->z, rz);
 292                                         o = tarval_rotl(l->o, rz);
 293                                 } else {
 294                                         goto cannot_analyse;
 295                                 }
 296                                 break;
 297                         }
 298
 299                         case iro_Add: {
 300                                 bitinfo* const l  = get_bitinfo(get_Add_left(irn));
 301                                 bitinfo* const r  = get_bitinfo(get_Add_right(irn));
 302                                 tarval*  const lz = l->z;
 303                                 tarval*  const lo = l->o;
 304                                 tarval*  const rz = r->z;
 305                                 tarval*  const ro = r->o;
 306                                 if (lz == lo && rz == ro) {
 307                                         z = o = tarval_add(lz, rz);
 308                                 } else {
 309                                         // TODO improve: can only do lower disjoint bits
 310                                         /* Determine where any of the operands has zero bits, i.e. where no
 311                                          * carry out is generated if there is not carry in */
 312                                         tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
 313                                         /* Generate a mask of the lower consecutive zeroes: x | -x.  In this
 314                                          * range the addition is disjoint and therefore Add behaves like Or.
 315                                          */
 316                                         tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
 317                                         z = tarval_or( tarval_or(lz, rz), low_zero_mask);
 318                                         tarval* const low_one_mask  = tarval_not(low_zero_mask);
 319                                         o = tarval_and(tarval_or(lo, ro), low_one_mask);
 320                                 }
 321                                 break;
 322                         }
 323
 324                         case iro_Sub: {
 325                                 bitinfo* const l = get_bitinfo(get_Sub_left(irn));
 326                                 bitinfo* const r = get_bitinfo(get_Sub_right(irn));
 327                                 if (l != NULL && r != NULL) { // Sub might subtract pointers.
 328                                         tarval* const lz = l->z;
 329                                         tarval* const lo = l->o;
 330                                         tarval* const rz = r->z;
 331                                         tarval* const ro = r->o;
 332                                         if (lz == lo && rz == ro) {
 333                                                 z = o = tarval_sub(lz, rz, NULL);
 334                                         } else if (tarval_is_null(tarval_andnot(rz, lo))) {
 335                                                 /* Every possible one of the subtrahend is backed by a safe one of the
 336                                                  * minuend, i.e. there are no borrows. */
 337                                                 // TODO extend no-borrow like carry for Add above
 338                                                 z = tarval_andnot(lz, ro);
 339                                                 o = tarval_andnot(lo, rz);
 340                                         } else {
 341                                                 goto cannot_analyse;
 342                                         }
 343                                 } else {
 344                                         goto cannot_analyse;
 345                                 }
 346                                 break;
 347                         }
 348
 349                         case iro_Mul: {
 350                                 bitinfo* const l  = get_bitinfo(get_Mul_left(irn));
 351                                 bitinfo* const r  = get_bitinfo(get_Mul_right(irn));
 352                                 tarval*  const lz = l->z;
 353                                 tarval*  const lo = l->o;
 354                                 tarval*  const rz = r->z;
 355                                 tarval*  const ro = r->o;
 356                                 if (lz == lo && rz == ro) {
 357                                         z = o = tarval_mul(lz, rz);
 358                                 } else {
 359                                         // TODO improve
 360                                         // Determine safe lower zeroes: x | -x.
 361                                         tarval* const lzn = tarval_or(lz, tarval_neg(lz));
 362                                         tarval* const rzn = tarval_or(rz, tarval_neg(rz));
 363                                         // Concatenate safe lower zeroes.
 364                                         if (tarval_cmp(lzn, rzn) == pn_Cmp_Lt) {
 365                                                 z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn);
 366                                         } else {
 367                                                 z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), lzn);
 368                                         }
 369                                         o = get_tarval_null(m);
 370                                 }
 371                                 break;
 372                         }
 373
 374                         case iro_Minus: {
 375                                 bitinfo* const b = get_bitinfo(get_Minus_op(irn));
 376                                 if (b->z == b->o) {
 377                                         z = o = tarval_neg(b->z);
 378                                 } else {
 379                                         goto cannot_analyse;
 380                                 }
 381                                 break;
 382                         }
 383
 384                         case iro_And: {
 385                                 bitinfo* const l = get_bitinfo(get_And_left(irn));
 386                                 bitinfo* const r = get_bitinfo(get_And_right(irn));
 387                                 z = tarval_and(l->z, r->z);
 388                                 o = tarval_and(l->o, r->o);
 389                                 break;
 390                         }
 391
 392                         case iro_Or: {
 393                                 bitinfo* const l = get_bitinfo(get_Or_left(irn));
 394                                 bitinfo* const r = get_bitinfo(get_Or_right(irn));
 395                                 z = tarval_or(l->z, r->z);
 396                                 o = tarval_or(l->o, r->o);
 397                                 break;
 398                         }
 399
 400                         case iro_Eor: {
 401                                 bitinfo* const l  = get_bitinfo(get_Eor_left(irn));
 402                                 bitinfo* const r  = get_bitinfo(get_Eor_right(irn));
 403                                 tarval*  const lz = l->z;
 404                                 tarval*  const lo = l->o;
 405                                 tarval*  const rz = r->z;
 406                                 tarval*  const ro = r->o;
 407                                 z = tarval_or(tarval_andnot(lz, ro), tarval_andnot(rz, lo));
 408                                 o = tarval_or(tarval_andnot(ro, lz), tarval_andnot(lo, rz));
 409                                 break;
 410                         }
 411
 412                         case iro_Not: {
 413                                 bitinfo* const b = get_bitinfo(get_Not_op(irn));
 414                                 z = tarval_not(b->o);
 415                                 o = tarval_not(b->z);
 416                                 break;
 417                         }
 418
 419                         case iro_Conv: {
 420                                 bitinfo* const b = get_bitinfo(get_Conv_op(irn));
 421                                 if (b == NULL) // Happens when converting from float values.
 422                                         goto result_unknown;
 423                                 z = tarval_convert_to(b->z, m);
 424                                 o = tarval_convert_to(b->o, m);
 425                                 break;
 426                         }
 427
 428                         case iro_Mux: {
 429                                 bitinfo* const f = get_bitinfo(get_Mux_false(irn));
 430                                 bitinfo* const t = get_bitinfo(get_Mux_true(irn));
 431                                 bitinfo* const c = get_bitinfo(get_Mux_sel(irn));
 432                                 if (c->o == get_tarval_b_true()) {
 433                                         z = t->z;
 434                                         o = t->o;
 435                                 } else if (c->z == get_tarval_b_false()) {
 436                                         z = f->z;
 437                                         o = f->o;
 438                                 } else {
 439                                         z = tarval_or( f->z, t->z);
 440                                         z = tarval_and(f->o, t->o);
 441                                 }
 442                         }
 443
 444                         case iro_Phi: {
 445                                 ir_node* const block = get_nodes_block(irn);
 446                                 int      const arity = get_Phi_n_preds(irn);
 447                                 int            i;
 448
 449                                 z = get_tarval_null(m);
 450                                 o = get_tarval_all_one(m);
 451                                 for (i = 0; i != arity; ++i) {
 452                                         bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
 453                                         if (b_cfg != NULL && b_cfg->z != get_tarval_b_false()) {
 454                                                 bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
 455                                                 z = tarval_or( z, b->z);
 456                                                 o = tarval_and(o, b->o);
 457                                         }
 458                                 }
 459                                 break;
 460                         }
 461
 462                         case iro_Proj: {
 463                                 ir_node* const pred = get_Proj_pred(irn);
 464                                 if (is_Cmp(pred)) { // TODO generalize
 465                                         bitinfo* const l = get_bitinfo(get_Cmp_left(pred));
 466                                         bitinfo* const r = get_bitinfo(get_Cmp_right(pred));
 467                                         if (l == NULL || r == NULL)
 468                                                 goto result_unknown; // Cmp compares something we cannot evaluate.
 469                                         switch (get_Proj_proj(irn)) {
 470                                                 case pn_Cmp_Lg: {
 471                                                         tarval* const lz = l->z;
 472                                                         tarval* const lo = l->o;
 473                                                         tarval* const rz = r->z;
 474                                                         tarval* const ro = r->o;
 475                                                         if (!tarval_is_null(tarval_andnot(ro, lz)) ||
 476                                                                         !tarval_is_null(tarval_andnot(lo, rz))) {
 477                                                                 // At least one bit differs.
 478                                                                 z = o = get_tarval_b_true();
 479                                                         } else if (lz == lo && rz == ro && lz == rz) {
 480                                                                 z = o = get_tarval_b_false();
 481                                                         } else {
 482                                                                 goto result_unknown;
 483                                                         }
 484                                                         break;
 485                                                 }
 486
 487                                                 case pn_Cmp_Eq: {
 488                                                         tarval* const lz = l->z;
 489                                                         tarval* const lo = l->o;
 490                                                         tarval* const rz = r->z;
 491                                                         tarval* const ro = r->o;
 492                                                         if (!tarval_is_null(tarval_andnot(ro, lz)) ||
 493                                                                         !tarval_is_null(tarval_andnot(lo, rz))) {
 494                                                                 // At least one bit differs.
 495                                                                 z = o = get_tarval_b_false();
 496                                                         } else if (lz == lo && rz == ro && lz == rz) {
 497                                                                 z = o = get_tarval_b_true();
 498                                                         } else {
 499                                                                 goto result_unknown;
 500                                                         }
 501                                                         break;
 502                                                 }
 503
 504                                                 default:
 505                                                         goto cannot_analyse;
 506                                         }
 507                                 } else {
 508                                         goto cannot_analyse;
 509                                 }
 510                                 break;
 511                         }
 512
 513                         default: {
 514 cannot_analyse:
 515                                 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
 516 result_unknown:
 517                                 z = get_tarval_all_one(m);
 518                                 o = get_tarval_null(m);
 519                                 break;
 520                         }
 521                 }
 522         } else {
 523                 return 0;
 524         }
 525
 526         return set_bitinfo(irn, z, o);
 527 }
 528
 529 static void first_round(ir_node* const irn, void* const env)
 530 {
 531         pdeq* const q = env;
 532
 533         transfer(irn);
 534         if (is_Phi(irn) || is_Block(irn)) {
 535                 /* Only Phis (and their users) need another round, if we did not have
 536                  * information about all their inputs in the first round, i.e. in loops. */
 537                 /* TODO inserts all Phis, should only insert Phis, which did no have all
 538                  * predecessors available */
 539                 pdeq_putr(q, irn);
 540         }
 541 }
 542
 543 static void apply_result(ir_node* const irn, void* const env)
 544 {
 545         bitinfo* const b = get_bitinfo(irn);
 546         tarval*        z;
 547         tarval*        o;
 548         (void)env;
 549
 550         if (!b) return;
 551         if (is_Const(irn)) return; // It cannot get any better than a Const.
 552
 553         z = b->z;
 554         o = b->o;
 555         // Only display information if we could find out anything about the value.
 556         DEBUG_ONLY(if (!tarval_is_all_one(z) || !tarval_is_null(o)))
 557                 DB((dbg, LEVEL_2, "%+F: 0:%T 1:%T%s\n", irn, z, o, z == o ? " --- constant" : ""));
 558
 559         // Replace node with constant value by Const.
 560         if (z == o) {
 561                 ir_mode* const m = get_irn_mode(irn);
 562                 ir_node*       n;
 563                 if (mode_is_intb(m)) {
 564                         n = new_Const(z);
 565                 } else if (m == mode_X) {
 566                         ir_node*  const block = get_nodes_block(irn);
 567                         ir_graph* const irg   = get_Block_irg(block);
 568                         if (z == get_tarval_b_true()) {
 569                                 // Might produce an endless loop, so keep the block.
 570                                 add_End_keepalive(get_irg_end(irg), block);
 571                                 n = new_r_Jmp(block);
 572                         } else {
 573                                 n = new_r_Bad(irg);
 574                                 /* Transferring analysis information to the bad node makes it a
 575                                  * candidate for replacement. */
 576                                 goto exchange_only;
 577                         }
 578                 } else {
 579                         return;
 580                 }
 581                 set_irn_link(n, b);
 582 exchange_only:
 583                 exchange(irn, n);
 584         }
 585
 586         switch (get_irn_opcode(irn)) {
 587                 case iro_And: {
 588                         ir_node*       const l  = get_And_left(irn);
 589                         ir_node*       const r  = get_And_right(irn);
 590                         bitinfo const* const bl = get_bitinfo(l);
 591                         bitinfo const* const br = get_bitinfo(r);
 592                         if (bl->z == bl->o) {
 593                                 if (tarval_is_null(tarval_andnot(br->z, bl->z))) {
 594                                         DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
 595                                         exchange(irn, r);
 596                                 }
 597                         } else if (br->z == br->o) {
 598                                 if (tarval_is_null(tarval_andnot(bl->z, br->z))) {
 599                                         DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
 600                                         exchange(irn, l);
 601                                 }
 602                         }
 603                         break;
 604                 }
 605
 606                 case iro_Or: {
 607                         ir_node*       const l  = get_Or_left(irn);
 608                         ir_node*       const r  = get_Or_right(irn);
 609                         bitinfo const* const bl = get_bitinfo(l);
 610                         bitinfo const* const br = get_bitinfo(r);
 611                         if (bl->z == bl->o) {
 612                                 if (tarval_is_null(tarval_andnot(bl->o, br->o))) {
 613                                         DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
 614                                         exchange(irn, r);
 615                                 }
 616                         } else if (br->z == br->o) {
 617                                 if (tarval_is_null(tarval_andnot(br->o, bl->o))) {
 618                                         DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
 619                                         exchange(irn, l);
 620                                 }
 621                         }
 622                         break;
 623                 }
 624         }
 625 }
 626
 627 static void queue_users(pdeq* const q, ir_node* const n)
 628 {
 629         if (get_irn_mode(n) == mode_X) {
 630                 /* When the state of a control flow node changes, not only queue its
 631                  * successor blocks, but also the Phis in these blocks, because the Phis
 632                  * must reconsider this input path. */
 633                 ir_edge_t const* e;
 634                 foreach_out_edge(n, e) {
 635                         ir_node*  const  src = get_edge_src_irn(e);
 636                         ir_edge_t const* src_e;
 637                         pdeq_putr(q, src);
 638                         foreach_out_edge(src, src_e) {
 639                                 ir_node* const src_src = get_edge_src_irn(src_e);
 640                                 if (is_Phi(src_src))
 641                                         pdeq_putr(q, src_src);
 642                         }
 643                 }
 644         } else {
 645                 ir_edge_t const* e;
 646                 foreach_out_edge(n, e) {
 647                         ir_node* const src = get_edge_src_irn(e);
 648                         if (get_irn_mode(src) == mode_T) {
 649                                 queue_users(q, src);
 650                         } else {
 651                                 pdeq_putr(q, src);
 652                         }
 653                 }
 654         }
 655 }
 656
 657 void fixpoint_vrp(ir_graph* const irg)
 658 {
 659         FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp");
 660         DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg));
 661
 662         obstack_init(&obst);
 663
 664         edges_assure(irg);
 665         assure_doms(irg);
 666
 667         { pdeq* const q = new_pdeq();
 668
 669                 /* TODO Improve iteration order. Best is reverse postorder in data flow
 670                  * direction and respecting loop nesting for fastest convergence. */
 671                 irg_walk_blkwise_dom_top_down(irg, firm_clear_link, first_round, q);
 672
 673                 while (!pdeq_empty(q)) {
 674                         ir_node* const n = pdeq_getl(q);
 675                         if (transfer(n))
 676                                 queue_users(q, n);
 677                 }
 678
 679                 del_pdeq(q);
 680         }
 681
 682         DB((dbg, LEVEL_2, "---> Applying analysis results\n"));
 683         irg_walk_graph(irg, NULL, apply_result, NULL);
 684
 685         obstack_free(&obst, NULL);
 686 }