3 * File name: ir/ir/iropt.c
4 * Purpose: iropt --- optimizations intertwined with IR construction.
5 * Author: Christian Schaefer
6 * Modified by: Goetz Lindenmaier
9 * Copyright: (c) 1998-2003 Universität Karlsruhe
10 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
17 # include "irnode_t.h"
18 # include "irgraph_t.h"
19 # include "irmode_t.h"
25 # include "dbginfo_t.h"
26 # include "iropt_dbg.h"
27 # include "irflag_t.h"
28 # include "firmstat.h"
30 /* Make types visible to allow most efficient access */
31 # include "entity_t.h"
34 * Trivial INLINEable routine for copy propagation.
35 * Does follow Ids, needed to optimize INLINEd code.
37 static INLINE ir_node *
38 follow_Id (ir_node *n)
40 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
45 * Returns the tarval of a Const node or tarval_bad for all other nodes.
47 static INLINE tarval *
50 if ((n != NULL) && (get_irn_op(n) == op_Const))
51 return get_Const_tarval(n); /* might return tarval_bad */
56 static tarval *computed_value_Const(ir_node *n)
58 return get_Const_tarval(n);
61 static tarval *computed_value_SymConst(ir_node *n)
63 if ((get_SymConst_kind(n) == size) &&
64 (get_type_state(get_SymConst_type(n))) == layout_fixed)
65 return new_tarval_from_long (get_type_size(get_SymConst_type(n)), mode_Is);
69 static tarval *computed_value_Add(ir_node *n)
71 ir_node *a = get_Add_left(n);
72 ir_node *b = get_Add_right(n);
74 tarval *ta = value_of(a);
75 tarval *tb = value_of(b);
77 if ((ta != tarval_bad) && (tb != tarval_bad)
78 && (get_irn_mode(a) == get_irn_mode(b))
79 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
80 return tarval_add(ta, tb);
85 static tarval *computed_value_Sub(ir_node *n)
87 ir_node *a = get_Sub_left(n);
88 ir_node *b = get_Sub_right(n);
90 tarval *ta = value_of(a);
91 tarval *tb = value_of(b);
93 if ((ta != tarval_bad) && (tb != tarval_bad)
94 && (get_irn_mode(a) == get_irn_mode(b))
95 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
96 return tarval_sub(ta, tb);
101 static tarval *computed_value_Minus(ir_node *n)
103 ir_node *a = get_Minus_op(n);
104 tarval *ta = value_of(a);
106 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
107 return tarval_neg(ta);
112 static tarval *computed_value_Mul(ir_node *n)
114 ir_node *a = get_Mul_left(n);
115 ir_node *b = get_Mul_right(n);
117 tarval *ta = value_of(a);
118 tarval *tb = value_of(b);
120 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
121 return tarval_mul(ta, tb);
123 /* a*0 = 0 or 0*b = 0:
124 calls computed_value recursive and returns the 0 with proper
128 if ( ( ((v = ta) != tarval_bad)
129 && (v == get_mode_null(get_tarval_mode(v))) )
130 || ( ((v = tb) != tarval_bad)
131 && (v == get_mode_null(get_tarval_mode(v))) )) {
138 static tarval *computed_value_Quot(ir_node *n)
140 ir_node *a = get_Quot_left(n);
141 ir_node *b = get_Quot_right(n);
143 tarval *ta = value_of(a);
144 tarval *tb = value_of(b);
146 /* This was missing in original implementation. Why? */
147 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
148 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
149 return tarval_quo(ta, tb);
154 static tarval *computed_value_Div(ir_node *n)
156 ir_node *a = get_Div_left(n);
157 ir_node *b = get_Div_right(n);
159 tarval *ta = value_of(a);
160 tarval *tb = value_of(b);
162 /* This was missing in original implementation. Why? */
163 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
164 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
165 return tarval_div(ta, tb);
170 static tarval *computed_value_Mod(ir_node *n)
172 ir_node *a = get_Mod_left(n);
173 ir_node *b = get_Mod_right(n);
175 tarval *ta = value_of(a);
176 tarval *tb = value_of(b);
178 /* This was missing in original implementation. Why? */
179 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
180 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
181 return tarval_mod(ta, tb);
186 static tarval *computed_value_Abs(ir_node *n)
188 ir_node *a = get_Abs_op(n);
189 tarval *ta = value_of(a);
191 if (ta != tarval_bad)
192 return tarval_abs(ta);
197 static tarval *computed_value_And(ir_node *n)
199 ir_node *a = get_And_left(n);
200 ir_node *b = get_And_right(n);
202 tarval *ta = value_of(a);
203 tarval *tb = value_of(b);
205 if ((ta != tarval_bad) && (tb != tarval_bad)) {
206 return tarval_and (ta, tb);
210 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_NULL)
211 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
218 static tarval *computed_value_Or(ir_node *n)
220 ir_node *a = get_Or_left(n);
221 ir_node *b = get_Or_right(n);
223 tarval *ta = value_of(a);
224 tarval *tb = value_of(b);
226 if ((ta != tarval_bad) && (tb != tarval_bad)) {
227 return tarval_or (ta, tb);
230 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
231 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
238 static tarval *computed_value_Eor(ir_node *n)
240 ir_node *a = get_Eor_left(n);
241 ir_node *b = get_Eor_right(n);
243 tarval *ta = value_of(a);
244 tarval *tb = value_of(b);
246 if ((ta != tarval_bad) && (tb != tarval_bad)) {
247 return tarval_eor (ta, tb);
252 static tarval *computed_value_Not(ir_node *n)
254 ir_node *a = get_Not_op(n);
255 tarval *ta = value_of(a);
257 if (ta != tarval_bad)
258 return tarval_not(ta);
263 static tarval *computed_value_Shl(ir_node *n)
265 ir_node *a = get_Shl_left(n);
266 ir_node *b = get_Shl_right(n);
268 tarval *ta = value_of(a);
269 tarval *tb = value_of(b);
271 if ((ta != tarval_bad) && (tb != tarval_bad)) {
272 return tarval_shl (ta, tb);
277 static tarval *computed_value_Shr(ir_node *n)
279 ir_node *a = get_Shr_left(n);
280 ir_node *b = get_Shr_right(n);
282 tarval *ta = value_of(a);
283 tarval *tb = value_of(b);
285 if ((ta != tarval_bad) && (tb != tarval_bad)) {
286 return tarval_shr (ta, tb);
291 static tarval *computed_value_Shrs(ir_node *n)
293 ir_node *a = get_Shrs_left(n);
294 ir_node *b = get_Shrs_right(n);
296 tarval *ta = value_of(a);
297 tarval *tb = value_of(b);
299 if ((ta != tarval_bad) && (tb != tarval_bad)) {
300 return tarval_shrs (ta, tb);
305 static tarval *computed_value_Rot(ir_node *n)
307 ir_node *a = get_Rot_left(n);
308 ir_node *b = get_Rot_right(n);
310 tarval *ta = value_of(a);
311 tarval *tb = value_of(b);
313 if ((ta != tarval_bad) && (tb != tarval_bad)) {
314 /* return tarval_rot (ta, tb); */
319 static tarval *computed_value_Conv(ir_node *n)
321 ir_node *a = get_Conv_op(n);
322 tarval *ta = value_of(a);
324 if (ta != tarval_bad)
325 return tarval_convert_to(ta, get_irn_mode(n));
330 static tarval *computed_value_Proj(ir_node *n)
332 ir_node *a = get_Proj_pred(n), *b;
335 /* Optimize Cmp nodes.
336 This performs a first step of unreachable code elimination.
337 Proj can not be computed, but folding a Cmp above the Proj here is
338 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
340 There are several case where we can evaluate a Cmp node:
341 1. The nodes compared are both the same. If we compare for
342 equal, greater equal, ... this will return true, else it
343 will return false. This step relies on cse.
344 2. The predecessors of Cmp are target values. We can evaluate
346 3. The predecessors are Allocs or void* constants. Allocs never
347 return NULL, they raise an exception. Therefore we can predict
349 if (get_irn_op(a) == op_Cmp) {
350 aa = get_Cmp_left(a);
351 ab = get_Cmp_right(a);
353 if (aa == ab) { /* 1.: */
354 /* This is a tric with the bits used for encoding the Cmp
355 Proj numbers, the following statement is not the same:
356 return new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
357 return new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
359 tarval *taa = computed_value (aa);
360 tarval *tab = computed_value (ab);
362 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
363 /* strange checks... */
364 pnc_number flags = tarval_cmp (taa, tab);
365 if (flags != False) {
366 return new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
368 } else { /* check for 3.: */
369 ir_node *aaa = skip_nop(skip_Proj(aa));
370 ir_node *aba = skip_nop(skip_Proj(ab));
372 if ( ( (/* aa is ProjP and aaa is Alloc */
373 (get_irn_op(aa) == op_Proj)
374 && (mode_is_reference(get_irn_mode(aa)))
375 && (get_irn_op(aaa) == op_Alloc))
376 && ( (/* ab is constant void */
377 (get_irn_op(ab) == op_Const)
378 && (mode_is_reference(get_irn_mode(ab)))
379 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
380 || (/* ab is other Alloc */
381 (get_irn_op(ab) == op_Proj)
382 && (mode_is_reference(get_irn_mode(ab)))
383 && (get_irn_op(aba) == op_Alloc)
385 || (/* aa is void and aba is Alloc */
386 (get_irn_op(aa) == op_Const)
387 && (mode_is_reference(get_irn_mode(aa)))
388 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
389 && (get_irn_op(ab) == op_Proj)
390 && (mode_is_reference(get_irn_mode(ab)))
391 && (get_irn_op(aba) == op_Alloc)))
393 return new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
396 } else if (get_irn_op(a) == op_DivMod) {
397 tarval *tb = value_of(b = get_DivMod_right(a));
398 tarval *ta = value_of(a = get_DivMod_left(a));
400 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
401 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
403 if (get_Proj_proj(n)== 0) /* Div */
404 return tarval_div(ta, tb);
406 return tarval_mod(ta, tb);
413 * If the parameter n can be computed, return its value, else tarval_bad.
414 * Performs constant folding.
416 * GL: Only if n is arithmetic operator?
418 tarval *computed_value(ir_node *n)
420 if (n->op->computed_value)
421 return n->op->computed_value(n);
426 * set the default computed_value evaluator
428 static ir_op *firm_set_default_computed_value(ir_op *op)
432 op->computed_value = computed_value_##a; \
457 op->computed_value = NULL;
465 /* returns 1 if the a and b are pointers to different locations. */
467 different_identity (ir_node *a, ir_node *b)
469 assert (mode_is_reference(get_irn_mode (a))
470 && mode_is_reference(get_irn_mode (b)));
472 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
473 ir_node *a1 = get_Proj_pred (a);
474 ir_node *b1 = get_Proj_pred (b);
475 if (a1 != b1 && get_irn_op (a1) == op_Alloc
476 && get_irn_op (b1) == op_Alloc)
483 static ir_node *equivalent_node_Block(ir_node *n)
487 /* The Block constructor does not call optimize, but mature_block
488 calls the optimization. */
489 assert(get_Block_matured(n));
491 /* Straightening: a single entry Block following a single exit Block
492 can be merged, if it is not the Start block. */
493 /* !!! Beware, all Phi-nodes of n must have been optimized away.
494 This should be true, as the block is matured before optimize is called.
495 But what about Phi-cycles with the Phi0/Id that could not be resolved?
496 Remaining Phi nodes are just Ids. */
497 if ((get_Block_n_cfgpreds(n) == 1) &&
498 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
499 (get_opt_control_flow_straightening())) {
500 n = get_nodes_Block(get_Block_cfgpred(n, 0));
502 /* Jmp jumps into the block it is in -- deal self cycle. */
503 n = new_Bad(); DBG_OPT_DEAD;
508 } else if ((get_Block_n_cfgpreds(n) == 2) &&
509 (get_opt_control_flow_weak_simplification())) {
510 /* Test whether Cond jumps twice to this block
511 @@@ we could do this also with two loops finding two preds from several ones. */
512 ir_node *a = get_Block_cfgpred(n, 0);
513 ir_node *b = get_Block_cfgpred(n, 1);
515 if ((get_irn_op(a) == op_Proj) &&
516 (get_irn_op(b) == op_Proj) &&
517 (get_Proj_pred(a) == get_Proj_pred(b)) &&
518 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
519 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
520 /* Also a single entry Block following a single exit Block. Phis have
521 twice the same operand and will be optimized away. */
522 n = get_nodes_Block(a); DBG_OPT_IFSIM;
524 } else if (get_opt_unreachable_code() &&
525 (n != current_ir_graph->start_block) &&
526 (n != current_ir_graph->end_block) ) {
528 /* If all inputs are dead, this block is dead too, except if it is
529 the start or end block. This is a step of unreachable code
531 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
532 if (!is_Bad(get_Block_cfgpred(n, i))) break;
534 if (i == get_Block_n_cfgpreds(n))
541 static ir_node *equivalent_node_Jmp(ir_node *n)
543 /* GL: Why not same for op_Raise?? */
544 /* unreachable code elimination */
545 if (is_Bad(get_nodes_Block(n)))
551 static ir_node *equivalent_node_Cond(ir_node *n)
553 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
554 See cases for iro_Cond and iro_Proj in transform_node. */
558 static ir_node *equivalent_node_Or(ir_node *n)
562 ir_node *a = get_Or_left(n);
563 ir_node *b = get_Or_right(n);
567 n = a; DBG_OPT_ALGSIM1;
574 * optimize operations that are commutative and have neutral 0.
576 static ir_node *equivalent_node_neutral_zero(ir_node *n)
580 ir_node *a = get_binop_left(n);
581 ir_node *b = get_binop_right(n);
586 /* After running compute_node there is only one constant predecessor.
587 Find this predecessors value and remember the other node: */
588 if ((tv = computed_value (a)) != tarval_bad) {
590 } else if ((tv = computed_value (b)) != tarval_bad) {
595 /* If this predecessors constant value is zero, the operation is
596 unnecessary. Remove it: */
597 if (tarval_classify (tv) == TV_CLASSIFY_NULL) {
598 n = on; DBG_OPT_ALGSIM1;
604 static ir_node *equivalent_node_Add(ir_node *n)
606 return equivalent_node_neutral_zero(n);
609 static ir_node *equivalent_node_Eor(ir_node *n)
611 return equivalent_node_neutral_zero(n);
615 * optimize operations that are not commutative but have neutral 0 on left.
616 * Test only one predecessor.
618 static ir_node *equivalent_node_left_zero(ir_node *n)
622 ir_node *a = get_binop_left(n);
623 ir_node *b = get_binop_right(n);
625 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_NULL) {
626 n = a; DBG_OPT_ALGSIM1;
632 static ir_node *equivalent_node_Sub(ir_node *n)
634 return equivalent_node_left_zero(n);
637 static ir_node *equivalent_node_Shl(ir_node *n)
639 return equivalent_node_left_zero(n);
642 static ir_node *equivalent_node_Shr(ir_node *n)
644 return equivalent_node_left_zero(n);
647 static ir_node *equivalent_node_Shrs(ir_node *n)
649 return equivalent_node_left_zero(n);
652 static ir_node *equivalent_node_Rot(ir_node *n)
654 return equivalent_node_left_zero(n);
657 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
661 /* optimize symmetric unop */
662 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
663 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
668 static ir_node *equivalent_node_Not(ir_node *n)
671 return equivalent_node_symmetric_unop(n);
674 static ir_node *equivalent_node_Minus(ir_node *n)
676 /* --x == x */ /* ??? Is this possible or can --x raise an
677 out of bounds exception if min =! max? */
678 return equivalent_node_symmetric_unop(n);
681 static ir_node *equivalent_node_Mul(ir_node *n)
685 ir_node *a = get_Mul_left(n);
686 ir_node *b = get_Mul_right(n);
688 /* Mul is commutative and has again an other neutral element. */
689 if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ONE) {
690 n = b; DBG_OPT_ALGSIM1;
691 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) {
692 n = a; DBG_OPT_ALGSIM1;
697 static ir_node *equivalent_node_Div(ir_node *n)
699 ir_node *a = get_Div_left(n);
700 ir_node *b = get_Div_right(n);
702 /* Div is not commutative. */
703 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
704 /* Turn Div into a tuple (mem, bad, a) */
705 ir_node *mem = get_Div_mem(n);
706 turn_into_tuple(n, 3);
707 set_Tuple_pred(n, pn_Div_M, mem);
708 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
709 set_Tuple_pred(n, pn_Div_res, a);
714 static ir_node *equivalent_node_And(ir_node *n)
718 ir_node *a = get_And_left(n);
719 ir_node *b = get_And_right(n);
722 n = a; /* And has it's own neutral element */
723 } else if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ALL_ONE) {
725 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ALL_ONE) {
728 if (n != oldn) DBG_OPT_ALGSIM1;
732 static ir_node *equivalent_node_Conv(ir_node *n)
735 ir_node *a = get_Conv_op(n);
738 ir_mode *n_mode = get_irn_mode(n);
739 ir_mode *a_mode = get_irn_mode(a);
741 if (n_mode == a_mode) { /* No Conv necessary */
742 n = a; DBG_OPT_ALGSIM3;
743 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
747 n_mode = get_irn_mode(n);
748 b_mode = get_irn_mode(b);
750 if (n_mode == b_mode) {
751 if (n_mode == mode_b) {
752 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM1;
754 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
755 if (smaller_mode(b_mode, a_mode)){
756 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ DBG_OPT_ALGSIM1;
764 static ir_node *equivalent_node_Phi(ir_node *n)
766 /* Several optimizations:
767 - no Phi in start block.
768 - remove Id operators that are inputs to Phi
769 - fold Phi-nodes, iff they have only one predecessor except
775 ir_node *block = NULL; /* to shutup gcc */
776 ir_node *first_val = NULL; /* to shutup gcc */
777 ir_node *scnd_val = NULL; /* to shutup gcc */
779 if (!get_opt_normalize()) return n;
781 n_preds = get_Phi_n_preds(n);
783 block = get_nodes_block(n);
784 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
785 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
786 if ((is_Bad(block)) || /* Control dead */
787 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
788 return new_Bad(); /* in the Start Block. */
790 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
793 /* first we test for a special case: */
794 /* Confirm is a special node fixing additional information for a
795 value that is known at a certain point. This is useful for
796 dataflow analysis. */
798 ir_node *a = get_Phi_pred(n, 0);
799 ir_node *b = get_Phi_pred(n, 1);
800 if ( (get_irn_op(a) == op_Confirm)
801 && (get_irn_op(b) == op_Confirm)
802 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
803 && (get_irn_n(a, 1) == get_irn_n (b, 1))
804 && (a->data.num == (~b->data.num & irpn_True) )) {
805 return get_irn_n(a, 0);
810 /* If the Block has a Bad pred, we also have one. */
811 for (i = 0; i < n_preds; ++i)
812 if (is_Bad (get_Block_cfgpred(block, i)))
813 set_Phi_pred(n, i, new_Bad());
815 /* Find first non-self-referencing input */
816 for (i = 0; i < n_preds; ++i) {
817 first_val = get_Phi_pred(n, i);
818 if ( (first_val != n) /* not self pointer */
820 && (get_irn_op(first_val) != op_Bad)
822 ) { /* value not dead */
823 break; /* then found first value. */
827 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
828 if (i >= n_preds) { return new_Bad(); }
832 /* follow_Id () for rest of inputs, determine if any of these
833 are non-self-referencing */
834 while (++i < n_preds) {
835 scnd_val = get_Phi_pred(n, i);
837 && (scnd_val != first_val)
839 && (get_irn_op(scnd_val) != op_Bad)
846 /* Fold, if no multiple distinct non-self-referencing inputs */
848 n = first_val; DBG_OPT_PHI;
850 /* skip the remaining Ids (done in get_Phi_pred). */
851 /* superfluous, since we walk all to propagate Block's Bads.
852 while (++i < n_preds) get_Phi_pred(n, i); */
857 static ir_node *equivalent_node_Load(ir_node *n)
859 #if 0 /* Is an illegal transformation: different nodes can
860 represent the same pointer value!! */
861 ir_node *a = skip_Proj(get_Load_mem(n));
862 ir_node *b = get_Load_ptr(n);
864 if (get_irn_op(a) == op_Store) {
865 if ( different_identity (b, get_Store_ptr(a))) {
866 /* load and store use different pointers, therefore load
867 needs not take store's memory but the state before. */
868 set_Load_mem (n, get_Store_mem(a));
869 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
876 static ir_node *equivalent_node_Store(ir_node *n)
880 /* remove unnecessary store. */
881 ir_node *a = skip_Proj(get_Store_mem(n));
882 ir_node *b = get_Store_ptr(n);
883 ir_node *c = skip_Proj(get_Store_value(n));
885 if (get_irn_op(a) == op_Store
886 && get_Store_ptr(a) == b
887 && skip_Proj(get_Store_value(a)) == c) {
888 /* We have twice exactly the same store -- a write after write. */
890 } else if (get_irn_op(c) == op_Load
891 && (a == c || skip_Proj(get_Load_mem(c)) == a)
892 && get_Load_ptr(c) == b ) {
893 /* We just loaded the value from the same memory, i.e., the store
894 doesn't change the memory -- a write after read. */
895 a = get_Store_mem(n);
896 turn_into_tuple(n, 2);
897 set_Tuple_pred(n, pn_Store_M, a);
898 set_Tuple_pred(n, pn_Store_X_except, new_Bad()); DBG_OPT_WAR;
903 static ir_node *equivalent_node_Proj(ir_node *n)
907 ir_node *a = get_Proj_pred(n);
909 if ( get_irn_op(a) == op_Tuple) {
910 /* Remove the Tuple/Proj combination. */
911 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
912 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
914 assert(0); /* This should not happen! */
917 } else if (get_irn_mode(n) == mode_X &&
918 is_Bad(get_nodes_Block(n))) {
919 /* Remove dead control flow -- early gigo. */
925 static ir_node *equivalent_node_Id(ir_node *n)
929 n = follow_Id (n); DBG_OPT_ID;
934 case iro_Mod, Quot, DivMod
935 DivMod allocates new nodes --> it's treated in transform node.
936 What about Quot, DivMod?
940 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
941 * perform no actual computation, as, e.g., the Id nodes. It does not create
942 * new nodes. It is therefore safe to free n if the node returned is not n.
943 * If a node returns a Tuple we can not just skip it. If the size of the
944 * in array fits, we transform n into a tuple (e.g., Div).
947 equivalent_node (ir_node *n)
949 if (n->op->equivalent_node)
950 return n->op->equivalent_node(n);
955 * set the default equivalent node operation
957 static ir_op *firm_set_default_equivalent_node(ir_op *op)
961 op->equivalent_node = equivalent_node_##a; \
988 op->equivalent_node = NULL;
996 * Do node specific optimizations of nodes predecessors.
999 optimize_preds(ir_node *n) {
1000 ir_node *a = NULL, *b = NULL;
1002 /* get the operands we will work on for simple cases. */
1004 a = get_binop_left(n);
1005 b = get_binop_right(n);
1006 } else if (is_unop(n)) {
1010 switch (get_irn_opcode(n)) {
1013 /* We don't want Cast as input to Cmp. */
1014 if (get_irn_op(a) == op_Cast) {
1018 if (get_irn_op(b) == op_Cast) {
1020 set_Cmp_right(n, b);
1028 static ir_node *transform_node_Div(ir_node *n)
1030 tarval *ta = computed_value(n);
1032 if (ta != tarval_bad) {
1033 /* Turn Div into a tuple (mem, bad, value) */
1034 ir_node *mem = get_Div_mem(n);
1036 turn_into_tuple(n, 3);
1037 set_Tuple_pred(n, pn_Div_M, mem);
1038 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1039 set_Tuple_pred(n, pn_Div_res, new_Const(get_tarval_mode(ta), ta));
1044 static ir_node *transform_node_Mod(ir_node *n)
1046 tarval *ta = computed_value(n);
1048 if (ta != tarval_bad) {
1049 /* Turn Mod into a tuple (mem, bad, value) */
1050 ir_node *mem = get_Mod_mem(n);
1051 turn_into_tuple(n, 3);
1052 set_Tuple_pred(n, pn_Mod_M, mem);
1053 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1054 set_Tuple_pred(n, pn_Mod_res, new_Const(get_tarval_mode(ta), ta));
1059 static ir_node *transform_node_DivMod(ir_node *n)
1063 ir_node *a = get_DivMod_left(n);
1064 ir_node *b = get_DivMod_right(n);
1065 ir_mode *mode = get_irn_mode(a);
1067 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1071 a = new_Const(mode, get_mode_one(mode));
1072 b = new_Const(mode, get_mode_null(mode));
1075 tarval *ta = value_of(a);
1076 tarval *tb = value_of(b);
1078 if (tb != tarval_bad) {
1079 if (tb == get_mode_one(get_tarval_mode(tb))) {
1080 b = new_Const (mode, get_mode_null(mode));
1082 } else if (ta != tarval_bad) {
1083 tarval *resa, *resb;
1084 resa = tarval_div (ta, tb);
1085 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1086 Jmp for X result!? */
1087 resb = tarval_mod (ta, tb);
1088 if (resb == tarval_bad) return n; /* Causes exception! */
1089 a = new_Const (mode, resa);
1090 b = new_Const (mode, resb);
1093 } else if (ta == get_mode_null(mode)) {
1098 if (evaluated) { /* replace by tuple */
1099 ir_node *mem = get_DivMod_mem(n);
1100 turn_into_tuple(n, 4);
1101 set_Tuple_pred(n, pn_DivMod_M, mem);
1102 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1103 set_Tuple_pred(n, pn_DivMod_res_div, a);
1104 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1105 assert(get_nodes_Block(n));
1111 static ir_node *transform_node_Cond(ir_node *n)
1113 /* Replace the Cond by a Jmp if it branches on a constant
1116 ir_node *a = get_Cond_selector(n);
1117 tarval *ta = value_of(a);
1119 if ((ta != tarval_bad) &&
1120 (get_irn_mode(a) == mode_b) &&
1121 (get_opt_unreachable_code())) {
1122 /* It's a boolean Cond, branching on a boolean constant.
1123 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1124 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
1125 turn_into_tuple(n, 2);
1126 if (ta == tarval_b_true) {
1127 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1128 set_Tuple_pred(n, pn_Cond_true, jmp);
1130 set_Tuple_pred(n, pn_Cond_false, jmp);
1131 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1133 /* We might generate an endless loop, so keep it alive. */
1134 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
1135 } else if ((ta != tarval_bad) &&
1136 (get_irn_mode(a) == mode_Iu) &&
1137 (get_Cond_kind(n) == dense) &&
1138 (get_opt_unreachable_code())) {
1139 /* I don't want to allow Tuples smaller than the biggest Proj.
1140 Also this tuple might get really big...
1141 I generate the Jmp here, and remember it in link. Link is used
1142 when optimizing Proj. */
1143 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
1144 /* We might generate an endless loop, so keep it alive. */
1145 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
1146 } else if ((get_irn_op(a) == op_Eor)
1147 && (get_irn_mode(a) == mode_b)
1148 && (tarval_classify(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1149 /* The Eor is a negate. Generate a new Cond without the negate,
1150 simulate the negate by exchanging the results. */
1151 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
1153 } else if ((get_irn_op(a) == op_Not)
1154 && (get_irn_mode(a) == mode_b)) {
1155 /* A Not before the Cond. Generate a new Cond without the Not,
1156 simulate the Not by exchanging the results. */
1157 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
1163 static ir_node *transform_node_Eor(ir_node *n)
1165 ir_node *a = get_Eor_left(n);
1166 ir_node *b = get_Eor_right(n);
1168 if ((get_irn_mode(n) == mode_b)
1169 && (get_irn_op(a) == op_Proj)
1170 && (get_irn_mode(a) == mode_b)
1171 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE)
1172 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1173 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1174 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
1175 mode_b, get_negated_pnc(get_Proj_proj(a)));
1176 else if ((get_irn_mode(n) == mode_b)
1177 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE))
1178 /* The Eor is a Not. Replace it by a Not. */
1179 /* ????!!!Extend to bitfield 1111111. */
1180 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
1185 static ir_node *transform_node_Not(ir_node *n)
1187 ir_node *a = get_Not_op(n);
1189 if ( (get_irn_mode(n) == mode_b)
1190 && (get_irn_op(a) == op_Proj)
1191 && (get_irn_mode(a) == mode_b)
1192 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1193 /* We negate a Cmp. The Cmp has the negated result anyways! */
1194 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
1195 mode_b, get_negated_pnc(get_Proj_proj(a)));
1202 * Tries several [inplace] [optimizing] transformations and returns an
1203 * equivalent node. The difference to equivalent_node() is that these
1204 * transformations _do_ generate new nodes, and thus the old node must
1205 * not be freed even if the equivalent node isn't the old one.
1207 static ir_node *transform_node(ir_node *n)
1209 if (n->op->transform_node)
1210 n = n->op->transform_node(n);
1215 * set the default transform node operation
1217 static ir_op *firm_set_default_transform_node(ir_op *op)
1221 op->transform_node = transform_node_##a; \
1232 op->transform_node = NULL;
1240 /* **************** Common Subexpression Elimination **************** */
1242 /** The size of the hash table used, should estimate the number of nodes
1244 #define N_IR_NODES 512
1246 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1248 return (get_Const_tarval(a) != get_Const_tarval(b))
1249 || (get_Const_type(a) != get_Const_type(b));
1252 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1254 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1257 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1259 return get_Filter_proj(a) != get_Filter_proj(b);
1262 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1264 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1265 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1268 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1270 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1273 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1275 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1276 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
1279 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1281 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1284 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1286 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1289 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1291 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1292 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1293 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1294 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1295 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1298 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1300 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1303 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1305 return get_Cast_type(a) != get_Cast_type(b);
1309 * set the default node attribute compare operation
1311 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1315 op->node_cmp_attr = node_cmp_attr_##a; \
1331 op->node_cmp_attr = NULL;
1339 * Compare function for two nodes in the hash table. Gets two
1340 * nodes as parameters. Returns 0 if the nodes are a cse.
1343 vt_cmp (const void *elt, const void *key)
1351 if (a == b) return 0;
1353 if ((get_irn_op(a) != get_irn_op(b)) ||
1354 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1356 /* compare if a's in and b's in are equal */
1357 irn_arity_a = get_irn_arity (a);
1358 if (irn_arity_a != get_irn_arity(b))
1361 /* for block-local cse and pinned nodes: */
1362 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
1363 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1367 /* compare a->in[0..ins] with b->in[0..ins] */
1368 for (i = 0; i < irn_arity_a; i++)
1369 if (get_irn_n(a, i) != get_irn_n(b, i))
1373 * here, we already now that the nodes are identical except their
1376 if (a->op->node_cmp_attr)
1377 return a->op->node_cmp_attr(a, b);
1383 * Calculate a hash value of a node.
1386 ir_node_hash (ir_node *node)
1391 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1392 h = irn_arity = get_irn_arity(node);
1394 /* consider all in nodes... except the block. */
1395 for (i = 0; i < irn_arity; i++) {
1396 h = 9*h + (unsigned long)get_irn_n(node, i);
1400 h = 9*h + (unsigned long) get_irn_mode (node);
1402 h = 9*h + (unsigned long) get_irn_op (node);
1408 new_identities (void)
1410 return new_pset (vt_cmp, N_IR_NODES);
1414 del_identities (pset *value_table)
1416 del_pset (value_table);
1420 * Return the canonical node computing the same value as n.
1421 * Looks up the node in a hash table.
1423 static INLINE ir_node *
1424 identify (pset *value_table, ir_node *n)
1428 if (!value_table) return n;
1430 /* TODO: use a generic commutative attribute */
1431 if (get_opt_reassociation()) {
1432 if (is_op_commutative(get_irn_op(n))) {
1433 /* for commutative operators perform a OP b == b OP a */
1434 if (get_binop_left(n) > get_binop_right(n)) {
1435 ir_node *h = get_binop_left(n);
1436 set_binop_left(n, get_binop_right(n));
1437 set_binop_right(n, h);
1442 o = pset_find (value_table, n, ir_node_hash (n));
1449 * During construction we set the pinned flag in the graph right when the
1450 * optimizatin is performed. The flag turning on procedure global cse could
1451 * be changed between two allocations. This way we are safe.
1453 static INLINE ir_node *
1454 identify_cons (pset *value_table, ir_node *n) {
1456 n = identify(value_table, n);
1457 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1458 set_irg_pinned(current_ir_graph, floats);
1463 * Return the canonical node computing the same value as n.
1464 * Looks up the node in a hash table, enters it in the table
1465 * if it isn't there yet.
1468 identify_remember (pset *value_table, ir_node *node)
1472 if (!value_table) return node;
1474 /* lookup or insert in hash table with given hash key. */
1475 o = pset_insert (value_table, node, ir_node_hash (node));
1477 if (o == node) return node;
1483 add_identities (pset *value_table, ir_node *node) {
1484 identify_remember (value_table, node);
1488 * garbage in, garbage out. If a node has a dead input, i.e., the
1489 * Bad node is input to the node, return the Bad node.
1491 static INLINE ir_node *
1492 gigo (ir_node *node)
1495 ir_op* op = get_irn_op(node);
1497 /* remove garbage blocks by looking at control flow that leaves the block
1498 and replacing the control flow by Bad. */
1499 if (get_irn_mode(node) == mode_X) {
1500 ir_node *block = get_nodes_block(node);
1501 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1502 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1503 irn_arity = get_irn_arity(block);
1504 for (i = 0; i < irn_arity; i++) {
1505 if (!is_Bad(get_irn_n(block, i))) break;
1507 if (i == irn_arity) return new_Bad();
1511 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1512 blocks predecessors is dead. */
1513 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1514 irn_arity = get_irn_arity(node);
1515 for (i = -1; i < irn_arity; i++) {
1516 if (is_Bad(get_irn_n(node, i))) {
1522 /* With this code we violate the agreement that local_optimize
1523 only leaves Bads in Block, Phi and Tuple nodes. */
1524 /* If Block has only Bads as predecessors it's garbage. */
1525 /* If Phi has only Bads as predecessors it's garbage. */
1526 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1527 irn_arity = get_irn_arity(node);
1528 for (i = 0; i < irn_arity; i++) {
1529 if (!is_Bad(get_irn_n(node, i))) break;
1531 if (i == irn_arity) node = new_Bad();
1539 * These optimizations deallocate nodes from the obstack.
1540 * It can only be called if it is guaranteed that no other nodes
1541 * reference this one, i.e., right after construction of a node.
1544 optimize_node (ir_node *n)
1548 opcode iro = get_irn_opcode(n);
1550 /* Allways optimize Phi nodes: part of the construction. */
1551 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1553 /* constant expression evaluation / constant folding */
1554 if (get_opt_constant_folding()) {
1555 /* constants can not be evaluated */
1556 if (iro != iro_Const) {
1557 /* try to evaluate */
1558 tv = computed_value (n);
1559 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1561 * we MUST copy the node here temparary, because it's still needed
1562 * for DBG_OPT_ALGSIM0
1566 /* evaluation was successful -- replace the node. */
1567 obstack_free (current_ir_graph->obst, n);
1568 n = new_Const (get_tarval_mode (tv), tv);
1575 /* remove unnecessary nodes */
1576 if (get_opt_constant_folding() ||
1577 (iro == iro_Phi) || /* always optimize these nodes. */
1579 (iro == iro_Proj) ||
1580 (iro == iro_Block) ) /* Flags tested local. */
1581 n = equivalent_node (n);
1583 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1585 /** common subexpression elimination **/
1586 /* Checks whether n is already available. */
1587 /* The block input is used to distinguish different subexpressions. Right
1588 now all nodes are pinned to blocks, i.e., the cse only finds common
1589 subexpressions within a block. */
1591 n = identify_cons (current_ir_graph->value_table, n);
1594 /* We found an existing, better node, so we can deallocate the old node. */
1595 obstack_free (current_ir_graph->obst, oldn);
1600 /* Some more constant expression evaluation that does not allow to
1602 iro = get_irn_opcode(n);
1603 if (get_opt_constant_folding() ||
1604 (iro == iro_Cond) ||
1605 (iro == iro_Proj)) /* Flags tested local. */
1606 n = transform_node (n);
1608 /* Remove nodes with dead (Bad) input.
1609 Run always for transformation induced Bads. */
1612 /* Now we have a legal, useful node. Enter it in hash table for cse */
1613 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1614 n = identify_remember (current_ir_graph->value_table, n);
1622 * These optimizations never deallocate nodes. This can cause dead
1623 * nodes lying on the obstack. Remove these by a dead node elimination,
1624 * i.e., a copying garbage collection.
1627 optimize_in_place_2 (ir_node *n)
1631 opcode iro = get_irn_opcode(n);
1633 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1635 /* if not optimize return n */
1638 /* Here this is possible. Why? */
1643 /* constant expression evaluation / constant folding */
1644 if (get_opt_constant_folding()) {
1645 /* constants can not be evaluated */
1646 if (iro != iro_Const) {
1647 /* try to evaluate */
1648 tv = computed_value (n);
1649 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1650 /* evaluation was successful -- replace the node. */
1651 n = new_Const (get_tarval_mode (tv), tv);
1658 /* remove unnecessary nodes */
1659 /*if (get_opt_constant_folding()) */
1660 if (get_opt_constant_folding() ||
1661 (iro == iro_Phi) || /* always optimize these nodes. */
1662 (iro == iro_Id) || /* ... */
1663 (iro == iro_Proj) || /* ... */
1664 (iro == iro_Block) ) /* Flags tested local. */
1665 n = equivalent_node (n);
1667 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1669 /** common subexpression elimination **/
1670 /* Checks whether n is already available. */
1671 /* The block input is used to distinguish different subexpressions. Right
1672 now all nodes are pinned to blocks, i.e., the cse only finds common
1673 subexpressions within a block. */
1674 if (get_opt_cse()) {
1675 n = identify (current_ir_graph->value_table, n);
1678 /* Some more constant expression evaluation. */
1679 iro = get_irn_opcode(n);
1680 if (get_opt_constant_folding() ||
1681 (iro == iro_Cond) ||
1682 (iro == iro_Proj)) /* Flags tested local. */
1683 n = transform_node (n);
1685 /* Remove nodes with dead (Bad) input.
1686 Run always for transformation induced Bads. */
1689 /* Now we can verify the node, as it has no dead inputs any more. */
1692 /* Now we have a legal, useful node. Enter it in hash table for cse.
1693 Blocks should be unique anyways. (Except the successor of start:
1694 is cse with the start block!) */
1695 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1696 n = identify_remember (current_ir_graph->value_table, n);
1702 * Wrapper for external use, set proper status bits after optimization.
1705 optimize_in_place (ir_node *n)
1707 /* Handle graph state */
1708 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1710 if (get_opt_global_cse())
1711 set_irg_pinned(current_ir_graph, floats);
1712 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1713 set_irg_outs_inconsistent(current_ir_graph);
1714 /* Maybe we could also test whether optimizing the node can
1715 change the control graph. */
1716 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1717 set_irg_dom_inconsistent(current_ir_graph);
1718 return optimize_in_place_2 (n);
1722 * set the default ir op operations
1724 ir_op *firm_set_default_operations(ir_op *op)
1726 op = firm_set_default_computed_value(op);
1727 op = firm_set_default_equivalent_node(op);
1728 op = firm_set_default_transform_node(op);
1729 op = firm_set_default_node_cmp_attr(op);