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 */
57 * return the value of a Constant
59 static tarval *computed_value_Const(ir_node *n)
61 return get_Const_tarval(n);
65 * return the value of a 'sizeof' SymConst
67 static tarval *computed_value_SymConst(ir_node *n)
69 if ((get_SymConst_kind(n) == symconst_size) &&
70 (get_type_state(get_SymConst_type(n))) == layout_fixed)
71 return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
75 static tarval *computed_value_Add(ir_node *n)
77 ir_node *a = get_Add_left(n);
78 ir_node *b = get_Add_right(n);
80 tarval *ta = value_of(a);
81 tarval *tb = value_of(b);
83 if ((ta != tarval_bad) && (tb != tarval_bad)
84 && (get_irn_mode(a) == get_irn_mode(b))
85 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
86 return tarval_add(ta, tb);
91 static tarval *computed_value_Sub(ir_node *n)
93 ir_node *a = get_Sub_left(n);
94 ir_node *b = get_Sub_right(n);
100 return get_tarval_null(get_irn_mode(n));
105 if ((ta != tarval_bad) && (tb != tarval_bad)
106 && (get_irn_mode(a) == get_irn_mode(b))
107 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
108 return tarval_sub(ta, tb);
113 static tarval *computed_value_Minus(ir_node *n)
115 ir_node *a = get_Minus_op(n);
116 tarval *ta = value_of(a);
118 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
119 return tarval_neg(ta);
124 static tarval *computed_value_Mul(ir_node *n)
126 ir_node *a = get_Mul_left(n);
127 ir_node *b = get_Mul_right(n);
129 tarval *ta = value_of(a);
130 tarval *tb = value_of(b);
132 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
133 return tarval_mul(ta, tb);
135 /* a*0 = 0 or 0*b = 0:
136 calls computed_value recursive and returns the 0 with proper
140 if ( ( ((v = ta) != tarval_bad)
141 && (v == get_mode_null(get_tarval_mode(v))) )
142 || ( ((v = tb) != tarval_bad)
143 && (v == get_mode_null(get_tarval_mode(v))) )) {
150 static tarval *computed_value_Quot(ir_node *n)
152 ir_node *a = get_Quot_left(n);
153 ir_node *b = get_Quot_right(n);
155 tarval *ta = value_of(a);
156 tarval *tb = value_of(b);
158 /* This was missing in original implementation. Why? */
159 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
160 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
161 return tarval_quo(ta, tb);
166 static tarval *computed_value_Div(ir_node *n)
168 ir_node *a = get_Div_left(n);
169 ir_node *b = get_Div_right(n);
171 tarval *ta = value_of(a);
172 tarval *tb = value_of(b);
174 /* This was missing in original implementation. Why? */
175 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
176 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
177 return tarval_div(ta, tb);
182 static tarval *computed_value_Mod(ir_node *n)
184 ir_node *a = get_Mod_left(n);
185 ir_node *b = get_Mod_right(n);
187 tarval *ta = value_of(a);
188 tarval *tb = value_of(b);
190 /* This was missing in original implementation. Why? */
191 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
192 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
193 return tarval_mod(ta, tb);
199 static tarval *computed_value_Abs(ir_node *n)
201 ir_node *a = get_Abs_op(n);
202 tarval *ta = value_of(a);
204 if (ta != tarval_bad)
205 return tarval_abs(ta);
210 static tarval *computed_value_And(ir_node *n)
212 ir_node *a = get_And_left(n);
213 ir_node *b = get_And_right(n);
215 tarval *ta = value_of(a);
216 tarval *tb = value_of(b);
218 if ((ta != tarval_bad) && (tb != tarval_bad)) {
219 return tarval_and (ta, tb);
223 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_NULL)
224 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
231 static tarval *computed_value_Or(ir_node *n)
233 ir_node *a = get_Or_left(n);
234 ir_node *b = get_Or_right(n);
236 tarval *ta = value_of(a);
237 tarval *tb = value_of(b);
239 if ((ta != tarval_bad) && (tb != tarval_bad)) {
240 return tarval_or (ta, tb);
243 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
244 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
251 static tarval *computed_value_Eor(ir_node *n)
253 ir_node *a = get_Eor_left(n);
254 ir_node *b = get_Eor_right(n);
256 tarval *ta = value_of(a);
257 tarval *tb = value_of(b);
259 if ((ta != tarval_bad) && (tb != tarval_bad)) {
260 return tarval_eor (ta, tb);
265 static tarval *computed_value_Not(ir_node *n)
267 ir_node *a = get_Not_op(n);
268 tarval *ta = value_of(a);
270 if (ta != tarval_bad)
271 return tarval_not(ta);
276 static tarval *computed_value_Shl(ir_node *n)
278 ir_node *a = get_Shl_left(n);
279 ir_node *b = get_Shl_right(n);
281 tarval *ta = value_of(a);
282 tarval *tb = value_of(b);
284 if ((ta != tarval_bad) && (tb != tarval_bad)) {
285 return tarval_shl (ta, tb);
290 static tarval *computed_value_Shr(ir_node *n)
292 ir_node *a = get_Shr_left(n);
293 ir_node *b = get_Shr_right(n);
295 tarval *ta = value_of(a);
296 tarval *tb = value_of(b);
298 if ((ta != tarval_bad) && (tb != tarval_bad)) {
299 return tarval_shr (ta, tb);
304 static tarval *computed_value_Shrs(ir_node *n)
306 ir_node *a = get_Shrs_left(n);
307 ir_node *b = get_Shrs_right(n);
309 tarval *ta = value_of(a);
310 tarval *tb = value_of(b);
312 if ((ta != tarval_bad) && (tb != tarval_bad)) {
313 return tarval_shrs (ta, tb);
318 static tarval *computed_value_Rot(ir_node *n)
320 ir_node *a = get_Rot_left(n);
321 ir_node *b = get_Rot_right(n);
323 tarval *ta = value_of(a);
324 tarval *tb = value_of(b);
326 if ((ta != tarval_bad) && (tb != tarval_bad)) {
327 return tarval_rot (ta, tb);
332 static tarval *computed_value_Conv(ir_node *n)
334 ir_node *a = get_Conv_op(n);
335 tarval *ta = value_of(a);
337 if (ta != tarval_bad)
338 return tarval_convert_to(ta, get_irn_mode(n));
343 static tarval *computed_value_Proj(ir_node *n)
345 ir_node *a = get_Proj_pred(n), *b;
348 /* Optimize Cmp nodes.
349 This performs a first step of unreachable code elimination.
350 Proj can not be computed, but folding a Cmp above the Proj here is
351 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
353 There are several case where we can evaluate a Cmp node:
354 1. The nodes compared are both the same. If we compare for
355 equal, greater equal, ... this will return true, else it
356 will return false. This step relies on cse.
357 2. The predecessors of Cmp are target values. We can evaluate
359 3. The predecessors are Allocs or void* constants. Allocs never
360 return NULL, they raise an exception. Therefore we can predict
362 switch (get_irn_opcode(a)) {
364 aa = get_Cmp_left(a);
365 ab = get_Cmp_right(a);
367 if (aa == ab) { /* 1.: */
368 /* This is a trick with the bits used for encoding the Cmp
369 Proj numbers, the following statement is not the same:
370 return new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
371 return new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
373 tarval *taa = computed_value (aa);
374 tarval *tab = computed_value (ab);
376 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
377 /* strange checks... */
378 pnc_number flags = tarval_cmp (taa, tab);
379 if (flags != False) {
380 return new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
382 } else { /* check for 3.: */
383 ir_node *aaa = skip_Id(skip_Proj(aa));
384 ir_node *aba = skip_Id(skip_Proj(ab));
386 if ( ( (/* aa is ProjP and aaa is Alloc */
387 (get_irn_op(aa) == op_Proj)
388 && (mode_is_reference(get_irn_mode(aa)))
389 && (get_irn_op(aaa) == op_Alloc))
390 && ( (/* ab is constant void */
391 (get_irn_op(ab) == op_Const)
392 && (mode_is_reference(get_irn_mode(ab)))
393 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
394 || (/* ab is other Alloc */
395 (get_irn_op(ab) == op_Proj)
396 && (mode_is_reference(get_irn_mode(ab)))
397 && (get_irn_op(aba) == op_Alloc)
399 || (/* aa is void and aba is Alloc */
400 (get_irn_op(aa) == op_Const)
401 && (mode_is_reference(get_irn_mode(aa)))
402 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
403 && (get_irn_op(ab) == op_Proj)
404 && (mode_is_reference(get_irn_mode(ab)))
405 && (get_irn_op(aba) == op_Alloc)))
407 return new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
414 tarval *tb = value_of(b = get_DivMod_right(a));
415 tarval *ta = value_of(a = get_DivMod_left(a));
417 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
418 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
420 if (get_Proj_proj(n)== pn_DivMod_res_div)
421 return tarval_div(ta, tb);
422 else if (get_Proj_proj(n)== pn_DivMod_res_mod)
423 return tarval_mod(ta, tb);
430 tarval *tb = value_of(b = get_Div_right(a));
431 tarval *ta = value_of(a = get_Div_left(a));
433 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
434 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
436 if (get_Proj_proj(n)== pn_Div_res)
437 return tarval_div(ta, tb);
444 tarval *tb = value_of(b = get_Mod_right(a));
445 tarval *ta = value_of(a = get_Mod_left(a));
447 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
448 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
450 if (get_Proj_proj(n)== pn_Mod_res)
451 return tarval_mod(ta, tb);
463 * If the parameter n can be computed, return its value, else tarval_bad.
464 * Performs constant folding.
466 * @param n The node this should be evaluated
468 tarval *computed_value(ir_node *n)
470 if (n->op->computed_value)
471 return n->op->computed_value(n);
476 * set the default computed_value evaluator
478 static ir_op *firm_set_default_computed_value(ir_op *op)
482 op->computed_value = computed_value_##a; \
507 op->computed_value = NULL;
515 /* returns 1 if the a and b are pointers to different locations. */
517 different_identity (ir_node *a, ir_node *b)
519 assert (mode_is_reference(get_irn_mode (a))
520 && mode_is_reference(get_irn_mode (b)));
522 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
523 ir_node *a1 = get_Proj_pred (a);
524 ir_node *b1 = get_Proj_pred (b);
525 if (a1 != b1 && get_irn_op (a1) == op_Alloc
526 && get_irn_op (b1) == op_Alloc)
533 static ir_node *equivalent_node_Block(ir_node *n)
537 /* The Block constructor does not call optimize, but mature_immBlock
538 calls the optimization. */
539 assert(get_Block_matured(n));
541 /* Straightening: a single entry Block following a single exit Block
542 can be merged, if it is not the Start block. */
543 /* !!! Beware, all Phi-nodes of n must have been optimized away.
544 This should be true, as the block is matured before optimize is called.
545 But what about Phi-cycles with the Phi0/Id that could not be resolved?
546 Remaining Phi nodes are just Ids. */
547 if ((get_Block_n_cfgpreds(n) == 1) &&
548 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
549 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
550 if (predblock == oldn) {
551 /* Jmp jumps into the block it is in -- deal self cycle. */
553 DBG_OPT_DEAD(oldn, n);
554 } else if (get_opt_control_flow_straightening()) {
556 DBG_OPT_STG(oldn, n);
559 else if ((get_Block_n_cfgpreds(n) == 1) &&
560 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
561 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
562 if (predblock == oldn) {
563 /* Jmp jumps into the block it is in -- deal self cycle. */
565 DBG_OPT_DEAD(oldn, n);
568 else if ((get_Block_n_cfgpreds(n) == 2) &&
569 (get_opt_control_flow_weak_simplification())) {
570 /* Test whether Cond jumps twice to this block
571 @@@ we could do this also with two loops finding two preds from several ones. */
572 ir_node *a = get_Block_cfgpred(n, 0);
573 ir_node *b = get_Block_cfgpred(n, 1);
575 if ((get_irn_op(a) == op_Proj) &&
576 (get_irn_op(b) == op_Proj) &&
577 (get_Proj_pred(a) == get_Proj_pred(b)) &&
578 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
579 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
580 /* Also a single entry Block following a single exit Block. Phis have
581 twice the same operand and will be optimized away. */
582 n = get_nodes_block(a);
583 DBG_OPT_IFSIM(oldn, a, b, n);
585 } else if (get_opt_unreachable_code() &&
586 (n != current_ir_graph->start_block) &&
587 (n != current_ir_graph->end_block) ) {
589 /* If all inputs are dead, this block is dead too, except if it is
590 the start or end block. This is a step of unreachable code
592 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
593 if (!is_Bad(get_Block_cfgpred(n, i))) break;
595 if (i == get_Block_n_cfgpreds(n))
603 * Returns a equivalent node for a Jmp, a Bad :-)
604 * Of course this only happens if the Block of the Jmp is Bad.
606 static ir_node *equivalent_node_Jmp(ir_node *n)
608 /* GL: Why not same for op_Raise?? */
609 /* unreachable code elimination */
610 if (is_Bad(get_nodes_block(n)))
616 static ir_node *equivalent_node_Cond(ir_node *n)
618 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
619 See cases for iro_Cond and iro_Proj in transform_node. */
624 * Use algebraic simplification a v a = a.
626 static ir_node *equivalent_node_Or(ir_node *n)
630 ir_node *a = get_Or_left(n);
631 ir_node *b = get_Or_right(n);
637 DBG_OPT_ALGSIM1(oldn, a, b, n);
644 * optimize operations that are commutative and have neutral 0,
645 * so a op 0 = 0 op a = a.
647 static ir_node *equivalent_node_neutral_zero(ir_node *n)
651 ir_node *a = get_binop_left(n);
652 ir_node *b = get_binop_right(n);
657 /* After running compute_node there is only one constant predecessor.
658 Find this predecessors value and remember the other node: */
659 if ((tv = computed_value(a)) != tarval_bad) {
661 } else if ((tv = computed_value(b)) != tarval_bad) {
666 /* If this predecessors constant value is zero, the operation is
667 unnecessary. Remove it: */
668 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
671 DBG_OPT_ALGSIM1(oldn, a, b, n);
677 #define equivalent_node_Add equivalent_node_neutral_zero
678 #define equivalent_node_Eor equivalent_node_neutral_zero
681 * optimize operations that are not commutative but have neutral 0 on left,
684 static ir_node *equivalent_node_left_zero(ir_node *n)
688 ir_node *a = get_binop_left(n);
689 ir_node *b = get_binop_right(n);
691 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_NULL) {
694 DBG_OPT_ALGSIM1(oldn, a, b, n);
700 #define equivalent_node_Sub equivalent_node_left_zero
701 #define equivalent_node_Shl equivalent_node_left_zero
702 #define equivalent_node_Shr equivalent_node_left_zero
703 #define equivalent_node_Shrs equivalent_node_left_zero
704 #define equivalent_node_Rot equivalent_node_left_zero
707 * Er, a "symmetic unop", ie op(op(n)) = n.
709 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
712 ir_node *pred = get_unop_op(n);
714 /* optimize symmetric unop */
715 if (get_irn_op(pred) == get_irn_op(n)) {
716 n = get_unop_op(pred);
717 DBG_OPT_ALGSIM2(oldn, pred, n);
723 #define equivalent_node_Not equivalent_node_symmetric_unop
725 /* --x == x */ /* ??? Is this possible or can --x raise an
726 out of bounds exception if min =! max? */
727 #define equivalent_node_Minus equivalent_node_symmetric_unop
730 * Optimize a * 1 = 1 * a = a.
732 static ir_node *equivalent_node_Mul(ir_node *n)
736 ir_node *a = get_Mul_left(n);
737 ir_node *b = get_Mul_right(n);
739 /* Mul is commutative and has again an other neutral element. */
740 if (classify_tarval (computed_value (a)) == TV_CLASSIFY_ONE) {
742 DBG_OPT_ALGSIM1(oldn, a, b, n);
743 } else if (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE) {
745 DBG_OPT_ALGSIM1(oldn, a, b, n);
751 * Optimize a / 1 = a.
753 static ir_node *equivalent_node_Div(ir_node *n)
755 ir_node *a = get_Div_left(n);
756 ir_node *b = get_Div_right(n);
758 /* Div is not commutative. */
759 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
760 /* Turn Div into a tuple (mem, bad, a) */
761 ir_node *mem = get_Div_mem(n);
762 turn_into_tuple(n, 3);
763 set_Tuple_pred(n, pn_Div_M, mem);
764 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
765 set_Tuple_pred(n, pn_Div_res, a);
771 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
773 static ir_node *equivalent_node_And(ir_node *n)
777 ir_node *a = get_And_left(n);
778 ir_node *b = get_And_right(n);
781 n = a; /* And has it's own neutral element */
782 } else if (classify_tarval(computed_value(a)) == TV_CLASSIFY_ALL_ONE) {
784 DBG_OPT_ALGSIM1(oldn, a, b, n);
785 } else if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ALL_ONE) {
787 DBG_OPT_ALGSIM1(oldn, a, b, n);
793 * Try to remove useless conv's:
795 static ir_node *equivalent_node_Conv(ir_node *n)
798 ir_node *a = get_Conv_op(n);
801 ir_mode *n_mode = get_irn_mode(n);
802 ir_mode *a_mode = get_irn_mode(a);
804 if (n_mode == a_mode) { /* No Conv necessary */
806 DBG_OPT_ALGSIM3(oldn, a, n);
807 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
811 n_mode = get_irn_mode(n);
812 b_mode = get_irn_mode(b);
814 if (n_mode == b_mode) {
815 if (n_mode == mode_b) {
816 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
817 DBG_OPT_ALGSIM1(oldn, a, b, n);
819 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
820 if (smaller_mode(b_mode, a_mode)){
821 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
822 DBG_OPT_ALGSIM1(oldn, a, b, n);
830 static ir_node *equivalent_node_Phi(ir_node *n)
832 /* Several optimizations:
833 - no Phi in start block.
834 - remove Id operators that are inputs to Phi
835 - fold Phi-nodes, iff they have only one predecessor except
841 ir_node *block = NULL; /* to shutup gcc */
842 ir_node *first_val = NULL; /* to shutup gcc */
843 ir_node *scnd_val = NULL; /* to shutup gcc */
845 if (!get_opt_normalize()) return n;
847 n_preds = get_Phi_n_preds(n);
849 block = get_nodes_block(n);
850 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
851 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
852 if ((is_Bad(block)) || /* Control dead */
853 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
854 return new_Bad(); /* in the Start Block. */
856 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
859 /* first we test for a special case: */
860 /* Confirm is a special node fixing additional information for a
861 value that is known at a certain point. This is useful for
862 dataflow analysis. */
864 ir_node *a = get_Phi_pred(n, 0);
865 ir_node *b = get_Phi_pred(n, 1);
866 if ( (get_irn_op(a) == op_Confirm)
867 && (get_irn_op(b) == op_Confirm)
868 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
869 && (get_irn_n(a, 1) == get_irn_n (b, 1))
870 && (a->data.num == (~b->data.num & irpn_True) )) {
871 return get_irn_n(a, 0);
876 /* If the Block has a Bad pred, we also have one. */
877 for (i = 0; i < n_preds; ++i)
878 if (is_Bad (get_Block_cfgpred(block, i)))
879 set_Phi_pred(n, i, new_Bad());
881 /* Find first non-self-referencing input */
882 for (i = 0; i < n_preds; ++i) {
883 first_val = get_Phi_pred(n, i);
884 if ( (first_val != n) /* not self pointer */
886 && (get_irn_op(first_val) != op_Bad)
888 ) { /* value not dead */
889 break; /* then found first value. */
893 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
894 if (i >= n_preds) { return new_Bad(); }
898 /* follow_Id () for rest of inputs, determine if any of these
899 are non-self-referencing */
900 while (++i < n_preds) {
901 scnd_val = get_Phi_pred(n, i);
903 && (scnd_val != first_val)
905 && (get_irn_op(scnd_val) != op_Bad)
912 /* Fold, if no multiple distinct non-self-referencing inputs */
915 DBG_OPT_PHI(oldn, first_val, n);
917 /* skip the remaining Ids (done in get_Phi_pred). */
918 /* superfluous, since we walk all to propagate Block's Bads.
919 while (++i < n_preds) get_Phi_pred(n, i); */
925 * optimize Proj(Tuple) and gigo for ProjX in Bad block
927 static ir_node *equivalent_node_Proj(ir_node *n)
931 ir_node *a = get_Proj_pred(n);
933 if ( get_irn_op(a) == op_Tuple) {
934 /* Remove the Tuple/Proj combination. */
935 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
936 n = get_Tuple_pred(a, get_Proj_proj(n));
937 DBG_OPT_TUPLE(oldn, a, n);
939 assert(0); /* This should not happen! */
942 } else if (get_irn_mode(n) == mode_X &&
943 is_Bad(get_nodes_block(n))) {
944 /* Remove dead control flow -- early gigo. */
953 static ir_node *equivalent_node_Id(ir_node *n)
963 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
964 * perform no actual computation, as, e.g., the Id nodes. It does not create
965 * new nodes. It is therefore safe to free n if the node returned is not n.
966 * If a node returns a Tuple we can not just skip it. If the size of the
967 * in array fits, we transform n into a tuple (e.g., Div).
970 equivalent_node(ir_node *n)
972 if (n->op->equivalent_node)
973 return n->op->equivalent_node(n);
978 * set the default equivalent node operation
980 static ir_op *firm_set_default_equivalent_node(ir_op *op)
984 op->equivalent_node = equivalent_node_##a; \
1009 op->equivalent_node = NULL;
1017 * Do node specific optimizations of nodes predecessors.
1020 optimize_preds(ir_node *n) {
1021 ir_node *a = NULL, *b = NULL;
1023 /* get the operands we will work on for simple cases. */
1025 a = get_binop_left(n);
1026 b = get_binop_right(n);
1027 } else if (is_unop(n)) {
1031 switch (get_irn_opcode(n)) {
1034 /* We don't want Cast as input to Cmp. */
1035 if (get_irn_op(a) == op_Cast) {
1039 if (get_irn_op(b) == op_Cast) {
1041 set_Cmp_right(n, b);
1049 static ir_node *transform_node_Div(ir_node *n)
1051 tarval *tv = computed_value(n);
1053 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1055 if (tv != tarval_bad) {
1056 /* Turn Div into a tuple (mem, bad, value) */
1057 ir_node *mem = get_Div_mem(n);
1059 turn_into_tuple(n, 3);
1060 set_Tuple_pred(n, pn_Div_M, mem);
1061 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1062 set_Tuple_pred(n, pn_Div_res, new_Const(get_tarval_mode(tv), tv));
1067 static ir_node *transform_node_Mod(ir_node *n)
1069 tarval *tv = computed_value(n);
1071 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1073 if (tv != tarval_bad) {
1074 /* Turn Mod into a tuple (mem, bad, value) */
1075 ir_node *mem = get_Mod_mem(n);
1076 turn_into_tuple(n, 3);
1077 set_Tuple_pred(n, pn_Mod_M, mem);
1078 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1079 set_Tuple_pred(n, pn_Mod_res, new_Const(get_tarval_mode(tv), tv));
1084 static ir_node *transform_node_DivMod(ir_node *n)
1088 ir_node *a = get_DivMod_left(n);
1089 ir_node *b = get_DivMod_right(n);
1090 ir_mode *mode = get_irn_mode(a);
1091 tarval *ta = value_of(a);
1092 tarval *tb = value_of(b);
1094 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1097 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1099 if (tb != tarval_bad) {
1100 if (tb == get_mode_one(get_tarval_mode(tb))) {
1101 b = new_Const (mode, get_mode_null(mode));
1103 } else if (ta != tarval_bad) {
1104 tarval *resa, *resb;
1105 resa = tarval_div (ta, tb);
1106 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1107 Jmp for X result!? */
1108 resb = tarval_mod (ta, tb);
1109 if (resb == tarval_bad) return n; /* Causes exception! */
1110 a = new_Const (mode, resa);
1111 b = new_Const (mode, resb);
1114 } else if (ta == get_mode_null(mode)) {
1118 if (evaluated) { /* replace by tuple */
1119 ir_node *mem = get_DivMod_mem(n);
1120 turn_into_tuple(n, 4);
1121 set_Tuple_pred(n, pn_DivMod_M, mem);
1122 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1123 set_Tuple_pred(n, pn_DivMod_res_div, a);
1124 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1125 assert(get_nodes_block(n));
1131 static ir_node *transform_node_Cond(ir_node *n)
1133 /* Replace the Cond by a Jmp if it branches on a constant
1136 ir_node *a = get_Cond_selector(n);
1137 tarval *ta = value_of(a);
1139 if ((ta != tarval_bad) &&
1140 (get_irn_mode(a) == mode_b) &&
1141 (get_opt_unreachable_code())) {
1142 /* It's a boolean Cond, branching on a boolean constant.
1143 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1144 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1145 turn_into_tuple(n, 2);
1146 if (ta == tarval_b_true) {
1147 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1148 set_Tuple_pred(n, pn_Cond_true, jmp);
1150 set_Tuple_pred(n, pn_Cond_false, jmp);
1151 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1153 /* We might generate an endless loop, so keep it alive. */
1154 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1155 } else if ((ta != tarval_bad) &&
1156 (get_irn_mode(a) == mode_Iu) &&
1157 (get_Cond_kind(n) == dense) &&
1158 (get_opt_unreachable_code())) {
1159 /* I don't want to allow Tuples smaller than the biggest Proj.
1160 Also this tuple might get really big...
1161 I generate the Jmp here, and remember it in link. Link is used
1162 when optimizing Proj. */
1163 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1164 /* We might generate an endless loop, so keep it alive. */
1165 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1166 } else if ((get_irn_op(a) == op_Eor)
1167 && (get_irn_mode(a) == mode_b)
1168 && (classify_tarval(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1169 /* The Eor is a negate. Generate a new Cond without the negate,
1170 simulate the negate by exchanging the results. */
1171 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1173 } else if ((get_irn_op(a) == op_Not)
1174 && (get_irn_mode(a) == mode_b)) {
1175 /* A Not before the Cond. Generate a new Cond without the Not,
1176 simulate the Not by exchanging the results. */
1177 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1183 static ir_node *transform_node_Eor(ir_node *n)
1185 ir_node *a = get_Eor_left(n);
1186 ir_node *b = get_Eor_right(n);
1188 if ((get_irn_mode(n) == mode_b)
1189 && (get_irn_op(a) == op_Proj)
1190 && (get_irn_mode(a) == mode_b)
1191 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE)
1192 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1193 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1194 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1195 mode_b, get_negated_pnc(get_Proj_proj(a)));
1196 else if ((get_irn_mode(n) == mode_b)
1197 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE))
1198 /* The Eor is a Not. Replace it by a Not. */
1199 /* ????!!!Extend to bitfield 1111111. */
1200 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1206 * Transfor a boolean Not.
1208 static ir_node *transform_node_Not(ir_node *n)
1210 ir_node *a = get_Not_op(n);
1212 if ( (get_irn_mode(n) == mode_b)
1213 && (get_irn_op(a) == op_Proj)
1214 && (get_irn_mode(a) == mode_b)
1215 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1216 /* We negate a Cmp. The Cmp has the negated result anyways! */
1217 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1218 mode_b, get_negated_pnc(get_Proj_proj(a)));
1224 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1225 * done here instead of equivalent node because in creates new
1228 static ir_node *transform_node_Proj(ir_node *proj)
1230 ir_node *n = get_Proj_pred(proj);
1235 switch (get_irn_opcode(n)) {
1237 b = get_Div_right(n);
1238 tb = computed_value(b);
1240 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1241 proj_nr = get_Proj_proj(proj);
1243 if (proj_nr == pn_Div_X_except) {
1244 /* we found an exception handler, remove it */
1247 else if (proj_nr == pn_Div_M) {
1248 /* the memory Proj can be removed */
1249 ir_node *res = get_Div_mem(n);
1250 set_Div_mem(n, get_irg_initial_mem(current_ir_graph));
1256 b = get_Mod_right(n);
1257 tb = computed_value(b);
1259 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1260 proj_nr = get_Proj_proj(proj);
1262 if (proj_nr == pn_Mod_X_except) {
1263 /* we found an exception handler, remove it */
1266 else if (proj_nr == pn_Mod_M) {
1267 /* the memory Proj can be removed */
1268 ir_node *res = get_Mod_mem(n);
1269 set_Mod_mem(n, get_irg_initial_mem(current_ir_graph));
1275 b = get_DivMod_right(n);
1276 tb = computed_value(b);
1278 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1279 proj_nr = get_Proj_proj(proj);
1281 if (proj_nr == pn_DivMod_X_except) {
1284 else if (proj_nr == pn_DivMod_M) {
1285 /* the memory Proj can be removed */
1286 ir_node *res = get_DivMod_mem(n);
1287 set_DivMod_mem(n, get_irg_initial_mem(current_ir_graph));
1294 if (get_opt_unreachable_code()) {
1295 b = get_Cond_selector(n);
1296 tb = computed_value(b);
1298 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1299 /* we have a constant switch */
1300 long num = get_Proj_proj(proj);
1302 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1303 if (get_tarval_long(tb) == num) {
1304 /* Do NOT create a jump here, or we will have 2 control flow ops
1305 * in a block. This case is optimized away in optimize_cf(). */
1316 /* should not happen, but if it does will be optimized away */
1324 /* we have added a Tuple, optimize it for the current Proj away */
1325 return equivalent_node_Proj(proj);
1329 * returns the operands of a commutative bin-op, if one operand is
1330 * a const, it is returned as the second one.
1332 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1334 ir_node *op_a = get_binop_left(binop);
1335 ir_node *op_b = get_binop_right(binop);
1337 assert(is_op_commutative(get_irn_op(binop)));
1339 if (get_irn_op(op_a) == op_Const) {
1350 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1351 * Such pattern may arise in bitfield stores.
1353 * value c4 value c4 & c2
1354 * AND c3 AND c1 | c3
1359 static ir_node *transform_node_Or(ir_node *or)
1363 ir_node *and_l, *c3;
1364 ir_node *value, *c4;
1365 ir_node *new_and, *new_const, *block;
1366 ir_mode *mode = get_irn_mode(or);
1368 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1370 get_comm_Binop_Ops(or, &and, &c1);
1371 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1374 get_comm_Binop_Ops(and, &or_l, &c2);
1375 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1378 get_comm_Binop_Ops(or_l, &and_l, &c3);
1379 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1382 get_comm_Binop_Ops(and_l, &value, &c4);
1383 if (get_irn_op(c4) != op_Const)
1386 /* ok, found the pattern, check for conditions */
1387 assert(mode == get_irn_mode(and));
1388 assert(mode == get_irn_mode(or_l));
1389 assert(mode == get_irn_mode(and_l));
1391 tv1 = get_Const_tarval(c1);
1392 tv2 = get_Const_tarval(c2);
1393 tv3 = get_Const_tarval(c3);
1394 tv4 = get_Const_tarval(c4);
1396 tv = tarval_or(tv4, tv2);
1397 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1398 /* have at least one 0 at the same bit position */
1402 n_tv4 = tarval_not(tv4);
1403 if (tv3 != tarval_and(tv3, n_tv4)) {
1404 /* bit in the or_mask is outside the and_mask */
1408 n_tv2 = tarval_not(tv2);
1409 if (tv1 != tarval_and(tv1, n_tv2)) {
1410 /* bit in the or_mask is outside the and_mask */
1414 /* ok, all conditions met */
1415 block = get_nodes_block(or);
1417 new_and = new_r_And(current_ir_graph, block,
1418 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1420 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1422 set_Or_left(or, new_and);
1423 set_Or_right(or, new_const);
1425 /* check for more */
1426 return transform_node_Or(or);
1430 * Tries several [inplace] [optimizing] transformations and returns an
1431 * equivalent node. The difference to equivalent_node() is that these
1432 * transformations _do_ generate new nodes, and thus the old node must
1433 * not be freed even if the equivalent node isn't the old one.
1435 static ir_node *transform_node(ir_node *n)
1437 if (n->op->transform_node)
1438 n = n->op->transform_node(n);
1443 * set the default transform node operation
1445 static ir_op *firm_set_default_transform_node(ir_op *op)
1449 op->transform_node = transform_node_##a; \
1462 op->transform_node = NULL;
1470 /* **************** Common Subexpression Elimination **************** */
1472 /** The size of the hash table used, should estimate the number of nodes
1474 #define N_IR_NODES 512
1476 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1478 return (get_Const_tarval(a) != get_Const_tarval(b))
1479 || (get_Const_type(a) != get_Const_type(b));
1482 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1484 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1487 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1489 return get_Filter_proj(a) != get_Filter_proj(b);
1492 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1494 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1495 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1498 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1500 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1503 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1505 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1506 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p);
1509 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1511 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1514 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1516 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1519 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1521 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1522 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1523 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1524 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1525 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1528 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1530 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1533 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1535 return get_Cast_type(a) != get_Cast_type(b);
1538 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
1540 if (get_Load_volatility(a) == volatility_is_volatile ||
1541 get_Load_volatility(b) == volatility_is_volatile)
1542 /* NEVER do CSE on volatile Loads */
1545 return get_Load_mode(a) != get_Load_mode(b);
1548 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
1550 /* NEVER do CSE on volatile Stores */
1551 return (get_Store_volatility(a) == volatility_is_volatile ||
1552 get_Load_volatility(b) == volatility_is_volatile);
1556 * set the default node attribute compare operation
1558 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1562 op->node_cmp_attr = node_cmp_attr_##a; \
1580 op->node_cmp_attr = NULL;
1588 * Compare function for two nodes in the hash table. Gets two
1589 * nodes as parameters. Returns 0 if the nodes are a cse.
1592 vt_cmp (const void *elt, const void *key)
1600 if (a == b) return 0;
1602 if ((get_irn_op(a) != get_irn_op(b)) ||
1603 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1605 /* compare if a's in and b's in are equal */
1606 irn_arity_a = get_irn_arity (a);
1607 if (irn_arity_a != get_irn_arity(b))
1610 /* for block-local cse and op_pin_state_pinned nodes: */
1611 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == op_pin_state_pinned)) {
1612 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1616 /* compare a->in[0..ins] with b->in[0..ins] */
1617 for (i = 0; i < irn_arity_a; i++)
1618 if (get_irn_n(a, i) != get_irn_n(b, i))
1622 * here, we already now that the nodes are identical except their
1625 if (a->op->node_cmp_attr)
1626 return a->op->node_cmp_attr(a, b);
1632 * Calculate a hash value of a node.
1635 ir_node_hash (ir_node *node)
1640 if (node->op == op_Const) {
1641 /* special value for const, as they only differ in their tarval. */
1642 h = ((unsigned) node->attr.con.tv)>>3 ;
1643 h = 9*h + (unsigned)get_irn_mode(node);
1644 } else if (node->op == op_SymConst) {
1645 /* special value for const, as they only differ in their symbol. */
1646 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1647 h = 9*h + (unsigned)get_irn_mode(node);
1650 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1651 h = irn_arity = get_irn_arity(node);
1653 /* consider all in nodes... except the block. */
1654 for (i = 0; i < irn_arity; i++) {
1655 h = 9*h + (unsigned)get_irn_n(node, i);
1659 h = 9*h + (unsigned) get_irn_mode (node);
1661 h = 9*h + (unsigned) get_irn_op (node);
1668 new_identities (void)
1670 return new_pset (vt_cmp, N_IR_NODES);
1674 del_identities (pset *value_table)
1676 del_pset (value_table);
1680 * Return the canonical node computing the same value as n.
1681 * Looks up the node in a hash table.
1683 * For Const nodes this is performed in the constructor, too. Const
1684 * nodes are extremely time critical because of their frequent use in
1685 * constant string arrays.
1687 static INLINE ir_node *
1688 identify (pset *value_table, ir_node *n)
1692 if (!value_table) return n;
1694 /* TODO: use a generic commutative attribute */
1695 if (get_opt_reassociation()) {
1696 if (is_op_commutative(get_irn_op(n))) {
1697 ir_node *l = get_binop_left(n);
1698 ir_node *r = get_binop_right(n);
1700 /* for commutative operators perform a OP b == b OP a */
1702 set_binop_left(n, r);
1703 set_binop_right(n, l);
1708 o = pset_find (value_table, n, ir_node_hash (n));
1715 * During construction we set the op_pin_state_pinned flag in the graph right when the
1716 * optimization is performed. The flag turning on procedure global cse could
1717 * be changed between two allocations. This way we are safe.
1719 static INLINE ir_node *
1720 identify_cons (pset *value_table, ir_node *n) {
1723 n = identify(value_table, n);
1724 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1725 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1730 * Return the canonical node computing the same value as n.
1731 * Looks up the node in a hash table, enters it in the table
1732 * if it isn't there yet.
1735 identify_remember (pset *value_table, ir_node *node)
1739 if (!value_table) return node;
1741 /* lookup or insert in hash table with given hash key. */
1742 o = pset_insert (value_table, node, ir_node_hash (node));
1744 if (o == node) return node;
1750 add_identities (pset *value_table, ir_node *node) {
1751 identify_remember (value_table, node);
1755 * garbage in, garbage out. If a node has a dead input, i.e., the
1756 * Bad node is input to the node, return the Bad node.
1758 static INLINE ir_node *
1759 gigo (ir_node *node)
1762 ir_op* op = get_irn_op(node);
1764 /* remove garbage blocks by looking at control flow that leaves the block
1765 and replacing the control flow by Bad. */
1766 if (get_irn_mode(node) == mode_X) {
1767 ir_node *block = get_nodes_block(node);
1768 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1769 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1770 irn_arity = get_irn_arity(block);
1771 for (i = 0; i < irn_arity; i++) {
1772 if (!is_Bad(get_irn_n(block, i))) break;
1774 if (i == irn_arity) return new_Bad();
1778 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1779 blocks predecessors is dead. */
1780 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1781 irn_arity = get_irn_arity(node);
1782 for (i = -1; i < irn_arity; i++) {
1783 if (is_Bad(get_irn_n(node, i))) {
1789 /* With this code we violate the agreement that local_optimize
1790 only leaves Bads in Block, Phi and Tuple nodes. */
1791 /* If Block has only Bads as predecessors it's garbage. */
1792 /* If Phi has only Bads as predecessors it's garbage. */
1793 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1794 irn_arity = get_irn_arity(node);
1795 for (i = 0; i < irn_arity; i++) {
1796 if (!is_Bad(get_irn_n(node, i))) break;
1798 if (i == irn_arity) node = new_Bad();
1806 * These optimizations deallocate nodes from the obstack.
1807 * It can only be called if it is guaranteed that no other nodes
1808 * reference this one, i.e., right after construction of a node.
1811 optimize_node (ir_node *n)
1815 opcode iro = get_irn_opcode(n);
1817 /* Allways optimize Phi nodes: part of the construction. */
1818 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1820 /* constant expression evaluation / constant folding */
1821 if (get_opt_constant_folding()) {
1822 /* constants can not be evaluated */
1823 if (iro != iro_Const) {
1824 /* try to evaluate */
1825 tv = computed_value (n);
1826 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1828 * we MUST copy the node here temporary, because it's still needed
1829 * for DBG_OPT_ALGSIM0
1831 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
1832 oldn = alloca(node_size);
1834 memcpy(oldn, n, node_size);
1835 CLONE_ARR_A(ir_node *, oldn->in, n->in);
1837 /* ARG, copy the in array, we need it for statistics */
1838 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
1840 /* evaluation was successful -- replace the node. */
1841 obstack_free (current_ir_graph->obst, n);
1842 n = new_Const (get_tarval_mode (tv), tv);
1844 DBG_OPT_ALGSIM0(oldn, n);
1850 /* remove unnecessary nodes */
1851 if (get_opt_constant_folding() ||
1852 (iro == iro_Phi) || /* always optimize these nodes. */
1854 (iro == iro_Proj) ||
1855 (iro == iro_Block) ) /* Flags tested local. */
1856 n = equivalent_node (n);
1858 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1860 /** common subexpression elimination **/
1861 /* Checks whether n is already available. */
1862 /* The block input is used to distinguish different subexpressions. Right
1863 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
1864 subexpressions within a block. */
1866 n = identify_cons (current_ir_graph->value_table, n);
1869 /* We found an existing, better node, so we can deallocate the old node. */
1870 obstack_free (current_ir_graph->obst, oldn);
1875 /* Some more constant expression evaluation that does not allow to
1877 iro = get_irn_opcode(n);
1878 if (get_opt_constant_folding() ||
1879 (iro == iro_Cond) ||
1880 (iro == iro_Proj)) /* Flags tested local. */
1881 n = transform_node (n);
1883 /* Remove nodes with dead (Bad) input.
1884 Run always for transformation induced Bads. */
1887 /* Now we have a legal, useful node. Enter it in hash table for cse */
1888 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1889 n = identify_remember (current_ir_graph->value_table, n);
1897 * These optimizations never deallocate nodes. This can cause dead
1898 * nodes lying on the obstack. Remove these by a dead node elimination,
1899 * i.e., a copying garbage collection.
1902 optimize_in_place_2 (ir_node *n)
1906 opcode iro = get_irn_opcode(n);
1908 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1910 /* if not optimize return n */
1913 /* Here this is possible. Why? */
1918 /* constant expression evaluation / constant folding */
1919 if (get_opt_constant_folding()) {
1920 /* constants can not be evaluated */
1921 if (iro != iro_Const) {
1922 /* try to evaluate */
1923 tv = computed_value (n);
1924 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1925 /* evaluation was successful -- replace the node. */
1926 n = new_Const (get_tarval_mode (tv), tv);
1928 DBG_OPT_ALGSIM0(oldn, n);
1934 /* remove unnecessary nodes */
1935 if (get_opt_constant_folding() ||
1936 (iro == iro_Phi) || /* always optimize these nodes. */
1937 (iro == iro_Id) || /* ... */
1938 (iro == iro_Proj) || /* ... */
1939 (iro == iro_Block) ) /* Flags tested local. */
1940 n = equivalent_node (n);
1942 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1944 /** common subexpression elimination **/
1945 /* Checks whether n is already available. */
1946 /* The block input is used to distinguish different subexpressions. Right
1947 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
1948 subexpressions within a block. */
1949 if (get_opt_cse()) {
1950 n = identify (current_ir_graph->value_table, n);
1953 /* Some more constant expression evaluation. */
1954 iro = get_irn_opcode(n);
1955 if (get_opt_constant_folding() ||
1956 (iro == iro_Cond) ||
1957 (iro == iro_Proj)) /* Flags tested local. */
1958 n = transform_node (n);
1960 /* Remove nodes with dead (Bad) input.
1961 Run always for transformation induced Bads. */
1964 /* Now we can verify the node, as it has no dead inputs any more. */
1967 /* Now we have a legal, useful node. Enter it in hash table for cse.
1968 Blocks should be unique anyways. (Except the successor of start:
1969 is cse with the start block!) */
1970 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1971 n = identify_remember (current_ir_graph->value_table, n);
1977 * Wrapper for external use, set proper status bits after optimization.
1980 optimize_in_place (ir_node *n)
1982 /* Handle graph state */
1983 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1985 if (get_opt_global_cse())
1986 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1987 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1988 set_irg_outs_inconsistent(current_ir_graph);
1990 /* Maybe we could also test whether optimizing the node can
1991 change the control graph. */
1992 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1993 set_irg_dom_inconsistent(current_ir_graph);
1994 return optimize_in_place_2 (n);
1998 * set the default ir op operations
2000 ir_op *firm_set_default_operations(ir_op *op)
2002 op = firm_set_default_computed_value(op);
2003 op = firm_set_default_equivalent_node(op);
2004 op = firm_set_default_transform_node(op);
2005 op = firm_set_default_node_cmp_attr(op);