2 * Copyright (C) 1995-2010 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
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.
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.
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
22 * @brief Data-flow driven minimal fixpoint value range propagation
23 * @author Christoph Mallon
33 #include "adt/xmalloc.h"
39 #include "irgraph_t.h"
42 #include "iroptimize.h"
47 #include "opt_manage.h"
50 * - Implement cleared/set bit calculation for Add, Sub, Minus, Mul, Div, Mod, Shl, Shr, Shrs, Rotl
51 * - Implement min/max calculation for And, Eor, Or, Not, Conv, Shl, Shr, Shrs, Rotl, Mux
52 * - Implement min/max calculation for Add, Sub, Minus, Mul, Div, Mod, Conv, Shl, Shr, Shrs, Rotl, Mux
55 /* Tables of the cleared/set bit lattice
57 * Encoding of the lattice
60 * 01 - impossible state, is zero /and/ one
61 * 10 T top, may be either zero or one
75 * Half adder, half subtractor, and, xor, or, Mux
87 * Full adder, full subtractor
118 * Assume: Xmin <= Xmax and no overflow
119 * A + B = (Amin + Bmin, Amax + Bmax)
120 * -A = (-Amax, -Amin)
121 * A - B = A + -B = (Amin (-B)min, Amax + (-B)max) = (Amin - Bmax, Amax - Bmin)
124 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
126 static struct obstack obst;
128 typedef struct bitinfo
130 ir_tarval* z; // safe zeroes, 0 = bit is zero, 1 = bit maybe is 1
131 ir_tarval* o; // safe ones, 0 = bit maybe is zero, 1 = bit is 1
134 typedef struct environment_t {
135 unsigned modified:1; /**< Set, if the graph was modified. */
138 static bool is_undefined(bitinfo const* const b)
140 return tarval_is_null(b->z) && tarval_is_all_one(b->o);
143 static inline bitinfo* get_bitinfo(ir_node const* const irn)
145 return (bitinfo*)get_irn_link(irn);
148 static int set_bitinfo(ir_node* const irn, ir_tarval* const z, ir_tarval* const o)
150 bitinfo* b = get_bitinfo(irn);
152 b = OALLOCZ(&obst, bitinfo);
153 set_irn_link(irn, b);
154 } else if (z == b->z && o == b->o) {
157 /* Assert monotonicity. */
158 assert(tarval_is_null(tarval_andnot(b->z, z)));
159 assert(tarval_is_null(tarval_andnot(o, b->o)));
163 DB((dbg, LEVEL_3, "%+F: 0:%T 1:%T\n", irn, z, o));
167 static int mode_is_intb(ir_mode const* const m)
169 return mode_is_int(m) || m == mode_b;
172 static int transfer(ir_node* const irn)
174 ir_tarval* const f = get_tarval_b_false();
175 ir_tarval* const t = get_tarval_b_true();
176 ir_mode* const m = get_irn_mode(irn);
180 if (is_Bad(irn)) return 0;
183 bitinfo* const b = get_bitinfo(get_nodes_block(irn));
185 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
187 /* Unreachble blocks might have no bitinfo. */
188 if (b == NULL || b->z == f) {
192 } else switch (get_irn_opcode(irn)) {
194 ir_node* const pred = get_Proj_pred(irn);
195 if (is_Start(pred)) {
196 goto result_unknown_X;
197 } else if (is_Cond(pred)) {
198 ir_node* const selector = get_Cond_selector(pred);
199 bitinfo* const b = get_bitinfo(selector);
203 if ((b->z == t) == get_Proj_proj(irn)) {
209 goto result_unknown_X;
211 } else if (is_Switch(pred)) {
212 ir_node* const selector = get_Switch_selector(pred);
213 bitinfo* const b = get_bitinfo(selector);
217 goto cannot_analyse_X;
219 goto cannot_analyse_X;
225 goto result_unknown_X;
229 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
235 } else if (is_Block(irn)) {
237 int const arity = get_Block_n_cfgpreds(irn);
240 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
241 for (i = 0; i != arity; ++i) {
242 bitinfo* const b = get_bitinfo(get_Block_cfgpred(irn, i));
243 if (b != NULL && b->z == t) {
250 ir_graph *const irg = get_Block_irg(irn);
252 irn == get_irg_start_block(irg) ||
253 irn == get_irg_end_block(irg);
263 } else if (mode_is_intb(m)) {
264 bitinfo* const b = get_bitinfo(get_nodes_block(irn));
266 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
268 if (b == NULL || b->z == f) {
270 z = get_tarval_null(m);
271 o = get_tarval_all_one(m);
272 } else if (is_Phi(irn)) {
273 ir_node* const block = get_nodes_block(irn);
274 int const arity = get_Phi_n_preds(irn);
277 z = get_tarval_null(m);
278 o = get_tarval_all_one(m);
279 for (i = 0; i != arity; ++i) {
280 bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
281 if (b_cfg != NULL && b_cfg->z != f) {
282 bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
283 /* Only use input if it's not undefined. */
284 if (!is_undefined(b)) {
285 z = tarval_or( z, b->z);
286 o = tarval_and(o, b->o);
291 int const arity = get_irn_arity(irn);
294 /* Undefined if any input is undefined. */
295 for (i = 0; i != arity; ++i) {
296 ir_node* const pred = get_irn_n(irn, i);
297 bitinfo* const pred_b = get_bitinfo(pred);
298 if (pred_b != NULL && is_undefined(pred_b))
302 switch (get_irn_opcode(irn)) {
304 z = o = get_Const_tarval(irn);
309 ir_node* const v = get_Confirm_value(irn);
310 bitinfo* const b = get_bitinfo(v);
311 /* TODO Use bound and relation. */
314 if ((get_Confirm_relation(irn) & ~ir_relation_unordered) == ir_relation_equal) {
315 bitinfo* const bound_b = get_bitinfo(get_Confirm_bound(irn));
316 z = tarval_and(z, bound_b->z);
317 o = tarval_or( o, bound_b->o);
323 bitinfo* const l = get_bitinfo(get_Shl_left(irn));
324 bitinfo* const r = get_bitinfo(get_Shl_right(irn));
325 ir_tarval* const rz = r->z;
327 z = tarval_shl(l->z, rz);
328 o = tarval_shl(l->o, rz);
336 bitinfo* const l = get_bitinfo(get_Shr_left(irn));
337 bitinfo* const r = get_bitinfo(get_Shr_right(irn));
338 ir_tarval* const rz = r->z;
340 z = tarval_shr(l->z, rz);
341 o = tarval_shr(l->o, rz);
349 bitinfo* const l = get_bitinfo(get_Shrs_left(irn));
350 bitinfo* const r = get_bitinfo(get_Shrs_right(irn));
351 ir_tarval* const rz = r->z;
353 z = tarval_shrs(l->z, rz);
354 o = tarval_shrs(l->o, rz);
362 bitinfo* const l = get_bitinfo(get_Rotl_left(irn));
363 bitinfo* const r = get_bitinfo(get_Rotl_right(irn));
364 ir_tarval* const rz = r->z;
366 z = tarval_rotl(l->z, rz);
367 o = tarval_rotl(l->o, rz);
375 bitinfo* const l = get_bitinfo(get_Add_left(irn));
376 bitinfo* const r = get_bitinfo(get_Add_right(irn));
377 ir_tarval* const lz = l->z;
378 ir_tarval* const lo = l->o;
379 ir_tarval* const rz = r->z;
380 ir_tarval* const ro = r->o;
381 if (lz == lo && rz == ro) {
382 z = o = tarval_add(lz, rz);
384 // TODO improve: can only do lower disjoint bits
385 /* Determine where any of the operands has zero bits, i.e. where no
386 * carry out is generated if there is not carry in */
387 ir_tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
388 /* Generate a mask of the lower consecutive zeroes: x | -x. In this
389 * range the addition is disjoint and therefore Add behaves like Or.
391 ir_tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
392 ir_tarval* const low_one_mask = tarval_not(low_zero_mask);
393 z = tarval_or( tarval_or(lz, rz), low_zero_mask);
394 o = tarval_and(tarval_or(lo, ro), low_one_mask);
400 bitinfo* const l = get_bitinfo(get_Sub_left(irn));
401 bitinfo* const r = get_bitinfo(get_Sub_right(irn));
402 if (l != NULL && r != NULL) { // Sub might subtract pointers.
403 ir_tarval* const lz = l->z;
404 ir_tarval* const lo = l->o;
405 ir_tarval* const rz = r->z;
406 ir_tarval* const ro = r->o;
407 if (lz == lo && rz == ro) {
408 z = o = tarval_sub(lz, rz, NULL);
409 } else if (tarval_is_null(tarval_andnot(rz, lo))) {
410 /* Every possible one of the subtrahend is backed by a safe one of the
411 * minuend, i.e. there are no borrows. */
412 // TODO extend no-borrow like carry for Add above
413 z = tarval_andnot(lz, ro);
414 o = tarval_andnot(lo, rz);
425 bitinfo* const l = get_bitinfo(get_Mul_left(irn));
426 bitinfo* const r = get_bitinfo(get_Mul_right(irn));
427 ir_tarval* const lz = l->z;
428 ir_tarval* const lo = l->o;
429 ir_tarval* const rz = r->z;
430 ir_tarval* const ro = r->o;
431 if (lz == lo && rz == ro) {
432 z = o = tarval_mul(lz, rz);
435 // Determine safe lower zeroes: x | -x.
436 ir_tarval* const lzn = tarval_or(lz, tarval_neg(lz));
437 ir_tarval* const rzn = tarval_or(rz, tarval_neg(rz));
438 // Concatenate safe lower zeroes.
439 if (tarval_cmp(lzn, rzn) == ir_relation_less) {
440 z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn);
442 z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), lzn);
444 o = get_tarval_null(m);
450 bitinfo* const b = get_bitinfo(get_Minus_op(irn));
452 z = o = tarval_neg(b->z);
460 bitinfo* const l = get_bitinfo(get_And_left(irn));
461 bitinfo* const r = get_bitinfo(get_And_right(irn));
462 z = tarval_and(l->z, r->z);
463 o = tarval_and(l->o, r->o);
468 bitinfo* const l = get_bitinfo(get_Or_left(irn));
469 bitinfo* const r = get_bitinfo(get_Or_right(irn));
470 z = tarval_or(l->z, r->z);
471 o = tarval_or(l->o, r->o);
476 bitinfo* const l = get_bitinfo(get_Eor_left(irn));
477 bitinfo* const r = get_bitinfo(get_Eor_right(irn));
478 ir_tarval* const lz = l->z;
479 ir_tarval* const lo = l->o;
480 ir_tarval* const rz = r->z;
481 ir_tarval* const ro = r->o;
482 z = tarval_or(tarval_andnot(lz, ro), tarval_andnot(rz, lo));
483 o = tarval_or(tarval_andnot(ro, lz), tarval_andnot(lo, rz));
488 bitinfo* const b = get_bitinfo(get_Not_op(irn));
489 z = tarval_not(b->o);
490 o = tarval_not(b->z);
495 bitinfo* const b = get_bitinfo(get_Conv_op(irn));
496 if (b == NULL) // Happens when converting from float values.
498 z = tarval_convert_to(b->z, m);
499 o = tarval_convert_to(b->o, m);
504 bitinfo* const bf = get_bitinfo(get_Mux_false(irn));
505 bitinfo* const bt = get_bitinfo(get_Mux_true(irn));
506 bitinfo* const c = get_bitinfo(get_Mux_sel(irn));
510 } else if (c->z == f) {
514 z = tarval_or( bf->z, bt->z);
515 o = tarval_and(bf->o, bt->o);
521 bitinfo* const l = get_bitinfo(get_Cmp_left(irn));
522 bitinfo* const r = get_bitinfo(get_Cmp_right(irn));
523 if (l == NULL || r == NULL) {
524 goto result_unknown; // Cmp compares something we cannot evaluate.
526 ir_tarval* const lz = l->z;
527 ir_tarval* const lo = l->o;
528 ir_tarval* const rz = r->z;
529 ir_tarval* const ro = r->o;
530 ir_relation const relation = get_Cmp_relation(irn);
532 case ir_relation_less_greater:
533 if (!tarval_is_null(tarval_andnot(ro, lz)) ||
534 !tarval_is_null(tarval_andnot(lo, rz))) {
535 // At least one bit differs.
537 } else if (lz == lo && rz == ro && lz == rz) {
544 case ir_relation_equal:
545 if (!tarval_is_null(tarval_andnot(ro, lz)) ||
546 !tarval_is_null(tarval_andnot(lo, rz))) {
547 // At least one bit differs.
549 } else if (lz == lo && rz == ro && lz == rz) {
556 case ir_relation_less_equal:
557 case ir_relation_less:
558 /* TODO handle negative values */
559 if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
560 tarval_is_negative(rz) || tarval_is_negative(ro))
563 if (tarval_cmp(lz, ro) & relation) {
564 /* Left upper bound is smaller(/equal) than right lower bound. */
566 } else if (!(tarval_cmp(lo, rz) & relation)) {
567 /* Left lower bound is not smaller(/equal) than right upper bound. */
574 case ir_relation_greater_equal:
575 case ir_relation_greater:
576 /* TODO handle negative values */
577 if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
578 tarval_is_negative(rz) || tarval_is_negative(ro))
581 if (!(tarval_cmp(lz, ro) & relation)) {
582 /* Left upper bound is not greater(/equal) than right lower bound. */
584 } else if (tarval_cmp(lo, rz) & relation) {
585 /* Left lower bound is greater(/equal) than right upper bound. */
601 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
603 z = get_tarval_all_one(m);
604 o = get_tarval_null(m);
613 return set_bitinfo(irn, z, o);
616 static void first_round(ir_node* const irn, void* const env)
618 pdeq* const q = (pdeq*)env;
621 if (is_Phi(irn) || is_Block(irn)) {
622 /* Only Phis (and their users) need another round, if we did not have
623 * information about all their inputs in the first round, i.e. in loops. */
624 /* TODO inserts all Phis, should only insert Phis, which did no have all
625 * predecessors available */
630 static ir_node *make_bad_block(ir_graph *irg)
632 ir_node *bad = new_r_Bad(irg, mode_BB);
633 bitinfo *bb = get_bitinfo(bad);
635 ir_tarval* const f = get_tarval_b_false();
636 ir_tarval* const t = get_tarval_b_true();
637 set_bitinfo(bad, f, t); /* Undefined. */
642 static void apply_result(ir_node* const irn, void* ctx)
644 environment_t* env = (environment_t*)ctx;
652 block_b = get_bitinfo(irn);
653 /* Trivially unreachable blocks have no info. */
654 if (block_b == NULL || block_b->z == get_tarval_b_false()) {
655 ir_node *bad = make_bad_block(get_irn_irg(irn));
662 block = get_nodes_block(irn);
663 block_b = get_bitinfo(block);
664 /* Trivially unreachable blocks have no info. */
665 if (block_b == NULL || block_b->z == get_tarval_b_false()) {
666 /* Unreachable blocks might be replaced before the nodes in them. */
667 ir_mode *mode = get_irn_mode(irn);
668 ir_graph *irg = get_irn_irg(irn);
669 ir_node *bad = new_r_Bad(irg, mode);
675 b = get_bitinfo(irn);
677 if (is_Const(irn)) return; // It cannot get any better than a Const.
681 // Only display information if we could find out anything about the value.
682 DEBUG_ONLY(if (!tarval_is_all_one(z) || !tarval_is_null(o)))
683 DB((dbg, LEVEL_2, "%+F: 0:%T 1:%T%s\n", irn, z, o, z == o ? " --- constant" : ""));
685 // Replace node with constant value by Const.
687 ir_mode* const m = get_irn_mode(irn);
689 if (mode_is_intb(m)) {
690 ir_graph *irg = get_irn_irg(irn);
691 n = new_r_Const(irg, z);
692 } else if (m == mode_X) {
693 ir_graph* const irg = get_Block_irg(block);
694 if (z == get_tarval_b_true()) {
695 // Might produce an endless loop, so keep the block.
696 add_End_keepalive(get_irg_end(irg), block);
697 n = new_r_Jmp(block);
699 n = new_r_Bad(irg, mode_X);
700 /* Transferring analysis information to the bad node makes it a
701 * candidate for replacement. */
713 switch (get_irn_opcode(irn)) {
715 ir_node* const l = get_And_left(irn);
716 ir_node* const r = get_And_right(irn);
717 bitinfo const* const bl = get_bitinfo(l);
718 bitinfo const* const br = get_bitinfo(r);
719 if (bl->z == bl->o) {
720 if (tarval_is_null(tarval_andnot(br->z, bl->z))) {
721 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
725 } else if (br->z == br->o) {
726 if (tarval_is_null(tarval_andnot(bl->z, br->z))) {
727 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
736 ir_node* const l = get_Eor_left(irn);
737 ir_node* const r = get_Eor_right(irn);
738 bitinfo const* const bl = get_bitinfo(l);
739 bitinfo const* const br = get_bitinfo(r);
740 /* if each bit is guaranteed to be zero on either the left or right
741 * then an Add will have the same effect as the Eor. Change it for
743 if (tarval_is_null(tarval_and(bl->z, br->z))) {
744 dbg_info *dbgi = get_irn_dbg_info(irn);
745 ir_node *block = get_nodes_block(irn);
746 ir_mode *mode = get_irn_mode(irn);
747 ir_node *new_node = new_rd_Add(dbgi, block, l, r, mode);
748 bitinfo const *bi = get_bitinfo(irn);
749 DB((dbg, LEVEL_2, "%+F(%+F, %+F) normalised to Add\n", irn, l, r));
750 set_bitinfo(new_node, bi->z, bi->o);
751 exchange(irn, new_node);
758 ir_node* const l = get_Or_left(irn);
759 ir_node* const r = get_Or_right(irn);
760 bitinfo const* const bl = get_bitinfo(l);
761 bitinfo const* const br = get_bitinfo(r);
762 if (bl->z == bl->o) {
763 if (tarval_is_null(tarval_andnot(bl->o, br->o))) {
764 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
768 } else if (br->z == br->o) {
769 if (tarval_is_null(tarval_andnot(br->o, bl->o))) {
770 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
776 /* if each bit is guaranteed to be zero on either the left or right
777 * then an Add will have the same effect as the Or. Change it for
779 if (tarval_is_null(tarval_and(bl->z, br->z))) {
780 dbg_info *dbgi = get_irn_dbg_info(irn);
781 ir_node *block = get_nodes_block(irn);
782 ir_mode *mode = get_irn_mode(irn);
783 ir_node *new_node = new_rd_Add(dbgi, block, l, r, mode);
784 bitinfo const *bi = get_bitinfo(irn);
785 DB((dbg, LEVEL_2, "%+F(%+F, %+F) normalised to Add\n", irn, l, r));
786 set_bitinfo(new_node, bi->z, bi->o);
787 exchange(irn, new_node);
796 static void queue_users(pdeq* const q, ir_node* const n)
798 if (get_irn_mode(n) == mode_X) {
799 /* When the state of a control flow node changes, not only queue its
800 * successor blocks, but also the Phis in these blocks, because the Phis
801 * must reconsider this input path. */
803 foreach_out_edge(n, e) {
804 ir_node* const src = get_edge_src_irn(e);
806 /* should always be a block */
809 for (phi = get_Block_phis(src); phi; phi = get_Phi_next(phi))
815 foreach_out_edge(n, e) {
816 ir_node* const src = get_edge_src_irn(e);
817 if (get_irn_mode(src) == mode_T) {
826 static void clear_links(ir_node *irn, void *env)
829 set_irn_link(irn, NULL);
831 set_Block_phis(irn, NULL);
834 static void build_phi_lists(ir_node *irn, void *env)
838 add_Block_phi(get_nodes_block(irn), irn);
841 static ir_graph_state_t do_fixpoint_vrp(ir_graph* const irg)
844 ir_graph_state_t res = 0;
846 FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp");
847 DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg));
851 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
854 pdeq* const q = new_pdeq();
856 /* We need this extra step because the dom tree does not contain
857 * unreachable blocks in Firm. Moreover build phi list. */
858 irg_walk_anchors(irg, clear_links, build_phi_lists, NULL);
861 ir_tarval* const f = get_tarval_b_false();
862 ir_tarval* const t = get_tarval_b_true();
863 set_bitinfo(get_irg_end_block(irg), t, f); /* Reachable. */
866 /* TODO Improve iteration order. Best is reverse postorder in data flow
867 * direction and respecting loop nesting for fastest convergence. */
868 irg_walk_blkwise_dom_top_down(irg, NULL, first_round, q);
870 while (!pdeq_empty(q)) {
871 ir_node* const n = (ir_node*)pdeq_getl(q);
879 DB((dbg, LEVEL_2, "---> Applying analysis results\n"));
881 irg_walk_graph(irg, NULL, apply_result, &env);
883 if (! env.modified) {
884 res |= IR_GRAPH_STATE_CONSISTENT_DOMINANCE | IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE;
887 ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
889 obstack_free(&obst, NULL);
894 static optdesc_t opt_fpvrp = {
896 IR_GRAPH_STATE_NO_BADS | IR_GRAPH_STATE_NO_UNREACHABLE_CODE | IR_GRAPH_STATE_CONSISTENT_DOMINANCE | IR_GRAPH_STATE_CONSISTENT_OUT_EDGES,
900 void fixpoint_vrp(ir_graph* const irg)
902 perform_irg_optimization(irg, &opt_fpvrp);
905 ir_graph_pass_t *fixpoint_vrp_irg_pass(const char *name)
907 return def_graph_pass(name ? name : "fixpoint_vrp", fixpoint_vrp);