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"
21 # include "ircons_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) ==symconst_size) &&
64 (get_type_state(get_SymConst_type(n))) == layout_fixed)
65 return new_tarval_from_long(get_type_size_bytes(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 tarval *computed_value(ir_node *n)
418 if (n->op->computed_value)
419 return n->op->computed_value(n);
424 * set the default computed_value evaluator
426 static ir_op *firm_set_default_computed_value(ir_op *op)
430 op->computed_value = computed_value_##a; \
455 op->computed_value = NULL;
463 /* returns 1 if the a and b are pointers to different locations. */
465 different_identity (ir_node *a, ir_node *b)
467 assert (mode_is_reference(get_irn_mode (a))
468 && mode_is_reference(get_irn_mode (b)));
470 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
471 ir_node *a1 = get_Proj_pred (a);
472 ir_node *b1 = get_Proj_pred (b);
473 if (a1 != b1 && get_irn_op (a1) == op_Alloc
474 && get_irn_op (b1) == op_Alloc)
481 static ir_node *equivalent_node_Block(ir_node *n)
485 /* The Block constructor does not call optimize, but mature_block
486 calls the optimization. */
487 assert(get_Block_matured(n));
489 /* Straightening: a single entry Block following a single exit Block
490 can be merged, if it is not the Start block. */
491 /* !!! Beware, all Phi-nodes of n must have been optimized away.
492 This should be true, as the block is matured before optimize is called.
493 But what about Phi-cycles with the Phi0/Id that could not be resolved?
494 Remaining Phi nodes are just Ids. */
495 if ((get_Block_n_cfgpreds(n) == 1) &&
496 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
497 ir_node *predblock = get_nodes_Block(get_Block_cfgpred(n, 0));
498 if (predblock == oldn) {
499 /* Jmp jumps into the block it is in -- deal self cycle. */
500 n = new_Bad(); DBG_OPT_DEAD;
501 } else if (get_opt_control_flow_straightening()) {
502 n = predblock; DBG_OPT_STG;
505 else if ((get_Block_n_cfgpreds(n) == 1) &&
506 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
507 ir_node *predblock = get_nodes_Block(get_Block_cfgpred(n, 0));
508 if (predblock == oldn) {
509 /* Jmp jumps into the block it is in -- deal self cycle. */
510 n = new_Bad(); DBG_OPT_DEAD;
513 else if ((get_Block_n_cfgpreds(n) == 2) &&
514 (get_opt_control_flow_weak_simplification())) {
515 /* Test whether Cond jumps twice to this block
516 @@@ we could do this also with two loops finding two preds from several ones. */
517 ir_node *a = get_Block_cfgpred(n, 0);
518 ir_node *b = get_Block_cfgpred(n, 1);
520 if ((get_irn_op(a) == op_Proj) &&
521 (get_irn_op(b) == op_Proj) &&
522 (get_Proj_pred(a) == get_Proj_pred(b)) &&
523 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
524 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
525 /* Also a single entry Block following a single exit Block. Phis have
526 twice the same operand and will be optimized away. */
527 n = get_nodes_Block(a); DBG_OPT_IFSIM;
529 } else if (get_opt_unreachable_code() &&
530 (n != current_ir_graph->start_block) &&
531 (n != current_ir_graph->end_block) ) {
533 /* If all inputs are dead, this block is dead too, except if it is
534 the start or end block. This is a step of unreachable code
536 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
537 if (!is_Bad(get_Block_cfgpred(n, i))) break;
539 if (i == get_Block_n_cfgpreds(n))
547 * Returns a equivalent node for a Jmp, a Bad :-)
548 * Of course this only happens if the Block of the Jmp is Bad.
550 static ir_node *equivalent_node_Jmp(ir_node *n)
552 /* GL: Why not same for op_Raise?? */
553 /* unreachable code elimination */
554 if (is_Bad(get_nodes_Block(n)))
560 static ir_node *equivalent_node_Cond(ir_node *n)
562 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
563 See cases for iro_Cond and iro_Proj in transform_node. */
568 * Use algebraic simplification a v a = a.
570 static ir_node *equivalent_node_Or(ir_node *n)
574 ir_node *a = get_Or_left(n);
575 ir_node *b = get_Or_right(n);
579 n = a; DBG_OPT_ALGSIM1;
586 * optimize operations that are commutative and have neutral 0,
587 * so a op 0 = 0 op a = a.
589 static ir_node *equivalent_node_neutral_zero(ir_node *n)
593 ir_node *a = get_binop_left(n);
594 ir_node *b = get_binop_right(n);
599 /* After running compute_node there is only one constant predecessor.
600 Find this predecessors value and remember the other node: */
601 if ((tv = computed_value(a)) != tarval_bad) {
603 } else if ((tv = computed_value(b)) != tarval_bad) {
608 /* If this predecessors constant value is zero, the operation is
609 unnecessary. Remove it: */
610 if (tarval_classify (tv) == TV_CLASSIFY_NULL) {
611 n = on; DBG_OPT_ALGSIM1;
617 #define equivalent_node_Add equivalent_node_neutral_zero
618 #define equivalent_node_Eor equivalent_node_neutral_zero
621 * optimize operations that are not commutative but have neutral 0 on left,
624 static ir_node *equivalent_node_left_zero(ir_node *n)
628 ir_node *a = get_binop_left(n);
629 ir_node *b = get_binop_right(n);
631 if (tarval_classify(computed_value(b)) == TV_CLASSIFY_NULL) {
632 n = a; DBG_OPT_ALGSIM1;
638 #define equivalent_node_Sub equivalent_node_left_zero
639 #define equivalent_node_Shl equivalent_node_left_zero
640 #define equivalent_node_Shr equivalent_node_left_zero
641 #define equivalent_node_Shrs equivalent_node_left_zero
642 #define equivalent_node_Rot equivalent_node_left_zero
645 * Er, a "symmetic unop", ie op(op(n)) = n.
647 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
651 /* optimize symmetric unop */
652 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
653 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
659 #define equivalent_node_Not equivalent_node_symmetric_unop
661 /* --x == x */ /* ??? Is this possible or can --x raise an
662 out of bounds exception if min =! max? */
663 #define equivalent_node_Minus equivalent_node_symmetric_unop
666 * Optimize a * 1 = 1 * a = a.
668 static ir_node *equivalent_node_Mul(ir_node *n)
672 ir_node *a = get_Mul_left(n);
673 ir_node *b = get_Mul_right(n);
675 /* Mul is commutative and has again an other neutral element. */
676 if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ONE) {
677 n = b; DBG_OPT_ALGSIM1;
678 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) {
679 n = a; DBG_OPT_ALGSIM1;
685 * Optimize a / 1 = a.
687 static ir_node *equivalent_node_Div(ir_node *n)
689 ir_node *a = get_Div_left(n);
690 ir_node *b = get_Div_right(n);
692 /* Div is not commutative. */
693 if (tarval_classify(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
694 /* Turn Div into a tuple (mem, bad, a) */
695 ir_node *mem = get_Div_mem(n);
696 turn_into_tuple(n, 3);
697 set_Tuple_pred(n, pn_Div_M, mem);
698 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
699 set_Tuple_pred(n, pn_Div_res, a);
705 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
707 static ir_node *equivalent_node_And(ir_node *n)
711 ir_node *a = get_And_left(n);
712 ir_node *b = get_And_right(n);
715 n = a; /* And has it's own neutral element */
716 } else if (tarval_classify(computed_value(a)) == TV_CLASSIFY_ALL_ONE) {
718 } else if (tarval_classify(computed_value(b)) == TV_CLASSIFY_ALL_ONE) {
721 if (n != oldn) DBG_OPT_ALGSIM1;
726 * Try to remove useless conv's:
728 static ir_node *equivalent_node_Conv(ir_node *n)
731 ir_node *a = get_Conv_op(n);
734 ir_mode *n_mode = get_irn_mode(n);
735 ir_mode *a_mode = get_irn_mode(a);
737 if (n_mode == a_mode) { /* No Conv necessary */
738 n = a; DBG_OPT_ALGSIM3;
739 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
743 n_mode = get_irn_mode(n);
744 b_mode = get_irn_mode(b);
746 if (n_mode == b_mode) {
747 if (n_mode == mode_b) {
748 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM1;
750 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
751 if (smaller_mode(b_mode, a_mode)){
752 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ DBG_OPT_ALGSIM1;
760 static ir_node *equivalent_node_Phi(ir_node *n)
762 /* Several optimizations:
763 - no Phi in start block.
764 - remove Id operators that are inputs to Phi
765 - fold Phi-nodes, iff they have only one predecessor except
771 ir_node *block = NULL; /* to shutup gcc */
772 ir_node *first_val = NULL; /* to shutup gcc */
773 ir_node *scnd_val = NULL; /* to shutup gcc */
775 if (!get_opt_normalize()) return n;
777 n_preds = get_Phi_n_preds(n);
779 block = get_nodes_block(n);
780 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
781 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
782 if ((is_Bad(block)) || /* Control dead */
783 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
784 return new_Bad(); /* in the Start Block. */
786 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
789 /* first we test for a special case: */
790 /* Confirm is a special node fixing additional information for a
791 value that is known at a certain point. This is useful for
792 dataflow analysis. */
794 ir_node *a = get_Phi_pred(n, 0);
795 ir_node *b = get_Phi_pred(n, 1);
796 if ( (get_irn_op(a) == op_Confirm)
797 && (get_irn_op(b) == op_Confirm)
798 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
799 && (get_irn_n(a, 1) == get_irn_n (b, 1))
800 && (a->data.num == (~b->data.num & irpn_True) )) {
801 return get_irn_n(a, 0);
806 /* If the Block has a Bad pred, we also have one. */
807 for (i = 0; i < n_preds; ++i)
808 if (is_Bad (get_Block_cfgpred(block, i)))
809 set_Phi_pred(n, i, new_Bad());
811 /* Find first non-self-referencing input */
812 for (i = 0; i < n_preds; ++i) {
813 first_val = get_Phi_pred(n, i);
814 if ( (first_val != n) /* not self pointer */
816 && (get_irn_op(first_val) != op_Bad)
818 ) { /* value not dead */
819 break; /* then found first value. */
823 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
824 if (i >= n_preds) { return new_Bad(); }
828 /* follow_Id () for rest of inputs, determine if any of these
829 are non-self-referencing */
830 while (++i < n_preds) {
831 scnd_val = get_Phi_pred(n, i);
833 && (scnd_val != first_val)
835 && (get_irn_op(scnd_val) != op_Bad)
842 /* Fold, if no multiple distinct non-self-referencing inputs */
844 n = first_val; DBG_OPT_PHI;
846 /* skip the remaining Ids (done in get_Phi_pred). */
847 /* superfluous, since we walk all to propagate Block's Bads.
848 while (++i < n_preds) get_Phi_pred(n, i); */
854 * Optimize Loads after Store.
856 * @todo FAILS for volatile entities
858 static ir_node *equivalent_node_Load(ir_node *n)
862 /* remove unnecessary Load. */
863 ir_node *a = skip_Proj(get_Load_mem(n));
864 ir_node *b = get_Load_ptr(n);
867 /* TODO: check for volatile */
868 if (get_irn_op(a) == op_Store && get_Store_ptr(a) == b) {
869 /* We load immediately after a store -- a read after write. */
870 ir_node *mem = get_Load_mem(n);
872 c = get_Store_value(a);
873 turn_into_tuple(n, 3);
874 set_Tuple_pred(n, pn_Load_M, mem);
875 set_Tuple_pred(n, pn_Load_res, c);
876 set_Tuple_pred(n, pn_Load_X_except, new_Bad()); DBG_OPT_RAW;
882 * Optimize store after store and load atfter store.
884 * @todo FAILS for volatile entities
886 static ir_node *equivalent_node_Store(ir_node *n)
890 /* remove unnecessary store. */
891 ir_node *a = skip_Proj(get_Store_mem(n));
892 ir_node *b = get_Store_ptr(n);
893 ir_node *c = skip_Proj(get_Store_value(n));
895 if (get_irn_op(a) == op_Store
896 && get_Store_ptr(a) == b
897 && skip_Proj(get_Store_value(a)) == c) {
898 /* We have twice exactly the same store -- a write after write. */
900 } else if (get_irn_op(c) == op_Load
901 && (a == c || skip_Proj(get_Load_mem(c)) == a)
902 && get_Load_ptr(c) == b ) {
903 /* We just loaded the value from the same memory, i.e., the store
904 doesn't change the memory -- a write after read. */
905 a = get_Store_mem(n);
906 turn_into_tuple(n, 2);
907 set_Tuple_pred(n, pn_Store_M, a);
908 set_Tuple_pred(n, pn_Store_X_except, new_Bad()); DBG_OPT_WAR;
913 static ir_node *equivalent_node_Proj(ir_node *n)
917 ir_node *a = get_Proj_pred(n);
919 if ( get_irn_op(a) == op_Tuple) {
920 /* Remove the Tuple/Proj combination. */
921 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
922 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
924 assert(0); /* This should not happen! */
927 } else if (get_irn_mode(n) == mode_X &&
928 is_Bad(get_nodes_Block(n))) {
929 /* Remove dead control flow -- early gigo. */
938 static ir_node *equivalent_node_Id(ir_node *n)
942 n = follow_Id(n); DBG_OPT_ID;
947 case iro_Mod, Quot, DivMod
948 DivMod allocates new nodes --> it's treated in transform node.
949 What about Quot, DivMod?
953 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
954 * perform no actual computation, as, e.g., the Id nodes. It does not create
955 * new nodes. It is therefore safe to free n if the node returned is not n.
956 * If a node returns a Tuple we can not just skip it. If the size of the
957 * in array fits, we transform n into a tuple (e.g., Div).
960 equivalent_node(ir_node *n)
962 if (n->op->equivalent_node)
963 return n->op->equivalent_node(n);
968 * set the default equivalent node operation
970 static ir_op *firm_set_default_equivalent_node(ir_op *op)
974 op->equivalent_node = equivalent_node_##a; \
996 // CASE(Load); /* dangerous */
997 // CASE(Store); /* dangerous, see todo */
1001 op->equivalent_node = NULL;
1009 * Do node specific optimizations of nodes predecessors.
1012 optimize_preds(ir_node *n) {
1013 ir_node *a = NULL, *b = NULL;
1015 /* get the operands we will work on for simple cases. */
1017 a = get_binop_left(n);
1018 b = get_binop_right(n);
1019 } else if (is_unop(n)) {
1023 switch (get_irn_opcode(n)) {
1026 /* We don't want Cast as input to Cmp. */
1027 if (get_irn_op(a) == op_Cast) {
1031 if (get_irn_op(b) == op_Cast) {
1033 set_Cmp_right(n, b);
1041 static ir_node *transform_node_Div(ir_node *n)
1043 tarval *tv = computed_value(n);
1045 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1047 if (tv != tarval_bad) {
1048 /* Turn Div into a tuple (mem, bad, value) */
1049 ir_node *mem = get_Div_mem(n);
1051 turn_into_tuple(n, 3);
1052 set_Tuple_pred(n, pn_Div_M, mem);
1053 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1054 set_Tuple_pred(n, pn_Div_res, new_Const(get_tarval_mode(tv), tv));
1059 static ir_node *transform_node_Mod(ir_node *n)
1061 tarval *tv = computed_value(n);
1063 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1065 if (tv != tarval_bad) {
1066 /* Turn Mod into a tuple (mem, bad, value) */
1067 ir_node *mem = get_Mod_mem(n);
1068 turn_into_tuple(n, 3);
1069 set_Tuple_pred(n, pn_Mod_M, mem);
1070 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1071 set_Tuple_pred(n, pn_Mod_res, new_Const(get_tarval_mode(tv), tv));
1076 static ir_node *transform_node_DivMod(ir_node *n)
1080 ir_node *a = get_DivMod_left(n);
1081 ir_node *b = get_DivMod_right(n);
1082 ir_mode *mode = get_irn_mode(a);
1083 tarval *ta = value_of(a);
1084 tarval *tb = value_of(b);
1086 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1089 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1091 if (tb != tarval_bad) {
1092 if (tb == get_mode_one(get_tarval_mode(tb))) {
1093 b = new_Const (mode, get_mode_null(mode));
1095 } else if (ta != tarval_bad) {
1096 tarval *resa, *resb;
1097 resa = tarval_div (ta, tb);
1098 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1099 Jmp for X result!? */
1100 resb = tarval_mod (ta, tb);
1101 if (resb == tarval_bad) return n; /* Causes exception! */
1102 a = new_Const (mode, resa);
1103 b = new_Const (mode, resb);
1106 } else if (ta == get_mode_null(mode)) {
1110 if (evaluated) { /* replace by tuple */
1111 ir_node *mem = get_DivMod_mem(n);
1112 turn_into_tuple(n, 4);
1113 set_Tuple_pred(n, pn_DivMod_M, mem);
1114 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1115 set_Tuple_pred(n, pn_DivMod_res_div, a);
1116 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1117 assert(get_nodes_Block(n));
1123 static ir_node *transform_node_Cond(ir_node *n)
1125 /* Replace the Cond by a Jmp if it branches on a constant
1128 ir_node *a = get_Cond_selector(n);
1129 tarval *ta = value_of(a);
1131 if ((ta != tarval_bad) &&
1132 (get_irn_mode(a) == mode_b) &&
1133 (get_opt_unreachable_code())) {
1134 /* It's a boolean Cond, branching on a boolean constant.
1135 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1136 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
1137 turn_into_tuple(n, 2);
1138 if (ta == tarval_b_true) {
1139 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1140 set_Tuple_pred(n, pn_Cond_true, jmp);
1142 set_Tuple_pred(n, pn_Cond_false, jmp);
1143 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1145 /* We might generate an endless loop, so keep it alive. */
1146 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
1147 } else if ((ta != tarval_bad) &&
1148 (get_irn_mode(a) == mode_Iu) &&
1149 (get_Cond_kind(n) == dense) &&
1150 (get_opt_unreachable_code())) {
1151 /* I don't want to allow Tuples smaller than the biggest Proj.
1152 Also this tuple might get really big...
1153 I generate the Jmp here, and remember it in link. Link is used
1154 when optimizing Proj. */
1155 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
1156 /* We might generate an endless loop, so keep it alive. */
1157 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
1158 } else if ((get_irn_op(a) == op_Eor)
1159 && (get_irn_mode(a) == mode_b)
1160 && (tarval_classify(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1161 /* The Eor is a negate. Generate a new Cond without the negate,
1162 simulate the negate by exchanging the results. */
1163 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
1165 } else if ((get_irn_op(a) == op_Not)
1166 && (get_irn_mode(a) == mode_b)) {
1167 /* A Not before the Cond. Generate a new Cond without the Not,
1168 simulate the Not by exchanging the results. */
1169 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
1175 static ir_node *transform_node_Eor(ir_node *n)
1177 ir_node *a = get_Eor_left(n);
1178 ir_node *b = get_Eor_right(n);
1180 if ((get_irn_mode(n) == mode_b)
1181 && (get_irn_op(a) == op_Proj)
1182 && (get_irn_mode(a) == mode_b)
1183 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE)
1184 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1185 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1186 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
1187 mode_b, get_negated_pnc(get_Proj_proj(a)));
1188 else if ((get_irn_mode(n) == mode_b)
1189 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE))
1190 /* The Eor is a Not. Replace it by a Not. */
1191 /* ????!!!Extend to bitfield 1111111. */
1192 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
1198 * Transfor a boolean Not.
1200 static ir_node *transform_node_Not(ir_node *n)
1202 ir_node *a = get_Not_op(n);
1204 if ( (get_irn_mode(n) == mode_b)
1205 && (get_irn_op(a) == op_Proj)
1206 && (get_irn_mode(a) == mode_b)
1207 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1208 /* We negate a Cmp. The Cmp has the negated result anyways! */
1209 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
1210 mode_b, get_negated_pnc(get_Proj_proj(a)));
1216 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1217 * done here to avoid that this optimization runs more than once...
1219 static ir_node *transform_node_Proj(ir_node *proj)
1221 ir_node *n = get_Proj_pred(proj);
1225 switch (get_irn_opcode(n)) {
1227 b = get_Div_right(n);
1228 tb = computed_value(b);
1230 if (tb != tarval_bad && tarval_classify(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1231 ir_node *div, *proj;
1232 ir_node *a = get_Div_left(n);
1233 ir_node *mem = get_Div_mem(n);
1234 int rem = get_optimize();
1238 div = new_rd_Div(get_irn_dbg_info(n), current_ir_graph,
1239 get_nodes_Block(n), get_irg_initial_mem(current_ir_graph), a, b);
1241 proj = new_r_Proj(current_ir_graph, get_nodes_Block(n), div, get_irn_mode(a), pn_Div_res);
1245 turn_into_tuple(n, 3);
1246 set_Tuple_pred(n, pn_Mod_M, mem);
1247 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1248 set_Tuple_pred(n, pn_Mod_res, proj);
1252 b = get_Mod_right(n);
1253 tb = computed_value(b);
1255 if (tb != tarval_bad && tarval_classify(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1256 ir_node *mod, *proj;
1257 ir_node *a = get_Mod_left(n);
1258 ir_node *mem = get_Mod_mem(n);
1259 int rem = get_optimize();
1263 mod = new_rd_Mod(get_irn_dbg_info(n), current_ir_graph,
1264 get_nodes_Block(n), get_irg_initial_mem(current_ir_graph), a, b);
1266 proj = new_r_Proj(current_ir_graph, get_nodes_Block(n), mod, get_irn_mode(a), pn_Mod_res);
1270 turn_into_tuple(n, 3);
1271 set_Tuple_pred(n, pn_Mod_M, mem);
1272 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1273 set_Tuple_pred(n, pn_Mod_res, proj);
1277 b = get_DivMod_right(n);
1278 tb = computed_value(b);
1280 if (tb != tarval_bad && tarval_classify(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1281 ir_node *div_mod, *proj_div, *proj_mod;
1282 ir_node *a = get_Mod_left(n);
1283 ir_node *mem = get_Mod_mem(n);
1284 int rem = get_optimize();
1288 div_mod = new_rd_DivMod(get_irn_dbg_info(n), current_ir_graph,
1289 get_nodes_Block(n), get_irg_initial_mem(current_ir_graph), a, b);
1291 proj_div = new_r_Proj(current_ir_graph, get_nodes_Block(n), div_mod, get_irn_mode(a), pn_DivMod_res_div);
1292 proj_mod = new_r_Proj(current_ir_graph, get_nodes_Block(n), div_mod, get_irn_mode(a), pn_DivMod_res_mod);
1296 turn_into_tuple(n, 4);
1297 set_Tuple_pred(n, pn_DivMod_M, mem);
1298 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad());
1299 set_Tuple_pred(n, pn_DivMod_res_div, proj_div);
1300 set_Tuple_pred(n, pn_DivMod_res_mod, proj_mod);
1305 if (get_opt_unreachable_code()) {
1306 b = get_Cond_selector(n);
1307 tb = computed_value(b);
1309 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1310 /* we have a constant switch */
1311 long num = get_Proj_proj(proj);
1313 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1314 if (get_tarval_long(tb) == num) {
1315 /* Do NOT create a jump here, or we will have 2 control flow ops
1316 * in a block. This case is optimized away in optimize_cf(). */
1331 /* we have added a Tuple, optimize it for the current Proj away */
1332 return equivalent_node_Proj(proj);
1336 * Transform a Store before a Store to the same address...
1337 * Both nodes must be in the same block.
1339 * @todo Check for volatile! Moreover, what if the first store
1340 * has a exception handler while the other has not?
1342 static ir_node *transform_node_Store(ir_node *store)
1344 ir_node *pred = skip_Proj(get_Store_mem(store));
1345 ir_node *ptr = get_Store_ptr(store);
1347 if (get_irn_op(pred) == op_Store &&
1348 get_Store_ptr(pred) == ptr &&
1349 get_nodes_block(pred) == get_nodes_block(store)) {
1350 /* the Store n is useless, as it is overwritten by the store store */
1351 ir_node *mem = get_Store_mem(pred);
1353 turn_into_tuple(pred, 2);
1354 set_Tuple_pred(pred, pn_Store_M, mem);
1355 set_Tuple_pred(pred, pn_Store_X_except, new_Bad());
1361 * returns the operands of a commutative bin-op, if one operand is
1362 * a const, it is returned as the second one.
1364 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1366 ir_node *op_a = get_binop_left(binop);
1367 ir_node *op_b = get_binop_right(binop);
1369 assert(is_op_commutative(get_irn_op(binop)));
1371 if (get_irn_op(op_a) == op_Const) {
1382 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1383 * Such pattern may arise in bitfield stores.
1385 * value c4 value c4 & c2
1386 * AND c3 AND c1 | c3
1391 static ir_node *transform_node_Or(ir_node *or)
1395 ir_node *and_l, *c3;
1396 ir_node *value, *c4;
1397 ir_node *new_and, *new_const, *block;
1398 ir_mode *mode = get_irn_mode(or);
1400 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1402 get_comm_Binop_Ops(or, &and, &c1);
1403 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1406 get_comm_Binop_Ops(and, &or_l, &c2);
1407 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1410 get_comm_Binop_Ops(or_l, &and_l, &c3);
1411 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1414 get_comm_Binop_Ops(and_l, &value, &c4);
1415 if (get_irn_op(c4) != op_Const)
1418 /* ok, found the pattern, check for conditions */
1419 assert(mode == get_irn_mode(and));
1420 assert(mode == get_irn_mode(or_l));
1421 assert(mode == get_irn_mode(and_l));
1423 tv1 = get_Const_tarval(c1);
1424 tv2 = get_Const_tarval(c2);
1425 tv3 = get_Const_tarval(c3);
1426 tv4 = get_Const_tarval(c4);
1428 tv = tarval_or(tv4, tv2);
1429 if (tarval_classify(tv) != TV_CLASSIFY_ALL_ONE) {
1430 /* have at least one 0 at the same bit position */
1434 n_tv4 = tarval_not(tv4);
1435 if (tv3 != tarval_and(tv3, n_tv4)) {
1436 /* bit in the or_mask is outside the and_mask */
1440 n_tv2 = tarval_not(tv2);
1441 if (tv1 != tarval_and(tv1, n_tv2)) {
1442 /* bit in the or_mask is outside the and_mask */
1446 /* ok, all conditions met */
1447 block = get_nodes_block(or);
1449 new_and = new_r_And(current_ir_graph, block,
1450 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1452 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1454 set_Or_left(or, new_and);
1455 set_Or_right(or, new_const);
1457 /* check for more */
1458 return transform_node_Or(or);
1462 * Tries several [inplace] [optimizing] transformations and returns an
1463 * equivalent node. The difference to equivalent_node() is that these
1464 * transformations _do_ generate new nodes, and thus the old node must
1465 * not be freed even if the equivalent node isn't the old one.
1467 static ir_node *transform_node(ir_node *n)
1469 if (n->op->transform_node)
1470 n = n->op->transform_node(n);
1475 * set the default transform node operation
1477 static ir_op *firm_set_default_transform_node(ir_op *op)
1481 op->transform_node = transform_node_##a; \
1492 // CASE(Store); /* dangerous, see todo */
1495 op->transform_node = NULL;
1503 /* **************** Common Subexpression Elimination **************** */
1505 /** The size of the hash table used, should estimate the number of nodes
1507 #define N_IR_NODES 512
1509 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1511 return (get_Const_tarval(a) != get_Const_tarval(b))
1512 || (get_Const_type(a) != get_Const_type(b));
1515 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1517 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1520 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1522 return get_Filter_proj(a) != get_Filter_proj(b);
1525 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1527 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1528 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1531 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1533 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1536 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1538 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1539 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p);
1542 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1544 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1547 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1549 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1552 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1554 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1555 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1556 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1557 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1558 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1561 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1563 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1566 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1568 return get_Cast_type(a) != get_Cast_type(b);
1572 * set the default node attribute compare operation
1574 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1578 op->node_cmp_attr = node_cmp_attr_##a; \
1594 op->node_cmp_attr = NULL;
1602 * Compare function for two nodes in the hash table. Gets two
1603 * nodes as parameters. Returns 0 if the nodes are a cse.
1606 vt_cmp (const void *elt, const void *key)
1614 if (a == b) return 0;
1616 if ((get_irn_op(a) != get_irn_op(b)) ||
1617 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1619 /* compare if a's in and b's in are equal */
1620 irn_arity_a = get_irn_arity (a);
1621 if (irn_arity_a != get_irn_arity(b))
1624 /* for block-local cse and pinned nodes: */
1625 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
1626 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1630 /* compare a->in[0..ins] with b->in[0..ins] */
1631 for (i = 0; i < irn_arity_a; i++)
1632 if (get_irn_n(a, i) != get_irn_n(b, i))
1636 * here, we already now that the nodes are identical except their
1639 if (a->op->node_cmp_attr)
1640 return a->op->node_cmp_attr(a, b);
1646 * Calculate a hash value of a node.
1649 ir_node_hash (ir_node *node)
1654 if (node->op == op_Const) {
1655 /* special value for const, as they only differ in their tarval. */
1656 h = ((unsigned) node->attr.con.tv)>>3 ;
1657 h = 9*h + (unsigned)get_irn_mode(node);
1658 } else if (node->op == op_SymConst) {
1659 /* special value for const, as they only differ in their symbol. */
1660 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1661 h = 9*h + (unsigned)get_irn_mode(node);
1664 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1665 h = irn_arity = get_irn_arity(node);
1667 /* consider all in nodes... except the block. */
1668 for (i = 0; i < irn_arity; i++) {
1669 h = 9*h + (unsigned)get_irn_n(node, i);
1673 h = 9*h + (unsigned) get_irn_mode (node);
1675 h = 9*h + (unsigned) get_irn_op (node);
1682 new_identities (void)
1684 return new_pset (vt_cmp, N_IR_NODES);
1688 del_identities (pset *value_table)
1690 del_pset (value_table);
1694 * Return the canonical node computing the same value as n.
1695 * Looks up the node in a hash table.
1697 * For Const nodes this is performed in the constructor, too. Const
1698 * nodes are extremely time critical because of their frequent use in
1699 * constant string arrays.
1701 static INLINE ir_node *
1702 identify (pset *value_table, ir_node *n)
1706 if (!value_table) return n;
1708 /* TODO: use a generic commutative attribute */
1709 if (get_opt_reassociation()) {
1710 if (is_op_commutative(get_irn_op(n))) {
1711 /* for commutative operators perform a OP b == b OP a */
1712 if (get_binop_left(n) > get_binop_right(n)) {
1713 ir_node *h = get_binop_left(n);
1714 set_binop_left(n, get_binop_right(n));
1715 set_binop_right(n, h);
1720 o = pset_find (value_table, n, ir_node_hash (n));
1727 * During construction we set the pinned flag in the graph right when the
1728 * optimization is performed. The flag turning on procedure global cse could
1729 * be changed between two allocations. This way we are safe.
1731 static INLINE ir_node *
1732 identify_cons (pset *value_table, ir_node *n) {
1734 n = identify(value_table, n);
1735 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1736 set_irg_pinned(current_ir_graph, floats);
1741 * Return the canonical node computing the same value as n.
1742 * Looks up the node in a hash table, enters it in the table
1743 * if it isn't there yet.
1746 identify_remember (pset *value_table, ir_node *node)
1750 if (!value_table) return node;
1752 /* lookup or insert in hash table with given hash key. */
1753 o = pset_insert (value_table, node, ir_node_hash (node));
1755 if (o == node) return node;
1761 add_identities (pset *value_table, ir_node *node) {
1762 identify_remember (value_table, node);
1766 * garbage in, garbage out. If a node has a dead input, i.e., the
1767 * Bad node is input to the node, return the Bad node.
1769 static INLINE ir_node *
1770 gigo (ir_node *node)
1773 ir_op* op = get_irn_op(node);
1775 /* remove garbage blocks by looking at control flow that leaves the block
1776 and replacing the control flow by Bad. */
1777 if (get_irn_mode(node) == mode_X) {
1778 ir_node *block = get_nodes_block(node);
1779 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1780 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1781 irn_arity = get_irn_arity(block);
1782 for (i = 0; i < irn_arity; i++) {
1783 if (!is_Bad(get_irn_n(block, i))) break;
1785 if (i == irn_arity) return new_Bad();
1789 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1790 blocks predecessors is dead. */
1791 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1792 irn_arity = get_irn_arity(node);
1793 for (i = -1; i < irn_arity; i++) {
1794 if (is_Bad(get_irn_n(node, i))) {
1800 /* With this code we violate the agreement that local_optimize
1801 only leaves Bads in Block, Phi and Tuple nodes. */
1802 /* If Block has only Bads as predecessors it's garbage. */
1803 /* If Phi has only Bads as predecessors it's garbage. */
1804 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1805 irn_arity = get_irn_arity(node);
1806 for (i = 0; i < irn_arity; i++) {
1807 if (!is_Bad(get_irn_n(node, i))) break;
1809 if (i == irn_arity) node = new_Bad();
1817 * These optimizations deallocate nodes from the obstack.
1818 * It can only be called if it is guaranteed that no other nodes
1819 * reference this one, i.e., right after construction of a node.
1822 optimize_node (ir_node *n)
1826 opcode iro = get_irn_opcode(n);
1828 /* Allways optimize Phi nodes: part of the construction. */
1829 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1831 /* constant expression evaluation / constant folding */
1832 if (get_opt_constant_folding()) {
1833 /* constants can not be evaluated */
1834 if (iro != iro_Const) {
1835 /* try to evaluate */
1836 tv = computed_value (n);
1837 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1839 * we MUST copy the node here temparary, because it's still needed
1840 * for DBG_OPT_ALGSIM0
1842 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
1843 ir_node *x = alloca(node_size);
1845 memcpy(x, n, node_size);
1848 /* evaluation was successful -- replace the node. */
1849 obstack_free (current_ir_graph->obst, n);
1850 n = new_Const (get_tarval_mode (tv), tv);
1857 /* remove unnecessary nodes */
1858 if (get_opt_constant_folding() ||
1859 (iro == iro_Phi) || /* always optimize these nodes. */
1861 (iro == iro_Proj) ||
1862 (iro == iro_Block) ) /* Flags tested local. */
1863 n = equivalent_node (n);
1865 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1867 /** common subexpression elimination **/
1868 /* Checks whether n is already available. */
1869 /* The block input is used to distinguish different subexpressions. Right
1870 now all nodes are pinned to blocks, i.e., the cse only finds common
1871 subexpressions within a block. */
1873 n = identify_cons (current_ir_graph->value_table, n);
1876 /* We found an existing, better node, so we can deallocate the old node. */
1877 obstack_free (current_ir_graph->obst, oldn);
1882 /* Some more constant expression evaluation that does not allow to
1884 iro = get_irn_opcode(n);
1885 if (get_opt_constant_folding() ||
1886 (iro == iro_Cond) ||
1887 (iro == iro_Proj)) /* Flags tested local. */
1888 n = transform_node (n);
1890 /* Remove nodes with dead (Bad) input.
1891 Run always for transformation induced Bads. */
1894 /* Now we have a legal, useful node. Enter it in hash table for cse */
1895 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1896 n = identify_remember (current_ir_graph->value_table, n);
1904 * These optimizations never deallocate nodes. This can cause dead
1905 * nodes lying on the obstack. Remove these by a dead node elimination,
1906 * i.e., a copying garbage collection.
1909 optimize_in_place_2 (ir_node *n)
1913 opcode iro = get_irn_opcode(n);
1915 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1917 /* if not optimize return n */
1920 /* Here this is possible. Why? */
1925 /* constant expression evaluation / constant folding */
1926 if (get_opt_constant_folding()) {
1927 /* constants can not be evaluated */
1928 if (iro != iro_Const) {
1929 /* try to evaluate */
1930 tv = computed_value (n);
1931 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1932 /* evaluation was successful -- replace the node. */
1933 n = new_Const (get_tarval_mode (tv), tv);
1940 /* remove unnecessary nodes */
1941 /*if (get_opt_constant_folding()) */
1942 if (get_opt_constant_folding() ||
1943 (iro == iro_Phi) || /* always optimize these nodes. */
1944 (iro == iro_Id) || /* ... */
1945 (iro == iro_Proj) || /* ... */
1946 (iro == iro_Block) ) /* Flags tested local. */
1947 n = equivalent_node (n);
1949 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1951 /** common subexpression elimination **/
1952 /* Checks whether n is already available. */
1953 /* The block input is used to distinguish different subexpressions. Right
1954 now all nodes are pinned to blocks, i.e., the cse only finds common
1955 subexpressions within a block. */
1956 if (get_opt_cse()) {
1957 n = identify (current_ir_graph->value_table, n);
1960 /* Some more constant expression evaluation. */
1961 iro = get_irn_opcode(n);
1962 if (get_opt_constant_folding() ||
1963 (iro == iro_Cond) ||
1964 (iro == iro_Proj)) /* Flags tested local. */
1965 n = transform_node (n);
1967 /* Remove nodes with dead (Bad) input.
1968 Run always for transformation induced Bads. */
1971 /* Now we can verify the node, as it has no dead inputs any more. */
1974 /* Now we have a legal, useful node. Enter it in hash table for cse.
1975 Blocks should be unique anyways. (Except the successor of start:
1976 is cse with the start block!) */
1977 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1978 n = identify_remember (current_ir_graph->value_table, n);
1984 * Wrapper for external use, set proper status bits after optimization.
1987 optimize_in_place (ir_node *n)
1989 /* Handle graph state */
1990 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1992 if (get_opt_global_cse())
1993 set_irg_pinned(current_ir_graph, floats);
1994 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1995 set_irg_outs_inconsistent(current_ir_graph);
1996 /* Maybe we could also test whether optimizing the node can
1997 change the control graph. */
1998 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1999 set_irg_dom_inconsistent(current_ir_graph);
2000 return optimize_in_place_2 (n);
2004 * set the default ir op operations
2006 ir_op *firm_set_default_operations(ir_op *op)
2008 op = firm_set_default_computed_value(op);
2009 op = firm_set_default_equivalent_node(op);
2010 op = firm_set_default_transform_node(op);
2011 op = firm_set_default_node_cmp_attr(op);