1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Christian Schaefer, Goetz Lindenmaier
6 ** iropt --- optimizations intertwined with IR construction.
15 /* Make types visible to allow most efficient access */
16 # include "entity_t.h"
18 /* Trivial inlineable routine for copy propagation.
19 Does follow Ids, needed to optimize inlined code. */
20 static inline ir_node *
21 follow_Id (ir_node *n)
23 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
28 static inline tarval *
31 if ((n != NULL) && (get_irn_op(n) == op_Const))
32 return get_Const_tarval(n);
38 /* if n can be computed, return the value, else NULL. Performs
39 constant Folding. GL: Only if n is arithmetic operator? */
41 computed_value (ir_node *n)
45 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
46 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
50 /* get the operands we will work on for simple cases. */
52 a = get_binop_left(n);
53 b = get_binop_right(n);
54 } else if (is_unop(n)) {
58 /* if the operands are constants, get the target value, else set it NULL.
59 (a and b may be NULL if we treat a node that is no computation.) */
63 /* Perform the constant evaluation / computation. */
64 switch (get_irn_opcode(n)) {
66 res = get_Const_tarval(n);
68 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
69 && (get_irn_mode(a) != mode_p)) {
70 res = tarval_add (ta, tb);
74 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
75 && (get_irn_mode(a) != mode_p)) {
76 res = tarval_sub (ta, tb);
78 res = tarval_mode_null [get_irn_modecode (n)];
82 if (ta && mode_is_float(get_irn_mode(a)))
83 res = /*tarval_minus (ta);*/ res;
86 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
87 res = tarval_mul (ta, tb);
89 /* calls computed_value recursive and returns the 0 with proper
90 mode. Why is this an extra case? */
92 if ( (tarval_classify ((v = computed_value (a))) == 0)
93 || (tarval_classify ((v = computed_value (b))) == 0)) {
100 res = /*tarval_abs (ta);*/ res;
101 /* allowded or problems with max/min ?? */
105 res = tarval_and (ta, tb);
108 if ( (tarval_classify ((v = computed_value (a))) == 0)
109 || (tarval_classify ((v = computed_value (b))) == 0)) {
116 res = tarval_or (ta, tb);
119 if ( (tarval_classify ((v = computed_value (a))) == -1)
120 || (tarval_classify ((v = computed_value (b))) == -1)) {
125 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
126 case iro_Not: if(ta) { /*res = tarval_not (ta)*/; } break;
127 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
128 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
129 case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
130 case iro_Rot: if(ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
131 case iro_Conv: if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
137 a = get_Proj_pred(n);
138 /* Optimize Cmp nodes.
139 This performs a first step of unreachable code elimination.
140 Proj can not be computed, but folding a Cmp above the Proj here is
141 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
143 There are several case where we can evaluate a Cmp node:
144 1. The nodes compared are both the same. If we compare for
145 equal, this will return true, else it will return false.
146 This step relies on cse.
147 2. The predecessors of Cmp are target values. We can evaluate
149 3. The predecessors are Allocs or void* constants. Allocs never
150 return NULL, they raise an exception. Therefore we can predict
152 if (get_irn_op(a) == op_Cmp) {
153 aa = get_Cmp_left(a);
154 ab = get_Cmp_right(a);
155 if (aa == ab) { /* 1.: */
156 /* This is a tric with the bits used for encoding the Cmp
157 Proj numbers, the following statement is not the same:
158 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
159 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
161 tarval *taa = computed_value (aa);
162 tarval *tab = computed_value (ab);
163 if (taa && tab) { /* 2.: */
164 /* strange checks... */
165 ir_pncmp flags = tarval_comp (taa, tab);
166 if (flags != irpn_False) {
167 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
169 } else { /* check for 3.: */
170 ir_node *aaa = skip_nop(skip_Proj(aa));
171 ir_node *aba = skip_nop(skip_Proj(ab));
172 if ( ( (/* aa is ProjP and aaa is Alloc */
173 (get_irn_op(aa) == op_Proj)
174 && (get_irn_mode(aa) == mode_p)
175 && (get_irn_op(aaa) == op_Alloc))
176 && ( (/* ab is constant void */
177 (get_irn_op(ab) == op_Const)
178 && (get_irn_mode(ab) == mode_p)
179 && (get_Const_tarval(ab) == tarval_p_void))
180 || (/* ab is other Alloc */
181 (get_irn_op(ab) == op_Proj)
182 && (get_irn_mode(ab) == mode_p)
183 && (get_irn_op(aba) == op_Alloc)
185 || (/* aa is void and aba is Alloc */
186 (get_irn_op(aa) == op_Const)
187 && (get_irn_mode(aa) == mode_p)
188 && (get_Const_tarval(aa) == tarval_p_void)
189 && (get_irn_op(ab) == op_Proj)
190 && (get_irn_mode(ab) == mode_p)
191 && (get_irn_op(aba) == op_Alloc)))
193 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
197 /* printf(" # comp_val: Proj node, not optimized\n"); */
209 /* returns 1 if the a and b are pointers to different locations. */
211 different_identity (ir_node *a, ir_node *b)
213 assert (get_irn_mode (a) == mode_p
214 && get_irn_mode (b) == mode_p);
216 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
217 ir_node *a1 = get_Proj_pred (a);
218 ir_node *b1 = get_Proj_pred (b);
219 if (a1 != b1 && get_irn_op (a1) == op_Alloc
220 && get_irn_op (b1) == op_Alloc)
227 /* equivalent_node returns a node equivalent to N. It skips all nodes that
228 perform no actual computation, as, e.g., the Id nodes. It does not create
229 new nodes. It is therefore safe to free N if the node returned is not N.
230 If a node returns a Tuple we can not just skip it. If the size of the
231 in array fits, we transform n into a tuple (e.g., Div). */
233 equivalent_node (ir_node *n)
236 ir_node *a = NULL; /* to shutup gcc */
237 ir_node *b = NULL; /* to shutup gcc */
238 ir_node *c = NULL; /* to shutup gcc */
240 ins = get_irn_arity (n);
242 /* get the operands we will work on */
244 a = get_binop_left(n);
245 b = get_binop_right(n);
246 } else if (is_unop(n)) {
251 /* skip unnecessary nodes. */
252 switch (get_irn_opcode (n)) {
255 /* The Block constructor does not call optimize, therefore
256 dead blocks are not removed without an extra optimizing
257 pass through the graph. */
258 assert(get_Block_matured(n));
260 /* a single entry Region following a single exit Region can be merged */
261 /* !!! Beware, all Phi-nodes of n must have been optimized away.
262 This is true, as the block is matured before optimize is called. */
263 if (get_Block_n_cfgpreds(n) == 1
264 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
265 n = get_nodes_Block(get_Block_cfgpred(n, 0));
266 } else if (n != current_ir_graph->start_block) {
269 /* If all inputs are dead, this block is dead too, except if it is
270 the start block. This is a step of unreachable code elimination */
272 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
273 if (!is_Bad(get_Block_cfgpred(n, i))) break;
275 if (i == get_Block_n_cfgpreds(n))
281 case iro_Jmp: /* GL: ??? Why not same for op_Raise?? */
282 /* unreachable code elimination */
283 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
285 /* GL: Why isn't there a case that checks whether input ot Cond is
286 constant true or false? For unreachable code elimination
287 is this done in Proj? It's not here as it generates a new node,
288 a Jmp. It is 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
383 ir_node *block = NULL; /* to shutup gcc */
384 ir_node *first_val = NULL; /* to shutup gcc */
385 ir_node *scnd_val = NULL; /* to shutup gcc */
387 n_preds = get_Phi_n_preds(n);
389 block = get_nodes_Block(n);
390 assert(get_irn_op (block) == op_Block);
392 /* there should be no Phi nodes in the Start region. */
393 if (block == current_ir_graph->start_block) {
398 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
399 /* GL: why not return new_Bad? */
404 /* first we test for a special case: */
405 /* Confirm is a special node fixing additional information for a
406 value that is known at a certain point. This is useful for
407 dataflow analysis. */
409 ir_node *a = follow_Id (get_Phi_pred(n, 0));
410 ir_node *b = follow_Id (get_Phi_pred(n, 1));
411 if ( (get_irn_op(a) == op_Confirm)
412 && (get_irn_op(b) == op_Confirm)
413 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
414 && (get_irn_n(a, 1) == get_irn_n (b, 1))
415 && (a->data.num == (~b->data.num & irpn_True) )) {
416 n = follow_Id (get_irn_n(a, 0));
422 /* Find first non-self-referencing input */
423 for (i = 0; i < n_preds; ++i) {
424 first_val = follow_Id(get_Phi_pred(n, i));
426 set_Phi_pred(n, i, first_val);
427 if ( (first_val != n) /* not self pointer */
428 && (get_irn_op(first_val) != op_Bad) /* value not dead */
429 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
430 break; /* then found first value. */
434 /* A totally Bad or self-referencing Phi */
435 if (i > n_preds) { n = new_Bad(); break; }
439 /* follow_Id () for rest of inputs, determine if any of these
440 are non-self-referencing */
441 while (++i < n_preds) {
442 scnd_val = follow_Id(get_Phi_pred(n, i));
444 set_Phi_pred(n, i, scnd_val);
446 && (scnd_val != first_val)
447 && (get_irn_op(scnd_val) != op_Bad)
448 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
453 /* Fold, if no multiple distinct non-self-referencing inputs */
457 /* skip the remaining Ids. */
458 while (++i < n_preds)
459 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
466 a = skip_Proj(get_Load_mem(n));
467 b = skip_Proj(get_Load_ptr(n));
469 if (get_irn_op(a) == op_Store) {
470 if ( different_identity (b, get_Store_ptr(a))) {
471 /* load and store use different pointers, therefore load
472 needs not take store's memory but the state before. */
473 set_Load_mem (n, get_Store_mem(a));
474 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
480 /* remove unnecessary store. */
482 a = skip_Proj(get_Store_mem(n));
483 b = get_Store_ptr(n);
484 c = skip_Proj(get_Store_value(n));
486 if (get_irn_op(a) == op_Store
487 && get_Store_ptr(a) == b
488 && skip_Proj(get_Store_value(a)) == c) {
489 /* We have twice exactly the same store -- a write after write. */
491 } else if (get_irn_op(c) == op_Load
492 && (a == c || skip_Proj(get_Load_mem(c)) == a)
493 && get_Load_ptr(c) == b )
494 /* !!!??? and a cryptic test */ {
495 /* We just loaded the value from the same memory, i.e., the store
496 doesn't change the memory -- a write after read. */
497 turn_into_tuple(n, 2);
498 set_Tuple_pred(n, 0, a);
499 set_Tuple_pred(n, 1, new_Bad());
506 a = get_Proj_pred(n);
508 if ( get_irn_op(a) == op_Tuple) {
509 /* Remove the Tuple/Proj combination. */
510 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
511 n = get_Tuple_pred(a, get_Proj_proj(n));
513 assert(0); /* This should not happen?! (GL added this assert) */
516 } else if (get_irn_mode(n) == mode_X &&
517 is_Bad(get_nodes_Block(n))) {
518 /* Remove dead control flow. */
532 } /* end equivalent_node() */
535 /* tries several [inplace] [optimizing] transformations and returns a
536 equivalent node. The difference to equivalent_node is that these
537 transformations _do_ generate new nodes, and thus the old node must
538 not be freed even if the equivalent node isn't the old one. */
540 transform_node (ir_node *n)
543 ir_node *a = NULL, *b;
546 switch (get_irn_opcode(n)) {
552 a = get_DivMod_left(n);
553 b = get_DivMod_right(n);
554 mode = get_irn_mode(a);
556 if (!( mode_is_int(get_irn_mode(a))
557 && mode_is_int(get_irn_mode(b))))
561 a = new_Const (mode, tarval_from_long (mode, 1));
562 b = new_Const (mode, tarval_from_long (mode, 0));
569 if (tarval_classify(tb) == 1) {
570 b = new_Const (mode, tarval_from_long (mode, 0));
574 resa = tarval_div (ta, tb);
575 if (!resa) break; /* Causes exception!!! Model by replacing through
576 Jmp for X result!? */
577 resb = tarval_mod (ta, tb);
578 if (!resb) break; /* Causes exception! */
579 a = new_Const (mode, resa);
580 b = new_Const (mode, resb);
583 } else if (tarval_classify (ta) == 0) {
588 if (evaluated) { /* replace by tuple */
589 ir_node *mem = get_DivMod_mem(n);
590 turn_into_tuple(n, 4);
591 set_Tuple_pred(n, 0, mem);
592 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
593 set_Tuple_pred(n, 2, a);
594 set_Tuple_pred(n, 3, b);
595 assert(get_nodes_Block(n));
601 /* Replace the Cond by a Jmp if it branches on a constant
605 a = get_Cond_selector(n);
608 if (ta && (get_irn_mode(a) == mode_b)) {
609 /* It's a boolean Cond, branching on a boolean constant.
610 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
611 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
612 turn_into_tuple(n, 2);
613 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
614 set_Tuple_pred(n, 0, new_Bad());
615 set_Tuple_pred(n, 1, jmp);
617 set_Tuple_pred(n, 0, jmp);
618 set_Tuple_pred(n, 1, new_Bad());
620 } else if (ta && (get_irn_mode(a) == mode_I)) {
621 /* I don't want to allow Tuples smaller than the biggest Proj.
622 Also this tuple might get really big...
623 I generate the Jmp here, and remember it in link. Link is used
624 when optimizing Proj. */
625 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
626 } else if ( ((get_irn_op(get_Cond_selector(n)) == op_Eor)
627 /* || (get_irn_op(get_Cond_selector(a)) == op_Not)*/)
628 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
629 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
630 /* The Eor is a negate. Generate a new Cond without the negate,
631 simulate the negate by exchanging the results. */
632 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
639 a = get_Proj_pred(n);
641 if ( (get_irn_op(a) == op_Cond)
643 && get_irn_op(get_irn_link(a)) == op_Cond) {
644 /* Use the better Cond if the Proj projs from a Cond which get's
645 its result from an Eor/Not. */
646 assert ( ((get_irn_op(get_Cond_selector(a)) == op_Eor)
647 /* || (get_irn_op(get_Cond_selector(a)) == op_Not)*/)
648 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
649 && (get_irn_op(get_irn_link(a)) == op_Cond)
650 && (get_Cond_selector(get_irn_link(a)) ==
651 get_Eor_left(get_Cond_selector(a))));
652 set_Proj_pred(n, get_irn_link(a));
653 if (get_Proj_proj(n) == 0)
657 } else if ( (get_irn_op(a) == op_Cond)
658 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
660 /* The Cond is a Switch on a Constant */
661 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
662 /* The always taken branch, reuse the existing Jmp. */
663 if (!get_irn_link(a)) /* well, if it exists ;-> */
664 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
665 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
668 /* a never taken branch */
674 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
676 b = get_Eor_right(n);
678 if ( (get_irn_mode(n) == mode_b)
679 && (get_irn_op(a) == op_Proj)
680 && (get_irn_mode(a) == mode_b)
681 && (tarval_classify (computed_value (b)) == 1)
682 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
683 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
684 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
685 mode_b, get_negated_pnc(get_Proj_proj(a)));
686 else if ( (get_irn_mode(n) == mode_b)
687 && (tarval_classify (computed_value (b)) == 1))
688 /* The Eor is a Not. Replace it by a Not. */
689 /* ????!!!Extend to bitfield 1111111. */
690 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
693 case iro_Not: { /* @@@ not tested as boolean Eor not allowed any more. */
696 if ( (get_irn_mode(n) == mode_b)
697 && (get_irn_op(a) == op_Proj)
698 && (get_irn_mode(a) == mode_b)
699 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
700 /* We negate a Cmp. The Cmp has the negated result anyways! */
701 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
702 mode_b, get_negated_pnc(get_Proj_proj(a)));
710 /***************** Common Subexpression Elimination *****************/
712 /* Compare function for two nodes in the hash table. Gets two */
713 /* nodes as parameters. */
714 /* @@@ a+b != b+a ? */
716 vt_cmp (const void *elt, const void *key)
724 if (a == b) return 0;
726 if ((get_irn_op(a) != get_irn_op(b)) ||
727 (get_irn_mode(a) != get_irn_mode(b))) return 1;
729 /* compare if a's in and b's in are equal */
730 /* GL: we optimize only nodes with in arrays of fixed sizes.
731 if (get_irn_arity (a) != -2) {
732 ins = get_irn_arity (a);
733 if (ins != get_irn_arity (b)) return 1;
734 ain = get_irn_in (a);
735 bin = get_irn_in (b);
738 if (get_irn_arity (a) != get_irn_arity(b))
741 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
742 /* do if (*ain++ != *bin++) return 1; while (ins--); */
743 for (i = -1; i < get_irn_arity(a); i++)
744 if (get_irn_n(a, i) != get_irn_n(b, i))
748 switch (get_irn_opcode(a)) {
750 return get_irn_const_attr (a) != get_irn_const_attr (b);
752 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
754 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
755 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
757 return (get_irn_free_attr(a) != get_irn_free_attr(b));
759 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
760 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
762 return (get_irn_call_attr(a)->kind != get_irn_call_attr(b)->kind)
763 || (get_irn_call_attr(a)->arity != get_irn_call_attr(b)->arity);
765 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
766 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
767 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
768 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
769 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
770 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
772 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
780 ir_node_hash (ir_node *node)
785 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
786 h = get_irn_arity(node);
788 /* consider all in nodes... except the block. */
789 for (i = 0; i < get_irn_arity(node); i++) {
790 h = 9*h + (unsigned long)get_irn_n(node, i);
794 h = 9*h + (unsigned long) get_irn_mode (node);
796 h = 9*h + (unsigned long) get_irn_op (node);
802 new_identities (void)
804 return new_pset (vt_cmp, TUNE_NIR_NODES);
808 del_identities (pset *value_table)
810 del_pset (value_table);
813 /* Return the canonical node computing the same value as n.
814 Looks up the node in a hash table. */
815 static inline ir_node *
816 identify (pset *value_table, ir_node *n)
820 if (!value_table) return n;
822 switch (get_irn_opcode (n)) {
829 /* for commutative operators perform a OP b == b OP a */
830 if (get_binop_left(n) > get_binop_right(n)) {
831 ir_node *h = get_binop_left(n);
832 set_binop_left(n, get_binop_right(n));
833 set_binop_right(n, h);
839 o = pset_find (value_table, n, ir_node_hash (n));
845 /* Return the canonical node computing the same value as n.
846 Looks up the node in a hash table, enters it in the table
847 if it isn't there yet. */
849 identify_remember (pset *value_table, ir_node *node)
853 if (!value_table) return node;
855 /* lookup or insert in hash table with given hash key. */
856 o = pset_insert (value_table, node, ir_node_hash (node));
858 if (o == node) return node;
863 /* garbage in, garbage out. If a node has a dead input, i.e., the
864 Bad node is input to the node, return the Bad node. */
865 static inline ir_node *
869 ir_op* op = get_irn_op(node);
871 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
872 blocks predecessors is dead. */
873 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
874 for (i = -1; i < get_irn_arity(node); i++) {
875 if (is_Bad(get_irn_n(node, i))) {
885 /* These optimizations deallocate nodes from the obstack.
886 It can only be called if it is guaranteed that no other nodes
887 reference this one, i.e., right after construction of a node. */
889 optimize (ir_node *n)
894 if (!get_optimize()) return NULL;
896 /* if not optimize return n */
898 printf(" attention: empty node!!! \n");
902 /* constant expression evaluation / constant folding */
903 if (get_opt_constant_folding()) {
904 /* constants can not be evaluated */
905 if (get_irn_op(n) != op_Const) {
906 /* try to evaluate */
907 tv = computed_value (n);
909 /* evaluation was succesful -- replace the node. */
910 obstack_free (current_ir_graph->obst, n);
911 return new_Const (get_tv_mode (tv), tv);
912 /* xprintf("* optimize: computed node %I\n", n->op->name); */
916 /* remove unnecessary nodes */
917 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
918 n = equivalent_node (n);
920 /** common subexpression elimination **/
921 /* Checks whether n is already available. */
922 /* The block input is used to distinguish different subexpressions. Right
923 now all nodes are pinned to blocks, i.e., the cse only finds common
924 subexpressions within a block. */
927 n = identify (current_ir_graph->value_table, n);
929 /* identify found a cse, so deallocate the old node. */
931 obstack_free (current_ir_graph->obst, old_n);
932 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
935 /* Some more constant expression evaluation that does not allow to
937 if (get_opt_constant_folding())
938 n = transform_node (n);
940 /* Remove nodes with dead (Bad) input. */
942 /* Now we can verify the node, as it has no dead inputs any more. */
945 /* Now we have a legal, useful node. Enter it in hash table for cse */
947 /* aborts ??! set/pset can not handle several hash tables??!
948 No, suddenly it works. */
949 n = identify_remember (current_ir_graph->value_table, n);
952 #if 0 /* GL: what's the use of this?? */
953 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
954 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
955 pdeq_putr (current_ir_graph->keep.living, n);
962 /* These optimizations never deallocate nodes. This can cause dead
963 nodes lying on the obstack. Remove these by a dead node elimination,
964 i.e., a copying garbage collection. */
966 optimize_in_place (ir_node *n)
972 /* if not optimize return n */
974 /* Here this is possible. Why? */
978 /* constant expression evaluation / constant folding */
979 if (get_opt_constant_folding()) {
980 /* constants can not be evaluated */
981 if (get_irn_op(n) != op_Const) {
982 /* try to evaluate */
983 tv = computed_value (n);
985 /* evaluation was succesful -- replace the node. */
986 return new_Const (get_tv_mode (tv), tv);
987 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
991 /* remove unnecessary nodes */
992 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
993 n = equivalent_node (n);
995 /** common subexpression elimination **/
996 /* Checks whether n is already available. */
997 /* The block input is used to distinguish different subexpressions. Right
998 now all nodes are pinned to blocks, i.e., the cse only finds common
999 subexpressions within a block. */
1002 n = identify (current_ir_graph->value_table, n);
1004 /* identify found a cse, so deallocate the old node. */
1006 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1010 /* Some more constant expression evaluation. */
1011 if (get_opt_constant_folding())
1012 n = transform_node (n);
1015 /* Remove nodes with dead (Bad) input. */
1017 /* Now we can verify the node, as it has no dead inputs any more. */
1020 /* Now we have a legal, useful node. Enter it in hash table for cse */
1021 if (get_opt_cse()) {
1022 /* aborts ??! set/pset can not handle several hash tables??!
1023 No, suddenly it works. */
1024 n = identify_remember (current_ir_graph->value_table, n);