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"
28 /* Make types visible to allow most efficient access */
29 # include "entity_t.h"
32 * Trivial INLINEable routine for copy propagation.
33 * Does follow Ids, needed to optimize INLINEd code.
35 static INLINE ir_node *
36 follow_Id (ir_node *n)
38 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
43 * Returns the tarval of a Const node or tarval_bad for all other nodes.
45 static INLINE tarval *
48 if ((n != NULL) && (get_irn_op(n) == op_Const))
49 return get_Const_tarval(n); /* might return tarval_bad */
55 * If the parameter n can be computed, return its value, else tarval_bad.
56 * Performs constant folding.
58 * GL: Only if n is arithmetic operator?
61 computed_value (ir_node *n)
65 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
66 /* initialized to uniformly filter invalid constants */
67 tarval *ta = tarval_bad, *tb = tarval_bad;
71 /* get the operands we will work on for simple cases. */
73 a = get_binop_left(n);
74 b = get_binop_right(n);
75 } else if (is_unop(n)) {
79 /* if the operands are constants, get the target value, else set it NULL.
80 (a and b may be NULL if we treat a node that is no computation.) */
84 /* Perform the constant evaluation / computation. */
85 switch (get_irn_opcode(n)) {
87 res = get_Const_tarval(n);
90 if ((get_SymConst_kind(n) == size) &&
91 (get_type_state(get_SymConst_type(n))) == layout_fixed)
92 res = new_tarval_from_long (get_type_size(get_SymConst_type(n)), mode_Is);
95 if ((ta != tarval_bad) && (tb != tarval_bad)
96 && (get_irn_mode(a) == get_irn_mode(b))
97 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
98 res = tarval_add (ta, tb);
102 if ((ta != tarval_bad) && (tb != tarval_bad)
103 && (get_irn_mode(a) == get_irn_mode(b))
104 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
105 res = tarval_sub (ta, tb);
109 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
110 res = tarval_neg (ta);
113 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
114 res = tarval_mul (ta, tb);
116 /* a*0 = 0 or 0*b = 0:
117 calls computed_value recursive and returns the 0 with proper
120 if ( ( ((v = computed_value (a)) != tarval_bad)
121 && (v == get_mode_null(get_tarval_mode(v))) )
122 || ( ((v = computed_value (b)) != tarval_bad)
123 && (v == get_mode_null(get_tarval_mode(v))) )) {
129 /* This was missing in original implementation. Why? */
130 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
131 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
132 res = tarval_quo(ta, tb);
136 /* This was missing in original implementation. Why? */
137 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
138 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
139 res = tarval_div(ta, tb);
143 /* This was missing in original implementation. Why? */
144 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
145 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
146 res = tarval_mod(ta, tb);
149 /* for iro_DivMod see iro_Proj */
151 if (ta != tarval_bad)
152 res = tarval_abs (ta);
155 if ((ta != tarval_bad) && (tb != tarval_bad)) {
156 res = tarval_and (ta, tb);
159 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_NULL)
160 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
166 if ((ta != tarval_bad) && (tb != tarval_bad)) {
167 res = tarval_or (ta, tb);
170 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
171 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
177 if ((ta != tarval_bad) && (tb != tarval_bad)) {
178 res = tarval_eor (ta, tb);
182 if ((ta != tarval_bad)) {
183 res = tarval_not (ta);
187 if ((ta != tarval_bad) && (tb != tarval_bad)) {
188 res = tarval_shl (ta, tb);
192 if ((ta != tarval_bad) && (tb != tarval_bad)) {
193 res = tarval_shr (ta, tb);
197 if ((ta != tarval_bad) && (tb != tarval_bad)) {
198 res = tarval_shrs (ta, tb);
202 if ((ta != tarval_bad) && (tb != tarval_bad)) {
203 /*res = tarval_rot (ta, tb)*/;
207 if (ta != tarval_bad) {
208 res = tarval_convert_to (ta, get_irn_mode (n));
211 case iro_Proj: /* iro_Cmp */
215 a = get_Proj_pred(n);
216 /* Optimize Cmp nodes.
217 This performs a first step of unreachable code elimination.
218 Proj can not be computed, but folding a Cmp above the Proj here is
219 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
221 There are several case where we can evaluate a Cmp node:
222 1. The nodes compared are both the same. If we compare for
223 equal, greater equal, ... this will return true, else it
224 will return false. This step relies on cse.
225 2. The predecessors of Cmp are target values. We can evaluate
227 3. The predecessors are Allocs or void* constants. Allocs never
228 return NULL, they raise an exception. Therefore we can predict
230 if (get_irn_op(a) == op_Cmp) {
231 aa = get_Cmp_left(a);
232 ab = get_Cmp_right(a);
233 if (aa == ab) { /* 1.: */
234 /* This is a tric with the bits used for encoding the Cmp
235 Proj numbers, the following statement is not the same:
236 res = new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
237 res = new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
239 tarval *taa = computed_value (aa);
240 tarval *tab = computed_value (ab);
241 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
242 /* strange checks... */
243 pnc_number flags = tarval_cmp (taa, tab);
244 if (flags != False) {
245 res = new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
247 } else { /* check for 3.: */
248 ir_node *aaa = skip_nop(skip_Proj(aa));
249 ir_node *aba = skip_nop(skip_Proj(ab));
250 if ( ( (/* aa is ProjP and aaa is Alloc */
251 (get_irn_op(aa) == op_Proj)
252 && (mode_is_reference(get_irn_mode(aa)))
253 && (get_irn_op(aaa) == op_Alloc))
254 && ( (/* ab is constant void */
255 (get_irn_op(ab) == op_Const)
256 && (mode_is_reference(get_irn_mode(ab)))
257 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
258 || (/* ab is other Alloc */
259 (get_irn_op(ab) == op_Proj)
260 && (mode_is_reference(get_irn_mode(ab)))
261 && (get_irn_op(aba) == op_Alloc)
263 || (/* aa is void and aba is Alloc */
264 (get_irn_op(aa) == op_Const)
265 && (mode_is_reference(get_irn_mode(aa)))
266 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
267 && (get_irn_op(ab) == op_Proj)
268 && (mode_is_reference(get_irn_mode(ab)))
269 && (get_irn_op(aba) == op_Alloc)))
271 res = new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
274 } else if (get_irn_op(a) == op_DivMod) {
275 ta = value_of(get_DivMod_left(a));
276 tb = value_of(get_DivMod_right(a));
277 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
278 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
279 if (get_Proj_proj(n)== 0) /* Div */
280 res = tarval_div(ta, tb);
282 res = tarval_mod(ta, tb);
295 /* returns 1 if the a and b are pointers to different locations. */
297 different_identity (ir_node *a, ir_node *b)
299 assert (mode_is_reference(get_irn_mode (a))
300 && mode_is_reference(get_irn_mode (b)));
302 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
303 ir_node *a1 = get_Proj_pred (a);
304 ir_node *b1 = get_Proj_pred (b);
305 if (a1 != b1 && get_irn_op (a1) == op_Alloc
306 && get_irn_op (b1) == op_Alloc)
314 * equivalent_node() returns a node equivalent to input n. It skips all nodes that
315 * perform no actual computation, as, e.g., the Id nodes. It does not create
316 * new nodes. It is therefore safe to free n if the node returned is not n.
317 * If a node returns a Tuple we can not just skip it. If the size of the
318 * in array fits, we transform n into a tuple (e.g., Div).
321 equivalent_node (ir_node *n)
324 ir_node *a = NULL; /* to shutup gcc */
325 ir_node *b = NULL; /* to shutup gcc */
326 ir_node *c = NULL; /* to shutup gcc */
329 ins = get_irn_arity (n);
331 /* get the operands we will work on */
333 a = get_binop_left(n);
334 b = get_binop_right(n);
335 } else if (is_unop(n)) {
339 /* skip unnecessary nodes. */
340 switch (get_irn_opcode (n)) {
343 /* The Block constructor does not call optimize, but mature_block
344 calls the optimization. */
345 assert(get_Block_matured(n));
347 /* Straightening: a single entry Block following a single exit Block
348 can be merged, if it is not the Start block. */
349 /* !!! Beware, all Phi-nodes of n must have been optimized away.
350 This should be true, as the block is matured before optimize is called.
351 But what about Phi-cycles with the Phi0/Id that could not be resolved?
352 Remaining Phi nodes are just Ids. */
353 if ((get_Block_n_cfgpreds(n) == 1) &&
354 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
355 (get_opt_control_flow_straightening())) {
356 n = get_nodes_Block(get_Block_cfgpred(n, 0)); DBG_OPT_STG;
358 } else if ((get_Block_n_cfgpreds(n) == 2) &&
359 (get_opt_control_flow_weak_simplification())) {
360 /* Test whether Cond jumps twice to this block
361 @@@ we could do this also with two loops finding two preds from several ones. */
362 a = get_Block_cfgpred(n, 0);
363 b = get_Block_cfgpred(n, 1);
364 if ((get_irn_op(a) == op_Proj) &&
365 (get_irn_op(b) == op_Proj) &&
366 (get_Proj_pred(a) == get_Proj_pred(b)) &&
367 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
368 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
369 /* Also a single entry Block following a single exit Block. Phis have
370 twice the same operand and will be optimized away. */
371 n = get_nodes_Block(a); DBG_OPT_IFSIM;
373 } else if (get_opt_unreachable_code() &&
374 (n != current_ir_graph->start_block) &&
375 (n != current_ir_graph->end_block) ) {
377 /* If all inputs are dead, this block is dead too, except if it is
378 the start or end block. This is a step of unreachable code
380 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
381 if (!is_Bad(get_Block_cfgpred(n, i))) break;
383 if (i == get_Block_n_cfgpreds(n))
389 case iro_Jmp: /* GL: Why not same for op_Raise?? */
390 /* unreachable code elimination */
391 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
393 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
394 See cases for iro_Cond and iro_Proj in transform_node. */
395 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
396 case iro_Or: if (a == b) {n = a; break;}
401 /* After running compute_node there is only one constant predecessor.
402 Find this predecessors value and remember the other node: */
403 if ((tv = computed_value (a)) != tarval_bad) {
405 } else if ((tv = computed_value (b)) != tarval_bad) {
409 /* If this predecessors constant value is zero, the operation is
410 unnecessary. Remove it: */
411 if (tarval_classify (tv) == TV_CLASSIFY_NULL) {
412 n = on; DBG_OPT_ALGSIM1;
420 /* these operations are not commutative. Test only one predecessor. */
421 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_NULL) {
422 n = a; DBG_OPT_ALGSIM1;
423 /* Test if b > #bits of a ==> return 0 / divide b by #bits
424 --> transform node? */
427 case iro_Not: /* NotNot x == x */
428 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
429 out of bounds exception if min =! max? */
430 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
431 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
435 /* Mul is commutative and has again an other neutral element. */
436 if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ONE) {
437 n = b; DBG_OPT_ALGSIM1;
438 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) {
439 n = a; DBG_OPT_ALGSIM1;
443 /* Div is not commutative. */
444 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
445 /* Turn Div into a tuple (mem, bad, a) */
446 ir_node *mem = get_Div_mem(n);
447 turn_into_tuple(n, 3);
448 set_Tuple_pred(n, 0, mem);
449 set_Tuple_pred(n, 1, new_Bad());
450 set_Tuple_pred(n, 2, a);
454 case iro_Mod, Quot, DivMod
455 DivMod allocates new nodes --> it's treated in transform node.
456 What about Quot, DivMod?
460 n = a; /* And has it's own neutral element */
461 } else if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ALL_ONE) {
463 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ALL_ONE) {
466 if (n != oldn) DBG_OPT_ALGSIM1;
470 ir_mode *n_mode = get_irn_mode(n);
471 ir_mode *a_mode = get_irn_mode(a);
473 if (n_mode == a_mode) { /* No Conv necessary */
474 n = a; DBG_OPT_ALGSIM3;
475 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
479 n_mode = get_irn_mode(n);
480 b_mode = get_irn_mode(b);
482 if (n_mode == b_mode) {
483 if (n_mode == mode_b) {
484 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM1;
486 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
487 if (smaller_mode(b_mode, a_mode)){
488 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ DBG_OPT_ALGSIM1;
497 /* Several optimizations:
498 - no Phi in start block.
499 - remove Id operators that are inputs to Phi
500 - fold Phi-nodes, iff they have only one predecessor except
505 ir_node *block = NULL; /* to shutup gcc */
506 ir_node *first_val = NULL; /* to shutup gcc */
507 ir_node *scnd_val = NULL; /* to shutup gcc */
509 if (!get_opt_normalize()) return n;
511 n_preds = get_Phi_n_preds(n);
513 block = get_nodes_Block(n);
514 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
515 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
516 if ((is_Bad(block)) || /* Control dead */
517 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
518 return new_Bad(); /* in the Start Block. */
520 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
523 /* first we test for a special case: */
524 /* Confirm is a special node fixing additional information for a
525 value that is known at a certain point. This is useful for
526 dataflow analysis. */
528 ir_node *a = follow_Id (get_Phi_pred(n, 0));
529 ir_node *b = follow_Id (get_Phi_pred(n, 1));
530 if ( (get_irn_op(a) == op_Confirm)
531 && (get_irn_op(b) == op_Confirm)
532 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
533 && (get_irn_n(a, 1) == get_irn_n (b, 1))
534 && (a->data.num == (~b->data.num & irpn_True) )) {
535 n = follow_Id (get_irn_n(a, 0));
541 /* Find first non-self-referencing input */
542 for (i = 0; i < n_preds; ++i) {
543 first_val = follow_Id(get_Phi_pred(n, i));
545 set_Phi_pred(n, i, first_val);
546 if ( (first_val != n) /* not self pointer */
547 && (get_irn_op(first_val) != op_Bad) /* value not dead */
548 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
549 break; /* then found first value. */
553 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
554 if (i >= n_preds) { n = new_Bad(); break; }
558 /* follow_Id () for rest of inputs, determine if any of these
559 are non-self-referencing */
560 while (++i < n_preds) {
561 scnd_val = follow_Id(get_Phi_pred(n, i));
563 set_Phi_pred(n, i, scnd_val);
565 && (scnd_val != first_val)
566 && (get_irn_op(scnd_val) != op_Bad)
567 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
572 /* Fold, if no multiple distinct non-self-referencing inputs */
574 n = first_val; DBG_OPT_PHI;
576 /* skip the remaining Ids. */
577 while (++i < n_preds) {
578 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
586 #if 0 /* Is an illegal transformation: different nodes can
587 represent the same pointer value!! */
588 a = skip_Proj(get_Load_mem(n));
591 if (get_irn_op(a) == op_Store) {
592 if ( different_identity (b, get_Store_ptr(a))) {
593 /* load and store use different pointers, therefore load
594 needs not take store's memory but the state before. */
595 set_Load_mem (n, get_Store_mem(a));
596 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
603 /* remove unnecessary store. */
605 a = skip_Proj(get_Store_mem(n));
606 b = get_Store_ptr(n);
607 c = skip_Proj(get_Store_value(n));
609 if (get_irn_op(a) == op_Store
610 && get_Store_ptr(a) == b
611 && skip_Proj(get_Store_value(a)) == c) {
612 /* We have twice exactly the same store -- a write after write. */
614 } else if (get_irn_op(c) == op_Load
615 && (a == c || skip_Proj(get_Load_mem(c)) == a)
616 && get_Load_ptr(c) == b ) {
617 /* We just loaded the value from the same memory, i.e., the store
618 doesn't change the memory -- a write after read. */
619 a = get_Store_mem(n);
620 turn_into_tuple(n, 2);
621 set_Tuple_pred(n, 0, a);
622 set_Tuple_pred(n, 1, new_Bad()); DBG_OPT_WAR;
629 a = get_Proj_pred(n);
631 if ( get_irn_op(a) == op_Tuple) {
632 /* Remove the Tuple/Proj combination. */
633 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
634 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
636 assert(0); /* This should not happen! */
639 } else if (get_irn_mode(n) == mode_X &&
640 is_Bad(get_nodes_Block(n))) {
641 /* Remove dead control flow -- early gigo. */
648 n = follow_Id (n); DBG_OPT_ID;
655 } /* end equivalent_node() */
658 * Do node specific optimizations of nodes predecessors.
661 optimize_preds(ir_node *n) {
662 ir_node *a = NULL, *b = NULL;
664 /* get the operands we will work on for simple cases. */
666 a = get_binop_left(n);
667 b = get_binop_right(n);
668 } else if (is_unop(n)) {
672 switch (get_irn_opcode(n)) {
675 /* We don't want Cast as input to Cmp. */
676 if (get_irn_op(a) == op_Cast) {
680 if (get_irn_op(b) == op_Cast) {
692 * Tries several [inplace] [optimizing] transformations and returns an
693 * equivalent node. The difference to equivalent_node() is that these
694 * transformations _do_ generate new nodes, and thus the old node must
695 * not be freed even if the equivalent node isn't the old one.
698 transform_node (ir_node *n) {
699 ir_node *a = NULL, *b;
702 switch (get_irn_opcode(n)) {
704 ta = computed_value(n);
705 if (ta != tarval_bad) {
706 /* Turn Div into a tuple (mem, bad, value) */
707 ir_node *mem = get_Div_mem(n);
708 turn_into_tuple(n, 3);
709 set_Tuple_pred(n, 0, mem);
710 set_Tuple_pred(n, 1, new_Bad());
711 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
715 ta = computed_value(n);
716 if (ta != tarval_bad) {
717 /* Turn Mod into a tuple (mem, bad, value) */
718 ir_node *mem = get_Mod_mem(n);
719 turn_into_tuple(n, 3);
720 set_Tuple_pred(n, 0, mem);
721 set_Tuple_pred(n, 1, new_Bad());
722 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
730 a = get_DivMod_left(n);
731 b = get_DivMod_right(n);
732 mode = get_irn_mode(a);
734 if (!(mode_is_int(get_irn_mode(a)) &&
735 mode_is_int(get_irn_mode(b))))
739 a = new_Const (mode, get_mode_one(mode));
740 b = new_Const (mode, get_mode_null(mode));
746 if (tb != tarval_bad) {
747 if (tb == get_mode_one(get_tarval_mode(tb))) {
748 b = new_Const (mode, get_mode_null(mode));
750 } else if (ta != tarval_bad) {
752 resa = tarval_div (ta, tb);
753 if (resa == tarval_bad) break; /* Causes exception!!! Model by replacing through
754 Jmp for X result!? */
755 resb = tarval_mod (ta, tb);
756 if (resb == tarval_bad) break; /* Causes exception! */
757 a = new_Const (mode, resa);
758 b = new_Const (mode, resb);
761 } else if (ta == get_mode_null(get_tarval_mode(ta))) {
766 if (evaluated) { /* replace by tuple */
767 ir_node *mem = get_DivMod_mem(n);
768 turn_into_tuple(n, 4);
769 set_Tuple_pred(n, 0, mem);
770 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
771 set_Tuple_pred(n, 2, a);
772 set_Tuple_pred(n, 3, b);
773 assert(get_nodes_Block(n));
779 /* Replace the Cond by a Jmp if it branches on a constant
782 a = get_Cond_selector(n);
785 if ((ta != tarval_bad) &&
786 (get_irn_mode(a) == mode_b) &&
787 (get_opt_unreachable_code())) {
788 /* It's a boolean Cond, branching on a boolean constant.
789 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
790 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
791 turn_into_tuple(n, 2);
792 if (ta == tarval_b_true) {
793 set_Tuple_pred(n, 0, new_Bad());
794 set_Tuple_pred(n, 1, jmp);
796 set_Tuple_pred(n, 0, jmp);
797 set_Tuple_pred(n, 1, new_Bad());
799 /* We might generate an endless loop, so keep it alive. */
800 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
801 } else if ((ta != tarval_bad) &&
802 (get_irn_mode(a) == mode_Iu) &&
803 (get_Cond_kind(n) == dense) &&
804 (get_opt_unreachable_code())) {
805 /* I don't want to allow Tuples smaller than the biggest Proj.
806 Also this tuple might get really big...
807 I generate the Jmp here, and remember it in link. Link is used
808 when optimizing Proj. */
809 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
810 /* We might generate an endless loop, so keep it alive. */
811 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
812 } else if ((get_irn_op(a) == op_Eor)
813 && (get_irn_mode(a) == mode_b)
814 && (tarval_classify(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
815 /* The Eor is a negate. Generate a new Cond without the negate,
816 simulate the negate by exchanging the results. */
817 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
819 } else if ((get_irn_op(a) == op_Not)
820 && (get_irn_mode(a) == mode_b)) {
821 /* A Not before the Cond. Generate a new Cond without the Not,
822 simulate the Not by exchanging the results. */
823 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
830 a = get_Proj_pred(n);
832 if ((get_irn_op(a) == op_Cond)
834 && get_irn_op(get_irn_link(a)) == op_Cond) {
835 /* Use the better Cond if the Proj projs from a Cond which get's
836 its result from an Eor/Not. */
837 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
838 || (get_irn_op(get_Cond_selector(a)) == op_Not))
839 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
840 && (get_irn_op(get_irn_link(a)) == op_Cond)
841 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
842 set_Proj_pred(n, get_irn_link(a));
843 if (get_Proj_proj(n) == 0)
847 } else if ((get_irn_op(a) == op_Cond)
848 && (get_irn_mode(get_Cond_selector(a)) == mode_Iu)
850 && (get_Cond_kind(a) == dense)
851 && (get_opt_unreachable_code())) {
852 /* The Cond is a Switch on a Constant */
853 if (get_Proj_proj(n) == tarval_to_long(value_of(a))) {
854 /* The always taken branch, reuse the existing Jmp. */
855 if (!get_irn_link(a)) /* well, if it exists ;-> */
856 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
857 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
859 } else {/* Not taken control flow, but be careful with the default! */
860 if (get_Proj_proj(n) < a->attr.c.default_proj){
861 /* a never taken branch */
864 a->attr.c.default_proj = get_Proj_proj(n);
869 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
871 b = get_Eor_right(n);
873 if ((get_irn_mode(n) == mode_b)
874 && (get_irn_op(a) == op_Proj)
875 && (get_irn_mode(a) == mode_b)
876 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE)
877 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
878 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
879 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
880 mode_b, get_negated_pnc(get_Proj_proj(a)));
881 else if ((get_irn_mode(n) == mode_b)
882 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE))
883 /* The Eor is a Not. Replace it by a Not. */
884 /* ????!!!Extend to bitfield 1111111. */
885 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
891 if ( (get_irn_mode(n) == mode_b)
892 && (get_irn_op(a) == op_Proj)
893 && (get_irn_mode(a) == mode_b)
894 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
895 /* We negate a Cmp. The Cmp has the negated result anyways! */
896 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
897 mode_b, get_negated_pnc(get_Proj_proj(a)));
905 /* **************** Common Subexpression Elimination **************** */
907 /** The size of the hash table used, should estimate the number of nodes
909 #define N_IR_NODES 512
912 * Compare function for two nodes in the hash table. Gets two
913 * nodes as parameters. Returns 0 if the nodes are a cse.
916 vt_cmp (const void *elt, const void *key)
924 if (a == b) return 0;
926 if ((get_irn_op(a) != get_irn_op(b)) ||
927 (get_irn_mode(a) != get_irn_mode(b))) return 1;
929 /* compare if a's in and b's in are equal */
930 irn_arity_a = get_irn_arity (a);
931 if (irn_arity_a != get_irn_arity(b))
934 /* for block-local cse and pinned nodes: */
935 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
936 if (get_irn_n(a, -1) != get_irn_n(b, -1))
940 /* compare a->in[0..ins] with b->in[0..ins] */
941 for (i = 0; i < irn_arity_a; i++)
942 if (get_irn_n(a, i) != get_irn_n(b, i))
945 switch (get_irn_opcode(a)) {
947 return (get_Const_tarval(a) != get_Const_tarval(b))
948 || (get_Const_type(a) != get_Const_type(b));
950 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
952 return get_Filter_proj(a) != get_Filter_proj(b);
954 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
955 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
957 return (get_irn_free_attr(a) != get_irn_free_attr(b));
959 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
960 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
962 return (get_irn_call_attr(a) != get_irn_call_attr(b));
964 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
965 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
966 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
967 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
968 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
970 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
972 return get_Cast_type(a) != get_Cast_type(b);
980 * Calculate a hash value of a node.
983 ir_node_hash (ir_node *node)
988 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
989 h = irn_arity = get_irn_arity(node);
991 /* consider all in nodes... except the block. */
992 for (i = 0; i < irn_arity; i++) {
993 h = 9*h + (unsigned long)get_irn_n(node, i);
997 h = 9*h + (unsigned long) get_irn_mode (node);
999 h = 9*h + (unsigned long) get_irn_op (node);
1005 new_identities (void)
1007 return new_pset (vt_cmp, N_IR_NODES);
1011 del_identities (pset *value_table)
1013 del_pset (value_table);
1017 * Return the canonical node computing the same value as n.
1018 * Looks up the node in a hash table.
1020 static INLINE ir_node *
1021 identify (pset *value_table, ir_node *n)
1025 if (!value_table) return n;
1027 /* TODO: use a generic commutative attribute */
1028 if (get_opt_reassociation()) {
1029 if (is_op_commutative(get_irn_op(n))) {
1030 /* for commutative operators perform a OP b == b OP a */
1031 if (get_binop_left(n) > get_binop_right(n)) {
1032 ir_node *h = get_binop_left(n);
1033 set_binop_left(n, get_binop_right(n));
1034 set_binop_right(n, h);
1039 o = pset_find (value_table, n, ir_node_hash (n));
1046 * During construction we set the pinned flag in the graph right when the
1047 * optimizatin is performed. The flag turning on procedure global cse could
1048 * be changed between two allocations. This way we are safe.
1050 static INLINE ir_node *
1051 identify_cons (pset *value_table, ir_node *n) {
1053 n = identify(value_table, n);
1054 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1055 set_irg_pinned(current_ir_graph, floats);
1060 * Return the canonical node computing the same value as n.
1061 * Looks up the node in a hash table, enters it in the table
1062 * if it isn't there yet.
1065 identify_remember (pset *value_table, ir_node *node)
1069 if (!value_table) return node;
1071 /* lookup or insert in hash table with given hash key. */
1072 o = pset_insert (value_table, node, ir_node_hash (node));
1074 if (o == node) return node;
1080 add_identities (pset *value_table, ir_node *node) {
1081 identify_remember (value_table, node);
1085 * garbage in, garbage out. If a node has a dead input, i.e., the
1086 * Bad node is input to the node, return the Bad node.
1088 static INLINE ir_node *
1089 gigo (ir_node *node)
1092 ir_op* op = get_irn_op(node);
1094 /* remove garbage blocks by looking at control flow that leaves the block
1095 and replacing the control flow by Bad. */
1096 if (get_irn_mode(node) == mode_X) {
1097 ir_node *block = get_nodes_block(node);
1098 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1099 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1100 irn_arity = get_irn_arity(block);
1101 for (i = 0; i < irn_arity; i++) {
1102 if (!is_Bad(get_irn_n(block, i))) break;
1104 if (i == irn_arity) return new_Bad();
1108 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1109 blocks predecessors is dead. */
1110 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1111 irn_arity = get_irn_arity(node);
1112 for (i = -1; i < irn_arity; i++) {
1113 if (is_Bad(get_irn_n(node, i))) {
1119 /* With this code we violate the agreement that local_optimize
1120 only leaves Bads in Block, Phi and Tuple nodes. */
1121 /* If Block has only Bads as predecessors it's garbage. */
1122 /* If Phi has only Bads as predecessors it's garbage. */
1123 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1124 irn_arity = get_irn_arity(node);
1125 for (i = 0; i < irn_arity; i++) {
1126 if (!is_Bad(get_irn_n(node, i))) break;
1128 if (i == irn_arity) node = new_Bad();
1136 * These optimizations deallocate nodes from the obstack.
1137 * It can only be called if it is guaranteed that no other nodes
1138 * reference this one, i.e., right after construction of a node.
1141 optimize_node (ir_node *n)
1145 opcode iro = get_irn_opcode(n);
1147 /* Allways optimize Phi nodes: part of the construction. */
1148 if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
1150 /* constant expression evaluation / constant folding */
1151 if (get_opt_constant_folding()) {
1152 /* constants can not be evaluated */
1153 if (get_irn_op(n) != op_Const) {
1154 /* try to evaluate */
1155 tv = computed_value (n);
1156 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1157 /* evaluation was succesful -- replace the node. */
1158 obstack_free (current_ir_graph->obst, n);
1159 return new_Const (get_tarval_mode (tv), tv);
1164 /* remove unnecessary nodes */
1165 if (get_opt_constant_folding() ||
1166 (iro == iro_Phi) || /* always optimize these nodes. */
1168 (iro == iro_Proj) ||
1169 (iro == iro_Block) ) /* Flags tested local. */
1170 n = equivalent_node (n);
1172 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1174 /** common subexpression elimination **/
1175 /* Checks whether n is already available. */
1176 /* The block input is used to distinguish different subexpressions. Right
1177 now all nodes are pinned to blocks, i.e., the cse only finds common
1178 subexpressions within a block. */
1180 n = identify_cons (current_ir_graph->value_table, n);
1183 /* We found an existing, better node, so we can deallocate the old node. */
1184 obstack_free (current_ir_graph->obst, old_n);
1187 /* Some more constant expression evaluation that does not allow to
1189 iro = get_irn_opcode(n);
1190 if (get_opt_constant_folding() ||
1191 (iro == iro_Cond) ||
1192 (iro == iro_Proj)) /* Flags tested local. */
1193 n = transform_node (n);
1195 /* Remove nodes with dead (Bad) input.
1196 Run always for transformation induced Bads. */
1199 /* Now we have a legal, useful node. Enter it in hash table for cse */
1200 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1201 n = identify_remember (current_ir_graph->value_table, n);
1209 * These optimizations never deallocate nodes. This can cause dead
1210 * nodes lying on the obstack. Remove these by a dead node elimination,
1211 * i.e., a copying garbage collection.
1214 optimize_in_place_2 (ir_node *n)
1218 opcode iro = get_irn_opcode(n);
1220 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1222 /* if not optimize return n */
1225 /* Here this is possible. Why? */
1230 /* constant expression evaluation / constant folding */
1231 if (get_opt_constant_folding()) {
1232 /* constants can not be evaluated */
1233 if (iro != iro_Const) {
1234 /* try to evaluate */
1235 tv = computed_value (n);
1236 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1237 /* evaluation was succesful -- replace the node. */
1238 n = new_Const (get_tarval_mode (tv), tv);
1239 __dbg_info_merge_pair(n, old_n, dbg_const_eval);
1245 /* remove unnecessary nodes */
1246 /*if (get_opt_constant_folding()) */
1247 if (get_opt_constant_folding() ||
1248 (iro == iro_Phi) || /* always optimize these nodes. */
1249 (iro == iro_Id) || /* ... */
1250 (iro == iro_Proj) || /* ... */
1251 (iro == iro_Block) ) /* Flags tested local. */
1252 n = equivalent_node (n);
1254 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1256 /** common subexpression elimination **/
1257 /* Checks whether n is already available. */
1258 /* The block input is used to distinguish different subexpressions. Right
1259 now all nodes are pinned to blocks, i.e., the cse only finds common
1260 subexpressions within a block. */
1261 if (get_opt_cse()) {
1262 n = identify (current_ir_graph->value_table, n);
1265 /* Some more constant expression evaluation. */
1266 iro = get_irn_opcode(n);
1267 if (get_opt_constant_folding() ||
1268 (iro == iro_Cond) ||
1269 (iro == iro_Proj)) /* Flags tested local. */
1270 n = transform_node (n);
1272 /* Remove nodes with dead (Bad) input.
1273 Run always for transformation induced Bads. */
1276 /* Now we can verify the node, as it has no dead inputs any more. */
1279 /* Now we have a legal, useful node. Enter it in hash table for cse.
1280 Blocks should be unique anyways. (Except the successor of start:
1281 is cse with the start block!) */
1282 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1283 n = identify_remember (current_ir_graph->value_table, n);
1289 * Wrapper for external use, set proper status bits after optimization.
1292 optimize_in_place (ir_node *n)
1294 /* Handle graph state */
1295 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1297 if (get_opt_global_cse())
1298 set_irg_pinned(current_ir_graph, floats);
1299 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1300 set_irg_outs_inconsistent(current_ir_graph);
1301 /* Maybe we could also test whether optimizing the node can
1302 change the control graph. */
1303 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1304 set_irg_dom_inconsistent(current_ir_graph);
1305 return optimize_in_place_2 (n);