2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Data-flow driven minimal fixpoint value range propagation
9 * @author Christoph Mallon
18 #include "adt/xmalloc.h"
24 #include "irgraph_t.h"
27 #include "iroptimize.h"
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
39 /* Tables of the cleared/set bit lattice
41 * Encoding of the lattice
44 * 01 - impossible state, is zero /and/ one
45 * 10 T top, may be either zero or one
59 * Half adder, half subtractor, and, xor, or, Mux
71 * Full adder, full subtractor
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)
108 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
110 static struct obstack obst;
112 typedef struct bitinfo
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
118 typedef struct environment_t {
119 unsigned modified:1; /**< Set, if the graph was modified. */
122 static bool is_undefined(bitinfo const* const b)
124 return tarval_is_null(b->z) && tarval_is_all_one(b->o);
127 static inline bitinfo* get_bitinfo(ir_node const* const irn)
129 return (bitinfo*)get_irn_link(irn);
132 static int set_bitinfo(ir_node* const irn, ir_tarval* const z, ir_tarval* const o)
134 bitinfo* b = get_bitinfo(irn);
136 b = OALLOCZ(&obst, bitinfo);
137 set_irn_link(irn, b);
138 } else if (z == b->z && o == b->o) {
141 /* Assert monotonicity. */
142 assert(tarval_is_null(tarval_andnot(b->z, z)));
143 assert(tarval_is_null(tarval_andnot(o, b->o)));
147 DB((dbg, LEVEL_3, "%+F: 0:%T 1:%T\n", irn, z, o));
151 static int mode_is_intb(ir_mode const* const m)
153 return mode_is_int(m) || m == mode_b;
156 static int transfer(ir_node* const irn)
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);
164 if (is_Bad(irn)) return 0;
167 bitinfo* const b = get_bitinfo(get_nodes_block(irn));
169 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
171 /* Unreachble blocks might have no bitinfo. */
172 if (b == NULL || b->z == f) {
176 } else switch (get_irn_opcode(irn)) {
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);
187 if ((b->z == t) == get_Proj_proj(irn)) {
193 goto result_unknown_X;
195 } else if (is_Switch(pred)) {
196 ir_node* const selector = get_Switch_selector(pred);
197 bitinfo* const b = get_bitinfo(selector);
201 goto cannot_analyse_X;
203 goto cannot_analyse_X;
209 goto result_unknown_X;
213 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
219 } else if (is_Block(irn)) {
221 int const arity = get_Block_n_cfgpreds(irn);
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) {
234 ir_graph *const irg = get_Block_irg(irn);
236 irn == get_irg_start_block(irg) ||
237 irn == get_irg_end_block(irg);
247 } else if (mode_is_intb(m)) {
248 bitinfo* const b = get_bitinfo(get_nodes_block(irn));
250 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
252 if (b == NULL || b->z == f) {
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);
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);
275 int const arity = get_irn_arity(irn);
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))
286 switch (get_irn_opcode(irn)) {
288 z = o = get_Const_tarval(irn);
293 ir_node* const v = get_Confirm_value(irn);
294 bitinfo* const b = get_bitinfo(v);
295 /* TODO Use bound and relation. */
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);
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;
311 z = tarval_shl(l->z, rz);
312 o = tarval_shl(l->o, rz);
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;
324 z = tarval_shr(l->z, rz);
325 o = tarval_shr(l->o, rz);
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;
337 z = tarval_shrs(l->z, rz);
338 o = tarval_shrs(l->o, rz);
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;
350 z = tarval_rotl(l->z, rz);
351 o = tarval_rotl(l->o, rz);
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);
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.
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);
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);
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);
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);
426 z = tarval_mul(tarval_eor(rzn, tarval_shl_unsigned(rzn, 1)), lzn);
428 o = get_tarval_null(m);
434 bitinfo* const b = get_bitinfo(get_Minus_op(irn));
436 z = o = tarval_neg(b->z);
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);
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);
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));
472 bitinfo* const b = get_bitinfo(get_Not_op(irn));
473 z = tarval_not(b->o);
474 o = tarval_not(b->z);
479 bitinfo* const b = get_bitinfo(get_Conv_op(irn));
480 if (b == NULL) // Happens when converting from float values.
482 z = tarval_convert_to(b->z, m);
483 o = tarval_convert_to(b->o, m);
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));
494 } else if (c->z == f) {
498 z = tarval_or( bf->z, bt->z);
499 o = tarval_and(bf->o, bt->o);
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.
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);
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.
521 } else if (lz == lo && rz == ro && lz == rz) {
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.
533 } else if (lz == lo && rz == ro && lz == rz) {
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))
547 if (tarval_cmp(lz, ro) & relation) {
548 /* Left upper bound is smaller(/equal) than right lower bound. */
550 } else if (!(tarval_cmp(lo, rz) & relation)) {
551 /* Left lower bound is not smaller(/equal) than right upper bound. */
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))
565 if (!(tarval_cmp(lz, ro) & relation)) {
566 /* Left upper bound is not greater(/equal) than right lower bound. */
568 } else if (tarval_cmp(lo, rz) & relation) {
569 /* Left lower bound is greater(/equal) than right upper bound. */
585 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
587 z = get_tarval_all_one(m);
588 o = get_tarval_null(m);
597 return set_bitinfo(irn, z, o);
600 static void first_round(ir_node* const irn, void* const env)
602 pdeq* const q = (pdeq*)env;
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 */
614 static ir_node *make_bad_block(ir_graph *irg)
616 ir_node *bad = new_r_Bad(irg, mode_BB);
617 bitinfo *bb = get_bitinfo(bad);
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. */
626 static void apply_result(ir_node* const irn, void* ctx)
628 environment_t* env = (environment_t*)ctx;
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));
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);
659 b = get_bitinfo(irn);
661 if (is_Const(irn)) return; // It cannot get any better than a Const.
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" : ""));
669 // Replace node with constant value by Const.
671 ir_mode* const m = get_irn_mode(irn);
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);
681 n = new_r_Bad(irg, mode_X);
682 /* Transferring analysis information to the bad node makes it a
683 * candidate for replacement. */
695 switch (get_irn_opcode(irn)) {
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));
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));
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
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);
736 ir_mode *mode = get_irn_mode(irn);
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);
745 DB((dbg, LEVEL_2, "%+F(%+F) is superfluous\n", irn, op));
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));
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));
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
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);
788 static void queue_users(pdeq* const q, ir_node* const n)
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);
797 /* should always be a block */
800 for (phi = get_Block_phis(src); phi; phi = get_Phi_next(phi))
805 foreach_out_edge(n, e) {
806 ir_node* const src = get_edge_src_irn(e);
807 if (get_irn_mode(src) == mode_T) {
816 static void clear_links(ir_node *irn, void *env)
819 set_irn_link(irn, NULL);
821 set_Block_phis(irn, NULL);
824 static void build_phi_lists(ir_node *irn, void *env)
828 add_Block_phi(get_nodes_block(irn), irn);
831 void fixpoint_vrp(ir_graph* const irg)
835 FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp");
836 DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg));
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);
846 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
849 pdeq* const q = new_pdeq();
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);
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. */
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);
865 while (!pdeq_empty(q)) {
866 ir_node* const n = (ir_node*)pdeq_getl(q);
874 DB((dbg, LEVEL_2, "---> Applying analysis results\n"));
876 irg_walk_graph(irg, NULL, apply_result, &env);
878 ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
880 obstack_free(&obst, NULL);
881 confirm_irg_properties(irg,
882 env.modified ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
885 ir_graph_pass_t *fixpoint_vrp_irg_pass(const char *name)
887 return def_graph_pass(name ? name : "fixpoint_vrp", fixpoint_vrp);