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"
46 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
48 typedef struct _walker_t {
49 int changes; /**< set, if a reassociation take place */
50 waitq *wq; /**< a wait queue */
54 NO_CONSTANT = 0, /**< node is not constant */
55 REAL_CONSTANT = 1, /**< node is a Const that is suitable for constant folding */
56 REGION_CONST = 4 /**< node is a constant expression in the current context,
57 use 4 here to simplify implementation of get_comm_Binop_ops() */
61 * returns whether a node is constant ie is a constant or
62 * is loop invariant (called region constant)
64 * @param n the node to be checked for constant
65 * @param block a block that might be in a loop
67 static const_class_t get_const_class(const ir_node *n, const ir_node *block)
72 /* constant nodes which can't be folded are region constants */
73 if (is_irn_constlike(n))
77 * Beware: Bad nodes are always loop-invariant, but
78 * cannot handled in later code, so filter them here.
80 if (! is_Bad(n) && is_loop_invariant(n, block))
84 } /* get_const_class */
87 * returns the operands of a commutative bin-op, if one operand is
88 * a region constant, it is returned as the second one.
90 * Beware: Real constants must be returned with higher priority than
91 * region constants, because they might be folded.
93 static void get_comm_Binop_ops(ir_node *binop, ir_node **a, ir_node **c)
95 ir_node *op_a = get_binop_left(binop);
96 ir_node *op_b = get_binop_right(binop);
97 ir_node *block = get_nodes_block(binop);
98 int class_a = get_const_class(op_a, block);
99 int class_b = get_const_class(op_b, block);
101 assert(is_op_commutative(get_irn_op(binop)));
103 switch (class_a + 2*class_b) {
104 case REAL_CONSTANT + 2*REAL_CONSTANT:
105 /* if both are constants, one might be a
106 * pointer constant like NULL, return the other
108 if (mode_is_reference(get_irn_mode(op_a))) {
116 case REAL_CONSTANT + 2*NO_CONSTANT:
117 case REAL_CONSTANT + 2*REGION_CONST:
118 case REGION_CONST + 2*NO_CONSTANT:
127 } /* get_comm_Binop_ops */
130 * reassociate a Sub: x - c = x + (-c)
132 static int reassoc_Sub(ir_node **in)
135 ir_node *right = get_Sub_right(n);
136 ir_mode *rmode = get_irn_mode(right);
139 /* cannot handle SubIs(P, P) */
140 if (mode_is_reference(rmode))
143 block = get_nodes_block(n);
146 * convert x - c => x + (-c)
148 if (get_const_class(right, block) == REAL_CONSTANT) {
149 ir_node *left = get_Sub_left(n);
154 switch (get_const_class(left, block)) {
156 irn = optimize_in_place(n);
166 /* already constant, nothing to do */
170 mode = get_irn_mode(n);
171 dbi = get_irn_dbg_info(n);
173 /* Beware of SubP(P, Is) */
174 irn = new_rd_Minus(dbi, block, right, rmode);
175 irn = new_rd_Add(dbi, block, left, irn, mode);
177 DBG((dbg, LEVEL_5, "Applied: %n - %n => %n + (-%n)\n",
178 get_Sub_left(n), right, get_Sub_left(n), right));
191 /** Retrieve a mode from the operands. We need this, because
192 * Add and Sub are allowed to operate on (P, Is)
194 static ir_mode *get_mode_from_ops(ir_node *op1, ir_node *op2)
198 m1 = get_irn_mode(op1);
199 if (mode_is_reference(m1))
202 m2 = get_irn_mode(op2);
203 if (mode_is_reference(m2))
209 } /* 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
246 * or two of them are:
247 * then applying this rule would lead into a cycle
249 * Note that if t2 is a constant so is c2 hence we save one test.
254 if ((c_c1 != NO_CONSTANT) /* & (c_c2 != NO_CONSTANT) */) {
255 /* handles rules R7, R8, R9, R10:
256 * convert c1 .OP. (c2 .OP. x) => x .OP. (c1 .OP. c2)
258 ir_node *irn, *in[2];
259 ir_mode *mode, *mode_c1 = get_irn_mode(c1), *mode_c2 = get_irn_mode(c2);
261 /* It might happen, that c1 and c2 have different modes, for
262 * instance Is and Iu.
265 if (mode_c1 != mode_c2) {
266 if (mode_is_int(mode_c1) && mode_is_int(mode_c2)) {
267 /* get the bigger one */
268 if (get_mode_size_bits(mode_c1) > get_mode_size_bits(mode_c2))
269 c2 = new_r_Conv(block, c2, mode_c1);
270 else if (get_mode_size_bits(mode_c1) < get_mode_size_bits(mode_c2))
271 c1 = new_r_Conv(block, c1, mode_c2);
273 /* Try to cast the real const */
274 if (c_c1 == REAL_CONSTANT)
275 c1 = new_r_Conv(block, c1, mode_c2);
277 c2 = new_r_Conv(block, c2, mode_c1);
285 mode = get_mode_from_ops(in[0], in[1]);
286 in[1] = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
289 mode = get_mode_from_ops(in[0], in[1]);
290 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
292 DBG((dbg, LEVEL_5, "Applied: %n .%s. (%n .%s. %n) => %n .%s. (%n .%s. %n)\n",
293 c1, get_irn_opname(n), c2, get_irn_opname(n), t2,
294 t2, get_irn_opname(n), c1, get_irn_opname(n), c2));
296 * In some rare cases it can really happen that we get the same
297 * node back. This might be happen in dead loops, were the Phi
298 * nodes are already gone away. So check this.
308 } /* reassoc_commutative */
312 static ir_op *commutative_op;
313 static ir_node *commutative_block;
314 static struct obstack commutative_args;
316 static void collect_args(ir_node *node)
318 ir_node *left = get_binop_left(node);
319 ir_node *right = get_binop_right(node);
321 if (get_irn_op(left) == commutative_op
322 && (!get_irn_outs_computed(left) || get_irn_n_outs(left) == 1)) {
325 obstack_ptr_grow(&commutative_args, left);
328 if (get_irn_op(right) == commutative_op
329 && (!get_irn_outs_computed(right) || get_irn_n_outs(right) == 1)) {
332 obstack_ptr_grow(&commutative_args, right);
337 ir_mode *mode = get_irn_mode(node);
338 if (is_Add(node) && mode_is_reference(mode)) {
339 assert(get_irn_mode(left) == mode || get_irn_mode(right) == mode);
341 assert(get_irn_mode(left) == mode);
342 assert(get_irn_mode(right) == mode);
348 static int compare_nodes(const ir_node *node1, const ir_node *node2)
350 const_class_t class1 = get_const_class(node1, commutative_block);
351 const_class_t class2 = get_const_class(node2, commutative_block);
353 if (class1 == class2)
355 // return get_irn_idx(node1) - get_irn_idx(node2);
360 assert(class1 > class2);
364 static int compare_node_ptr(const void *e1, const void *e2)
366 const ir_node *node1 = *((const ir_node *const*) e1);
367 const ir_node *node2 = *((const ir_node *const*) e2);
368 return compare_nodes(node1, node2);
371 static int reassoc_commutative(ir_node **n)
380 commutative_op = get_irn_op(node);
381 commutative_block = get_nodes_block(node);
383 /* collect all nodes with same op type */
386 n_args = obstack_object_size(&commutative_args) / sizeof(ir_node*);
387 args = obstack_finish(&commutative_args);
389 /* shortcut: in most cases there's nothing to do */
390 if (n_args == 2 && compare_nodes(args[0], args[1]) <= 0) {
391 obstack_free(&commutative_args, args);
395 /* sort the arguments */
396 qsort(args, n_args, sizeof(ir_node*), compare_node_ptr);
399 last = args[n_args-1];
400 mode = get_irn_mode(last);
401 for (i = n_args-2; i >= 0; --i) {
409 /* AddP violates the assumption that all modes in args are equal...
410 * we need some hacks to cope with this */
411 mode_right = get_irn_mode(in[1]);
412 if (mode_is_reference(mode_right)) {
413 assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
414 mode = get_irn_mode(in[1]);
416 if (mode_right != mode) {
417 assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
418 in[1] = new_r_Conv(current_ir_graph, commutative_block,in[1], mode);
421 /* TODO: produce useful debug info! */
422 new_node = new_ir_node(NULL, current_ir_graph, commutative_block,
423 commutative_op, mode, 2, in);
424 new_node = optimize_node(new_node);
428 /* CSE often returns the old node again, only exchange if needed */
430 exchange(node, last);
439 #define reassoc_Add reassoc_commutative
440 #define reassoc_And reassoc_commutative
441 #define reassoc_Or reassoc_commutative
442 #define reassoc_Eor reassoc_commutative
445 * Reassociate using commutative law for Mul and distributive law for Mul and Add/Sub:
447 static int reassoc_Mul(ir_node **node)
450 ir_node *add_sub, *c;
453 if (reassoc_commutative(&n))
456 get_comm_Binop_ops(n, &add_sub, &c);
457 op = get_irn_op(add_sub);
459 /* handles rules R11, R12, R13, R14, R15, R16, R17, R18, R19, R20 */
460 if (op == op_Add || op == op_Sub) {
461 ir_mode *mode = get_irn_mode(n);
462 ir_node *irn, *block, *t1, *t2, *in[2];
464 block = get_nodes_block(n);
465 t1 = get_binop_left(add_sub);
466 t2 = get_binop_right(add_sub);
468 /* we can only multiplication rules on integer arithmetic */
469 if (mode_is_int(get_irn_mode(t1)) && mode_is_int(get_irn_mode(t2))) {
470 in[0] = new_rd_Mul(NULL, block, c, t1, mode);
471 in[1] = new_rd_Mul(NULL, block, c, t2, mode);
473 irn = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
475 /* In some cases it might happen that the new irn is equal the old one, for
477 * (x - 1) * y == x * y - y
478 * will be transformed back by simpler optimization
479 * We could switch simple optimizations off, but this only happens iff y
480 * is a loop-invariant expression and that it is not clear if the new form
482 * So, we let the old one.
485 DBG((dbg, LEVEL_5, "Applied: (%n .%s. %n) %n %n => (%n %n %n) .%s. (%n %n %n)\n",
486 t1, get_op_name(op), t2, n, c, t1, n, c, get_op_name(op), t2, n, c));
498 * Reassociate Shl. We transform Shl(x, const) into Mul's if possible.
500 static int reassoc_Shl(ir_node **node) {
502 ir_node *c = get_Shl_right(n);
503 ir_node *x, *blk, *irn;
511 mode = get_irn_mode(x);
513 tv = get_mode_one(mode);
514 tv = tarval_shl(tv, get_Const_tarval(c));
516 if (tv == tarval_bad)
519 blk = get_nodes_block(n);
521 irn = new_rd_Mul(get_irn_dbg_info(n), blk, x, c, mode);
532 * The walker for the reassociation.
534 static void wq_walker(ir_node *n, void *env)
536 walker_t *wenv = env;
538 set_irn_link(n, NULL);
539 if (is_no_Block(n)) {
540 ir_node *blk = get_nodes_block(n);
542 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
543 /* We are in a dead block, do not optimize or we may fall into an endless
544 loop. We check this here instead of requiring that all dead blocks are removed
545 which or cf_opt do not guarantee yet. */
548 waitq_put(wenv->wq, n);
549 set_irn_link(n, wenv->wq);
554 * The walker for the reassociation.
556 static void do_reassociation(walker_t *wenv)
561 while (! waitq_empty(wenv->wq)) {
562 n = waitq_get(wenv->wq);
563 set_irn_link(n, NULL);
565 blk = get_nodes_block(n);
566 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
567 /* We are in a dead block, do not optimize or we may fall into an endless
568 loop. We check this here instead of requiring that all dead blocks are removed
569 which or cf_opt do not guarantee yet. */
576 /* reassociation must run until a fixpoint is reached. */
579 ir_op *op = get_irn_op(n);
580 ir_mode *mode = get_irn_mode(n);
584 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
585 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
588 if (op->ops.reassociate) {
589 res = op->ops.reassociate(&n);
596 wenv->changes |= changed;
599 for (i = get_irn_arity(n) - 1; i >= 0; --i) {
600 ir_node *pred = get_irn_n(n, i);
602 if (get_irn_link(pred) != wenv->wq) {
603 waitq_put(wenv->wq, pred);
604 set_irn_link(pred, wenv->wq);
609 } /* do_reassociation */
612 * Returns the earliest were a,b are available.
613 * Note that we know that a, b both dominate
614 * the block of the previous operation, so one must dominate the other.
616 * If the earliest block is the start block, return curr_blk instead
618 static ir_node *earliest_block(ir_node *a, ir_node *b, ir_node *curr_blk) {
619 ir_node *blk_a = get_nodes_block(a);
620 ir_node *blk_b = get_nodes_block(b);
623 /* if blk_a != blk_b, one must dominate the other */
624 if (block_dominates(blk_a, blk_b))
628 if (res == get_irg_start_block(current_ir_graph))
631 } /* earliest_block */
634 * Checks whether a node is a Constant expression.
635 * The following trees are constant expressions:
637 * Const, SymConst, Const + SymConst
639 * Handling SymConsts as const might be not a good idea for all
642 static int is_constant_expr(ir_node *irn) {
645 switch (get_irn_opcode(irn)) {
650 op = get_irn_op(get_Add_left(irn));
651 if (op != op_Const && op != op_SymConst)
653 op = get_irn_op(get_Add_right(irn));
654 if (op != op_Const && op != op_SymConst)
660 } /* is_constant_expr */
663 * Apply distributive Law for Mul and Add/Sub
665 static int reverse_rule_distributive(ir_node **node) {
667 ir_node *left = get_binop_left(n);
668 ir_node *right = get_binop_right(n);
669 ir_node *x, *blk, *curr_blk;
670 ir_node *a, *b, *irn;
675 op = get_irn_op(left);
676 if (op != get_irn_op(right))
680 x = get_Shl_right(left);
682 if (x == get_Shl_right(right)) {
683 /* (a << x) +/- (b << x) ==> (a +/- b) << x */
684 a = get_Shl_left(left);
685 b = get_Shl_left(right);
688 } else if (op == op_Mul) {
689 x = get_Mul_left(left);
691 if (x == get_Mul_left(right)) {
692 /* (x * a) +/- (x * b) ==> (a +/- b) * x */
693 a = get_Mul_right(left);
694 b = get_Mul_right(right);
696 } else if (x == get_Mul_right(right)) {
697 /* (x * a) +/- (b * x) ==> (a +/- b) * x */
698 a = get_Mul_right(left);
699 b = get_Mul_left(right);
703 x = get_Mul_right(left);
705 if (x == get_Mul_right(right)) {
706 /* (a * x) +/- (b * x) ==> (a +/- b) * x */
707 a = get_Mul_left(left);
708 b = get_Mul_left(right);
710 } else if (x == get_Mul_left(right)) {
711 /* (a * x) +/- (x * b) ==> (a +/- b) * x */
712 a = get_Mul_left(left);
713 b = get_Mul_right(right);
720 curr_blk = get_nodes_block(n);
722 blk = earliest_block(a, b, curr_blk);
724 dbg = get_irn_dbg_info(n);
725 mode = get_irn_mode(n);
728 irn = new_rd_Add(dbg, blk, a, b, mode);
730 irn = new_rd_Sub(dbg, blk, a, b, mode);
732 blk = earliest_block(irn, x, curr_blk);
735 irn = new_rd_Mul(dbg, blk, irn, x, mode);
737 irn = new_rd_Shl(dbg, blk, irn, x, mode);
742 } /* reverse_rule_distributive */
745 * Move Constants towards the root.
747 static int move_consts_up(ir_node **node) {
750 ir_node *l, *r, *a, *b, *c, *blk, *irn, *in[2];
751 ir_mode *mode, *ma, *mb;
754 l = get_binop_left(n);
755 r = get_binop_right(n);
757 /* check if one is already a constant expression */
758 if (is_constant_expr(l) || is_constant_expr(r))
761 dbg = get_irn_dbg_info(n);
763 if (get_irn_op(l) == op) {
764 /* (a .op. b) .op. r */
765 a = get_binop_left(l);
766 b = get_binop_right(l);
768 if (is_constant_expr(a)) {
769 /* (C .op. b) .op. r ==> (r .op. b) .op. C */
772 blk = get_nodes_block(l);
773 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
775 } else if (is_constant_expr(b)) {
776 /* (a .op. C) .op. r ==> (a .op. r) .op. C */
779 blk = get_nodes_block(l);
780 dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
783 } else if (get_irn_op(r) == op) {
784 /* l .op. (a .op. b) */
785 a = get_binop_left(r);
786 b = get_binop_right(r);
788 if (is_constant_expr(a)) {
789 /* l .op. (C .op. b) ==> (l .op. b) .op. C */
792 blk = get_nodes_block(r);
793 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
795 } else if (is_constant_expr(b)) {
796 /* l .op. (a .op. C) ==> (a .op. l) .op. C */
799 blk = get_nodes_block(r);
800 dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
807 /* In some cases a and b might be both of different integer mode, and c a SymConst.
808 * in that case we could either
809 * 1.) cast into unsigned mode
811 * we implement the second here
813 ma = get_irn_mode(a);
814 mb = get_irn_mode(b);
815 if (ma != mb && mode_is_int(ma) && mode_is_int(mb))
818 /* check if (a .op. b) can be calculated in the same block is the old instruction */
819 if (! block_dominates(get_nodes_block(a), blk))
821 if (! block_dominates(get_nodes_block(b), blk))
827 mode = get_mode_from_ops(a, b);
828 in[0] = irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
830 /* beware: optimize_node might have changed the opcode, check again */
831 if (is_Add(irn) || is_Sub(irn)) {
832 reverse_rule_distributive(&in[0]);
836 mode = get_mode_from_ops(in[0], in[1]);
837 irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
842 } /* move_consts_up */
845 * Apply the rules in reverse order, removing code that was not collapsed
847 static void reverse_rules(ir_node *node, void *env) {
848 walker_t *wenv = env;
849 ir_mode *mode = get_irn_mode(node);
852 /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
853 if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
857 ir_op *op = get_irn_op(node);
860 if (is_op_commutative(op)) {
861 wenv->changes |= res = move_consts_up(&node);
863 /* beware: move_consts_up might have changed the opcode, check again */
864 if (is_Add(node) || is_Sub(node)) {
865 wenv->changes |= res = reverse_rule_distributive(&node);
871 * do the reassociation
873 int optimize_reassociation(ir_graph *irg)
876 irg_loopinfo_state state;
879 assert(get_irg_phase_state(irg) != phase_building);
880 assert(get_irg_pinned(irg) != op_pin_state_floats &&
881 "Reassociation needs pinned graph to work properly");
883 rem = current_ir_graph;
884 current_ir_graph = irg;
886 /* we use dominance to detect dead blocks */
890 assure_irg_outs(irg);
891 obstack_init(&commutative_args);
895 * Calculate loop info, so we could identify loop-invariant
896 * code and threat it like a constant.
897 * We only need control flow loops here but can handle generic
898 * INTRA info as well.
900 state = get_irg_loopinfo_state(irg);
901 if ((state & loopinfo_inter) ||
902 (state & (loopinfo_constructed | loopinfo_valid)) != (loopinfo_constructed | loopinfo_valid))
903 construct_cf_backedges(irg);
906 env.wq = new_waitq();
908 /* disable some optimizations while reassoc is running to prevent endless loops */
909 set_reassoc_running(1);
911 /* now we have collected enough information, optimize */
912 irg_walk_graph(irg, NULL, wq_walker, &env);
913 do_reassociation(&env);
915 /* reverse those rules that do not result in collapsed constants */
916 irg_walk_graph(irg, NULL, reverse_rules, &env);
918 set_reassoc_running(0);
920 /* Handle graph state */
922 set_irg_outs_inconsistent(irg);
923 set_irg_loopinfo_inconsistent(irg);
927 obstack_free(&commutative_args, NULL);
931 current_ir_graph = rem;
933 } /* optimize_reassociation */
935 /* Sets the default reassociation operation for an ir_op_ops. */
936 ir_op_ops *firm_set_default_reassoc(ir_opcode code, ir_op_ops *ops)
938 #define CASE(a) case iro_##a: ops->reassociate = reassoc_##a; break
954 } /* firm_set_default_reassoc */
956 /* initialize the reassociation by adding operations to some opcodes */
957 void firm_init_reassociation(void)
959 FIRM_DBG_REGISTER(dbg, "firm.opt.reassoc");
960 } /* firm_init_reassociation */