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