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