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"
24 # include "dbginfo_t.h"
25 # include "iropt_dbg.h"
26 # include "irflag_t.h"
27 # include "firmstat.h"
29 /* Make types visible to allow most efficient access */
30 # include "entity_t.h"
33 * Trivial INLINEable routine for copy propagation.
34 * Does follow Ids, needed to optimize INLINEd code.
36 static INLINE ir_node *
37 follow_Id (ir_node *n)
39 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
44 * Returns the tarval of a Const node or tarval_bad for all other nodes.
46 static INLINE tarval *
49 if ((n != NULL) && (get_irn_op(n) == op_Const))
50 return get_Const_tarval(n); /* might return tarval_bad */
55 static tarval *computed_value_Const(ir_node *n)
57 return get_Const_tarval(n);
60 static tarval *computed_value_SymConst(ir_node *n)
62 if ((get_SymConst_kind(n) == size) &&
63 (get_type_state(get_SymConst_type(n))) == layout_fixed)
64 return new_tarval_from_long (get_type_size(get_SymConst_type(n)), mode_Is);
68 static tarval *computed_value_Add(ir_node *n)
70 ir_node *a = get_Add_left(n);
71 ir_node *b = get_Add_right(n);
73 tarval *ta = value_of(a);
74 tarval *tb = value_of(b);
76 if ((ta != tarval_bad) && (tb != tarval_bad)
77 && (get_irn_mode(a) == get_irn_mode(b))
78 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
79 return tarval_add(ta, tb);
84 static tarval *computed_value_Sub(ir_node *n)
86 ir_node *a = get_Sub_left(n);
87 ir_node *b = get_Sub_right(n);
89 tarval *ta = value_of(a);
90 tarval *tb = value_of(b);
92 if ((ta != tarval_bad) && (tb != tarval_bad)
93 && (get_irn_mode(a) == get_irn_mode(b))
94 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
95 return tarval_sub(ta, tb);
100 static tarval *computed_value_Minus(ir_node *n)
102 ir_node *a = get_Minus_op(n);
103 tarval *ta = value_of(a);
105 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
106 return tarval_neg(ta);
111 static tarval *computed_value_Mul(ir_node *n)
113 ir_node *a = get_Mul_left(n);
114 ir_node *b = get_Mul_right(n);
116 tarval *ta = value_of(a);
117 tarval *tb = value_of(b);
119 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
120 return tarval_mul(ta, tb);
122 /* a*0 = 0 or 0*b = 0:
123 calls computed_value recursive and returns the 0 with proper
127 if ( ( ((v = ta) != tarval_bad)
128 && (v == get_mode_null(get_tarval_mode(v))) )
129 || ( ((v = tb) != tarval_bad)
130 && (v == get_mode_null(get_tarval_mode(v))) )) {
137 static tarval *computed_value_Quot(ir_node *n)
139 ir_node *a = get_Quot_left(n);
140 ir_node *b = get_Quot_right(n);
142 tarval *ta = value_of(a);
143 tarval *tb = value_of(b);
145 /* This was missing in original implementation. Why? */
146 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
147 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
148 return tarval_quo(ta, tb);
153 static tarval *computed_value_Div(ir_node *n)
155 ir_node *a = get_Div_left(n);
156 ir_node *b = get_Div_right(n);
158 tarval *ta = value_of(a);
159 tarval *tb = value_of(b);
161 /* This was missing in original implementation. Why? */
162 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
163 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
164 return tarval_div(ta, tb);
169 static tarval *computed_value_Mod(ir_node *n)
171 ir_node *a = get_Mod_left(n);
172 ir_node *b = get_Mod_right(n);
174 tarval *ta = value_of(a);
175 tarval *tb = value_of(b);
177 /* This was missing in original implementation. Why? */
178 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
179 if (tb != get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
180 return tarval_mod(ta, tb);
185 static tarval *computed_value_Abs(ir_node *n)
187 ir_node *a = get_Abs_op(n);
188 tarval *ta = value_of(a);
190 if (ta != tarval_bad)
191 return tarval_abs(ta);
196 static tarval *computed_value_And(ir_node *n)
198 ir_node *a = get_And_left(n);
199 ir_node *b = get_And_right(n);
201 tarval *ta = value_of(a);
202 tarval *tb = value_of(b);
204 if ((ta != tarval_bad) && (tb != tarval_bad)) {
205 return tarval_and (ta, tb);
209 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_NULL)
210 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
217 static tarval *computed_value_Or(ir_node *n)
219 ir_node *a = get_Or_left(n);
220 ir_node *b = get_Or_right(n);
222 tarval *ta = value_of(a);
223 tarval *tb = value_of(b);
225 if ((ta != tarval_bad) && (tb != tarval_bad)) {
226 return tarval_or (ta, tb);
229 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
230 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
237 static tarval *computed_value_Eor(ir_node *n)
239 ir_node *a = get_Eor_left(n);
240 ir_node *b = get_Eor_right(n);
242 tarval *ta = value_of(a);
243 tarval *tb = value_of(b);
245 if ((ta != tarval_bad) && (tb != tarval_bad)) {
246 return tarval_eor (ta, tb);
251 static tarval *computed_value_Not(ir_node *n)
253 ir_node *a = get_Not_op(n);
254 tarval *ta = value_of(a);
256 if (ta != tarval_bad)
257 return tarval_not(ta);
262 static tarval *computed_value_Shl(ir_node *n)
264 ir_node *a = get_Shl_left(n);
265 ir_node *b = get_Shl_right(n);
267 tarval *ta = value_of(a);
268 tarval *tb = value_of(b);
270 if ((ta != tarval_bad) && (tb != tarval_bad)) {
271 return tarval_shl (ta, tb);
276 static tarval *computed_value_Shr(ir_node *n)
278 ir_node *a = get_Shr_left(n);
279 ir_node *b = get_Shr_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_shr (ta, tb);
290 static tarval *computed_value_Shrs(ir_node *n)
292 ir_node *a = get_Shrs_left(n);
293 ir_node *b = get_Shrs_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_shrs (ta, tb);
304 static tarval *computed_value_Rot(ir_node *n)
306 ir_node *a = get_Rot_left(n);
307 ir_node *b = get_Rot_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_rot (ta, tb); */
318 static tarval *computed_value_Conv(ir_node *n)
320 ir_node *a = get_Conv_op(n);
321 tarval *ta = value_of(a);
323 if (ta != tarval_bad)
324 return tarval_convert_to(ta, get_irn_mode(n));
329 static tarval *computed_value_Proj(ir_node *n)
331 ir_node *a = get_Proj_pred(n), *b;
334 /* Optimize Cmp nodes.
335 This performs a first step of unreachable code elimination.
336 Proj can not be computed, but folding a Cmp above the Proj here is
337 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
339 There are several case where we can evaluate a Cmp node:
340 1. The nodes compared are both the same. If we compare for
341 equal, greater equal, ... this will return true, else it
342 will return false. This step relies on cse.
343 2. The predecessors of Cmp are target values. We can evaluate
345 3. The predecessors are Allocs or void* constants. Allocs never
346 return NULL, they raise an exception. Therefore we can predict
348 if (get_irn_op(a) == op_Cmp) {
349 aa = get_Cmp_left(a);
350 ab = get_Cmp_right(a);
352 if (aa == ab) { /* 1.: */
353 /* This is a tric with the bits used for encoding the Cmp
354 Proj numbers, the following statement is not the same:
355 return new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
356 return new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
358 tarval *taa = computed_value (aa);
359 tarval *tab = computed_value (ab);
361 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
362 /* strange checks... */
363 pnc_number flags = tarval_cmp (taa, tab);
364 if (flags != False) {
365 return new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
367 } else { /* check for 3.: */
368 ir_node *aaa = skip_nop(skip_Proj(aa));
369 ir_node *aba = skip_nop(skip_Proj(ab));
371 if ( ( (/* aa is ProjP and aaa is Alloc */
372 (get_irn_op(aa) == op_Proj)
373 && (mode_is_reference(get_irn_mode(aa)))
374 && (get_irn_op(aaa) == op_Alloc))
375 && ( (/* ab is constant void */
376 (get_irn_op(ab) == op_Const)
377 && (mode_is_reference(get_irn_mode(ab)))
378 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
379 || (/* ab is other Alloc */
380 (get_irn_op(ab) == op_Proj)
381 && (mode_is_reference(get_irn_mode(ab)))
382 && (get_irn_op(aba) == op_Alloc)
384 || (/* aa is void and aba is Alloc */
385 (get_irn_op(aa) == op_Const)
386 && (mode_is_reference(get_irn_mode(aa)))
387 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
388 && (get_irn_op(ab) == op_Proj)
389 && (mode_is_reference(get_irn_mode(ab)))
390 && (get_irn_op(aba) == op_Alloc)))
392 return new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
395 } else if (get_irn_op(a) == op_DivMod) {
396 tarval *tb = value_of(b = get_DivMod_right(a));
397 tarval *ta = value_of(a = get_DivMod_left(a));
399 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
400 if (tb == get_mode_null(get_tarval_mode(tb))) /* div by zero: return tarval_bad */
402 if (get_Proj_proj(n)== 0) /* Div */
403 return tarval_div(ta, tb);
405 return tarval_mod(ta, tb);
412 * If the parameter n can be computed, return its value, else tarval_bad.
413 * Performs constant folding.
415 * GL: Only if n is arithmetic operator?
417 tarval *computed_value(ir_node *n)
419 if (n->op->computed_value)
420 return n->op->computed_value(n);
425 * set the default computed_value evaluator
427 static ir_op *firm_set_default_computed_value(ir_op *op)
431 op->computed_value = computed_value_##a; \
456 op->computed_value = NULL;
464 /* returns 1 if the a and b are pointers to different locations. */
466 different_identity (ir_node *a, ir_node *b)
468 assert (mode_is_reference(get_irn_mode (a))
469 && mode_is_reference(get_irn_mode (b)));
471 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
472 ir_node *a1 = get_Proj_pred (a);
473 ir_node *b1 = get_Proj_pred (b);
474 if (a1 != b1 && get_irn_op (a1) == op_Alloc
475 && get_irn_op (b1) == op_Alloc)
482 static ir_node *equivalent_node_Block(ir_node *n)
486 /* The Block constructor does not call optimize, but mature_block
487 calls the optimization. */
488 assert(get_Block_matured(n));
490 /* Straightening: a single entry Block following a single exit Block
491 can be merged, if it is not the Start block. */
492 /* !!! Beware, all Phi-nodes of n must have been optimized away.
493 This should be true, as the block is matured before optimize is called.
494 But what about Phi-cycles with the Phi0/Id that could not be resolved?
495 Remaining Phi nodes are just Ids. */
496 if ((get_Block_n_cfgpreds(n) == 1) &&
497 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
498 (get_opt_control_flow_straightening())) {
499 n = get_nodes_Block(get_Block_cfgpred(n, 0)); DBG_OPT_STG;
501 } else if ((get_Block_n_cfgpreds(n) == 2) &&
502 (get_opt_control_flow_weak_simplification())) {
503 /* Test whether Cond jumps twice to this block
504 @@@ we could do this also with two loops finding two preds from several ones. */
505 ir_node *a = get_Block_cfgpred(n, 0);
506 ir_node *b = get_Block_cfgpred(n, 1);
508 if ((get_irn_op(a) == op_Proj) &&
509 (get_irn_op(b) == op_Proj) &&
510 (get_Proj_pred(a) == get_Proj_pred(b)) &&
511 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
512 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
513 /* Also a single entry Block following a single exit Block. Phis have
514 twice the same operand and will be optimized away. */
515 n = get_nodes_Block(a); DBG_OPT_IFSIM;
517 } else if (get_opt_unreachable_code() &&
518 (n != current_ir_graph->start_block) &&
519 (n != current_ir_graph->end_block) ) {
521 /* If all inputs are dead, this block is dead too, except if it is
522 the start or end block. This is a step of unreachable code
524 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
525 if (!is_Bad(get_Block_cfgpred(n, i))) break;
527 if (i == get_Block_n_cfgpreds(n))
534 static ir_node *equivalent_node_Jmp(ir_node *n)
536 /* GL: Why not same for op_Raise?? */
537 /* unreachable code elimination */
538 if (is_Bad(get_nodes_Block(n)))
544 static ir_node *equivalent_node_Cond(ir_node *n)
546 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
547 See cases for iro_Cond and iro_Proj in transform_node. */
551 static ir_node *equivalent_node_Or(ir_node *n)
555 ir_node *a = get_Or_left(n);
556 ir_node *b = get_Or_right(n);
560 n = a; DBG_OPT_ALGSIM1;
567 * optimize operations that are commutative and have neutral 0.
569 static ir_node *equivalent_node_neutral_zero(ir_node *n)
573 ir_node *a = get_binop_left(n);
574 ir_node *b = get_binop_right(n);
579 /* After running compute_node there is only one constant predecessor.
580 Find this predecessors value and remember the other node: */
581 if ((tv = computed_value (a)) != tarval_bad) {
583 } else if ((tv = computed_value (b)) != tarval_bad) {
588 /* If this predecessors constant value is zero, the operation is
589 unnecessary. Remove it: */
590 if (tarval_classify (tv) == TV_CLASSIFY_NULL) {
591 n = on; DBG_OPT_ALGSIM1;
597 static ir_node *equivalent_node_Add(ir_node *n)
599 return equivalent_node_neutral_zero(n);
602 static ir_node *equivalent_node_Eor(ir_node *n)
604 return equivalent_node_neutral_zero(n);
608 * optimize operations that are not commutative but have neutral 0 on left.
609 * Test only one predecessor.
611 static ir_node *equivalent_node_left_zero(ir_node *n)
615 ir_node *a = get_binop_left(n);
616 ir_node *b = get_binop_right(n);
618 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_NULL) {
619 n = a; DBG_OPT_ALGSIM1;
625 static ir_node *equivalent_node_Sub(ir_node *n)
627 return equivalent_node_left_zero(n);
630 static ir_node *equivalent_node_Shl(ir_node *n)
632 return equivalent_node_left_zero(n);
635 static ir_node *equivalent_node_Shr(ir_node *n)
637 return equivalent_node_left_zero(n);
640 static ir_node *equivalent_node_Shrs(ir_node *n)
642 return equivalent_node_left_zero(n);
645 static ir_node *equivalent_node_Rot(ir_node *n)
647 return equivalent_node_left_zero(n);
650 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
654 /* optimize symmetric unop */
655 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
656 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
661 static ir_node *equivalent_node_Not(ir_node *n)
664 return equivalent_node_symmetric_unop(n);
667 static ir_node *equivalent_node_Minus(ir_node *n)
669 /* --x == x */ /* ??? Is this possible or can --x raise an
670 out of bounds exception if min =! max? */
671 return equivalent_node_symmetric_unop(n);
674 static ir_node *equivalent_node_Mul(ir_node *n)
678 ir_node *a = get_Mul_left(n);
679 ir_node *b = get_Mul_right(n);
681 /* Mul is commutative and has again an other neutral element. */
682 if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ONE) {
683 n = b; DBG_OPT_ALGSIM1;
684 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) {
685 n = a; DBG_OPT_ALGSIM1;
690 static ir_node *equivalent_node_Div(ir_node *n)
692 ir_node *a = get_Div_left(n);
693 ir_node *b = get_Div_right(n);
695 /* Div is not commutative. */
696 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
697 /* Turn Div into a tuple (mem, bad, a) */
698 ir_node *mem = get_Div_mem(n);
699 turn_into_tuple(n, 3);
700 set_Tuple_pred(n, pn_Div_M, mem);
701 set_Tuple_pred(n, pn_Div_X_except, new_Bad()); /* no exception */
702 set_Tuple_pred(n, pn_Div_res, a);
707 static ir_node *equivalent_node_And(ir_node *n)
711 ir_node *a = get_And_left(n);
712 ir_node *b = get_And_right(n);
715 n = a; /* And has it's own neutral element */
716 } else if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ALL_ONE) {
718 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ALL_ONE) {
721 if (n != oldn) DBG_OPT_ALGSIM1;
725 static ir_node *equivalent_node_Conv(ir_node *n)
728 ir_node *a = get_Conv_op(n);
731 ir_mode *n_mode = get_irn_mode(n);
732 ir_mode *a_mode = get_irn_mode(a);
734 if (n_mode == a_mode) { /* No Conv necessary */
735 n = a; DBG_OPT_ALGSIM3;
736 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
740 n_mode = get_irn_mode(n);
741 b_mode = get_irn_mode(b);
743 if (n_mode == b_mode) {
744 if (n_mode == mode_b) {
745 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM1;
747 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
748 if (smaller_mode(b_mode, a_mode)){
749 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ DBG_OPT_ALGSIM1;
757 static ir_node *equivalent_node_Phi(ir_node *n)
759 /* Several optimizations:
760 - no Phi in start block.
761 - remove Id operators that are inputs to Phi
762 - fold Phi-nodes, iff they have only one predecessor except
768 ir_node *block = NULL; /* to shutup gcc */
769 ir_node *first_val = NULL; /* to shutup gcc */
770 ir_node *scnd_val = NULL; /* to shutup gcc */
772 if (!get_opt_normalize()) return n;
774 n_preds = get_Phi_n_preds(n);
776 block = get_nodes_Block(n);
777 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
778 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
779 if ((is_Bad(block)) || /* Control dead */
780 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
781 return new_Bad(); /* in the Start Block. */
783 if (n_preds == 0) return n; /* Phi of dead Region without predecessors. */
786 /* first we test for a special case: */
787 /* Confirm is a special node fixing additional information for a
788 value that is known at a certain point. This is useful for
789 dataflow analysis. */
791 ir_node *a = follow_Id (get_Phi_pred(n, 0));
792 ir_node *b = follow_Id (get_Phi_pred(n, 1));
793 if ( (get_irn_op(a) == op_Confirm)
794 && (get_irn_op(b) == op_Confirm)
795 && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
796 && (get_irn_n(a, 1) == get_irn_n (b, 1))
797 && (a->data.num == (~b->data.num & irpn_True) )) {
798 return get_irn_n(a, 0);
803 /* Find first non-self-referencing input */
804 for (i = 0; i < n_preds; ++i) {
805 first_val = follow_Id(get_Phi_pred(n, i));
807 set_Phi_pred(n, i, first_val);
808 if ( (first_val != n) /* not self pointer */
809 && (get_irn_op(first_val) != op_Bad) /* value not dead */
810 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
811 break; /* then found first value. */
815 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
816 if (i >= n_preds) { return new_Bad(); }
820 /* follow_Id () for rest of inputs, determine if any of these
821 are non-self-referencing */
822 while (++i < n_preds) {
823 scnd_val = follow_Id(get_Phi_pred(n, i));
825 set_Phi_pred(n, i, scnd_val);
827 && (scnd_val != first_val)
828 && (get_irn_op(scnd_val) != op_Bad)
829 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
834 /* Fold, if no multiple distinct non-self-referencing inputs */
836 n = first_val; DBG_OPT_PHI;
838 /* skip the remaining Ids. */
839 while (++i < n_preds) {
840 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
846 static ir_node *equivalent_node_Load(ir_node *n)
848 #if 0 /* Is an illegal transformation: different nodes can
849 represent the same pointer value!! */
850 ir_node *a = skip_Proj(get_Load_mem(n));
851 ir_node *b = get_Load_ptr(n);
853 if (get_irn_op(a) == op_Store) {
854 if ( different_identity (b, get_Store_ptr(a))) {
855 /* load and store use different pointers, therefore load
856 needs not take store's memory but the state before. */
857 set_Load_mem (n, get_Store_mem(a));
858 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
865 static ir_node *equivalent_node_Store(ir_node *n)
869 /* remove unnecessary store. */
870 ir_node *a = skip_Proj(get_Store_mem(n));
871 ir_node *b = get_Store_ptr(n);
872 ir_node *c = skip_Proj(get_Store_value(n));
874 if (get_irn_op(a) == op_Store
875 && get_Store_ptr(a) == b
876 && skip_Proj(get_Store_value(a)) == c) {
877 /* We have twice exactly the same store -- a write after write. */
879 } else if (get_irn_op(c) == op_Load
880 && (a == c || skip_Proj(get_Load_mem(c)) == a)
881 && get_Load_ptr(c) == b ) {
882 /* We just loaded the value from the same memory, i.e., the store
883 doesn't change the memory -- a write after read. */
884 a = get_Store_mem(n);
885 turn_into_tuple(n, 2);
886 set_Tuple_pred(n, pn_Store_M, a);
887 set_Tuple_pred(n, pn_Store_X_except, new_Bad()); DBG_OPT_WAR;
892 static ir_node *equivalent_node_Proj(ir_node *n)
896 ir_node *a = get_Proj_pred(n);
898 if ( get_irn_op(a) == op_Tuple) {
899 /* Remove the Tuple/Proj combination. */
900 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
901 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
903 assert(0); /* This should not happen! */
906 } else if (get_irn_mode(n) == mode_X &&
907 is_Bad(get_nodes_Block(n))) {
908 /* Remove dead control flow -- early gigo. */
914 static ir_node *equivalent_node_Id(ir_node *n)
918 n = follow_Id (n); DBG_OPT_ID;
923 case iro_Mod, Quot, DivMod
924 DivMod allocates new nodes --> it's treated in transform node.
925 What about Quot, DivMod?
929 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
930 * perform no actual computation, as, e.g., the Id nodes. It does not create
931 * new nodes. It is therefore safe to free n if the node returned is not n.
932 * If a node returns a Tuple we can not just skip it. If the size of the
933 * in array fits, we transform n into a tuple (e.g., Div).
936 equivalent_node (ir_node *n)
938 if (n->op->equivalent_node)
939 return n->op->equivalent_node(n);
944 * set the default equivalent node operation
946 static ir_op *firm_set_default_equivalent_node(ir_op *op)
950 op->equivalent_node = equivalent_node_##a; \
977 op->equivalent_node = NULL;
985 * Do node specific optimizations of nodes predecessors.
988 optimize_preds(ir_node *n) {
989 ir_node *a = NULL, *b = NULL;
991 /* get the operands we will work on for simple cases. */
993 a = get_binop_left(n);
994 b = get_binop_right(n);
995 } else if (is_unop(n)) {
999 switch (get_irn_opcode(n)) {
1002 /* We don't want Cast as input to Cmp. */
1003 if (get_irn_op(a) == op_Cast) {
1007 if (get_irn_op(b) == op_Cast) {
1009 set_Cmp_right(n, b);
1017 static ir_node *transform_node_Div(ir_node *n)
1019 tarval *ta = computed_value(n);
1021 if (ta != tarval_bad) {
1022 /* Turn Div into a tuple (mem, bad, value) */
1023 ir_node *mem = get_Div_mem(n);
1025 turn_into_tuple(n, 3);
1026 set_Tuple_pred(n, pn_Div_M, mem);
1027 set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1028 set_Tuple_pred(n, pn_Div_res, new_Const(get_tarval_mode(ta), ta));
1033 static ir_node *transform_node_Mod(ir_node *n)
1035 tarval *ta = computed_value(n);
1037 if (ta != tarval_bad) {
1038 /* Turn Mod into a tuple (mem, bad, value) */
1039 ir_node *mem = get_Mod_mem(n);
1040 turn_into_tuple(n, 3);
1041 set_Tuple_pred(n, pn_Mod_M, mem);
1042 set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1043 set_Tuple_pred(n, pn_Mod_res, new_Const(get_tarval_mode(ta), ta));
1048 static ir_node *transform_node_DivMod(ir_node *n)
1052 ir_node *a = get_DivMod_left(n);
1053 ir_node *b = get_DivMod_right(n);
1054 ir_mode *mode = get_irn_mode(a);
1056 if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1060 a = new_Const(mode, get_mode_one(mode));
1061 b = new_Const(mode, get_mode_null(mode));
1064 tarval *ta = value_of(a);
1065 tarval *tb = value_of(b);
1067 if (tb != tarval_bad) {
1068 if (tb == get_mode_one(get_tarval_mode(tb))) {
1069 b = new_Const (mode, get_mode_null(mode));
1071 } else if (ta != tarval_bad) {
1072 tarval *resa, *resb;
1073 resa = tarval_div (ta, tb);
1074 if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1075 Jmp for X result!? */
1076 resb = tarval_mod (ta, tb);
1077 if (resb == tarval_bad) return n; /* Causes exception! */
1078 a = new_Const (mode, resa);
1079 b = new_Const (mode, resb);
1082 } else if (ta == get_mode_null(get_tarval_mode(ta))) {
1087 if (evaluated) { /* replace by tuple */
1088 ir_node *mem = get_DivMod_mem(n);
1089 turn_into_tuple(n, 4);
1090 set_Tuple_pred(n, pn_DivMod_M, mem);
1091 set_Tuple_pred(n, pn_DivMod_X_except, new_Bad()); /* no exception */
1092 set_Tuple_pred(n, pn_DivMod_res_div, a);
1093 set_Tuple_pred(n, pn_DivMod_res_mod, b);
1094 assert(get_nodes_Block(n));
1100 static ir_node *transform_node_Cond(ir_node *n)
1102 /* Replace the Cond by a Jmp if it branches on a constant
1105 ir_node *a = get_Cond_selector(n);
1106 tarval *ta = value_of(a);
1108 if ((ta != tarval_bad) &&
1109 (get_irn_mode(a) == mode_b) &&
1110 (get_opt_unreachable_code())) {
1111 /* It's a boolean Cond, branching on a boolean constant.
1112 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1113 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
1114 turn_into_tuple(n, 2);
1115 if (ta == tarval_b_true) {
1116 set_Tuple_pred(n, pn_Cond_false, new_Bad());
1117 set_Tuple_pred(n, pn_Cond_true, jmp);
1119 set_Tuple_pred(n, pn_Cond_false, jmp);
1120 set_Tuple_pred(n, pn_Cond_true, new_Bad());
1122 /* We might generate an endless loop, so keep it alive. */
1123 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
1124 } else if ((ta != tarval_bad) &&
1125 (get_irn_mode(a) == mode_Iu) &&
1126 (get_Cond_kind(n) == dense) &&
1127 (get_opt_unreachable_code())) {
1128 /* I don't want to allow Tuples smaller than the biggest Proj.
1129 Also this tuple might get really big...
1130 I generate the Jmp here, and remember it in link. Link is used
1131 when optimizing Proj. */
1132 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
1133 /* We might generate an endless loop, so keep it alive. */
1134 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
1135 } else if ((get_irn_op(a) == op_Eor)
1136 && (get_irn_mode(a) == mode_b)
1137 && (tarval_classify(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1138 /* The Eor is a negate. Generate a new Cond without the negate,
1139 simulate the negate by exchanging the results. */
1140 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
1142 } else if ((get_irn_op(a) == op_Not)
1143 && (get_irn_mode(a) == mode_b)) {
1144 /* A Not before the Cond. Generate a new Cond without the Not,
1145 simulate the Not by exchanging the results. */
1146 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
1152 static ir_node *transform_node_Eor(ir_node *n)
1154 ir_node *a = get_Eor_left(n);
1155 ir_node *b = get_Eor_right(n);
1157 if ((get_irn_mode(n) == mode_b)
1158 && (get_irn_op(a) == op_Proj)
1159 && (get_irn_mode(a) == mode_b)
1160 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE)
1161 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1162 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1163 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
1164 mode_b, get_negated_pnc(get_Proj_proj(a)));
1165 else if ((get_irn_mode(n) == mode_b)
1166 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE))
1167 /* The Eor is a Not. Replace it by a Not. */
1168 /* ????!!!Extend to bitfield 1111111. */
1169 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
1174 static ir_node *transform_node_Not(ir_node *n)
1176 ir_node *a = get_Not_op(n);
1178 if ( (get_irn_mode(n) == mode_b)
1179 && (get_irn_op(a) == op_Proj)
1180 && (get_irn_mode(a) == mode_b)
1181 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1182 /* We negate a Cmp. The Cmp has the negated result anyways! */
1183 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
1184 mode_b, get_negated_pnc(get_Proj_proj(a)));
1191 * Tries several [inplace] [optimizing] transformations and returns an
1192 * equivalent node. The difference to equivalent_node() is that these
1193 * transformations _do_ generate new nodes, and thus the old node must
1194 * not be freed even if the equivalent node isn't the old one.
1196 static ir_node *transform_node(ir_node *n)
1198 if (n->op->transform_node)
1199 n = n->op->transform_node(n);
1204 * set the default transform node operation
1206 static ir_op *firm_set_default_transform_node(ir_op *op)
1210 op->transform_node = transform_node_##a; \
1221 op->transform_node = NULL;
1229 /* **************** Common Subexpression Elimination **************** */
1231 /** The size of the hash table used, should estimate the number of nodes
1233 #define N_IR_NODES 512
1235 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1237 return (get_Const_tarval(a) != get_Const_tarval(b))
1238 || (get_Const_type(a) != get_Const_type(b));
1241 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1243 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1246 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1248 return get_Filter_proj(a) != get_Filter_proj(b);
1251 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1253 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1254 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1257 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1259 return (get_irn_free_attr(a) != get_irn_free_attr(b));
1262 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1264 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1265 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
1268 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1270 return (get_irn_call_attr(a) != get_irn_call_attr(b));
1273 static int node_cmp_attr_FuncCall(ir_node *a, ir_node *b)
1275 return (get_irn_funccall_attr(a) != get_irn_funccall_attr(b));
1278 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1280 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
1281 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
1282 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
1283 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1284 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
1287 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1289 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1292 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1294 return get_Cast_type(a) != get_Cast_type(b);
1298 * set the default node attribute compare operation
1300 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
1304 op->node_cmp_attr = node_cmp_attr_##a; \
1320 op->node_cmp_attr = NULL;
1328 * Compare function for two nodes in the hash table. Gets two
1329 * nodes as parameters. Returns 0 if the nodes are a cse.
1332 vt_cmp (const void *elt, const void *key)
1340 if (a == b) return 0;
1342 if ((get_irn_op(a) != get_irn_op(b)) ||
1343 (get_irn_mode(a) != get_irn_mode(b))) return 1;
1345 /* compare if a's in and b's in are equal */
1346 irn_arity_a = get_irn_arity (a);
1347 if (irn_arity_a != get_irn_arity(b))
1350 /* for block-local cse and pinned nodes: */
1351 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
1352 if (get_irn_n(a, -1) != get_irn_n(b, -1))
1356 /* compare a->in[0..ins] with b->in[0..ins] */
1357 for (i = 0; i < irn_arity_a; i++)
1358 if (get_irn_n(a, i) != get_irn_n(b, i))
1362 * here, we already now that the nodes are identical except their
1365 if (a->op->node_cmp_attr)
1366 return a->op->node_cmp_attr(a, b);
1372 * Calculate a hash value of a node.
1375 ir_node_hash (ir_node *node)
1380 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
1381 h = irn_arity = get_irn_arity(node);
1383 /* consider all in nodes... except the block. */
1384 for (i = 0; i < irn_arity; i++) {
1385 h = 9*h + (unsigned long)get_irn_n(node, i);
1389 h = 9*h + (unsigned long) get_irn_mode (node);
1391 h = 9*h + (unsigned long) get_irn_op (node);
1397 new_identities (void)
1399 return new_pset (vt_cmp, N_IR_NODES);
1403 del_identities (pset *value_table)
1405 del_pset (value_table);
1409 * Return the canonical node computing the same value as n.
1410 * Looks up the node in a hash table.
1412 static INLINE ir_node *
1413 identify (pset *value_table, ir_node *n)
1417 if (!value_table) return n;
1419 /* TODO: use a generic commutative attribute */
1420 if (get_opt_reassociation()) {
1421 if (is_op_commutative(get_irn_op(n))) {
1422 /* for commutative operators perform a OP b == b OP a */
1423 if (get_binop_left(n) > get_binop_right(n)) {
1424 ir_node *h = get_binop_left(n);
1425 set_binop_left(n, get_binop_right(n));
1426 set_binop_right(n, h);
1431 o = pset_find (value_table, n, ir_node_hash (n));
1438 * During construction we set the pinned flag in the graph right when the
1439 * optimizatin is performed. The flag turning on procedure global cse could
1440 * be changed between two allocations. This way we are safe.
1442 static INLINE ir_node *
1443 identify_cons (pset *value_table, ir_node *n) {
1445 n = identify(value_table, n);
1446 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1447 set_irg_pinned(current_ir_graph, floats);
1452 * Return the canonical node computing the same value as n.
1453 * Looks up the node in a hash table, enters it in the table
1454 * if it isn't there yet.
1457 identify_remember (pset *value_table, ir_node *node)
1461 if (!value_table) return node;
1463 /* lookup or insert in hash table with given hash key. */
1464 o = pset_insert (value_table, node, ir_node_hash (node));
1466 if (o == node) return node;
1472 add_identities (pset *value_table, ir_node *node) {
1473 identify_remember (value_table, node);
1477 * garbage in, garbage out. If a node has a dead input, i.e., the
1478 * Bad node is input to the node, return the Bad node.
1480 static INLINE ir_node *
1481 gigo (ir_node *node)
1484 ir_op* op = get_irn_op(node);
1486 /* remove garbage blocks by looking at control flow that leaves the block
1487 and replacing the control flow by Bad. */
1488 if (get_irn_mode(node) == mode_X) {
1489 ir_node *block = get_nodes_block(node);
1490 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1491 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1492 irn_arity = get_irn_arity(block);
1493 for (i = 0; i < irn_arity; i++) {
1494 if (!is_Bad(get_irn_n(block, i))) break;
1496 if (i == irn_arity) return new_Bad();
1500 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1501 blocks predecessors is dead. */
1502 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1503 irn_arity = get_irn_arity(node);
1504 for (i = -1; i < irn_arity; i++) {
1505 if (is_Bad(get_irn_n(node, i))) {
1511 /* With this code we violate the agreement that local_optimize
1512 only leaves Bads in Block, Phi and Tuple nodes. */
1513 /* If Block has only Bads as predecessors it's garbage. */
1514 /* If Phi has only Bads as predecessors it's garbage. */
1515 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1516 irn_arity = get_irn_arity(node);
1517 for (i = 0; i < irn_arity; i++) {
1518 if (!is_Bad(get_irn_n(node, i))) break;
1520 if (i == irn_arity) node = new_Bad();
1528 * These optimizations deallocate nodes from the obstack.
1529 * It can only be called if it is guaranteed that no other nodes
1530 * reference this one, i.e., right after construction of a node.
1533 optimize_node (ir_node *n)
1537 opcode iro = get_irn_opcode(n);
1539 /* Allways optimize Phi nodes: part of the construction. */
1540 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1542 /* constant expression evaluation / constant folding */
1543 if (get_opt_constant_folding()) {
1544 /* constants can not be evaluated */
1545 if (get_irn_op(n) != op_Const) {
1546 /* try to evaluate */
1547 tv = computed_value (n);
1548 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1550 * we MUST copy the node here temparary, because it's still needed
1551 * for DBG_OPT_ALGSIM0
1555 /* evaluation was succesful -- replace the node. */
1556 obstack_free (current_ir_graph->obst, n);
1557 n = new_Const (get_tarval_mode (tv), tv);
1564 /* remove unnecessary nodes */
1565 if (get_opt_constant_folding() ||
1566 (iro == iro_Phi) || /* always optimize these nodes. */
1568 (iro == iro_Proj) ||
1569 (iro == iro_Block) ) /* Flags tested local. */
1570 n = equivalent_node (n);
1572 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1574 /** common subexpression elimination **/
1575 /* Checks whether n is already available. */
1576 /* The block input is used to distinguish different subexpressions. Right
1577 now all nodes are pinned to blocks, i.e., the cse only finds common
1578 subexpressions within a block. */
1580 n = identify_cons (current_ir_graph->value_table, n);
1583 /* We found an existing, better node, so we can deallocate the old node. */
1584 obstack_free (current_ir_graph->obst, oldn);
1589 /* Some more constant expression evaluation that does not allow to
1591 iro = get_irn_opcode(n);
1592 if (get_opt_constant_folding() ||
1593 (iro == iro_Cond) ||
1594 (iro == iro_Proj)) /* Flags tested local. */
1595 n = transform_node (n);
1597 /* Remove nodes with dead (Bad) input.
1598 Run always for transformation induced Bads. */
1601 /* Now we have a legal, useful node. Enter it in hash table for cse */
1602 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1603 n = identify_remember (current_ir_graph->value_table, n);
1611 * These optimizations never deallocate nodes. This can cause dead
1612 * nodes lying on the obstack. Remove these by a dead node elimination,
1613 * i.e., a copying garbage collection.
1616 optimize_in_place_2 (ir_node *n)
1620 opcode iro = get_irn_opcode(n);
1622 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1624 /* if not optimize return n */
1627 /* Here this is possible. Why? */
1632 /* constant expression evaluation / constant folding */
1633 if (get_opt_constant_folding()) {
1634 /* constants can not be evaluated */
1635 if (iro != iro_Const) {
1636 /* try to evaluate */
1637 tv = computed_value (n);
1638 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1639 /* evaluation was succesful -- replace the node. */
1640 n = new_Const (get_tarval_mode (tv), tv);
1647 /* remove unnecessary nodes */
1648 /*if (get_opt_constant_folding()) */
1649 if (get_opt_constant_folding() ||
1650 (iro == iro_Phi) || /* always optimize these nodes. */
1651 (iro == iro_Id) || /* ... */
1652 (iro == iro_Proj) || /* ... */
1653 (iro == iro_Block) ) /* Flags tested local. */
1654 n = equivalent_node (n);
1656 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1658 /** common subexpression elimination **/
1659 /* Checks whether n is already available. */
1660 /* The block input is used to distinguish different subexpressions. Right
1661 now all nodes are pinned to blocks, i.e., the cse only finds common
1662 subexpressions within a block. */
1663 if (get_opt_cse()) {
1664 n = identify (current_ir_graph->value_table, n);
1667 /* Some more constant expression evaluation. */
1668 iro = get_irn_opcode(n);
1669 if (get_opt_constant_folding() ||
1670 (iro == iro_Cond) ||
1671 (iro == iro_Proj)) /* Flags tested local. */
1672 n = transform_node (n);
1674 /* Remove nodes with dead (Bad) input.
1675 Run always for transformation induced Bads. */
1678 /* Now we can verify the node, as it has no dead inputs any more. */
1681 /* Now we have a legal, useful node. Enter it in hash table for cse.
1682 Blocks should be unique anyways. (Except the successor of start:
1683 is cse with the start block!) */
1684 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1685 n = identify_remember (current_ir_graph->value_table, n);
1691 * Wrapper for external use, set proper status bits after optimization.
1694 optimize_in_place (ir_node *n)
1696 /* Handle graph state */
1697 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1699 if (get_opt_global_cse())
1700 set_irg_pinned(current_ir_graph, floats);
1701 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1702 set_irg_outs_inconsistent(current_ir_graph);
1703 /* Maybe we could also test whether optimizing the node can
1704 change the control graph. */
1705 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1706 set_irg_dom_inconsistent(current_ir_graph);
1707 return optimize_in_place_2 (n);
1711 * set the default ir op operations
1713 ir_op *firm_set_default_operations(ir_op *op)
1715 op = firm_set_default_computed_value(op);
1716 op = firm_set_default_equivalent_node(op);
1717 op = firm_set_default_transform_node(op);
1718 op = firm_set_default_node_cmp_attr(op);