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
30 #include "adt/xmalloc.h"
39 #include "iroptimize.h"
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
51 /* Tables of the cleared/set bit lattice
53 * Encoding of the lattice
56 * 01 - impossible state, is zero /and/ one
57 * 10 T top, may be either zero or one
71 * Half adder, half subtractor, and, xor, or, Mux
83 * Full adder, full subtractor
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)
120 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
122 static struct obstack obst;
124 typedef struct bitinfo
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
130 typedef struct environment_t {
131 unsigned modified:1; /**< Set, if the graph was modified. */
134 static inline bitinfo* get_bitinfo(ir_node const* const irn)
136 return (bitinfo*)get_irn_link(irn);
139 static int set_bitinfo(ir_node* const irn, ir_tarval* const z, ir_tarval* const o)
141 bitinfo* b = get_bitinfo(irn);
143 b = OALLOCZ(&obst, bitinfo);
144 set_irn_link(irn, b);
145 } else if (z == b->z && o == b->o) {
150 DB((dbg, LEVEL_3, "%+F: 0:%T 1:%T\n", irn, z, o));
154 static int mode_is_intb(ir_mode const* const m)
156 return mode_is_int(m) || m == mode_b;
159 static int transfer(ir_node* const irn)
161 ir_mode* const m = get_irn_mode(irn);
166 ir_tarval* const f = get_tarval_b_false();
167 bitinfo* const b = get_bitinfo(get_nodes_block(irn));
169 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
171 if (b->z == f && b->o == f) {
174 } else switch (get_irn_opcode(irn)) {
176 ir_node* const pred = get_Proj_pred(irn);
177 if (is_Start(pred)) {
178 goto result_unknown_X;
179 } else if (is_Cond(pred)) {
180 ir_node* const selector = get_Cond_selector(pred);
181 bitinfo* const b = get_bitinfo(selector);
182 ir_tarval* const bz = b->z;
183 ir_tarval* const bo = b->o;
184 if (get_irn_mode(selector) == mode_b) {
186 if ((bz == get_tarval_b_true()) == get_Proj_proj(irn)) {
187 z = o = get_tarval_b_true();
189 z = o = get_tarval_b_false();
192 goto result_unknown_X;
195 long const val = get_Proj_proj(irn);
196 if (val != get_Cond_default_proj(pred)) {
197 ir_tarval* const tv = new_tarval_from_long(val, get_irn_mode(selector));
198 if (!tarval_is_null(tarval_andnot(tv, bz)) ||
199 !tarval_is_null(tarval_andnot(bo, tv))) {
200 // At least one bit differs.
201 z = o = get_tarval_b_false();
202 #if 0 // TODO must handle default Proj
203 } else if (bz == bo && bz == tv) {
204 z = o = get_tarval_b_true();
207 goto result_unknown_X;
210 goto cannot_analyse_X;
214 goto cannot_analyse_X;
220 goto result_unknown_X;
224 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
226 z = get_tarval_b_true();
227 o = get_tarval_b_false();
230 } else if (is_Block(irn)) {
232 int const arity = get_Block_n_cfgpreds(irn);
235 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
236 for (i = 0; i != arity; ++i) {
237 bitinfo* const b = get_bitinfo(get_Block_cfgpred(irn, i));
238 if (b != NULL && b->z == get_tarval_b_true()) {
245 ir_graph *const irg = get_Block_irg(irn);
247 irn == get_irg_start_block(irg) ||
248 irn == get_irg_end_block(irg);
251 o = get_tarval_b_false();
252 z = reachable ? get_tarval_b_true() : o;
253 } else if (mode_is_intb(m)) {
254 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
255 switch (get_irn_opcode(irn)) {
257 z = o = get_Const_tarval(irn);
262 ir_node* const v = get_Confirm_value(irn);
263 bitinfo* const b = get_bitinfo(v);
264 /* TODO Use bound and relation. */
271 bitinfo* const l = get_bitinfo(get_Shl_left(irn));
272 bitinfo* const r = get_bitinfo(get_Shl_right(irn));
273 ir_tarval* const rz = r->z;
275 z = tarval_shl(l->z, rz);
276 o = tarval_shl(l->o, rz);
284 bitinfo* const l = get_bitinfo(get_Shr_left(irn));
285 bitinfo* const r = get_bitinfo(get_Shr_right(irn));
286 ir_tarval* const rz = r->z;
288 z = tarval_shr(l->z, rz);
289 o = tarval_shr(l->o, rz);
297 bitinfo* const l = get_bitinfo(get_Shrs_left(irn));
298 bitinfo* const r = get_bitinfo(get_Shrs_right(irn));
299 ir_tarval* const rz = r->z;
301 z = tarval_shrs(l->z, rz);
302 o = tarval_shrs(l->o, rz);
310 bitinfo* const l = get_bitinfo(get_Rotl_left(irn));
311 bitinfo* const r = get_bitinfo(get_Rotl_right(irn));
312 ir_tarval* const rz = r->z;
314 z = tarval_rotl(l->z, rz);
315 o = tarval_rotl(l->o, rz);
323 bitinfo* const l = get_bitinfo(get_Add_left(irn));
324 bitinfo* const r = get_bitinfo(get_Add_right(irn));
325 ir_tarval* const lz = l->z;
326 ir_tarval* const lo = l->o;
327 ir_tarval* const rz = r->z;
328 ir_tarval* const ro = r->o;
329 if (lz == lo && rz == ro) {
330 z = o = tarval_add(lz, rz);
332 // TODO improve: can only do lower disjoint bits
333 /* Determine where any of the operands has zero bits, i.e. where no
334 * carry out is generated if there is not carry in */
335 ir_tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
336 /* Generate a mask of the lower consecutive zeroes: x | -x. In this
337 * range the addition is disjoint and therefore Add behaves like Or.
339 ir_tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
340 ir_tarval* const low_one_mask = tarval_not(low_zero_mask);
341 z = tarval_or( tarval_or(lz, rz), low_zero_mask);
342 o = tarval_and(tarval_or(lo, ro), low_one_mask);
348 bitinfo* const l = get_bitinfo(get_Sub_left(irn));
349 bitinfo* const r = get_bitinfo(get_Sub_right(irn));
350 if (l != NULL && r != NULL) { // Sub might subtract pointers.
351 ir_tarval* const lz = l->z;
352 ir_tarval* const lo = l->o;
353 ir_tarval* const rz = r->z;
354 ir_tarval* const ro = r->o;
355 if (lz == lo && rz == ro) {
356 z = o = tarval_sub(lz, rz, NULL);
357 } else if (tarval_is_null(tarval_andnot(rz, lo))) {
358 /* Every possible one of the subtrahend is backed by a safe one of the
359 * minuend, i.e. there are no borrows. */
360 // TODO extend no-borrow like carry for Add above
361 z = tarval_andnot(lz, ro);
362 o = tarval_andnot(lo, rz);
373 bitinfo* const l = get_bitinfo(get_Mul_left(irn));
374 bitinfo* const r = get_bitinfo(get_Mul_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_mul(lz, rz);
383 // Determine safe lower zeroes: x | -x.
384 ir_tarval* const lzn = tarval_or(lz, tarval_neg(lz));
385 ir_tarval* const rzn = tarval_or(rz, tarval_neg(rz));
386 // Concatenate safe lower zeroes.
387 if (tarval_cmp(lzn, rzn) == ir_relation_less) {
388 z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn);
390 z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), lzn);
392 o = get_tarval_null(m);
398 bitinfo* const b = get_bitinfo(get_Minus_op(irn));
400 z = o = tarval_neg(b->z);
408 bitinfo* const l = get_bitinfo(get_And_left(irn));
409 bitinfo* const r = get_bitinfo(get_And_right(irn));
410 z = tarval_and(l->z, r->z);
411 o = tarval_and(l->o, r->o);
416 bitinfo* const l = get_bitinfo(get_Or_left(irn));
417 bitinfo* const r = get_bitinfo(get_Or_right(irn));
418 z = tarval_or(l->z, r->z);
419 o = tarval_or(l->o, r->o);
424 bitinfo* const l = get_bitinfo(get_Eor_left(irn));
425 bitinfo* const r = get_bitinfo(get_Eor_right(irn));
426 ir_tarval* const lz = l->z;
427 ir_tarval* const lo = l->o;
428 ir_tarval* const rz = r->z;
429 ir_tarval* const ro = r->o;
430 z = tarval_or(tarval_andnot(lz, ro), tarval_andnot(rz, lo));
431 o = tarval_or(tarval_andnot(ro, lz), tarval_andnot(lo, rz));
436 bitinfo* const b = get_bitinfo(get_Not_op(irn));
437 z = tarval_not(b->o);
438 o = tarval_not(b->z);
443 bitinfo* const b = get_bitinfo(get_Conv_op(irn));
444 if (b == NULL) // Happens when converting from float values.
446 z = tarval_convert_to(b->z, m);
447 o = tarval_convert_to(b->o, m);
452 bitinfo* const f = get_bitinfo(get_Mux_false(irn));
453 bitinfo* const t = get_bitinfo(get_Mux_true(irn));
454 bitinfo* const c = get_bitinfo(get_Mux_sel(irn));
455 if (c->o == get_tarval_b_true()) {
458 } else if (c->z == get_tarval_b_false()) {
462 z = tarval_or( f->z, t->z);
463 o = tarval_and(f->o, t->o);
469 ir_node* const block = get_nodes_block(irn);
470 int const arity = get_Phi_n_preds(irn);
473 z = get_tarval_null(m);
474 o = get_tarval_all_one(m);
475 for (i = 0; i != arity; ++i) {
476 bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
477 if (b_cfg != NULL && b_cfg->z != get_tarval_b_false()) {
478 bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
479 z = tarval_or( z, b->z);
480 o = tarval_and(o, b->o);
487 bitinfo* const l = get_bitinfo(get_Cmp_left(irn));
488 bitinfo* const r = get_bitinfo(get_Cmp_right(irn));
489 if (l == NULL || r == NULL) {
490 goto result_unknown; // Cmp compares something we cannot evaluate.
492 ir_tarval* const lz = l->z;
493 ir_tarval* const lo = l->o;
494 ir_tarval* const rz = r->z;
495 ir_tarval* const ro = r->o;
496 ir_relation const relation = get_Cmp_relation(irn);
498 case ir_relation_less_greater:
499 if (!tarval_is_null(tarval_andnot(ro, lz)) ||
500 !tarval_is_null(tarval_andnot(lo, rz))) {
501 // At least one bit differs.
502 z = o = get_tarval_b_true();
503 } else if (lz == lo && rz == ro && lz == rz) {
504 z = o = get_tarval_b_false();
510 case ir_relation_equal:
511 if (!tarval_is_null(tarval_andnot(ro, lz)) ||
512 !tarval_is_null(tarval_andnot(lo, rz))) {
513 // At least one bit differs.
514 z = o = get_tarval_b_false();
515 } else if (lz == lo && rz == ro && lz == rz) {
516 z = o = get_tarval_b_true();
522 case ir_relation_less_equal:
523 case ir_relation_less:
524 /* TODO handle negative values */
525 if (tarval_is_negative(lz) || tarval_is_negative(lo) ||
526 tarval_is_negative(rz) || tarval_is_negative(ro))
529 if (tarval_cmp(lz, ro) & relation) {
530 /* Left upper bound is smaller(/equal) than right lower bound. */
531 z = o = get_tarval_b_true();
532 } else if (!(tarval_cmp(lo, rz) & relation)) {
533 /* Left lower bound is not smaller(/equal) than right upper bound. */
534 z = o = get_tarval_b_false();
540 case ir_relation_greater_equal:
541 case ir_relation_greater:
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 not greater(/equal) than right lower bound. */
549 z = o = get_tarval_b_false();
550 } else if (tarval_cmp(lo, rz) & relation) {
551 /* Left lower bound is greater(/equal) than right upper bound. */
552 z = o = get_tarval_b_true();
567 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
569 z = get_tarval_all_one(m);
570 o = get_tarval_null(m);
578 return set_bitinfo(irn, z, o);
581 static void first_round(ir_node* const irn, void* const env)
583 pdeq* const q = (pdeq*)env;
586 if (is_Phi(irn) || is_Block(irn)) {
587 /* Only Phis (and their users) need another round, if we did not have
588 * information about all their inputs in the first round, i.e. in loops. */
589 /* TODO inserts all Phis, should only insert Phis, which did no have all
590 * predecessors available */
595 static void apply_result(ir_node* const irn, void* ctx)
597 environment_t* env = (environment_t*)ctx;
604 bitinfo* const block_b = get_bitinfo(irn);
605 /* Trivially unreachable blocks have no info. */
606 if (block_b == NULL || block_b->z == get_tarval_b_false()) {
607 exchange(irn, get_irg_bad(get_Block_irg(irn)));
613 /* Unreachable blocks are replaced before the nodes in them. */
614 block = get_nodes_block(irn);
616 exchange(irn, block);
621 b = get_bitinfo(irn);
623 if (is_Const(irn)) return; // It cannot get any better than a Const.
627 // Only display information if we could find out anything about the value.
628 DEBUG_ONLY(if (!tarval_is_all_one(z) || !tarval_is_null(o)))
629 DB((dbg, LEVEL_2, "%+F: 0:%T 1:%T%s\n", irn, z, o, z == o ? " --- constant" : ""));
631 // Replace node with constant value by Const.
633 ir_mode* const m = get_irn_mode(irn);
635 if (mode_is_intb(m)) {
636 ir_graph *irg = get_irn_irg(irn);
637 n = new_r_Const(irg, z);
638 } else if (m == mode_X) {
639 ir_graph* const irg = get_Block_irg(block);
640 if (z == get_tarval_b_true()) {
641 // Might produce an endless loop, so keep the block.
642 add_End_keepalive(get_irg_end(irg), block);
643 n = new_r_Jmp(block);
646 /* Transferring analysis information to the bad node makes it a
647 * candidate for replacement. */
659 switch (get_irn_opcode(irn)) {
661 ir_node* const l = get_And_left(irn);
662 ir_node* const r = get_And_right(irn);
663 bitinfo const* const bl = get_bitinfo(l);
664 bitinfo const* const br = get_bitinfo(r);
665 if (bl->z == bl->o) {
666 if (tarval_is_null(tarval_andnot(br->z, bl->z))) {
667 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
671 } else if (br->z == br->o) {
672 if (tarval_is_null(tarval_andnot(bl->z, br->z))) {
673 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
682 ir_node* const l = get_Or_left(irn);
683 ir_node* const r = get_Or_right(irn);
684 bitinfo const* const bl = get_bitinfo(l);
685 bitinfo const* const br = get_bitinfo(r);
686 if (bl->z == bl->o) {
687 if (tarval_is_null(tarval_andnot(bl->o, br->o))) {
688 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
692 } else if (br->z == br->o) {
693 if (tarval_is_null(tarval_andnot(br->o, bl->o))) {
694 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
704 static void queue_users(pdeq* const q, ir_node* const n)
706 if (get_irn_mode(n) == mode_X) {
707 /* When the state of a control flow node changes, not only queue its
708 * successor blocks, but also the Phis in these blocks, because the Phis
709 * must reconsider this input path. */
711 foreach_out_edge(n, e) {
712 ir_node* const src = get_edge_src_irn(e);
714 /* should always be a block */
717 for (phi = get_Block_phis(src); phi; phi = get_Phi_next(phi))
723 foreach_out_edge(n, e) {
724 ir_node* const src = get_edge_src_irn(e);
725 if (get_irn_mode(src) == mode_T) {
734 static void clear_links(ir_node *irn, void *env)
737 set_irn_link(irn, NULL);
739 set_Block_phis(irn, NULL);
742 static void build_phi_lists(ir_node *irn, void *env)
746 add_Block_phi(get_nodes_block(irn), irn);
749 void fixpoint_vrp(ir_graph* const irg)
753 FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp");
754 DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg));
758 /* HACK: to avoid finding dead code */
759 edges_deactivate(irg);
765 ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
768 pdeq* const q = new_pdeq();
770 /* We need this extra step because the dom tree does not contain unreachable
771 blocks in Firm. Moreover build phi list. */
772 irg_walk_anchors(irg, clear_links, build_phi_lists, NULL);
774 /* TODO Improve iteration order. Best is reverse postorder in data flow
775 * direction and respecting loop nesting for fastest convergence. */
776 irg_walk_blkwise_dom_top_down(irg, NULL, first_round, q);
778 while (!pdeq_empty(q)) {
779 ir_node* const n = (ir_node*)pdeq_getl(q);
787 DB((dbg, LEVEL_2, "---> Applying analysis results\n"));
789 irg_walk_graph(irg, NULL, apply_result, &env);
792 /* control flow might changed */
793 set_irg_outs_inconsistent(irg);
794 set_irg_extblk_inconsistent(irg);
795 set_irg_doms_inconsistent(irg);
796 set_irg_loopinfo_inconsistent(irg);
797 set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
800 ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_PHI_LIST);
802 obstack_free(&obst, NULL);
805 ir_graph_pass_t *fixpoint_vrp_irg_pass(const char *name)
807 return def_graph_pass(name ? name : "fixpoint_vrp", fixpoint_vrp);