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"
31 /* Make types visible to allow most efficient access */
32 # include "entity_t.h"
35 * Trivial INLINEable routine for copy propagation.
36 * Does follow Ids, needed to optimize INLINEd code.
38 static INLINE ir_node *
39 follow_Id (ir_node *n)
41 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
46 * Returns the tarval of a Const node or tarval_bad for all other nodes.
48 static INLINE tarval *
51 if ((n != NULL) && (get_irn_op(n) == op_Const))
52 return get_Const_tarval(n); /* might return tarval_bad */
58 * return the value of a Constant
60 static tarval *computed_value_Const(ir_node *n)
62 return get_Const_tarval(n);
66 * return the value of a 'sizeof' SymConst
68 static tarval *computed_value_SymConst(ir_node *n)
70 if ((get_SymConst_kind(n) == symconst_size) &&
71 (get_type_state(get_SymConst_type(n))) == layout_fixed)
72 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
76 static tarval *computed_value_Add(ir_node *n)
78 ir_node *a = get_Add_left(n);
79 ir_node *b = get_Add_right(n);
81 tarval *ta = value_of(a);
82 tarval *tb = value_of(b);
84 if ((ta != tarval_bad) && (tb != tarval_bad)
85 && (get_irn_mode(a) == get_irn_mode(b))
86 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
87 return tarval_add(ta, tb);
92 static tarval *computed_value_Sub(ir_node *n)
94 ir_node *a = get_Sub_left(n);
95 ir_node *b = get_Sub_right(n);
101 return get_tarval_null(get_irn_mode(n));
106 if ((ta != tarval_bad) && (tb != tarval_bad)
107 && (get_irn_mode(a) == get_irn_mode(b))
108 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
109 return tarval_sub(ta, tb);
114 static tarval *computed_value_Minus(ir_node *n)
116 ir_node *a = get_Minus_op(n);
117 tarval *ta = value_of(a);
119 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
120 return tarval_neg(ta);
125 static tarval *computed_value_Mul(ir_node *n)
127 ir_node *a = get_Mul_left(n);
128 ir_node *b = get_Mul_right(n);
130 tarval *ta = value_of(a);
131 tarval *tb = value_of(b);
133 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
134 return tarval_mul(ta, tb);
136 /* a*0 = 0 or 0*b = 0:
137 calls computed_value recursive and returns the 0 with proper
141 if ( ( ((v = ta) != tarval_bad)
142 && (v == get_mode_null(get_tarval_mode(v))) )
143 || ( ((v = tb) != tarval_bad)
144 && (v == get_mode_null(get_tarval_mode(v))) )) {
151 static tarval *computed_value_Quot(ir_node *n)
153 ir_node *a = get_Quot_left(n);
154 ir_node *b = get_Quot_right(n);
156 tarval *ta = value_of(a);
157 tarval *tb = value_of(b);
159 /* This was missing in original implementation. Why? */
160 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
161 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
162 return tarval_quo(ta, tb);
167 static tarval *computed_value_Div(ir_node *n)
169 ir_node *a = get_Div_left(n);
170 ir_node *b = get_Div_right(n);
172 tarval *ta = value_of(a);
173 tarval *tb = value_of(b);
175 /* This was missing in original implementation. Why? */
176 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
177 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
178 return tarval_div(ta, tb);
183 static tarval *computed_value_Mod(ir_node *n)
185 ir_node *a = get_Mod_left(n);
186 ir_node *b = get_Mod_right(n);
188 tarval *ta = value_of(a);
189 tarval *tb = value_of(b);
191 /* This was missing in original implementation. Why? */
192 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
193 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
194 return tarval_mod(ta, tb);
200 static tarval *computed_value_Abs(ir_node *n)
202 ir_node *a = get_Abs_op(n);
203 tarval *ta = value_of(a);
205 if (ta != tarval_bad)
206 return tarval_abs(ta);
211 static tarval *computed_value_And(ir_node *n)
213 ir_node *a = get_And_left(n);
214 ir_node *b = get_And_right(n);
216 tarval *ta = value_of(a);
217 tarval *tb = value_of(b);
219 if ((ta != tarval_bad) && (tb != tarval_bad)) {
220 return tarval_and (ta, tb);
224 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_NULL)
225 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
232 static tarval *computed_value_Or(ir_node *n)
234 ir_node *a = get_Or_left(n);
235 ir_node *b = get_Or_right(n);
237 tarval *ta = value_of(a);
238 tarval *tb = value_of(b);
240 if ((ta != tarval_bad) && (tb != tarval_bad)) {
241 return tarval_or (ta, tb);
244 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
245 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
252 static tarval *computed_value_Eor(ir_node *n)
254 ir_node *a = get_Eor_left(n);
255 ir_node *b = get_Eor_right(n);
257 tarval *ta = value_of(a);
258 tarval *tb = value_of(b);
260 if ((ta != tarval_bad) && (tb != tarval_bad)) {
261 return tarval_eor (ta, tb);
266 static tarval *computed_value_Not(ir_node *n)
268 ir_node *a = get_Not_op(n);
269 tarval *ta = value_of(a);
271 if (ta != tarval_bad)
272 return tarval_not(ta);
277 static tarval *computed_value_Shl(ir_node *n)
279 ir_node *a = get_Shl_left(n);
280 ir_node *b = get_Shl_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_shl (ta, tb);
291 static tarval *computed_value_Shr(ir_node *n)
293 ir_node *a = get_Shr_left(n);
294 ir_node *b = get_Shr_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_shr (ta, tb);
305 static tarval *computed_value_Shrs(ir_node *n)
307 ir_node *a = get_Shrs_left(n);
308 ir_node *b = get_Shrs_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_shrs (ta, tb);
319 static tarval *computed_value_Rot(ir_node *n)
321 ir_node *a = get_Rot_left(n);
322 ir_node *b = get_Rot_right(n);
324 tarval *ta = value_of(a);
325 tarval *tb = value_of(b);
327 if ((ta != tarval_bad) && (tb != tarval_bad)) {
328 return tarval_rot (ta, tb);
333 static tarval *computed_value_Conv(ir_node *n)
335 ir_node *a = get_Conv_op(n);
336 tarval *ta = value_of(a);
338 if (ta != tarval_bad)
339 return tarval_convert_to(ta, get_irn_mode(n));
344 static tarval *computed_value_Proj(ir_node *n)
346 ir_node *a = get_Proj_pred(n), *b;
349 /* Optimize Cmp nodes.
350 This performs a first step of unreachable code elimination.
351 Proj can not be computed, but folding a Cmp above the Proj here is
352 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
354 There are several case where we can evaluate a Cmp node:
355 1. The nodes compared are both the same. If we compare for
356 equal, greater equal, ... this will return true, else it
357 will return false. This step relies on cse.
358 2. The predecessors of Cmp are target values. We can evaluate
360 3. The predecessors are Allocs or void* constants. Allocs never
361 return NULL, they raise an exception. Therefore we can predict
363 switch (get_irn_opcode(a)) {
365 aa = get_Cmp_left(a);
366 ab = get_Cmp_right(a);
368 if (aa == ab) { /* 1.: */
369 /* This is a trick with the bits used for encoding the Cmp
370 Proj numbers, the following statement is not the same:
371 return new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
372 return new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
374 tarval *taa = computed_value (aa);
375 tarval *tab = computed_value (ab);
377 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
378 /* strange checks... */
379 pnc_number flags = tarval_cmp (taa, tab);
380 if (flags != False) {
381 return new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
383 } else { /* check for 3.: */
384 ir_node *aaa = skip_Id(skip_Proj(aa));
385 ir_node *aba = skip_Id(skip_Proj(ab));
387 if ( ( (/* aa is ProjP and aaa is Alloc */
388 (get_irn_op(aa) == op_Proj)
389 && (mode_is_reference(get_irn_mode(aa)))
390 && (get_irn_op(aaa) == op_Alloc))
391 && ( (/* ab is constant void */
392 (get_irn_op(ab) == op_Const)
393 && (mode_is_reference(get_irn_mode(ab)))
394 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
395 || (/* ab is other Alloc */
396 (get_irn_op(ab) == op_Proj)
397 && (mode_is_reference(get_irn_mode(ab)))
398 && (get_irn_op(aba) == op_Alloc)
400 || (/* aa is void and aba is Alloc */
401 (get_irn_op(aa) == op_Const)
402 && (mode_is_reference(get_irn_mode(aa)))
403 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
404 && (get_irn_op(ab) == op_Proj)
405 && (mode_is_reference(get_irn_mode(ab)))
406 && (get_irn_op(aba) == op_Alloc)))
408 return new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
415 tarval *tb = value_of(b = get_DivMod_right(a));
416 tarval *ta = value_of(a = get_DivMod_left(a));
418 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
419 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
421 if (get_Proj_proj(n)== pn_DivMod_res_div)
422 return tarval_div(ta, tb);
423 else if (get_Proj_proj(n)== pn_DivMod_res_mod)
424 return tarval_mod(ta, tb);
431 tarval *tb = value_of(b = get_Div_right(a));
432 tarval *ta = value_of(a = get_Div_left(a));
434 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
435 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
437 if (get_Proj_proj(n)== pn_Div_res)
438 return tarval_div(ta, tb);
445 tarval *tb = value_of(b = get_Mod_right(a));
446 tarval *ta = value_of(a = get_Mod_left(a));
448 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
449 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
451 if (get_Proj_proj(n)== pn_Mod_res)
452 return tarval_mod(ta, tb);
464 * If the parameter n can be computed, return its value, else tarval_bad.
465 * Performs constant folding.
467 * @param n The node this should be evaluated
469 tarval *computed_value(ir_node *n)
471 if (n->op->computed_value)
472 return n->op->computed_value(n);
477 * set the default computed_value evaluator
479 static ir_op *firm_set_default_computed_value(ir_op *op)
483 op->computed_value = computed_value_##a; \
508 op->computed_value = NULL;
516 /* returns 1 if the a and b are pointers to different locations. */
518 different_identity (ir_node *a, ir_node *b)
520 assert (mode_is_reference(get_irn_mode (a))
521 && mode_is_reference(get_irn_mode (b)));
523 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
524 ir_node *a1 = get_Proj_pred (a);
525 ir_node *b1 = get_Proj_pred (b);
526 if (a1 != b1 && get_irn_op (a1) == op_Alloc
527 && get_irn_op (b1) == op_Alloc)
534 static ir_node *equivalent_node_Block(ir_node *n)
538 /* The Block constructor does not call optimize, but mature_immBlock
539 calls the optimization. */
540 assert(get_Block_matured(n));
542 /* Straightening: a single entry Block following a single exit Block
543 can be merged, if it is not the Start block. */
544 /* !!! Beware, all Phi-nodes of n must have been optimized away.
545 This should be true, as the block is matured before optimize is called.
546 But what about Phi-cycles with the Phi0/Id that could not be resolved?
547 Remaining Phi nodes are just Ids. */
548 if ((get_Block_n_cfgpreds(n) == 1) &&
549 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
550 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
551 if (predblock == oldn) {
552 /* Jmp jumps into the block it is in -- deal self cycle. */
554 DBG_OPT_DEAD(oldn, n);
555 } else if (get_opt_control_flow_straightening()) {
557 DBG_OPT_STG(oldn, n);
560 else if ((get_Block_n_cfgpreds(n) == 1) &&
561 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
562 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
563 if (predblock == oldn) {
564 /* Jmp jumps into the block it is in -- deal self cycle. */
566 DBG_OPT_DEAD(oldn, n);
569 else if ((get_Block_n_cfgpreds(n) == 2) &&
570 (get_opt_control_flow_weak_simplification())) {
571 /* Test whether Cond jumps twice to this block
572 @@@ we could do this also with two loops finding two preds from several ones. */
573 ir_node *a = get_Block_cfgpred(n, 0);
574 ir_node *b = get_Block_cfgpred(n, 1);
576 if ((get_irn_op(a) == op_Proj) &&
577 (get_irn_op(b) == op_Proj) &&
578 (get_Proj_pred(a) == get_Proj_pred(b)) &&
579 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
580 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
581 /* Also a single entry Block following a single exit Block. Phis have
582 twice the same operand and will be optimized away. */
583 n = get_nodes_block(a);
584 DBG_OPT_IFSIM(oldn, a, b, n);
586 } else if (get_opt_unreachable_code() &&
587 (n != current_ir_graph->start_block) &&
588 (n != current_ir_graph->end_block) ) {
590 /* If all inputs are dead, this block is dead too, except if it is
591 the start or end block. This is a step of unreachable code
593 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
594 if (!is_Bad(get_Block_cfgpred(n, i))) break;
596 if (i == get_Block_n_cfgpreds(n))
604 * Returns a equivalent node for a Jmp, a Bad :-)
605 * Of course this only happens if the Block of the Jmp is Bad.
607 static ir_node *equivalent_node_Jmp(ir_node *n)
609 /* GL: Why not same for op_Raise?? */
610 /* unreachable code elimination */
611 if (is_Bad(get_nodes_block(n)))
617 static ir_node *equivalent_node_Cond(ir_node *n)
619 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
620 See cases for iro_Cond and iro_Proj in transform_node. */
625 * Use algebraic simplification a v a = a.
627 static ir_node *equivalent_node_Or(ir_node *n)
631 ir_node *a = get_Or_left(n);
632 ir_node *b = get_Or_right(n);
638 DBG_OPT_ALGSIM1(oldn, a, b, n);
645 * optimize operations that are commutative and have neutral 0,
646 * so a op 0 = 0 op a = a.
648 static ir_node *equivalent_node_neutral_zero(ir_node *n)
652 ir_node *a = get_binop_left(n);
653 ir_node *b = get_binop_right(n);
658 /* After running compute_node there is only one constant predecessor.
659 Find this predecessors value and remember the other node: */
660 if ((tv = computed_value(a)) != tarval_bad) {
662 } else if ((tv = computed_value(b)) != tarval_bad) {
667 /* If this predecessors constant value is zero, the operation is
668 unnecessary. Remove it: */
669 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
672 DBG_OPT_ALGSIM1(oldn, a, b, n);
678 #define equivalent_node_Add equivalent_node_neutral_zero
679 #define equivalent_node_Eor equivalent_node_neutral_zero
682 * optimize operations that are not commutative but have neutral 0 on left,
685 static ir_node *equivalent_node_left_zero(ir_node *n)
689 ir_node *a = get_binop_left(n);
690 ir_node *b = get_binop_right(n);
692 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_NULL) {
695 DBG_OPT_ALGSIM1(oldn, a, b, n);
701 #define equivalent_node_Sub equivalent_node_left_zero
702 #define equivalent_node_Shl equivalent_node_left_zero
703 #define equivalent_node_Shr equivalent_node_left_zero
704 #define equivalent_node_Shrs equivalent_node_left_zero
705 #define equivalent_node_Rot equivalent_node_left_zero
708 * Er, a "symmetic unop", ie op(op(n)) = n.
710 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
713 ir_node *pred = get_unop_op(n);
715 /* optimize symmetric unop */
716 if (get_irn_op(pred) == get_irn_op(n)) {
717 n = get_unop_op(pred);
718 DBG_OPT_ALGSIM2(oldn, pred, n);
724 #define equivalent_node_Not equivalent_node_symmetric_unop
726 /* --x == x */ /* ??? Is this possible or can --x raise an
727 out of bounds exception if min =! max? */
728 #define equivalent_node_Minus equivalent_node_symmetric_unop
731 * Optimize a * 1 = 1 * a = a.
733 static ir_node *equivalent_node_Mul(ir_node *n)
737 ir_node *a = get_Mul_left(n);
738 ir_node *b = get_Mul_right(n);
740 /* Mul is commutative and has again an other neutral element. */
741 if (classify_tarval (computed_value (a)) == TV_CLASSIFY_ONE) {
743 DBG_OPT_ALGSIM1(oldn, a, b, n);
744 } else if (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE) {
746 DBG_OPT_ALGSIM1(oldn, a, b, n);
752 * Optimize a / 1 = a.
754 static ir_node *equivalent_node_Div(ir_node *n)
756 ir_node *a = get_Div_left(n);
757 ir_node *b = get_Div_right(n);
759 /* Div is not commutative. */
760 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
761 /* Turn Div into a tuple (mem, bad, a) */
762 ir_node *mem = get_Div_mem(n);
763 turn_into_tuple(n, 3);
764 set_Tuple_pred(n, pn_Div_M, mem);
765 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
766 set_Tuple_pred(n, pn_Div_res, a);
772 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
774 static ir_node *equivalent_node_And(ir_node *n)
778 ir_node *a = get_And_left(n);
779 ir_node *b = get_And_right(n);
782 n = a; /* And has it's own neutral element */
783 } else if (classify_tarval(computed_value(a)) == TV_CLASSIFY_ALL_ONE) {
785 DBG_OPT_ALGSIM1(oldn, a, b, n);
786 } else if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ALL_ONE) {
788 DBG_OPT_ALGSIM1(oldn, a, b, n);
794 * Try to remove useless conv's:
796 static ir_node *equivalent_node_Conv(ir_node *n)
799 ir_node *a = get_Conv_op(n);
802 ir_mode *n_mode = get_irn_mode(n);
803 ir_mode *a_mode = get_irn_mode(a);
805 if (n_mode == a_mode) { /* No Conv necessary */
807 DBG_OPT_ALGSIM3(oldn, a, n);
808 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
812 n_mode = get_irn_mode(n);
813 b_mode = get_irn_mode(b);
815 if (n_mode == b_mode) {
816 if (n_mode == mode_b) {
817 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
818 DBG_OPT_ALGSIM1(oldn, a, b, n);
820 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
821 if (smaller_mode(b_mode, a_mode)){
822 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
823 DBG_OPT_ALGSIM1(oldn, a, b, n);
831 static ir_node *equivalent_node_Phi(ir_node *n)
833 /* Several optimizations:
834 - no Phi in start block.
835 - remove Id operators that are inputs to Phi
836 - fold Phi-nodes, iff they have only one predecessor except
842 ir_node *block = NULL; /* to shutup gcc */
843 ir_node *first_val = NULL; /* to shutup gcc */
844 ir_node *scnd_val = NULL; /* to shutup gcc */
846 if (!get_opt_normalize()) return n;
848 n_preds = get_Phi_n_preds(n);
850 block = get_nodes_block(n);
851 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
852 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
853 if ((is_Bad(block)) || /* Control dead */
854 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
855 return new_Bad(); /* in the Start Block. */
857 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
860 /* first we test for a special case: */
861 /* Confirm is a special node fixing additional information for a
862 value that is known at a certain point. This is useful for
863 dataflow analysis. */
865 ir_node *a = get_Phi_pred(n, 0);
866 ir_node *b = get_Phi_pred(n, 1);
867 if ( (get_irn_op(a) == op_Confirm)
868 && (get_irn_op(b) == op_Confirm)
869 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
870 && (get_irn_n(a, 1) == get_irn_n (b, 1))
871 && (a->data.num == (~b->data.num & irpn_True) )) {
872 return get_irn_n(a, 0);
877 /* If the Block has a Bad pred, we also have one. */
878 for (i = 0; i < n_preds; ++i)
879 if (is_Bad (get_Block_cfgpred(block, i)))
880 set_Phi_pred(n, i, new_Bad());
882 /* Find first non-self-referencing input */
883 for (i = 0; i < n_preds; ++i) {
884 first_val = get_Phi_pred(n, i);
885 if ( (first_val != n) /* not self pointer */
887 && (get_irn_op(first_val) != op_Bad)
889 ) { /* value not dead */
890 break; /* then found first value. */
894 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
895 if (i >= n_preds) { return new_Bad(); }
899 /* follow_Id () for rest of inputs, determine if any of these
900 are non-self-referencing */
901 while (++i < n_preds) {
902 scnd_val = get_Phi_pred(n, i);
904 && (scnd_val != first_val)
906 && (get_irn_op(scnd_val) != op_Bad)
913 /* Fold, if no multiple distinct non-self-referencing inputs */
916 DBG_OPT_PHI(oldn, first_val, n);
918 /* skip the remaining Ids (done in get_Phi_pred). */
919 /* superfluous, since we walk all to propagate Block's Bads.
920 while (++i < n_preds) get_Phi_pred(n, i); */
926 * optimize Proj(Tuple) and gigo for ProjX in Bad block
928 static ir_node *equivalent_node_Proj(ir_node *n)
932 ir_node *a = get_Proj_pred(n);
934 if ( get_irn_op(a) == op_Tuple) {
935 /* Remove the Tuple/Proj combination. */
936 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
937 n = get_Tuple_pred(a, get_Proj_proj(n));
938 DBG_OPT_TUPLE(oldn, a, n);
940 assert(0); /* This should not happen! */
943 } else if (get_irn_mode(n) == mode_X &&
944 is_Bad(get_nodes_block(n))) {
945 /* Remove dead control flow -- early gigo. */
954 static ir_node *equivalent_node_Id(ir_node *n)
964 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
965 * perform no actual computation, as, e.g., the Id nodes. It does not create
966 * new nodes. It is therefore safe to free n if the node returned is not n.
967 * If a node returns a Tuple we can not just skip it. If the size of the
968 * in array fits, we transform n into a tuple (e.g., Div).
971 equivalent_node(ir_node *n)
973 if (n->op->equivalent_node)
974 return n->op->equivalent_node(n);
979 * set the default equivalent node operation
981 static ir_op *firm_set_default_equivalent_node(ir_op *op)
985 op->equivalent_node = equivalent_node_##a; \
1010 op->equivalent_node = NULL;
1018 * Do node specific optimizations of nodes predecessors.
1021 optimize_preds(ir_node *n) {
1022 ir_node *a = NULL, *b = NULL;
1024 /* get the operands we will work on for simple cases. */
1026 a = get_binop_left(n);
1027 b = get_binop_right(n);
1028 } else if (is_unop(n)) {
1032 switch (get_irn_opcode(n)) {
1035 /* We don't want Cast as input to Cmp. */
1036 if (get_irn_op(a) == op_Cast) {
1040 if (get_irn_op(b) == op_Cast) {
1042 set_Cmp_right(n, b);
1050 static ir_node *transform_node_Mul(ir_node *n)
1052 return arch_dep_replace_mul_with_shifts(n);
1055 static ir_node *transform_node_Div(ir_node *n)
1057 tarval *tv = computed_value(n);
1060 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1062 if (tv != tarval_bad)
1063 value = new_Const(get_tarval_mode(tv), tv);
1064 else /* Try architecture dependand optimization */
1065 value = arch_dep_replace_div_with_shifts(n);
1068 /* Turn Div into a tuple (mem, bad, value) */
1069 ir_node *mem = get_Div_mem(n);
1071 turn_into_tuple(n, 3);
1072 set_Tuple_pred(n, pn_Div_M, mem);
1073 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1074 set_Tuple_pred(n, pn_Div_res, value);
1079 static ir_node *transform_node_Mod(ir_node *n)
1081 tarval *tv = computed_value(n);
1083 tarval *tb = value_of(get_Mod_right(n));
1085 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1087 if (tv != tarval_bad)
1088 value = new_Const(get_tarval_mode(tv), tv);
1089 else if (tb != tarval_bad && tb == get_mode_one(get_tarval_mode(tb))) { /* x mod 1 == 0 */
1090 ir_mode *mode = get_irn_mode(get_DivMod_left(n));
1091 value = new_Const(mode, get_mode_null(mode));
1095 /* Turn Mod into a tuple (mem, bad, value) */
1096 ir_node *mem = get_Mod_mem(n);
1098 turn_into_tuple(n, 3);
1099 set_Tuple_pred(n, pn_Mod_M, mem);
1100 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1101 set_Tuple_pred(n, pn_Mod_res, value);
1106 static ir_node *transform_node_DivMod(ir_node *n)
1110 ir_node *a = get_DivMod_left(n);
1111 ir_node *b = get_DivMod_right(n);
1112 ir_mode *mode = get_irn_mode(a);
1113 tarval *ta = value_of(a);
1114 tarval *tb = value_of(b);
1116 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1119 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1121 if (tb != tarval_bad) {
1122 if (tb == get_mode_one(get_tarval_mode(tb))) {
1123 b = new_Const (mode, get_mode_null(mode));
1125 } else if (ta != tarval_bad) {
1126 tarval *resa, *resb;
1127 resa = tarval_div (ta, tb);
1128 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1129 Jmp for X result!? */
1130 resb = tarval_mod (ta, tb);
1131 if (resb == tarval_bad) return n; /* Causes exception! */
1132 a = new_Const (mode, resa);
1133 b = new_Const (mode, resb);
1136 } else if (ta == get_mode_null(mode)) {
1140 if (evaluated) { /* replace by tuple */
1141 ir_node *mem = get_DivMod_mem(n);
1142 turn_into_tuple(n, 4);
1143 set_Tuple_pred(n, pn_DivMod_M, mem);
1144 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1145 set_Tuple_pred(n, pn_DivMod_res_div, a);
1146 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1147 assert(get_nodes_block(n));
1153 static ir_node *transform_node_Cond(ir_node *n)
1155 /* Replace the Cond by a Jmp if it branches on a constant
1158 ir_node *a = get_Cond_selector(n);
1159 tarval *ta = value_of(a);
1161 if ((ta != tarval_bad) &&
1162 (get_irn_mode(a) == mode_b) &&
1163 (get_opt_unreachable_code())) {
1164 /* It's a boolean Cond, branching on a boolean constant.
1165 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1166 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1167 turn_into_tuple(n, 2);
1168 if (ta == tarval_b_true) {
1169 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1170 set_Tuple_pred(n, pn_Cond_true, jmp);
1172 set_Tuple_pred(n, pn_Cond_false, jmp);
1173 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1175 /* We might generate an endless loop, so keep it alive. */
1176 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1177 } else if ((ta != tarval_bad) &&
1178 (get_irn_mode(a) == mode_Iu) &&
1179 (get_Cond_kind(n) == dense) &&
1180 (get_opt_unreachable_code())) {
1181 /* I don't want to allow Tuples smaller than the biggest Proj.
1182 Also this tuple might get really big...
1183 I generate the Jmp here, and remember it in link. Link is used
1184 when optimizing Proj. */
1185 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1186 /* We might generate an endless loop, so keep it alive. */
1187 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1188 } else if ((get_irn_op(a) == op_Eor)
1189 && (get_irn_mode(a) == mode_b)
1190 && (classify_tarval(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1191 /* The Eor is a negate. Generate a new Cond without the negate,
1192 simulate the negate by exchanging the results. */
1193 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1195 } else if ((get_irn_op(a) == op_Not)
1196 && (get_irn_mode(a) == mode_b)) {
1197 /* A Not before the Cond. Generate a new Cond without the Not,
1198 simulate the Not by exchanging the results. */
1199 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1205 static ir_node *transform_node_Eor(ir_node *n)
1207 ir_node *a = get_Eor_left(n);
1208 ir_node *b = get_Eor_right(n);
1210 if ((get_irn_mode(n) == mode_b)
1211 && (get_irn_op(a) == op_Proj)
1212 && (get_irn_mode(a) == mode_b)
1213 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE)
1214 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1215 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1216 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1217 mode_b, get_negated_pnc(get_Proj_proj(a)));
1218 else if ((get_irn_mode(n) == mode_b)
1219 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE))
1220 /* The Eor is a Not. Replace it by a Not. */
1221 /* ????!!!Extend to bitfield 1111111. */
1222 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1228 * Transfor a boolean Not.
1230 static ir_node *transform_node_Not(ir_node *n)
1232 ir_node *a = get_Not_op(n);
1234 if ( (get_irn_mode(n) == mode_b)
1235 && (get_irn_op(a) == op_Proj)
1236 && (get_irn_mode(a) == mode_b)
1237 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1238 /* We negate a Cmp. The Cmp has the negated result anyways! */
1239 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1240 mode_b, get_negated_pnc(get_Proj_proj(a)));
1246 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1247 * done here instead of equivalent node because in creates new
1250 static ir_node *transform_node_Proj(ir_node *proj)
1252 ir_node *n = get_Proj_pred(proj);
1257 switch (get_irn_opcode(n)) {
1259 b = get_Div_right(n);
1260 tb = computed_value(b);
1262 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1263 proj_nr = get_Proj_proj(proj);
1265 if (proj_nr == pn_Div_X_except) {
1266 /* we found an exception handler, remove it */
1269 else if (proj_nr == pn_Div_M) {
1270 /* the memory Proj can be removed */
1271 ir_node *res = get_Div_mem(n);
1272 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1278 b = get_Mod_right(n);
1279 tb = computed_value(b);
1281 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1282 proj_nr = get_Proj_proj(proj);
1284 if (proj_nr == pn_Mod_X_except) {
1285 /* we found an exception handler, remove it */
1288 else if (proj_nr == pn_Mod_M) {
1289 /* the memory Proj can be removed */
1290 ir_node *res = get_Mod_mem(n);
1291 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1297 b = get_DivMod_right(n);
1298 tb = computed_value(b);
1300 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1301 proj_nr = get_Proj_proj(proj);
1303 if (proj_nr == pn_DivMod_X_except) {
1306 else if (proj_nr == pn_DivMod_M) {
1307 /* the memory Proj can be removed */
1308 ir_node *res = get_DivMod_mem(n);
1309 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1316 if (get_opt_unreachable_code()) {
1317 b = get_Cond_selector(n);
1318 tb = computed_value(b);
1320 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1321 /* we have a constant switch */
1322 long num = get_Proj_proj(proj);
1324 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1325 if (get_tarval_long(tb) == num) {
1326 /* Do NOT create a jump here, or we will have 2 control flow ops
1327 * in a block. This case is optimized away in optimize_cf(). */
1338 /* should not happen, but if it does will be optimized away */
1346 /* we have added a Tuple, optimize it for the current Proj away */
1347 return equivalent_node_Proj(proj);
1351 * returns the operands of a commutative bin-op, if one operand is
1352 * a const, it is returned as the second one.
1354 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1356 ir_node *op_a = get_binop_left(binop);
1357 ir_node *op_b = get_binop_right(binop);
1359 assert(is_op_commutative(get_irn_op(binop)));
1361 if (get_irn_op(op_a) == op_Const) {
1372 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1373 * Such pattern may arise in bitfield stores.
1375 * value c4 value c4 & c2
1376 * AND c3 AND c1 | c3
1381 static ir_node *transform_node_Or(ir_node *or)
1385 ir_node *and_l, *c3;
1386 ir_node *value, *c4;
1387 ir_node *new_and, *new_const, *block;
1388 ir_mode *mode = get_irn_mode(or);
1390 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1392 get_comm_Binop_Ops(or, &and, &c1);
1393 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1396 get_comm_Binop_Ops(and, &or_l, &c2);
1397 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1400 get_comm_Binop_Ops(or_l, &and_l, &c3);
1401 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1404 get_comm_Binop_Ops(and_l, &value, &c4);
1405 if (get_irn_op(c4) != op_Const)
1408 /* ok, found the pattern, check for conditions */
1409 assert(mode == get_irn_mode(and));
1410 assert(mode == get_irn_mode(or_l));
1411 assert(mode == get_irn_mode(and_l));
1413 tv1 = get_Const_tarval(c1);
1414 tv2 = get_Const_tarval(c2);
1415 tv3 = get_Const_tarval(c3);
1416 tv4 = get_Const_tarval(c4);
1418 tv = tarval_or(tv4, tv2);
1419 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1420 /* have at least one 0 at the same bit position */
1424 n_tv4 = tarval_not(tv4);
1425 if (tv3 != tarval_and(tv3, n_tv4)) {
1426 /* bit in the or_mask is outside the and_mask */
1430 n_tv2 = tarval_not(tv2);
1431 if (tv1 != tarval_and(tv1, n_tv2)) {
1432 /* bit in the or_mask is outside the and_mask */
1436 /* ok, all conditions met */
1437 block = get_nodes_block(or);
1439 new_and = new_r_And(current_ir_graph, block,
1440 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1442 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1444 set_Or_left(or, new_and);
1445 set_Or_right(or, new_const);
1447 /* check for more */
1448 return transform_node_Or(or);
1452 * Tries several [inplace] [optimizing] transformations and returns an
1453 * equivalent node. The difference to equivalent_node() is that these
1454 * transformations _do_ generate new nodes, and thus the old node must
1455 * not be freed even if the equivalent node isn't the old one.
1457 static ir_node *transform_node(ir_node *n)
1459 if (n->op->transform_node)
1460 n = n->op->transform_node(n);
1465 * set the default transform node operation
1467 static ir_op *firm_set_default_transform_node(ir_op *op)
1471 op->transform_node = transform_node_##a; \
1485 op->transform_node = NULL;
1493 /* **************** Common Subexpression Elimination **************** */
1495 /** The size of the hash table used, should estimate the number of nodes
1497 #define N_IR_NODES 512
1499 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1501 return (get_Const_tarval(a) != get_Const_tarval(b))
1502 || (get_Const_type(a) != get_Const_type(b));
1505 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1507 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1510 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1512 return get_Filter_proj(a) != get_Filter_proj(b);
1515 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1517 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1518 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1521 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1523 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1526 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1528 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1529 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p);
1532 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1534 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1537 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1539 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1542 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1544 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1545 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1546 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1547 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1548 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1551 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1553 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1556 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1558 return get_Cast_type(a) != get_Cast_type(b);
1561 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1563 if (get_Load_volatility(a) == volatility_is_volatile ||
1564 get_Load_volatility(b) == volatility_is_volatile)
1565 /* NEVER do CSE on volatile Loads */
1568 return get_Load_mode(a) != get_Load_mode(b);
1571 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1573 /* NEVER do CSE on volatile Stores */
1574 return (get_Store_volatility(a) == volatility_is_volatile ||
1575 get_Load_volatility(b) == volatility_is_volatile);
1579 * set the default node attribute compare operation
1581 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1585 op->node_cmp_attr = node_cmp_attr_##a; \
1603 op->node_cmp_attr = NULL;
1611 * Compare function for two nodes in the hash table. Gets two
1612 * nodes as parameters. Returns 0 if the nodes are a cse.
1615 vt_cmp (const void *elt, const void *key)
1623 if (a == b) return 0;
1625 if ((get_irn_op(a) != get_irn_op(b)) ||
1626 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1628 /* compare if a's in and b's in are equal */
1629 irn_arity_a = get_irn_arity (a);
1630 if (irn_arity_a != get_irn_arity(b))
1633 /* for block-local cse and op_pin_state_pinned nodes: */
1634 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == op_pin_state_pinned)) {
1635 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1639 /* compare a->in[0..ins] with b->in[0..ins] */
1640 for (i = 0; i < irn_arity_a; i++)
1641 if (get_irn_n(a, i) != get_irn_n(b, i))
1645 * here, we already now that the nodes are identical except their
1648 if (a->op->node_cmp_attr)
1649 return a->op->node_cmp_attr(a, b);
1655 * Calculate a hash value of a node.
1658 ir_node_hash (ir_node *node)
1663 if (node->op == op_Const) {
1664 /* special value for const, as they only differ in their tarval. */
1665 h = ((unsigned) node->attr.con.tv)>>3 ;
1666 h = 9*h + (unsigned)get_irn_mode(node);
1667 } else if (node->op == op_SymConst) {
1668 /* special value for const, as they only differ in their symbol. */
1669 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1670 h = 9*h + (unsigned)get_irn_mode(node);
1673 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1674 h = irn_arity = get_irn_arity(node);
1676 /* consider all in nodes... except the block. */
1677 for (i = 0; i < irn_arity; i++) {
1678 h = 9*h + (unsigned)get_irn_n(node, i);
1682 h = 9*h + (unsigned) get_irn_mode (node);
1684 h = 9*h + (unsigned) get_irn_op (node);
1691 new_identities (void)
1693 return new_pset (vt_cmp, N_IR_NODES);
1697 del_identities (pset *value_table)
1699 del_pset (value_table);
1703 * Return the canonical node computing the same value as n.
1704 * Looks up the node in a hash table.
1706 * For Const nodes this is performed in the constructor, too. Const
1707 * nodes are extremely time critical because of their frequent use in
1708 * constant string arrays.
1710 static INLINE ir_node *
1711 identify (pset *value_table, ir_node *n)
1715 if (!value_table) return n;
1717 /* TODO: use a generic commutative attribute */
1718 if (get_opt_reassociation()) {
1719 if (is_op_commutative(get_irn_op(n))) {
1720 ir_node *l = get_binop_left(n);
1721 ir_node *r = get_binop_right(n);
1723 /* for commutative operators perform a OP b == b OP a */
1725 set_binop_left(n, r);
1726 set_binop_right(n, l);
1731 o = pset_find (value_table, n, ir_node_hash (n));
1740 * During construction we set the op_pin_state_pinned flag in the graph right when the
1741 * optimization is performed. The flag turning on procedure global cse could
1742 * be changed between two allocations. This way we are safe.
1744 static INLINE ir_node *
1745 identify_cons (pset *value_table, ir_node *n) {
1748 n = identify(value_table, n);
1749 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1750 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1755 * Return the canonical node computing the same value as n.
1756 * Looks up the node in a hash table, enters it in the table
1757 * if it isn't there yet.
1760 identify_remember (pset *value_table, ir_node *node)
1764 if (!value_table) return node;
1766 /* lookup or insert in hash table with given hash key. */
1767 o = pset_insert (value_table, node, ir_node_hash (node));
1769 if (o == node) return node;
1775 add_identities (pset *value_table, ir_node *node) {
1776 identify_remember (value_table, node);
1780 * garbage in, garbage out. If a node has a dead input, i.e., the
1781 * Bad node is input to the node, return the Bad node.
1783 static INLINE ir_node *
1784 gigo (ir_node *node)
1787 ir_op* op = get_irn_op(node);
1789 /* remove garbage blocks by looking at control flow that leaves the block
1790 and replacing the control flow by Bad. */
1791 if (get_irn_mode(node) == mode_X) {
1792 ir_node *block = get_nodes_block(node);
1793 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1794 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1795 irn_arity = get_irn_arity(block);
1796 for (i = 0; i < irn_arity; i++) {
1797 if (!is_Bad(get_irn_n(block, i))) break;
1799 if (i == irn_arity) return new_Bad();
1803 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1804 blocks predecessors is dead. */
1805 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1806 irn_arity = get_irn_arity(node);
1807 for (i = -1; i < irn_arity; i++) {
1808 if (is_Bad(get_irn_n(node, i))) {
1814 /* With this code we violate the agreement that local_optimize
1815 only leaves Bads in Block, Phi and Tuple nodes. */
1816 /* If Block has only Bads as predecessors it's garbage. */
1817 /* If Phi has only Bads as predecessors it's garbage. */
1818 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1819 irn_arity = get_irn_arity(node);
1820 for (i = 0; i < irn_arity; i++) {
1821 if (!is_Bad(get_irn_n(node, i))) break;
1823 if (i == irn_arity) node = new_Bad();
1831 * These optimizations deallocate nodes from the obstack.
1832 * It can only be called if it is guaranteed that no other nodes
1833 * reference this one, i.e., right after construction of a node.
1836 optimize_node (ir_node *n)
1840 opcode iro = get_irn_opcode(n);
1842 /* Allways optimize Phi nodes: part of the construction. */
1843 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1845 /* constant expression evaluation / constant folding */
1846 if (get_opt_constant_folding()) {
1847 /* constants can not be evaluated */
1848 if (iro != iro_Const) {
1849 /* try to evaluate */
1850 tv = computed_value (n);
1851 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1853 * we MUST copy the node here temporary, because it's still needed
1854 * for DBG_OPT_ALGSIM0
1856 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
1857 oldn = alloca(node_size);
1859 memcpy(oldn, n, node_size);
1860 CLONE_ARR_A(ir_node *, oldn->in, n->in);
1862 /* ARG, copy the in array, we need it for statistics */
1863 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
1865 /* evaluation was successful -- replace the node. */
1866 obstack_free (current_ir_graph->obst, n);
1867 n = new_Const (get_tarval_mode (tv), tv);
1869 DBG_OPT_ALGSIM0(oldn, n);
1875 /* remove unnecessary nodes */
1876 if (get_opt_constant_folding() ||
1877 (iro == iro_Phi) || /* always optimize these nodes. */
1879 (iro == iro_Proj) ||
1880 (iro == iro_Block) ) /* Flags tested local. */
1881 n = equivalent_node (n);
1883 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1885 /** common subexpression elimination **/
1886 /* Checks whether n is already available. */
1887 /* The block input is used to distinguish different subexpressions. Right
1888 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
1889 subexpressions within a block. */
1891 n = identify_cons (current_ir_graph->value_table, n);
1894 /* We found an existing, better node, so we can deallocate the old node. */
1895 obstack_free (current_ir_graph->obst, oldn);
1900 /* Some more constant expression evaluation that does not allow to
1902 iro = get_irn_opcode(n);
1903 if (get_opt_constant_folding() ||
1904 (iro == iro_Cond) ||
1905 (iro == iro_Proj)) /* Flags tested local. */
1906 n = transform_node (n);
1908 /* Remove nodes with dead (Bad) input.
1909 Run always for transformation induced Bads. */
1912 /* Now we have a legal, useful node. Enter it in hash table for cse */
1913 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1914 n = identify_remember (current_ir_graph->value_table, n);
1922 * These optimizations never deallocate nodes. This can cause dead
1923 * nodes lying on the obstack. Remove these by a dead node elimination,
1924 * i.e., a copying garbage collection.
1927 optimize_in_place_2 (ir_node *n)
1931 opcode iro = get_irn_opcode(n);
1933 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1935 /* if not optimize return n */
1938 /* Here this is possible. Why? */
1943 /* constant expression evaluation / constant folding */
1944 if (get_opt_constant_folding()) {
1945 /* constants can not be evaluated */
1946 if (iro != iro_Const) {
1947 /* try to evaluate */
1948 tv = computed_value (n);
1949 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1950 /* evaluation was successful -- replace the node. */
1951 n = new_Const (get_tarval_mode (tv), tv);
1953 DBG_OPT_ALGSIM0(oldn, n);
1959 /* remove unnecessary nodes */
1960 if (get_opt_constant_folding() ||
1961 (iro == iro_Phi) || /* always optimize these nodes. */
1962 (iro == iro_Id) || /* ... */
1963 (iro == iro_Proj) || /* ... */
1964 (iro == iro_Block) ) /* Flags tested local. */
1965 n = equivalent_node (n);
1967 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1969 /** common subexpression elimination **/
1970 /* Checks whether n is already available. */
1971 /* The block input is used to distinguish different subexpressions. Right
1972 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
1973 subexpressions within a block. */
1974 if (get_opt_cse()) {
1975 n = identify (current_ir_graph->value_table, n);
1978 /* Some more constant expression evaluation. */
1979 iro = get_irn_opcode(n);
1980 if (get_opt_constant_folding() ||
1981 (iro == iro_Cond) ||
1982 (iro == iro_Proj)) /* Flags tested local. */
1983 n = transform_node (n);
1985 /* Remove nodes with dead (Bad) input.
1986 Run always for transformation induced Bads. */
1989 /* Now we can verify the node, as it has no dead inputs any more. */
1992 /* Now we have a legal, useful node. Enter it in hash table for cse.
1993 Blocks should be unique anyways. (Except the successor of start:
1994 is cse with the start block!) */
1995 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1996 n = identify_remember (current_ir_graph->value_table, n);
2002 * Wrapper for external use, set proper status bits after optimization.
2005 optimize_in_place (ir_node *n)
2007 /* Handle graph state */
2008 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2010 if (get_opt_global_cse())
2011 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2012 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2013 set_irg_outs_inconsistent(current_ir_graph);
2015 /* Maybe we could also test whether optimizing the node can
2016 change the control graph. */
2017 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2018 set_irg_dom_inconsistent(current_ir_graph);
2019 return optimize_in_place_2 (n);
2023 * set the default ir op operations
2025 ir_op *firm_set_default_operations(ir_op *op)
2027 op = firm_set_default_computed_value(op);
2028 op = firm_set_default_equivalent_node(op);
2029 op = firm_set_default_transform_node(op);
2030 op = firm_set_default_node_cmp_attr(op);