2 * Copyright (C) 1995-2008 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 Reassociation
23 * @author Michael Beck
32 #include "irgraph_t.h"
36 #include "iropt_dbg.h"
39 #include "reassoc_t.h"
45 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
47 typedef struct _walker_t {
48 int changes; /**< set, if a reassociation take place */
49 waitq *wq; /**< a wait queue */
53 NO_CONSTANT = 0, /**< node is not constant */
54 REAL_CONSTANT = 1, /**< node is a Const that is suitable for constant folding */
55 REGION_CONST = 4 /**< node is a constant expression in the current context,
56 use 4 here to simplify implementation of get_comm_Binop_ops() */
60 * returns whether a node is constant ie is a constant or
61 * is loop invariant (called region constant)
63 * @param n the node to be checked for constant
64 * @param block a block that might be in a loop
66 static const_class_t get_const_class(ir_node *n, ir_node *block)
68 ir_op *op = get_irn_op(n);
73 /* although SymConst's are of course real constant, we cannot
74 fold them, so handle them like region constants */
75 if (op == op_SymConst)
79 * Beware: Bad nodes are always loop-invariant, but
80 * cannot handled in later code, so filter them here.
82 if (! is_Bad(n) && is_loop_invariant(n, block))
86 } /* get_const_class */
89 * returns the operands of a commutative bin-op, if one operand is
90 * a region constant, it is returned as the second one.
92 * Beware: Real constants must be returned with higher priority than
93 * region constants, because they might be folded.
95 static void get_comm_Binop_ops(ir_node *binop, ir_node **a, ir_node **c)
97 ir_node *op_a = get_binop_left(binop);
98 ir_node *op_b = get_binop_right(binop);
99 ir_node *block = get_nodes_block(binop);
100 int class_a = get_const_class(op_a, block);
101 int class_b = get_const_class(op_b, block);
103 assert(is_op_commutative(get_irn_op(binop)));
105 switch (class_a + 2*class_b) {
106 case REAL_CONSTANT + 2*REAL_CONSTANT:
107 /* if both are constants, one might be a
108 * pointer constant like NULL, return the other
110 if (mode_is_reference(get_irn_mode(op_a))) {
118 case REAL_CONSTANT + 2*NO_CONSTANT:
119 case REAL_CONSTANT + 2*REGION_CONST:
120 case REGION_CONST + 2*NO_CONSTANT:
129 } /* get_comm_Binop_ops */
132 * reassociate a Sub: x - c = x + (-c)
134 static int reassoc_Sub(ir_node **in)
137 ir_node *right = get_Sub_right(n);
138 ir_mode *rmode = get_irn_mode(right);
141 /* cannot handle SubIs(P, P) */
142 if (mode_is_reference(rmode))
145 block = get_nodes_block(n);
148 * convert x - c => x + (-c)
150 if (get_const_class(right, block) == REAL_CONSTANT) {
151 ir_node *left = get_Sub_left(n);
156 switch (get_const_class(left, block)) {
158 irn = optimize_in_place(n);
168 /* already constant, nothing to do */
172 mode = get_irn_mode(n);
173 dbi = get_irn_dbg_info(n);
175 /* Beware of SubP(P, Is) */
176 irn = new_rd_Minus(dbi, current_ir_graph, block, right, rmode);
177 irn = new_rd_Add(dbi, current_ir_graph, block, left, irn, mode);
179 DBG((dbg, LEVEL_5, "Applied: %n - %n => %n + (-%n)\n",
180 get_Sub_left(n), right, get_Sub_left(n), right));
193 /** Retrieve a mode from the operands. We need this, because
194 * Add and Sub are allowed to operate on (P, Is)
196 static ir_mode *get_mode_from_ops(ir_node *op1, ir_node *op2)
200 m1 = get_irn_mode(op1);
201 if (mode_is_reference(m1))
204 m2 = get_irn_mode(op2);
205 if (mode_is_reference(m2))
211 } /* get_mode_from_ops */
214 * reassociate a commutative Binop
216 * BEWARE: this rule leads to a potential loop, if
217 * two operands are region constants and the third is a
218 * constant, so avoid this situation.
220 static int reassoc_commutative(ir_node **node)
223 ir_op *op = get_irn_op(n);
224 ir_node *block = get_nodes_block(n);
227 get_comm_Binop_ops(n, &t1, &c1);
229 if (get_irn_op(t1) == op) {
231 const_class_t c_c1, c_c2, c_t2;
233 get_comm_Binop_ops(t1, &t2, &c2);
235 /* do not optimize Bad nodes, will fail later */
239 c_c1 = get_const_class(c1, block);
240 c_c2 = get_const_class(c2, block);
241 c_t2 = get_const_class(t2, block);
243 if ( ((c_c1 > NO_CONSTANT) & (c_t2 > NO_CONSTANT)) &&
244 ((((c_c1 ^ c_c2 ^ c_t2) & REGION_CONST) == 0) || ((c_c1 & c_c2 & c_t2) == REGION_CONST)) ) {
245 /* All three are constant and either all are constant expressions or two of them are:
246 * then applying this rule would lead into a cycle
248 * Note that if t2 is a constant so is c2 hence we save one test.
253 if ((c_c1 != NO_CONSTANT) /* & (c_c2 != NO_CONSTANT) */) {
254 /* handles rules R7, R8, R9, R10:
255 * convert c1 .OP. (c2 .OP. x) => x .OP. (c1 .OP. c2)
257 ir_node *irn, *in[2];
258 ir_mode *mode, *mode_c1 = get_irn_mode(c1), *mode_c2 = get_irn_mode(c2);
260 /* It might happen, that c1 and c2 have different modes, for instance Is and Iu.
263 if (mode_c1 != mode_c2) {
264 if (mode_is_int(mode_c1) && mode_is_int(mode_c2)) {
265 /* get the bigger one */
266 if (get_mode_size_bits(mode_c1) > get_mode_size_bits(mode_c2))
267 c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
268 else if (get_mode_size_bits(mode_c1) < get_mode_size_bits(mode_c2))
269 c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
271 /* Try to cast the real const */
272 if (c_c1 == REAL_CONSTANT)
273 c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
275 c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
283 mode = get_mode_from_ops(in[0], in[1]);
284 in[1] = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
287 mode = get_mode_from_ops(in[0], in[1]);
288 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
290 DBG((dbg, LEVEL_5, "Applied: %n .%s. (%n .%s. %n) => %n .%s. (%n .%s. %n)\n",
291 c1, get_irn_opname(n), c2, get_irn_opname(n), t2,
292 t2, get_irn_opname(n), c1, get_irn_opname(n), c2));
294 * In some rare cases it can really happen that we get the same node back.
295 * This might be happen in dead loops, were the Phi nodes are already gone away.
306 } /* reassoc_commutative */
308 #define reassoc_Add reassoc_commutative
309 #define reassoc_And reassoc_commutative
310 #define reassoc_Or reassoc_commutative
311 #define reassoc_Eor reassoc_commutative
314 * Reassociate using commutative law for Mul and distributive law for Mul and Add/Sub:
316 static int reassoc_Mul(ir_node **node)
319 ir_node *add_sub, *c;
322 if (reassoc_commutative(&n))
325 get_comm_Binop_ops(n, &add_sub, &c);
326 op = get_irn_op(add_sub);
328 /* handles rules R11, R12, R13, R14, R15, R16, R17, R18, R19, R20 */
329 if (op == op_Add || op == op_Sub) {
330 ir_mode *mode = get_irn_mode(n);
331 ir_node *irn, *block, *t1, *t2, *in[2];
333 block = get_nodes_block(n);
334 t1 = get_binop_left(add_sub);
335 t2 = get_binop_right(add_sub);
337 /* we can only multiplication rules on integer arithmetic */
338 if (mode_is_int(get_irn_mode(t1)) && mode_is_int(get_irn_mode(t2))) {
339 in[0] = new_rd_Mul(NULL, current_ir_graph, block, c, t1, mode);
340 in[1] = new_rd_Mul(NULL, current_ir_graph, block, c, t2, mode);
342 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
344 /* In some cases it might happen that the new irn is equal the old one, for
346 * (x - 1) * y == x * y - y
347 * will be transformed back by simpler optimization
348 * We could switch simple optimizations off, but this only happens iff y
349 * is a loop-invariant expression and that it is not clear if the new form
351 * So, we let the old one.
354 DBG((dbg, LEVEL_5, "Applied: (%n .%s. %n) %n %n => (%n %n %n) .%s. (%n %n %n)\n",
355 t1, get_op_name(op), t2, n, c, t1, n, c, get_op_name(op), t2, n, c));
367 * Reassociate Shl. We transform Shl(x, const) into Mul's if possible.
369 static int reassoc_Shl(ir_node **node) {
371 ir_node *c = get_Shl_right(n);
372 ir_node *x, *blk, *irn;
380 mode = get_irn_mode(x);
382 tv = get_mode_one(mode);
383 tv = tarval_shl(tv, get_Const_tarval(c));
385 if (tv == tarval_bad)
388 blk = get_nodes_block(n);
389 c = new_r_Const(current_ir_graph, blk, mode, tv);
390 irn = new_rd_Mul(get_irn_dbg_info(n), current_ir_graph, blk, x, c, mode);
401 * The walker for the reassociation.
403 static void wq_walker(ir_node *n, void *env)
405 walker_t *wenv = env;
407 set_irn_link(n, NULL);
408 if (is_no_Block(n)) {
409 ir_node *blk = get_nodes_block(n);
411 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
412 /* We are in a dead block, do not optimize or we may fall into an endless
413 loop. We check this here instead of requiring that all dead blocks are removed
414 which or cf_opt do not guarantee yet. */
417 waitq_put(wenv->wq, n);
418 set_irn_link(n, wenv->wq);
423 * The walker for the reassociation.
425 static void do_reassociation(walker_t *wenv)
431 while (! waitq_empty(wenv->wq)) {
432 n = waitq_get(wenv->wq);
433 set_irn_link(n, NULL);
435 blk = get_nodes_block(n);
436 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
437 /* We are in a dead block, do not optimize or we may fall into an endless
438 loop. We check this here instead of requiring that all dead blocks are removed
439 which or cf_opt do not guarantee yet. */
446 /* reassociation must run until a fixpoint is reached. */
449 ir_op *op = get_irn_op(n);
450 ir_mode *mode = get_irn_mode(n);
454 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
455 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
458 if (op->ops.reassociate) {
459 res = op->ops.reassociate(&n);
466 wenv->changes |= changed;
469 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
470 ir_node *pred = get_irn_n(n, i);
472 if (get_irn_link(pred) != wenv->wq) {
473 waitq_put(wenv->wq, pred);
474 set_irn_link(pred, wenv->wq);
479 } /* do_reassociation */
482 * Returns the earliest were a,b are available.
483 * Note that we know that a, b both dominate
484 * the block of the previous operation, so one must dominate the other.
486 * If the earliest block is the start block, return curr_blk instead
488 static ir_node *earliest_block(ir_node *a, ir_node *b, ir_node *curr_blk) {
489 ir_node *blk_a = get_nodes_block(a);
490 ir_node *blk_b = get_nodes_block(b);
493 /* if blk_a != blk_b, one must dominate the other */
494 if (block_dominates(blk_a, blk_b))
498 if (res == get_irg_start_block(current_ir_graph))
501 } /* earliest_block */
504 * Checks whether a node is a Constant expression.
505 * The following trees are constant expressions:
507 * Const, SymConst, Const + SymConst
509 * Handling SymConsts as const might be not a good idea for all
512 static int is_constant_expr(ir_node *irn) {
515 switch (get_irn_opcode(irn)) {
520 op = get_irn_op(get_Add_left(irn));
521 if (op != op_Const && op != op_SymConst)
523 op = get_irn_op(get_Add_right(irn));
524 if (op != op_Const && op != op_SymConst)
530 } /* is_constant_expr */
533 * Apply distributive Law for Mul and Add/Sub
535 static int reverse_rule_distributive(ir_node **node) {
537 ir_node *left = get_binop_left(n);
538 ir_node *right = get_binop_right(n);
539 ir_node *x, *blk, *curr_blk;
540 ir_node *a, *b, *irn;
545 op = get_irn_op(left);
546 if (op != get_irn_op(right))
550 x = get_Shl_right(left);
552 if (x == get_Shl_right(right)) {
553 /* (a << x) +/- (b << x) ==> (a +/- b) << x */
554 a = get_Shl_left(left);
555 b = get_Shl_left(right);
558 } else if (op == op_Mul) {
559 x = get_Mul_left(left);
561 if (x == get_Mul_left(right)) {
562 /* (x * a) +/- (x * b) ==> (a +/- b) * x */
563 a = get_Mul_right(left);
564 b = get_Mul_right(right);
566 } else if (x == get_Mul_right(right)) {
567 /* (x * a) +/- (b * x) ==> (a +/- b) * x */
568 a = get_Mul_right(left);
569 b = get_Mul_left(right);
573 x = get_Mul_right(left);
575 if (x == get_Mul_right(right)) {
576 /* (a * x) +/- (b * x) ==> (a +/- b) * x */
577 a = get_Mul_left(left);
578 b = get_Mul_left(right);
580 } else if (x == get_Mul_left(right)) {
581 /* (a * x) +/- (x * b) ==> (a +/- b) * x */
582 a = get_Mul_left(left);
583 b = get_Mul_right(right);
590 curr_blk = get_nodes_block(n);
592 blk = earliest_block(a, b, curr_blk);
594 dbg = get_irn_dbg_info(n);
595 mode = get_irn_mode(n);
598 irn = new_rd_Add(dbg, current_ir_graph, blk, a, b, mode);
600 irn = new_rd_Sub(dbg, current_ir_graph, blk, a, b, mode);
602 blk = earliest_block(irn, x, curr_blk);
605 irn = new_rd_Mul(dbg, current_ir_graph, blk, irn, x, mode);
607 irn = new_rd_Shl(dbg, current_ir_graph, blk, irn, x, mode);
612 } /* reverse_rule_distributive */
615 * Move Constants towards the root.
617 static int move_consts_up(ir_node **node) {
620 ir_node *l, *r, *a, *b, *c, *blk, *irn, *in[2];
621 ir_mode *mode, *ma, *mb;
624 l = get_binop_left(n);
625 r = get_binop_right(n);
627 /* check if one is already a constant expression */
628 if (is_constant_expr(l) || is_constant_expr(r))
631 dbg = get_irn_dbg_info(n);
633 if (get_irn_op(l) == op) {
634 /* (a .op. b) .op. r */
635 a = get_binop_left(l);
636 b = get_binop_right(l);
638 if (is_constant_expr(a)) {
639 /* (C .op. b) .op. r ==> (r .op. b) .op. C */
642 blk = get_nodes_block(l);
643 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
645 } else if (is_constant_expr(b)) {
646 /* (a .op. C) .op. r ==> (a .op. r) .op. C */
649 blk = get_nodes_block(l);
650 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
653 } else if (get_irn_op(r) == op) {
654 /* l .op. (a .op. b) */
655 a = get_binop_left(r);
656 b = get_binop_right(r);
658 if (is_constant_expr(a)) {
659 /* l .op. (C .op. b) ==> (l .op. b) .op. C */
662 blk = get_nodes_block(r);
663 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
665 } else if (is_constant_expr(b)) {
666 /* l .op. (a .op. C) ==> (a .op. l) .op. C */
669 blk = get_nodes_block(r);
670 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
677 /* In some cases a and b might be both of different integer mode, and c a SymConst.
678 * in that case we could either
679 * 1.) cast into unsigned mode
681 * we implement the second here
683 ma = get_irn_mode(a);
684 mb = get_irn_mode(b);
685 if (ma != mb && mode_is_int(ma) && mode_is_int(mb))
688 /* check if (a .op. b) can be calculated in the same block is the old instruction */
689 if (! block_dominates(get_nodes_block(a), blk))
691 if (! block_dominates(get_nodes_block(b), blk))
697 mode = get_mode_from_ops(a, b);
698 in[0] = irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
700 /* beware: optimize_node might have changed the opcode, check again */
701 if (is_Add(irn) || is_Sub(irn)) {
702 reverse_rule_distributive(&in[0]);
706 mode = get_mode_from_ops(in[0], in[1]);
707 irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
712 } /* move_consts_up */
715 * Apply the rules in reverse order, removing code that was not collapsed
717 static void reverse_rules(ir_node *node, void *env) {
718 walker_t *wenv = env;
719 ir_mode *mode = get_irn_mode(node);
722 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
723 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
727 ir_op *op = get_irn_op(node);
730 if (is_op_commutative(op)) {
731 wenv->changes |= res = move_consts_up(&node);
733 /* beware: move_consts_up might have changed the opcode, check again */
734 if (is_Add(node) || is_Sub(node)) {
735 wenv->changes |= res = reverse_rule_distributive(&node);
741 * do the reassociation
743 void optimize_reassociation(ir_graph *irg)
746 irg_loopinfo_state state;
749 assert(get_irg_phase_state(irg) != phase_building);
750 assert(get_irg_pinned(irg) != op_pin_state_floats &&
751 "Reassociation needs pinned graph to work properly");
753 rem = current_ir_graph;
754 current_ir_graph = irg;
756 /* we use dominance to detect dead blocks */
760 * Calculate loop info, so we could identify loop-invariant
761 * code and threat it like a constant.
762 * We only need control flow loops here but can handle generic
763 * INTRA info as well.
765 state = get_irg_loopinfo_state(irg);
766 if ((state & loopinfo_inter) ||
767 (state & (loopinfo_constructed | loopinfo_valid)) != (loopinfo_constructed | loopinfo_valid))
768 construct_cf_backedges(irg);
771 env.wq = new_waitq();
773 /* disable some optimizations while reassoc is running to prevent endless loops */
774 set_reassoc_running(1);
776 /* now we have collected enough information, optimize */
777 irg_walk_graph(irg, NULL, wq_walker, &env);
778 do_reassociation(&env);
780 /* reverse those rules that do not result in collapsed constants */
781 irg_walk_graph(irg, NULL, reverse_rules, &env);
783 set_reassoc_running(0);
785 /* Handle graph state */
787 set_irg_outs_inconsistent(irg);
788 set_irg_loopinfo_inconsistent(irg);
792 current_ir_graph = rem;
793 } /* optimize_reassociation */
795 /* Sets the default reassociation operation for an ir_op_ops. */
796 ir_op_ops *firm_set_default_reassoc(ir_opcode code, ir_op_ops *ops)
798 #define CASE(a) case iro_##a: ops->reassociate = reassoc_##a; break
814 } /* firm_set_default_reassoc */
816 /* initialize the reassociation by adding operations to some opcodes */
817 void firm_init_reassociation(void)
819 FIRM_DBG_REGISTER(dbg, "firm.opt.reassoc");
820 } /* firm_init_reassociation */