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
30 #include "irgraph_t.h"
34 #include "iropt_dbg.h"
38 #include "reassoc_t.h"
47 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
49 typedef struct _walker_t {
50 int changes; /**< set, if a reassociation take place */
51 waitq *wq; /**< a wait queue */
55 NO_CONSTANT = 0, /**< node is not constant */
56 REAL_CONSTANT = 1, /**< node is a Const that is suitable for constant folding */
57 REGION_CONST = 4 /**< node is a constant expression in the current context,
58 use 4 here to simplify implementation of get_comm_Binop_ops() */
62 * returns whether a node is constant ie is a constant or
63 * is loop invariant (called region constant)
65 * @param n the node to be checked for constant
66 * @param block a block that might be in a loop
68 static const_class_t get_const_class(const ir_node *n, const ir_node *block)
73 /* constant nodes which can't be folded are region constants */
74 if (is_irn_constlike(n))
78 * Beware: Bad nodes are always loop-invariant, but
79 * cannot handled in later code, so filter them here.
81 if (! is_Bad(n) && is_loop_invariant(n, block))
85 } /* get_const_class */
88 * returns the operands of a commutative bin-op, if one operand is
89 * a region constant, it is returned as the second one.
91 * Beware: Real constants must be returned with higher priority than
92 * region constants, because they might be folded.
94 static void get_comm_Binop_ops(ir_node *binop, ir_node **a, ir_node **c)
96 ir_node *op_a = get_binop_left(binop);
97 ir_node *op_b = get_binop_right(binop);
98 ir_node *block = get_nodes_block(binop);
99 int class_a = get_const_class(op_a, block);
100 int class_b = get_const_class(op_b, block);
102 assert(is_op_commutative(get_irn_op(binop)));
104 switch (class_a + 2*class_b) {
105 case REAL_CONSTANT + 2*REAL_CONSTANT:
106 /* if both are constants, one might be a
107 * pointer constant like NULL, return the other
109 if (mode_is_reference(get_irn_mode(op_a))) {
117 case REAL_CONSTANT + 2*NO_CONSTANT:
118 case REAL_CONSTANT + 2*REGION_CONST:
119 case REGION_CONST + 2*NO_CONSTANT:
128 } /* get_comm_Binop_ops */
131 * reassociate a Sub: x - c = x + (-c)
133 static int reassoc_Sub(ir_node **in)
136 ir_node *right = get_Sub_right(n);
137 ir_mode *rmode = get_irn_mode(right);
140 /* cannot handle SubIs(P, P) */
141 if (mode_is_reference(rmode))
144 block = get_nodes_block(n);
147 * convert x - c => x + (-c)
149 if (get_const_class(right, block) == REAL_CONSTANT) {
150 ir_node *left = get_Sub_left(n);
155 switch (get_const_class(left, block)) {
157 irn = optimize_in_place(n);
167 /* 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, block, right, rmode);
176 irn = new_rd_Add(dbi, block, left, irn, mode);
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 */
215 * reassociate a commutative Binop
217 * BEWARE: this rule leads to a potential loop, if
218 * two operands are region constants and the third is a
219 * constant, so avoid this situation.
221 static int reassoc_commutative(ir_node **node)
224 ir_op *op = get_irn_op(n);
225 ir_node *block = get_nodes_block(n);
228 get_comm_Binop_ops(n, &t1, &c1);
230 if (get_irn_op(t1) == op) {
232 const_class_t c_c1, c_c2, c_t2;
234 get_comm_Binop_ops(t1, &t2, &c2);
236 /* do not optimize Bad nodes, will fail later */
240 c_c1 = get_const_class(c1, block);
241 c_c2 = get_const_class(c2, block);
242 c_t2 = get_const_class(t2, block);
244 if ( ((c_c1 > NO_CONSTANT) & (c_t2 > NO_CONSTANT)) &&
245 ((((c_c1 ^ c_c2 ^ c_t2) & REGION_CONST) == 0) || ((c_c1 & c_c2 & c_t2) == REGION_CONST)) ) {
246 /* All three are constant and either all are constant expressions
247 * or two of them are:
248 * then applying this rule would lead into a cycle
250 * Note that if t2 is a constant so is c2 hence we save one test.
255 if ((c_c1 != NO_CONSTANT) /* & (c_c2 != NO_CONSTANT) */) {
256 /* handles rules R7, R8, R9, R10:
257 * convert c1 .OP. (c2 .OP. x) => x .OP. (c1 .OP. c2)
259 ir_node *irn, *in[2];
260 ir_mode *mode, *mode_c1 = get_irn_mode(c1), *mode_c2 = get_irn_mode(c2);
262 /* It might happen, that c1 and c2 have different modes, for
263 * instance Is and Iu.
266 if (mode_c1 != mode_c2) {
267 if (mode_is_int(mode_c1) && mode_is_int(mode_c2)) {
268 /* get the bigger one */
269 if (get_mode_size_bits(mode_c1) > get_mode_size_bits(mode_c2))
270 c2 = new_r_Conv(block, c2, mode_c1);
271 else if (get_mode_size_bits(mode_c1) < get_mode_size_bits(mode_c2))
272 c1 = new_r_Conv(block, c1, mode_c2);
274 /* Try to cast the real const */
275 if (c_c1 == REAL_CONSTANT)
276 c1 = new_r_Conv(block, c1, mode_c2);
278 c2 = new_r_Conv(block, c2, mode_c1);
286 mode = get_mode_from_ops(in[0], in[1]);
287 in[1] = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
290 mode = get_mode_from_ops(in[0], in[1]);
291 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
293 DBG((dbg, LEVEL_5, "Applied: %n .%s. (%n .%s. %n) => %n .%s. (%n .%s. %n)\n",
294 c1, get_irn_opname(n), c2, get_irn_opname(n), t2,
295 t2, get_irn_opname(n), c1, get_irn_opname(n), c2));
297 * In some rare cases it can really happen that we get the same
298 * node back. This might be happen in dead loops, were the Phi
299 * nodes are already gone away. So check this.
309 } /* reassoc_commutative */
313 static ir_op *commutative_op;
314 static ir_node *commutative_block;
315 static struct obstack commutative_args;
317 static void collect_args(ir_node *node)
319 ir_node *left = get_binop_left(node);
320 ir_node *right = get_binop_right(node);
322 if (get_irn_op(left) == commutative_op
323 && (!get_irn_outs_computed(left) || get_irn_n_outs(left) == 1)) {
326 obstack_ptr_grow(&commutative_args, left);
329 if (get_irn_op(right) == commutative_op
330 && (!get_irn_outs_computed(right) || get_irn_n_outs(right) == 1)) {
333 obstack_ptr_grow(&commutative_args, right);
338 ir_mode *mode = get_irn_mode(node);
339 if (is_Add(node) && mode_is_reference(mode)) {
340 assert(get_irn_mode(left) == mode || get_irn_mode(right) == mode);
342 assert(get_irn_mode(left) == mode);
343 assert(get_irn_mode(right) == mode);
349 static int compare_nodes(const ir_node *node1, const ir_node *node2)
351 const_class_t class1 = get_const_class(node1, commutative_block);
352 const_class_t class2 = get_const_class(node2, commutative_block);
354 if (class1 == class2)
356 // return get_irn_idx(node1) - get_irn_idx(node2);
361 assert(class1 > class2);
365 static int compare_node_ptr(const void *e1, const void *e2)
367 const ir_node *node1 = *((const ir_node *const*) e1);
368 const ir_node *node2 = *((const ir_node *const*) e2);
369 return compare_nodes(node1, node2);
372 static int reassoc_commutative(ir_node **n)
381 commutative_op = get_irn_op(node);
382 commutative_block = get_nodes_block(node);
384 /* collect all nodes with same op type */
387 n_args = obstack_object_size(&commutative_args) / sizeof(ir_node*);
388 args = obstack_finish(&commutative_args);
390 /* shortcut: in most cases there's nothing to do */
391 if (n_args == 2 && compare_nodes(args[0], args[1]) <= 0) {
392 obstack_free(&commutative_args, args);
396 /* sort the arguments */
397 qsort(args, n_args, sizeof(ir_node*), compare_node_ptr);
400 last = args[n_args-1];
401 mode = get_irn_mode(last);
402 for (i = n_args-2; i >= 0; --i) {
410 /* AddP violates the assumption that all modes in args are equal...
411 * we need some hacks to cope with this */
412 mode_right = get_irn_mode(in[1]);
413 if (mode_is_reference(mode_right)) {
414 assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
415 mode = get_irn_mode(in[1]);
417 if (mode_right != mode) {
418 assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
419 in[1] = new_r_Conv(current_ir_graph, commutative_block,in[1], mode);
422 /* TODO: produce useful debug info! */
423 new_node = new_ir_node(NULL, current_ir_graph, commutative_block,
424 commutative_op, mode, 2, in);
425 new_node = optimize_node(new_node);
429 /* CSE often returns the old node again, only exchange if needed */
431 exchange(node, last);
440 #define reassoc_Add reassoc_commutative
441 #define reassoc_And reassoc_commutative
442 #define reassoc_Or reassoc_commutative
443 #define reassoc_Eor reassoc_commutative
446 * Reassociate using commutative law for Mul and distributive law for Mul and Add/Sub:
448 static int reassoc_Mul(ir_node **node)
451 ir_node *add_sub, *c;
454 if (reassoc_commutative(&n))
457 get_comm_Binop_ops(n, &add_sub, &c);
458 op = get_irn_op(add_sub);
460 /* handles rules R11, R12, R13, R14, R15, R16, R17, R18, R19, R20 */
461 if (op == op_Add || op == op_Sub) {
462 ir_mode *mode = get_irn_mode(n);
463 ir_node *irn, *block, *t1, *t2, *in[2];
465 block = get_nodes_block(n);
466 t1 = get_binop_left(add_sub);
467 t2 = get_binop_right(add_sub);
469 /* we can only multiplication rules on integer arithmetic */
470 if (mode_is_int(get_irn_mode(t1)) && mode_is_int(get_irn_mode(t2))) {
471 in[0] = new_rd_Mul(NULL, block, c, t1, mode);
472 in[1] = new_rd_Mul(NULL, block, c, t2, mode);
474 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
476 /* In some cases it might happen that the new irn is equal the old one, for
478 * (x - 1) * y == x * y - y
479 * will be transformed back by simpler optimization
480 * We could switch simple optimizations off, but this only happens iff y
481 * is a loop-invariant expression and that it is not clear if the new form
483 * So, we let the old one.
486 DBG((dbg, LEVEL_5, "Applied: (%n .%s. %n) %n %n => (%n %n %n) .%s. (%n %n %n)\n",
487 t1, get_op_name(op), t2, n, c, t1, n, c, get_op_name(op), t2, n, c));
499 * Reassociate Shl. We transform Shl(x, const) into Mul's if possible.
501 static int reassoc_Shl(ir_node **node) {
503 ir_node *c = get_Shl_right(n);
504 ir_node *x, *blk, *irn;
512 mode = get_irn_mode(x);
514 tv = get_mode_one(mode);
515 tv = tarval_shl(tv, get_Const_tarval(c));
517 if (tv == tarval_bad)
520 blk = get_nodes_block(n);
522 irn = new_rd_Mul(get_irn_dbg_info(n), blk, x, c, mode);
533 * The walker for the reassociation.
535 static void wq_walker(ir_node *n, void *env)
537 walker_t *wenv = env;
539 set_irn_link(n, NULL);
540 if (is_no_Block(n)) {
541 ir_node *blk = get_nodes_block(n);
543 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
544 /* We are in a dead block, do not optimize or we may fall into an endless
545 loop. We check this here instead of requiring that all dead blocks are removed
546 which or cf_opt do not guarantee yet. */
549 waitq_put(wenv->wq, n);
550 set_irn_link(n, wenv->wq);
555 * The walker for the reassociation.
557 static void do_reassociation(walker_t *wenv)
562 while (! waitq_empty(wenv->wq)) {
563 n = waitq_get(wenv->wq);
564 set_irn_link(n, NULL);
566 blk = get_nodes_block(n);
567 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
568 /* We are in a dead block, do not optimize or we may fall into an endless
569 loop. We check this here instead of requiring that all dead blocks are removed
570 which or cf_opt do not guarantee yet. */
577 /* reassociation must run until a fixpoint is reached. */
580 ir_op *op = get_irn_op(n);
581 ir_mode *mode = get_irn_mode(n);
585 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
586 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
589 if (op->ops.reassociate) {
590 res = op->ops.reassociate(&n);
597 wenv->changes |= changed;
600 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
601 ir_node *pred = get_irn_n(n, i);
603 if (get_irn_link(pred) != wenv->wq) {
604 waitq_put(wenv->wq, pred);
605 set_irn_link(pred, wenv->wq);
610 } /* do_reassociation */
613 * Returns the earliest were a,b are available.
614 * Note that we know that a, b both dominate
615 * the block of the previous operation, so one must dominate the other.
617 * If the earliest block is the start block, return curr_blk instead
619 static ir_node *earliest_block(ir_node *a, ir_node *b, ir_node *curr_blk) {
620 ir_node *blk_a = get_nodes_block(a);
621 ir_node *blk_b = get_nodes_block(b);
624 /* if blk_a != blk_b, one must dominate the other */
625 if (block_dominates(blk_a, blk_b))
629 if (res == get_irg_start_block(current_ir_graph))
632 } /* earliest_block */
635 * Checks whether a node is a Constant expression.
636 * The following trees are constant expressions:
638 * Const, SymConst, Const + SymConst
640 * Handling SymConsts as const might be not a good idea for all
643 static int is_constant_expr(ir_node *irn) {
646 switch (get_irn_opcode(irn)) {
651 op = get_irn_op(get_Add_left(irn));
652 if (op != op_Const && op != op_SymConst)
654 op = get_irn_op(get_Add_right(irn));
655 if (op != op_Const && op != op_SymConst)
661 } /* is_constant_expr */
664 * Apply distributive Law for Mul and Add/Sub
666 static int reverse_rule_distributive(ir_node **node) {
668 ir_node *left = get_binop_left(n);
669 ir_node *right = get_binop_right(n);
670 ir_node *x, *blk, *curr_blk;
671 ir_node *a, *b, *irn;
676 op = get_irn_op(left);
677 if (op != get_irn_op(right))
681 x = get_Shl_right(left);
683 if (x == get_Shl_right(right)) {
684 /* (a << x) +/- (b << x) ==> (a +/- b) << x */
685 a = get_Shl_left(left);
686 b = get_Shl_left(right);
689 } else if (op == op_Mul) {
690 x = get_Mul_left(left);
692 if (x == get_Mul_left(right)) {
693 /* (x * a) +/- (x * b) ==> (a +/- b) * x */
694 a = get_Mul_right(left);
695 b = get_Mul_right(right);
697 } else if (x == get_Mul_right(right)) {
698 /* (x * a) +/- (b * x) ==> (a +/- b) * x */
699 a = get_Mul_right(left);
700 b = get_Mul_left(right);
704 x = get_Mul_right(left);
706 if (x == get_Mul_right(right)) {
707 /* (a * x) +/- (b * x) ==> (a +/- b) * x */
708 a = get_Mul_left(left);
709 b = get_Mul_left(right);
711 } else if (x == get_Mul_left(right)) {
712 /* (a * x) +/- (x * b) ==> (a +/- b) * x */
713 a = get_Mul_left(left);
714 b = get_Mul_right(right);
721 curr_blk = get_nodes_block(n);
723 blk = earliest_block(a, b, curr_blk);
725 dbg = get_irn_dbg_info(n);
726 mode = get_irn_mode(n);
729 irn = new_rd_Add(dbg, blk, a, b, mode);
731 irn = new_rd_Sub(dbg, blk, a, b, mode);
733 blk = earliest_block(irn, x, curr_blk);
736 irn = new_rd_Mul(dbg, blk, irn, x, mode);
738 irn = new_rd_Shl(dbg, blk, irn, x, mode);
743 } /* reverse_rule_distributive */
746 * Move Constants towards the root.
748 static int move_consts_up(ir_node **node) {
751 ir_node *l, *r, *a, *b, *c, *blk, *irn, *in[2];
752 ir_mode *mode, *ma, *mb;
755 l = get_binop_left(n);
756 r = get_binop_right(n);
758 /* check if one is already a constant expression */
759 if (is_constant_expr(l) || is_constant_expr(r))
762 dbg = get_irn_dbg_info(n);
764 if (get_irn_op(l) == op) {
765 /* (a .op. b) .op. r */
766 a = get_binop_left(l);
767 b = get_binop_right(l);
769 if (is_constant_expr(a)) {
770 /* (C .op. b) .op. r ==> (r .op. b) .op. C */
773 blk = get_nodes_block(l);
774 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
776 } else if (is_constant_expr(b)) {
777 /* (a .op. C) .op. r ==> (a .op. r) .op. C */
780 blk = get_nodes_block(l);
781 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
784 } else if (get_irn_op(r) == op) {
785 /* l .op. (a .op. b) */
786 a = get_binop_left(r);
787 b = get_binop_right(r);
789 if (is_constant_expr(a)) {
790 /* l .op. (C .op. b) ==> (l .op. b) .op. C */
793 blk = get_nodes_block(r);
794 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
796 } else if (is_constant_expr(b)) {
797 /* l .op. (a .op. C) ==> (a .op. l) .op. C */
800 blk = get_nodes_block(r);
801 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
808 /* In some cases a and b might be both of different integer mode, and c a SymConst.
809 * in that case we could either
810 * 1.) cast into unsigned mode
812 * we implement the second here
814 ma = get_irn_mode(a);
815 mb = get_irn_mode(b);
816 if (ma != mb && mode_is_int(ma) && mode_is_int(mb))
819 /* check if (a .op. b) can be calculated in the same block is the old instruction */
820 if (! block_dominates(get_nodes_block(a), blk))
822 if (! block_dominates(get_nodes_block(b), blk))
828 mode = get_mode_from_ops(a, b);
829 in[0] = irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
831 /* beware: optimize_node might have changed the opcode, check again */
832 if (is_Add(irn) || is_Sub(irn)) {
833 reverse_rule_distributive(&in[0]);
837 mode = get_mode_from_ops(in[0], in[1]);
838 irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
843 } /* move_consts_up */
846 * Apply the rules in reverse order, removing code that was not collapsed
848 static void reverse_rules(ir_node *node, void *env) {
849 walker_t *wenv = env;
850 ir_mode *mode = get_irn_mode(node);
853 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
854 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
858 ir_op *op = get_irn_op(node);
861 if (is_op_commutative(op)) {
862 wenv->changes |= res = move_consts_up(&node);
864 /* beware: move_consts_up might have changed the opcode, check again */
865 if (is_Add(node) || is_Sub(node)) {
866 wenv->changes |= res = reverse_rule_distributive(&node);
872 * do the reassociation
874 int optimize_reassociation(ir_graph *irg)
877 irg_loopinfo_state state;
880 assert(get_irg_phase_state(irg) != phase_building);
881 assert(get_irg_pinned(irg) != op_pin_state_floats &&
882 "Reassociation needs pinned graph to work properly");
884 rem = current_ir_graph;
885 current_ir_graph = irg;
887 /* we use dominance to detect dead blocks */
891 assure_irg_outs(irg);
892 obstack_init(&commutative_args);
896 * Calculate loop info, so we could identify loop-invariant
897 * code and threat it like a constant.
898 * We only need control flow loops here but can handle generic
899 * INTRA info as well.
901 state = get_irg_loopinfo_state(irg);
902 if ((state & loopinfo_inter) ||
903 (state & (loopinfo_constructed | loopinfo_valid)) != (loopinfo_constructed | loopinfo_valid))
904 construct_cf_backedges(irg);
907 env.wq = new_waitq();
909 /* disable some optimizations while reassoc is running to prevent endless loops */
910 set_reassoc_running(1);
912 /* now we have collected enough information, optimize */
913 irg_walk_graph(irg, NULL, wq_walker, &env);
914 do_reassociation(&env);
916 /* reverse those rules that do not result in collapsed constants */
917 irg_walk_graph(irg, NULL, reverse_rules, &env);
919 set_reassoc_running(0);
921 /* Handle graph state */
923 set_irg_outs_inconsistent(irg);
924 set_irg_loopinfo_inconsistent(irg);
928 obstack_free(&commutative_args, NULL);
932 current_ir_graph = rem;
934 } /* optimize_reassociation */
936 /* create a pass for the reassociation */
937 ir_graph_pass_t *optimize_reassociation_pass(const char *name) {
938 return def_graph_pass_ret(name ? name : "reassoc", optimize_reassociation);
939 } /* optimize_reassociation_pass */
941 /* Sets the default reassociation operation for an ir_op_ops. */
942 ir_op_ops *firm_set_default_reassoc(ir_opcode code, ir_op_ops *ops)
944 #define CASE(a) case iro_##a: ops->reassociate = reassoc_##a; break
960 } /* firm_set_default_reassoc */
962 /* initialize the reassociation by adding operations to some opcodes */
963 void firm_init_reassociation(void)
965 FIRM_DBG_REGISTER(dbg, "firm.opt.reassoc");
966 } /* firm_init_reassociation */