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_minus (ta);*/ res;
92 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
93 res = tarval_mul (ta, tb);
95 /* calls computed_value recursive and returns the 0 with proper
96 mode. Why is this an extra case? */
98 if ( (tarval_classify ((v = computed_value (a))) == 0)
99 || (tarval_classify ((v = computed_value (b))) == 0)) {
106 res = /*tarval_abs (ta);*/ res;
107 /* allowed or problems with max/min ?? */
111 res = tarval_and (ta, tb);
114 if ( (tarval_classify ((v = computed_value (a))) == 0)
115 || (tarval_classify ((v = computed_value (b))) == 0)) {
122 res = tarval_or (ta, tb);
125 if ( (tarval_classify ((v = computed_value (a))) == -1)
126 || (tarval_classify ((v = computed_value (b))) == -1)) {
131 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
132 case iro_Not: if (ta) { /*res = tarval_not (ta)*/; } break;
133 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
134 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
135 case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
136 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
137 case iro_Conv: if(ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
143 a = get_Proj_pred(n);
144 /* Optimize Cmp nodes.
145 This performs a first step of unreachable code elimination.
146 Proj can not be computed, but folding a Cmp above the Proj here is
147 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
149 There are several case where we can evaluate a Cmp node:
150 1. The nodes compared are both the same. If we compare for
151 equal, this will return true, else it will return false.
152 This step relies on cse.
153 2. The predecessors of Cmp are target values. We can evaluate
155 3. The predecessors are Allocs or void* constants. Allocs never
156 return NULL, they raise an exception. Therefore we can predict
158 if (get_irn_op(a) == op_Cmp) {
159 aa = get_Cmp_left(a);
160 ab = get_Cmp_right(a);
161 if (aa == ab) { /* 1.: */
162 /* This is a tric with the bits used for encoding the Cmp
163 Proj numbers, the following statement is not the same:
164 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
165 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
167 tarval *taa = computed_value (aa);
168 tarval *tab = computed_value (ab);
169 if (taa && tab) { /* 2.: */
170 /* strange checks... */
171 ir_pncmp flags = tarval_comp (taa, tab);
172 if (flags != irpn_False) {
173 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
175 } else { /* check for 3.: */
176 ir_node *aaa = skip_nop(skip_Proj(aa));
177 ir_node *aba = skip_nop(skip_Proj(ab));
178 if ( ( (/* aa is ProjP and aaa is Alloc */
179 (get_irn_op(aa) == op_Proj)
180 && (get_irn_mode(aa) == mode_p)
181 && (get_irn_op(aaa) == op_Alloc))
182 && ( (/* ab is constant void */
183 (get_irn_op(ab) == op_Const)
184 && (get_irn_mode(ab) == mode_p)
185 && (get_Const_tarval(ab) == tarval_p_void))
186 || (/* ab is other Alloc */
187 (get_irn_op(ab) == op_Proj)
188 && (get_irn_mode(ab) == mode_p)
189 && (get_irn_op(aba) == op_Alloc)
191 || (/* aa is void and aba is Alloc */
192 (get_irn_op(aa) == op_Const)
193 && (get_irn_mode(aa) == mode_p)
194 && (get_Const_tarval(aa) == tarval_p_void)
195 && (get_irn_op(ab) == op_Proj)
196 && (get_irn_mode(ab) == mode_p)
197 && (get_irn_op(aba) == op_Alloc)))
199 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
203 /* printf(" # comp_val: Proj node, not optimized\n"); */
215 /* returns 1 if the a and b are pointers to different locations. */
217 different_identity (ir_node *a, ir_node *b)
219 assert (get_irn_mode (a) == mode_p
220 && get_irn_mode (b) == mode_p);
222 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
223 ir_node *a1 = get_Proj_pred (a);
224 ir_node *b1 = get_Proj_pred (b);
225 if (a1 != b1 && get_irn_op (a1) == op_Alloc
226 && get_irn_op (b1) == op_Alloc)
233 /* equivalent_node returns a node equivalent to N. It skips all nodes that
234 perform no actual computation, as, e.g., the Id nodes. It does not create
235 new nodes. It is therefore safe to free N if the node returned is not N.
236 If a node returns a Tuple we can not just skip it. If the size of the
237 in array fits, we transform n into a tuple (e.g., Div). */
239 equivalent_node (ir_node *n)
242 ir_node *a = NULL; /* to shutup gcc */
243 ir_node *b = NULL; /* to shutup gcc */
244 ir_node *c = NULL; /* to shutup gcc */
246 ins = get_irn_arity (n);
248 /* get the operands we will work on */
250 a = get_binop_left(n);
251 b = get_binop_right(n);
252 } else if (is_unop(n)) {
256 /* skip unnecessary nodes. */
257 switch (get_irn_opcode (n)) {
260 /* The Block constructor does not call optimize, but mature_block
261 calls the optimization. */
262 assert(get_Block_matured(n));
264 /* A single entry Block following a single exit Block can be merged,
265 if it is not the Start block. */
266 /* !!! Beware, all Phi-nodes of n must have been optimized away.
267 This should be true, as the block is matured before optimize is called.
268 But what about Phi-cycles with the Phi0/Id that could not be resolved? */
269 if (get_Block_n_cfgpreds(n) == 1
270 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
271 n = get_nodes_Block(get_Block_cfgpred(n, 0));
273 } else if (n != current_ir_graph->start_block) {
275 /* If all inputs are dead, this block is dead too, except if it is
276 the start block. This is a step of unreachable code elimination */
277 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
278 if (!is_Bad(get_Block_cfgpred(n, i))) break;
280 if (i == get_Block_n_cfgpreds(n))
286 case iro_Jmp: /* GL: Why not same for op_Raise?? */
287 /* unreachable code elimination */
288 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
290 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
291 See cases for iro_Cond and iro_Proj in transform_node. */
292 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
293 case iro_Or: if (a == b) {n = a; break;}
298 /* After running compute_node there is only one constant predecessor.
299 Find this predecessors value and remember the other node: */
300 if ((tv = computed_value (a))) {
302 } else if ((tv = computed_value (b))) {
306 /* If this predecessors constant value is zero, the operation is
307 unnecessary. Remove it: */
308 if (tarval_classify (tv) == 0) {
318 /* these operations are not commutative. Test only one predecessor. */
319 if (tarval_classify (computed_value (b)) == 0) {
321 /* Test if b > #bits of a ==> return 0 / divide b by #bits
322 --> transform node? */
325 case iro_Not: /* NotNot x == x */
326 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
327 out of bounds exception if min =! max? */
328 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
329 n = get_unop_op(get_unop_op(n));
332 /* Mul is commutative and has again an other neutral element. */
333 if (tarval_classify (computed_value (a)) == 1) {
335 } else if (tarval_classify (computed_value (b)) == 1) {
340 /* Div is not commutative. */
341 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
342 /* Turn Div into a tuple (mem, bad, a) */
343 ir_node *mem = get_Div_mem(n);
344 turn_into_tuple(n, 3);
345 set_Tuple_pred(n, 0, mem);
346 set_Tuple_pred(n, 1, new_Bad());
347 set_Tuple_pred(n, 2, a);
350 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
351 teated in transform node.
352 case iro_Mod, Quot, DivMod
356 /* And has it's own neutral element */
357 else if (tarval_classify (computed_value (a)) == -1) {
359 } else if (tarval_classify (computed_value (b)) == -1) {
364 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
366 } else if (get_irn_mode(n) == mode_b) {
367 if (get_irn_op(a) == op_Conv &&
368 get_irn_mode (get_Conv_op(a)) == mode_b) {
369 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
376 /* Several optimizations:
377 - no Phi in start block.
378 - remove Id operators that are inputs to Phi
379 - fold Phi-nodes, iff they have only one predecessor except
385 ir_node *block = NULL; /* to shutup gcc */
386 ir_node *first_val = NULL; /* to shutup gcc */
387 ir_node *scnd_val = NULL; /* to shutup gcc */
389 n_preds = get_Phi_n_preds(n);
391 block = get_nodes_Block(n);
392 assert(get_irn_op (block) == op_Block);
394 /* there should be no Phi nodes in the Start region. */
395 if (block == current_ir_graph->start_block) {
400 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
401 /* GL: why not return new_Bad? */
406 /* first we test for a special case: */
407 /* Confirm is a special node fixing additional information for a
408 value that is known at a certain point. This is useful for
409 dataflow analysis. */
411 ir_node *a = follow_Id (get_Phi_pred(n, 0));
412 ir_node *b = follow_Id (get_Phi_pred(n, 1));
413 if ( (get_irn_op(a) == op_Confirm)
414 && (get_irn_op(b) == op_Confirm)
415 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
416 && (get_irn_n(a, 1) == get_irn_n (b, 1))
417 && (a->data.num == (~b->data.num & irpn_True) )) {
418 n = follow_Id (get_irn_n(a, 0));
424 /* Find first non-self-referencing input */
425 for (i = 0; i < n_preds; ++i) {
426 first_val = follow_Id(get_Phi_pred(n, i));
428 set_Phi_pred(n, i, first_val);
429 if ( (first_val != n) /* not self pointer */
430 && (get_irn_op(first_val) != op_Bad) /* value not dead */
431 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
432 break; /* then found first value. */
436 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
437 if (i >= n_preds) { n = new_Bad(); break; }
441 /* follow_Id () for rest of inputs, determine if any of these
442 are non-self-referencing */
443 while (++i < n_preds) {
444 scnd_val = follow_Id(get_Phi_pred(n, i));
446 set_Phi_pred(n, i, scnd_val);
448 && (scnd_val != first_val)
449 && (get_irn_op(scnd_val) != op_Bad)
450 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
455 /* Fold, if no multiple distinct non-self-referencing inputs */
459 /* skip the remaining Ids. */
460 while (++i < n_preds) {
461 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
469 a = skip_Proj(get_Load_mem(n));
470 b = skip_Proj(get_Load_ptr(n));
472 if (get_irn_op(a) == op_Store) {
473 if ( different_identity (b, get_Store_ptr(a))) {
474 /* load and store use different pointers, therefore load
475 needs not take store's memory but the state before. */
476 set_Load_mem (n, get_Store_mem(a));
477 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
483 /* remove unnecessary store. */
485 a = skip_Proj(get_Store_mem(n));
486 b = get_Store_ptr(n);
487 c = skip_Proj(get_Store_value(n));
489 if (get_irn_op(a) == op_Store
490 && get_Store_ptr(a) == b
491 && skip_Proj(get_Store_value(a)) == c) {
492 /* We have twice exactly the same store -- a write after write. */
494 } else if (get_irn_op(c) == op_Load
495 && (a == c || skip_Proj(get_Load_mem(c)) == a)
496 && get_Load_ptr(c) == b )
497 /* !!!??? and a cryptic test */ {
498 /* We just loaded the value from the same memory, i.e., the store
499 doesn't change the memory -- a write after read. */
500 turn_into_tuple(n, 2);
501 set_Tuple_pred(n, 0, a);
502 set_Tuple_pred(n, 1, new_Bad());
509 a = get_Proj_pred(n);
511 if ( get_irn_op(a) == op_Tuple) {
512 /* Remove the Tuple/Proj combination. */
513 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
514 n = get_Tuple_pred(a, get_Proj_proj(n));
516 assert(0); /* This should not happen! (GL added this assert) */
519 } else if (get_irn_mode(n) == mode_X &&
520 is_Bad(get_nodes_Block(n))) {
521 /* Remove dead control flow. */
535 } /* end equivalent_node() */
538 /* tries several [inplace] [optimizing] transformations and returns a
539 equivalent node. The difference to equivalent_node is that these
540 transformations _do_ generate new nodes, and thus the old node must
541 not be freed even if the equivalent node isn't the old one. */
543 transform_node (ir_node *n)
546 ir_node *a = NULL, *b;
549 switch (get_irn_opcode(n)) {
555 a = get_DivMod_left(n);
556 b = get_DivMod_right(n);
557 mode = get_irn_mode(a);
559 if (!( mode_is_int(get_irn_mode(a))
560 && mode_is_int(get_irn_mode(b))))
564 a = new_Const (mode, tarval_from_long (mode, 1));
565 b = new_Const (mode, tarval_from_long (mode, 0));
572 if (tarval_classify(tb) == 1) {
573 b = new_Const (mode, tarval_from_long (mode, 0));
577 resa = tarval_div (ta, tb);
578 if (!resa) break; /* Causes exception!!! Model by replacing through
579 Jmp for X result!? */
580 resb = tarval_mod (ta, tb);
581 if (!resb) break; /* Causes exception! */
582 a = new_Const (mode, resa);
583 b = new_Const (mode, resb);
586 } else if (tarval_classify (ta) == 0) {
591 if (evaluated) { /* replace by tuple */
592 ir_node *mem = get_DivMod_mem(n);
593 turn_into_tuple(n, 4);
594 set_Tuple_pred(n, 0, mem);
595 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
596 set_Tuple_pred(n, 2, a);
597 set_Tuple_pred(n, 3, b);
598 assert(get_nodes_Block(n));
604 /* Replace the Cond by a Jmp if it branches on a constant
607 a = get_Cond_selector(n);
610 if (ta && (get_irn_mode(a) == mode_b)) {
611 /* It's a boolean Cond, branching on a boolean constant.
612 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
613 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
614 turn_into_tuple(n, 2);
615 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
616 set_Tuple_pred(n, 0, new_Bad());
617 set_Tuple_pred(n, 1, jmp);
619 set_Tuple_pred(n, 0, jmp);
620 set_Tuple_pred(n, 1, new_Bad());
622 } else if (ta && (get_irn_mode(a) == mode_I)) {
623 /* I don't want to allow Tuples smaller than the biggest Proj.
624 Also this tuple might get really big...
625 I generate the Jmp here, and remember it in link. Link is used
626 when optimizing Proj. */
627 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
628 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
629 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
630 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
631 /* The Eor is a negate. Generate a new Cond without the negate,
632 simulate the negate by exchanging the results. */
633 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
635 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
636 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
637 /* A Not before the Cond. Generate a new Cond without the Not,
638 simulate the Not by exchanging the results. */
639 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
646 a = get_Proj_pred(n);
648 if ( (get_irn_op(a) == op_Cond)
650 && get_irn_op(get_irn_link(a)) == op_Cond) {
651 /* Use the better Cond if the Proj projs from a Cond which get's
652 its result from an Eor/Not. */
653 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
654 || (get_irn_op(get_Cond_selector(a)) == op_Not))
655 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
656 && (get_irn_op(get_irn_link(a)) == op_Cond)
657 && (get_Cond_selector(get_irn_link(a)) ==
658 get_Eor_left(get_Cond_selector(a))));
659 set_Proj_pred(n, get_irn_link(a));
660 if (get_Proj_proj(n) == 0)
664 } else if ( (get_irn_op(a) == op_Cond)
665 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
667 /* The Cond is a Switch on a Constant */
668 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
669 /* The always taken branch, reuse the existing Jmp. */
670 if (!get_irn_link(a)) /* well, if it exists ;-> */
671 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
672 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
675 /* a never taken branch */
681 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
683 b = get_Eor_right(n);
685 if ( (get_irn_mode(n) == mode_b)
686 && (get_irn_op(a) == op_Proj)
687 && (get_irn_mode(a) == mode_b)
688 && (tarval_classify (computed_value (b)) == 1)
689 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
690 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
691 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
692 mode_b, get_negated_pnc(get_Proj_proj(a)));
693 else if ( (get_irn_mode(n) == mode_b)
694 && (tarval_classify (computed_value (b)) == 1))
695 /* The Eor is a Not. Replace it by a Not. */
696 /* ????!!!Extend to bitfield 1111111. */
697 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
703 if ( (get_irn_mode(n) == mode_b)
704 && (get_irn_op(a) == op_Proj)
705 && (get_irn_mode(a) == mode_b)
706 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
707 /* We negate a Cmp. The Cmp has the negated result anyways! */
708 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
709 mode_b, get_negated_pnc(get_Proj_proj(a)));
717 /***************** Common Subexpression Elimination *****************/
719 /* Compare function for two nodes in the hash table. Gets two */
720 /* nodes as parameters. */
721 /* @@@ a+b != b+a ? */
723 vt_cmp (const void *elt, const void *key)
731 if (a == b) return 0;
733 if ((get_irn_op(a) != get_irn_op(b)) ||
734 (get_irn_mode(a) != get_irn_mode(b))) return 1;
736 /* compare if a's in and b's in are equal */
737 /* GL: we optimize only nodes with in arrays of fixed sizes.
738 if (get_irn_arity (a) != -2) {
739 ins = get_irn_arity (a);
740 if (ins != get_irn_arity (b)) return 1;
741 ain = get_irn_in (a);
742 bin = get_irn_in (b);
745 if (get_irn_arity (a) != get_irn_arity(b))
748 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
749 /* do if (*ain++ != *bin++) return 1; while (ins--); */
750 for (i = -1; i < get_irn_arity(a); i++)
751 if (get_irn_n(a, i) != get_irn_n(b, i))
755 switch (get_irn_opcode(a)) {
757 return get_irn_const_attr (a) != get_irn_const_attr (b);
759 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
761 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
762 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
764 return (get_irn_free_attr(a) != get_irn_free_attr(b));
766 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
767 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
769 return (get_irn_call_attr(a)->kind != get_irn_call_attr(b)->kind)
770 || (get_irn_call_attr(a)->arity != get_irn_call_attr(b)->arity);
772 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
773 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
774 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
775 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
776 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
777 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
779 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
787 ir_node_hash (ir_node *node)
792 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
793 h = get_irn_arity(node);
795 /* consider all in nodes... except the block. */
796 for (i = 0; i < get_irn_arity(node); i++) {
797 h = 9*h + (unsigned long)get_irn_n(node, i);
801 h = 9*h + (unsigned long) get_irn_mode (node);
803 h = 9*h + (unsigned long) get_irn_op (node);
809 new_identities (void)
811 return new_pset (vt_cmp, TUNE_NIR_NODES);
815 del_identities (pset *value_table)
817 del_pset (value_table);
820 /* Return the canonical node computing the same value as n.
821 Looks up the node in a hash table. */
822 static inline ir_node *
823 identify (pset *value_table, ir_node *n)
827 if (!value_table) return n;
829 switch (get_irn_opcode (n)) {
836 /* for commutative operators perform a OP b == b OP a */
837 if (get_binop_left(n) > get_binop_right(n)) {
838 ir_node *h = get_binop_left(n);
839 set_binop_left(n, get_binop_right(n));
840 set_binop_right(n, h);
846 o = pset_find (value_table, n, ir_node_hash (n));
852 /* Return the canonical node computing the same value as n.
853 Looks up the node in a hash table, enters it in the table
854 if it isn't there yet. */
856 identify_remember (pset *value_table, ir_node *node)
860 if (!value_table) return node;
862 /* lookup or insert in hash table with given hash key. */
863 o = pset_insert (value_table, node, ir_node_hash (node));
865 if (o == node) return node;
870 /* garbage in, garbage out. If a node has a dead input, i.e., the
871 Bad node is input to the node, return the Bad node. */
872 static inline ir_node *
876 ir_op* op = get_irn_op(node);
878 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
879 blocks predecessors is dead. */
880 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
881 for (i = -1; i < get_irn_arity(node); i++) {
882 if (is_Bad(get_irn_n(node, i))) {
888 /* If Block has only Bads as predecessors it's garbage. */
889 /* If Phi has only Bads as predecessors it's garbage. */
890 if (op == op_Block || op == op_Phi) {
891 for (i = 0; i < get_irn_arity(node); i++) {
892 if (!is_Bad(get_irn_n(node, i))) break;
894 if (i = get_irn_arity(node)) node = new_Bad();
901 /* These optimizations deallocate nodes from the obstack.
902 It can only be called if it is guaranteed that no other nodes
903 reference this one, i.e., right after construction of a node. */
905 optimize (ir_node *n)
910 /* Allways optimize Phi nodes: part of the construction. */
911 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
913 /* if not optimize return n */
915 printf(" attention: empty node!!! \n");
919 /* constant expression evaluation / constant folding */
920 if (get_opt_constant_folding()) {
921 /* constants can not be evaluated */
922 if (get_irn_op(n) != op_Const) {
923 /* try to evaluate */
924 tv = computed_value (n);
926 /* evaluation was succesful -- replace the node. */
927 obstack_free (current_ir_graph->obst, n);
928 return new_Const (get_tv_mode (tv), tv);
933 /* remove unnecessary nodes */
934 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
935 n = equivalent_node (n);
937 /** common subexpression elimination **/
938 /* Checks whether n is already available. */
939 /* The block input is used to distinguish different subexpressions. Right
940 now all nodes are pinned to blocks, i.e., the cse only finds common
941 subexpressions within a block. */
943 n = identify (current_ir_graph->value_table, n);
944 /* identify found a cse, so deallocate the old node. */
946 obstack_free (current_ir_graph->obst, old_n);
947 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
950 /* Some more constant expression evaluation that does not allow to
952 if (get_opt_constant_folding())
953 n = transform_node (n);
955 /* Remove nodes with dead (Bad) input. */
957 /* Now we can verify the node, as it has no dead inputs any more. */
960 /* Now we have a legal, useful node. Enter it in hash table for cse */
962 n = identify_remember (current_ir_graph->value_table, n);
965 #if 0 /* GL: what's the use of this?? */
966 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
967 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
968 pdeq_putr (current_ir_graph->keep.living, n);
975 /* These optimizations never deallocate nodes. This can cause dead
976 nodes lying on the obstack. Remove these by a dead node elimination,
977 i.e., a copying garbage collection. */
979 optimize_in_place (ir_node *n)
984 if (!get_optimize()) return n;
986 /* if not optimize return n */
988 /* Here this is possible. Why? */
992 /* constant expression evaluation / constant folding */
993 if (get_opt_constant_folding()) {
994 /* constants can not be evaluated */
995 if (get_irn_op(n) != op_Const) {
996 /* try to evaluate */
997 tv = computed_value (n);
999 /* evaluation was succesful -- replace the node. */
1000 n = new_Const (get_tv_mode (tv), tv);
1001 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1003 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1008 /* remove unnecessary nodes */
1009 /*if (get_opt_constant_folding()) */
1010 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1011 n = equivalent_node (n);
1013 /** common subexpression elimination **/
1014 /* Checks whether n is already available. */
1015 /* The block input is used to distinguish different subexpressions. Right
1016 now all nodes are pinned to blocks, i.e., the cse only finds common
1017 subexpressions within a block. */
1019 n = identify (current_ir_graph->value_table, n);
1021 /* identify found a cse, so deallocate the old node. */
1023 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1026 /* Some more constant expression evaluation. */
1027 if (get_opt_constant_folding())
1028 n = transform_node (n);
1030 /* Remove nodes with dead (Bad) input. */
1032 /* Now we can verify the node, as it has no dead inputs any more. */
1035 /* Now we have a legal, useful node. Enter it in hash table for cse.
1036 Blocks should be unique anyways. (Except the successor of start:
1037 is cse with the start block!) */
1038 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1039 n = identify_remember (current_ir_graph->value_table, n);