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
31 #include "adt/xmalloc.h"
40 #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 tarval* z; // safe zeroes, 0 = bit is zero, 1 = bit maybe is 1
127 tarval* o; // safe ones, 0 = bit maybe is zero, 1 = bit is 1
130 static inline bitinfo* get_bitinfo(ir_node const* const irn)
132 return get_irn_link(irn);
135 static int set_bitinfo(ir_node* const irn, tarval* const z, tarval* const o)
137 bitinfo* b = get_bitinfo(irn);
139 b = OALLOCZ(&obst, bitinfo);
140 set_irn_link(irn, b);
141 } else if (z == b->z && o == b->o) {
146 DB((dbg, LEVEL_3, "%+F: 0:%T 1:%T\n", irn, z, o));
150 static int mode_is_intb(ir_mode const* const m)
152 return mode_is_int(m) || m == mode_b;
155 static int transfer(ir_node* const irn)
157 ir_mode* const m = get_irn_mode(irn);
162 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
163 switch (get_irn_opcode(irn)) {
165 ir_node* const pred = get_Proj_pred(irn);
166 if (is_Start(pred)) {
167 z = get_tarval_b_true();
168 o = get_tarval_b_false();
169 } else if (is_Cond(pred)) {
170 ir_node* const selector = get_Cond_selector(pred);
171 bitinfo* const b = get_bitinfo(selector);
172 tarval* const bz = b->z;
173 tarval* const bo = b->o;
174 if (get_irn_mode(selector) == mode_b) {
176 if ((bz == get_tarval_b_true()) == get_Proj_proj(irn)) {
177 z = o = get_tarval_b_true();
179 z = o = get_tarval_b_false();
182 goto result_unknown_X;
185 long const val = get_Proj_proj(irn);
186 if (val != get_Cond_default_proj(pred)) {
187 tarval* const tv = new_tarval_from_long(val, get_irn_mode(selector));
188 if (!tarval_is_null(tarval_andnot(tv, bz)) ||
189 !tarval_is_null(tarval_andnot(bo, tv))) {
190 // At least one bit differs.
191 z = o = get_tarval_b_false();
192 #if 0 // TODO must handle default Proj
193 } else if (bz == bo && bz == tv) {
194 z = o = get_tarval_b_true();
197 goto result_unknown_X;
200 goto cannot_analyse_X;
204 goto cannot_analyse_X;
210 bitinfo* const b = get_bitinfo(get_nodes_block(irn));
218 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
220 z = get_tarval_b_true();
221 o = get_tarval_b_false();
224 } else if (is_Block(irn)) {
226 int const arity = get_Block_n_cfgpreds(irn);
229 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
230 for (i = 0; i != arity; ++i) {
231 bitinfo* const b = get_bitinfo(get_Block_cfgpred(irn, i));
232 if (b != NULL && b->z == get_tarval_b_true()) {
238 o = get_tarval_b_false();
239 z = reachable || irn == get_irg_start_block(get_irn_irg(irn)) ? get_tarval_b_true() : o;
240 } else if (mode_is_intb(m)) {
241 DB((dbg, LEVEL_3, "transfer %+F\n", irn));
242 switch (get_irn_opcode(irn)) {
244 z = o = get_Const_tarval(irn);
249 bitinfo* const l = get_bitinfo(get_Shl_left(irn));
250 bitinfo* const r = get_bitinfo(get_Shl_right(irn));
251 tarval* const rz = r->z;
253 z = tarval_shl(l->z, rz);
254 o = tarval_shl(l->o, rz);
262 bitinfo* const l = get_bitinfo(get_Shr_left(irn));
263 bitinfo* const r = get_bitinfo(get_Shr_right(irn));
264 tarval* const rz = r->z;
266 z = tarval_shr(l->z, rz);
267 o = tarval_shr(l->o, rz);
275 bitinfo* const l = get_bitinfo(get_Shrs_left(irn));
276 bitinfo* const r = get_bitinfo(get_Shrs_right(irn));
277 tarval* const rz = r->z;
279 z = tarval_shrs(l->z, rz);
280 o = tarval_shrs(l->o, rz);
288 bitinfo* const l = get_bitinfo(get_Rotl_left(irn));
289 bitinfo* const r = get_bitinfo(get_Rotl_right(irn));
290 tarval* const rz = r->z;
292 z = tarval_rotl(l->z, rz);
293 o = tarval_rotl(l->o, rz);
301 bitinfo* const l = get_bitinfo(get_Add_left(irn));
302 bitinfo* const r = get_bitinfo(get_Add_right(irn));
303 tarval* const lz = l->z;
304 tarval* const lo = l->o;
305 tarval* const rz = r->z;
306 tarval* const ro = r->o;
307 if (lz == lo && rz == ro) {
308 z = o = tarval_add(lz, rz);
310 // TODO improve: can only do lower disjoint bits
311 /* Determine where any of the operands has zero bits, i.e. where no
312 * carry out is generated if there is not carry in */
313 tarval* const no_c_in_no_c_out = tarval_and(lz, rz);
314 /* Generate a mask of the lower consecutive zeroes: x | -x. In this
315 * range the addition is disjoint and therefore Add behaves like Or.
317 tarval* const low_zero_mask = tarval_or(no_c_in_no_c_out, tarval_neg(no_c_in_no_c_out));
318 tarval* const low_one_mask = tarval_not(low_zero_mask);
319 z = tarval_or( tarval_or(lz, rz), low_zero_mask);
320 o = tarval_and(tarval_or(lo, ro), low_one_mask);
326 bitinfo* const l = get_bitinfo(get_Sub_left(irn));
327 bitinfo* const r = get_bitinfo(get_Sub_right(irn));
328 if (l != NULL && r != NULL) { // Sub might subtract pointers.
329 tarval* const lz = l->z;
330 tarval* const lo = l->o;
331 tarval* const rz = r->z;
332 tarval* const ro = r->o;
333 if (lz == lo && rz == ro) {
334 z = o = tarval_sub(lz, rz, NULL);
335 } else if (tarval_is_null(tarval_andnot(rz, lo))) {
336 /* Every possible one of the subtrahend is backed by a safe one of the
337 * minuend, i.e. there are no borrows. */
338 // TODO extend no-borrow like carry for Add above
339 z = tarval_andnot(lz, ro);
340 o = tarval_andnot(lo, rz);
351 bitinfo* const l = get_bitinfo(get_Mul_left(irn));
352 bitinfo* const r = get_bitinfo(get_Mul_right(irn));
353 tarval* const lz = l->z;
354 tarval* const lo = l->o;
355 tarval* const rz = r->z;
356 tarval* const ro = r->o;
357 if (lz == lo && rz == ro) {
358 z = o = tarval_mul(lz, rz);
361 // Determine safe lower zeroes: x | -x.
362 tarval* const lzn = tarval_or(lz, tarval_neg(lz));
363 tarval* const rzn = tarval_or(rz, tarval_neg(rz));
364 // Concatenate safe lower zeroes.
365 if (tarval_cmp(lzn, rzn) == pn_Cmp_Lt) {
366 z = tarval_mul(tarval_eor(lzn, tarval_shl(lzn, get_tarval_one(m))), rzn);
368 z = tarval_mul(tarval_eor(rzn, tarval_shl(rzn, get_tarval_one(m))), lzn);
370 o = get_tarval_null(m);
376 bitinfo* const b = get_bitinfo(get_Minus_op(irn));
378 z = o = tarval_neg(b->z);
386 bitinfo* const l = get_bitinfo(get_And_left(irn));
387 bitinfo* const r = get_bitinfo(get_And_right(irn));
388 z = tarval_and(l->z, r->z);
389 o = tarval_and(l->o, r->o);
394 bitinfo* const l = get_bitinfo(get_Or_left(irn));
395 bitinfo* const r = get_bitinfo(get_Or_right(irn));
396 z = tarval_or(l->z, r->z);
397 o = tarval_or(l->o, r->o);
402 bitinfo* const l = get_bitinfo(get_Eor_left(irn));
403 bitinfo* const r = get_bitinfo(get_Eor_right(irn));
404 tarval* const lz = l->z;
405 tarval* const lo = l->o;
406 tarval* const rz = r->z;
407 tarval* const ro = r->o;
408 z = tarval_or(tarval_andnot(lz, ro), tarval_andnot(rz, lo));
409 o = tarval_or(tarval_andnot(ro, lz), tarval_andnot(lo, rz));
414 bitinfo* const b = get_bitinfo(get_Not_op(irn));
415 z = tarval_not(b->o);
416 o = tarval_not(b->z);
421 bitinfo* const b = get_bitinfo(get_Conv_op(irn));
422 if (b == NULL) // Happens when converting from float values.
424 z = tarval_convert_to(b->z, m);
425 o = tarval_convert_to(b->o, m);
430 bitinfo* const f = get_bitinfo(get_Mux_false(irn));
431 bitinfo* const t = get_bitinfo(get_Mux_true(irn));
432 bitinfo* const c = get_bitinfo(get_Mux_sel(irn));
433 if (c->o == get_tarval_b_true()) {
436 } else if (c->z == get_tarval_b_false()) {
440 z = tarval_or( f->z, t->z);
441 z = tarval_and(f->o, t->o);
446 ir_node* const block = get_nodes_block(irn);
447 int const arity = get_Phi_n_preds(irn);
450 z = get_tarval_null(m);
451 o = get_tarval_all_one(m);
452 for (i = 0; i != arity; ++i) {
453 bitinfo* const b_cfg = get_bitinfo(get_Block_cfgpred(block, i));
454 if (b_cfg != NULL && b_cfg->z != get_tarval_b_false()) {
455 bitinfo* const b = get_bitinfo(get_Phi_pred(irn, i));
456 z = tarval_or( z, b->z);
457 o = tarval_and(o, b->o);
464 ir_node* const pred = get_Proj_pred(irn);
465 if (is_Cmp(pred)) { // TODO generalize
466 bitinfo* const l = get_bitinfo(get_Cmp_left(pred));
467 bitinfo* const r = get_bitinfo(get_Cmp_right(pred));
468 if (l == NULL || r == NULL)
469 goto result_unknown; // Cmp compares something we cannot evaluate.
470 switch (get_Proj_proj(irn)) {
472 tarval* const lz = l->z;
473 tarval* const lo = l->o;
474 tarval* const rz = r->z;
475 tarval* const ro = r->o;
476 if (!tarval_is_null(tarval_andnot(ro, lz)) ||
477 !tarval_is_null(tarval_andnot(lo, rz))) {
478 // At least one bit differs.
479 z = o = get_tarval_b_true();
480 } else if (lz == lo && rz == ro && lz == rz) {
481 z = o = get_tarval_b_false();
489 tarval* const lz = l->z;
490 tarval* const lo = l->o;
491 tarval* const rz = r->z;
492 tarval* const ro = r->o;
493 if (!tarval_is_null(tarval_andnot(ro, lz)) ||
494 !tarval_is_null(tarval_andnot(lo, rz))) {
495 // At least one bit differs.
496 z = o = get_tarval_b_false();
497 } else if (lz == lo && rz == ro && lz == rz) {
498 z = o = get_tarval_b_true();
516 DB((dbg, LEVEL_4, "cannot analyse %+F\n", irn));
518 z = get_tarval_all_one(m);
519 o = get_tarval_null(m);
527 return set_bitinfo(irn, z, o);
530 static void first_round(ir_node* const irn, void* const env)
535 if (is_Phi(irn) || is_Block(irn)) {
536 /* Only Phis (and their users) need another round, if we did not have
537 * information about all their inputs in the first round, i.e. in loops. */
538 /* TODO inserts all Phis, should only insert Phis, which did no have all
539 * predecessors available */
544 static void apply_result(ir_node* const irn, void* const env)
546 bitinfo* const b = get_bitinfo(irn);
552 if (is_Const(irn)) return; // It cannot get any better than a Const.
556 // Only display information if we could find out anything about the value.
557 DEBUG_ONLY(if (!tarval_is_all_one(z) || !tarval_is_null(o)))
558 DB((dbg, LEVEL_2, "%+F: 0:%T 1:%T%s\n", irn, z, o, z == o ? " --- constant" : ""));
560 // Replace node with constant value by Const.
562 ir_mode* const m = get_irn_mode(irn);
564 if (mode_is_intb(m)) {
566 } else if (m == mode_X) {
567 ir_node* const block = get_nodes_block(irn);
568 ir_graph* const irg = get_Block_irg(block);
569 if (z == get_tarval_b_true()) {
570 // Might produce an endless loop, so keep the block.
571 add_End_keepalive(get_irg_end(irg), block);
572 n = new_r_Jmp(block);
575 /* Transferring analysis information to the bad node makes it a
576 * candidate for replacement. */
587 switch (get_irn_opcode(irn)) {
589 ir_node* const l = get_And_left(irn);
590 ir_node* const r = get_And_right(irn);
591 bitinfo const* const bl = get_bitinfo(l);
592 bitinfo const* const br = get_bitinfo(r);
593 if (bl->z == bl->o) {
594 if (tarval_is_null(tarval_andnot(br->z, bl->z))) {
595 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
598 } else if (br->z == br->o) {
599 if (tarval_is_null(tarval_andnot(bl->z, br->z))) {
600 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
608 ir_node* const l = get_Or_left(irn);
609 ir_node* const r = get_Or_right(irn);
610 bitinfo const* const bl = get_bitinfo(l);
611 bitinfo const* const br = get_bitinfo(r);
612 if (bl->z == bl->o) {
613 if (tarval_is_null(tarval_andnot(bl->o, br->o))) {
614 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
617 } else if (br->z == br->o) {
618 if (tarval_is_null(tarval_andnot(br->o, bl->o))) {
619 DB((dbg, LEVEL_2, "%+F(%+F, %+F) is superfluous\n", irn, l, r));
628 static void queue_users(pdeq* const q, ir_node* const n)
630 if (get_irn_mode(n) == mode_X) {
631 /* When the state of a control flow node changes, not only queue its
632 * successor blocks, but also the Phis in these blocks, because the Phis
633 * must reconsider this input path. */
635 foreach_out_edge(n, e) {
636 ir_node* const src = get_edge_src_irn(e);
637 ir_edge_t const* src_e;
639 foreach_out_edge(src, src_e) {
640 ir_node* const src_src = get_edge_src_irn(src_e);
642 pdeq_putr(q, src_src);
647 foreach_out_edge(n, e) {
648 ir_node* const src = get_edge_src_irn(e);
649 if (get_irn_mode(src) == mode_T) {
658 void fixpoint_vrp(ir_graph* const irg)
660 FIRM_DBG_REGISTER(dbg, "firm.opt.fp-vrp");
661 DB((dbg, LEVEL_1, "===> Performing constant propagation on %+F\n", irg));
668 { pdeq* const q = new_pdeq();
670 /* TODO Improve iteration order. Best is reverse postorder in data flow
671 * direction and respecting loop nesting for fastest convergence. */
672 irg_walk_blkwise_dom_top_down(irg, firm_clear_link, first_round, q);
674 while (!pdeq_empty(q)) {
675 ir_node* const n = pdeq_getl(q);
683 DB((dbg, LEVEL_2, "---> Applying analysis results\n"));
684 irg_walk_graph(irg, NULL, apply_result, NULL);
686 obstack_free(&obst, NULL);
689 ir_graph_pass_t *fixpoint_vrp_irg_pass(const char *name)
691 return def_graph_pass(name ? name : "fixpoint_vrp", fixpoint_vrp);