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"
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);
76 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
77 && (get_irn_mode(a) != mode_p)) {
78 res = tarval_add (ta, tb);
82 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
83 && (get_irn_mode(a) != mode_p)) {
84 res = tarval_sub (ta, tb);
86 res = tarval_mode_null [get_irn_modecode (n)];
90 if (ta && mode_is_float(get_irn_mode(a)))
91 res = tarval_neg (ta);
94 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
95 res = tarval_mul (ta, tb);
97 /* a*0 = 0 or 0*b = 0:
98 calls computed_value recursive and returns the 0 with proper
101 if ( (tarval_classify ((v = computed_value (a))) == 0)
102 || (tarval_classify ((v = computed_value (b))) == 0)) {
108 /* This was missing in original implementation. Why? */
109 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
110 if (tarval_classify(tb) == 0) {res = NULL; break;}
111 res = tarval_quo(ta, tb);
115 /* This was missing in original implementation. Why? */
116 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
117 if (tarval_classify(tb) == 0) {res = NULL; break;}
118 res = tarval_div(ta, tb);
122 /* This was missing in original implementation. Why? */
123 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
124 if (tarval_classify(tb) == 0) {res = NULL; break;}
125 res = tarval_mod(ta, tb);
128 /* for iro_DivMod see iro_Proj */
131 res = tarval_abs (ta);
135 res = tarval_and (ta, tb);
138 if ( (tarval_classify ((v = computed_value (a))) == 0)
139 || (tarval_classify ((v = computed_value (b))) == 0)) {
146 res = tarval_or (ta, tb);
149 if ( (tarval_classify ((v = computed_value (a))) == -1)
150 || (tarval_classify ((v = computed_value (b))) == -1)) {
155 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
156 case iro_Not: if (ta) { res = tarval_neg (ta); } break;
157 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
158 /* tarval_shr is faulty !! */
159 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
160 case iro_Shrs:if (ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
161 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
162 case iro_Conv:if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
164 case iro_Proj: /* iro_Cmp */
168 a = get_Proj_pred(n);
169 /* Optimize Cmp nodes.
170 This performs a first step of unreachable code elimination.
171 Proj can not be computed, but folding a Cmp above the Proj here is
172 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
174 There are several case where we can evaluate a Cmp node:
175 1. The nodes compared are both the same. If we compare for
176 equal, this will return true, else it will return false.
177 This step relies on cse.
178 2. The predecessors of Cmp are target values. We can evaluate
180 3. The predecessors are Allocs or void* constants. Allocs never
181 return NULL, they raise an exception. Therefore we can predict
183 if (get_irn_op(a) == op_Cmp) {
184 aa = get_Cmp_left(a);
185 ab = get_Cmp_right(a);
186 if (aa == ab) { /* 1.: */
187 /* This is a tric with the bits used for encoding the Cmp
188 Proj numbers, the following statement is not the same:
189 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
190 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
192 tarval *taa = computed_value (aa);
193 tarval *tab = computed_value (ab);
194 if (taa && tab) { /* 2.: */
195 /* strange checks... */
196 ir_pncmp flags = tarval_comp (taa, tab);
197 if (flags != irpn_False) {
198 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
200 } else { /* check for 3.: */
201 ir_node *aaa = skip_nop(skip_Proj(aa));
202 ir_node *aba = skip_nop(skip_Proj(ab));
203 if ( ( (/* aa is ProjP and aaa is Alloc */
204 (get_irn_op(aa) == op_Proj)
205 && (get_irn_mode(aa) == mode_p)
206 && (get_irn_op(aaa) == op_Alloc))
207 && ( (/* ab is constant void */
208 (get_irn_op(ab) == op_Const)
209 && (get_irn_mode(ab) == mode_p)
210 && (get_Const_tarval(ab) == tarval_p_void))
211 || (/* ab is other Alloc */
212 (get_irn_op(ab) == op_Proj)
213 && (get_irn_mode(ab) == mode_p)
214 && (get_irn_op(aba) == op_Alloc)
216 || (/* aa is void and aba is Alloc */
217 (get_irn_op(aa) == op_Const)
218 && (get_irn_mode(aa) == mode_p)
219 && (get_Const_tarval(aa) == tarval_p_void)
220 && (get_irn_op(ab) == op_Proj)
221 && (get_irn_mode(ab) == mode_p)
222 && (get_irn_op(aba) == op_Alloc)))
224 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
227 } else if (get_irn_op(a) == op_DivMod) {
228 ta = value_of(get_DivMod_left(a));
229 tb = value_of(get_DivMod_right(a));
230 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
231 if (tarval_classify(tb) == 0) {res = NULL; break;}
232 if (get_Proj_proj(n)== 0) /* Div */
233 res = tarval_div(ta, tb);
235 res = tarval_mod(ta, tb);
248 /* returns 1 if the a and b are pointers to different locations. */
250 different_identity (ir_node *a, ir_node *b)
252 assert (get_irn_mode (a) == mode_p
253 && get_irn_mode (b) == mode_p);
255 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
256 ir_node *a1 = get_Proj_pred (a);
257 ir_node *b1 = get_Proj_pred (b);
258 if (a1 != b1 && get_irn_op (a1) == op_Alloc
259 && get_irn_op (b1) == op_Alloc)
266 /* equivalent_node returns a node equivalent to N. It skips all nodes that
267 perform no actual computation, as, e.g., the Id nodes. It does not create
268 new nodes. It is therefore safe to free N if the node returned is not N.
269 If a node returns a Tuple we can not just skip it. If the size of the
270 in array fits, we transform n into a tuple (e.g., Div). */
272 equivalent_node (ir_node *n)
275 ir_node *a = NULL; /* to shutup gcc */
276 ir_node *b = NULL; /* to shutup gcc */
277 ir_node *c = NULL; /* to shutup gcc */
279 ins = get_irn_arity (n);
281 /* get the operands we will work on */
283 a = get_binop_left(n);
284 b = get_binop_right(n);
285 } else if (is_unop(n)) {
289 /* skip unnecessary nodes. */
290 switch (get_irn_opcode (n)) {
293 /* The Block constructor does not call optimize, but mature_block
294 calls the optimization. */
295 assert(get_Block_matured(n));
297 /* Straightening: a single entry Block following a single exit Block
298 can be merged, if it is not the Start block. */
299 /* !!! Beware, all Phi-nodes of n must have been optimized away.
300 This should be true, as the block is matured before optimize is called.
301 But what about Phi-cycles with the Phi0/Id that could not be resolved?
302 Remaining Phi nodes are just Ids. */
303 if ((get_Block_n_cfgpreds(n) == 1) &&
304 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
305 (get_opt_control_flow())) {
306 n = get_nodes_Block(get_Block_cfgpred(n, 0));
307 } else if ((get_Block_n_cfgpreds(n) == 2) &&
308 (get_opt_control_flow())) {
309 /* Test whether Cond jumps twice to this block
310 @@@ we could do this also with two loops finding two preds from several ones. */
311 a = get_Block_cfgpred(n, 0);
312 b = get_Block_cfgpred(n, 1);
313 if ((get_irn_op(a) == op_Proj) &&
314 (get_irn_op(b) == op_Proj) &&
315 (get_Proj_pred(a) == get_Proj_pred(b)) &&
316 (get_irn_op(get_Proj_pred(a)) == op_Cond)) {
317 /* Also a single entry Block following a single exit Block. Phis have
318 twice the same operand and will be optimized away. */
319 n = get_nodes_Block(a);
321 } else if (get_opt_unreachable_code() &&
322 (n != current_ir_graph->start_block) &&
323 (n != current_ir_graph->end_block) ) {
325 /* If all inputs are dead, this block is dead too, except if it is
326 the start or end block. This is a step of unreachable code
328 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
329 if (!is_Bad(get_Block_cfgpred(n, i))) break;
331 if (i == get_Block_n_cfgpreds(n))
337 case iro_Jmp: /* GL: Why not same for op_Raise?? */
338 /* unreachable code elimination */
339 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
341 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
342 See cases for iro_Cond and iro_Proj in transform_node. */
343 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
344 case iro_Or: if (a == b) {n = a; break;}
349 /* After running compute_node there is only one constant predecessor.
350 Find this predecessors value and remember the other node: */
351 if ((tv = computed_value (a))) {
353 } else if ((tv = computed_value (b))) {
357 /* If this predecessors constant value is zero, the operation is
358 unnecessary. Remove it: */
359 if (tarval_classify (tv) == 0) {
369 /* these operations are not commutative. Test only one predecessor. */
370 if (tarval_classify (computed_value (b)) == 0) {
372 /* Test if b > #bits of a ==> return 0 / divide b by #bits
373 --> transform node? */
376 case iro_Not: /* NotNot x == x */
377 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
378 out of bounds exception if min =! max? */
379 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
380 n = get_unop_op(get_unop_op(n));
383 /* Mul is commutative and has again an other neutral element. */
384 if (tarval_classify (computed_value (a)) == 1) {
386 } else if (tarval_classify (computed_value (b)) == 1) {
391 /* Div is not commutative. */
392 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
393 /* Turn Div into a tuple (mem, bad, a) */
394 ir_node *mem = get_Div_mem(n);
395 turn_into_tuple(n, 3);
396 set_Tuple_pred(n, 0, mem);
397 set_Tuple_pred(n, 1, new_Bad());
398 set_Tuple_pred(n, 2, a);
401 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
402 treated in transform node.
403 case iro_Mod, Quot, DivMod
407 /* And has it's own neutral element */
408 else if (tarval_classify (computed_value (a)) == -1) {
410 } else if (tarval_classify (computed_value (b)) == -1) {
415 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
417 } else if (get_irn_mode(n) == mode_b) {
418 if (get_irn_op(a) == op_Conv &&
419 get_irn_mode (get_Conv_op(a)) == mode_b) {
420 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
427 /* Several optimizations:
428 - no Phi in start block.
429 - remove Id operators that are inputs to Phi
430 - fold Phi-nodes, iff they have only one predecessor except
435 ir_node *block = NULL; /* to shutup gcc */
436 ir_node *first_val = NULL; /* to shutup gcc */
437 ir_node *scnd_val = NULL; /* to shutup gcc */
439 n_preds = get_Phi_n_preds(n);
441 block = get_nodes_Block(n);
442 if ((is_Bad(block)) || /* Control dead */
443 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
444 return new_Bad(); /* in the Start Block. */
446 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
449 /* first we test for a special case: */
450 /* Confirm is a special node fixing additional information for a
451 value that is known at a certain point. This is useful for
452 dataflow analysis. */
454 ir_node *a = follow_Id (get_Phi_pred(n, 0));
455 ir_node *b = follow_Id (get_Phi_pred(n, 1));
456 if ( (get_irn_op(a) == op_Confirm)
457 && (get_irn_op(b) == op_Confirm)
458 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
459 && (get_irn_n(a, 1) == get_irn_n (b, 1))
460 && (a->data.num == (~b->data.num & irpn_True) )) {
461 n = follow_Id (get_irn_n(a, 0));
467 /* Find first non-self-referencing input */
468 for (i = 0; i < n_preds; ++i) {
469 first_val = follow_Id(get_Phi_pred(n, i));
471 set_Phi_pred(n, i, first_val);
472 if ( (first_val != n) /* not self pointer */
473 && (get_irn_op(first_val) != op_Bad) /* value not dead */
474 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
475 break; /* then found first value. */
479 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
480 if (i >= n_preds) { n = new_Bad(); break; }
484 /* follow_Id () for rest of inputs, determine if any of these
485 are non-self-referencing */
486 while (++i < n_preds) {
487 scnd_val = follow_Id(get_Phi_pred(n, i));
489 set_Phi_pred(n, i, scnd_val);
491 && (scnd_val != first_val)
492 && (get_irn_op(scnd_val) != op_Bad)
493 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
498 /* Fold, if no multiple distinct non-self-referencing inputs */
502 /* skip the remaining Ids. */
503 while (++i < n_preds) {
504 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
512 #if 0 /* Is an illegal transformation: different nodes can
513 represent the same pointer value!! */
514 a = skip_Proj(get_Load_mem(n));
517 if (get_irn_op(a) == op_Store) {
518 if ( different_identity (b, get_Store_ptr(a))) {
519 /* load and store use different pointers, therefore load
520 needs not take store's memory but the state before. */
521 set_Load_mem (n, get_Store_mem(a));
522 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
529 /* remove unnecessary store. */
531 a = skip_Proj(get_Store_mem(n));
532 b = get_Store_ptr(n);
533 c = skip_Proj(get_Store_value(n));
535 if (get_irn_op(a) == op_Store
536 && get_Store_ptr(a) == b
537 && skip_Proj(get_Store_value(a)) == c) {
538 /* We have twice exactly the same store -- a write after write. */
540 } else if (get_irn_op(c) == op_Load
541 && (a == c || skip_Proj(get_Load_mem(c)) == a)
542 && get_Load_ptr(c) == b )
543 /* !!!??? and a cryptic test */ {
544 /* We just loaded the value from the same memory, i.e., the store
545 doesn't change the memory -- a write after read. */
546 a = get_Store_mem(n);
547 turn_into_tuple(n, 2);
548 set_Tuple_pred(n, 0, a);
549 set_Tuple_pred(n, 1, new_Bad());
556 a = get_Proj_pred(n);
558 if ( get_irn_op(a) == op_Tuple) {
559 /* Remove the Tuple/Proj combination. */
560 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
561 n = get_Tuple_pred(a, get_Proj_proj(n));
563 assert(0); /* This should not happen! */
566 } else if (get_irn_mode(n) == mode_X &&
567 is_Bad(get_nodes_Block(n))) {
568 /* Remove dead control flow. */
582 } /* end equivalent_node() */
585 /* tries several [inplace] [optimizing] transformations and returns an
586 equivalent node. The difference to equivalent_node is that these
587 transformations _do_ generate new nodes, and thus the old node must
588 not be freed even if the equivalent node isn't the old one. */
590 transform_node (ir_node *n)
593 ir_node *a = NULL, *b;
596 switch (get_irn_opcode(n)) {
598 ta = computed_value(n);
600 /* Turn Div into a tuple (mem, bad, value) */
601 ir_node *mem = get_Div_mem(n);
602 turn_into_tuple(n, 3);
603 set_Tuple_pred(n, 0, mem);
604 set_Tuple_pred(n, 1, new_Bad());
605 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
609 ta = computed_value(n);
611 /* Turn Div into a tuple (mem, bad, value) */
612 ir_node *mem = get_Mod_mem(n);
613 turn_into_tuple(n, 3);
614 set_Tuple_pred(n, 0, mem);
615 set_Tuple_pred(n, 1, new_Bad());
616 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
624 a = get_DivMod_left(n);
625 b = get_DivMod_right(n);
626 mode = get_irn_mode(a);
628 if (!(mode_is_int(get_irn_mode(a)) &&
629 mode_is_int(get_irn_mode(b))))
633 a = new_Const (mode, tarval_from_long (mode, 1));
634 b = new_Const (mode, tarval_from_long (mode, 0));
641 if (tarval_classify(tb) == 1) {
642 b = new_Const (mode, tarval_from_long (mode, 0));
646 resa = tarval_div (ta, tb);
647 if (!resa) break; /* Causes exception!!! Model by replacing through
648 Jmp for X result!? */
649 resb = tarval_mod (ta, tb);
650 if (!resb) break; /* Causes exception! */
651 a = new_Const (mode, resa);
652 b = new_Const (mode, resb);
655 } else if (tarval_classify (ta) == 0) {
660 if (evaluated) { /* replace by tuple */
661 ir_node *mem = get_DivMod_mem(n);
662 turn_into_tuple(n, 4);
663 set_Tuple_pred(n, 0, mem);
664 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
665 set_Tuple_pred(n, 2, a);
666 set_Tuple_pred(n, 3, b);
667 assert(get_nodes_Block(n));
673 /* Replace the Cond by a Jmp if it branches on a constant
676 a = get_Cond_selector(n);
680 (get_irn_mode(a) == mode_b) &&
681 (get_opt_unreachable_code())) {
682 /* It's a boolean Cond, branching on a boolean constant.
683 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
684 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
685 turn_into_tuple(n, 2);
686 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
687 set_Tuple_pred(n, 0, new_Bad());
688 set_Tuple_pred(n, 1, jmp);
690 set_Tuple_pred(n, 0, jmp);
691 set_Tuple_pred(n, 1, new_Bad());
693 /* We might generate an endless loop, so keep it alive. */
694 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
696 (get_irn_mode(a) == mode_I) &&
697 (get_Cond_kind(n) == dense) &&
698 (get_opt_unreachable_code())) {
699 /* I don't want to allow Tuples smaller than the biggest Proj.
700 Also this tuple might get really big...
701 I generate the Jmp here, and remember it in link. Link is used
702 when optimizing Proj. */
703 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
704 /* We might generate an endless loop, so keep it alive. */
705 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
706 } else if ((get_irn_op(get_Cond_selector(n)) == op_Eor)
707 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
708 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
709 /* The Eor is a negate. Generate a new Cond without the negate,
710 simulate the negate by exchanging the results. */
711 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
713 } else if ((get_irn_op(get_Cond_selector(n)) == op_Not)
714 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
715 /* A Not before the Cond. Generate a new Cond without the Not,
716 simulate the Not by exchanging the results. */
717 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
724 a = get_Proj_pred(n);
726 if ((get_irn_op(a) == op_Cond)
728 && get_irn_op(get_irn_link(a)) == op_Cond) {
729 /* Use the better Cond if the Proj projs from a Cond which get's
730 its result from an Eor/Not. */
731 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
732 || (get_irn_op(get_Cond_selector(a)) == op_Not))
733 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
734 && (get_irn_op(get_irn_link(a)) == op_Cond)
735 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
736 set_Proj_pred(n, get_irn_link(a));
737 if (get_Proj_proj(n) == 0)
741 } else if ((get_irn_op(a) == op_Cond)
742 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
744 && (get_Cond_kind(a) == dense)
745 && (get_opt_unreachable_code())) {
746 /* The Cond is a Switch on a Constant */
747 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
748 /* The always taken branch, reuse the existing Jmp. */
749 if (!get_irn_link(a)) /* well, if it exists ;-> */
750 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
751 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
753 } else {/* Not taken control flow, but be careful with the default! */
754 if (get_Proj_proj(n) < a->attr.c.default_proj){
755 /* a never taken branch */
758 a->attr.c.default_proj = get_Proj_proj(n);
763 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
765 b = get_Eor_right(n);
767 if ((get_irn_mode(n) == mode_b)
768 && (get_irn_op(a) == op_Proj)
769 && (get_irn_mode(a) == mode_b)
770 && (tarval_classify (computed_value (b)) == 1)
771 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
772 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
773 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
774 mode_b, get_negated_pnc(get_Proj_proj(a)));
775 else if ((get_irn_mode(n) == mode_b)
776 && (tarval_classify (computed_value (b)) == 1))
777 /* The Eor is a Not. Replace it by a Not. */
778 /* ????!!!Extend to bitfield 1111111. */
779 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
785 if ( (get_irn_mode(n) == mode_b)
786 && (get_irn_op(a) == op_Proj)
787 && (get_irn_mode(a) == mode_b)
788 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
789 /* We negate a Cmp. The Cmp has the negated result anyways! */
790 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
791 mode_b, get_negated_pnc(get_Proj_proj(a)));
799 /* **************** Common Subexpression Elimination **************** */
801 /* Compare function for two nodes in the hash table. Gets two */
802 /* nodes as parameters. Returns 0 if the nodes are a cse. */
804 vt_cmp (const void *elt, const void *key)
812 if (a == b) return 0;
814 if ((get_irn_op(a) != get_irn_op(b)) ||
815 (get_irn_mode(a) != get_irn_mode(b))) return 1;
817 /* compare if a's in and b's in are equal */
818 /* GL: we optimize only nodes with in arrays of fixed sizes.
819 if (get_irn_arity (a) != -2) {
820 ins = get_irn_arity (a);
821 if (ins != get_irn_arity (b)) return 1;
822 ain = get_irn_in (a);
823 bin = get_irn_in (b);
826 if (get_irn_arity (a) != get_irn_arity(b))
829 /* for block-local cse and pinned nodes: */
830 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
831 if (get_irn_n(a, -1) != get_irn_n(b, -1))
835 /* compare a->in[0..ins] with b->in[0..ins] */
836 for (i = 0; i < get_irn_arity(a); i++)
837 if (get_irn_n(a, i) != get_irn_n(b, i))
840 switch (get_irn_opcode(a)) {
842 return get_irn_const_attr (a) != get_irn_const_attr (b);
844 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
846 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
847 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
849 return (get_irn_free_attr(a) != get_irn_free_attr(b));
851 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
852 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
854 return (get_irn_call_attr(a) != get_irn_call_attr(b));
856 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
857 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
858 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
859 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
860 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
861 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
863 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
871 ir_node_hash (ir_node *node)
876 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
877 h = get_irn_arity(node);
879 /* consider all in nodes... except the block. */
880 for (i = 0; i < get_irn_arity(node); i++) {
881 h = 9*h + (unsigned long)get_irn_n(node, i);
885 h = 9*h + (unsigned long) get_irn_mode (node);
887 h = 9*h + (unsigned long) get_irn_op (node);
893 new_identities (void)
895 return new_pset (vt_cmp, TUNE_NIR_NODES);
899 del_identities (pset *value_table)
901 del_pset (value_table);
904 /* Return the canonical node computing the same value as n.
905 Looks up the node in a hash table. */
906 static inline ir_node *
907 identify (pset *value_table, ir_node *n)
911 if (!value_table) return n;
913 if (get_opt_reassociation()) {
914 switch (get_irn_opcode (n)) {
921 /* for commutative operators perform a OP b == b OP a */
922 if (get_binop_left(n) > get_binop_right(n)) {
923 ir_node *h = get_binop_left(n);
924 set_binop_left(n, get_binop_right(n));
925 set_binop_right(n, h);
933 o = pset_find (value_table, n, ir_node_hash (n));
939 /* During construction we set the pinned flag in the graph right when the
940 optimizatin is performed. The flag turning on procedure global cse could
941 be changed between two allocations. This way we are safe. */
942 static inline ir_node *
943 identify_cons (pset *value_table, ir_node *n) {
945 n = identify(value_table, n);
946 if (get_irn_n(old, -1) != get_irn_n(n, -1))
947 set_irg_pinned(current_ir_graph, floats);
951 /* Return the canonical node computing the same value as n.
952 Looks up the node in a hash table, enters it in the table
953 if it isn't there yet. */
955 identify_remember (pset *value_table, ir_node *node)
959 if (!value_table) return node;
961 /* lookup or insert in hash table with given hash key. */
962 o = pset_insert (value_table, node, ir_node_hash (node));
964 if (o == node) return node;
970 add_identities (pset *value_table, ir_node *node) {
971 identify_remember (value_table, node);
974 /* garbage in, garbage out. If a node has a dead input, i.e., the
975 Bad node is input to the node, return the Bad node. */
976 static inline ir_node *
980 ir_op* op = get_irn_op(node);
982 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
983 blocks predecessors is dead. */
984 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
985 for (i = -1; i < get_irn_arity(node); i++) {
986 if (is_Bad(get_irn_n(node, i))) {
992 /* If Block has only Bads as predecessors it's garbage. */
993 /* If Phi has only Bads as predecessors it's garbage. */
994 if (op == op_Block || op == op_Phi) {
995 for (i = 0; i < get_irn_arity(node); i++) {
996 if (!is_Bad(get_irn_n(node, i))) break;
998 if (i = get_irn_arity(node)) node = new_Bad();
1005 /* These optimizations deallocate nodes from the obstack.
1006 It can only be called if it is guaranteed that no other nodes
1007 reference this one, i.e., right after construction of a node. */
1009 optimize (ir_node *n)
1014 /* Allways optimize Phi nodes: part of the construction. */
1015 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1017 /* constant expression evaluation / constant folding */
1018 if (get_opt_constant_folding()) {
1019 /* constants can not be evaluated */
1020 if (get_irn_op(n) != op_Const) {
1021 /* try to evaluate */
1022 tv = computed_value (n);
1023 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1024 /* evaluation was succesful -- replace the node. */
1025 obstack_free (current_ir_graph->obst, n);
1026 return new_Const (get_tv_mode (tv), tv);
1031 /* remove unnecessary nodes */
1032 if (get_opt_constant_folding() ||
1033 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1034 (get_irn_op(n) == op_Id) ||
1035 (get_irn_op(n) == op_Proj) ||
1036 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1037 n = equivalent_node (n);
1039 /** common subexpression elimination **/
1040 /* Checks whether n is already available. */
1041 /* The block input is used to distinguish different subexpressions. Right
1042 now all nodes are pinned to blocks, i.e., the cse only finds common
1043 subexpressions within a block. */
1045 n = identify_cons (current_ir_graph->value_table, n);
1048 /* We found an existing, better node, so we can deallocate the old node. */
1049 obstack_free (current_ir_graph->obst, old_n);
1052 /* Some more constant expression evaluation that does not allow to
1054 if (get_opt_constant_folding() ||
1055 (get_irn_op(n) == op_Cond) ||
1056 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1057 n = transform_node (n);
1059 /* Remove nodes with dead (Bad) input.
1060 Run always for transformation induced Bads. */
1063 /* Now we can verify the node, as it has no dead inputs any more. */
1066 /* Now we have a legal, useful node. Enter it in hash table for cse */
1067 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1068 n = identify_remember (current_ir_graph->value_table, n);
1075 /* These optimizations never deallocate nodes. This can cause dead
1076 nodes lying on the obstack. Remove these by a dead node elimination,
1077 i.e., a copying garbage collection. */
1079 optimize_in_place_2 (ir_node *n)
1084 if (!get_optimize() && (get_irn_op(n) != op_Phi)) return n;
1086 /* if not optimize return n */
1089 /* Here this is possible. Why? */
1093 /* constant expression evaluation / constant folding */
1094 if (get_opt_constant_folding()) {
1095 /* constants can not be evaluated */
1096 if (get_irn_op(n) != op_Const) {
1097 /* try to evaluate */
1098 tv = computed_value (n);
1099 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1100 /* evaluation was succesful -- replace the node. */
1101 n = new_Const (get_tv_mode (tv), tv);
1102 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1104 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1109 /* remove unnecessary nodes */
1110 /*if (get_opt_constant_folding()) */
1111 if (get_opt_constant_folding() ||
1112 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1113 (get_irn_op(n) == op_Id) ||
1114 (get_irn_op(n) == op_Proj) ||
1115 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1116 n = equivalent_node (n);
1118 /** common subexpression elimination **/
1119 /* Checks whether n is already available. */
1120 /* The block input is used to distinguish different subexpressions. Right
1121 now all nodes are pinned to blocks, i.e., the cse only finds common
1122 subexpressions within a block. */
1123 if (get_opt_cse()) {
1124 n = identify (current_ir_graph->value_table, n);
1127 /* Some more constant expression evaluation. */
1128 if (get_opt_constant_folding() ||
1129 (get_irn_op(n) == op_Cond) ||
1130 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1131 n = transform_node (n);
1133 /* Remove nodes with dead (Bad) input.
1134 Run always for transformation induced Bads. */
1137 /* Now we can verify the node, as it has no dead inputs any more. */
1140 /* Now we have a legal, useful node. Enter it in hash table for cse.
1141 Blocks should be unique anyways. (Except the successor of start:
1142 is cse with the start block!) */
1143 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1144 n = identify_remember (current_ir_graph->value_table, n);
1149 /* Wrapper for external use, set proper status bits after optimization */
1151 optimize_in_place (ir_node *n) {
1152 /* Handle graph state */
1153 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1154 if (get_opt_global_cse())
1155 set_irg_pinned(current_ir_graph, floats);
1156 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1157 set_irg_outs_inconsistent(current_ir_graph);
1158 /* Maybe we could also test whether optimizing the node can
1159 change the control graph. */
1160 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1161 set_irg_dom_inconsistent(current_ir_graph);
1162 return optimize_in_place_2 (n);