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 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 n = get_nodes_Block(get_Block_cfgpred(n, 0));
307 } else if ((n != current_ir_graph->start_block) &&
308 (n != current_ir_graph->end_block) ) {
310 /* If all inputs are dead, this block is dead too, except if it is
311 the start or end block. This is a step of unreachable code
313 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
314 if (!is_Bad(get_Block_cfgpred(n, i))) break;
316 if (i == get_Block_n_cfgpreds(n))
322 case iro_Jmp: /* GL: Why not same for op_Raise?? */
323 /* unreachable code elimination */
324 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
326 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
327 See cases for iro_Cond and iro_Proj in transform_node. */
328 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
329 case iro_Or: if (a == b) {n = a; break;}
334 /* After running compute_node there is only one constant predecessor.
335 Find this predecessors value and remember the other node: */
336 if ((tv = computed_value (a))) {
338 } else if ((tv = computed_value (b))) {
342 /* If this predecessors constant value is zero, the operation is
343 unnecessary. Remove it: */
344 if (tarval_classify (tv) == 0) {
354 /* these operations are not commutative. Test only one predecessor. */
355 if (tarval_classify (computed_value (b)) == 0) {
357 /* Test if b > #bits of a ==> return 0 / divide b by #bits
358 --> transform node? */
361 case iro_Not: /* NotNot x == x */
362 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
363 out of bounds exception if min =! max? */
364 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
365 n = get_unop_op(get_unop_op(n));
368 /* Mul is commutative and has again an other neutral element. */
369 if (tarval_classify (computed_value (a)) == 1) {
371 } else if (tarval_classify (computed_value (b)) == 1) {
376 /* Div is not commutative. */
377 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
378 /* Turn Div into a tuple (mem, bad, a) */
379 ir_node *mem = get_Div_mem(n);
380 turn_into_tuple(n, 3);
381 set_Tuple_pred(n, 0, mem);
382 set_Tuple_pred(n, 1, new_Bad());
383 set_Tuple_pred(n, 2, a);
386 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
387 teated in transform node.
388 case iro_Mod, Quot, DivMod
392 /* And has it's own neutral element */
393 else if (tarval_classify (computed_value (a)) == -1) {
395 } else if (tarval_classify (computed_value (b)) == -1) {
400 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
402 } else if (get_irn_mode(n) == mode_b) {
403 if (get_irn_op(a) == op_Conv &&
404 get_irn_mode (get_Conv_op(a)) == mode_b) {
405 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
412 /* Several optimizations:
413 - no Phi in start block.
414 - remove Id operators that are inputs to Phi
415 - fold Phi-nodes, iff they have only one predecessor except
421 ir_node *block = NULL; /* to shutup gcc */
422 ir_node *first_val = NULL; /* to shutup gcc */
423 ir_node *scnd_val = NULL; /* to shutup gcc */
425 n_preds = get_Phi_n_preds(n);
427 block = get_nodes_Block(n);
428 assert(get_irn_op (block) == op_Block);
430 /* there should be no Phi nodes in the Start region. */
431 if (block == current_ir_graph->start_block) {
436 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
437 /* GL: why not return new_Bad? */
442 /* first we test for a special case: */
443 /* Confirm is a special node fixing additional information for a
444 value that is known at a certain point. This is useful for
445 dataflow analysis. */
447 ir_node *a = follow_Id (get_Phi_pred(n, 0));
448 ir_node *b = follow_Id (get_Phi_pred(n, 1));
449 if ( (get_irn_op(a) == op_Confirm)
450 && (get_irn_op(b) == op_Confirm)
451 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
452 && (get_irn_n(a, 1) == get_irn_n (b, 1))
453 && (a->data.num == (~b->data.num & irpn_True) )) {
454 n = follow_Id (get_irn_n(a, 0));
460 /* Find first non-self-referencing input */
461 for (i = 0; i < n_preds; ++i) {
462 first_val = follow_Id(get_Phi_pred(n, i));
464 set_Phi_pred(n, i, first_val);
465 if ( (first_val != n) /* not self pointer */
466 && (get_irn_op(first_val) != op_Bad) /* value not dead */
467 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
468 break; /* then found first value. */
472 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
473 if (i >= n_preds) { n = new_Bad(); break; }
477 /* follow_Id () for rest of inputs, determine if any of these
478 are non-self-referencing */
479 while (++i < n_preds) {
480 scnd_val = follow_Id(get_Phi_pred(n, i));
482 set_Phi_pred(n, i, scnd_val);
484 && (scnd_val != first_val)
485 && (get_irn_op(scnd_val) != op_Bad)
486 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
491 /* Fold, if no multiple distinct non-self-referencing inputs */
495 /* skip the remaining Ids. */
496 while (++i < n_preds) {
497 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
505 #if 0 /* Is an illegal transformation: different nodes can
506 represent the same pointer value!! */
507 a = skip_Proj(get_Load_mem(n));
510 if (get_irn_op(a) == op_Store) {
511 if ( different_identity (b, get_Store_ptr(a))) {
512 /* load and store use different pointers, therefore load
513 needs not take store's memory but the state before. */
514 set_Load_mem (n, get_Store_mem(a));
515 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
522 /* remove unnecessary store. */
524 a = skip_Proj(get_Store_mem(n));
525 b = get_Store_ptr(n);
526 c = skip_Proj(get_Store_value(n));
528 if (get_irn_op(a) == op_Store
529 && get_Store_ptr(a) == b
530 && skip_Proj(get_Store_value(a)) == c) {
531 /* We have twice exactly the same store -- a write after write. */
533 } else if (get_irn_op(c) == op_Load
534 && (a == c || skip_Proj(get_Load_mem(c)) == a)
535 && get_Load_ptr(c) == b )
536 /* !!!??? and a cryptic test */ {
537 /* We just loaded the value from the same memory, i.e., the store
538 doesn't change the memory -- a write after read. */
539 turn_into_tuple(n, 2);
540 set_Tuple_pred(n, 0, a);
541 set_Tuple_pred(n, 1, new_Bad());
548 a = get_Proj_pred(n);
550 if ( get_irn_op(a) == op_Tuple) {
551 /* Remove the Tuple/Proj combination. */
552 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
553 n = get_Tuple_pred(a, get_Proj_proj(n));
555 assert(0); /* This should not happen! */
558 } else if (get_irn_mode(n) == mode_X &&
559 is_Bad(get_nodes_Block(n))) {
560 /* Remove dead control flow. */
574 } /* end equivalent_node() */
577 /* tries several [inplace] [optimizing] transformations and returns a
578 equivalent node. The difference to equivalent_node is that these
579 transformations _do_ generate new nodes, and thus the old node must
580 not be freed even if the equivalent node isn't the old one. */
582 transform_node (ir_node *n)
585 ir_node *a = NULL, *b;
588 switch (get_irn_opcode(n)) {
594 a = get_DivMod_left(n);
595 b = get_DivMod_right(n);
596 mode = get_irn_mode(a);
598 if (!( mode_is_int(get_irn_mode(a))
599 && mode_is_int(get_irn_mode(b))))
603 a = new_Const (mode, tarval_from_long (mode, 1));
604 b = new_Const (mode, tarval_from_long (mode, 0));
611 if (tarval_classify(tb) == 1) {
612 b = new_Const (mode, tarval_from_long (mode, 0));
616 resa = tarval_div (ta, tb);
617 if (!resa) break; /* Causes exception!!! Model by replacing through
618 Jmp for X result!? */
619 resb = tarval_mod (ta, tb);
620 if (!resb) break; /* Causes exception! */
621 a = new_Const (mode, resa);
622 b = new_Const (mode, resb);
625 } else if (tarval_classify (ta) == 0) {
630 if (evaluated) { /* replace by tuple */
631 ir_node *mem = get_DivMod_mem(n);
632 turn_into_tuple(n, 4);
633 set_Tuple_pred(n, 0, mem);
634 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
635 set_Tuple_pred(n, 2, a);
636 set_Tuple_pred(n, 3, b);
637 assert(get_nodes_Block(n));
643 /* Replace the Cond by a Jmp if it branches on a constant
646 a = get_Cond_selector(n);
649 if (ta && (get_irn_mode(a) == mode_b)) {
650 /* It's a boolean Cond, branching on a boolean constant.
651 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
652 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
653 turn_into_tuple(n, 2);
654 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
655 set_Tuple_pred(n, 0, new_Bad());
656 set_Tuple_pred(n, 1, jmp);
658 set_Tuple_pred(n, 0, jmp);
659 set_Tuple_pred(n, 1, new_Bad());
661 } else if (ta && (get_irn_mode(a) == mode_I) && (get_Cond_kind(n) == dense)) {
662 /* I don't want to allow Tuples smaller than the biggest Proj.
663 Also this tuple might get really big...
664 I generate the Jmp here, and remember it in link. Link is used
665 when optimizing Proj. */
666 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
667 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
668 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
669 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
670 /* The Eor is a negate. Generate a new Cond without the negate,
671 simulate the negate by exchanging the results. */
672 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
674 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
675 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
676 /* A Not before the Cond. Generate a new Cond without the Not,
677 simulate the Not by exchanging the results. */
678 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
685 a = get_Proj_pred(n);
687 if ( (get_irn_op(a) == op_Cond)
689 && get_irn_op(get_irn_link(a)) == op_Cond) {
690 /* Use the better Cond if the Proj projs from a Cond which get's
691 its result from an Eor/Not. */
692 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
693 || (get_irn_op(get_Cond_selector(a)) == op_Not))
694 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
695 && (get_irn_op(get_irn_link(a)) == op_Cond)
696 && (get_Cond_selector(get_irn_link(a)) ==
697 get_Eor_left(get_Cond_selector(a))));
698 set_Proj_pred(n, get_irn_link(a));
699 if (get_Proj_proj(n) == 0)
703 } else if ( (get_irn_op(a) == op_Cond)
704 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
706 && (get_Cond_kind(a) == dense)) {
707 /* The Cond is a Switch on a Constant */
708 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
709 /* The always taken branch, reuse the existing Jmp. */
710 if (!get_irn_link(a)) /* well, if it exists ;-> */
711 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
712 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
714 } else {/* Not taken control flow, but be careful with the default! */
715 if (get_Proj_proj(n) < a->attr.c.default_proj){
716 /* a never taken branch */
719 a->attr.c.default_proj = get_Proj_proj(n);
724 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
726 b = get_Eor_right(n);
728 if ( (get_irn_mode(n) == mode_b)
729 && (get_irn_op(a) == op_Proj)
730 && (get_irn_mode(a) == mode_b)
731 && (tarval_classify (computed_value (b)) == 1)
732 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
733 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
734 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
735 mode_b, get_negated_pnc(get_Proj_proj(a)));
736 else if ( (get_irn_mode(n) == mode_b)
737 && (tarval_classify (computed_value (b)) == 1))
738 /* The Eor is a Not. Replace it by a Not. */
739 /* ????!!!Extend to bitfield 1111111. */
740 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
746 if ( (get_irn_mode(n) == mode_b)
747 && (get_irn_op(a) == op_Proj)
748 && (get_irn_mode(a) == mode_b)
749 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
750 /* We negate a Cmp. The Cmp has the negated result anyways! */
751 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
752 mode_b, get_negated_pnc(get_Proj_proj(a)));
760 /* **************** Common Subexpression Elimination **************** */
762 /* Compare function for two nodes in the hash table. Gets two */
763 /* nodes as parameters. */
764 /* @@@ a+b != b+a ? */
766 vt_cmp (const void *elt, const void *key)
774 if (a == b) return 0;
776 if ((get_irn_op(a) != get_irn_op(b)) ||
777 (get_irn_mode(a) != get_irn_mode(b))) return 1;
779 /* compare if a's in and b's in are equal */
780 /* GL: we optimize only nodes with in arrays of fixed sizes.
781 if (get_irn_arity (a) != -2) {
782 ins = get_irn_arity (a);
783 if (ins != get_irn_arity (b)) return 1;
784 ain = get_irn_in (a);
785 bin = get_irn_in (b);
788 if (get_irn_arity (a) != get_irn_arity(b))
791 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
792 /* do if (*ain++ != *bin++) return 1; while (ins--); */
793 for (i = -1; i < get_irn_arity(a); i++)
794 if (get_irn_n(a, i) != get_irn_n(b, i))
798 switch (get_irn_opcode(a)) {
800 return get_irn_const_attr (a) != get_irn_const_attr (b);
802 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
804 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
805 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
807 return (get_irn_free_attr(a) != get_irn_free_attr(b));
809 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
810 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
812 return (get_irn_call_attr(a) != get_irn_call_attr(b));
814 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
815 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
816 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
817 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
818 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
819 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
821 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
829 ir_node_hash (ir_node *node)
834 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
835 h = get_irn_arity(node);
837 /* consider all in nodes... except the block. */
838 for (i = 0; i < get_irn_arity(node); i++) {
839 h = 9*h + (unsigned long)get_irn_n(node, i);
843 h = 9*h + (unsigned long) get_irn_mode (node);
845 h = 9*h + (unsigned long) get_irn_op (node);
851 new_identities (void)
853 return new_pset (vt_cmp, TUNE_NIR_NODES);
857 del_identities (pset *value_table)
859 del_pset (value_table);
862 /* Return the canonical node computing the same value as n.
863 Looks up the node in a hash table. */
864 static inline ir_node *
865 identify (pset *value_table, ir_node *n)
869 if (!value_table) return n;
871 switch (get_irn_opcode (n)) {
878 /* for commutative operators perform a OP b == b OP a */
879 if (get_binop_left(n) > get_binop_right(n)) {
880 ir_node *h = get_binop_left(n);
881 set_binop_left(n, get_binop_right(n));
882 set_binop_right(n, h);
888 o = pset_find (value_table, n, ir_node_hash (n));
894 /* Return the canonical node computing the same value as n.
895 Looks up the node in a hash table, enters it in the table
896 if it isn't there yet. */
898 identify_remember (pset *value_table, ir_node *node)
902 if (!value_table) return node;
904 /* lookup or insert in hash table with given hash key. */
905 o = pset_insert (value_table, node, ir_node_hash (node));
907 if (o == node) return node;
913 add_identities (pset *value_table, ir_node *node) {
914 identify_remember (value_table, node);
917 /* garbage in, garbage out. If a node has a dead input, i.e., the
918 Bad node is input to the node, return the Bad node. */
919 static inline ir_node *
923 ir_op* op = get_irn_op(node);
925 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
926 blocks predecessors is dead. */
927 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
928 for (i = -1; i < get_irn_arity(node); i++) {
929 if (is_Bad(get_irn_n(node, i))) {
935 /* If Block has only Bads as predecessors it's garbage. */
936 /* If Phi has only Bads as predecessors it's garbage. */
937 if (op == op_Block || op == op_Phi) {
938 for (i = 0; i < get_irn_arity(node); i++) {
939 if (!is_Bad(get_irn_n(node, i))) break;
941 if (i = get_irn_arity(node)) node = new_Bad();
948 /* These optimizations deallocate nodes from the obstack.
949 It can only be called if it is guaranteed that no other nodes
950 reference this one, i.e., right after construction of a node. */
952 optimize (ir_node *n)
957 /* Allways optimize Phi nodes: part of the construction. */
958 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
960 /* if not optimize return n */
962 printf(" attention: empty node!!! \n");
966 /* constant expression evaluation / constant folding */
967 if (get_opt_constant_folding()) {
968 /* constants can not be evaluated */
969 if (get_irn_op(n) != op_Const) {
970 /* try to evaluate */
971 tv = computed_value (n);
973 /* evaluation was succesful -- replace the node. */
974 obstack_free (current_ir_graph->obst, n);
975 return new_Const (get_tv_mode (tv), tv);
980 /* remove unnecessary nodes */
981 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
982 n = equivalent_node (n);
984 /** common subexpression elimination **/
985 /* Checks whether n is already available. */
986 /* The block input is used to distinguish different subexpressions. Right
987 now all nodes are pinned to blocks, i.e., the cse only finds common
988 subexpressions within a block. */
990 n = identify (current_ir_graph->value_table, n);
991 /* identify found a cse, so deallocate the old node. */
993 obstack_free (current_ir_graph->obst, old_n);
994 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
997 /* Some more constant expression evaluation that does not allow to
999 if (get_opt_constant_folding())
1000 n = transform_node (n);
1002 /* Remove nodes with dead (Bad) input. */
1003 if (get_opt_unreachable_code())
1005 /* Now we can verify the node, as it has no dead inputs any more. */
1008 /* Now we have a legal, useful node. Enter it in hash table for cse */
1009 if (get_opt_cse()) {
1010 n = identify_remember (current_ir_graph->value_table, n);
1013 #if 0 /* GL: what's the use of this?? */
1014 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
1015 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
1016 pdeq_putr (current_ir_graph->keep.living, n);
1023 /* These optimizations never deallocate nodes. This can cause dead
1024 nodes lying on the obstack. Remove these by a dead node elimination,
1025 i.e., a copying garbage collection. */
1027 optimize_in_place (ir_node *n)
1032 if (!get_optimize()) return n;
1034 /* if not optimize return n */
1036 /* Here this is possible. Why? */
1040 /* constant expression evaluation / constant folding */
1041 if (get_opt_constant_folding()) {
1042 /* constants can not be evaluated */
1043 if (get_irn_op(n) != op_Const) {
1044 /* try to evaluate */
1045 tv = computed_value (n);
1047 /* evaluation was succesful -- replace the node. */
1048 n = new_Const (get_tv_mode (tv), tv);
1049 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1051 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1056 /* remove unnecessary nodes */
1057 /*if (get_opt_constant_folding()) */
1058 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1059 n = equivalent_node (n);
1061 /** common subexpression elimination **/
1062 /* Checks whether n is already available. */
1063 /* The block input is used to distinguish different subexpressions. Right
1064 now all nodes are pinned to blocks, i.e., the cse only finds common
1065 subexpressions within a block. */
1067 n = identify (current_ir_graph->value_table, n);
1069 /* identify found a cse, so deallocate the old node. */
1071 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1074 /* Some more constant expression evaluation. */
1075 if (get_opt_constant_folding())
1076 n = transform_node (n);
1078 /* Remove nodes with dead (Bad) input. */
1079 if (get_opt_unreachable_code())
1081 /* Now we can verify the node, as it has no dead inputs any more. */
1084 /* Now we have a legal, useful node. Enter it in hash table for cse.
1085 Blocks should be unique anyways. (Except the successor of start:
1086 is cse with the start block!) */
1087 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1088 n = identify_remember (current_ir_graph->value_table, n);