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.
10 # include "irgraph_t.h"
19 /* Make types visible to allow most efficient access */
20 # include "entity_t.h"
22 /* Trivial inlineable routine for copy propagation.
23 Does follow Ids, needed to optimize inlined code. */
24 static inline ir_node *
25 follow_Id (ir_node *n)
27 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
31 static inline tarval *
34 if ((n != NULL) && (get_irn_op(n) == op_Const))
35 return get_Const_tarval(n);
40 /* if n can be computed, return the value, else NULL. Performs
41 constant folding. GL: Only if n is arithmetic operator? */
43 computed_value (ir_node *n)
47 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
48 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
52 /* get the operands we will work on for simple cases. */
54 a = get_binop_left(n);
55 b = get_binop_right(n);
56 } else if (is_unop(n)) {
60 /* if the operands are constants, get the target value, else set it NULL.
61 (a and b may be NULL if we treat a node that is no computation.) */
65 /* Perform the constant evaluation / computation. */
66 switch (get_irn_opcode(n)) {
68 res = get_Const_tarval(n);
70 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
71 && (get_irn_mode(a) != mode_p)) {
72 res = tarval_add (ta, tb);
76 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
77 && (get_irn_mode(a) != mode_p)) {
78 res = tarval_sub (ta, tb);
80 res = tarval_mode_null [get_irn_modecode (n)];
84 if (ta && mode_is_float(get_irn_mode(a)))
85 res = /*tarval_minus (ta);*/ res;
88 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
89 res = tarval_mul (ta, tb);
91 /* calls computed_value recursive and returns the 0 with proper
92 mode. Why is this an extra case? */
94 if ( (tarval_classify ((v = computed_value (a))) == 0)
95 || (tarval_classify ((v = computed_value (b))) == 0)) {
102 res = /*tarval_abs (ta);*/ res;
103 /* allowed or problems with max/min ?? */
107 res = tarval_and (ta, tb);
110 if ( (tarval_classify ((v = computed_value (a))) == 0)
111 || (tarval_classify ((v = computed_value (b))) == 0)) {
118 res = tarval_or (ta, tb);
121 if ( (tarval_classify ((v = computed_value (a))) == -1)
122 || (tarval_classify ((v = computed_value (b))) == -1)) {
127 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
128 case iro_Not: if (ta) { /*res = tarval_not (ta)*/; } break;
129 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
130 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
131 case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
132 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
133 case iro_Conv: if(ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
139 a = get_Proj_pred(n);
140 /* Optimize Cmp nodes.
141 This performs a first step of unreachable code elimination.
142 Proj can not be computed, but folding a Cmp above the Proj here is
143 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
145 There are several case where we can evaluate a Cmp node:
146 1. The nodes compared are both the same. If we compare for
147 equal, this will return true, else it will return false.
148 This step relies on cse.
149 2. The predecessors of Cmp are target values. We can evaluate
151 3. The predecessors are Allocs or void* constants. Allocs never
152 return NULL, they raise an exception. Therefore we can predict
154 if (get_irn_op(a) == op_Cmp) {
155 aa = get_Cmp_left(a);
156 ab = get_Cmp_right(a);
157 if (aa == ab) { /* 1.: */
158 /* This is a tric with the bits used for encoding the Cmp
159 Proj numbers, the following statement is not the same:
160 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
161 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
163 tarval *taa = computed_value (aa);
164 tarval *tab = computed_value (ab);
165 if (taa && tab) { /* 2.: */
166 /* strange checks... */
167 ir_pncmp flags = tarval_comp (taa, tab);
168 if (flags != irpn_False) {
169 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
171 } else { /* check for 3.: */
172 ir_node *aaa = skip_nop(skip_Proj(aa));
173 ir_node *aba = skip_nop(skip_Proj(ab));
174 if ( ( (/* aa is ProjP and aaa is Alloc */
175 (get_irn_op(aa) == op_Proj)
176 && (get_irn_mode(aa) == mode_p)
177 && (get_irn_op(aaa) == op_Alloc))
178 && ( (/* ab is constant void */
179 (get_irn_op(ab) == op_Const)
180 && (get_irn_mode(ab) == mode_p)
181 && (get_Const_tarval(ab) == tarval_p_void))
182 || (/* ab is other Alloc */
183 (get_irn_op(ab) == op_Proj)
184 && (get_irn_mode(ab) == mode_p)
185 && (get_irn_op(aba) == op_Alloc)
187 || (/* aa is void and aba is Alloc */
188 (get_irn_op(aa) == op_Const)
189 && (get_irn_mode(aa) == mode_p)
190 && (get_Const_tarval(aa) == tarval_p_void)
191 && (get_irn_op(ab) == op_Proj)
192 && (get_irn_mode(ab) == mode_p)
193 && (get_irn_op(aba) == op_Alloc)))
195 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
199 /* printf(" # comp_val: Proj node, not optimized\n"); */
211 /* returns 1 if the a and b are pointers to different locations. */
213 different_identity (ir_node *a, ir_node *b)
215 assert (get_irn_mode (a) == mode_p
216 && get_irn_mode (b) == mode_p);
218 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
219 ir_node *a1 = get_Proj_pred (a);
220 ir_node *b1 = get_Proj_pred (b);
221 if (a1 != b1 && get_irn_op (a1) == op_Alloc
222 && get_irn_op (b1) == op_Alloc)
229 /* equivalent_node returns a node equivalent to N. It skips all nodes that
230 perform no actual computation, as, e.g., the Id nodes. It does not create
231 new nodes. It is therefore safe to free N if the node returned is not N.
232 If a node returns a Tuple we can not just skip it. If the size of the
233 in array fits, we transform n into a tuple (e.g., Div). */
235 equivalent_node (ir_node *n)
238 ir_node *a = NULL; /* to shutup gcc */
239 ir_node *b = NULL; /* to shutup gcc */
240 ir_node *c = NULL; /* to shutup gcc */
242 ins = get_irn_arity (n);
244 /* get the operands we will work on */
246 a = get_binop_left(n);
247 b = get_binop_right(n);
248 } else if (is_unop(n)) {
252 /* skip unnecessary nodes. */
253 switch (get_irn_opcode (n)) {
256 /* The Block constructor does not call optimize, but mature_block
257 calls the optimization. */
258 assert(get_Block_matured(n));
260 /* A single entry Block following a single exit Block can be merged,
261 if it is not the Start block. */
262 /* !!! Beware, all Phi-nodes of n must have been optimized away.
263 This should be true, as the block is matured before optimize is called.
264 But what about Phi-cycles with the Phi0/Id that could not be resolved? */
265 if (get_Block_n_cfgpreds(n) == 1
266 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
267 n = get_nodes_Block(get_Block_cfgpred(n, 0));
269 } else if (n != current_ir_graph->start_block) {
271 /* If all inputs are dead, this block is dead too, except if it is
272 the start block. This is a step of unreachable code elimination */
273 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
274 if (!is_Bad(get_Block_cfgpred(n, i))) break;
276 if (i == get_Block_n_cfgpreds(n))
282 case iro_Jmp: /* GL: Why not same for op_Raise?? */
283 /* unreachable code elimination */
284 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
286 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
287 See cases for iro_Cond and iro_Proj in transform_node. */
288 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
289 case iro_Or: if (a == b) {n = a; break;}
294 /* After running compute_node there is only one constant predecessor.
295 Find this predecessors value and remember the other node: */
296 if ((tv = computed_value (a))) {
298 } else if ((tv = computed_value (b))) {
302 /* If this predecessors constant value is zero, the operation is
303 unnecessary. Remove it: */
304 if (tarval_classify (tv) == 0) {
314 /* these operations are not commutative. Test only one predecessor. */
315 if (tarval_classify (computed_value (b)) == 0) {
317 /* Test if b > #bits of a ==> return 0 / divide b by #bits
318 --> transform node? */
321 case iro_Not: /* NotNot x == x */
322 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
323 out of bounds exception if min =! max? */
324 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
325 n = get_unop_op(get_unop_op(n));
328 /* Mul is commutative and has again an other neutral element. */
329 if (tarval_classify (computed_value (a)) == 1) {
331 } else if (tarval_classify (computed_value (b)) == 1) {
336 /* Div is not commutative. */
337 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
338 /* Turn Div into a tuple (mem, bad, a) */
339 ir_node *mem = get_Div_mem(n);
340 turn_into_tuple(n, 3);
341 set_Tuple_pred(n, 0, mem);
342 set_Tuple_pred(n, 1, new_Bad());
343 set_Tuple_pred(n, 2, a);
346 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
347 teated in transform node.
348 case iro_Mod, Quot, DivMod
352 /* And has it's own neutral element */
353 else if (tarval_classify (computed_value (a)) == -1) {
355 } else if (tarval_classify (computed_value (b)) == -1) {
360 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
362 } else if (get_irn_mode(n) == mode_b) {
363 if (get_irn_op(a) == op_Conv &&
364 get_irn_mode (get_Conv_op(a)) == mode_b) {
365 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
372 /* Several optimizations:
373 - no Phi in start block.
374 - remove Id operators that are inputs to Phi
375 - fold Phi-nodes, iff they have only one predecessor except
381 ir_node *block = NULL; /* to shutup gcc */
382 ir_node *first_val = NULL; /* to shutup gcc */
383 ir_node *scnd_val = NULL; /* to shutup gcc */
385 n_preds = get_Phi_n_preds(n);
387 block = get_nodes_Block(n);
388 assert(get_irn_op (block) == op_Block);
390 /* there should be no Phi nodes in the Start region. */
391 if (block == current_ir_graph->start_block) {
396 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
397 /* GL: why not return new_Bad? */
402 /* first we test for a special case: */
403 /* Confirm is a special node fixing additional information for a
404 value that is known at a certain point. This is useful for
405 dataflow analysis. */
407 ir_node *a = follow_Id (get_Phi_pred(n, 0));
408 ir_node *b = follow_Id (get_Phi_pred(n, 1));
409 if ( (get_irn_op(a) == op_Confirm)
410 && (get_irn_op(b) == op_Confirm)
411 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
412 && (get_irn_n(a, 1) == get_irn_n (b, 1))
413 && (a->data.num == (~b->data.num & irpn_True) )) {
414 n = follow_Id (get_irn_n(a, 0));
420 /* Find first non-self-referencing input */
421 for (i = 0; i < n_preds; ++i) {
422 first_val = follow_Id(get_Phi_pred(n, i));
424 set_Phi_pred(n, i, first_val);
425 if ( (first_val != n) /* not self pointer */
426 && (get_irn_op(first_val) != op_Bad) /* value not dead */
427 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
428 break; /* then found first value. */
432 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
433 if (i >= n_preds) { n = new_Bad(); break; }
437 /* follow_Id () for rest of inputs, determine if any of these
438 are non-self-referencing */
439 while (++i < n_preds) {
440 scnd_val = follow_Id(get_Phi_pred(n, i));
442 set_Phi_pred(n, i, scnd_val);
444 && (scnd_val != first_val)
445 && (get_irn_op(scnd_val) != op_Bad)
446 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
451 /* Fold, if no multiple distinct non-self-referencing inputs */
455 /* skip the remaining Ids. */
456 while (++i < n_preds) {
457 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
465 a = skip_Proj(get_Load_mem(n));
466 b = skip_Proj(get_Load_ptr(n));
468 if (get_irn_op(a) == op_Store) {
469 if ( different_identity (b, get_Store_ptr(a))) {
470 /* load and store use different pointers, therefore load
471 needs not take store's memory but the state before. */
472 set_Load_mem (n, get_Store_mem(a));
473 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
479 /* remove unnecessary store. */
481 a = skip_Proj(get_Store_mem(n));
482 b = get_Store_ptr(n);
483 c = skip_Proj(get_Store_value(n));
485 if (get_irn_op(a) == op_Store
486 && get_Store_ptr(a) == b
487 && skip_Proj(get_Store_value(a)) == c) {
488 /* We have twice exactly the same store -- a write after write. */
490 } else if (get_irn_op(c) == op_Load
491 && (a == c || skip_Proj(get_Load_mem(c)) == a)
492 && get_Load_ptr(c) == b )
493 /* !!!??? and a cryptic test */ {
494 /* We just loaded the value from the same memory, i.e., the store
495 doesn't change the memory -- a write after read. */
496 turn_into_tuple(n, 2);
497 set_Tuple_pred(n, 0, a);
498 set_Tuple_pred(n, 1, new_Bad());
505 a = get_Proj_pred(n);
507 if ( get_irn_op(a) == op_Tuple) {
508 /* Remove the Tuple/Proj combination. */
509 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
510 n = get_Tuple_pred(a, get_Proj_proj(n));
512 assert(0); /* This should not happen! (GL added this assert) */
515 } else if (get_irn_mode(n) == mode_X &&
516 is_Bad(get_nodes_Block(n))) {
517 /* Remove dead control flow. */
531 } /* end equivalent_node() */
534 /* tries several [inplace] [optimizing] transformations and returns a
535 equivalent node. The difference to equivalent_node is that these
536 transformations _do_ generate new nodes, and thus the old node must
537 not be freed even if the equivalent node isn't the old one. */
539 transform_node (ir_node *n)
542 ir_node *a = NULL, *b;
545 switch (get_irn_opcode(n)) {
551 a = get_DivMod_left(n);
552 b = get_DivMod_right(n);
553 mode = get_irn_mode(a);
555 if (!( mode_is_int(get_irn_mode(a))
556 && mode_is_int(get_irn_mode(b))))
560 a = new_Const (mode, tarval_from_long (mode, 1));
561 b = new_Const (mode, tarval_from_long (mode, 0));
568 if (tarval_classify(tb) == 1) {
569 b = new_Const (mode, tarval_from_long (mode, 0));
573 resa = tarval_div (ta, tb);
574 if (!resa) break; /* Causes exception!!! Model by replacing through
575 Jmp for X result!? */
576 resb = tarval_mod (ta, tb);
577 if (!resb) break; /* Causes exception! */
578 a = new_Const (mode, resa);
579 b = new_Const (mode, resb);
582 } else if (tarval_classify (ta) == 0) {
587 if (evaluated) { /* replace by tuple */
588 ir_node *mem = get_DivMod_mem(n);
589 turn_into_tuple(n, 4);
590 set_Tuple_pred(n, 0, mem);
591 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
592 set_Tuple_pred(n, 2, a);
593 set_Tuple_pred(n, 3, b);
594 assert(get_nodes_Block(n));
600 /* Replace the Cond by a Jmp if it branches on a constant
603 a = get_Cond_selector(n);
606 if (ta && (get_irn_mode(a) == mode_b)) {
607 /* It's a boolean Cond, branching on a boolean constant.
608 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
609 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
610 turn_into_tuple(n, 2);
611 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
612 set_Tuple_pred(n, 0, new_Bad());
613 set_Tuple_pred(n, 1, jmp);
615 set_Tuple_pred(n, 0, jmp);
616 set_Tuple_pred(n, 1, new_Bad());
618 } else if (ta && (get_irn_mode(a) == mode_I)) {
619 /* I don't want to allow Tuples smaller than the biggest Proj.
620 Also this tuple might get really big...
621 I generate the Jmp here, and remember it in link. Link is used
622 when optimizing Proj. */
623 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
624 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
625 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
626 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
627 /* The Eor is a negate. Generate a new Cond without the negate,
628 simulate the negate by exchanging the results. */
629 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
631 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
632 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
633 /* A Not before the Cond. Generate a new Cond without the Not,
634 simulate the Not by exchanging the results. */
635 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
642 a = get_Proj_pred(n);
644 if ( (get_irn_op(a) == op_Cond)
646 && get_irn_op(get_irn_link(a)) == op_Cond) {
647 /* Use the better Cond if the Proj projs from a Cond which get's
648 its result from an Eor/Not. */
649 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
650 || (get_irn_op(get_Cond_selector(a)) == op_Not))
651 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
652 && (get_irn_op(get_irn_link(a)) == op_Cond)
653 && (get_Cond_selector(get_irn_link(a)) ==
654 get_Eor_left(get_Cond_selector(a))));
655 set_Proj_pred(n, get_irn_link(a));
656 if (get_Proj_proj(n) == 0)
660 } else if ( (get_irn_op(a) == op_Cond)
661 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
663 /* The Cond is a Switch on a Constant */
664 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
665 /* The always taken branch, reuse the existing Jmp. */
666 if (!get_irn_link(a)) /* well, if it exists ;-> */
667 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
668 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
671 /* a never taken branch */
677 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
679 b = get_Eor_right(n);
681 if ( (get_irn_mode(n) == mode_b)
682 && (get_irn_op(a) == op_Proj)
683 && (get_irn_mode(a) == mode_b)
684 && (tarval_classify (computed_value (b)) == 1)
685 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
686 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
687 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
688 mode_b, get_negated_pnc(get_Proj_proj(a)));
689 else if ( (get_irn_mode(n) == mode_b)
690 && (tarval_classify (computed_value (b)) == 1))
691 /* The Eor is a Not. Replace it by a Not. */
692 /* ????!!!Extend to bitfield 1111111. */
693 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
699 if ( (get_irn_mode(n) == mode_b)
700 && (get_irn_op(a) == op_Proj)
701 && (get_irn_mode(a) == mode_b)
702 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
703 /* We negate a Cmp. The Cmp has the negated result anyways! */
704 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
705 mode_b, get_negated_pnc(get_Proj_proj(a)));
713 /***************** Common Subexpression Elimination *****************/
715 /* Compare function for two nodes in the hash table. Gets two */
716 /* nodes as parameters. */
717 /* @@@ a+b != b+a ? */
719 vt_cmp (const void *elt, const void *key)
727 if (a == b) return 0;
729 if ((get_irn_op(a) != get_irn_op(b)) ||
730 (get_irn_mode(a) != get_irn_mode(b))) return 1;
732 /* compare if a's in and b's in are equal */
733 /* GL: we optimize only nodes with in arrays of fixed sizes.
734 if (get_irn_arity (a) != -2) {
735 ins = get_irn_arity (a);
736 if (ins != get_irn_arity (b)) return 1;
737 ain = get_irn_in (a);
738 bin = get_irn_in (b);
741 if (get_irn_arity (a) != get_irn_arity(b))
744 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
745 /* do if (*ain++ != *bin++) return 1; while (ins--); */
746 for (i = -1; i < get_irn_arity(a); i++)
747 if (get_irn_n(a, i) != get_irn_n(b, i))
751 switch (get_irn_opcode(a)) {
753 return get_irn_const_attr (a) != get_irn_const_attr (b);
755 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
757 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
758 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
760 return (get_irn_free_attr(a) != get_irn_free_attr(b));
762 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
763 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
765 return (get_irn_call_attr(a)->kind != get_irn_call_attr(b)->kind)
766 || (get_irn_call_attr(a)->arity != get_irn_call_attr(b)->arity);
768 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
769 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
770 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
771 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
772 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
773 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
775 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
783 ir_node_hash (ir_node *node)
788 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
789 h = get_irn_arity(node);
791 /* consider all in nodes... except the block. */
792 for (i = 0; i < get_irn_arity(node); i++) {
793 h = 9*h + (unsigned long)get_irn_n(node, i);
797 h = 9*h + (unsigned long) get_irn_mode (node);
799 h = 9*h + (unsigned long) get_irn_op (node);
805 new_identities (void)
807 return new_pset (vt_cmp, TUNE_NIR_NODES);
811 del_identities (pset *value_table)
813 del_pset (value_table);
816 /* Return the canonical node computing the same value as n.
817 Looks up the node in a hash table. */
818 static inline ir_node *
819 identify (pset *value_table, ir_node *n)
823 if (!value_table) return n;
825 switch (get_irn_opcode (n)) {
832 /* for commutative operators perform a OP b == b OP a */
833 if (get_binop_left(n) > get_binop_right(n)) {
834 ir_node *h = get_binop_left(n);
835 set_binop_left(n, get_binop_right(n));
836 set_binop_right(n, h);
842 o = pset_find (value_table, n, ir_node_hash (n));
848 /* Return the canonical node computing the same value as n.
849 Looks up the node in a hash table, enters it in the table
850 if it isn't there yet. */
852 identify_remember (pset *value_table, ir_node *node)
856 if (!value_table) return node;
858 /* lookup or insert in hash table with given hash key. */
859 o = pset_insert (value_table, node, ir_node_hash (node));
861 if (o == node) return node;
866 /* garbage in, garbage out. If a node has a dead input, i.e., the
867 Bad node is input to the node, return the Bad node. */
868 static inline ir_node *
872 ir_op* op = get_irn_op(node);
874 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
875 blocks predecessors is dead. */
876 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
877 for (i = -1; i < get_irn_arity(node); i++) {
878 if (is_Bad(get_irn_n(node, i))) {
884 /* If Block has only Bads as predecessors it's garbage. */
885 /* If Phi has only Bads as predecessors it's garbage. */
886 if (op == op_Block || op == op_Phi) {
887 for (i = 0; i < get_irn_arity(node); i++) {
888 if (!is_Bad(get_irn_n(node, i))) break;
890 if (i = get_irn_arity(node)) node = new_Bad();
897 /* These optimizations deallocate nodes from the obstack.
898 It can only be called if it is guaranteed that no other nodes
899 reference this one, i.e., right after construction of a node. */
901 optimize (ir_node *n)
906 /* Allways optimize Phi nodes: part of the construction. */
907 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
909 /* if not optimize return n */
911 printf(" attention: empty node!!! \n");
915 /* constant expression evaluation / constant folding */
916 if (get_opt_constant_folding()) {
917 /* constants can not be evaluated */
918 if (get_irn_op(n) != op_Const) {
919 /* try to evaluate */
920 tv = computed_value (n);
922 /* evaluation was succesful -- replace the node. */
923 obstack_free (current_ir_graph->obst, n);
924 return new_Const (get_tv_mode (tv), tv);
929 /* remove unnecessary nodes */
930 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
931 n = equivalent_node (n);
933 /** common subexpression elimination **/
934 /* Checks whether n is already available. */
935 /* The block input is used to distinguish different subexpressions. Right
936 now all nodes are pinned to blocks, i.e., the cse only finds common
937 subexpressions within a block. */
939 n = identify (current_ir_graph->value_table, n);
940 /* identify found a cse, so deallocate the old node. */
942 obstack_free (current_ir_graph->obst, old_n);
943 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
946 /* Some more constant expression evaluation that does not allow to
948 if (get_opt_constant_folding())
949 n = transform_node (n);
951 /* Remove nodes with dead (Bad) input. */
953 /* Now we can verify the node, as it has no dead inputs any more. */
956 /* Now we have a legal, useful node. Enter it in hash table for cse */
958 n = identify_remember (current_ir_graph->value_table, n);
961 #if 0 /* GL: what's the use of this?? */
962 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
963 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
964 pdeq_putr (current_ir_graph->keep.living, n);
971 /* These optimizations never deallocate nodes. This can cause dead
972 nodes lying on the obstack. Remove these by a dead node elimination,
973 i.e., a copying garbage collection. */
975 optimize_in_place (ir_node *n)
980 if (!get_optimize()) return n;
982 /* if not optimize return n */
984 /* Here this is possible. Why? */
988 /* constant expression evaluation / constant folding */
989 if (get_opt_constant_folding()) {
990 /* constants can not be evaluated */
991 if (get_irn_op(n) != op_Const) {
992 /* try to evaluate */
993 tv = computed_value (n);
995 /* evaluation was succesful -- replace the node. */
996 n = new_Const (get_tv_mode (tv), tv);
997 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
999 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1004 /* remove unnecessary nodes */
1005 //if (get_opt_constant_folding())
1006 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1007 n = equivalent_node (n);
1009 /** common subexpression elimination **/
1010 /* Checks whether n is already available. */
1011 /* The block input is used to distinguish different subexpressions. Right
1012 now all nodes are pinned to blocks, i.e., the cse only finds common
1013 subexpressions within a block. */
1015 n = identify (current_ir_graph->value_table, n);
1017 /* identify found a cse, so deallocate the old node. */
1019 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1022 /* Some more constant expression evaluation. */
1023 if (get_opt_constant_folding())
1024 n = transform_node (n);
1026 /* Remove nodes with dead (Bad) input. */
1028 /* Now we can verify the node, as it has no dead inputs any more. */
1031 /* Now we have a legal, useful node. Enter it in hash table for cse.
1032 Blocks should be unique anyways. (Except the successor of start:
1033 is cse with the start block!) */
1034 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1035 n = identify_remember (current_ir_graph->value_table, n);