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"
40 #include "reassoc_t.h"
48 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
50 typedef struct _walker_t {
51 int changes; /**< set, if a reassociation take place */
52 waitq *wq; /**< a wait queue */
56 NO_CONSTANT = 0, /**< node is not constant */
57 REAL_CONSTANT = 1, /**< node is a Const that is suitable for constant folding */
58 REGION_CONST = 4 /**< node is a constant expression in the current context,
59 use 4 here to simplify implementation of get_comm_Binop_ops() */
63 * returns whether a node is constant ie is a constant or
64 * is loop invariant (called region constant)
66 * @param n the node to be checked for constant
67 * @param block a block that might be in a loop
69 static const_class_t get_const_class(const ir_node *n, const ir_node *block)
74 /* constant nodes which can't be folded are region constants */
75 if (is_irn_constlike(n))
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 */
216 * reassociate a commutative Binop
218 * BEWARE: this rule leads to a potential loop, if
219 * two operands are region constants and the third is a
220 * constant, so avoid this situation.
222 static int reassoc_commutative(ir_node **node)
225 ir_op *op = get_irn_op(n);
226 ir_node *block = get_nodes_block(n);
229 get_comm_Binop_ops(n, &t1, &c1);
231 if (get_irn_op(t1) == op) {
233 const_class_t c_c1, c_c2, c_t2;
235 get_comm_Binop_ops(t1, &t2, &c2);
237 /* do not optimize Bad nodes, will fail later */
241 c_c1 = get_const_class(c1, block);
242 c_c2 = get_const_class(c2, block);
243 c_t2 = get_const_class(t2, block);
245 if ( ((c_c1 > NO_CONSTANT) & (c_t2 > NO_CONSTANT)) &&
246 ((((c_c1 ^ c_c2 ^ c_t2) & REGION_CONST) == 0) || ((c_c1 & c_c2 & c_t2) == REGION_CONST)) ) {
247 /* All three are constant and either all are constant expressions
248 * or two of them are:
249 * then applying this rule would lead into a cycle
251 * Note that if t2 is a constant so is c2 hence we save one test.
256 if ((c_c1 != NO_CONSTANT) /* & (c_c2 != NO_CONSTANT) */) {
257 /* handles rules R7, R8, R9, R10:
258 * convert c1 .OP. (c2 .OP. x) => x .OP. (c1 .OP. c2)
260 ir_node *irn, *in[2];
261 ir_mode *mode, *mode_c1 = get_irn_mode(c1), *mode_c2 = get_irn_mode(c2);
263 /* It might happen, that c1 and c2 have different modes, for
264 * instance Is and Iu.
267 if (mode_c1 != mode_c2) {
268 if (mode_is_int(mode_c1) && mode_is_int(mode_c2)) {
269 /* get the bigger one */
270 if (get_mode_size_bits(mode_c1) > get_mode_size_bits(mode_c2))
271 c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
272 else if (get_mode_size_bits(mode_c1) < get_mode_size_bits(mode_c2))
273 c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
275 /* Try to cast the real const */
276 if (c_c1 == REAL_CONSTANT)
277 c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
279 c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
287 mode = get_mode_from_ops(in[0], in[1]);
288 in[1] = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
291 mode = get_mode_from_ops(in[0], in[1]);
292 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
294 DBG((dbg, LEVEL_5, "Applied: %n .%s. (%n .%s. %n) => %n .%s. (%n .%s. %n)\n",
295 c1, get_irn_opname(n), c2, get_irn_opname(n), t2,
296 t2, get_irn_opname(n), c1, get_irn_opname(n), c2));
298 * In some rare cases it can really happen that we get the same
299 * node back. This might be happen in dead loops, were the Phi
300 * nodes are already gone away. So check this.
310 } /* reassoc_commutative */
314 static ir_op *commutative_op;
315 static ir_node *commutative_block;
316 static struct obstack commutative_args;
318 static void collect_args(ir_node *node)
320 ir_node *left = get_binop_left(node);
321 ir_node *right = get_binop_right(node);
323 if (get_irn_op(left) == commutative_op
324 && (!get_irn_outs_computed(left) || get_irn_n_outs(left) == 1)) {
327 obstack_ptr_grow(&commutative_args, left);
330 if (get_irn_op(right) == commutative_op
331 && (!get_irn_outs_computed(right) || get_irn_n_outs(right) == 1)) {
334 obstack_ptr_grow(&commutative_args, right);
339 ir_mode *mode = get_irn_mode(node);
340 if (is_Add(node) && mode_is_reference(mode)) {
341 assert(get_irn_mode(left) == mode || get_irn_mode(right) == mode);
343 assert(get_irn_mode(left) == mode);
344 assert(get_irn_mode(right) == mode);
350 static int compare_nodes(const ir_node *node1, const ir_node *node2)
352 const_class_t class1 = get_const_class(node1, commutative_block);
353 const_class_t class2 = get_const_class(node2, commutative_block);
355 if (class1 == class2)
357 // return get_irn_idx(node1) - get_irn_idx(node2);
362 assert(class1 > class2);
366 static int compare_node_ptr(const void *e1, const void *e2)
368 const ir_node *node1 = *((const ir_node *const*) e1);
369 const ir_node *node2 = *((const ir_node *const*) e2);
370 return compare_nodes(node1, node2);
373 static int reassoc_commutative(ir_node **n)
382 commutative_op = get_irn_op(node);
383 commutative_block = get_nodes_block(node);
385 /* collect all nodes with same op type */
388 n_args = obstack_object_size(&commutative_args) / sizeof(ir_node*);
389 args = obstack_finish(&commutative_args);
391 /* shortcut: in most cases there's nothing to do */
392 if (n_args == 2 && compare_nodes(args[0], args[1]) <= 0) {
393 obstack_free(&commutative_args, args);
397 /* sort the arguments */
398 qsort(args, n_args, sizeof(ir_node*), compare_node_ptr);
401 last = args[n_args-1];
402 mode = get_irn_mode(last);
403 for (i = n_args-2; i >= 0; --i) {
411 /* AddP violates the assumption that all modes in args are equal...
412 * we need some hacks to cope with this */
413 mode_right = get_irn_mode(in[1]);
414 if (mode_is_reference(mode_right)) {
415 assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
416 mode = get_irn_mode(in[1]);
418 if (mode_right != mode) {
419 assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
420 in[1] = new_r_Conv(current_ir_graph, commutative_block,in[1], mode);
423 /* TODO: produce useful debug info! */
424 new_node = new_ir_node(NULL, current_ir_graph, commutative_block,
425 commutative_op, mode, 2, in);
426 new_node = optimize_node(new_node);
430 /* CSE often returns the old node again, only exchange if needed */
432 exchange(node, last);
441 #define reassoc_Add reassoc_commutative
442 #define reassoc_And reassoc_commutative
443 #define reassoc_Or reassoc_commutative
444 #define reassoc_Eor reassoc_commutative
447 * Reassociate using commutative law for Mul and distributive law for Mul and Add/Sub:
449 static int reassoc_Mul(ir_node **node)
452 ir_node *add_sub, *c;
455 if (reassoc_commutative(&n))
458 get_comm_Binop_ops(n, &add_sub, &c);
459 op = get_irn_op(add_sub);
461 /* handles rules R11, R12, R13, R14, R15, R16, R17, R18, R19, R20 */
462 if (op == op_Add || op == op_Sub) {
463 ir_mode *mode = get_irn_mode(n);
464 ir_node *irn, *block, *t1, *t2, *in[2];
466 block = get_nodes_block(n);
467 t1 = get_binop_left(add_sub);
468 t2 = get_binop_right(add_sub);
470 /* we can only multiplication rules on integer arithmetic */
471 if (mode_is_int(get_irn_mode(t1)) && mode_is_int(get_irn_mode(t2))) {
472 in[0] = new_rd_Mul(NULL, current_ir_graph, block, c, t1, mode);
473 in[1] = new_rd_Mul(NULL, current_ir_graph, block, c, t2, mode);
475 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
477 /* In some cases it might happen that the new irn is equal the old one, for
479 * (x - 1) * y == x * y - y
480 * will be transformed back by simpler optimization
481 * We could switch simple optimizations off, but this only happens iff y
482 * is a loop-invariant expression and that it is not clear if the new form
484 * So, we let the old one.
487 DBG((dbg, LEVEL_5, "Applied: (%n .%s. %n) %n %n => (%n %n %n) .%s. (%n %n %n)\n",
488 t1, get_op_name(op), t2, n, c, t1, n, c, get_op_name(op), t2, n, c));
500 * Reassociate Shl. We transform Shl(x, const) into Mul's if possible.
502 static int reassoc_Shl(ir_node **node) {
504 ir_node *c = get_Shl_right(n);
505 ir_node *x, *blk, *irn;
513 mode = get_irn_mode(x);
515 tv = get_mode_one(mode);
516 tv = tarval_shl(tv, get_Const_tarval(c));
518 if (tv == tarval_bad)
521 blk = get_nodes_block(n);
522 c = new_r_Const(current_ir_graph, blk, mode, tv);
523 irn = new_rd_Mul(get_irn_dbg_info(n), current_ir_graph, blk, x, c, mode);
534 * The walker for the reassociation.
536 static void wq_walker(ir_node *n, void *env)
538 walker_t *wenv = env;
540 set_irn_link(n, NULL);
541 if (is_no_Block(n)) {
542 ir_node *blk = get_nodes_block(n);
544 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
545 /* We are in a dead block, do not optimize or we may fall into an endless
546 loop. We check this here instead of requiring that all dead blocks are removed
547 which or cf_opt do not guarantee yet. */
550 waitq_put(wenv->wq, n);
551 set_irn_link(n, wenv->wq);
556 * The walker for the reassociation.
558 static void do_reassociation(walker_t *wenv)
563 while (! waitq_empty(wenv->wq)) {
564 n = waitq_get(wenv->wq);
565 set_irn_link(n, NULL);
567 blk = get_nodes_block(n);
568 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
569 /* We are in a dead block, do not optimize or we may fall into an endless
570 loop. We check this here instead of requiring that all dead blocks are removed
571 which or cf_opt do not guarantee yet. */
578 /* reassociation must run until a fixpoint is reached. */
581 ir_op *op = get_irn_op(n);
582 ir_mode *mode = get_irn_mode(n);
586 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
587 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
590 if (op->ops.reassociate) {
591 res = op->ops.reassociate(&n);
598 wenv->changes |= changed;
601 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
602 ir_node *pred = get_irn_n(n, i);
604 if (get_irn_link(pred) != wenv->wq) {
605 waitq_put(wenv->wq, pred);
606 set_irn_link(pred, wenv->wq);
611 } /* do_reassociation */
614 * Returns the earliest were a,b are available.
615 * Note that we know that a, b both dominate
616 * the block of the previous operation, so one must dominate the other.
618 * If the earliest block is the start block, return curr_blk instead
620 static ir_node *earliest_block(ir_node *a, ir_node *b, ir_node *curr_blk) {
621 ir_node *blk_a = get_nodes_block(a);
622 ir_node *blk_b = get_nodes_block(b);
625 /* if blk_a != blk_b, one must dominate the other */
626 if (block_dominates(blk_a, blk_b))
630 if (res == get_irg_start_block(current_ir_graph))
633 } /* earliest_block */
636 * Checks whether a node is a Constant expression.
637 * The following trees are constant expressions:
639 * Const, SymConst, Const + SymConst
641 * Handling SymConsts as const might be not a good idea for all
644 static int is_constant_expr(ir_node *irn) {
647 switch (get_irn_opcode(irn)) {
652 op = get_irn_op(get_Add_left(irn));
653 if (op != op_Const && op != op_SymConst)
655 op = get_irn_op(get_Add_right(irn));
656 if (op != op_Const && op != op_SymConst)
662 } /* is_constant_expr */
665 * Apply distributive Law for Mul and Add/Sub
667 static int reverse_rule_distributive(ir_node **node) {
669 ir_node *left = get_binop_left(n);
670 ir_node *right = get_binop_right(n);
671 ir_node *x, *blk, *curr_blk;
672 ir_node *a, *b, *irn;
677 op = get_irn_op(left);
678 if (op != get_irn_op(right))
682 x = get_Shl_right(left);
684 if (x == get_Shl_right(right)) {
685 /* (a << x) +/- (b << x) ==> (a +/- b) << x */
686 a = get_Shl_left(left);
687 b = get_Shl_left(right);
690 } else if (op == op_Mul) {
691 x = get_Mul_left(left);
693 if (x == get_Mul_left(right)) {
694 /* (x * a) +/- (x * b) ==> (a +/- b) * x */
695 a = get_Mul_right(left);
696 b = get_Mul_right(right);
698 } else if (x == get_Mul_right(right)) {
699 /* (x * a) +/- (b * x) ==> (a +/- b) * x */
700 a = get_Mul_right(left);
701 b = get_Mul_left(right);
705 x = get_Mul_right(left);
707 if (x == get_Mul_right(right)) {
708 /* (a * x) +/- (b * x) ==> (a +/- b) * x */
709 a = get_Mul_left(left);
710 b = get_Mul_left(right);
712 } else if (x == get_Mul_left(right)) {
713 /* (a * x) +/- (x * b) ==> (a +/- b) * x */
714 a = get_Mul_left(left);
715 b = get_Mul_right(right);
722 curr_blk = get_nodes_block(n);
724 blk = earliest_block(a, b, curr_blk);
726 dbg = get_irn_dbg_info(n);
727 mode = get_irn_mode(n);
730 irn = new_rd_Add(dbg, current_ir_graph, blk, a, b, mode);
732 irn = new_rd_Sub(dbg, current_ir_graph, blk, a, b, mode);
734 blk = earliest_block(irn, x, curr_blk);
737 irn = new_rd_Mul(dbg, current_ir_graph, blk, irn, x, mode);
739 irn = new_rd_Shl(dbg, current_ir_graph, blk, irn, x, mode);
744 } /* reverse_rule_distributive */
747 * Move Constants towards the root.
749 static int move_consts_up(ir_node **node) {
752 ir_node *l, *r, *a, *b, *c, *blk, *irn, *in[2];
753 ir_mode *mode, *ma, *mb;
756 l = get_binop_left(n);
757 r = get_binop_right(n);
759 /* check if one is already a constant expression */
760 if (is_constant_expr(l) || is_constant_expr(r))
763 dbg = get_irn_dbg_info(n);
765 if (get_irn_op(l) == op) {
766 /* (a .op. b) .op. r */
767 a = get_binop_left(l);
768 b = get_binop_right(l);
770 if (is_constant_expr(a)) {
771 /* (C .op. b) .op. r ==> (r .op. b) .op. C */
774 blk = get_nodes_block(l);
775 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
777 } else if (is_constant_expr(b)) {
778 /* (a .op. C) .op. r ==> (a .op. r) .op. C */
781 blk = get_nodes_block(l);
782 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
785 } else if (get_irn_op(r) == op) {
786 /* l .op. (a .op. b) */
787 a = get_binop_left(r);
788 b = get_binop_right(r);
790 if (is_constant_expr(a)) {
791 /* l .op. (C .op. b) ==> (l .op. b) .op. C */
794 blk = get_nodes_block(r);
795 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
797 } else if (is_constant_expr(b)) {
798 /* l .op. (a .op. C) ==> (a .op. l) .op. C */
801 blk = get_nodes_block(r);
802 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
809 /* In some cases a and b might be both of different integer mode, and c a SymConst.
810 * in that case we could either
811 * 1.) cast into unsigned mode
813 * we implement the second here
815 ma = get_irn_mode(a);
816 mb = get_irn_mode(b);
817 if (ma != mb && mode_is_int(ma) && mode_is_int(mb))
820 /* check if (a .op. b) can be calculated in the same block is the old instruction */
821 if (! block_dominates(get_nodes_block(a), blk))
823 if (! block_dominates(get_nodes_block(b), blk))
829 mode = get_mode_from_ops(a, b);
830 in[0] = irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
832 /* beware: optimize_node might have changed the opcode, check again */
833 if (is_Add(irn) || is_Sub(irn)) {
834 reverse_rule_distributive(&in[0]);
838 mode = get_mode_from_ops(in[0], in[1]);
839 irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
844 } /* move_consts_up */
847 * Apply the rules in reverse order, removing code that was not collapsed
849 static void reverse_rules(ir_node *node, void *env) {
850 walker_t *wenv = env;
851 ir_mode *mode = get_irn_mode(node);
854 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
855 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
859 ir_op *op = get_irn_op(node);
862 if (is_op_commutative(op)) {
863 wenv->changes |= res = move_consts_up(&node);
865 /* beware: move_consts_up might have changed the opcode, check again */
866 if (is_Add(node) || is_Sub(node)) {
867 wenv->changes |= res = reverse_rule_distributive(&node);
873 * do the reassociation
875 int optimize_reassociation(ir_graph *irg)
878 irg_loopinfo_state state;
881 assert(get_irg_phase_state(irg) != phase_building);
882 assert(get_irg_pinned(irg) != op_pin_state_floats &&
883 "Reassociation needs pinned graph to work properly");
885 rem = current_ir_graph;
886 current_ir_graph = irg;
888 /* we use dominance to detect dead blocks */
892 assure_irg_outs(irg);
893 obstack_init(&commutative_args);
897 * Calculate loop info, so we could identify loop-invariant
898 * code and threat it like a constant.
899 * We only need control flow loops here but can handle generic
900 * INTRA info as well.
902 state = get_irg_loopinfo_state(irg);
903 if ((state & loopinfo_inter) ||
904 (state & (loopinfo_constructed | loopinfo_valid)) != (loopinfo_constructed | loopinfo_valid))
905 construct_cf_backedges(irg);
908 env.wq = new_waitq();
910 /* disable some optimizations while reassoc is running to prevent endless loops */
911 set_reassoc_running(1);
913 /* now we have collected enough information, optimize */
914 irg_walk_graph(irg, NULL, wq_walker, &env);
915 do_reassociation(&env);
917 /* reverse those rules that do not result in collapsed constants */
918 irg_walk_graph(irg, NULL, reverse_rules, &env);
920 set_reassoc_running(0);
922 /* Handle graph state */
924 set_irg_outs_inconsistent(irg);
925 set_irg_loopinfo_inconsistent(irg);
929 obstack_free(&commutative_args, NULL);
933 current_ir_graph = rem;
935 } /* optimize_reassociation */
937 /* Sets the default reassociation operation for an ir_op_ops. */
938 ir_op_ops *firm_set_default_reassoc(ir_opcode code, ir_op_ops *ops)
940 #define CASE(a) case iro_##a: ops->reassociate = reassoc_##a; break
956 } /* firm_set_default_reassoc */
958 /* initialize the reassociation by adding operations to some opcodes */
959 void firm_init_reassociation(void)
961 FIRM_DBG_REGISTER(dbg, "firm.opt.reassoc");
962 } /* firm_init_reassociation */