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);
96 tarval *ta = value_of(a);
97 tarval *tb = value_of(b);
99 if ((ta != tarval_bad) && (tb != tarval_bad)
100 && (get_irn_mode(a) == get_irn_mode(b))
101 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
102 return tarval_sub(ta, tb);
107 static tarval *computed_value_Minus(ir_node *n)
109 ir_node *a = get_Minus_op(n);
110 tarval *ta = value_of(a);
112 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
113 return tarval_neg(ta);
118 static tarval *computed_value_Mul(ir_node *n)
120 ir_node *a = get_Mul_left(n);
121 ir_node *b = get_Mul_right(n);
123 tarval *ta = value_of(a);
124 tarval *tb = value_of(b);
126 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
127 return tarval_mul(ta, tb);
129 /* a*0 = 0 or 0*b = 0:
130 calls computed_value recursive and returns the 0 with proper
134 if ( ( ((v = ta) != tarval_bad)
135 && (v == get_mode_null(get_tarval_mode(v))) )
136 || ( ((v = tb) != tarval_bad)
137 && (v == get_mode_null(get_tarval_mode(v))) )) {
144 static tarval *computed_value_Quot(ir_node *n)
146 ir_node *a = get_Quot_left(n);
147 ir_node *b = get_Quot_right(n);
149 tarval *ta = value_of(a);
150 tarval *tb = value_of(b);
152 /* This was missing in original implementation. Why? */
153 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
154 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
155 return tarval_quo(ta, tb);
160 static tarval *computed_value_Div(ir_node *n)
162 ir_node *a = get_Div_left(n);
163 ir_node *b = get_Div_right(n);
165 tarval *ta = value_of(a);
166 tarval *tb = value_of(b);
168 /* This was missing in original implementation. Why? */
169 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
170 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
171 return tarval_div(ta, tb);
176 static tarval *computed_value_Mod(ir_node *n)
178 ir_node *a = get_Mod_left(n);
179 ir_node *b = get_Mod_right(n);
181 tarval *ta = value_of(a);
182 tarval *tb = value_of(b);
184 /* This was missing in original implementation. Why? */
185 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
186 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
187 return tarval_mod(ta, tb);
192 static tarval *computed_value_Abs(ir_node *n)
194 ir_node *a = get_Abs_op(n);
195 tarval *ta = value_of(a);
197 if (ta != tarval_bad)
198 return tarval_abs(ta);
203 static tarval *computed_value_And(ir_node *n)
205 ir_node *a = get_And_left(n);
206 ir_node *b = get_And_right(n);
208 tarval *ta = value_of(a);
209 tarval *tb = value_of(b);
211 if ((ta != tarval_bad) && (tb != tarval_bad)) {
212 return tarval_and (ta, tb);
216 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_NULL)
217 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
224 static tarval *computed_value_Or(ir_node *n)
226 ir_node *a = get_Or_left(n);
227 ir_node *b = get_Or_right(n);
229 tarval *ta = value_of(a);
230 tarval *tb = value_of(b);
232 if ((ta != tarval_bad) && (tb != tarval_bad)) {
233 return tarval_or (ta, tb);
236 if ( (classify_tarval ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
237 || (classify_tarval ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
244 static tarval *computed_value_Eor(ir_node *n)
246 ir_node *a = get_Eor_left(n);
247 ir_node *b = get_Eor_right(n);
249 tarval *ta = value_of(a);
250 tarval *tb = value_of(b);
252 if ((ta != tarval_bad) && (tb != tarval_bad)) {
253 return tarval_eor (ta, tb);
258 static tarval *computed_value_Not(ir_node *n)
260 ir_node *a = get_Not_op(n);
261 tarval *ta = value_of(a);
263 if (ta != tarval_bad)
264 return tarval_not(ta);
269 static tarval *computed_value_Shl(ir_node *n)
271 ir_node *a = get_Shl_left(n);
272 ir_node *b = get_Shl_right(n);
274 tarval *ta = value_of(a);
275 tarval *tb = value_of(b);
277 if ((ta != tarval_bad) && (tb != tarval_bad)) {
278 return tarval_shl (ta, tb);
283 static tarval *computed_value_Shr(ir_node *n)
285 ir_node *a = get_Shr_left(n);
286 ir_node *b = get_Shr_right(n);
288 tarval *ta = value_of(a);
289 tarval *tb = value_of(b);
291 if ((ta != tarval_bad) && (tb != tarval_bad)) {
292 return tarval_shr (ta, tb);
297 static tarval *computed_value_Shrs(ir_node *n)
299 ir_node *a = get_Shrs_left(n);
300 ir_node *b = get_Shrs_right(n);
302 tarval *ta = value_of(a);
303 tarval *tb = value_of(b);
305 if ((ta != tarval_bad) && (tb != tarval_bad)) {
306 return tarval_shrs (ta, tb);
311 static tarval *computed_value_Rot(ir_node *n)
313 ir_node *a = get_Rot_left(n);
314 ir_node *b = get_Rot_right(n);
316 tarval *ta = value_of(a);
317 tarval *tb = value_of(b);
319 if ((ta != tarval_bad) && (tb != tarval_bad)) {
320 return tarval_rot (ta, tb);
325 static tarval *computed_value_Conv(ir_node *n)
327 ir_node *a = get_Conv_op(n);
328 tarval *ta = value_of(a);
330 if (ta != tarval_bad)
331 return tarval_convert_to(ta, get_irn_mode(n));
336 static tarval *computed_value_Proj(ir_node *n)
338 ir_node *a = get_Proj_pred(n), *b;
341 /* Optimize Cmp nodes.
342 This performs a first step of unreachable code elimination.
343 Proj can not be computed, but folding a Cmp above the Proj here is
344 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
346 There are several case where we can evaluate a Cmp node:
347 1. The nodes compared are both the same. If we compare for
348 equal, greater equal, ... this will return true, else it
349 will return false. This step relies on cse.
350 2. The predecessors of Cmp are target values. We can evaluate
352 3. The predecessors are Allocs or void* constants. Allocs never
353 return NULL, they raise an exception. Therefore we can predict
355 switch (get_irn_opcode(a)) {
357 aa = get_Cmp_left(a);
358 ab = get_Cmp_right(a);
360 if (aa == ab) { /* 1.: */
361 /* This is a trick with the bits used for encoding the Cmp
362 Proj numbers, the following statement is not the same:
363 return new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
364 return new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
366 tarval *taa = computed_value (aa);
367 tarval *tab = computed_value (ab);
369 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
370 /* strange checks... */
371 pnc_number flags = tarval_cmp (taa, tab);
372 if (flags != False) {
373 return new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
375 } else { /* check for 3.: */
376 ir_node *aaa = skip_Id(skip_Proj(aa));
377 ir_node *aba = skip_Id(skip_Proj(ab));
379 if ( ( (/* aa is ProjP and aaa is Alloc */
380 (get_irn_op(aa) == op_Proj)
381 && (mode_is_reference(get_irn_mode(aa)))
382 && (get_irn_op(aaa) == op_Alloc))
383 && ( (/* ab is constant void */
384 (get_irn_op(ab) == op_Const)
385 && (mode_is_reference(get_irn_mode(ab)))
386 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
387 || (/* ab is other Alloc */
388 (get_irn_op(ab) == op_Proj)
389 && (mode_is_reference(get_irn_mode(ab)))
390 && (get_irn_op(aba) == op_Alloc)
392 || (/* aa is void and aba is Alloc */
393 (get_irn_op(aa) == op_Const)
394 && (mode_is_reference(get_irn_mode(aa)))
395 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
396 && (get_irn_op(ab) == op_Proj)
397 && (mode_is_reference(get_irn_mode(ab)))
398 && (get_irn_op(aba) == op_Alloc)))
400 return new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
407 tarval *tb = value_of(b = get_DivMod_right(a));
408 tarval *ta = value_of(a = get_DivMod_left(a));
410 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
411 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
413 if (get_Proj_proj(n)== pn_DivMod_res_div)
414 return tarval_div(ta, tb);
415 else if (get_Proj_proj(n)== pn_DivMod_res_mod)
416 return tarval_mod(ta, tb);
423 tarval *tb = value_of(b = get_Div_right(a));
424 tarval *ta = value_of(a = get_Div_left(a));
426 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
427 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
429 if (get_Proj_proj(n)== pn_Div_res)
430 return tarval_div(ta, tb);
437 tarval *tb = value_of(b = get_Mod_right(a));
438 tarval *ta = value_of(a = get_Mod_left(a));
440 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
441 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
443 if (get_Proj_proj(n)== pn_Mod_res)
444 return tarval_mod(ta, tb);
456 * If the parameter n can be computed, return its value, else tarval_bad.
457 * Performs constant folding.
459 * @param n The node this should be evaluated
461 tarval *computed_value(ir_node *n)
463 if (n->op->computed_value)
464 return n->op->computed_value(n);
469 * set the default computed_value evaluator
471 static ir_op *firm_set_default_computed_value(ir_op *op)
475 op->computed_value = computed_value_##a; \
500 op->computed_value = NULL;
508 /* returns 1 if the a and b are pointers to different locations. */
510 different_identity (ir_node *a, ir_node *b)
512 assert (mode_is_reference(get_irn_mode (a))
513 && mode_is_reference(get_irn_mode (b)));
515 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
516 ir_node *a1 = get_Proj_pred (a);
517 ir_node *b1 = get_Proj_pred (b);
518 if (a1 != b1 && get_irn_op (a1) == op_Alloc
519 && get_irn_op (b1) == op_Alloc)
526 static ir_node *equivalent_node_Block(ir_node *n)
530 /* The Block constructor does not call optimize, but mature_immBlock
531 calls the optimization. */
532 assert(get_Block_matured(n));
534 /* Straightening: a single entry Block following a single exit Block
535 can be merged, if it is not the Start block. */
536 /* !!! Beware, all Phi-nodes of n must have been optimized away.
537 This should be true, as the block is matured before optimize is called.
538 But what about Phi-cycles with the Phi0/Id that could not be resolved?
539 Remaining Phi nodes are just Ids. */
540 if ((get_Block_n_cfgpreds(n) == 1) &&
541 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
542 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
543 if (predblock == oldn) {
544 /* Jmp jumps into the block it is in -- deal self cycle. */
545 n = new_Bad(); DBG_OPT_DEAD;
546 } else if (get_opt_control_flow_straightening()) {
547 n = predblock; DBG_OPT_STG;
550 else if ((get_Block_n_cfgpreds(n) == 1) &&
551 (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
552 ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
553 if (predblock == oldn) {
554 /* Jmp jumps into the block it is in -- deal self cycle. */
555 n = new_Bad(); DBG_OPT_DEAD;
558 else if ((get_Block_n_cfgpreds(n) == 2) &&
559 (get_opt_control_flow_weak_simplification())) {
560 /* Test whether Cond jumps twice to this block
561 @@@ we could do this also with two loops finding two preds from several ones. */
562 ir_node *a = get_Block_cfgpred(n, 0);
563 ir_node *b = get_Block_cfgpred(n, 1);
565 if ((get_irn_op(a) == op_Proj) &&
566 (get_irn_op(b) == op_Proj) &&
567 (get_Proj_pred(a) == get_Proj_pred(b)) &&
568 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
569 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
570 /* Also a single entry Block following a single exit Block. Phis have
571 twice the same operand and will be optimized away. */
572 n = get_nodes_block(a); DBG_OPT_IFSIM;
574 } else if (get_opt_unreachable_code() &&
575 (n != current_ir_graph->start_block) &&
576 (n != current_ir_graph->end_block) ) {
578 /* If all inputs are dead, this block is dead too, except if it is
579 the start or end block. This is a step of unreachable code
581 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
582 if (!is_Bad(get_Block_cfgpred(n, i))) break;
584 if (i == get_Block_n_cfgpreds(n))
592 * Returns a equivalent node for a Jmp, a Bad :-)
593 * Of course this only happens if the Block of the Jmp is Bad.
595 static ir_node *equivalent_node_Jmp(ir_node *n)
597 /* GL: Why not same for op_Raise?? */
598 /* unreachable code elimination */
599 if (is_Bad(get_nodes_block(n)))
605 static ir_node *equivalent_node_Cond(ir_node *n)
607 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
608 See cases for iro_Cond and iro_Proj in transform_node. */
613 * Use algebraic simplification a v a = a.
615 static ir_node *equivalent_node_Or(ir_node *n)
619 ir_node *a = get_Or_left(n);
620 ir_node *b = get_Or_right(n);
624 n = a; DBG_OPT_ALGSIM1;
631 * optimize operations that are commutative and have neutral 0,
632 * so a op 0 = 0 op a = a.
634 static ir_node *equivalent_node_neutral_zero(ir_node *n)
638 ir_node *a = get_binop_left(n);
639 ir_node *b = get_binop_right(n);
644 /* After running compute_node there is only one constant predecessor.
645 Find this predecessors value and remember the other node: */
646 if ((tv = computed_value(a)) != tarval_bad) {
648 } else if ((tv = computed_value(b)) != tarval_bad) {
653 /* If this predecessors constant value is zero, the operation is
654 unnecessary. Remove it: */
655 if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
656 n = on; DBG_OPT_ALGSIM1;
662 #define equivalent_node_Add equivalent_node_neutral_zero
663 #define equivalent_node_Eor equivalent_node_neutral_zero
666 * optimize operations that are not commutative but have neutral 0 on left,
669 static ir_node *equivalent_node_left_zero(ir_node *n)
673 ir_node *a = get_binop_left(n);
674 ir_node *b = get_binop_right(n);
676 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_NULL) {
677 n = a; DBG_OPT_ALGSIM1;
683 #define equivalent_node_Sub equivalent_node_left_zero
684 #define equivalent_node_Shl equivalent_node_left_zero
685 #define equivalent_node_Shr equivalent_node_left_zero
686 #define equivalent_node_Shrs equivalent_node_left_zero
687 #define equivalent_node_Rot equivalent_node_left_zero
690 * Er, a "symmetic unop", ie op(op(n)) = n.
692 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
696 /* optimize symmetric unop */
697 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
698 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
704 #define equivalent_node_Not equivalent_node_symmetric_unop
706 /* --x == x */ /* ??? Is this possible or can --x raise an
707 out of bounds exception if min =! max? */
708 #define equivalent_node_Minus equivalent_node_symmetric_unop
711 * Optimize a * 1 = 1 * a = a.
713 static ir_node *equivalent_node_Mul(ir_node *n)
717 ir_node *a = get_Mul_left(n);
718 ir_node *b = get_Mul_right(n);
720 /* Mul is commutative and has again an other neutral element. */
721 if (classify_tarval (computed_value (a)) == TV_CLASSIFY_ONE) {
722 n = b; DBG_OPT_ALGSIM1;
723 } else if (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE) {
724 n = a; DBG_OPT_ALGSIM1;
730 * Optimize a / 1 = a.
732 static ir_node *equivalent_node_Div(ir_node *n)
734 ir_node *a = get_Div_left(n);
735 ir_node *b = get_Div_right(n);
737 /* Div is not commutative. */
738 if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
739 /* Turn Div into a tuple (mem, bad, a) */
740 ir_node *mem = get_Div_mem(n);
741 turn_into_tuple(n, 3);
742 set_Tuple_pred(n, pn_Div_M, mem);
743 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
744 set_Tuple_pred(n, pn_Div_res, a);
750 * Optimize a & 0b1...1 = 0b1...1 & a = a & a = a.
752 static ir_node *equivalent_node_And(ir_node *n)
756 ir_node *a = get_And_left(n);
757 ir_node *b = get_And_right(n);
760 n = a; /* And has it's own neutral element */
761 } else if (classify_tarval(computed_value(a)) == TV_CLASSIFY_ALL_ONE) {
763 } else if (classify_tarval(computed_value(b)) == TV_CLASSIFY_ALL_ONE) {
766 if (n != oldn) DBG_OPT_ALGSIM1;
771 * Try to remove useless conv's:
773 static ir_node *equivalent_node_Conv(ir_node *n)
776 ir_node *a = get_Conv_op(n);
779 ir_mode *n_mode = get_irn_mode(n);
780 ir_mode *a_mode = get_irn_mode(a);
782 if (n_mode == a_mode) { /* No Conv necessary */
783 n = a; DBG_OPT_ALGSIM3;
784 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
788 n_mode = get_irn_mode(n);
789 b_mode = get_irn_mode(b);
791 if (n_mode == b_mode) {
792 if (n_mode == mode_b) {
793 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM1;
795 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
796 if (smaller_mode(b_mode, a_mode)){
797 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ DBG_OPT_ALGSIM1;
805 static ir_node *equivalent_node_Phi(ir_node *n)
807 /* Several optimizations:
808 - no Phi in start block.
809 - remove Id operators that are inputs to Phi
810 - fold Phi-nodes, iff they have only one predecessor except
816 ir_node *block = NULL; /* to shutup gcc */
817 ir_node *first_val = NULL; /* to shutup gcc */
818 ir_node *scnd_val = NULL; /* to shutup gcc */
820 if (!get_opt_normalize()) return n;
822 n_preds = get_Phi_n_preds(n);
824 block = get_nodes_block(n);
825 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
826 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
827 if ((is_Bad(block)) || /* Control dead */
828 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
829 return new_Bad(); /* in the Start Block. */
831 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
834 /* first we test for a special case: */
835 /* Confirm is a special node fixing additional information for a
836 value that is known at a certain point. This is useful for
837 dataflow analysis. */
839 ir_node *a = get_Phi_pred(n, 0);
840 ir_node *b = get_Phi_pred(n, 1);
841 if ( (get_irn_op(a) == op_Confirm)
842 && (get_irn_op(b) == op_Confirm)
843 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
844 && (get_irn_n(a, 1) == get_irn_n (b, 1))
845 && (a->data.num == (~b->data.num & irpn_True) )) {
846 return get_irn_n(a, 0);
851 /* If the Block has a Bad pred, we also have one. */
852 for (i = 0; i < n_preds; ++i)
853 if (is_Bad (get_Block_cfgpred(block, i)))
854 set_Phi_pred(n, i, new_Bad());
856 /* Find first non-self-referencing input */
857 for (i = 0; i < n_preds; ++i) {
858 first_val = get_Phi_pred(n, i);
859 if ( (first_val != n) /* not self pointer */
861 && (get_irn_op(first_val) != op_Bad)
863 ) { /* value not dead */
864 break; /* then found first value. */
868 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
869 if (i >= n_preds) { return new_Bad(); }
873 /* follow_Id () for rest of inputs, determine if any of these
874 are non-self-referencing */
875 while (++i < n_preds) {
876 scnd_val = get_Phi_pred(n, i);
878 && (scnd_val != first_val)
880 && (get_irn_op(scnd_val) != op_Bad)
887 /* Fold, if no multiple distinct non-self-referencing inputs */
889 n = first_val; DBG_OPT_PHI;
891 /* skip the remaining Ids (done in get_Phi_pred). */
892 /* superfluous, since we walk all to propagate Block's Bads.
893 while (++i < n_preds) get_Phi_pred(n, i); */
899 * Optimize Loads after Store.
901 * @todo FAILS for volatile entities
903 static ir_node *equivalent_node_Load(ir_node *n)
907 if (!get_opt_redundant_LoadStore()) return n;
909 /* remove unnecessary Load. */
910 ir_node *a = skip_Proj(get_Load_mem(n));
911 ir_node *b = get_Load_ptr(n);
914 /* TODO: check for volatile */
915 if (get_irn_op(a) == op_Store && get_Store_ptr(a) == b) {
916 /* We load immediately after a store -- a read after write. */
917 ir_node *mem = get_Load_mem(n);
919 c = get_Store_value(a);
920 turn_into_tuple(n, 3);
921 set_Tuple_pred(n, pn_Load_M, mem);
922 set_Tuple_pred(n, pn_Load_X_except, new_Bad());
923 set_Tuple_pred(n, pn_Load_res, c); DBG_OPT_RAW;
925 else if (get_irn_op(a) == op_Load && get_Load_ptr(a) == b) {
926 /* We load immediately after a Load -- a read after read. */
934 * Optimize store after store and load after store.
936 * @todo FAILS for volatile entities
938 static ir_node *equivalent_node_Store(ir_node *n)
942 if (!get_opt_redundant_LoadStore()) return n;
944 /* remove unnecessary store. */
945 ir_node *a = skip_Proj(get_Store_mem(n));
946 ir_node *b = get_Store_ptr(n);
947 ir_node *c = skip_Proj(get_Store_value(n));
949 if (get_irn_op(a) == op_Store
950 && get_Store_ptr(a) == b
951 && skip_Proj(get_Store_value(a)) == c) {
952 /* We have twice exactly the same store -- a write after write. */
954 } else if (get_irn_op(c) == op_Load
955 && (a == c || skip_Proj(get_Load_mem(c)) == a)
956 && get_Load_ptr(c) == b ) {
957 /* We just loaded the value from the same memory, i.e., the store
958 doesn't change the memory -- a write after read. */
959 a = get_Store_mem(n);
960 turn_into_tuple(n, 2);
961 set_Tuple_pred(n, pn_Store_M, a);
962 set_Tuple_pred(n, pn_Store_X_except, new_Bad()); DBG_OPT_WAR;
968 * optimize Proj(Tuple) and gigo for ProjX in Bad block
970 static ir_node *equivalent_node_Proj(ir_node *n)
974 ir_node *a = get_Proj_pred(n);
976 if ( get_irn_op(a) == op_Tuple) {
977 /* Remove the Tuple/Proj combination. */
978 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
979 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
981 assert(0); /* This should not happen! */
984 } else if (get_irn_mode(n) == mode_X &&
985 is_Bad(get_nodes_block(n))) {
986 /* Remove dead control flow -- early gigo. */
995 static ir_node *equivalent_node_Id(ir_node *n)
999 n = follow_Id(n); DBG_OPT_ID;
1004 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1005 * perform no actual computation, as, e.g., the Id nodes. It does not create
1006 * new nodes. It is therefore safe to free n if the node returned is not n.
1007 * If a node returns a Tuple we can not just skip it. If the size of the
1008 * in array fits, we transform n into a tuple (e.g., Div).
1011 equivalent_node(ir_node *n)
1013 if (n->op->equivalent_node)
1014 return n->op->equivalent_node(n);
1019 * set the default equivalent node operation
1021 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1025 op->equivalent_node = equivalent_node_##a; \
1047 // CASE(Load); /* dangerous */
1048 // CASE(Store); /* dangerous, see todo */
1052 op->equivalent_node = NULL;
1060 * Do node specific optimizations of nodes predecessors.
1063 optimize_preds(ir_node *n) {
1064 ir_node *a = NULL, *b = NULL;
1066 /* get the operands we will work on for simple cases. */
1068 a = get_binop_left(n);
1069 b = get_binop_right(n);
1070 } else if (is_unop(n)) {
1074 switch (get_irn_opcode(n)) {
1077 /* We don't want Cast as input to Cmp. */
1078 if (get_irn_op(a) == op_Cast) {
1082 if (get_irn_op(b) == op_Cast) {
1084 set_Cmp_right(n, b);
1092 static ir_node *transform_node_Div(ir_node *n)
1094 tarval *tv = computed_value(n);
1096 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1098 if (tv != tarval_bad) {
1099 /* Turn Div into a tuple (mem, bad, value) */
1100 ir_node *mem = get_Div_mem(n);
1102 turn_into_tuple(n, 3);
1103 set_Tuple_pred(n, pn_Div_M, mem);
1104 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1105 set_Tuple_pred(n, pn_Div_res, new_Const(get_tarval_mode(tv), tv));
1110 static ir_node *transform_node_Mod(ir_node *n)
1112 tarval *tv = computed_value(n);
1114 /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1116 if (tv != tarval_bad) {
1117 /* Turn Mod into a tuple (mem, bad, value) */
1118 ir_node *mem = get_Mod_mem(n);
1119 turn_into_tuple(n, 3);
1120 set_Tuple_pred(n, pn_Mod_M, mem);
1121 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1122 set_Tuple_pred(n, pn_Mod_res, new_Const(get_tarval_mode(tv), tv));
1127 static ir_node *transform_node_DivMod(ir_node *n)
1131 ir_node *a = get_DivMod_left(n);
1132 ir_node *b = get_DivMod_right(n);
1133 ir_mode *mode = get_irn_mode(a);
1134 tarval *ta = value_of(a);
1135 tarval *tb = value_of(b);
1137 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1140 /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1142 if (tb != tarval_bad) {
1143 if (tb == get_mode_one(get_tarval_mode(tb))) {
1144 b = new_Const (mode, get_mode_null(mode));
1146 } else if (ta != tarval_bad) {
1147 tarval *resa, *resb;
1148 resa = tarval_div (ta, tb);
1149 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1150 Jmp for X result!? */
1151 resb = tarval_mod (ta, tb);
1152 if (resb == tarval_bad) return n; /* Causes exception! */
1153 a = new_Const (mode, resa);
1154 b = new_Const (mode, resb);
1157 } else if (ta == get_mode_null(mode)) {
1161 if (evaluated) { /* replace by tuple */
1162 ir_node *mem = get_DivMod_mem(n);
1163 turn_into_tuple(n, 4);
1164 set_Tuple_pred(n, pn_DivMod_M, mem);
1165 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1166 set_Tuple_pred(n, pn_DivMod_res_div, a);
1167 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1168 assert(get_nodes_block(n));
1174 static ir_node *transform_node_Cond(ir_node *n)
1176 /* Replace the Cond by a Jmp if it branches on a constant
1179 ir_node *a = get_Cond_selector(n);
1180 tarval *ta = value_of(a);
1182 if ((ta != tarval_bad) &&
1183 (get_irn_mode(a) == mode_b) &&
1184 (get_opt_unreachable_code())) {
1185 /* It's a boolean Cond, branching on a boolean constant.
1186 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1187 jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1188 turn_into_tuple(n, 2);
1189 if (ta == tarval_b_true) {
1190 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1191 set_Tuple_pred(n, pn_Cond_true, jmp);
1193 set_Tuple_pred(n, pn_Cond_false, jmp);
1194 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1196 /* We might generate an endless loop, so keep it alive. */
1197 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1198 } else if ((ta != tarval_bad) &&
1199 (get_irn_mode(a) == mode_Iu) &&
1200 (get_Cond_kind(n) == dense) &&
1201 (get_opt_unreachable_code())) {
1202 /* I don't want to allow Tuples smaller than the biggest Proj.
1203 Also this tuple might get really big...
1204 I generate the Jmp here, and remember it in link. Link is used
1205 when optimizing Proj. */
1206 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1207 /* We might generate an endless loop, so keep it alive. */
1208 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1209 } else if ((get_irn_op(a) == op_Eor)
1210 && (get_irn_mode(a) == mode_b)
1211 && (classify_tarval(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1212 /* The Eor is a negate. Generate a new Cond without the negate,
1213 simulate the negate by exchanging the results. */
1214 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1216 } else if ((get_irn_op(a) == op_Not)
1217 && (get_irn_mode(a) == mode_b)) {
1218 /* A Not before the Cond. Generate a new Cond without the Not,
1219 simulate the Not by exchanging the results. */
1220 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1226 static ir_node *transform_node_Eor(ir_node *n)
1228 ir_node *a = get_Eor_left(n);
1229 ir_node *b = get_Eor_right(n);
1231 if ((get_irn_mode(n) == mode_b)
1232 && (get_irn_op(a) == op_Proj)
1233 && (get_irn_mode(a) == mode_b)
1234 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE)
1235 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1236 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1237 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1238 mode_b, get_negated_pnc(get_Proj_proj(a)));
1239 else if ((get_irn_mode(n) == mode_b)
1240 && (classify_tarval (computed_value (b)) == TV_CLASSIFY_ONE))
1241 /* The Eor is a Not. Replace it by a Not. */
1242 /* ????!!!Extend to bitfield 1111111. */
1243 n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1249 * Transfor a boolean Not.
1251 static ir_node *transform_node_Not(ir_node *n)
1253 ir_node *a = get_Not_op(n);
1255 if ( (get_irn_mode(n) == mode_b)
1256 && (get_irn_op(a) == op_Proj)
1257 && (get_irn_mode(a) == mode_b)
1258 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1259 /* We negate a Cmp. The Cmp has the negated result anyways! */
1260 n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1261 mode_b, get_negated_pnc(get_Proj_proj(a)));
1267 * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1268 * done here instead of equivalent node because in creates new
1271 static ir_node *transform_node_Proj(ir_node *proj)
1273 ir_node *n = get_Proj_pred(proj);
1277 switch (get_irn_opcode(n)) {
1279 b = get_Div_right(n);
1280 tb = computed_value(b);
1282 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1283 ir_node *div, *proj;
1284 ir_node *a = get_Div_left(n);
1285 ir_node *mem = get_Div_mem(n);
1286 int rem = get_optimize();
1290 div = new_rd_Div(get_irn_dbg_info(n), current_ir_graph,
1291 get_nodes_block(n), get_irg_initial_mem(current_ir_graph), a, b);
1293 proj = new_r_Proj(current_ir_graph, get_nodes_block(n), div, get_irn_mode(a), pn_Div_res);
1297 turn_into_tuple(n, 3);
1298 set_Tuple_pred(n, pn_Mod_M, mem);
1299 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1300 set_Tuple_pred(n, pn_Mod_res, proj);
1304 b = get_Mod_right(n);
1305 tb = computed_value(b);
1307 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1308 ir_node *mod, *proj;
1309 ir_node *a = get_Mod_left(n);
1310 ir_node *mem = get_Mod_mem(n);
1311 int rem = get_optimize();
1315 mod = new_rd_Mod(get_irn_dbg_info(n), current_ir_graph,
1316 get_nodes_block(n), get_irg_initial_mem(current_ir_graph), a, b);
1318 proj = new_r_Proj(current_ir_graph, get_nodes_block(n), mod, get_irn_mode(a), pn_Mod_res);
1322 turn_into_tuple(n, 3);
1323 set_Tuple_pred(n, pn_Mod_M, mem);
1324 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1325 set_Tuple_pred(n, pn_Mod_res, proj);
1329 b = get_DivMod_right(n);
1330 tb = computed_value(b);
1332 if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1333 ir_node *div_mod, *proj_div, *proj_mod;
1334 ir_node *a = get_Mod_left(n);
1335 ir_node *mem = get_Mod_mem(n);
1336 int rem = get_optimize();
1340 div_mod = new_rd_DivMod(get_irn_dbg_info(n), current_ir_graph,
1341 get_nodes_block(n), get_irg_initial_mem(current_ir_graph), a, b);
1343 proj_div = new_r_Proj(current_ir_graph, get_nodes_block(n), div_mod, get_irn_mode(a), pn_DivMod_res_div);
1344 proj_mod = new_r_Proj(current_ir_graph, get_nodes_block(n), div_mod, get_irn_mode(a), pn_DivMod_res_mod);
1348 turn_into_tuple(n, 4);
1349 set_Tuple_pred(n, pn_DivMod_M, mem);
1350 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad());
1351 set_Tuple_pred(n, pn_DivMod_res_div, proj_div);
1352 set_Tuple_pred(n, pn_DivMod_res_mod, proj_mod);
1357 if (get_opt_unreachable_code()) {
1358 b = get_Cond_selector(n);
1359 tb = computed_value(b);
1361 if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1362 /* we have a constant switch */
1363 long num = get_Proj_proj(proj);
1365 if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1366 if (get_tarval_long(tb) == num) {
1367 /* Do NOT create a jump here, or we will have 2 control flow ops
1368 * in a block. This case is optimized away in optimize_cf(). */
1379 * Ugly case: due to the walk order it may happen, that a proj is visited
1380 * before the preceding Load/Store is optimized (happens in cycles).
1381 * This will lead to a Tuple that will be alive after local_optimize(), which
1382 * is bad. So, we do it here again.
1388 n = equivalent_node(n);
1390 set_Proj_pred(proj, n);
1396 /* should not happen, but if it doest will optimize */
1404 /* we have added a Tuple, optimize it for the current Proj away */
1405 return equivalent_node_Proj(proj);
1409 * Transform a Store before a Store to the same address...
1410 * Both nodes must be in the same block.
1412 * @todo Check for volatile! Moreover, what if the first store
1413 * has a exception handler while the other has not?
1415 static ir_node *transform_node_Store(ir_node *store)
1417 ir_node *pred = skip_Proj(get_Store_mem(store));
1418 ir_node *ptr = get_Store_ptr(store);
1420 if (!get_opt_redundant_LoadStore()) return store;
1422 if (get_irn_op(pred) == op_Store &&
1423 get_Store_ptr(pred) == ptr &&
1424 get_nodes_block(pred) == get_nodes_block(store)) {
1425 /* the Store n is useless, as it is overwritten by the store store */
1426 ir_node *mem = get_Store_mem(pred);
1428 turn_into_tuple(pred, 2);
1429 set_Tuple_pred(pred, pn_Store_M, mem);
1430 set_Tuple_pred(pred, pn_Store_X_except, new_Bad());
1436 * returns the operands of a commutative bin-op, if one operand is
1437 * a const, it is returned as the second one.
1439 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1441 ir_node *op_a = get_binop_left(binop);
1442 ir_node *op_b = get_binop_right(binop);
1444 assert(is_op_commutative(get_irn_op(binop)));
1446 if (get_irn_op(op_a) == op_Const) {
1457 * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1458 * Such pattern may arise in bitfield stores.
1460 * value c4 value c4 & c2
1461 * AND c3 AND c1 | c3
1466 static ir_node *transform_node_Or(ir_node *or)
1470 ir_node *and_l, *c3;
1471 ir_node *value, *c4;
1472 ir_node *new_and, *new_const, *block;
1473 ir_mode *mode = get_irn_mode(or);
1475 tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1477 get_comm_Binop_Ops(or, &and, &c1);
1478 if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1481 get_comm_Binop_Ops(and, &or_l, &c2);
1482 if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1485 get_comm_Binop_Ops(or_l, &and_l, &c3);
1486 if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1489 get_comm_Binop_Ops(and_l, &value, &c4);
1490 if (get_irn_op(c4) != op_Const)
1493 /* ok, found the pattern, check for conditions */
1494 assert(mode == get_irn_mode(and));
1495 assert(mode == get_irn_mode(or_l));
1496 assert(mode == get_irn_mode(and_l));
1498 tv1 = get_Const_tarval(c1);
1499 tv2 = get_Const_tarval(c2);
1500 tv3 = get_Const_tarval(c3);
1501 tv4 = get_Const_tarval(c4);
1503 tv = tarval_or(tv4, tv2);
1504 if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1505 /* have at least one 0 at the same bit position */
1509 n_tv4 = tarval_not(tv4);
1510 if (tv3 != tarval_and(tv3, n_tv4)) {
1511 /* bit in the or_mask is outside the and_mask */
1515 n_tv2 = tarval_not(tv2);
1516 if (tv1 != tarval_and(tv1, n_tv2)) {
1517 /* bit in the or_mask is outside the and_mask */
1521 /* ok, all conditions met */
1522 block = get_nodes_block(or);
1524 new_and = new_r_And(current_ir_graph, block,
1525 value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1527 new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1529 set_Or_left(or, new_and);
1530 set_Or_right(or, new_const);
1532 /* check for more */
1533 return transform_node_Or(or);
1537 * Tries several [inplace] [optimizing] transformations and returns an
1538 * equivalent node. The difference to equivalent_node() is that these
1539 * transformations _do_ generate new nodes, and thus the old node must
1540 * not be freed even if the equivalent node isn't the old one.
1542 static ir_node *transform_node(ir_node *n)
1544 if (n->op->transform_node)
1545 n = n->op->transform_node(n);
1550 * set the default transform node operation
1552 static ir_op *firm_set_default_transform_node(ir_op *op)
1556 op->transform_node = transform_node_##a; \
1567 CASE(Store); /* dangerous, see todo */
1570 op->transform_node = NULL;
1578 /* **************** Common Subexpression Elimination **************** */
1580 /** The size of the hash table used, should estimate the number of nodes
1582 #define N_IR_NODES 512
1584 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1586 return (get_Const_tarval(a) != get_Const_tarval(b))
1587 || (get_Const_type(a) != get_Const_type(b));
1590 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1592 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1595 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1597 return get_Filter_proj(a) != get_Filter_proj(b);
1600 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1602 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1603 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1606 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1608 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1611 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1613 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1614 || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p);
1617 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1619 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1622 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1624 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1627 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1629 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1630 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1631 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1632 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1633 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1636 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1638 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1641 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1643 return get_Cast_type(a) != get_Cast_type(b);
1647 * set the default node attribute compare operation
1649 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1653 op->node_cmp_attr = node_cmp_attr_##a; \
1669 op->node_cmp_attr = NULL;
1677 * Compare function for two nodes in the hash table. Gets two
1678 * nodes as parameters. Returns 0 if the nodes are a cse.
1681 vt_cmp (const void *elt, const void *key)
1689 if (a == b) return 0;
1691 if ((get_irn_op(a) != get_irn_op(b)) ||
1692 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1694 /* compare if a's in and b's in are equal */
1695 irn_arity_a = get_irn_arity (a);
1696 if (irn_arity_a != get_irn_arity(b))
1699 /* for block-local cse and op_pin_state_pinned nodes: */
1700 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == op_pin_state_pinned)) {
1701 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1705 /* compare a->in[0..ins] with b->in[0..ins] */
1706 for (i = 0; i < irn_arity_a; i++)
1707 if (get_irn_n(a, i) != get_irn_n(b, i))
1711 * here, we already now that the nodes are identical except their
1714 if (a->op->node_cmp_attr)
1715 return a->op->node_cmp_attr(a, b);
1721 * Calculate a hash value of a node.
1724 ir_node_hash (ir_node *node)
1729 if (node->op == op_Const) {
1730 /* special value for const, as they only differ in their tarval. */
1731 h = ((unsigned) node->attr.con.tv)>>3 ;
1732 h = 9*h + (unsigned)get_irn_mode(node);
1733 } else if (node->op == op_SymConst) {
1734 /* special value for const, as they only differ in their symbol. */
1735 h = ((unsigned) node->attr.i.sym.type_p)>>3 ;
1736 h = 9*h + (unsigned)get_irn_mode(node);
1739 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1740 h = irn_arity = get_irn_arity(node);
1742 /* consider all in nodes... except the block. */
1743 for (i = 0; i < irn_arity; i++) {
1744 h = 9*h + (unsigned)get_irn_n(node, i);
1748 h = 9*h + (unsigned) get_irn_mode (node);
1750 h = 9*h + (unsigned) get_irn_op (node);
1757 new_identities (void)
1759 return new_pset (vt_cmp, N_IR_NODES);
1763 del_identities (pset *value_table)
1765 del_pset (value_table);
1769 * Return the canonical node computing the same value as n.
1770 * Looks up the node in a hash table.
1772 * For Const nodes this is performed in the constructor, too. Const
1773 * nodes are extremely time critical because of their frequent use in
1774 * constant string arrays.
1776 static INLINE ir_node *
1777 identify (pset *value_table, ir_node *n)
1781 if (!value_table) return n;
1783 /* TODO: use a generic commutative attribute */
1784 if (get_opt_reassociation()) {
1785 if (is_op_commutative(get_irn_op(n))) {
1786 /* for commutative operators perform a OP b == b OP a */
1787 if (get_binop_left(n) > get_binop_right(n)) {
1788 ir_node *h = get_binop_left(n);
1789 set_binop_left(n, get_binop_right(n));
1790 set_binop_right(n, h);
1795 o = pset_find (value_table, n, ir_node_hash (n));
1802 * During construction we set the op_pin_state_pinned flag in the graph right when the
1803 * optimization is performed. The flag turning on procedure global cse could
1804 * be changed between two allocations. This way we are safe.
1806 static INLINE ir_node *
1807 identify_cons (pset *value_table, ir_node *n) {
1809 n = identify(value_table, n);
1810 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1811 set_irg_pinned(current_ir_graph, op_pin_state_floats);
1816 * Return the canonical node computing the same value as n.
1817 * Looks up the node in a hash table, enters it in the table
1818 * if it isn't there yet.
1821 identify_remember (pset *value_table, ir_node *node)
1825 if (!value_table) return node;
1827 /* lookup or insert in hash table with given hash key. */
1828 o = pset_insert (value_table, node, ir_node_hash (node));
1830 if (o == node) return node;
1836 add_identities (pset *value_table, ir_node *node) {
1837 identify_remember (value_table, node);
1841 * garbage in, garbage out. If a node has a dead input, i.e., the
1842 * Bad node is input to the node, return the Bad node.
1844 static INLINE ir_node *
1845 gigo (ir_node *node)
1848 ir_op* op = get_irn_op(node);
1850 /* remove garbage blocks by looking at control flow that leaves the block
1851 and replacing the control flow by Bad. */
1852 if (get_irn_mode(node) == mode_X) {
1853 ir_node *block = get_nodes_block(node);
1854 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1855 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1856 irn_arity = get_irn_arity(block);
1857 for (i = 0; i < irn_arity; i++) {
1858 if (!is_Bad(get_irn_n(block, i))) break;
1860 if (i == irn_arity) return new_Bad();
1864 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1865 blocks predecessors is dead. */
1866 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1867 irn_arity = get_irn_arity(node);
1868 for (i = -1; i < irn_arity; i++) {
1869 if (is_Bad(get_irn_n(node, i))) {
1875 /* With this code we violate the agreement that local_optimize
1876 only leaves Bads in Block, Phi and Tuple nodes. */
1877 /* If Block has only Bads as predecessors it's garbage. */
1878 /* If Phi has only Bads as predecessors it's garbage. */
1879 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1880 irn_arity = get_irn_arity(node);
1881 for (i = 0; i < irn_arity; i++) {
1882 if (!is_Bad(get_irn_n(node, i))) break;
1884 if (i == irn_arity) node = new_Bad();
1892 * These optimizations deallocate nodes from the obstack.
1893 * It can only be called if it is guaranteed that no other nodes
1894 * reference this one, i.e., right after construction of a node.
1897 optimize_node (ir_node *n)
1901 opcode iro = get_irn_opcode(n);
1903 /* Allways optimize Phi nodes: part of the construction. */
1904 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1906 /* constant expression evaluation / constant folding */
1907 if (get_opt_constant_folding()) {
1908 /* constants can not be evaluated */
1909 if (iro != iro_Const) {
1910 /* try to evaluate */
1911 tv = computed_value (n);
1912 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1914 * we MUST copy the node here temporary, because it's still needed
1915 * for DBG_OPT_ALGSIM0
1917 int node_size = offsetof(ir_node, attr) + n->op->attr_size;
1918 ir_node *x = alloca(node_size);
1920 memcpy(x, n, node_size);
1923 /* evaluation was successful -- replace the node. */
1924 obstack_free (current_ir_graph->obst, n);
1925 n = new_Const (get_tarval_mode (tv), tv);
1932 /* remove unnecessary nodes */
1933 if (get_opt_constant_folding() ||
1934 (iro == iro_Phi) || /* always optimize these nodes. */
1936 (iro == iro_Proj) ||
1937 (iro == iro_Block) ) /* Flags tested local. */
1938 n = equivalent_node (n);
1940 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1942 /** common subexpression elimination **/
1943 /* Checks whether n is already available. */
1944 /* The block input is used to distinguish different subexpressions. Right
1945 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
1946 subexpressions within a block. */
1948 n = identify_cons (current_ir_graph->value_table, n);
1951 /* We found an existing, better node, so we can deallocate the old node. */
1952 obstack_free (current_ir_graph->obst, oldn);
1957 /* Some more constant expression evaluation that does not allow to
1959 iro = get_irn_opcode(n);
1960 if (get_opt_constant_folding() ||
1961 (iro == iro_Cond) ||
1962 (iro == iro_Proj)) /* Flags tested local. */
1963 n = transform_node (n);
1965 /* Remove nodes with dead (Bad) input.
1966 Run always for transformation induced Bads. */
1969 /* Now we have a legal, useful node. Enter it in hash table for cse */
1970 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1971 n = identify_remember (current_ir_graph->value_table, n);
1979 * These optimizations never deallocate nodes. This can cause dead
1980 * nodes lying on the obstack. Remove these by a dead node elimination,
1981 * i.e., a copying garbage collection.
1984 optimize_in_place_2 (ir_node *n)
1988 opcode iro = get_irn_opcode(n);
1990 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1992 /* if not optimize return n */
1995 /* Here this is possible. Why? */
2000 /* constant expression evaluation / constant folding */
2001 if (get_opt_constant_folding()) {
2002 /* constants can not be evaluated */
2003 if (iro != iro_Const) {
2004 /* try to evaluate */
2005 tv = computed_value (n);
2006 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2007 /* evaluation was successful -- replace the node. */
2008 n = new_Const (get_tarval_mode (tv), tv);
2015 /* remove unnecessary nodes */
2016 if (get_opt_constant_folding() ||
2017 (iro == iro_Phi) || /* always optimize these nodes. */
2018 (iro == iro_Id) || /* ... */
2019 (iro == iro_Proj) || /* ... */
2020 (iro == iro_Block) ) /* Flags tested local. */
2021 n = equivalent_node (n);
2023 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
2025 /** common subexpression elimination **/
2026 /* Checks whether n is already available. */
2027 /* The block input is used to distinguish different subexpressions. Right
2028 now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2029 subexpressions within a block. */
2030 if (get_opt_cse()) {
2031 n = identify (current_ir_graph->value_table, n);
2034 /* Some more constant expression evaluation. */
2035 iro = get_irn_opcode(n);
2036 if (get_opt_constant_folding() ||
2037 (iro == iro_Cond) ||
2038 (iro == iro_Proj)) /* Flags tested local. */
2039 n = transform_node (n);
2041 /* Remove nodes with dead (Bad) input.
2042 Run always for transformation induced Bads. */
2045 /* Now we can verify the node, as it has no dead inputs any more. */
2048 /* Now we have a legal, useful node. Enter it in hash table for cse.
2049 Blocks should be unique anyways. (Except the successor of start:
2050 is cse with the start block!) */
2051 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2052 n = identify_remember (current_ir_graph->value_table, n);
2058 * Wrapper for external use, set proper status bits after optimization.
2061 optimize_in_place (ir_node *n)
2063 /* Handle graph state */
2064 assert(get_irg_phase_state(current_ir_graph) != phase_building);
2066 if (get_opt_global_cse())
2067 set_irg_pinned(current_ir_graph, op_pin_state_floats);
2068 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2069 set_irg_outs_inconsistent(current_ir_graph);
2071 /* Maybe we could also test whether optimizing the node can
2072 change the control graph. */
2073 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2074 set_irg_dom_inconsistent(current_ir_graph);
2075 return optimize_in_place_2 (n);
2079 * set the default ir op operations
2081 ir_op *firm_set_default_operations(ir_op *op)
2083 op = firm_set_default_computed_value(op);
2084 op = firm_set_default_equivalent_node(op);
2085 op = firm_set_default_transform_node(op);
2086 op = firm_set_default_node_cmp_attr(op);