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"
27 /* Make types visible to allow most efficient access */
28 # include "entity_t.h"
30 /* Trivial INLINEable routine for copy propagation.
31 Does follow Ids, needed to optimize INLINEd code. */
32 static INLINE ir_node *
33 follow_Id (ir_node *n)
35 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
39 static INLINE tarval *
42 if ((n != NULL) && (get_irn_op(n) == op_Const))
43 return get_Const_tarval(n); /* might return tarval_bad */
48 /* if n can be computed, return the value, else tarval_bad. Performs
49 constant folding. GL: Only if n is arithmetic operator? */
51 computed_value (ir_node *n)
55 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
56 /* initialized to uniformly filter invalid constants */
57 tarval *ta = tarval_bad, *tb = tarval_bad;
61 /* get the operands we will work on for simple cases. */
63 a = get_binop_left(n);
64 b = get_binop_right(n);
65 } else if (is_unop(n)) {
69 /* if the operands are constants, get the target value, else set it NULL.
70 (a and b may be NULL if we treat a node that is no computation.) */
74 /* Perform the constant evaluation / computation. */
75 switch (get_irn_opcode(n)) {
77 res = get_Const_tarval(n);
80 if ((get_SymConst_kind(n) == size) &&
81 (get_type_state(get_SymConst_type(n))) == layout_fixed)
82 res = new_tarval_from_long (get_type_size(get_SymConst_type(n)), mode_Is);
85 if ((ta != tarval_bad) && (tb != tarval_bad)
86 && (get_irn_mode(a) == get_irn_mode(b))
87 && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
88 res = tarval_add (ta, tb);
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 res = tarval_sub (ta, tb);
99 if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
100 res = tarval_neg (ta);
103 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
104 res = tarval_mul (ta, tb);
106 /* a*0 = 0 or 0*b = 0:
107 calls computed_value recursive and returns the 0 with proper
110 if ( ( ((v = computed_value (a)) != tarval_bad)
111 && (v == get_mode_null(get_tarval_mode(v))) )
112 || ( ((v = computed_value (b)) != tarval_bad)
113 && (v == get_mode_null(get_tarval_mode(v))) )) {
119 /* This was missing in original implementation. Why? */
120 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
121 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
122 res = tarval_quo(ta, tb);
126 /* This was missing in original implementation. Why? */
127 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
128 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
129 res = tarval_div(ta, tb);
133 /* This was missing in original implementation. Why? */
134 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
135 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
136 res = tarval_mod(ta, tb);
139 /* for iro_DivMod see iro_Proj */
141 if (ta != tarval_bad)
142 res = tarval_abs (ta);
145 if ((ta != tarval_bad) && (tb != tarval_bad)) {
146 res = tarval_and (ta, tb);
149 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_NULL)
150 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
156 if ((ta != tarval_bad) && (tb != tarval_bad)) {
157 res = tarval_or (ta, tb);
160 if ( (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
161 || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
167 if ((ta != tarval_bad) && (tb != tarval_bad)) {
168 res = tarval_eor (ta, tb);
172 if ((ta != tarval_bad)) {
173 res = tarval_not (ta);
177 if ((ta != tarval_bad) && (tb != tarval_bad)) {
178 res = tarval_shl (ta, tb);
182 if ((ta != tarval_bad) && (tb != tarval_bad)) {
183 res = tarval_shr (ta, tb);
187 if ((ta != tarval_bad) && (tb != tarval_bad)) {
188 res = tarval_shrs (ta, tb);
192 if ((ta != tarval_bad) && (tb != tarval_bad)) {
193 /*res = tarval_rot (ta, tb)*/;
197 if (ta != tarval_bad) {
198 res = tarval_convert_to (ta, get_irn_mode (n));
201 case iro_Proj: /* iro_Cmp */
205 a = get_Proj_pred(n);
206 /* Optimize Cmp nodes.
207 This performs a first step of unreachable code elimination.
208 Proj can not be computed, but folding a Cmp above the Proj here is
209 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
211 There are several case where we can evaluate a Cmp node:
212 1. The nodes compared are both the same. If we compare for
213 equal, greater equal, ... this will return true, else it
214 will return false. This step relies on cse.
215 2. The predecessors of Cmp are target values. We can evaluate
217 3. The predecessors are Allocs or void* constants. Allocs never
218 return NULL, they raise an exception. Therefore we can predict
220 if (get_irn_op(a) == op_Cmp) {
221 aa = get_Cmp_left(a);
222 ab = get_Cmp_right(a);
223 if (aa == ab) { /* 1.: */
224 /* This is a tric with the bits used for encoding the Cmp
225 Proj numbers, the following statement is not the same:
226 res = new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
227 res = new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
229 tarval *taa = computed_value (aa);
230 tarval *tab = computed_value (ab);
231 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
232 /* strange checks... */
233 pnc_number flags = tarval_cmp (taa, tab);
234 if (flags != False) {
235 res = new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
237 } else { /* check for 3.: */
238 ir_node *aaa = skip_nop(skip_Proj(aa));
239 ir_node *aba = skip_nop(skip_Proj(ab));
240 if ( ( (/* aa is ProjP and aaa is Alloc */
241 (get_irn_op(aa) == op_Proj)
242 && (mode_is_reference(get_irn_mode(aa)))
243 && (get_irn_op(aaa) == op_Alloc))
244 && ( (/* ab is constant void */
245 (get_irn_op(ab) == op_Const)
246 && (mode_is_reference(get_irn_mode(ab)))
247 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
248 || (/* ab is other Alloc */
249 (get_irn_op(ab) == op_Proj)
250 && (mode_is_reference(get_irn_mode(ab)))
251 && (get_irn_op(aba) == op_Alloc)
253 || (/* aa is void and aba is Alloc */
254 (get_irn_op(aa) == op_Const)
255 && (mode_is_reference(get_irn_mode(aa)))
256 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
257 && (get_irn_op(ab) == op_Proj)
258 && (mode_is_reference(get_irn_mode(ab)))
259 && (get_irn_op(aba) == op_Alloc)))
261 res = new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
264 } else if (get_irn_op(a) == op_DivMod) {
265 ta = value_of(get_DivMod_left(a));
266 tb = value_of(get_DivMod_right(a));
267 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
268 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
269 if (get_Proj_proj(n)== 0) /* Div */
270 res = tarval_div(ta, tb);
272 res = tarval_mod(ta, tb);
285 /* returns 1 if the a and b are pointers to different locations. */
287 different_identity (ir_node *a, ir_node *b)
289 assert (mode_is_reference(get_irn_mode (a))
290 && mode_is_reference(get_irn_mode (b)));
292 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
293 ir_node *a1 = get_Proj_pred (a);
294 ir_node *b1 = get_Proj_pred (b);
295 if (a1 != b1 && get_irn_op (a1) == op_Alloc
296 && get_irn_op (b1) == op_Alloc)
303 /* equivalent_node returns a node equivalent to N. It skips all nodes that
304 perform no actual computation, as, e.g., the Id nodes. It does not create
305 new nodes. It is therefore safe to free N if the node returned is not N.
306 If a node returns a Tuple we can not just skip it. If the size of the
307 in array fits, we transform n into a tuple (e.g., Div). */
309 equivalent_node (ir_node *n)
312 ir_node *a = NULL; /* to shutup gcc */
313 ir_node *b = NULL; /* to shutup gcc */
314 ir_node *c = NULL; /* to shutup gcc */
317 ins = get_irn_arity (n);
319 /* get the operands we will work on */
321 a = get_binop_left(n);
322 b = get_binop_right(n);
323 } else if (is_unop(n)) {
327 /* skip unnecessary nodes. */
328 switch (get_irn_opcode (n)) {
331 /* The Block constructor does not call optimize, but mature_block
332 calls the optimization. */
333 assert(get_Block_matured(n));
335 /* Straightening: a single entry Block following a single exit Block
336 can be merged, if it is not the Start block. */
337 /* !!! Beware, all Phi-nodes of n must have been optimized away.
338 This should be true, as the block is matured before optimize is called.
339 But what about Phi-cycles with the Phi0/Id that could not be resolved?
340 Remaining Phi nodes are just Ids. */
341 if ((get_Block_n_cfgpreds(n) == 1) &&
342 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
343 (get_opt_control_flow_straightening())) {
344 n = get_nodes_Block(get_Block_cfgpred(n, 0)); DBG_OPT_STG;
346 } else if ((get_Block_n_cfgpreds(n) == 2) &&
347 (get_opt_control_flow_weak_simplification())) {
348 /* Test whether Cond jumps twice to this block
349 @@@ we could do this also with two loops finding two preds from several ones. */
350 a = get_Block_cfgpred(n, 0);
351 b = get_Block_cfgpred(n, 1);
352 if ((get_irn_op(a) == op_Proj) &&
353 (get_irn_op(b) == op_Proj) &&
354 (get_Proj_pred(a) == get_Proj_pred(b)) &&
355 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
356 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
357 /* Also a single entry Block following a single exit Block. Phis have
358 twice the same operand and will be optimized away. */
359 n = get_nodes_Block(a); DBG_OPT_IFSIM;
361 } else if (get_opt_unreachable_code() &&
362 (n != current_ir_graph->start_block) &&
363 (n != current_ir_graph->end_block) ) {
365 /* If all inputs are dead, this block is dead too, except if it is
366 the start or end block. This is a step of unreachable code
368 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
369 if (!is_Bad(get_Block_cfgpred(n, i))) break;
371 if (i == get_Block_n_cfgpreds(n))
377 case iro_Jmp: /* GL: Why not same for op_Raise?? */
378 /* unreachable code elimination */
379 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
381 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
382 See cases for iro_Cond and iro_Proj in transform_node. */
383 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
384 case iro_Or: if (a == b) {n = a; break;}
389 /* After running compute_node there is only one constant predecessor.
390 Find this predecessors value and remember the other node: */
391 if ((tv = computed_value (a)) != tarval_bad) {
393 } else if ((tv = computed_value (b)) != tarval_bad) {
397 /* If this predecessors constant value is zero, the operation is
398 unnecessary. Remove it: */
399 if (tarval_classify (tv) == TV_CLASSIFY_NULL) {
400 n = on; DBG_OPT_ALGSIM1;
408 /* these operations are not commutative. Test only one predecessor. */
409 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_NULL) {
410 n = a; DBG_OPT_ALGSIM1;
411 /* Test if b > #bits of a ==> return 0 / divide b by #bits
412 --> transform node? */
415 case iro_Not: /* NotNot x == x */
416 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
417 out of bounds exception if min =! max? */
418 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
419 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
423 /* Mul is commutative and has again an other neutral element. */
424 if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ONE) {
425 n = b; DBG_OPT_ALGSIM1;
426 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) {
427 n = a; DBG_OPT_ALGSIM1;
431 /* Div is not commutative. */
432 if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
433 /* Turn Div into a tuple (mem, bad, a) */
434 ir_node *mem = get_Div_mem(n);
435 turn_into_tuple(n, 3);
436 set_Tuple_pred(n, 0, mem);
437 set_Tuple_pred(n, 1, new_Bad());
438 set_Tuple_pred(n, 2, a);
442 case iro_Mod, Quot, DivMod
443 DivMod allocates new nodes --> it's treated in transform node.
444 What about Quot, DivMod?
448 n = a; /* And has it's own neutral element */
449 } else if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ALL_ONE) {
451 } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ALL_ONE) {
454 if (n != oldn) DBG_OPT_ALGSIM1;
458 ir_mode *n_mode = get_irn_mode(n);
459 ir_mode *a_mode = get_irn_mode(a);
461 if (n_mode == a_mode) { /* No Conv necessary */
462 n = a; DBG_OPT_ALGSIM3;
463 } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
467 n_mode = get_irn_mode(n);
468 b_mode = get_irn_mode(b);
470 if (n_mode == b_mode) {
471 if (n_mode == mode_b) {
472 n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM1;
474 else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
475 if (smaller_mode(b_mode, a_mode)){
476 n = b; /* ConvS(ConvL(xxxS(...))) == xxxS(...) */ DBG_OPT_ALGSIM1;
485 /* Several optimizations:
486 - no Phi in start block.
487 - remove Id operators that are inputs to Phi
488 - fold Phi-nodes, iff they have only one predecessor except
493 ir_node *block = NULL; /* to shutup gcc */
494 ir_node *first_val = NULL; /* to shutup gcc */
495 ir_node *scnd_val = NULL; /* to shutup gcc */
497 if (!get_opt_normalize()) return n;
499 n_preds = get_Phi_n_preds(n);
501 block = get_nodes_Block(n);
502 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
503 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
504 if ((is_Bad(block)) || /* Control dead */
505 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
506 return new_Bad(); /* in the Start Block. */
508 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
511 /* first we test for a special case: */
512 /* Confirm is a special node fixing additional information for a
513 value that is known at a certain point. This is useful for
514 dataflow analysis. */
516 ir_node *a = follow_Id (get_Phi_pred(n, 0));
517 ir_node *b = follow_Id (get_Phi_pred(n, 1));
518 if ( (get_irn_op(a) == op_Confirm)
519 && (get_irn_op(b) == op_Confirm)
520 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
521 && (get_irn_n(a, 1) == get_irn_n (b, 1))
522 && (a->data.num == (~b->data.num & irpn_True) )) {
523 n = follow_Id (get_irn_n(a, 0));
529 /* Find first non-self-referencing input */
530 for (i = 0; i < n_preds; ++i) {
531 first_val = follow_Id(get_Phi_pred(n, i));
533 set_Phi_pred(n, i, first_val);
534 if ( (first_val != n) /* not self pointer */
535 && (get_irn_op(first_val) != op_Bad) /* value not dead */
536 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
537 break; /* then found first value. */
541 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
542 if (i >= n_preds) { n = new_Bad(); break; }
546 /* follow_Id () for rest of inputs, determine if any of these
547 are non-self-referencing */
548 while (++i < n_preds) {
549 scnd_val = follow_Id(get_Phi_pred(n, i));
551 set_Phi_pred(n, i, scnd_val);
553 && (scnd_val != first_val)
554 && (get_irn_op(scnd_val) != op_Bad)
555 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
560 /* Fold, if no multiple distinct non-self-referencing inputs */
562 n = first_val; DBG_OPT_PHI;
564 /* skip the remaining Ids. */
565 while (++i < n_preds) {
566 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
574 #if 0 /* Is an illegal transformation: different nodes can
575 represent the same pointer value!! */
576 a = skip_Proj(get_Load_mem(n));
579 if (get_irn_op(a) == op_Store) {
580 if ( different_identity (b, get_Store_ptr(a))) {
581 /* load and store use different pointers, therefore load
582 needs not take store's memory but the state before. */
583 set_Load_mem (n, get_Store_mem(a));
584 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
591 /* remove unnecessary store. */
593 a = skip_Proj(get_Store_mem(n));
594 b = get_Store_ptr(n);
595 c = skip_Proj(get_Store_value(n));
597 if (get_irn_op(a) == op_Store
598 && get_Store_ptr(a) == b
599 && skip_Proj(get_Store_value(a)) == c) {
600 /* We have twice exactly the same store -- a write after write. */
602 } else if (get_irn_op(c) == op_Load
603 && (a == c || skip_Proj(get_Load_mem(c)) == a)
604 && get_Load_ptr(c) == b ) {
605 /* We just loaded the value from the same memory, i.e., the store
606 doesn't change the memory -- a write after read. */
607 a = get_Store_mem(n);
608 turn_into_tuple(n, 2);
609 set_Tuple_pred(n, 0, a);
610 set_Tuple_pred(n, 1, new_Bad()); DBG_OPT_WAR;
617 a = get_Proj_pred(n);
619 if ( get_irn_op(a) == op_Tuple) {
620 /* Remove the Tuple/Proj combination. */
621 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
622 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
624 assert(0); /* This should not happen! */
627 } else if (get_irn_mode(n) == mode_X &&
628 is_Bad(get_nodes_Block(n))) {
629 /* Remove dead control flow -- early gigo. */
636 n = follow_Id (n); DBG_OPT_ID;
643 } /* end equivalent_node() */
645 /* do node specific optimizations of nodes predecessors. */
647 optimize_preds(ir_node *n) {
648 ir_node *a = NULL, *b = NULL;
650 /* get the operands we will work on for simple cases. */
652 a = get_binop_left(n);
653 b = get_binop_right(n);
654 } else if (is_unop(n)) {
658 switch (get_irn_opcode(n)) {
661 /* We don't want Cast as input to Cmp. */
662 if (get_irn_op(a) == op_Cast) {
666 if (get_irn_op(b) == op_Cast) {
677 /* tries several [inplace] [optimizing] transformations and returns an
678 equivalent node. The difference to equivalent_node is that these
679 transformations _do_ generate new nodes, and thus the old node must
680 not be freed even if the equivalent node isn't the old one. */
682 transform_node (ir_node *n) {
683 ir_node *a = NULL, *b;
686 switch (get_irn_opcode(n)) {
688 ta = computed_value(n);
689 if (ta != tarval_bad) {
690 /* Turn Div into a tuple (mem, bad, value) */
691 ir_node *mem = get_Div_mem(n);
692 turn_into_tuple(n, 3);
693 set_Tuple_pred(n, 0, mem);
694 set_Tuple_pred(n, 1, new_Bad());
695 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
699 ta = computed_value(n);
700 if (ta != tarval_bad) {
701 /* Turn Mod into a tuple (mem, bad, value) */
702 ir_node *mem = get_Mod_mem(n);
703 turn_into_tuple(n, 3);
704 set_Tuple_pred(n, 0, mem);
705 set_Tuple_pred(n, 1, new_Bad());
706 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
714 a = get_DivMod_left(n);
715 b = get_DivMod_right(n);
716 mode = get_irn_mode(a);
718 if (!(mode_is_int(get_irn_mode(a)) &&
719 mode_is_int(get_irn_mode(b))))
723 a = new_Const (mode, get_mode_one(mode));
724 b = new_Const (mode, get_mode_null(mode));
730 if (tb != tarval_bad) {
731 if (tb == get_mode_one(get_tarval_mode(tb))) {
732 b = new_Const (mode, get_mode_null(mode));
734 } else if (ta != tarval_bad) {
736 resa = tarval_div (ta, tb);
737 if (resa == tarval_bad) break; /* Causes exception!!! Model by replacing through
738 Jmp for X result!? */
739 resb = tarval_mod (ta, tb);
740 if (resb == tarval_bad) break; /* Causes exception! */
741 a = new_Const (mode, resa);
742 b = new_Const (mode, resb);
745 } else if (ta == get_mode_null(get_tarval_mode(ta))) {
750 if (evaluated) { /* replace by tuple */
751 ir_node *mem = get_DivMod_mem(n);
752 turn_into_tuple(n, 4);
753 set_Tuple_pred(n, 0, mem);
754 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
755 set_Tuple_pred(n, 2, a);
756 set_Tuple_pred(n, 3, b);
757 assert(get_nodes_Block(n));
763 /* Replace the Cond by a Jmp if it branches on a constant
766 a = get_Cond_selector(n);
769 if ((ta != tarval_bad) &&
770 (get_irn_mode(a) == mode_b) &&
771 (get_opt_unreachable_code())) {
772 /* It's a boolean Cond, branching on a boolean constant.
773 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
774 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
775 turn_into_tuple(n, 2);
776 if (ta == tarval_b_true) {
777 set_Tuple_pred(n, 0, new_Bad());
778 set_Tuple_pred(n, 1, jmp);
780 set_Tuple_pred(n, 0, jmp);
781 set_Tuple_pred(n, 1, new_Bad());
783 /* We might generate an endless loop, so keep it alive. */
784 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
785 } else if ((ta != tarval_bad) &&
786 (get_irn_mode(a) == mode_Iu) &&
787 (get_Cond_kind(n) == dense) &&
788 (get_opt_unreachable_code())) {
789 /* I don't want to allow Tuples smaller than the biggest Proj.
790 Also this tuple might get really big...
791 I generate the Jmp here, and remember it in link. Link is used
792 when optimizing Proj. */
793 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
794 /* We might generate an endless loop, so keep it alive. */
795 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
796 } else if ((get_irn_op(a) == op_Eor)
797 && (get_irn_mode(a) == mode_b)
798 && (tarval_classify(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
799 /* The Eor is a negate. Generate a new Cond without the negate,
800 simulate the negate by exchanging the results. */
801 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
803 } else if ((get_irn_op(a) == op_Not)
804 && (get_irn_mode(a) == mode_b)) {
805 /* A Not before the Cond. Generate a new Cond without the Not,
806 simulate the Not by exchanging the results. */
807 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
814 a = get_Proj_pred(n);
816 if ((get_irn_op(a) == op_Cond)
818 && get_irn_op(get_irn_link(a)) == op_Cond) {
819 /* Use the better Cond if the Proj projs from a Cond which get's
820 its result from an Eor/Not. */
821 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
822 || (get_irn_op(get_Cond_selector(a)) == op_Not))
823 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
824 && (get_irn_op(get_irn_link(a)) == op_Cond)
825 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
826 set_Proj_pred(n, get_irn_link(a));
827 if (get_Proj_proj(n) == 0)
831 } else if ((get_irn_op(a) == op_Cond)
832 && (get_irn_mode(get_Cond_selector(a)) == mode_Iu)
834 && (get_Cond_kind(a) == dense)
835 && (get_opt_unreachable_code())) {
836 /* The Cond is a Switch on a Constant */
837 if (get_Proj_proj(n) == tarval_to_long(value_of(a))) {
838 /* The always taken branch, reuse the existing Jmp. */
839 if (!get_irn_link(a)) /* well, if it exists ;-> */
840 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
841 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
843 } else {/* Not taken control flow, but be careful with the default! */
844 if (get_Proj_proj(n) < a->attr.c.default_proj){
845 /* a never taken branch */
848 a->attr.c.default_proj = get_Proj_proj(n);
853 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
855 b = get_Eor_right(n);
857 if ((get_irn_mode(n) == mode_b)
858 && (get_irn_op(a) == op_Proj)
859 && (get_irn_mode(a) == mode_b)
860 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE)
861 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
862 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
863 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
864 mode_b, get_negated_pnc(get_Proj_proj(a)));
865 else if ((get_irn_mode(n) == mode_b)
866 && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE))
867 /* The Eor is a Not. Replace it by a Not. */
868 /* ????!!!Extend to bitfield 1111111. */
869 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
875 if ( (get_irn_mode(n) == mode_b)
876 && (get_irn_op(a) == op_Proj)
877 && (get_irn_mode(a) == mode_b)
878 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
879 /* We negate a Cmp. The Cmp has the negated result anyways! */
880 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
881 mode_b, get_negated_pnc(get_Proj_proj(a)));
889 /* **************** Common Subexpression Elimination **************** */
891 /** The size of the hash table used, should estimate the number of nodes
893 #define N_IR_NODES 512
895 /* Compare function for two nodes in the hash table. Gets two */
896 /* nodes as parameters. Returns 0 if the nodes are a cse. */
898 vt_cmp (const void *elt, const void *key)
906 if (a == b) return 0;
908 if ((get_irn_op(a) != get_irn_op(b)) ||
909 (get_irn_mode(a) != get_irn_mode(b))) return 1;
911 /* compare if a's in and b's in are equal */
912 irn_arity_a = get_irn_arity (a);
913 if (irn_arity_a != get_irn_arity(b))
916 /* for block-local cse and pinned nodes: */
917 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
918 if (get_irn_n(a, -1) != get_irn_n(b, -1))
922 /* compare a->in[0..ins] with b->in[0..ins] */
923 for (i = 0; i < irn_arity_a; i++)
924 if (get_irn_n(a, i) != get_irn_n(b, i))
927 switch (get_irn_opcode(a)) {
929 return (get_Const_tarval(a) != get_Const_tarval(b))
930 || (get_Const_type(a) != get_Const_type(b));
932 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
934 return get_Filter_proj(a) != get_Filter_proj(b);
936 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
937 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
939 return (get_irn_free_attr(a) != get_irn_free_attr(b));
941 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
942 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
944 return (get_irn_call_attr(a) != get_irn_call_attr(b));
946 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
947 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
948 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
949 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
950 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
952 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
954 return get_Cast_type(a) != get_Cast_type(b);
962 ir_node_hash (ir_node *node)
967 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
968 h = irn_arity = get_irn_arity(node);
970 /* consider all in nodes... except the block. */
971 for (i = 0; i < irn_arity; i++) {
972 h = 9*h + (unsigned long)get_irn_n(node, i);
976 h = 9*h + (unsigned long) get_irn_mode (node);
978 h = 9*h + (unsigned long) get_irn_op (node);
984 new_identities (void)
986 return new_pset (vt_cmp, N_IR_NODES);
990 del_identities (pset *value_table)
992 del_pset (value_table);
995 /* Return the canonical node computing the same value as n.
996 Looks up the node in a hash table. */
997 static INLINE ir_node *
998 identify (pset *value_table, ir_node *n)
1002 if (!value_table) return n;
1004 if (get_opt_reassociation()) {
1005 switch (get_irn_opcode (n)) {
1012 /* for commutative operators perform a OP b == b OP a */
1013 if (get_binop_left(n) > get_binop_right(n)) {
1014 ir_node *h = get_binop_left(n);
1015 set_binop_left(n, get_binop_right(n));
1016 set_binop_right(n, h);
1024 o = pset_find (value_table, n, ir_node_hash (n));
1030 /* During construction we set the pinned flag in the graph right when the
1031 optimizatin is performed. The flag turning on procedure global cse could
1032 be changed between two allocations. This way we are safe. */
1033 static INLINE ir_node *
1034 identify_cons (pset *value_table, ir_node *n) {
1036 n = identify(value_table, n);
1037 if (get_irn_n(old, -1) != get_irn_n(n, -1))
1038 set_irg_pinned(current_ir_graph, floats);
1042 /* Return the canonical node computing the same value as n.
1043 Looks up the node in a hash table, enters it in the table
1044 if it isn't there yet. */
1046 identify_remember (pset *value_table, ir_node *node)
1050 if (!value_table) return node;
1052 /* lookup or insert in hash table with given hash key. */
1053 o = pset_insert (value_table, node, ir_node_hash (node));
1055 if (o == node) return node;
1061 add_identities (pset *value_table, ir_node *node) {
1062 identify_remember (value_table, node);
1065 /* garbage in, garbage out. If a node has a dead input, i.e., the
1066 Bad node is input to the node, return the Bad node. */
1067 static INLINE ir_node *
1068 gigo (ir_node *node)
1071 ir_op* op = get_irn_op(node);
1074 /* remove garbage blocks by looking at control flow that leaves the block
1075 and replacing the control flow by Bad. */
1076 if (get_irn_mode(node) == mode_X) {
1077 ir_node *block = get_nodes_block(node);
1078 if (op == op_End) return node; /* Don't optimize End, may have Bads. */
1079 if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1080 irn_arity = get_irn_arity(block);
1081 for (i = 0; i < irn_arity; i++) {
1082 if (!is_Bad(get_irn_n(block, i))) break;
1084 if (i == irn_arity) return new_Bad();
1088 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1089 blocks predecessors is dead. */
1090 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1091 irn_arity = get_irn_arity(node);
1092 for (i = -1; i < irn_arity; i++) {
1093 if (is_Bad(get_irn_n(node, i))) {
1099 /* With this code we violate the agreement that local_optimize
1100 only leaves Bads in Block, Phi and Tuple nodes. */
1101 /* If Block has only Bads as predecessors it's garbage. */
1102 /* If Phi has only Bads as predecessors it's garbage. */
1103 if ((op == op_Block && get_Block_matured(node)) || op == op_Phi) {
1104 irn_arity = get_irn_arity(node);
1105 for (i = 0; i < irn_arity; i++) {
1106 if (!is_Bad(get_irn_n(node, i))) break;
1108 if (i == irn_arity) node = new_Bad();
1115 /* These optimizations deallocate nodes from the obstack.
1116 It can only be called if it is guaranteed that no other nodes
1117 reference this one, i.e., right after construction of a node. */
1119 optimize_node (ir_node *n)
1124 /* Allways optimize Phi nodes: part of the construction. */
1125 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1127 /* constant expression evaluation / constant folding */
1128 if (get_opt_constant_folding()) {
1129 /* constants can not be evaluated */
1130 if (get_irn_op(n) != op_Const) {
1131 /* try to evaluate */
1132 tv = computed_value (n);
1133 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1134 /* evaluation was succesful -- replace the node. */
1135 obstack_free (current_ir_graph->obst, n);
1136 return new_Const (get_tarval_mode (tv), tv);
1141 /* remove unnecessary nodes */
1142 if (get_opt_constant_folding() ||
1143 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1144 (get_irn_op(n) == op_Id) ||
1145 (get_irn_op(n) == op_Proj) ||
1146 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1147 n = equivalent_node (n);
1149 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1151 /** common subexpression elimination **/
1152 /* Checks whether n is already available. */
1153 /* The block input is used to distinguish different subexpressions. Right
1154 now all nodes are pinned to blocks, i.e., the cse only finds common
1155 subexpressions within a block. */
1157 n = identify_cons (current_ir_graph->value_table, n);
1160 /* We found an existing, better node, so we can deallocate the old node. */
1161 obstack_free (current_ir_graph->obst, old_n);
1164 /* Some more constant expression evaluation that does not allow to
1166 if (get_opt_constant_folding() ||
1167 (get_irn_op(n) == op_Cond) ||
1168 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1169 n = transform_node (n);
1171 /* Remove nodes with dead (Bad) input.
1172 Run always for transformation induced Bads. */
1175 /* Now we can verify the node, as it has no dead inputs any more. */
1178 /* Now we have a legal, useful node. Enter it in hash table for cse */
1179 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1180 n = identify_remember (current_ir_graph->value_table, n);
1187 /* These optimizations never deallocate nodes. This can cause dead
1188 nodes lying on the obstack. Remove these by a dead node elimination,
1189 i.e., a copying garbage collection. */
1191 optimize_in_place_2 (ir_node *n)
1196 if (!get_optimize() && (get_irn_op(n) != op_Phi)) return n;
1198 /* if not optimize return n */
1201 /* Here this is possible. Why? */
1206 /* constant expression evaluation / constant folding */
1207 if (get_opt_constant_folding()) {
1208 /* constants can not be evaluated */
1209 if (get_irn_op(n) != op_Const) {
1210 /* try to evaluate */
1211 tv = computed_value (n);
1212 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1213 /* evaluation was succesful -- replace the node. */
1214 n = new_Const (get_tarval_mode (tv), tv);
1215 __dbg_info_merge_pair(n, old_n, dbg_const_eval);
1221 /* remove unnecessary nodes */
1222 /*if (get_opt_constant_folding()) */
1223 if (get_opt_constant_folding() ||
1224 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1225 (get_irn_op(n) == op_Id) || /* ... */
1226 (get_irn_op(n) == op_Proj) || /* ... */
1227 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1228 n = equivalent_node (n);
1230 optimize_preds(n); /* do node specific optimizations of nodes predecessors. */
1232 /** common subexpression elimination **/
1233 /* Checks whether n is already available. */
1234 /* The block input is used to distinguish different subexpressions. Right
1235 now all nodes are pinned to blocks, i.e., the cse only finds common
1236 subexpressions within a block. */
1237 if (get_opt_cse()) {
1238 n = identify (current_ir_graph->value_table, n);
1241 /* Some more constant expression evaluation. */
1242 if (get_opt_constant_folding() ||
1243 (get_irn_op(n) == op_Cond) ||
1244 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1245 n = transform_node (n);
1247 /* Remove nodes with dead (Bad) input.
1248 Run always for transformation induced Bads. */
1251 /* Now we can verify the node, as it has no dead inputs any more. */
1254 /* Now we have a legal, useful node. Enter it in hash table for cse.
1255 Blocks should be unique anyways. (Except the successor of start:
1256 is cse with the start block!) */
1257 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1258 n = identify_remember (current_ir_graph->value_table, n);
1263 /* Wrapper for external use, set proper status bits after optimization */
1265 optimize_in_place (ir_node *n) {
1266 /* Handle graph state */
1267 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1268 if (get_opt_global_cse())
1269 set_irg_pinned(current_ir_graph, floats);
1270 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1271 set_irg_outs_inconsistent(current_ir_graph);
1272 /* Maybe we could also test whether optimizing the node can
1273 change the control graph. */
1274 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1275 set_irg_dom_inconsistent(current_ir_graph);
1276 return optimize_in_place_2 (n);