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"
31 /* Trivial INLINEable routine for copy propagation.
32 Does follow Ids, needed to optimize INLINEd code. */
33 static INLINE ir_node *
34 follow_Id (ir_node *n)
36 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
40 static INLINE tarval *
43 if ((n != NULL) && (get_irn_op(n) == op_Const))
44 return get_Const_tarval(n); /* might return tarval_bad */
49 /* if n can be computed, return the value, else tarval_bad. Performs
50 constant folding. GL: Only if n is arithmetic operator? */
52 computed_value (ir_node *n)
56 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
57 /* initialized to uniformly filter invalid constants */
58 tarval *ta = tarval_bad, *tb = tarval_bad;
62 /* get the operands we will work on for simple cases. */
64 a = get_binop_left(n);
65 b = get_binop_right(n);
66 } else if (is_unop(n)) {
70 /* if the operands are constants, get the target value, else set it NULL.
71 (a and b may be NULL if we treat a node that is no computation.) */
75 /* Perform the constant evaluation / computation. */
76 switch (get_irn_opcode(n)) {
78 res = get_Const_tarval(n);
81 if ((get_SymConst_kind(n) == size) &&
82 (get_type_state(get_SymConst_type(n))) == layout_fixed)
83 res = new_tarval_from_long (get_type_size(get_SymConst_type(n)), mode_Is);
86 if ((ta != tarval_bad) && (tb != tarval_bad)
87 && (get_irn_mode(a) == get_irn_mode(b))
88 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
89 res = tarval_add (ta, tb);
93 if ((ta != tarval_bad) && (tb != tarval_bad)
94 && (get_irn_mode(a) == get_irn_mode(b))
95 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
96 res = tarval_sub (ta, tb);
100 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
101 res = tarval_neg (ta);
104 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
105 res = tarval_mul (ta, tb);
107 /* a*0 = 0 or 0*b = 0:
108 calls computed_value recursive and returns the 0 with proper
111 if ( ( ((v = computed_value (a)) != tarval_bad)
112 && (v == get_mode_null(get_tarval_mode(v))) )
113 || ( ((v = computed_value (b)) != tarval_bad)
114 && (v == get_mode_null(get_tarval_mode(v))) )) {
120 /* This was missing in original implementation. Why? */
121 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
122 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
123 res = tarval_quo(ta, tb);
127 /* This was missing in original implementation. Why? */
128 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
129 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
130 res = tarval_div(ta, tb);
134 /* This was missing in original implementation. Why? */
135 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
136 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
137 res = tarval_mod(ta, tb);
140 /* for iro_DivMod see iro_Proj */
142 if (ta != tarval_bad)
143 res = tarval_abs (ta);
146 if ((ta != tarval_bad) && (tb != tarval_bad)) {
147 res = tarval_and (ta, tb);
150 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_NULL)
151 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
157 if ((ta != tarval_bad) && (tb != tarval_bad)) {
158 res = tarval_or (ta, tb);
161 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
162 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
168 if ((ta != tarval_bad) && (tb != tarval_bad)) {
169 res = tarval_eor (ta, tb);
173 if ((ta != tarval_bad)) {
174 res = tarval_not (ta);
178 if ((ta != tarval_bad) && (tb != tarval_bad)) {
179 res = tarval_shl (ta, tb);
183 if ((ta != tarval_bad) && (tb != tarval_bad)) {
184 res = tarval_shr (ta, tb);
188 if ((ta != tarval_bad) && (tb != tarval_bad)) {
189 res = tarval_shrs (ta, tb);
193 if ((ta != tarval_bad) && (tb != tarval_bad)) {
194 /*res = tarval_rot (ta, tb)*/;
198 if (ta != tarval_bad) {
199 res = tarval_convert_to (ta, get_irn_mode (n));
202 case iro_Proj: /* iro_Cmp */
206 a = get_Proj_pred(n);
207 /* Optimize Cmp nodes.
208 This performs a first step of unreachable code elimination.
209 Proj can not be computed, but folding a Cmp above the Proj here is
210 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
212 There are several case where we can evaluate a Cmp node:
213 1. The nodes compared are both the same. If we compare for
214 equal, greater equal, ... this will return true, else it
215 will return false. This step relies on cse.
216 2. The predecessors of Cmp are target values. We can evaluate
218 3. The predecessors are Allocs or void* constants. Allocs never
219 return NULL, they raise an exception. Therefore we can predict
221 if (get_irn_op(a) == op_Cmp) {
222 aa = get_Cmp_left(a);
223 ab = get_Cmp_right(a);
224 if (aa == ab) { /* 1.: */
225 /* This is a tric with the bits used for encoding the Cmp
226 Proj numbers, the following statement is not the same:
227 res = new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
228 res = new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
230 tarval *taa = computed_value (aa);
231 tarval *tab = computed_value (ab);
232 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
233 /* strange checks... */
234 pnc_number flags = tarval_cmp (taa, tab);
235 if (flags != False) {
236 res = new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
238 } else { /* check for 3.: */
239 ir_node *aaa = skip_nop(skip_Proj(aa));
240 ir_node *aba = skip_nop(skip_Proj(ab));
241 if ( ( (/* aa is ProjP and aaa is Alloc */
242 (get_irn_op(aa) == op_Proj)
243 && (mode_is_reference(get_irn_mode(aa)))
244 && (get_irn_op(aaa) == op_Alloc))
245 && ( (/* ab is constant void */
246 (get_irn_op(ab) == op_Const)
247 && (mode_is_reference(get_irn_mode(ab)))
248 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
249 || (/* ab is other Alloc */
250 (get_irn_op(ab) == op_Proj)
251 && (mode_is_reference(get_irn_mode(ab)))
252 && (get_irn_op(aba) == op_Alloc)
254 || (/* aa is void and aba is Alloc */
255 (get_irn_op(aa) == op_Const)
256 && (mode_is_reference(get_irn_mode(aa)))
257 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
258 && (get_irn_op(ab) == op_Proj)
259 && (mode_is_reference(get_irn_mode(ab)))
260 && (get_irn_op(aba) == op_Alloc)))
262 res = new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
265 } else if (get_irn_op(a) == op_DivMod) {
266 ta = value_of(get_DivMod_left(a));
267 tb = value_of(get_DivMod_right(a));
268 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
269 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
270 if (get_Proj_proj(n)== 0) /* Div */
271 res = tarval_div(ta, tb);
273 res = tarval_mod(ta, tb);
286 /* returns 1 if the a and b are pointers to different locations. */
288 different_identity (ir_node *a, ir_node *b)
290 assert (mode_is_reference(get_irn_mode (a))
291 && mode_is_reference(get_irn_mode (b)));
293 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
294 ir_node *a1 = get_Proj_pred (a);
295 ir_node *b1 = get_Proj_pred (b);
296 if (a1 != b1 && get_irn_op (a1) == op_Alloc
297 && get_irn_op (b1) == op_Alloc)
304 /* equivalent_node returns a node equivalent to N. It skips all nodes that
305 perform no actual computation, as, e.g., the Id nodes. It does not create
306 new nodes. It is therefore safe to free N if the node returned is not N.
307 If a node returns a Tuple we can not just skip it. If the size of the
308 in array fits, we transform n into a tuple (e.g., Div). */
310 equivalent_node (ir_node *n)
313 ir_node *a = NULL; /* to shutup gcc */
314 ir_node *b = NULL; /* to shutup gcc */
315 ir_node *c = NULL; /* to shutup gcc */
318 ins = get_irn_arity (n);
320 /* get the operands we will work on */
322 a = get_binop_left(n);
323 b = get_binop_right(n);
324 } else if (is_unop(n)) {
328 /* skip unnecessary nodes. */
329 switch (get_irn_opcode (n)) {
332 /* The Block constructor does not call optimize, but mature_block
333 calls the optimization. */
334 assert(get_Block_matured(n));
336 /* Straightening: a single entry Block following a single exit Block
337 can be merged, if it is not the Start block. */
338 /* !!! Beware, all Phi-nodes of n must have been optimized away.
339 This should be true, as the block is matured before optimize is called.
340 But what about Phi-cycles with the Phi0/Id that could not be resolved?
341 Remaining Phi nodes are just Ids. */
342 if ((get_Block_n_cfgpreds(n) == 1) &&
343 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
344 (get_opt_control_flow_straightening())) {
345 n = get_nodes_Block(get_Block_cfgpred(n, 0)); DBG_OPT_STG;
347 } else if ((get_Block_n_cfgpreds(n) == 2) &&
348 (get_opt_control_flow_weak_simplification())) {
349 /* Test whether Cond jumps twice to this block
350 @@@ we could do this also with two loops finding two preds from several ones. */
351 a = get_Block_cfgpred(n, 0);
352 b = get_Block_cfgpred(n, 1);
353 if ((get_irn_op(a) == op_Proj) &&
354 (get_irn_op(b) == op_Proj) &&
355 (get_Proj_pred(a) == get_Proj_pred(b)) &&
356 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
357 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
358 /* Also a single entry Block following a single exit Block. Phis have
359 twice the same operand and will be optimized away. */
360 n = get_nodes_Block(a); DBG_OPT_IFSIM;
362 } else if (get_opt_unreachable_code() &&
363 (n != current_ir_graph->start_block) &&
364 (n != current_ir_graph->end_block) ) {
366 /* If all inputs are dead, this block is dead too, except if it is
367 the start or end block. This is a step of unreachable code
369 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
370 if (!is_Bad(get_Block_cfgpred(n, i))) break;
372 if (i == get_Block_n_cfgpreds(n))
378 case iro_Jmp: /* GL: Why not same for op_Raise?? */
379 /* unreachable code elimination */
380 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
382 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
383 See cases for iro_Cond and iro_Proj in transform_node. */
384 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
385 case iro_Or: if (a == b) {n = a; break;}
390 /* After running compute_node there is only one constant predecessor.
391 Find this predecessors value and remember the other node: */
392 if ((tv = computed_value (a)) != tarval_bad) {
394 } else if ((tv = computed_value (b)) != tarval_bad) {
398 /* If this predecessors constant value is zero, the operation is
399 unnecessary. Remove it: */
400 if (tarval_classify (tv) == TV_CLASSIFY_NULL) {
401 n = on; DBG_OPT_ALGSIM1;
409 /* these operations are not commutative. Test only one predecessor. */
410 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_NULL) {
411 n = a; DBG_OPT_ALGSIM1;
412 /* Test if b > #bits of a ==> return 0 / divide b by #bits
413 --> transform node? */
416 case iro_Not: /* NotNot x == x */
417 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
418 out of bounds exception if min =! max? */
419 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
420 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
424 /* Mul is commutative and has again an other neutral element. */
425 if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ONE) {
426 n = b; DBG_OPT_ALGSIM1;
427 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) {
428 n = a; DBG_OPT_ALGSIM1;
432 /* Div is not commutative. */
433 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
434 /* Turn Div into a tuple (mem, bad, a) */
435 ir_node *mem = get_Div_mem(n);
436 turn_into_tuple(n, 3);
437 set_Tuple_pred(n, 0, mem);
438 set_Tuple_pred(n, 1, new_Bad());
439 set_Tuple_pred(n, 2, a);
443 case iro_Mod, Quot, DivMod
444 DivMod allocates new nodes --> it's treated in transform node.
445 What about Quot, DivMod?
449 n = a; /* And has it's own neutral element */
450 } else if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ALL_ONE) {
452 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ALL_ONE) {
455 if (n != oldn) DBG_OPT_ALGSIM1;
459 ir_mode *n_mode = get_irn_mode(n);
460 ir_mode *a_mode = get_irn_mode(a);
462 if (n_mode == a_mode) { /* No Conv necessary */
463 n = a; DBG_OPT_ALGSIM3;
464 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
468 n_mode = get_irn_mode(n);
469 b_mode = get_irn_mode(b);
471 if (n_mode == b_mode) {
472 if (n_mode == mode_b) {
473 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM1;
475 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
476 if (smaller_mode(b_mode, a_mode)){
477 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ DBG_OPT_ALGSIM1;
486 /* Several optimizations:
487 - no Phi in start block.
488 - remove Id operators that are inputs to Phi
489 - fold Phi-nodes, iff they have only one predecessor except
494 ir_node *block = NULL; /* to shutup gcc */
495 ir_node *first_val = NULL; /* to shutup gcc */
496 ir_node *scnd_val = NULL; /* to shutup gcc */
498 if (!get_opt_normalize()) return n;
500 n_preds = get_Phi_n_preds(n);
502 block = get_nodes_Block(n);
503 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
504 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
505 if ((is_Bad(block)) || /* Control dead */
506 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
507 return new_Bad(); /* in the Start Block. */
509 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
512 /* first we test for a special case: */
513 /* Confirm is a special node fixing additional information for a
514 value that is known at a certain point. This is useful for
515 dataflow analysis. */
517 ir_node *a = follow_Id (get_Phi_pred(n, 0));
518 ir_node *b = follow_Id (get_Phi_pred(n, 1));
519 if ( (get_irn_op(a) == op_Confirm)
520 && (get_irn_op(b) == op_Confirm)
521 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
522 && (get_irn_n(a, 1) == get_irn_n (b, 1))
523 && (a->data.num == (~b->data.num & irpn_True) )) {
524 n = follow_Id (get_irn_n(a, 0));
530 /* Find first non-self-referencing input */
531 for (i = 0; i < n_preds; ++i) {
532 first_val = follow_Id(get_Phi_pred(n, i));
534 set_Phi_pred(n, i, first_val);
535 if ( (first_val != n) /* not self pointer */
536 && (get_irn_op(first_val) != op_Bad) /* value not dead */
537 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
538 break; /* then found first value. */
542 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
543 if (i >= n_preds) { n = new_Bad(); break; }
547 /* follow_Id () for rest of inputs, determine if any of these
548 are non-self-referencing */
549 while (++i < n_preds) {
550 scnd_val = follow_Id(get_Phi_pred(n, i));
552 set_Phi_pred(n, i, scnd_val);
554 && (scnd_val != first_val)
555 && (get_irn_op(scnd_val) != op_Bad)
556 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
561 /* Fold, if no multiple distinct non-self-referencing inputs */
563 n = first_val; DBG_OPT_PHI;
565 /* skip the remaining Ids. */
566 while (++i < n_preds) {
567 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
575 #if 0 /* Is an illegal transformation: different nodes can
576 represent the same pointer value!! */
577 a = skip_Proj(get_Load_mem(n));
580 if (get_irn_op(a) == op_Store) {
581 if ( different_identity (b, get_Store_ptr(a))) {
582 /* load and store use different pointers, therefore load
583 needs not take store's memory but the state before. */
584 set_Load_mem (n, get_Store_mem(a));
585 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
592 /* remove unnecessary store. */
594 a = skip_Proj(get_Store_mem(n));
595 b = get_Store_ptr(n);
596 c = skip_Proj(get_Store_value(n));
598 if (get_irn_op(a) == op_Store
599 && get_Store_ptr(a) == b
600 && skip_Proj(get_Store_value(a)) == c) {
601 /* We have twice exactly the same store -- a write after write. */
603 } else if (get_irn_op(c) == op_Load
604 && (a == c || skip_Proj(get_Load_mem(c)) == a)
605 && get_Load_ptr(c) == b ) {
606 /* We just loaded the value from the same memory, i.e., the store
607 doesn't change the memory -- a write after read. */
608 a = get_Store_mem(n);
609 turn_into_tuple(n, 2);
610 set_Tuple_pred(n, 0, a);
611 set_Tuple_pred(n, 1, new_Bad()); DBG_OPT_WAR;
618 a = get_Proj_pred(n);
620 if ( get_irn_op(a) == op_Tuple) {
621 /* Remove the Tuple/Proj combination. */
622 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
623 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
625 assert(0); /* This should not happen! */
628 } else if (get_irn_mode(n) == mode_X &&
629 is_Bad(get_nodes_Block(n))) {
630 /* Remove dead control flow -- early gigo. */
637 n = follow_Id (n); DBG_OPT_ID;
644 } /* end equivalent_node() */
646 /* do node specific optimizations of nodes predecessors. */
648 optimize_preds(ir_node *n) {
649 ir_node *a = NULL, *b = NULL;
651 /* get the operands we will work on for simple cases. */
653 a = get_binop_left(n);
654 b = get_binop_right(n);
655 } else if (is_unop(n)) {
659 switch (get_irn_opcode(n)) {
662 /* We don't want Cast as input to Cmp. */
663 if (get_irn_op(a) == op_Cast) {
667 if (get_irn_op(b) == op_Cast) {
678 /* tries several [inplace] [optimizing] transformations and returns an
679 equivalent node. The difference to equivalent_node is that these
680 transformations _do_ generate new nodes, and thus the old node must
681 not be freed even if the equivalent node isn't the old one. */
683 transform_node (ir_node *n) {
684 ir_node *a = NULL, *b;
687 switch (get_irn_opcode(n)) {
689 ta = computed_value(n);
690 if (ta != tarval_bad) {
691 /* Turn Div into a tuple (mem, bad, value) */
692 ir_node *mem = get_Div_mem(n);
693 turn_into_tuple(n, 3);
694 set_Tuple_pred(n, 0, mem);
695 set_Tuple_pred(n, 1, new_Bad());
696 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
700 ta = computed_value(n);
701 if (ta != tarval_bad) {
702 /* Turn Mod into a tuple (mem, bad, value) */
703 ir_node *mem = get_Mod_mem(n);
704 turn_into_tuple(n, 3);
705 set_Tuple_pred(n, 0, mem);
706 set_Tuple_pred(n, 1, new_Bad());
707 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
715 a = get_DivMod_left(n);
716 b = get_DivMod_right(n);
717 mode = get_irn_mode(a);
719 if (!(mode_is_int(get_irn_mode(a)) &&
720 mode_is_int(get_irn_mode(b))))
724 a = new_Const (mode, get_mode_one(mode));
725 b = new_Const (mode, get_mode_null(mode));
731 if (tb != tarval_bad) {
732 if (tb == get_mode_one(get_tarval_mode(tb))) {
733 b = new_Const (mode, get_mode_null(mode));
735 } else if (ta != tarval_bad) {
737 resa = tarval_div (ta, tb);
738 if (resa == tarval_bad) break; /* Causes exception!!! Model by replacing through
739 Jmp for X result!? */
740 resb = tarval_mod (ta, tb);
741 if (resb == tarval_bad) break; /* Causes exception! */
742 a = new_Const (mode, resa);
743 b = new_Const (mode, resb);
746 } else if (ta == get_mode_null(get_tarval_mode(ta))) {
751 if (evaluated) { /* replace by tuple */
752 ir_node *mem = get_DivMod_mem(n);
753 turn_into_tuple(n, 4);
754 set_Tuple_pred(n, 0, mem);
755 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
756 set_Tuple_pred(n, 2, a);
757 set_Tuple_pred(n, 3, b);
758 assert(get_nodes_Block(n));
764 /* Replace the Cond by a Jmp if it branches on a constant
767 a = get_Cond_selector(n);
770 if ((ta != tarval_bad) &&
771 (get_irn_mode(a) == mode_b) &&
772 (get_opt_unreachable_code())) {
773 /* It's a boolean Cond, branching on a boolean constant.
774 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
775 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
776 turn_into_tuple(n, 2);
777 if (ta == tarval_b_true) {
778 set_Tuple_pred(n, 0, new_Bad());
779 set_Tuple_pred(n, 1, jmp);
781 set_Tuple_pred(n, 0, jmp);
782 set_Tuple_pred(n, 1, new_Bad());
784 /* We might generate an endless loop, so keep it alive. */
785 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
786 } else if ((ta != tarval_bad) &&
787 (get_irn_mode(a) == mode_Iu) &&
788 (get_Cond_kind(n) == dense) &&
789 (get_opt_unreachable_code())) {
790 /* I don't want to allow Tuples smaller than the biggest Proj.
791 Also this tuple might get really big...
792 I generate the Jmp here, and remember it in link. Link is used
793 when optimizing Proj. */
794 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
795 /* We might generate an endless loop, so keep it alive. */
796 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
797 } else if ((get_irn_op(a) == op_Eor)
798 && (get_irn_mode(a) == mode_b)
799 && (tarval_classify(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
800 /* The Eor is a negate. Generate a new Cond without the negate,
801 simulate the negate by exchanging the results. */
802 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
804 } else if ((get_irn_op(a) == op_Not)
805 && (get_irn_mode(a) == mode_b)) {
806 /* A Not before the Cond. Generate a new Cond without the Not,
807 simulate the Not by exchanging the results. */
808 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
815 a = get_Proj_pred(n);
817 if ((get_irn_op(a) == op_Cond)
819 && get_irn_op(get_irn_link(a)) == op_Cond) {
820 /* Use the better Cond if the Proj projs from a Cond which get's
821 its result from an Eor/Not. */
822 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
823 || (get_irn_op(get_Cond_selector(a)) == op_Not))
824 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
825 && (get_irn_op(get_irn_link(a)) == op_Cond)
826 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
827 set_Proj_pred(n, get_irn_link(a));
828 if (get_Proj_proj(n) == 0)
832 } else if ((get_irn_op(a) == op_Cond)
833 && (get_irn_mode(get_Cond_selector(a)) == mode_Iu)
835 && (get_Cond_kind(a) == dense)
836 && (get_opt_unreachable_code())) {
837 /* The Cond is a Switch on a Constant */
838 if (get_Proj_proj(n) == tarval_to_long(value_of(a))) {
839 /* The always taken branch, reuse the existing Jmp. */
840 if (!get_irn_link(a)) /* well, if it exists ;-> */
841 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
842 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
844 } else {/* Not taken control flow, but be careful with the default! */
845 if (get_Proj_proj(n) < a->attr.c.default_proj){
846 /* a never taken branch */
849 a->attr.c.default_proj = get_Proj_proj(n);
854 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
856 b = get_Eor_right(n);
858 if ((get_irn_mode(n) == mode_b)
859 && (get_irn_op(a) == op_Proj)
860 && (get_irn_mode(a) == mode_b)
861 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE)
862 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
863 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
864 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
865 mode_b, get_negated_pnc(get_Proj_proj(a)));
866 else if ((get_irn_mode(n) == mode_b)
867 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE))
868 /* The Eor is a Not. Replace it by a Not. */
869 /* ????!!!Extend to bitfield 1111111. */
870 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
876 if ( (get_irn_mode(n) == mode_b)
877 && (get_irn_op(a) == op_Proj)
878 && (get_irn_mode(a) == mode_b)
879 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
880 /* We negate a Cmp. The Cmp has the negated result anyways! */
881 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
882 mode_b, get_negated_pnc(get_Proj_proj(a)));
890 /* **************** Common Subexpression Elimination **************** */
892 /** The size of the hash table used, should estimate the number of nodes
894 #define N_IR_NODES 512
896 /* Compare function for two nodes in the hash table. Gets two */
897 /* nodes as parameters. Returns 0 if the nodes are a cse. */
899 vt_cmp (const void *elt, const void *key)
907 if (a == b) return 0;
909 if ((get_irn_op(a) != get_irn_op(b)) ||
910 (get_irn_mode(a) != get_irn_mode(b))) return 1;
912 /* compare if a's in and b's in are equal */
913 irn_arity_a = get_irn_arity (a);
914 if (irn_arity_a != get_irn_arity(b))
917 /* for block-local cse and pinned nodes: */
918 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
919 if (get_irn_n(a, -1) != get_irn_n(b, -1))
923 /* compare a->in[0..ins] with b->in[0..ins] */
924 for (i = 0; i < irn_arity_a; i++)
925 if (get_irn_n(a, i) != get_irn_n(b, i))
928 switch (get_irn_opcode(a)) {
930 return (get_Const_tarval(a) != get_Const_tarval(b))
931 || (get_Const_type(a) != get_Const_type(b));
933 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
935 return get_Filter_proj(a) != get_Filter_proj(b);
937 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
938 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
940 return (get_irn_free_attr(a) != get_irn_free_attr(b));
942 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
943 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
945 return (get_irn_call_attr(a) != get_irn_call_attr(b));
947 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
948 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
949 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
950 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
951 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
953 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
955 return get_Cast_type(a) != get_Cast_type(b);
963 ir_node_hash (ir_node *node)
968 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
969 h = irn_arity = get_irn_arity(node);
971 /* consider all in nodes... except the block. */
972 for (i = 0; i < irn_arity; i++) {
973 h = 9*h + (unsigned long)get_irn_n(node, i);
977 h = 9*h + (unsigned long) get_irn_mode (node);
979 h = 9*h + (unsigned long) get_irn_op (node);
985 new_identities (void)
987 return new_pset (vt_cmp, N_IR_NODES);
991 del_identities (pset *value_table)
993 del_pset (value_table);
996 /* Return the canonical node computing the same value as n.
997 Looks up the node in a hash table. */
998 static INLINE ir_node *
999 identify (pset *value_table, ir_node *n)
1003 if (!value_table) return n;
1005 if (get_opt_reassociation()) {
1006 switch (get_irn_opcode (n)) {
1013 /* for commutative operators perform a OP b == b OP a */
1014 if (get_binop_left(n) > get_binop_right(n)) {
1015 ir_node *h = get_binop_left(n);
1016 set_binop_left(n, get_binop_right(n));
1017 set_binop_right(n, h);
1025 o = pset_find (value_table, n, ir_node_hash (n));
1031 /* During construction we set the pinned flag in the graph right when the
1032 optimizatin is performed. The flag turning on procedure global cse could
1033 be changed between two allocations. This way we are safe. */
1034 static INLINE ir_node *
1035 identify_cons (pset *value_table, ir_node *n) {
1037 n = identify(value_table, n);
1038 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1039 set_irg_pinned(current_ir_graph, floats);
1043 /* Return the canonical node computing the same value as n.
1044 Looks up the node in a hash table, enters it in the table
1045 if it isn't there yet. */
1047 identify_remember (pset *value_table, ir_node *node)
1051 if (!value_table) return node;
1053 /* lookup or insert in hash table with given hash key. */
1054 o = pset_insert (value_table, node, ir_node_hash (node));
1056 if (o == node) return node;
1062 add_identities (pset *value_table, ir_node *node) {
1063 identify_remember (value_table, node);
1066 /* garbage in, garbage out. If a node has a dead input, i.e., the
1067 Bad node is input to the node, return the Bad node. */
1068 static INLINE ir_node *
1069 gigo (ir_node *node)
1072 ir_op* op = get_irn_op(node);
1075 /* remove garbage blocks by looking at control flow that leaves the block
1076 and replacing the control flow by Bad. */
1077 if (get_irn_mode(node) == mode_X) {
1078 ir_node *block = get_nodes_block(node);
1079 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1080 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1081 irn_arity = get_irn_arity(block);
1082 for (i = 0; i < irn_arity; i++) {
1083 if (!is_Bad(get_irn_n(block, i))) break;
1085 if (i == irn_arity) return new_Bad();
1089 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1090 blocks predecessors is dead. */
1091 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1092 irn_arity = get_irn_arity(node);
1093 for (i = -1; i < irn_arity; i++) {
1094 if (is_Bad(get_irn_n(node, i))) {
1100 /* With this code we violate the agreement that local_optimize
1101 only leaves Bads in Block, Phi and Tuple nodes. */
1102 /* If Block has only Bads as predecessors it's garbage. */
1103 /* If Phi has only Bads as predecessors it's garbage. */
1104 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1105 irn_arity = get_irn_arity(node);
1106 for (i = 0; i < irn_arity; i++) {
1107 if (!is_Bad(get_irn_n(node, i))) break;
1109 if (i == irn_arity) node = new_Bad();
1116 /* These optimizations deallocate nodes from the obstack.
1117 It can only be called if it is guaranteed that no other nodes
1118 reference this one, i.e., right after construction of a node. */
1120 optimize_node (ir_node *n)
1125 /* Allways optimize Phi nodes: part of the construction. */
1126 if ((!get_opt_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1128 /* constant expression evaluation / constant folding */
1129 if (get_opt_constant_folding()) {
1130 /* constants can not be evaluated */
1131 if (get_irn_op(n) != op_Const) {
1132 /* try to evaluate */
1133 tv = computed_value (n);
1134 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1135 /* evaluation was succesful -- replace the node. */
1136 obstack_free (current_ir_graph->obst, n);
1137 return new_Const (get_tarval_mode (tv), tv);
1142 /* remove unnecessary nodes */
1143 if (get_opt_constant_folding() ||
1144 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1145 (get_irn_op(n) == op_Id) ||
1146 (get_irn_op(n) == op_Proj) ||
1147 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1148 n = equivalent_node (n);
1150 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1152 /** common subexpression elimination **/
1153 /* Checks whether n is already available. */
1154 /* The block input is used to distinguish different subexpressions. Right
1155 now all nodes are pinned to blocks, i.e., the cse only finds common
1156 subexpressions within a block. */
1158 n = identify_cons (current_ir_graph->value_table, n);
1161 /* We found an existing, better node, so we can deallocate the old node. */
1162 obstack_free (current_ir_graph->obst, old_n);
1165 /* Some more constant expression evaluation that does not allow to
1167 if (get_opt_constant_folding() ||
1168 (get_irn_op(n) == op_Cond) ||
1169 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1170 n = transform_node (n);
1172 /* Remove nodes with dead (Bad) input.
1173 Run always for transformation induced Bads. */
1176 /* Now we have a legal, useful node. Enter it in hash table for cse */
1177 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1178 n = identify_remember (current_ir_graph->value_table, n);
1185 /* These optimizations never deallocate nodes. This can cause dead
1186 nodes lying on the obstack. Remove these by a dead node elimination,
1187 i.e., a copying garbage collection. */
1189 optimize_in_place_2 (ir_node *n)
1194 if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
1196 /* if not optimize return n */
1199 /* Here this is possible. Why? */
1204 /* constant expression evaluation / constant folding */
1205 if (get_opt_constant_folding()) {
1206 /* constants can not be evaluated */
1207 if (get_irn_op(n) != op_Const) {
1208 /* try to evaluate */
1209 tv = computed_value (n);
1210 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1211 /* evaluation was succesful -- replace the node. */
1212 n = new_Const (get_tarval_mode (tv), tv);
1213 __dbg_info_merge_pair(n, old_n, dbg_const_eval);
1219 /* remove unnecessary nodes */
1220 /*if (get_opt_constant_folding()) */
1221 if (get_opt_constant_folding() ||
1222 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1223 (get_irn_op(n) == op_Id) || /* ... */
1224 (get_irn_op(n) == op_Proj) || /* ... */
1225 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1226 n = equivalent_node (n);
1228 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1230 /** common subexpression elimination **/
1231 /* Checks whether n is already available. */
1232 /* The block input is used to distinguish different subexpressions. Right
1233 now all nodes are pinned to blocks, i.e., the cse only finds common
1234 subexpressions within a block. */
1235 if (get_opt_cse()) {
1236 n = identify (current_ir_graph->value_table, n);
1239 /* Some more constant expression evaluation. */
1240 if (get_opt_constant_folding() ||
1241 (get_irn_op(n) == op_Cond) ||
1242 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1243 n = transform_node (n);
1245 /* Remove nodes with dead (Bad) input.
1246 Run always for transformation induced Bads. */
1249 /* Now we can verify the node, as it has no dead inputs any more. */
1252 /* Now we have a legal, useful node. Enter it in hash table for cse.
1253 Blocks should be unique anyways. (Except the successor of start:
1254 is cse with the start block!) */
1255 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1256 n = identify_remember (current_ir_graph->value_table, n);
1261 /* Wrapper for external use, set proper status bits after optimization */
1263 optimize_in_place (ir_node *n) {
1264 /* Handle graph state */
1265 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1266 if (get_opt_global_cse())
1267 set_irg_pinned(current_ir_graph, floats);
1268 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1269 set_irg_outs_inconsistent(current_ir_graph);
1270 /* Maybe we could also test whether optimizing the node can
1271 change the control graph. */
1272 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1273 set_irg_dom_inconsistent(current_ir_graph);
1274 return optimize_in_place_2 (n);