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