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 */
171 mode = get_irn_mode(n);
172 dbi = get_irn_dbg_info(n);
174 /* Beware of SubP(P, Is) */
175 irn = new_rd_Minus(dbi, current_ir_graph, block, right, rmode);
176 irn = new_rd_Add(dbi, current_ir_graph, block, left, irn, get_irn_mode(n));
178 DBG((dbg, LEVEL_5, "Applied: %n - %n => %n + (-%n)\n",
179 get_Sub_left(n), right, get_Sub_left(n), right));
192 /** Retrieve a mode from the operands. We need this, because
193 * Add and Sub are allowed to operate on (P, Is)
195 static ir_mode *get_mode_from_ops(ir_node *op1, ir_node *op2)
199 m1 = get_irn_mode(op1);
200 if (mode_is_reference(m1))
203 m2 = get_irn_mode(op2);
204 if (mode_is_reference(m2))
210 } /* get_mode_from_ops */
213 * reassociate a commutative Binop
215 * BEWARE: this rule leads to a potential loop, if
216 * two operands are region constants and the third is a
217 * constant, so avoid this situation.
219 static int reassoc_commutative(ir_node **node)
222 ir_op *op = get_irn_op(n);
223 ir_node *block = get_nodes_block(n);
226 get_comm_Binop_ops(n, &t1, &c1);
228 if (get_irn_op(t1) == op) {
230 const_class_t c_c1, c_c2, c_t2;
232 get_comm_Binop_ops(t1, &t2, &c2);
234 /* do not optimize Bad nodes, will fail later */
238 c_c1 = get_const_class(c1, block);
239 c_c2 = get_const_class(c2, block);
240 c_t2 = get_const_class(t2, block);
242 if ( ((c_c1 > NO_CONSTANT) & (c_t2 > NO_CONSTANT)) &&
243 ((((c_c1 ^ c_c2 ^ c_t2) & REGION_CONST) == 0) || ((c_c1 & c_c2 & c_t2) == REGION_CONST)) ) {
244 /* All three are constant and either all are constant expressions or two of them are:
245 * then applying this rule would lead into a cycle
247 * Note that if t2 is a constant so is c2 hence we save one test.
252 if ((c_c1 != NO_CONSTANT) /* & (c_c2 != NO_CONSTANT) */) {
253 /* handles rules R7, R8, R9, R10:
254 * convert c1 .OP. (c2 .OP. x) => x .OP. (c1 .OP. c2)
256 ir_node *irn, *in[2];
257 ir_mode *mode, *mode_c1 = get_irn_mode(c1), *mode_c2 = get_irn_mode(c2);
259 /* It might happen, that c1 and c2 have different modes, for instance Is and Iu.
262 if (mode_c1 != mode_c2) {
263 if (mode_is_int(mode_c1) && mode_is_int(mode_c2)) {
264 /* get the bigger one */
265 if (get_mode_size_bits(mode_c1) > get_mode_size_bits(mode_c2))
266 c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
267 else if (get_mode_size_bits(mode_c1) < get_mode_size_bits(mode_c2))
268 c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
270 /* Try to cast the real const */
271 if (c_c1 == REAL_CONSTANT)
272 c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
274 c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
282 mode = get_mode_from_ops(in[0], in[1]);
283 in[1] = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
286 mode = get_mode_from_ops(in[0], in[1]);
287 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
289 DBG((dbg, LEVEL_5, "Applied: %n .%s. (%n .%s. %n) => %n .%s. (%n .%s. %n)\n",
290 c1, get_irn_opname(n), c2, get_irn_opname(n), t2,
291 t2, get_irn_opname(n), c1, get_irn_opname(n), c2));
293 * In some rare cases it can really happen that we get the same node back.
294 * This might be happen in dead loops, were the Phi nodes are already gone away.
305 } /* reassoc_commutative */
307 #define reassoc_Add reassoc_commutative
308 #define reassoc_And reassoc_commutative
309 #define reassoc_Or reassoc_commutative
310 #define reassoc_Eor reassoc_commutative
313 * Reassociate using commutative law for Mul and distributive law for Mul and Add/Sub:
315 static int reassoc_Mul(ir_node **node)
318 ir_node *add_sub, *c;
321 if (reassoc_commutative(&n))
324 get_comm_Binop_ops(n, &add_sub, &c);
325 op = get_irn_op(add_sub);
327 /* handles rules R11, R12, R13, R14, R15, R16, R17, R18, R19, R20 */
328 if (op == op_Add || op == op_Sub) {
329 ir_mode *mode = get_irn_mode(n);
330 ir_node *irn, *block, *t1, *t2, *in[2];
332 block = get_nodes_block(n);
333 t1 = get_binop_left(add_sub);
334 t2 = get_binop_right(add_sub);
336 /* we can only multiplication rules on integer arithmetic */
337 if (mode_is_int(get_irn_mode(t1)) && mode_is_int(get_irn_mode(t2))) {
338 in[0] = new_rd_Mul(NULL, current_ir_graph, block, c, t1, mode);
339 in[1] = new_rd_Mul(NULL, current_ir_graph, block, c, t2, mode);
341 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
343 /* In some cases it might happen that the new irn is equal the old one, for
345 * (x - 1) * y == x * y - y
346 * will be transformed back by simpler optimization
347 * We could switch simple optimizations off, but this only happens iff y
348 * is a loop-invariant expression and that it is not clear if the new form
350 * So, we let the old one.
353 DBG((dbg, LEVEL_5, "Applied: (%n .%s. %n) %n %n => (%n %n %n) .%s. (%n %n %n)\n",
354 t1, get_op_name(op), t2, n, c, t1, n, c, get_op_name(op), t2, n, c));
366 * Reassociate Shl. We transform Shl(x, const) into Mul's if possible.
368 static int reassoc_Shl(ir_node **node) {
370 ir_node *c = get_Shl_right(n);
371 ir_node *x, *blk, *irn;
379 mode = get_irn_mode(x);
381 tv = get_mode_one(mode);
382 tv = tarval_shl(tv, get_Const_tarval(c));
384 if (tv == tarval_bad)
387 blk = get_nodes_block(n);
388 c = new_r_Const(current_ir_graph, blk, mode, tv);
389 irn = new_rd_Mul(get_irn_dbg_info(n), current_ir_graph, blk, x, c, mode);
400 * The walker for the reassociation.
402 static void wq_walker(ir_node *n, void *env)
404 walker_t *wenv = env;
406 set_irn_link(n, NULL);
407 if (is_no_Block(n)) {
408 ir_node *blk = get_nodes_block(n);
410 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
411 /* We are in a dead block, do not optimize or we may fall into an endless
412 loop. We check this here instead of requiring that all dead blocks are removed
413 which or cf_opt do not guarantee yet. */
416 waitq_put(wenv->wq, n);
417 set_irn_link(n, wenv->wq);
422 * The walker for the reassociation.
424 static void do_reassociation(walker_t *wenv)
430 while (! waitq_empty(wenv->wq)) {
431 n = waitq_get(wenv->wq);
432 set_irn_link(n, NULL);
434 blk = get_nodes_block(n);
435 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
436 /* We are in a dead block, do not optimize or we may fall into an endless
437 loop. We check this here instead of requiring that all dead blocks are removed
438 which or cf_opt do not guarantee yet. */
445 /* reassociation must run until a fixpoint is reached. */
448 ir_op *op = get_irn_op(n);
449 ir_mode *mode = get_irn_mode(n);
453 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
454 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
457 if (op->ops.reassociate) {
458 res = op->ops.reassociate(&n);
465 wenv->changes |= changed;
468 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
469 ir_node *pred = get_irn_n(n, i);
471 if (get_irn_link(pred) != wenv->wq) {
472 waitq_put(wenv->wq, pred);
473 set_irn_link(pred, wenv->wq);
478 } /* do_reassociation */
481 * Returns the earliest were a,b are available.
482 * Note that we know that a, b both dominate
483 * the block of the previous operation, so one must dominate the other.
485 * If the earliest block is the start block, return curr_blk instead
487 static ir_node *earliest_block(ir_node *a, ir_node *b, ir_node *curr_blk) {
488 ir_node *blk_a = get_nodes_block(a);
489 ir_node *blk_b = get_nodes_block(b);
492 /* if blk_a != blk_b, one must dominate the other */
493 if (block_dominates(blk_a, blk_b))
497 if (res == get_irg_start_block(current_ir_graph))
500 } /* earliest_block */
503 * Checks whether a node is a Constant expression.
504 * The following trees are constant expressions:
506 * Const, SymConst, Const + SymConst
508 * Handling SymConsts as const might be not a good idea for all
511 static int is_constant_expr(ir_node *irn) {
514 switch (get_irn_opcode(irn)) {
519 op = get_irn_op(get_Add_left(irn));
520 if (op != op_Const && op != op_SymConst)
522 op = get_irn_op(get_Add_right(irn));
523 if (op != op_Const && op != op_SymConst)
529 } /* is_constant_expr */
532 * Apply distributive Law for Mul and Add/Sub
534 static int reverse_rule_distributive(ir_node **node) {
536 ir_node *left = get_binop_left(n);
537 ir_node *right = get_binop_right(n);
538 ir_node *x, *blk, *curr_blk;
539 ir_node *a, *b, *irn;
544 op = get_irn_op(left);
545 if (op != get_irn_op(right))
549 x = get_Shl_right(left);
551 if (x == get_Shl_right(right)) {
552 /* (a << x) +/- (b << x) ==> (a +/- b) << x */
553 a = get_Shl_left(left);
554 b = get_Shl_left(right);
557 } else if (op == op_Mul) {
558 x = get_Mul_left(left);
560 if (x == get_Mul_left(right)) {
561 /* (x * a) +/- (x * b) ==> (a +/- b) * x */
562 a = get_Mul_right(left);
563 b = get_Mul_right(right);
565 } else if (x == get_Mul_right(right)) {
566 /* (x * a) +/- (b * x) ==> (a +/- b) * x */
567 a = get_Mul_right(left);
568 b = get_Mul_left(right);
572 x = get_Mul_right(left);
574 if (x == get_Mul_right(right)) {
575 /* (a * x) +/- (b * x) ==> (a +/- b) * x */
576 a = get_Mul_left(left);
577 b = get_Mul_left(right);
579 } else if (x == get_Mul_left(right)) {
580 /* (a * x) +/- (x * b) ==> (a +/- b) * x */
581 a = get_Mul_left(left);
582 b = get_Mul_right(right);
589 curr_blk = get_nodes_block(n);
591 blk = earliest_block(a, b, curr_blk);
593 dbg = get_irn_dbg_info(n);
594 mode = get_irn_mode(n);
597 irn = new_rd_Add(dbg, current_ir_graph, blk, a, b, mode);
599 irn = new_rd_Sub(dbg, current_ir_graph, blk, a, b, mode);
601 blk = earliest_block(irn, x, curr_blk);
604 irn = new_rd_Mul(dbg, current_ir_graph, blk, irn, x, mode);
606 irn = new_rd_Shl(dbg, current_ir_graph, blk, irn, x, mode);
611 } /* reverse_rule_distributive */
614 * Move Constants towards the root.
616 static int move_consts_up(ir_node **node) {
619 ir_node *l, *r, *a, *b, *c, *blk, *irn, *in[2];
620 ir_mode *mode, *ma, *mb;
623 l = get_binop_left(n);
624 r = get_binop_right(n);
626 /* check if one is already a constant expression */
627 if (is_constant_expr(l) || is_constant_expr(r))
630 dbg = get_irn_dbg_info(n);
632 if (get_irn_op(l) == op) {
633 /* (a .op. b) .op. r */
634 a = get_binop_left(l);
635 b = get_binop_right(l);
637 if (is_constant_expr(a)) {
638 /* (C .op. b) .op. r ==> (r .op. b) .op. C */
641 blk = get_nodes_block(l);
642 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
644 } else if (is_constant_expr(b)) {
645 /* (a .op. C) .op. r ==> (a .op. r) .op. C */
648 blk = get_nodes_block(l);
649 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
652 } else if (get_irn_op(r) == op) {
653 /* l .op. (a .op. b) */
654 a = get_binop_left(r);
655 b = get_binop_right(r);
657 if (is_constant_expr(a)) {
658 /* l .op. (C .op. b) ==> (l .op. b) .op. C */
661 blk = get_nodes_block(r);
662 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
664 } else if (is_constant_expr(b)) {
665 /* l .op. (a .op. C) ==> (a .op. l) .op. C */
668 blk = get_nodes_block(r);
669 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
676 /* In some cases a and b might be both of different integer mode, and c a SymConst.
677 * in that case we could either
678 * 1.) cast into unsigned mode
680 * we implement the second here
682 ma = get_irn_mode(a);
683 mb = get_irn_mode(b);
684 if (ma != mb && mode_is_int(ma) && mode_is_int(mb))
687 /* check if (a .op. b) can be calculated in the same block is the old instruction */
688 if (! block_dominates(get_nodes_block(a), blk))
690 if (! block_dominates(get_nodes_block(b), blk))
696 mode = get_mode_from_ops(a, b);
697 in[0] = irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
699 /* beware: optimize_node might have changed the opcode, check again */
700 if (is_Add(irn) || is_Sub(irn)) {
701 reverse_rule_distributive(&in[0]);
705 mode = get_mode_from_ops(in[0], in[1]);
706 irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
711 } /* move_consts_up */
714 * Apply the rules in reverse order, removing code that was not collapsed
716 static void reverse_rules(ir_node *node, void *env) {
717 walker_t *wenv = env;
718 ir_mode *mode = get_irn_mode(node);
721 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
722 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
726 ir_op *op = get_irn_op(node);
729 if (is_op_commutative(op)) {
730 wenv->changes |= res = move_consts_up(&node);
732 /* beware: move_consts_up might have changed the opcode, check again */
733 if (is_Add(node) || is_Sub(node)) {
734 wenv->changes |= res = reverse_rule_distributive(&node);
740 * do the reassociation
742 void optimize_reassociation(ir_graph *irg)
745 irg_loopinfo_state state;
748 assert(get_irg_phase_state(irg) != phase_building);
749 assert(get_irg_pinned(irg) != op_pin_state_floats &&
750 "Reassociation needs pinned graph to work properly");
752 rem = current_ir_graph;
753 current_ir_graph = irg;
755 /* we use dominance to detect dead blocks */
759 * Calculate loop info, so we could identify loop-invariant
760 * code and threat it like a constant.
761 * We only need control flow loops here but can handle generic
762 * INTRA info as well.
764 state = get_irg_loopinfo_state(irg);
765 if ((state & loopinfo_inter) ||
766 (state & (loopinfo_constructed | loopinfo_valid)) != (loopinfo_constructed | loopinfo_valid))
767 construct_cf_backedges(irg);
770 env.wq = new_waitq();
772 /* disable some optimizations while reassoc is running to prevent endless loops */
773 set_reassoc_running(1);
775 /* now we have collected enough information, optimize */
776 irg_walk_graph(irg, NULL, wq_walker, &env);
777 do_reassociation(&env);
779 /* reverse those rules that do not result in collapsed constants */
780 irg_walk_graph(irg, NULL, reverse_rules, &env);
782 set_reassoc_running(0);
784 /* Handle graph state */
786 set_irg_outs_inconsistent(irg);
787 set_irg_loopinfo_inconsistent(irg);
791 current_ir_graph = rem;
792 } /* optimize_reassociation */
794 /* Sets the default reassociation operation for an ir_op_ops. */
795 ir_op_ops *firm_set_default_reassoc(ir_opcode code, ir_op_ops *ops)
797 #define CASE(a) case iro_##a: ops->reassociate = reassoc_##a; break
813 } /* firm_set_default_reassoc */
815 /* initialize the reassociation by adding operations to some opcodes */
816 void firm_init_reassociation(void)
818 FIRM_DBG_REGISTER(dbg, "firm.opt.reassoc");
819 } /* firm_init_reassociation */