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) &&
274 (n != current_ir_graph->end_block) ) {
276 /* If all inputs are dead, this block is dead too, except if it is
277 the start or end block. This is a step of unreachable code
279 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
280 if (!is_Bad(get_Block_cfgpred(n, i))) break;
282 if (i == get_Block_n_cfgpreds(n))
288 case iro_Jmp: /* GL: Why not same for op_Raise?? */
289 /* unreachable code elimination */
290 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
292 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
293 See cases for iro_Cond and iro_Proj in transform_node. */
294 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
295 case iro_Or: if (a == b) {n = a; break;}
300 /* After running compute_node there is only one constant predecessor.
301 Find this predecessors value and remember the other node: */
302 if ((tv = computed_value (a))) {
304 } else if ((tv = computed_value (b))) {
308 /* If this predecessors constant value is zero, the operation is
309 unnecessary. Remove it: */
310 if (tarval_classify (tv) == 0) {
320 /* these operations are not commutative. Test only one predecessor. */
321 if (tarval_classify (computed_value (b)) == 0) {
323 /* Test if b > #bits of a ==> return 0 / divide b by #bits
324 --> transform node? */
327 case iro_Not: /* NotNot x == x */
328 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
329 out of bounds exception if min =! max? */
330 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
331 n = get_unop_op(get_unop_op(n));
334 /* Mul is commutative and has again an other neutral element. */
335 if (tarval_classify (computed_value (a)) == 1) {
337 } else if (tarval_classify (computed_value (b)) == 1) {
342 /* Div is not commutative. */
343 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
344 /* Turn Div into a tuple (mem, bad, a) */
345 ir_node *mem = get_Div_mem(n);
346 turn_into_tuple(n, 3);
347 set_Tuple_pred(n, 0, mem);
348 set_Tuple_pred(n, 1, new_Bad());
349 set_Tuple_pred(n, 2, a);
352 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
353 teated in transform node.
354 case iro_Mod, Quot, DivMod
358 /* And has it's own neutral element */
359 else if (tarval_classify (computed_value (a)) == -1) {
361 } else if (tarval_classify (computed_value (b)) == -1) {
366 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
368 } else if (get_irn_mode(n) == mode_b) {
369 if (get_irn_op(a) == op_Conv &&
370 get_irn_mode (get_Conv_op(a)) == mode_b) {
371 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
378 /* Several optimizations:
379 - no Phi in start block.
380 - remove Id operators that are inputs to Phi
381 - fold Phi-nodes, iff they have only one predecessor except
387 ir_node *block = NULL; /* to shutup gcc */
388 ir_node *first_val = NULL; /* to shutup gcc */
389 ir_node *scnd_val = NULL; /* to shutup gcc */
391 n_preds = get_Phi_n_preds(n);
393 block = get_nodes_Block(n);
394 assert(get_irn_op (block) == op_Block);
396 /* there should be no Phi nodes in the Start region. */
397 if (block == current_ir_graph->start_block) {
402 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
403 /* GL: why not return new_Bad? */
408 /* first we test for a special case: */
409 /* Confirm is a special node fixing additional information for a
410 value that is known at a certain point. This is useful for
411 dataflow analysis. */
413 ir_node *a = follow_Id (get_Phi_pred(n, 0));
414 ir_node *b = follow_Id (get_Phi_pred(n, 1));
415 if ( (get_irn_op(a) == op_Confirm)
416 && (get_irn_op(b) == op_Confirm)
417 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
418 && (get_irn_n(a, 1) == get_irn_n (b, 1))
419 && (a->data.num == (~b->data.num & irpn_True) )) {
420 n = follow_Id (get_irn_n(a, 0));
426 /* Find first non-self-referencing input */
427 for (i = 0; i < n_preds; ++i) {
428 first_val = follow_Id(get_Phi_pred(n, i));
430 set_Phi_pred(n, i, first_val);
431 if ( (first_val != n) /* not self pointer */
432 && (get_irn_op(first_val) != op_Bad) /* value not dead */
433 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
434 break; /* then found first value. */
438 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
439 if (i >= n_preds) { n = new_Bad(); break; }
443 /* follow_Id () for rest of inputs, determine if any of these
444 are non-self-referencing */
445 while (++i < n_preds) {
446 scnd_val = follow_Id(get_Phi_pred(n, i));
448 set_Phi_pred(n, i, scnd_val);
450 && (scnd_val != first_val)
451 && (get_irn_op(scnd_val) != op_Bad)
452 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
457 /* Fold, if no multiple distinct non-self-referencing inputs */
461 /* skip the remaining Ids. */
462 while (++i < n_preds) {
463 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
471 a = skip_Proj(get_Load_mem(n));
472 b = skip_Proj(get_Load_ptr(n));
474 if (get_irn_op(a) == op_Store) {
475 if ( different_identity (b, get_Store_ptr(a))) {
476 /* load and store use different pointers, therefore load
477 needs not take store's memory but the state before. */
478 set_Load_mem (n, get_Store_mem(a));
479 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
485 /* remove unnecessary store. */
487 a = skip_Proj(get_Store_mem(n));
488 b = get_Store_ptr(n);
489 c = skip_Proj(get_Store_value(n));
491 if (get_irn_op(a) == op_Store
492 && get_Store_ptr(a) == b
493 && skip_Proj(get_Store_value(a)) == c) {
494 /* We have twice exactly the same store -- a write after write. */
496 } else if (get_irn_op(c) == op_Load
497 && (a == c || skip_Proj(get_Load_mem(c)) == a)
498 && get_Load_ptr(c) == b )
499 /* !!!??? and a cryptic test */ {
500 /* We just loaded the value from the same memory, i.e., the store
501 doesn't change the memory -- a write after read. */
502 turn_into_tuple(n, 2);
503 set_Tuple_pred(n, 0, a);
504 set_Tuple_pred(n, 1, new_Bad());
511 a = get_Proj_pred(n);
513 if ( get_irn_op(a) == op_Tuple) {
514 /* Remove the Tuple/Proj combination. */
515 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
516 n = get_Tuple_pred(a, get_Proj_proj(n));
518 assert(0); /* This should not happen! (GL added this assert) */
521 } else if (get_irn_mode(n) == mode_X &&
522 is_Bad(get_nodes_Block(n))) {
523 /* Remove dead control flow. */
537 } /* end equivalent_node() */
540 /* tries several [inplace] [optimizing] transformations and returns a
541 equivalent node. The difference to equivalent_node is that these
542 transformations _do_ generate new nodes, and thus the old node must
543 not be freed even if the equivalent node isn't the old one. */
545 transform_node (ir_node *n)
548 ir_node *a = NULL, *b;
551 switch (get_irn_opcode(n)) {
557 a = get_DivMod_left(n);
558 b = get_DivMod_right(n);
559 mode = get_irn_mode(a);
561 if (!( mode_is_int(get_irn_mode(a))
562 && mode_is_int(get_irn_mode(b))))
566 a = new_Const (mode, tarval_from_long (mode, 1));
567 b = new_Const (mode, tarval_from_long (mode, 0));
574 if (tarval_classify(tb) == 1) {
575 b = new_Const (mode, tarval_from_long (mode, 0));
579 resa = tarval_div (ta, tb);
580 if (!resa) break; /* Causes exception!!! Model by replacing through
581 Jmp for X result!? */
582 resb = tarval_mod (ta, tb);
583 if (!resb) break; /* Causes exception! */
584 a = new_Const (mode, resa);
585 b = new_Const (mode, resb);
588 } else if (tarval_classify (ta) == 0) {
593 if (evaluated) { /* replace by tuple */
594 ir_node *mem = get_DivMod_mem(n);
595 turn_into_tuple(n, 4);
596 set_Tuple_pred(n, 0, mem);
597 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
598 set_Tuple_pred(n, 2, a);
599 set_Tuple_pred(n, 3, b);
600 assert(get_nodes_Block(n));
606 /* Replace the Cond by a Jmp if it branches on a constant
609 a = get_Cond_selector(n);
612 if (ta && (get_irn_mode(a) == mode_b)) {
613 /* It's a boolean Cond, branching on a boolean constant.
614 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
615 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
616 turn_into_tuple(n, 2);
617 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
618 set_Tuple_pred(n, 0, new_Bad());
619 set_Tuple_pred(n, 1, jmp);
621 set_Tuple_pred(n, 0, jmp);
622 set_Tuple_pred(n, 1, new_Bad());
624 } else if (ta && (get_irn_mode(a) == mode_I)) {
625 /* I don't want to allow Tuples smaller than the biggest Proj.
626 Also this tuple might get really big...
627 I generate the Jmp here, and remember it in link. Link is used
628 when optimizing Proj. */
629 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
630 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
631 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
632 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
633 /* The Eor is a negate. Generate a new Cond without the negate,
634 simulate the negate by exchanging the results. */
635 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
637 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
638 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
639 /* A Not before the Cond. Generate a new Cond without the Not,
640 simulate the Not by exchanging the results. */
641 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
648 a = get_Proj_pred(n);
650 if ( (get_irn_op(a) == op_Cond)
652 && get_irn_op(get_irn_link(a)) == op_Cond) {
653 /* Use the better Cond if the Proj projs from a Cond which get's
654 its result from an Eor/Not. */
655 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
656 || (get_irn_op(get_Cond_selector(a)) == op_Not))
657 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
658 && (get_irn_op(get_irn_link(a)) == op_Cond)
659 && (get_Cond_selector(get_irn_link(a)) ==
660 get_Eor_left(get_Cond_selector(a))));
661 set_Proj_pred(n, get_irn_link(a));
662 if (get_Proj_proj(n) == 0)
666 } else if ( (get_irn_op(a) == op_Cond)
667 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
669 /* The Cond is a Switch on a Constant */
670 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
671 /* The always taken branch, reuse the existing Jmp. */
672 if (!get_irn_link(a)) /* well, if it exists ;-> */
673 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
674 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
677 /* a never taken branch */
683 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
685 b = get_Eor_right(n);
687 if ( (get_irn_mode(n) == mode_b)
688 && (get_irn_op(a) == op_Proj)
689 && (get_irn_mode(a) == mode_b)
690 && (tarval_classify (computed_value (b)) == 1)
691 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
692 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
693 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
694 mode_b, get_negated_pnc(get_Proj_proj(a)));
695 else if ( (get_irn_mode(n) == mode_b)
696 && (tarval_classify (computed_value (b)) == 1))
697 /* The Eor is a Not. Replace it by a Not. */
698 /* ????!!!Extend to bitfield 1111111. */
699 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
705 if ( (get_irn_mode(n) == mode_b)
706 && (get_irn_op(a) == op_Proj)
707 && (get_irn_mode(a) == mode_b)
708 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
709 /* We negate a Cmp. The Cmp has the negated result anyways! */
710 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
711 mode_b, get_negated_pnc(get_Proj_proj(a)));
719 /* **************** Common Subexpression Elimination **************** */
721 /* Compare function for two nodes in the hash table. Gets two */
722 /* nodes as parameters. */
723 /* @@@ a+b != b+a ? */
725 vt_cmp (const void *elt, const void *key)
733 if (a == b) return 0;
735 if ((get_irn_op(a) != get_irn_op(b)) ||
736 (get_irn_mode(a) != get_irn_mode(b))) return 1;
738 /* compare if a's in and b's in are equal */
739 /* GL: we optimize only nodes with in arrays of fixed sizes.
740 if (get_irn_arity (a) != -2) {
741 ins = get_irn_arity (a);
742 if (ins != get_irn_arity (b)) return 1;
743 ain = get_irn_in (a);
744 bin = get_irn_in (b);
747 if (get_irn_arity (a) != get_irn_arity(b))
750 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
751 /* do if (*ain++ != *bin++) return 1; while (ins--); */
752 for (i = -1; i < get_irn_arity(a); i++)
753 if (get_irn_n(a, i) != get_irn_n(b, i))
757 switch (get_irn_opcode(a)) {
759 return get_irn_const_attr (a) != get_irn_const_attr (b);
761 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
763 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
764 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
766 return (get_irn_free_attr(a) != get_irn_free_attr(b));
768 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
769 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
771 return (get_irn_call_attr(a) != get_irn_call_attr(b));
773 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
774 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
775 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
776 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
777 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
778 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
780 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
788 ir_node_hash (ir_node *node)
793 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
794 h = get_irn_arity(node);
796 /* consider all in nodes... except the block. */
797 for (i = 0; i < get_irn_arity(node); i++) {
798 h = 9*h + (unsigned long)get_irn_n(node, i);
802 h = 9*h + (unsigned long) get_irn_mode (node);
804 h = 9*h + (unsigned long) get_irn_op (node);
810 new_identities (void)
812 return new_pset (vt_cmp, TUNE_NIR_NODES);
816 del_identities (pset *value_table)
818 del_pset (value_table);
821 /* Return the canonical node computing the same value as n.
822 Looks up the node in a hash table. */
823 static inline ir_node *
824 identify (pset *value_table, ir_node *n)
828 if (!value_table) return n;
830 switch (get_irn_opcode (n)) {
837 /* for commutative operators perform a OP b == b OP a */
838 if (get_binop_left(n) > get_binop_right(n)) {
839 ir_node *h = get_binop_left(n);
840 set_binop_left(n, get_binop_right(n));
841 set_binop_right(n, h);
847 o = pset_find (value_table, n, ir_node_hash (n));
853 /* Return the canonical node computing the same value as n.
854 Looks up the node in a hash table, enters it in the table
855 if it isn't there yet. */
857 identify_remember (pset *value_table, ir_node *node)
861 if (!value_table) return node;
863 /* lookup or insert in hash table with given hash key. */
864 o = pset_insert (value_table, node, ir_node_hash (node));
866 if (o == node) return node;
871 /* garbage in, garbage out. If a node has a dead input, i.e., the
872 Bad node is input to the node, return the Bad node. */
873 static inline ir_node *
877 ir_op* op = get_irn_op(node);
879 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
880 blocks predecessors is dead. */
881 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
882 for (i = -1; i < get_irn_arity(node); i++) {
883 if (is_Bad(get_irn_n(node, i))) {
889 /* If Block has only Bads as predecessors it's garbage. */
890 /* If Phi has only Bads as predecessors it's garbage. */
891 if (op == op_Block || op == op_Phi) {
892 for (i = 0; i < get_irn_arity(node); i++) {
893 if (!is_Bad(get_irn_n(node, i))) break;
895 if (i = get_irn_arity(node)) node = new_Bad();
902 /* These optimizations deallocate nodes from the obstack.
903 It can only be called if it is guaranteed that no other nodes
904 reference this one, i.e., right after construction of a node. */
906 optimize (ir_node *n)
911 /* Allways optimize Phi nodes: part of the construction. */
912 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
914 /* if not optimize return n */
916 printf(" attention: empty node!!! \n");
920 /* constant expression evaluation / constant folding */
921 if (get_opt_constant_folding()) {
922 /* constants can not be evaluated */
923 if (get_irn_op(n) != op_Const) {
924 /* try to evaluate */
925 tv = computed_value (n);
927 /* evaluation was succesful -- replace the node. */
928 obstack_free (current_ir_graph->obst, n);
929 return new_Const (get_tv_mode (tv), tv);
934 /* remove unnecessary nodes */
935 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
936 n = equivalent_node (n);
938 /** common subexpression elimination **/
939 /* Checks whether n is already available. */
940 /* The block input is used to distinguish different subexpressions. Right
941 now all nodes are pinned to blocks, i.e., the cse only finds common
942 subexpressions within a block. */
944 n = identify (current_ir_graph->value_table, n);
945 /* identify found a cse, so deallocate the old node. */
947 obstack_free (current_ir_graph->obst, old_n);
948 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
951 /* Some more constant expression evaluation that does not allow to
953 if (get_opt_constant_folding())
954 n = transform_node (n);
956 /* Remove nodes with dead (Bad) input. */
958 /* Now we can verify the node, as it has no dead inputs any more. */
961 /* Now we have a legal, useful node. Enter it in hash table for cse */
963 n = identify_remember (current_ir_graph->value_table, n);
966 #if 0 /* GL: what's the use of this?? */
967 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
968 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
969 pdeq_putr (current_ir_graph->keep.living, n);
976 /* These optimizations never deallocate nodes. This can cause dead
977 nodes lying on the obstack. Remove these by a dead node elimination,
978 i.e., a copying garbage collection. */
980 optimize_in_place (ir_node *n)
985 if (!get_optimize()) return n;
987 /* if not optimize return n */
989 /* Here this is possible. Why? */
993 /* constant expression evaluation / constant folding */
994 if (get_opt_constant_folding()) {
995 /* constants can not be evaluated */
996 if (get_irn_op(n) != op_Const) {
997 /* try to evaluate */
998 tv = computed_value (n);
1000 /* evaluation was succesful -- replace the node. */
1001 n = new_Const (get_tv_mode (tv), tv);
1002 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1004 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1009 /* remove unnecessary nodes */
1010 /*if (get_opt_constant_folding()) */
1011 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1012 n = equivalent_node (n);
1014 /** common subexpression elimination **/
1015 /* Checks whether n is already available. */
1016 /* The block input is used to distinguish different subexpressions. Right
1017 now all nodes are pinned to blocks, i.e., the cse only finds common
1018 subexpressions within a block. */
1020 n = identify (current_ir_graph->value_table, n);
1022 /* identify found a cse, so deallocate the old node. */
1024 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1027 /* Some more constant expression evaluation. */
1028 if (get_opt_constant_folding())
1029 n = transform_node (n);
1031 /* Remove nodes with dead (Bad) input. */
1033 /* Now we can verify the node, as it has no dead inputs any more. */
1036 /* Now we have a legal, useful node. Enter it in hash table for cse.
1037 Blocks should be unique anyways. (Except the successor of start:
1038 is cse with the start block!) */
1039 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1040 n = identify_remember (current_ir_graph->value_table, n);