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