1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Christian Schaefer, Goetz Lindenmaier
6 ** iropt --- optimizations intertwined with IR construction.
15 # include "irnode_t.h"
16 # include "irgraph_t.h"
23 # include "dbginfo_t.h"
25 /* Make types visible to allow most efficient access */
26 # include "entity_t.h"
28 /* Trivial inlineable routine for copy propagation.
29 Does follow Ids, needed to optimize inlined code. */
30 static inline ir_node *
31 follow_Id (ir_node *n)
33 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
37 static inline tarval *
40 if ((n != NULL) && (get_irn_op(n) == op_Const))
41 return get_Const_tarval(n);
46 /* if n can be computed, return the value, else NULL. Performs
47 constant folding. GL: Only if n is arithmetic operator? */
49 computed_value (ir_node *n)
53 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
54 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
58 /* get the operands we will work on for simple cases. */
60 a = get_binop_left(n);
61 b = get_binop_right(n);
62 } else if (is_unop(n)) {
66 /* if the operands are constants, get the target value, else set it NULL.
67 (a and b may be NULL if we treat a node that is no computation.) */
71 /* Perform the constant evaluation / computation. */
72 switch (get_irn_opcode(n)) {
74 res = get_Const_tarval(n);
77 if ((get_SymConst_kind(n) == size) &&
78 (get_type_state(get_SymConst_type(n))) == layout_fixed)
79 res = tarval_from_long (mode_i, get_type_size(get_SymConst_type(n)));
82 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
83 && (get_irn_mode(a) != mode_p)) {
84 res = tarval_add (ta, tb);
88 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
89 && (get_irn_mode(a) != mode_p)) {
90 res = tarval_sub (ta, tb);
92 res = tarval_mode_null [get_irn_modecode (n)];
96 if (ta && mode_is_float(get_irn_mode(a)))
97 res = tarval_neg (ta);
100 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
101 res = tarval_mul (ta, tb);
103 /* a*0 = 0 or 0*b = 0:
104 calls computed_value recursive and returns the 0 with proper
107 if ( (tarval_classify ((v = computed_value (a))) == 0)
108 || (tarval_classify ((v = computed_value (b))) == 0)) {
114 /* This was missing in original implementation. Why? */
115 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
116 if (tarval_classify(tb) == 0) {res = NULL; break;}
117 res = tarval_quo(ta, tb);
121 /* This was missing in original implementation. Why? */
122 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
123 if (tarval_classify(tb) == 0) {res = NULL; break;}
124 res = tarval_div(ta, tb);
128 /* This was missing in original implementation. Why? */
129 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
130 if (tarval_classify(tb) == 0) {res = NULL; break;}
131 res = tarval_mod(ta, tb);
134 /* for iro_DivMod see iro_Proj */
137 res = tarval_abs (ta);
141 res = tarval_and (ta, tb);
144 if ( (tarval_classify ((v = computed_value (a))) == 0)
145 || (tarval_classify ((v = computed_value (b))) == 0)) {
152 res = tarval_or (ta, tb);
155 if ( (tarval_classify ((v = computed_value (a))) == -1)
156 || (tarval_classify ((v = computed_value (b))) == -1)) {
161 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
162 case iro_Not: if (ta) { res = tarval_neg (ta); } break;
163 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
164 /* tarval_shr is faulty !! */
165 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
166 case iro_Shrs:if (ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
167 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
168 case iro_Conv:if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
170 case iro_Proj: /* iro_Cmp */
174 a = get_Proj_pred(n);
175 /* Optimize Cmp nodes.
176 This performs a first step of unreachable code elimination.
177 Proj can not be computed, but folding a Cmp above the Proj here is
178 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
180 There are several case where we can evaluate a Cmp node:
181 1. The nodes compared are both the same. If we compare for
182 equal, this will return true, else it will return false.
183 This step relies on cse.
184 2. The predecessors of Cmp are target values. We can evaluate
186 3. The predecessors are Allocs or void* constants. Allocs never
187 return NULL, they raise an exception. Therefore we can predict
189 if (get_irn_op(a) == op_Cmp) {
190 aa = get_Cmp_left(a);
191 ab = get_Cmp_right(a);
192 if (aa == ab) { /* 1.: */
193 /* This is a tric with the bits used for encoding the Cmp
194 Proj numbers, the following statement is not the same:
195 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
196 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
198 tarval *taa = computed_value (aa);
199 tarval *tab = computed_value (ab);
200 if (taa && tab) { /* 2.: */
201 /* strange checks... */
202 ir_pncmp flags = tarval_comp (taa, tab);
203 if (flags != irpn_False) {
204 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
206 } else { /* check for 3.: */
207 ir_node *aaa = skip_nop(skip_Proj(aa));
208 ir_node *aba = skip_nop(skip_Proj(ab));
209 if ( ( (/* aa is ProjP and aaa is Alloc */
210 (get_irn_op(aa) == op_Proj)
211 && (get_irn_mode(aa) == mode_p)
212 && (get_irn_op(aaa) == op_Alloc))
213 && ( (/* ab is constant void */
214 (get_irn_op(ab) == op_Const)
215 && (get_irn_mode(ab) == mode_p)
216 && (get_Const_tarval(ab) == tarval_p_void))
217 || (/* ab is other Alloc */
218 (get_irn_op(ab) == op_Proj)
219 && (get_irn_mode(ab) == mode_p)
220 && (get_irn_op(aba) == op_Alloc)
222 || (/* aa is void and aba is Alloc */
223 (get_irn_op(aa) == op_Const)
224 && (get_irn_mode(aa) == mode_p)
225 && (get_Const_tarval(aa) == tarval_p_void)
226 && (get_irn_op(ab) == op_Proj)
227 && (get_irn_mode(ab) == mode_p)
228 && (get_irn_op(aba) == op_Alloc)))
230 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
233 } else if (get_irn_op(a) == op_DivMod) {
234 ta = value_of(get_DivMod_left(a));
235 tb = value_of(get_DivMod_right(a));
236 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
237 if (tarval_classify(tb) == 0) {res = NULL; break;}
238 if (get_Proj_proj(n)== 0) /* Div */
239 res = tarval_div(ta, tb);
241 res = tarval_mod(ta, tb);
254 /* returns 1 if the a and b are pointers to different locations. */
256 different_identity (ir_node *a, ir_node *b)
258 assert (get_irn_mode (a) == mode_p
259 && get_irn_mode (b) == mode_p);
261 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
262 ir_node *a1 = get_Proj_pred (a);
263 ir_node *b1 = get_Proj_pred (b);
264 if (a1 != b1 && get_irn_op (a1) == op_Alloc
265 && get_irn_op (b1) == op_Alloc)
272 /* equivalent_node returns a node equivalent to N. It skips all nodes that
273 perform no actual computation, as, e.g., the Id nodes. It does not create
274 new nodes. It is therefore safe to free N if the node returned is not N.
275 If a node returns a Tuple we can not just skip it. If the size of the
276 in array fits, we transform n into a tuple (e.g., Div). */
278 equivalent_node (ir_node *n)
281 ir_node *a = NULL; /* to shutup gcc */
282 ir_node *b = NULL; /* to shutup gcc */
283 ir_node *c = NULL; /* to shutup gcc */
285 ins = get_irn_arity (n);
287 /* get the operands we will work on */
289 a = get_binop_left(n);
290 b = get_binop_right(n);
291 } else if (is_unop(n)) {
295 /* skip unnecessary nodes. */
296 switch (get_irn_opcode (n)) {
299 /* The Block constructor does not call optimize, but mature_block
300 calls the optimization. */
301 assert(get_Block_matured(n));
303 /* Straightening: a single entry Block following a single exit Block
304 can be merged, if it is not the Start block. */
305 /* !!! Beware, all Phi-nodes of n must have been optimized away.
306 This should be true, as the block is matured before optimize is called.
307 But what about Phi-cycles with the Phi0/Id that could not be resolved?
308 Remaining Phi nodes are just Ids. */
309 if ((get_Block_n_cfgpreds(n) == 1) &&
310 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
311 (get_opt_control_flow())) {
312 n = get_nodes_Block(get_Block_cfgpred(n, 0));
313 } else if ((get_Block_n_cfgpreds(n) == 2) &&
314 (get_opt_control_flow())) {
315 /* Test whether Cond jumps twice to this block
316 @@@ we could do this also with two loops finding two preds from several ones. */
317 a = get_Block_cfgpred(n, 0);
318 b = get_Block_cfgpred(n, 1);
319 if ((get_irn_op(a) == op_Proj) &&
320 (get_irn_op(b) == op_Proj) &&
321 (get_Proj_pred(a) == get_Proj_pred(b)) &&
322 (get_irn_op(get_Proj_pred(a)) == op_Cond)) {
323 /* Also a single entry Block following a single exit Block. Phis have
324 twice the same operand and will be optimized away. */
325 n = get_nodes_Block(a);
327 } else if (get_opt_unreachable_code() &&
328 (n != current_ir_graph->start_block) &&
329 (n != current_ir_graph->end_block) ) {
331 /* If all inputs are dead, this block is dead too, except if it is
332 the start or end block. This is a step of unreachable code
334 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
335 if (!is_Bad(get_Block_cfgpred(n, i))) break;
337 if (i == get_Block_n_cfgpreds(n))
343 case iro_Jmp: /* GL: Why not same for op_Raise?? */
344 /* unreachable code elimination */
345 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
347 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
348 See cases for iro_Cond and iro_Proj in transform_node. */
349 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
350 case iro_Or: if (a == b) {n = a; break;}
355 /* After running compute_node there is only one constant predecessor.
356 Find this predecessors value and remember the other node: */
357 if ((tv = computed_value (a))) {
359 } else if ((tv = computed_value (b))) {
363 /* If this predecessors constant value is zero, the operation is
364 unnecessary. Remove it: */
365 if (tarval_classify (tv) == 0) {
375 /* these operations are not commutative. Test only one predecessor. */
376 if (tarval_classify (computed_value (b)) == 0) {
378 /* Test if b > #bits of a ==> return 0 / divide b by #bits
379 --> transform node? */
382 case iro_Not: /* NotNot x == x */
383 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
384 out of bounds exception if min =! max? */
385 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
386 n = get_unop_op(get_unop_op(n));
389 /* Mul is commutative and has again an other neutral element. */
390 if (tarval_classify (computed_value (a)) == 1) {
392 } else if (tarval_classify (computed_value (b)) == 1) {
397 /* Div is not commutative. */
398 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
399 /* Turn Div into a tuple (mem, bad, a) */
400 ir_node *mem = get_Div_mem(n);
401 turn_into_tuple(n, 3);
402 set_Tuple_pred(n, 0, mem);
403 set_Tuple_pred(n, 1, new_Bad());
404 set_Tuple_pred(n, 2, a);
407 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
408 treated in transform node.
409 case iro_Mod, Quot, DivMod
413 /* And has it's own neutral element */
414 else if (tarval_classify (computed_value (a)) == -1) {
416 } else if (tarval_classify (computed_value (b)) == -1) {
421 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
423 } else if (get_irn_mode(n) == mode_b) {
424 if (get_irn_op(a) == op_Conv &&
425 get_irn_mode (get_Conv_op(a)) == mode_b) {
426 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
433 /* Several optimizations:
434 - no Phi in start block.
435 - remove Id operators that are inputs to Phi
436 - fold Phi-nodes, iff they have only one predecessor except
441 ir_node *block = NULL; /* to shutup gcc */
442 ir_node *first_val = NULL; /* to shutup gcc */
443 ir_node *scnd_val = NULL; /* to shutup gcc */
445 n_preds = get_Phi_n_preds(n);
447 block = get_nodes_Block(n);
448 if ((is_Bad(block)) || /* Control dead */
449 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
450 return new_Bad(); /* in the Start Block. */
452 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
455 /* first we test for a special case: */
456 /* Confirm is a special node fixing additional information for a
457 value that is known at a certain point. This is useful for
458 dataflow analysis. */
460 ir_node *a = follow_Id (get_Phi_pred(n, 0));
461 ir_node *b = follow_Id (get_Phi_pred(n, 1));
462 if ( (get_irn_op(a) == op_Confirm)
463 && (get_irn_op(b) == op_Confirm)
464 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
465 && (get_irn_n(a, 1) == get_irn_n (b, 1))
466 && (a->data.num == (~b->data.num & irpn_True) )) {
467 n = follow_Id (get_irn_n(a, 0));
473 /* Find first non-self-referencing input */
474 for (i = 0; i < n_preds; ++i) {
475 first_val = follow_Id(get_Phi_pred(n, i));
477 set_Phi_pred(n, i, first_val);
478 if ( (first_val != n) /* not self pointer */
479 && (get_irn_op(first_val) != op_Bad) /* value not dead */
480 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
481 break; /* then found first value. */
485 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
486 if (i >= n_preds) { n = new_Bad(); break; }
490 /* follow_Id () for rest of inputs, determine if any of these
491 are non-self-referencing */
492 while (++i < n_preds) {
493 scnd_val = follow_Id(get_Phi_pred(n, i));
495 set_Phi_pred(n, i, scnd_val);
497 && (scnd_val != first_val)
498 && (get_irn_op(scnd_val) != op_Bad)
499 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
504 /* Fold, if no multiple distinct non-self-referencing inputs */
508 /* skip the remaining Ids. */
509 while (++i < n_preds) {
510 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
518 #if 0 /* Is an illegal transformation: different nodes can
519 represent the same pointer value!! */
520 a = skip_Proj(get_Load_mem(n));
523 if (get_irn_op(a) == op_Store) {
524 if ( different_identity (b, get_Store_ptr(a))) {
525 /* load and store use different pointers, therefore load
526 needs not take store's memory but the state before. */
527 set_Load_mem (n, get_Store_mem(a));
528 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
535 /* remove unnecessary store. */
537 a = skip_Proj(get_Store_mem(n));
538 b = get_Store_ptr(n);
539 c = skip_Proj(get_Store_value(n));
541 if (get_irn_op(a) == op_Store
542 && get_Store_ptr(a) == b
543 && skip_Proj(get_Store_value(a)) == c) {
544 /* We have twice exactly the same store -- a write after write. */
546 } else if (get_irn_op(c) == op_Load
547 && (a == c || skip_Proj(get_Load_mem(c)) == a)
548 && get_Load_ptr(c) == b )
549 /* !!!??? and a cryptic test */ {
550 /* We just loaded the value from the same memory, i.e., the store
551 doesn't change the memory -- a write after read. */
552 a = get_Store_mem(n);
553 turn_into_tuple(n, 2);
554 set_Tuple_pred(n, 0, a);
555 set_Tuple_pred(n, 1, new_Bad());
562 a = get_Proj_pred(n);
564 if ( get_irn_op(a) == op_Tuple) {
565 /* Remove the Tuple/Proj combination. */
566 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
567 n = get_Tuple_pred(a, get_Proj_proj(n));
569 assert(0); /* This should not happen! */
572 } else if (get_irn_mode(n) == mode_X &&
573 is_Bad(get_nodes_Block(n))) {
574 /* Remove dead control flow. */
588 } /* end equivalent_node() */
591 /* tries several [inplace] [optimizing] transformations and returns an
592 equivalent node. The difference to equivalent_node is that these
593 transformations _do_ generate new nodes, and thus the old node must
594 not be freed even if the equivalent node isn't the old one. */
596 transform_node (ir_node *n)
599 ir_node *a = NULL, *b;
602 switch (get_irn_opcode(n)) {
604 ta = computed_value(n);
606 /* Turn Div into a tuple (mem, bad, value) */
607 ir_node *mem = get_Div_mem(n);
608 turn_into_tuple(n, 3);
609 set_Tuple_pred(n, 0, mem);
610 set_Tuple_pred(n, 1, new_Bad());
611 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
615 ta = computed_value(n);
617 /* Turn Div into a tuple (mem, bad, value) */
618 ir_node *mem = get_Mod_mem(n);
619 turn_into_tuple(n, 3);
620 set_Tuple_pred(n, 0, mem);
621 set_Tuple_pred(n, 1, new_Bad());
622 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
630 a = get_DivMod_left(n);
631 b = get_DivMod_right(n);
632 mode = get_irn_mode(a);
634 if (!(mode_is_int(get_irn_mode(a)) &&
635 mode_is_int(get_irn_mode(b))))
639 a = new_Const (mode, tarval_from_long (mode, 1));
640 b = new_Const (mode, tarval_from_long (mode, 0));
647 if (tarval_classify(tb) == 1) {
648 b = new_Const (mode, tarval_from_long (mode, 0));
652 resa = tarval_div (ta, tb);
653 if (!resa) break; /* Causes exception!!! Model by replacing through
654 Jmp for X result!? */
655 resb = tarval_mod (ta, tb);
656 if (!resb) break; /* Causes exception! */
657 a = new_Const (mode, resa);
658 b = new_Const (mode, resb);
661 } else if (tarval_classify (ta) == 0) {
666 if (evaluated) { /* replace by tuple */
667 ir_node *mem = get_DivMod_mem(n);
668 turn_into_tuple(n, 4);
669 set_Tuple_pred(n, 0, mem);
670 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
671 set_Tuple_pred(n, 2, a);
672 set_Tuple_pred(n, 3, b);
673 assert(get_nodes_Block(n));
679 /* Replace the Cond by a Jmp if it branches on a constant
682 a = get_Cond_selector(n);
686 (get_irn_mode(a) == mode_b) &&
687 (get_opt_unreachable_code())) {
688 /* It's a boolean Cond, branching on a boolean constant.
689 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
690 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
691 turn_into_tuple(n, 2);
692 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
693 set_Tuple_pred(n, 0, new_Bad());
694 set_Tuple_pred(n, 1, jmp);
696 set_Tuple_pred(n, 0, jmp);
697 set_Tuple_pred(n, 1, new_Bad());
699 /* We might generate an endless loop, so keep it alive. */
700 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
702 (get_irn_mode(a) == mode_I) &&
703 (get_Cond_kind(n) == dense) &&
704 (get_opt_unreachable_code())) {
705 /* I don't want to allow Tuples smaller than the biggest Proj.
706 Also this tuple might get really big...
707 I generate the Jmp here, and remember it in link. Link is used
708 when optimizing Proj. */
709 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
710 /* We might generate an endless loop, so keep it alive. */
711 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
712 } else if ((get_irn_op(get_Cond_selector(n)) == op_Eor)
713 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
714 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
715 /* The Eor is a negate. Generate a new Cond without the negate,
716 simulate the negate by exchanging the results. */
717 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
719 } else if ((get_irn_op(get_Cond_selector(n)) == op_Not)
720 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
721 /* A Not before the Cond. Generate a new Cond without the Not,
722 simulate the Not by exchanging the results. */
723 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
730 a = get_Proj_pred(n);
732 if ((get_irn_op(a) == op_Cond)
734 && get_irn_op(get_irn_link(a)) == op_Cond) {
735 /* Use the better Cond if the Proj projs from a Cond which get's
736 its result from an Eor/Not. */
737 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
738 || (get_irn_op(get_Cond_selector(a)) == op_Not))
739 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
740 && (get_irn_op(get_irn_link(a)) == op_Cond)
741 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
742 set_Proj_pred(n, get_irn_link(a));
743 if (get_Proj_proj(n) == 0)
747 } else if ((get_irn_op(a) == op_Cond)
748 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
750 && (get_Cond_kind(a) == dense)
751 && (get_opt_unreachable_code())) {
752 /* The Cond is a Switch on a Constant */
753 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
754 /* The always taken branch, reuse the existing Jmp. */
755 if (!get_irn_link(a)) /* well, if it exists ;-> */
756 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
757 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
759 } else {/* Not taken control flow, but be careful with the default! */
760 if (get_Proj_proj(n) < a->attr.c.default_proj){
761 /* a never taken branch */
764 a->attr.c.default_proj = get_Proj_proj(n);
769 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
771 b = get_Eor_right(n);
773 if ((get_irn_mode(n) == mode_b)
774 && (get_irn_op(a) == op_Proj)
775 && (get_irn_mode(a) == mode_b)
776 && (tarval_classify (computed_value (b)) == 1)
777 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
778 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
779 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
780 mode_b, get_negated_pnc(get_Proj_proj(a)));
781 else if ((get_irn_mode(n) == mode_b)
782 && (tarval_classify (computed_value (b)) == 1))
783 /* The Eor is a Not. Replace it by a Not. */
784 /* ????!!!Extend to bitfield 1111111. */
785 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
791 if ( (get_irn_mode(n) == mode_b)
792 && (get_irn_op(a) == op_Proj)
793 && (get_irn_mode(a) == mode_b)
794 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
795 /* We negate a Cmp. The Cmp has the negated result anyways! */
796 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
797 mode_b, get_negated_pnc(get_Proj_proj(a)));
805 /* **************** Common Subexpression Elimination **************** */
807 /* Compare function for two nodes in the hash table. Gets two */
808 /* nodes as parameters. Returns 0 if the nodes are a cse. */
810 vt_cmp (const void *elt, const void *key)
818 if (a == b) return 0;
820 if ((get_irn_op(a) != get_irn_op(b)) ||
821 (get_irn_mode(a) != get_irn_mode(b))) return 1;
823 /* compare if a's in and b's in are equal */
824 /* GL: we optimize only nodes with in arrays of fixed sizes.
825 if (get_irn_arity (a) != -2) {
826 ins = get_irn_arity (a);
827 if (ins != get_irn_arity (b)) return 1;
828 ain = get_irn_in (a);
829 bin = get_irn_in (b);
832 if (get_irn_arity (a) != get_irn_arity(b))
835 /* for block-local cse and pinned nodes: */
836 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
837 if (get_irn_n(a, -1) != get_irn_n(b, -1))
841 /* compare a->in[0..ins] with b->in[0..ins] */
842 for (i = 0; i < get_irn_arity(a); i++)
843 if (get_irn_n(a, i) != get_irn_n(b, i))
846 switch (get_irn_opcode(a)) {
848 return get_irn_const_attr (a) != get_irn_const_attr (b);
850 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
852 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
853 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
855 return (get_irn_free_attr(a) != get_irn_free_attr(b));
857 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
858 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
860 return (get_irn_call_attr(a) != get_irn_call_attr(b));
862 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
863 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
864 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
865 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
866 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
867 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
869 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
877 ir_node_hash (ir_node *node)
882 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
883 h = get_irn_arity(node);
885 /* consider all in nodes... except the block. */
886 for (i = 0; i < get_irn_arity(node); i++) {
887 h = 9*h + (unsigned long)get_irn_n(node, i);
891 h = 9*h + (unsigned long) get_irn_mode (node);
893 h = 9*h + (unsigned long) get_irn_op (node);
899 new_identities (void)
901 return new_pset (vt_cmp, TUNE_NIR_NODES);
905 del_identities (pset *value_table)
907 del_pset (value_table);
910 /* Return the canonical node computing the same value as n.
911 Looks up the node in a hash table. */
912 static inline ir_node *
913 identify (pset *value_table, ir_node *n)
917 if (!value_table) return n;
919 if (get_opt_reassociation()) {
920 switch (get_irn_opcode (n)) {
927 /* for commutative operators perform a OP b == b OP a */
928 if (get_binop_left(n) > get_binop_right(n)) {
929 ir_node *h = get_binop_left(n);
930 set_binop_left(n, get_binop_right(n));
931 set_binop_right(n, h);
939 o = pset_find (value_table, n, ir_node_hash (n));
945 /* During construction we set the pinned flag in the graph right when the
946 optimizatin is performed. The flag turning on procedure global cse could
947 be changed between two allocations. This way we are safe. */
948 static inline ir_node *
949 identify_cons (pset *value_table, ir_node *n) {
951 n = identify(value_table, n);
952 if (get_irn_n(old, -1) != get_irn_n(n, -1))
953 set_irg_pinned(current_ir_graph, floats);
957 /* Return the canonical node computing the same value as n.
958 Looks up the node in a hash table, enters it in the table
959 if it isn't there yet. */
961 identify_remember (pset *value_table, ir_node *node)
965 if (!value_table) return node;
967 /* lookup or insert in hash table with given hash key. */
968 o = pset_insert (value_table, node, ir_node_hash (node));
970 if (o == node) return node;
976 add_identities (pset *value_table, ir_node *node) {
977 identify_remember (value_table, node);
980 /* garbage in, garbage out. If a node has a dead input, i.e., the
981 Bad node is input to the node, return the Bad node. */
982 static inline ir_node *
986 ir_op* op = get_irn_op(node);
988 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
989 blocks predecessors is dead. */
990 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
991 for (i = -1; i < get_irn_arity(node); i++) {
992 if (is_Bad(get_irn_n(node, i))) {
998 /* If Block has only Bads as predecessors it's garbage. */
999 /* If Phi has only Bads as predecessors it's garbage. */
1000 if (op == op_Block || op == op_Phi) {
1001 for (i = 0; i < get_irn_arity(node); i++) {
1002 if (!is_Bad(get_irn_n(node, i))) break;
1004 if (i = get_irn_arity(node)) node = new_Bad();
1011 /* These optimizations deallocate nodes from the obstack.
1012 It can only be called if it is guaranteed that no other nodes
1013 reference this one, i.e., right after construction of a node. */
1015 optimize (ir_node *n)
1020 /* Allways optimize Phi nodes: part of the construction. */
1021 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1023 /* constant expression evaluation / constant folding */
1024 if (get_opt_constant_folding()) {
1025 /* constants can not be evaluated */
1026 if (get_irn_op(n) != op_Const) {
1027 /* try to evaluate */
1028 tv = computed_value (n);
1029 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1030 /* evaluation was succesful -- replace the node. */
1031 obstack_free (current_ir_graph->obst, n);
1032 return new_Const (get_tv_mode (tv), tv);
1037 /* remove unnecessary nodes */
1038 if (get_opt_constant_folding() ||
1039 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1040 (get_irn_op(n) == op_Id) ||
1041 (get_irn_op(n) == op_Proj) ||
1042 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1043 n = equivalent_node (n);
1045 /** common subexpression elimination **/
1046 /* Checks whether n is already available. */
1047 /* The block input is used to distinguish different subexpressions. Right
1048 now all nodes are pinned to blocks, i.e., the cse only finds common
1049 subexpressions within a block. */
1051 n = identify_cons (current_ir_graph->value_table, n);
1054 /* We found an existing, better node, so we can deallocate the old node. */
1055 obstack_free (current_ir_graph->obst, old_n);
1058 /* Some more constant expression evaluation that does not allow to
1060 if (get_opt_constant_folding() ||
1061 (get_irn_op(n) == op_Cond) ||
1062 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1063 n = transform_node (n);
1065 /* Remove nodes with dead (Bad) input.
1066 Run always for transformation induced Bads. */
1069 /* Now we can verify the node, as it has no dead inputs any more. */
1072 /* Now we have a legal, useful node. Enter it in hash table for cse */
1073 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1074 n = identify_remember (current_ir_graph->value_table, n);
1081 /* These optimizations never deallocate nodes. This can cause dead
1082 nodes lying on the obstack. Remove these by a dead node elimination,
1083 i.e., a copying garbage collection. */
1085 optimize_in_place_2 (ir_node *n)
1090 if (!get_optimize() && (get_irn_op(n) != op_Phi)) return n;
1092 /* if not optimize return n */
1095 /* Here this is possible. Why? */
1100 /* constant expression evaluation / constant folding */
1101 if (get_opt_constant_folding()) {
1102 /* constants can not be evaluated */
1103 if (get_irn_op(n) != op_Const) {
1104 /* try to evaluate */
1105 tv = computed_value (n);
1106 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1107 /* evaluation was succesful -- replace the node. */
1108 n = new_Const (get_tv_mode (tv), tv);
1109 __dbg_info_merge_pair(n, old_n, id_from_str("const_eval", 10));
1111 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1116 /* remove unnecessary nodes */
1117 /*if (get_opt_constant_folding()) */
1118 if (get_opt_constant_folding() ||
1119 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1120 (get_irn_op(n) == op_Id) ||
1121 (get_irn_op(n) == op_Proj) ||
1122 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1123 n = equivalent_node (n);
1125 /** common subexpression elimination **/
1126 /* Checks whether n is already available. */
1127 /* The block input is used to distinguish different subexpressions. Right
1128 now all nodes are pinned to blocks, i.e., the cse only finds common
1129 subexpressions within a block. */
1130 if (get_opt_cse()) {
1131 n = identify (current_ir_graph->value_table, n);
1134 /* Some more constant expression evaluation. */
1135 if (get_opt_constant_folding() ||
1136 (get_irn_op(n) == op_Cond) ||
1137 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1138 n = transform_node (n);
1140 /* Remove nodes with dead (Bad) input.
1141 Run always for transformation induced Bads. */
1144 /* Now we can verify the node, as it has no dead inputs any more. */
1147 /* Now we have a legal, useful node. Enter it in hash table for cse.
1148 Blocks should be unique anyways. (Except the successor of start:
1149 is cse with the start block!) */
1150 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1151 n = identify_remember (current_ir_graph->value_table, n);
1156 /* Wrapper for external use, set proper status bits after optimization */
1158 optimize_in_place (ir_node *n) {
1159 /* Handle graph state */
1160 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1161 if (get_opt_global_cse())
1162 set_irg_pinned(current_ir_graph, floats);
1163 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1164 set_irg_outs_inconsistent(current_ir_graph);
1165 /* Maybe we could also test whether optimizing the node can
1166 change the control graph. */
1167 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1168 set_irg_dom_inconsistent(current_ir_graph);
1169 return optimize_in_place_2 (n);