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.
13 # include "irnode_t.h"
14 # include "irgraph_t.h"
23 /* Make types visible to allow most efficient access */
24 # include "entity_t.h"
26 /* Trivial inlineable routine for copy propagation.
27 Does follow Ids, needed to optimize inlined code. */
28 static inline ir_node *
29 follow_Id (ir_node *n)
31 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
35 static inline tarval *
38 if ((n != NULL) && (get_irn_op(n) == op_Const))
39 return get_Const_tarval(n);
44 /* if n can be computed, return the value, else NULL. Performs
45 constant folding. GL: Only if n is arithmetic operator? */
47 computed_value (ir_node *n)
51 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
52 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
56 /* get the operands we will work on for simple cases. */
58 a = get_binop_left(n);
59 b = get_binop_right(n);
60 } else if (is_unop(n)) {
64 /* if the operands are constants, get the target value, else set it NULL.
65 (a and b may be NULL if we treat a node that is no computation.) */
69 /* Perform the constant evaluation / computation. */
70 switch (get_irn_opcode(n)) {
72 res = get_Const_tarval(n);
74 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
75 && (get_irn_mode(a) != mode_p)) {
76 res = tarval_add (ta, tb);
80 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
81 && (get_irn_mode(a) != mode_p)) {
82 res = tarval_sub (ta, tb);
84 res = tarval_mode_null [get_irn_modecode (n)];
88 if (ta && mode_is_float(get_irn_mode(a)))
89 res = tarval_neg (ta);
92 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
93 res = tarval_mul (ta, tb);
95 /* a*0 = 0 or 0*b = 0:
96 calls computed_value recursive and returns the 0 with proper
99 if ( (tarval_classify ((v = computed_value (a))) == 0)
100 || (tarval_classify ((v = computed_value (b))) == 0)) {
106 /* This was missing in original implementation. Why? */
107 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
108 if (tarval_classify(tb) == 0) {res = NULL; break;}
109 res = tarval_quo(ta, tb);
113 /* This was missing in original implementation. Why? */
114 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
115 if (tarval_classify(tb) == 0) {res = NULL; break;}
116 res = tarval_div(ta, tb);
120 /* This was missing in original implementation. Why? */
121 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
122 if (tarval_classify(tb) == 0) {res = NULL; break;}
123 res = tarval_mod(ta, tb);
126 /* for iro_DivMod see iro_Proj */
129 res = tarval_abs (ta);
133 res = tarval_and (ta, tb);
136 if ( (tarval_classify ((v = computed_value (a))) == 0)
137 || (tarval_classify ((v = computed_value (b))) == 0)) {
144 res = tarval_or (ta, tb);
147 if ( (tarval_classify ((v = computed_value (a))) == -1)
148 || (tarval_classify ((v = computed_value (b))) == -1)) {
153 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
154 case iro_Not: if (ta) { res = tarval_neg (ta); } break;
155 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
156 /* tarval_shr is faulty !! */
157 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
158 case iro_Shrs:if (ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
159 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
160 case iro_Conv:if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
162 case iro_Proj: /* iro_Cmp */
166 a = get_Proj_pred(n);
167 /* Optimize Cmp nodes.
168 This performs a first step of unreachable code elimination.
169 Proj can not be computed, but folding a Cmp above the Proj here is
170 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
172 There are several case where we can evaluate a Cmp node:
173 1. The nodes compared are both the same. If we compare for
174 equal, this will return true, else it will return false.
175 This step relies on cse.
176 2. The predecessors of Cmp are target values. We can evaluate
178 3. The predecessors are Allocs or void* constants. Allocs never
179 return NULL, they raise an exception. Therefore we can predict
181 if (get_irn_op(a) == op_Cmp) {
182 aa = get_Cmp_left(a);
183 ab = get_Cmp_right(a);
184 if (aa == ab) { /* 1.: */
185 /* This is a tric with the bits used for encoding the Cmp
186 Proj numbers, the following statement is not the same:
187 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
188 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
190 tarval *taa = computed_value (aa);
191 tarval *tab = computed_value (ab);
192 if (taa && tab) { /* 2.: */
193 /* strange checks... */
194 ir_pncmp flags = tarval_comp (taa, tab);
195 if (flags != irpn_False) {
196 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
198 } else { /* check for 3.: */
199 ir_node *aaa = skip_nop(skip_Proj(aa));
200 ir_node *aba = skip_nop(skip_Proj(ab));
201 if ( ( (/* aa is ProjP and aaa is Alloc */
202 (get_irn_op(aa) == op_Proj)
203 && (get_irn_mode(aa) == mode_p)
204 && (get_irn_op(aaa) == op_Alloc))
205 && ( (/* ab is constant void */
206 (get_irn_op(ab) == op_Const)
207 && (get_irn_mode(ab) == mode_p)
208 && (get_Const_tarval(ab) == tarval_p_void))
209 || (/* ab is other Alloc */
210 (get_irn_op(ab) == op_Proj)
211 && (get_irn_mode(ab) == mode_p)
212 && (get_irn_op(aba) == op_Alloc)
214 || (/* aa is void and aba is Alloc */
215 (get_irn_op(aa) == op_Const)
216 && (get_irn_mode(aa) == mode_p)
217 && (get_Const_tarval(aa) == tarval_p_void)
218 && (get_irn_op(ab) == op_Proj)
219 && (get_irn_mode(ab) == mode_p)
220 && (get_irn_op(aba) == op_Alloc)))
222 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
225 } else if (get_irn_op(a) == op_DivMod) {
226 ta = value_of(get_DivMod_left(a));
227 tb = value_of(get_DivMod_right(a));
228 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
229 if (tarval_classify(tb) == 0) {res = NULL; break;}
230 if (get_Proj_proj(n)== 0) /* Div */
231 res = tarval_div(ta, tb);
233 res = tarval_mod(ta, tb);
236 /* printf(" # comp_val: Proj node, not optimized\n"); */
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 /* A single entry Block following a single exit Block can be merged,
298 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 if (get_Block_n_cfgpreds(n) == 1
303 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
304 n = get_nodes_Block(get_Block_cfgpred(n, 0));
306 } else if ((n != current_ir_graph->start_block) &&
307 (n != current_ir_graph->end_block) ) {
309 /* If all inputs are dead, this block is dead too, except if it is
310 the start or end block. This is a step of unreachable code
312 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
313 if (!is_Bad(get_Block_cfgpred(n, i))) break;
315 if (i == get_Block_n_cfgpreds(n))
321 case iro_Jmp: /* GL: Why not same for op_Raise?? */
322 /* unreachable code elimination */
323 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
325 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
326 See cases for iro_Cond and iro_Proj in transform_node. */
327 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
328 case iro_Or: if (a == b) {n = a; break;}
333 /* After running compute_node there is only one constant predecessor.
334 Find this predecessors value and remember the other node: */
335 if ((tv = computed_value (a))) {
337 } else if ((tv = computed_value (b))) {
341 /* If this predecessors constant value is zero, the operation is
342 unnecessary. Remove it: */
343 if (tarval_classify (tv) == 0) {
353 /* these operations are not commutative. Test only one predecessor. */
354 if (tarval_classify (computed_value (b)) == 0) {
356 /* Test if b > #bits of a ==> return 0 / divide b by #bits
357 --> transform node? */
360 case iro_Not: /* NotNot x == x */
361 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
362 out of bounds exception if min =! max? */
363 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
364 n = get_unop_op(get_unop_op(n));
367 /* Mul is commutative and has again an other neutral element. */
368 if (tarval_classify (computed_value (a)) == 1) {
370 } else if (tarval_classify (computed_value (b)) == 1) {
375 /* Div is not commutative. */
376 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
377 /* Turn Div into a tuple (mem, bad, a) */
378 ir_node *mem = get_Div_mem(n);
379 turn_into_tuple(n, 3);
380 set_Tuple_pred(n, 0, mem);
381 set_Tuple_pred(n, 1, new_Bad());
382 set_Tuple_pred(n, 2, a);
385 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
386 teated in transform node.
387 case iro_Mod, Quot, DivMod
391 /* And has it's own neutral element */
392 else if (tarval_classify (computed_value (a)) == -1) {
394 } else if (tarval_classify (computed_value (b)) == -1) {
399 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
401 } else if (get_irn_mode(n) == mode_b) {
402 if (get_irn_op(a) == op_Conv &&
403 get_irn_mode (get_Conv_op(a)) == mode_b) {
404 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
411 /* Several optimizations:
412 - no Phi in start block.
413 - remove Id operators that are inputs to Phi
414 - fold Phi-nodes, iff they have only one predecessor except
420 ir_node *block = NULL; /* to shutup gcc */
421 ir_node *first_val = NULL; /* to shutup gcc */
422 ir_node *scnd_val = NULL; /* to shutup gcc */
424 n_preds = get_Phi_n_preds(n);
426 block = get_nodes_Block(n);
427 assert(get_irn_op (block) == op_Block);
429 /* there should be no Phi nodes in the Start region. */
430 if (block == current_ir_graph->start_block) {
435 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
436 /* GL: why not return new_Bad? */
441 /* first we test for a special case: */
442 /* Confirm is a special node fixing additional information for a
443 value that is known at a certain point. This is useful for
444 dataflow analysis. */
446 ir_node *a = follow_Id (get_Phi_pred(n, 0));
447 ir_node *b = follow_Id (get_Phi_pred(n, 1));
448 if ( (get_irn_op(a) == op_Confirm)
449 && (get_irn_op(b) == op_Confirm)
450 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
451 && (get_irn_n(a, 1) == get_irn_n (b, 1))
452 && (a->data.num == (~b->data.num & irpn_True) )) {
453 n = follow_Id (get_irn_n(a, 0));
459 /* Find first non-self-referencing input */
460 for (i = 0; i < n_preds; ++i) {
461 first_val = follow_Id(get_Phi_pred(n, i));
463 set_Phi_pred(n, i, first_val);
464 if ( (first_val != n) /* not self pointer */
465 && (get_irn_op(first_val) != op_Bad) /* value not dead */
466 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
467 break; /* then found first value. */
471 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
472 if (i >= n_preds) { n = new_Bad(); break; }
476 /* follow_Id () for rest of inputs, determine if any of these
477 are non-self-referencing */
478 while (++i < n_preds) {
479 scnd_val = follow_Id(get_Phi_pred(n, i));
481 set_Phi_pred(n, i, scnd_val);
483 && (scnd_val != first_val)
484 && (get_irn_op(scnd_val) != op_Bad)
485 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
490 /* Fold, if no multiple distinct non-self-referencing inputs */
494 /* skip the remaining Ids. */
495 while (++i < n_preds) {
496 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
504 a = skip_Proj(get_Load_mem(n));
505 b = skip_Proj(get_Load_ptr(n));
507 if (get_irn_op(a) == op_Store) {
508 if ( different_identity (b, get_Store_ptr(a))) {
509 /* load and store use different pointers, therefore load
510 needs not take store's memory but the state before. */
511 set_Load_mem (n, get_Store_mem(a));
512 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
518 /* remove unnecessary store. */
520 a = skip_Proj(get_Store_mem(n));
521 b = get_Store_ptr(n);
522 c = skip_Proj(get_Store_value(n));
524 if (get_irn_op(a) == op_Store
525 && get_Store_ptr(a) == b
526 && skip_Proj(get_Store_value(a)) == c) {
527 /* We have twice exactly the same store -- a write after write. */
529 } else if (get_irn_op(c) == op_Load
530 && (a == c || skip_Proj(get_Load_mem(c)) == a)
531 && get_Load_ptr(c) == b )
532 /* !!!??? and a cryptic test */ {
533 /* We just loaded the value from the same memory, i.e., the store
534 doesn't change the memory -- a write after read. */
535 turn_into_tuple(n, 2);
536 set_Tuple_pred(n, 0, a);
537 set_Tuple_pred(n, 1, new_Bad());
544 a = get_Proj_pred(n);
546 if ( get_irn_op(a) == op_Tuple) {
547 /* Remove the Tuple/Proj combination. */
548 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
549 n = get_Tuple_pred(a, get_Proj_proj(n));
551 assert(0); /* This should not happen! (GL added this assert) */
554 } else if (get_irn_mode(n) == mode_X &&
555 is_Bad(get_nodes_Block(n))) {
556 /* Remove dead control flow. */
570 } /* end equivalent_node() */
573 /* tries several [inplace] [optimizing] transformations and returns a
574 equivalent node. The difference to equivalent_node is that these
575 transformations _do_ generate new nodes, and thus the old node must
576 not be freed even if the equivalent node isn't the old one. */
578 transform_node (ir_node *n)
581 ir_node *a = NULL, *b;
584 switch (get_irn_opcode(n)) {
590 a = get_DivMod_left(n);
591 b = get_DivMod_right(n);
592 mode = get_irn_mode(a);
594 if (!( mode_is_int(get_irn_mode(a))
595 && mode_is_int(get_irn_mode(b))))
599 a = new_Const (mode, tarval_from_long (mode, 1));
600 b = new_Const (mode, tarval_from_long (mode, 0));
607 if (tarval_classify(tb) == 1) {
608 b = new_Const (mode, tarval_from_long (mode, 0));
612 resa = tarval_div (ta, tb);
613 if (!resa) break; /* Causes exception!!! Model by replacing through
614 Jmp for X result!? */
615 resb = tarval_mod (ta, tb);
616 if (!resb) break; /* Causes exception! */
617 a = new_Const (mode, resa);
618 b = new_Const (mode, resb);
621 } else if (tarval_classify (ta) == 0) {
626 if (evaluated) { /* replace by tuple */
627 ir_node *mem = get_DivMod_mem(n);
628 turn_into_tuple(n, 4);
629 set_Tuple_pred(n, 0, mem);
630 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
631 set_Tuple_pred(n, 2, a);
632 set_Tuple_pred(n, 3, b);
633 assert(get_nodes_Block(n));
639 /* Replace the Cond by a Jmp if it branches on a constant
642 a = get_Cond_selector(n);
645 if (ta && (get_irn_mode(a) == mode_b)) {
646 /* It's a boolean Cond, branching on a boolean constant.
647 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
648 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
649 turn_into_tuple(n, 2);
650 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
651 set_Tuple_pred(n, 0, new_Bad());
652 set_Tuple_pred(n, 1, jmp);
654 set_Tuple_pred(n, 0, jmp);
655 set_Tuple_pred(n, 1, new_Bad());
657 } else if (ta && (get_irn_mode(a) == mode_I) && (get_Cond_kind(n) == dense)) {
658 /* I don't want to allow Tuples smaller than the biggest Proj.
659 Also this tuple might get really big...
660 I generate the Jmp here, and remember it in link. Link is used
661 when optimizing Proj. */
662 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
663 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
664 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
665 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
666 /* The Eor is a negate. Generate a new Cond without the negate,
667 simulate the negate by exchanging the results. */
668 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
670 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
671 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
672 /* A Not before the Cond. Generate a new Cond without the Not,
673 simulate the Not by exchanging the results. */
674 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
681 a = get_Proj_pred(n);
683 if ( (get_irn_op(a) == op_Cond)
685 && get_irn_op(get_irn_link(a)) == op_Cond) {
686 /* Use the better Cond if the Proj projs from a Cond which get's
687 its result from an Eor/Not. */
688 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
689 || (get_irn_op(get_Cond_selector(a)) == op_Not))
690 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
691 && (get_irn_op(get_irn_link(a)) == op_Cond)
692 && (get_Cond_selector(get_irn_link(a)) ==
693 get_Eor_left(get_Cond_selector(a))));
694 set_Proj_pred(n, get_irn_link(a));
695 if (get_Proj_proj(n) == 0)
699 } else if ( (get_irn_op(a) == op_Cond)
700 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
702 && (get_Cond_kind(a) == dense)) {
703 /* The Cond is a Switch on a Constant */
704 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
705 /* The always taken branch, reuse the existing Jmp. */
706 if (!get_irn_link(a)) /* well, if it exists ;-> */
707 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
708 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
710 } else {/* Not taken control flow, but be careful with the default! */
711 if (get_Proj_proj(n) < a->attr.c.default_proj){
712 /* a never taken branch */
715 a->attr.c.default_proj = get_Proj_proj(n);
720 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
722 b = get_Eor_right(n);
724 if ( (get_irn_mode(n) == mode_b)
725 && (get_irn_op(a) == op_Proj)
726 && (get_irn_mode(a) == mode_b)
727 && (tarval_classify (computed_value (b)) == 1)
728 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
729 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
730 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
731 mode_b, get_negated_pnc(get_Proj_proj(a)));
732 else if ( (get_irn_mode(n) == mode_b)
733 && (tarval_classify (computed_value (b)) == 1))
734 /* The Eor is a Not. Replace it by a Not. */
735 /* ????!!!Extend to bitfield 1111111. */
736 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
742 if ( (get_irn_mode(n) == mode_b)
743 && (get_irn_op(a) == op_Proj)
744 && (get_irn_mode(a) == mode_b)
745 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
746 /* We negate a Cmp. The Cmp has the negated result anyways! */
747 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
748 mode_b, get_negated_pnc(get_Proj_proj(a)));
756 /* **************** Common Subexpression Elimination **************** */
758 /* Compare function for two nodes in the hash table. Gets two */
759 /* nodes as parameters. */
760 /* @@@ a+b != b+a ? */
762 vt_cmp (const void *elt, const void *key)
770 if (a == b) return 0;
772 if ((get_irn_op(a) != get_irn_op(b)) ||
773 (get_irn_mode(a) != get_irn_mode(b))) return 1;
775 /* compare if a's in and b's in are equal */
776 /* GL: we optimize only nodes with in arrays of fixed sizes.
777 if (get_irn_arity (a) != -2) {
778 ins = get_irn_arity (a);
779 if (ins != get_irn_arity (b)) return 1;
780 ain = get_irn_in (a);
781 bin = get_irn_in (b);
784 if (get_irn_arity (a) != get_irn_arity(b))
787 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
788 /* do if (*ain++ != *bin++) return 1; while (ins--); */
789 for (i = -1; i < get_irn_arity(a); i++)
790 if (get_irn_n(a, i) != get_irn_n(b, i))
794 switch (get_irn_opcode(a)) {
796 return get_irn_const_attr (a) != get_irn_const_attr (b);
798 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
800 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
801 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
803 return (get_irn_free_attr(a) != get_irn_free_attr(b));
805 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
806 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
808 return (get_irn_call_attr(a) != get_irn_call_attr(b));
810 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
811 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
812 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
813 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
814 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
815 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
817 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
825 ir_node_hash (ir_node *node)
830 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
831 h = get_irn_arity(node);
833 /* consider all in nodes... except the block. */
834 for (i = 0; i < get_irn_arity(node); i++) {
835 h = 9*h + (unsigned long)get_irn_n(node, i);
839 h = 9*h + (unsigned long) get_irn_mode (node);
841 h = 9*h + (unsigned long) get_irn_op (node);
847 new_identities (void)
849 return new_pset (vt_cmp, TUNE_NIR_NODES);
853 del_identities (pset *value_table)
855 del_pset (value_table);
859 add_identities (pset *value_table, ir_node *node) {
860 identify_remember (value_table, node);
863 /* Return the canonical node computing the same value as n.
864 Looks up the node in a hash table. */
865 static inline ir_node *
866 identify (pset *value_table, ir_node *n)
870 if (!value_table) return n;
872 switch (get_irn_opcode (n)) {
879 /* for commutative operators perform a OP b == b OP a */
880 if (get_binop_left(n) > get_binop_right(n)) {
881 ir_node *h = get_binop_left(n);
882 set_binop_left(n, get_binop_right(n));
883 set_binop_right(n, h);
889 o = pset_find (value_table, n, ir_node_hash (n));
895 /* Return the canonical node computing the same value as n.
896 Looks up the node in a hash table, enters it in the table
897 if it isn't there yet. */
899 identify_remember (pset *value_table, ir_node *node)
903 if (!value_table) return node;
905 /* lookup or insert in hash table with given hash key. */
906 o = pset_insert (value_table, node, ir_node_hash (node));
908 if (o == node) return node;
913 /* garbage in, garbage out. If a node has a dead input, i.e., the
914 Bad node is input to the node, return the Bad node. */
915 static inline ir_node *
919 ir_op* op = get_irn_op(node);
921 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
922 blocks predecessors is dead. */
923 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
924 for (i = -1; i < get_irn_arity(node); i++) {
925 if (is_Bad(get_irn_n(node, i))) {
931 /* If Block has only Bads as predecessors it's garbage. */
932 /* If Phi has only Bads as predecessors it's garbage. */
933 if (op == op_Block || op == op_Phi) {
934 for (i = 0; i < get_irn_arity(node); i++) {
935 if (!is_Bad(get_irn_n(node, i))) break;
937 if (i = get_irn_arity(node)) node = new_Bad();
944 /* These optimizations deallocate nodes from the obstack.
945 It can only be called if it is guaranteed that no other nodes
946 reference this one, i.e., right after construction of a node. */
948 optimize (ir_node *n)
953 /* Allways optimize Phi nodes: part of the construction. */
954 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
956 /* if not optimize return n */
958 printf(" attention: empty node!!! \n");
962 /* constant expression evaluation / constant folding */
963 if (get_opt_constant_folding()) {
964 /* constants can not be evaluated */
965 if (get_irn_op(n) != op_Const) {
966 /* try to evaluate */
967 tv = computed_value (n);
969 /* evaluation was succesful -- replace the node. */
970 obstack_free (current_ir_graph->obst, n);
971 return new_Const (get_tv_mode (tv), tv);
976 /* remove unnecessary nodes */
977 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
978 n = equivalent_node (n);
980 /** common subexpression elimination **/
981 /* Checks whether n is already available. */
982 /* The block input is used to distinguish different subexpressions. Right
983 now all nodes are pinned to blocks, i.e., the cse only finds common
984 subexpressions within a block. */
986 n = identify (current_ir_graph->value_table, n);
987 /* identify found a cse, so deallocate the old node. */
989 obstack_free (current_ir_graph->obst, old_n);
990 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
993 /* Some more constant expression evaluation that does not allow to
995 if (get_opt_constant_folding())
996 n = transform_node (n);
998 /* Remove nodes with dead (Bad) input. */
1000 /* Now we can verify the node, as it has no dead inputs any more. */
1003 /* Now we have a legal, useful node. Enter it in hash table for cse */
1004 if (get_opt_cse()) {
1005 n = identify_remember (current_ir_graph->value_table, n);
1008 #if 0 /* GL: what's the use of this?? */
1009 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
1010 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
1011 pdeq_putr (current_ir_graph->keep.living, n);
1018 /* These optimizations never deallocate nodes. This can cause dead
1019 nodes lying on the obstack. Remove these by a dead node elimination,
1020 i.e., a copying garbage collection. */
1022 optimize_in_place (ir_node *n)
1027 if (!get_optimize()) return n;
1029 /* if not optimize return n */
1031 /* Here this is possible. Why? */
1035 /* constant expression evaluation / constant folding */
1036 if (get_opt_constant_folding()) {
1037 /* constants can not be evaluated */
1038 if (get_irn_op(n) != op_Const) {
1039 /* try to evaluate */
1040 tv = computed_value (n);
1042 /* evaluation was succesful -- replace the node. */
1043 n = new_Const (get_tv_mode (tv), tv);
1044 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1046 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1051 /* remove unnecessary nodes */
1052 /*if (get_opt_constant_folding()) */
1053 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1054 n = equivalent_node (n);
1056 /** common subexpression elimination **/
1057 /* Checks whether n is already available. */
1058 /* The block input is used to distinguish different subexpressions. Right
1059 now all nodes are pinned to blocks, i.e., the cse only finds common
1060 subexpressions within a block. */
1062 n = identify (current_ir_graph->value_table, n);
1064 /* identify found a cse, so deallocate the old node. */
1066 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1069 /* Some more constant expression evaluation. */
1070 if (get_opt_constant_folding())
1071 n = transform_node (n);
1073 /* Remove nodes with dead (Bad) input. */
1075 /* Now we can verify the node, as it has no dead inputs any more. */
1078 /* Now we have a legal, useful node. Enter it in hash table for cse.
1079 Blocks should be unique anyways. (Except the successor of start:
1080 is cse with the start block!) */
1081 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1082 n = identify_remember (current_ir_graph->value_table, n);