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

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