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"
25 # include "dbginfo_t.h"
26 # include "iropt_dbg.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 ( ( ((v = computed_value (a)) != tarval_bad)
151 && (v == get_mode_null(get_tarval_mode(v))) )
152 || ( ((v = computed_value (b)) != tarval_bad)
153 && (v == get_mode_null(get_tarval_mode(v))) )) {
159 if ((ta != tarval_bad) && (tb != tarval_bad)) {
160 res = tarval_or (ta, tb);
163 if ( (tarval_classify ((v = computed_value (a))) == -1)
164 || (tarval_classify ((v = computed_value (b))) == -1)) {
170 if ((ta != tarval_bad) && (tb != tarval_bad)) {
171 res = tarval_eor (ta, tb);
175 if ((ta != tarval_bad)) {
176 res = tarval_neg (ta);
180 if ((ta != tarval_bad) && (tb != tarval_bad)) {
181 res = tarval_shl (ta, tb);
185 if ((ta != tarval_bad) && (tb != tarval_bad)) {
186 res = tarval_shr (ta, tb);
190 if ((ta != tarval_bad) && (tb != tarval_bad)) {
191 res = tarval_shrs (ta, tb);
195 if ((ta != tarval_bad) && (tb != tarval_bad)) {
196 /*res = tarval_rot (ta, tb)*/;
200 if (ta != tarval_bad) {
201 res = tarval_convert_to (ta, get_irn_mode (n));
204 case iro_Proj: /* iro_Cmp */
208 a = get_Proj_pred(n);
209 /* Optimize Cmp nodes.
210 This performs a first step of unreachable code elimination.
211 Proj can not be computed, but folding a Cmp above the Proj here is
212 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
214 There are several case where we can evaluate a Cmp node:
215 1. The nodes compared are both the same. If we compare for
216 equal, greater equal, ... this will return true, else it
217 will return false. This step relies on cse.
218 2. The predecessors of Cmp are target values. We can evaluate
220 3. The predecessors are Allocs or void* constants. Allocs never
221 return NULL, they raise an exception. Therefore we can predict
223 if (get_irn_op(a) == op_Cmp) {
224 aa = get_Cmp_left(a);
225 ab = get_Cmp_right(a);
226 if (aa == ab) { /* 1.: */
227 /* This is a tric with the bits used for encoding the Cmp
228 Proj numbers, the following statement is not the same:
229 res = new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
230 res = new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
232 tarval *taa = computed_value (aa);
233 tarval *tab = computed_value (ab);
234 if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
235 /* strange checks... */
236 pnc_number flags = tarval_cmp (taa, tab);
237 if (flags != False) {
238 res = new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
240 } else { /* check for 3.: */
241 ir_node *aaa = skip_nop(skip_Proj(aa));
242 ir_node *aba = skip_nop(skip_Proj(ab));
243 if ( ( (/* aa is ProjP and aaa is Alloc */
244 (get_irn_op(aa) == op_Proj)
245 && (mode_is_reference(get_irn_mode(aa)))
246 && (get_irn_op(aaa) == op_Alloc))
247 && ( (/* ab is constant void */
248 (get_irn_op(ab) == op_Const)
249 && (mode_is_reference(get_irn_mode(ab)))
250 && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
251 || (/* ab is other Alloc */
252 (get_irn_op(ab) == op_Proj)
253 && (mode_is_reference(get_irn_mode(ab)))
254 && (get_irn_op(aba) == op_Alloc)
256 || (/* aa is void and aba is Alloc */
257 (get_irn_op(aa) == op_Const)
258 && (mode_is_reference(get_irn_mode(aa)))
259 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
260 && (get_irn_op(ab) == op_Proj)
261 && (mode_is_reference(get_irn_mode(ab)))
262 && (get_irn_op(aba) == op_Alloc)))
264 res = new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
267 } else if (get_irn_op(a) == op_DivMod) {
268 ta = value_of(get_DivMod_left(a));
269 tb = value_of(get_DivMod_right(a));
270 if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
271 if (tb == get_mode_null(get_tarval_mode(tb))) break; /* div by zero: return tarval_bad */
272 if (get_Proj_proj(n)== 0) /* Div */
273 res = tarval_div(ta, tb);
275 res = tarval_mod(ta, tb);
288 /* returns 1 if the a and b are pointers to different locations. */
290 different_identity (ir_node *a, ir_node *b)
292 assert (mode_is_reference(get_irn_mode (a))
293 && mode_is_reference(get_irn_mode (b)));
295 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
296 ir_node *a1 = get_Proj_pred (a);
297 ir_node *b1 = get_Proj_pred (b);
298 if (a1 != b1 && get_irn_op (a1) == op_Alloc
299 && get_irn_op (b1) == op_Alloc)
306 /* equivalent_node returns a node equivalent to N. It skips all nodes that
307 perform no actual computation, as, e.g., the Id nodes. It does not create
308 new nodes. It is therefore safe to free N if the node returned is not N.
309 If a node returns a Tuple we can not just skip it. If the size of the
310 in array fits, we transform n into a tuple (e.g., Div). */
312 equivalent_node (ir_node *n)
315 ir_node *a = NULL; /* to shutup gcc */
316 ir_node *b = NULL; /* to shutup gcc */
317 ir_node *c = NULL; /* to shutup gcc */
320 ins = get_irn_arity (n);
322 /* get the operands we will work on */
324 a = get_binop_left(n);
325 b = get_binop_right(n);
326 } else if (is_unop(n)) {
330 /* skip unnecessary nodes. */
331 switch (get_irn_opcode (n)) {
334 /* The Block constructor does not call optimize, but mature_block
335 calls the optimization. */
336 assert(get_Block_matured(n));
338 /* Straightening: a single entry Block following a single exit Block
339 can be merged, if it is not the Start block. */
340 /* !!! Beware, all Phi-nodes of n must have been optimized away.
341 This should be true, as the block is matured before optimize is called.
342 But what about Phi-cycles with the Phi0/Id that could not be resolved?
343 Remaining Phi nodes are just Ids. */
344 if ((get_Block_n_cfgpreds(n) == 1) &&
345 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
346 (get_opt_control_flow_straightening())) {
347 n = get_nodes_Block(get_Block_cfgpred(n, 0)); DBG_OPT_STG;
349 } else if ((get_Block_n_cfgpreds(n) == 2) &&
350 (get_opt_control_flow_weak_simplification())) {
351 /* Test whether Cond jumps twice to this block
352 @@@ we could do this also with two loops finding two preds from several ones. */
353 a = get_Block_cfgpred(n, 0);
354 b = get_Block_cfgpred(n, 1);
355 if ((get_irn_op(a) == op_Proj) &&
356 (get_irn_op(b) == op_Proj) &&
357 (get_Proj_pred(a) == get_Proj_pred(b)) &&
358 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
359 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
360 /* Also a single entry Block following a single exit Block. Phis have
361 twice the same operand and will be optimized away. */
362 n = get_nodes_Block(a); DBG_OPT_IFSIM;
364 } else if (get_opt_unreachable_code() &&
365 (n != current_ir_graph->start_block) &&
366 (n != current_ir_graph->end_block) ) {
368 /* If all inputs are dead, this block is dead too, except if it is
369 the start or end block. This is a step of unreachable code
371 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
372 if (!is_Bad(get_Block_cfgpred(n, i))) break;
374 if (i == get_Block_n_cfgpreds(n))
380 case iro_Jmp: /* GL: Why not same for op_Raise?? */
381 /* unreachable code elimination */
382 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
384 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
385 See cases for iro_Cond and iro_Proj in transform_node. */
386 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
387 case iro_Or: if (a == b) {n = a; break;}
392 /* After running compute_node there is only one constant predecessor.
393 Find this predecessors value and remember the other node: */
394 if ((tv = computed_value (a)) != tarval_bad) {
396 } else if ((tv = computed_value (b)) != tarval_bad) {
400 /* If this predecessors constant value is zero, the operation is
401 unnecessary. Remove it: */
402 if (tarval_classify (tv) == 0) {
403 n = on; DBG_OPT_ALGSIM1;
411 /* these operations are not commutative. Test only one predecessor. */
412 if (tarval_classify (computed_value (b)) == 0) {
413 n = a; DBG_OPT_ALGSIM1;
414 /* Test if b > #bits of a ==> return 0 / divide b by #bits
415 --> transform node? */
418 case iro_Not: /* NotNot x == x */
419 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
420 out of bounds exception if min =! max? */
421 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
422 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
426 /* Mul is commutative and has again an other neutral element. */
427 if (tarval_classify (computed_value (a)) == 1) {
428 n = b; DBG_OPT_ALGSIM1;
429 } else if (tarval_classify (computed_value (b)) == 1) {
430 n = a; DBG_OPT_ALGSIM1;
434 /* Div is not commutative. */
435 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
436 /* Turn Div into a tuple (mem, bad, a) */
437 ir_node *mem = get_Div_mem(n);
438 turn_into_tuple(n, 3);
439 set_Tuple_pred(n, 0, mem);
440 set_Tuple_pred(n, 1, new_Bad());
441 set_Tuple_pred(n, 2, a);
445 case iro_Mod, Quot, DivMod
446 DivMod allocates new nodes --> it's treated in transform node.
447 What about Quot, DivMod?
451 n = a; /* And has it's own neutral element */
452 } else if (tarval_classify (computed_value (a)) == -1) {
454 } else if (tarval_classify (computed_value (b)) == -1) {
457 if (n != oldn) DBG_OPT_ALGSIM1;
460 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
461 n = a; DBG_OPT_ALGSIM3;
462 } else if (get_irn_mode(n) == mode_b) {
463 if (get_irn_op(a) == op_Conv &&
464 get_irn_mode (get_Conv_op(a)) == mode_b) {
465 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM2;
472 /* Several optimizations:
473 - no Phi in start block.
474 - remove Id operators that are inputs to Phi
475 - fold Phi-nodes, iff they have only one predecessor except
480 ir_node *block = NULL; /* to shutup gcc */
481 ir_node *first_val = NULL; /* to shutup gcc */
482 ir_node *scnd_val = NULL; /* to shutup gcc */
484 if (!get_opt_normalize()) return n;
486 n_preds = get_Phi_n_preds(n);
488 block = get_nodes_Block(n);
489 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
490 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
491 if ((is_Bad(block)) || /* Control dead */
492 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
493 return new_Bad(); /* in the Start Block. */
495 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
498 /* first we test for a special case: */
499 /* Confirm is a special node fixing additional information for a
500 value that is known at a certain point. This is useful for
501 dataflow analysis. */
503 ir_node *a = follow_Id (get_Phi_pred(n, 0));
504 ir_node *b = follow_Id (get_Phi_pred(n, 1));
505 if ( (get_irn_op(a) == op_Confirm)
506 && (get_irn_op(b) == op_Confirm)
507 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
508 && (get_irn_n(a, 1) == get_irn_n (b, 1))
509 && (a->data.num == (~b->data.num & irpn_True) )) {
510 n = follow_Id (get_irn_n(a, 0));
516 /* Find first non-self-referencing input */
517 for (i = 0; i < n_preds; ++i) {
518 first_val = follow_Id(get_Phi_pred(n, i));
520 set_Phi_pred(n, i, first_val);
521 if ( (first_val != n) /* not self pointer */
522 && (get_irn_op(first_val) != op_Bad) /* value not dead */
523 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
524 break; /* then found first value. */
528 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
529 if (i >= n_preds) { n = new_Bad(); break; }
533 /* follow_Id () for rest of inputs, determine if any of these
534 are non-self-referencing */
535 while (++i < n_preds) {
536 scnd_val = follow_Id(get_Phi_pred(n, i));
538 set_Phi_pred(n, i, scnd_val);
540 && (scnd_val != first_val)
541 && (get_irn_op(scnd_val) != op_Bad)
542 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
547 /* Fold, if no multiple distinct non-self-referencing inputs */
549 n = first_val; DBG_OPT_PHI;
551 /* skip the remaining Ids. */
552 while (++i < n_preds) {
553 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
561 #if 0 /* Is an illegal transformation: different nodes can
562 represent the same pointer value!! */
563 a = skip_Proj(get_Load_mem(n));
566 if (get_irn_op(a) == op_Store) {
567 if ( different_identity (b, get_Store_ptr(a))) {
568 /* load and store use different pointers, therefore load
569 needs not take store's memory but the state before. */
570 set_Load_mem (n, get_Store_mem(a));
571 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
578 /* remove unnecessary store. */
580 a = skip_Proj(get_Store_mem(n));
581 b = get_Store_ptr(n);
582 c = skip_Proj(get_Store_value(n));
584 if (get_irn_op(a) == op_Store
585 && get_Store_ptr(a) == b
586 && skip_Proj(get_Store_value(a)) == c) {
587 /* We have twice exactly the same store -- a write after write. */
589 } else if (get_irn_op(c) == op_Load
590 && (a == c || skip_Proj(get_Load_mem(c)) == a)
591 && get_Load_ptr(c) == b ) {
592 /* We just loaded the value from the same memory, i.e., the store
593 doesn't change the memory -- a write after read. */
594 a = get_Store_mem(n);
595 turn_into_tuple(n, 2);
596 set_Tuple_pred(n, 0, a);
597 set_Tuple_pred(n, 1, new_Bad()); DBG_OPT_WAR;
604 a = get_Proj_pred(n);
606 if ( get_irn_op(a) == op_Tuple) {
607 /* Remove the Tuple/Proj combination. */
608 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
609 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
611 assert(0); /* This should not happen! */
614 } else if (get_irn_mode(n) == mode_X &&
615 is_Bad(get_nodes_Block(n))) {
616 /* Remove dead control flow -- early gigo. */
623 n = follow_Id (n); DBG_OPT_ID;
630 } /* end equivalent_node() */
633 /* tries several [inplace] [optimizing] transformations and returns an
634 equivalent node. The difference to equivalent_node is that these
635 transformations _do_ generate new nodes, and thus the old node must
636 not be freed even if the equivalent node isn't the old one. */
638 transform_node (ir_node *n)
641 ir_node *a = NULL, *b;
644 switch (get_irn_opcode(n)) {
646 ta = computed_value(n);
647 if (ta != tarval_bad) {
648 /* Turn Div into a tuple (mem, bad, value) */
649 ir_node *mem = get_Div_mem(n);
650 turn_into_tuple(n, 3);
651 set_Tuple_pred(n, 0, mem);
652 set_Tuple_pred(n, 1, new_Bad());
653 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
657 ta = computed_value(n);
658 if (ta != tarval_bad) {
659 /* Turn Div into a tuple (mem, bad, value) */
660 ir_node *mem = get_Mod_mem(n);
661 turn_into_tuple(n, 3);
662 set_Tuple_pred(n, 0, mem);
663 set_Tuple_pred(n, 1, new_Bad());
664 set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
672 a = get_DivMod_left(n);
673 b = get_DivMod_right(n);
674 mode = get_irn_mode(a);
676 if (!(mode_is_int(get_irn_mode(a)) &&
677 mode_is_int(get_irn_mode(b))))
681 a = new_Const (mode, get_mode_one(mode));
682 b = new_Const (mode, get_mode_null(mode));
688 if (tb != tarval_bad) {
689 if (tb == get_mode_one(get_tarval_mode(tb))) {
690 b = new_Const (mode, get_mode_null(mode));
692 } else if (ta != tarval_bad) {
694 resa = tarval_div (ta, tb);
695 if (resa == tarval_bad) break; /* Causes exception!!! Model by replacing through
696 Jmp for X result!? */
697 resb = tarval_mod (ta, tb);
698 if (resb == tarval_bad) break; /* Causes exception! */
699 a = new_Const (mode, resa);
700 b = new_Const (mode, resb);
703 } else if (ta == get_mode_null(get_tarval_mode(ta))) {
708 if (evaluated) { /* replace by tuple */
709 ir_node *mem = get_DivMod_mem(n);
710 turn_into_tuple(n, 4);
711 set_Tuple_pred(n, 0, mem);
712 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
713 set_Tuple_pred(n, 2, a);
714 set_Tuple_pred(n, 3, b);
715 assert(get_nodes_Block(n));
721 /* Replace the Cond by a Jmp if it branches on a constant
724 a = get_Cond_selector(n);
727 if ((ta != tarval_bad) &&
728 (get_irn_mode(a) == mode_b) &&
729 (get_opt_unreachable_code())) {
730 /* It's a boolean Cond, branching on a boolean constant.
731 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
732 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
733 turn_into_tuple(n, 2);
734 if (ta == tarval_b_true) {
735 set_Tuple_pred(n, 0, new_Bad());
736 set_Tuple_pred(n, 1, jmp);
738 set_Tuple_pred(n, 0, jmp);
739 set_Tuple_pred(n, 1, new_Bad());
741 /* We might generate an endless loop, so keep it alive. */
742 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
743 } else if ((ta != tarval_bad) &&
744 (get_irn_mode(a) == mode_Iu) &&
745 (get_Cond_kind(n) == dense) &&
746 (get_opt_unreachable_code())) {
747 /* I don't want to allow Tuples smaller than the biggest Proj.
748 Also this tuple might get really big...
749 I generate the Jmp here, and remember it in link. Link is used
750 when optimizing Proj. */
751 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
752 /* We might generate an endless loop, so keep it alive. */
753 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
754 } else if ((get_irn_op(get_Cond_selector(n)) == op_Eor)
755 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
756 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
757 /* The Eor is a negate. Generate a new Cond without the negate,
758 simulate the negate by exchanging the results. */
759 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
761 } else if ((get_irn_op(get_Cond_selector(n)) == op_Not)
762 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
763 /* A Not before the Cond. Generate a new Cond without the Not,
764 simulate the Not by exchanging the results. */
765 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
772 a = get_Proj_pred(n);
774 if ((get_irn_op(a) == op_Cond)
776 && get_irn_op(get_irn_link(a)) == op_Cond) {
777 /* Use the better Cond if the Proj projs from a Cond which get's
778 its result from an Eor/Not. */
779 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
780 || (get_irn_op(get_Cond_selector(a)) == op_Not))
781 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
782 && (get_irn_op(get_irn_link(a)) == op_Cond)
783 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
784 set_Proj_pred(n, get_irn_link(a));
785 if (get_Proj_proj(n) == 0)
789 } else if ((get_irn_op(a) == op_Cond)
790 && (get_irn_mode(get_Cond_selector(a)) == mode_Iu)
792 && (get_Cond_kind(a) == dense)
793 && (get_opt_unreachable_code())) {
794 /* The Cond is a Switch on a Constant */
795 if (get_Proj_proj(n) == tarval_to_long(value_of(a))) {
796 /* The always taken branch, reuse the existing Jmp. */
797 if (!get_irn_link(a)) /* well, if it exists ;-> */
798 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
799 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
801 } else {/* Not taken control flow, but be careful with the default! */
802 if (get_Proj_proj(n) < a->attr.c.default_proj){
803 /* a never taken branch */
806 a->attr.c.default_proj = get_Proj_proj(n);
811 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
813 b = get_Eor_right(n);
815 if ((get_irn_mode(n) == mode_b)
816 && (get_irn_op(a) == op_Proj)
817 && (get_irn_mode(a) == mode_b)
818 && (tarval_classify (computed_value (b)) == 1)
819 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
820 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
821 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
822 mode_b, get_negated_pnc(get_Proj_proj(a)));
823 else if ((get_irn_mode(n) == mode_b)
824 && (tarval_classify (computed_value (b)) == 1))
825 /* The Eor is a Not. Replace it by a Not. */
826 /* ????!!!Extend to bitfield 1111111. */
827 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
833 if ( (get_irn_mode(n) == mode_b)
834 && (get_irn_op(a) == op_Proj)
835 && (get_irn_mode(a) == mode_b)
836 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
837 /* We negate a Cmp. The Cmp has the negated result anyways! */
838 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
839 mode_b, get_negated_pnc(get_Proj_proj(a)));
847 /* **************** Common Subexpression Elimination **************** */
849 /* Compare function for two nodes in the hash table. Gets two */
850 /* nodes as parameters. Returns 0 if the nodes are a cse. */
852 vt_cmp (const void *elt, const void *key)
860 if (a == b) return 0;
862 if ((get_irn_op(a) != get_irn_op(b)) ||
863 (get_irn_mode(a) != get_irn_mode(b))) return 1;
865 /* compare if a's in and b's in are equal */
866 if (get_irn_arity (a) != get_irn_arity(b))
869 /* for block-local cse and pinned nodes: */
870 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
871 if (get_irn_n(a, -1) != get_irn_n(b, -1))
875 /* compare a->in[0..ins] with b->in[0..ins] */
876 for (i = 0; i < get_irn_arity(a); i++)
877 if (get_irn_n(a, i) != get_irn_n(b, i))
880 switch (get_irn_opcode(a)) {
882 return get_irn_const_attr (a) != get_irn_const_attr (b);
884 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
886 return get_Filter_proj(a) != get_Filter_proj(b);
888 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
889 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
891 return (get_irn_free_attr(a) != get_irn_free_attr(b));
893 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
894 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
896 return (get_irn_call_attr(a) != get_irn_call_attr(b));
898 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
899 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
900 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
901 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
902 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
904 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
906 return get_Cast_type(a) != get_Cast_type(b);
914 ir_node_hash (ir_node *node)
919 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
920 h = get_irn_arity(node);
922 /* consider all in nodes... except the block. */
923 for (i = 0; i < get_irn_arity(node); i++) {
924 h = 9*h + (unsigned long)get_irn_n(node, i);
928 h = 9*h + (unsigned long) get_irn_mode (node);
930 h = 9*h + (unsigned long) get_irn_op (node);
936 new_identities (void)
938 return new_pset (vt_cmp, TUNE_NIR_NODES);
942 del_identities (pset *value_table)
944 del_pset (value_table);
947 /* Return the canonical node computing the same value as n.
948 Looks up the node in a hash table. */
949 static INLINE ir_node *
950 identify (pset *value_table, ir_node *n)
954 if (!value_table) return n;
956 if (get_opt_reassociation()) {
957 switch (get_irn_opcode (n)) {
964 /* for commutative operators perform a OP b == b OP a */
965 if (get_binop_left(n) > get_binop_right(n)) {
966 ir_node *h = get_binop_left(n);
967 set_binop_left(n, get_binop_right(n));
968 set_binop_right(n, h);
976 o = pset_find (value_table, n, ir_node_hash (n));
982 /* During construction we set the pinned flag in the graph right when the
983 optimizatin is performed. The flag turning on procedure global cse could
984 be changed between two allocations. This way we are safe. */
985 static INLINE ir_node *
986 identify_cons (pset *value_table, ir_node *n) {
988 n = identify(value_table, n);
989 if (get_irn_n(old, -1) != get_irn_n(n, -1))
990 set_irg_pinned(current_ir_graph, floats);
994 /* Return the canonical node computing the same value as n.
995 Looks up the node in a hash table, enters it in the table
996 if it isn't there yet. */
998 identify_remember (pset *value_table, ir_node *node)
1002 if (!value_table) return node;
1004 /* lookup or insert in hash table with given hash key. */
1005 o = pset_insert (value_table, node, ir_node_hash (node));
1007 if (o == node) return node;
1013 add_identities (pset *value_table, ir_node *node) {
1014 identify_remember (value_table, node);
1017 /* garbage in, garbage out. If a node has a dead input, i.e., the
1018 Bad node is input to the node, return the Bad node. */
1019 static INLINE ir_node *
1020 gigo (ir_node *node)
1023 ir_op* op = get_irn_op(node);
1025 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1026 blocks predecessors is dead. */
1027 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1028 for (i = -1; i < get_irn_arity(node); i++) {
1029 if (is_Bad(get_irn_n(node, i))) {
1035 /* If Block has only Bads as predecessors it's garbage. */
1036 /* If Phi has only Bads as predecessors it's garbage. */
1037 if (op == op_Block || op == op_Phi) {
1038 for (i = 0; i < get_irn_arity(node); i++) {
1039 if (!is_Bad(get_irn_n(node, i))) break;
1041 if (i = get_irn_arity(node)) node = new_Bad();
1048 /* These optimizations deallocate nodes from the obstack.
1049 It can only be called if it is guaranteed that no other nodes
1050 reference this one, i.e., right after construction of a node. */
1052 optimize_node (ir_node *n)
1057 /* Allways optimize Phi nodes: part of the construction. */
1058 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1060 /* constant expression evaluation / constant folding */
1061 if (get_opt_constant_folding()) {
1062 /* constants can not be evaluated */
1063 if (get_irn_op(n) != op_Const) {
1064 /* try to evaluate */
1065 tv = computed_value (n);
1066 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1067 /* evaluation was succesful -- replace the node. */
1068 obstack_free (current_ir_graph->obst, n);
1069 return new_Const (get_tarval_mode (tv), tv);
1074 /* remove unnecessary nodes */
1075 if (get_opt_constant_folding() ||
1076 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1077 (get_irn_op(n) == op_Id) ||
1078 (get_irn_op(n) == op_Proj) ||
1079 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1080 n = equivalent_node (n);
1082 /** common subexpression elimination **/
1083 /* Checks whether n is already available. */
1084 /* The block input is used to distinguish different subexpressions. Right
1085 now all nodes are pinned to blocks, i.e., the cse only finds common
1086 subexpressions within a block. */
1088 n = identify_cons (current_ir_graph->value_table, n);
1091 /* We found an existing, better node, so we can deallocate the old node. */
1092 obstack_free (current_ir_graph->obst, old_n);
1095 /* Some more constant expression evaluation that does not allow to
1097 if (get_opt_constant_folding() ||
1098 (get_irn_op(n) == op_Cond) ||
1099 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1100 n = transform_node (n);
1102 /* Remove nodes with dead (Bad) input.
1103 Run always for transformation induced Bads. */
1106 /* Now we can verify the node, as it has no dead inputs any more. */
1109 /* Now we have a legal, useful node. Enter it in hash table for cse */
1110 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1111 n = identify_remember (current_ir_graph->value_table, n);
1118 /* These optimizations never deallocate nodes. This can cause dead
1119 nodes lying on the obstack. Remove these by a dead node elimination,
1120 i.e., a copying garbage collection. */
1122 optimize_in_place_2 (ir_node *n)
1127 if (!get_optimize() && (get_irn_op(n) != op_Phi)) return n;
1129 /* if not optimize return n */
1132 /* Here this is possible. Why? */
1137 /* constant expression evaluation / constant folding */
1138 if (get_opt_constant_folding()) {
1139 /* constants can not be evaluated */
1140 if (get_irn_op(n) != op_Const) {
1141 /* try to evaluate */
1142 tv = computed_value (n);
1143 if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1144 /* evaluation was succesful -- replace the node. */
1145 n = new_Const (get_tarval_mode (tv), tv);
1146 __dbg_info_merge_pair(n, old_n, dbg_const_eval);
1152 /* remove unnecessary nodes */
1153 /*if (get_opt_constant_folding()) */
1154 if (get_opt_constant_folding() ||
1155 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1156 (get_irn_op(n) == op_Id) || /* ... */
1157 (get_irn_op(n) == op_Proj) || /* ... */
1158 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1159 n = equivalent_node (n);
1161 /** common subexpression elimination **/
1162 /* Checks whether n is already available. */
1163 /* The block input is used to distinguish different subexpressions. Right
1164 now all nodes are pinned to blocks, i.e., the cse only finds common
1165 subexpressions within a block. */
1166 if (get_opt_cse()) {
1167 n = identify (current_ir_graph->value_table, n);
1170 /* Some more constant expression evaluation. */
1171 if (get_opt_constant_folding() ||
1172 (get_irn_op(n) == op_Cond) ||
1173 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1174 n = transform_node (n);
1176 /* Remove nodes with dead (Bad) input.
1177 Run always for transformation induced Bads. */
1180 /* Now we can verify the node, as it has no dead inputs any more. */
1183 /* Now we have a legal, useful node. Enter it in hash table for cse.
1184 Blocks should be unique anyways. (Except the successor of start:
1185 is cse with the start block!) */
1186 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1187 n = identify_remember (current_ir_graph->value_table, n);
1192 /* Wrapper for external use, set proper status bits after optimization */
1194 optimize_in_place (ir_node *n) {
1195 /* Handle graph state */
1196 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1197 if (get_opt_global_cse())
1198 set_irg_pinned(current_ir_graph, floats);
1199 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1200 set_irg_outs_inconsistent(current_ir_graph);
1201 /* Maybe we could also test whether optimizing the node can
1202 change the control graph. */
1203 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1204 set_irg_dom_inconsistent(current_ir_graph);
1205 return optimize_in_place_2 (n);