1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
2 ** All rights reserved.
4 ** Authors: Christian Schaefer, Goetz Lindenmaier
6 ** iropt --- optimizations intertwined with IR construction.
13 # include "irnode_t.h"
14 # include "irgraph_t.h"
23 /* Make types visible to allow most efficient access */
24 # include "entity_t.h"
26 /* Trivial inlineable routine for copy propagation.
27 Does follow Ids, needed to optimize inlined code. */
28 static inline ir_node *
29 follow_Id (ir_node *n)
31 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
35 static inline tarval *
38 if ((n != NULL) && (get_irn_op(n) == op_Const))
39 return get_Const_tarval(n);
44 /* if n can be computed, return the value, else NULL. Performs
45 constant folding. GL: Only if n is arithmetic operator? */
47 computed_value (ir_node *n)
51 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
52 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
56 /* get the operands we will work on for simple cases. */
58 a = get_binop_left(n);
59 b = get_binop_right(n);
60 } else if (is_unop(n)) {
64 /* if the operands are constants, get the target value, else set it NULL.
65 (a and b may be NULL if we treat a node that is no computation.) */
69 /* Perform the constant evaluation / computation. */
70 switch (get_irn_opcode(n)) {
72 res = get_Const_tarval(n);
74 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
75 && (get_irn_mode(a) != mode_p)) {
76 res = tarval_add (ta, tb);
80 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
81 && (get_irn_mode(a) != mode_p)) {
82 res = tarval_sub (ta, tb);
84 res = tarval_mode_null [get_irn_modecode (n)];
88 if (ta && mode_is_float(get_irn_mode(a)))
89 res = tarval_neg (ta);
92 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
93 res = tarval_mul (ta, tb);
95 /* a*0 = 0 or 0*b = 0:
96 calls computed_value recursive and returns the 0 with proper
99 if ( (tarval_classify ((v = computed_value (a))) == 0)
100 || (tarval_classify ((v = computed_value (b))) == 0)) {
106 /* This was missing in original implementation. Why? */
107 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
108 if (tarval_classify(tb) == 0) {res = NULL; break;}
109 res = tarval_quo(ta, tb);
113 /* This was missing in original implementation. Why? */
114 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
115 if (tarval_classify(tb) == 0) {res = NULL; break;}
116 res = tarval_div(ta, tb);
120 /* This was missing in original implementation. Why? */
121 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
122 if (tarval_classify(tb) == 0) {res = NULL; break;}
123 res = tarval_mod(ta, tb);
128 res = tarval_abs (ta);
132 res = tarval_and (ta, tb);
135 if ( (tarval_classify ((v = computed_value (a))) == 0)
136 || (tarval_classify ((v = computed_value (b))) == 0)) {
143 res = tarval_or (ta, tb);
146 if ( (tarval_classify ((v = computed_value (a))) == -1)
147 || (tarval_classify ((v = computed_value (b))) == -1)) {
152 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
153 case iro_Not: if (ta) { res = tarval_neg (ta); } break;
154 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
155 /* tarval_shr is faulty !! */
156 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
157 case iro_Shrs:if (ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
158 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
159 case iro_Conv:if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
161 case iro_Proj: /* iro_Cmp */
165 a = get_Proj_pred(n);
166 /* Optimize Cmp nodes.
167 This performs a first step of unreachable code elimination.
168 Proj can not be computed, but folding a Cmp above the Proj here is
169 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
171 There are several case where we can evaluate a Cmp node:
172 1. The nodes compared are both the same. If we compare for
173 equal, this will return true, else it will return false.
174 This step relies on cse.
175 2. The predecessors of Cmp are target values. We can evaluate
177 3. The predecessors are Allocs or void* constants. Allocs never
178 return NULL, they raise an exception. Therefore we can predict
180 if (get_irn_op(a) == op_Cmp) {
181 aa = get_Cmp_left(a);
182 ab = get_Cmp_right(a);
183 if (aa == ab) { /* 1.: */
184 /* This is a tric with the bits used for encoding the Cmp
185 Proj numbers, the following statement is not the same:
186 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
187 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
189 tarval *taa = computed_value (aa);
190 tarval *tab = computed_value (ab);
191 if (taa && tab) { /* 2.: */
192 /* strange checks... */
193 ir_pncmp flags = tarval_comp (taa, tab);
194 if (flags != irpn_False) {
195 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
197 } else { /* check for 3.: */
198 ir_node *aaa = skip_nop(skip_Proj(aa));
199 ir_node *aba = skip_nop(skip_Proj(ab));
200 if ( ( (/* aa is ProjP and aaa is Alloc */
201 (get_irn_op(aa) == op_Proj)
202 && (get_irn_mode(aa) == mode_p)
203 && (get_irn_op(aaa) == op_Alloc))
204 && ( (/* ab is constant void */
205 (get_irn_op(ab) == op_Const)
206 && (get_irn_mode(ab) == mode_p)
207 && (get_Const_tarval(ab) == tarval_p_void))
208 || (/* ab is other Alloc */
209 (get_irn_op(ab) == op_Proj)
210 && (get_irn_mode(ab) == mode_p)
211 && (get_irn_op(aba) == op_Alloc)
213 || (/* aa is void and aba is Alloc */
214 (get_irn_op(aa) == op_Const)
215 && (get_irn_mode(aa) == mode_p)
216 && (get_Const_tarval(aa) == tarval_p_void)
217 && (get_irn_op(ab) == op_Proj)
218 && (get_irn_mode(ab) == mode_p)
219 && (get_irn_op(aba) == op_Alloc)))
221 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
225 /* printf(" # comp_val: Proj node, not optimized\n"); */
237 /* returns 1 if the a and b are pointers to different locations. */
239 different_identity (ir_node *a, ir_node *b)
241 assert (get_irn_mode (a) == mode_p
242 && get_irn_mode (b) == mode_p);
244 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
245 ir_node *a1 = get_Proj_pred (a);
246 ir_node *b1 = get_Proj_pred (b);
247 if (a1 != b1 && get_irn_op (a1) == op_Alloc
248 && get_irn_op (b1) == op_Alloc)
255 /* equivalent_node returns a node equivalent to N. It skips all nodes that
256 perform no actual computation, as, e.g., the Id nodes. It does not create
257 new nodes. It is therefore safe to free N if the node returned is not N.
258 If a node returns a Tuple we can not just skip it. If the size of the
259 in array fits, we transform n into a tuple (e.g., Div). */
261 equivalent_node (ir_node *n)
264 ir_node *a = NULL; /* to shutup gcc */
265 ir_node *b = NULL; /* to shutup gcc */
266 ir_node *c = NULL; /* to shutup gcc */
268 ins = get_irn_arity (n);
270 /* get the operands we will work on */
272 a = get_binop_left(n);
273 b = get_binop_right(n);
274 } else if (is_unop(n)) {
278 /* skip unnecessary nodes. */
279 switch (get_irn_opcode (n)) {
282 /* The Block constructor does not call optimize, but mature_block
283 calls the optimization. */
284 assert(get_Block_matured(n));
286 /* A single entry Block following a single exit Block can be merged,
287 if it is not the Start block. */
288 /* !!! Beware, all Phi-nodes of n must have been optimized away.
289 This should be true, as the block is matured before optimize is called.
290 But what about Phi-cycles with the Phi0/Id that could not be resolved? */
291 if (get_Block_n_cfgpreds(n) == 1
292 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
293 n = get_nodes_Block(get_Block_cfgpred(n, 0));
295 } else if ((n != current_ir_graph->start_block) &&
296 (n != current_ir_graph->end_block) ) {
298 /* If all inputs are dead, this block is dead too, except if it is
299 the start or end block. This is a step of unreachable code
301 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
302 if (!is_Bad(get_Block_cfgpred(n, i))) break;
304 if (i == get_Block_n_cfgpreds(n))
310 case iro_Jmp: /* GL: Why not same for op_Raise?? */
311 /* unreachable code elimination */
312 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
314 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
315 See cases for iro_Cond and iro_Proj in transform_node. */
316 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
317 case iro_Or: if (a == b) {n = a; break;}
322 /* After running compute_node there is only one constant predecessor.
323 Find this predecessors value and remember the other node: */
324 if ((tv = computed_value (a))) {
326 } else if ((tv = computed_value (b))) {
330 /* If this predecessors constant value is zero, the operation is
331 unnecessary. Remove it: */
332 if (tarval_classify (tv) == 0) {
342 /* these operations are not commutative. Test only one predecessor. */
343 if (tarval_classify (computed_value (b)) == 0) {
345 /* Test if b > #bits of a ==> return 0 / divide b by #bits
346 --> transform node? */
349 case iro_Not: /* NotNot x == x */
350 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
351 out of bounds exception if min =! max? */
352 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
353 n = get_unop_op(get_unop_op(n));
356 /* Mul is commutative and has again an other neutral element. */
357 if (tarval_classify (computed_value (a)) == 1) {
359 } else if (tarval_classify (computed_value (b)) == 1) {
364 /* Div is not commutative. */
365 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
366 /* Turn Div into a tuple (mem, bad, a) */
367 ir_node *mem = get_Div_mem(n);
368 turn_into_tuple(n, 3);
369 set_Tuple_pred(n, 0, mem);
370 set_Tuple_pred(n, 1, new_Bad());
371 set_Tuple_pred(n, 2, a);
374 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
375 teated in transform node.
376 case iro_Mod, Quot, DivMod
380 /* And has it's own neutral element */
381 else if (tarval_classify (computed_value (a)) == -1) {
383 } else if (tarval_classify (computed_value (b)) == -1) {
388 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
390 } else if (get_irn_mode(n) == mode_b) {
391 if (get_irn_op(a) == op_Conv &&
392 get_irn_mode (get_Conv_op(a)) == mode_b) {
393 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
400 /* Several optimizations:
401 - no Phi in start block.
402 - remove Id operators that are inputs to Phi
403 - fold Phi-nodes, iff they have only one predecessor except
409 ir_node *block = NULL; /* to shutup gcc */
410 ir_node *first_val = NULL; /* to shutup gcc */
411 ir_node *scnd_val = NULL; /* to shutup gcc */
413 n_preds = get_Phi_n_preds(n);
415 block = get_nodes_Block(n);
416 assert(get_irn_op (block) == op_Block);
418 /* there should be no Phi nodes in the Start region. */
419 if (block == current_ir_graph->start_block) {
424 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
425 /* GL: why not return new_Bad? */
430 /* first we test for a special case: */
431 /* Confirm is a special node fixing additional information for a
432 value that is known at a certain point. This is useful for
433 dataflow analysis. */
435 ir_node *a = follow_Id (get_Phi_pred(n, 0));
436 ir_node *b = follow_Id (get_Phi_pred(n, 1));
437 if ( (get_irn_op(a) == op_Confirm)
438 && (get_irn_op(b) == op_Confirm)
439 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
440 && (get_irn_n(a, 1) == get_irn_n (b, 1))
441 && (a->data.num == (~b->data.num & irpn_True) )) {
442 n = follow_Id (get_irn_n(a, 0));
448 /* Find first non-self-referencing input */
449 for (i = 0; i < n_preds; ++i) {
450 first_val = follow_Id(get_Phi_pred(n, i));
452 set_Phi_pred(n, i, first_val);
453 if ( (first_val != n) /* not self pointer */
454 && (get_irn_op(first_val) != op_Bad) /* value not dead */
455 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
456 break; /* then found first value. */
460 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
461 if (i >= n_preds) { n = new_Bad(); break; }
465 /* follow_Id () for rest of inputs, determine if any of these
466 are non-self-referencing */
467 while (++i < n_preds) {
468 scnd_val = follow_Id(get_Phi_pred(n, i));
470 set_Phi_pred(n, i, scnd_val);
472 && (scnd_val != first_val)
473 && (get_irn_op(scnd_val) != op_Bad)
474 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
479 /* Fold, if no multiple distinct non-self-referencing inputs */
483 /* skip the remaining Ids. */
484 while (++i < n_preds) {
485 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
493 a = skip_Proj(get_Load_mem(n));
494 b = skip_Proj(get_Load_ptr(n));
496 if (get_irn_op(a) == op_Store) {
497 if ( different_identity (b, get_Store_ptr(a))) {
498 /* load and store use different pointers, therefore load
499 needs not take store's memory but the state before. */
500 set_Load_mem (n, get_Store_mem(a));
501 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
507 /* remove unnecessary store. */
509 a = skip_Proj(get_Store_mem(n));
510 b = get_Store_ptr(n);
511 c = skip_Proj(get_Store_value(n));
513 if (get_irn_op(a) == op_Store
514 && get_Store_ptr(a) == b
515 && skip_Proj(get_Store_value(a)) == c) {
516 /* We have twice exactly the same store -- a write after write. */
518 } else if (get_irn_op(c) == op_Load
519 && (a == c || skip_Proj(get_Load_mem(c)) == a)
520 && get_Load_ptr(c) == b )
521 /* !!!??? and a cryptic test */ {
522 /* We just loaded the value from the same memory, i.e., the store
523 doesn't change the memory -- a write after read. */
524 turn_into_tuple(n, 2);
525 set_Tuple_pred(n, 0, a);
526 set_Tuple_pred(n, 1, new_Bad());
533 a = get_Proj_pred(n);
535 if ( get_irn_op(a) == op_Tuple) {
536 /* Remove the Tuple/Proj combination. */
537 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
538 n = get_Tuple_pred(a, get_Proj_proj(n));
540 assert(0); /* This should not happen! (GL added this assert) */
543 } else if (get_irn_mode(n) == mode_X &&
544 is_Bad(get_nodes_Block(n))) {
545 /* Remove dead control flow. */
559 } /* end equivalent_node() */
562 /* tries several [inplace] [optimizing] transformations and returns a
563 equivalent node. The difference to equivalent_node is that these
564 transformations _do_ generate new nodes, and thus the old node must
565 not be freed even if the equivalent node isn't the old one. */
567 transform_node (ir_node *n)
570 ir_node *a = NULL, *b;
573 switch (get_irn_opcode(n)) {
579 a = get_DivMod_left(n);
580 b = get_DivMod_right(n);
581 mode = get_irn_mode(a);
583 if (!( mode_is_int(get_irn_mode(a))
584 && mode_is_int(get_irn_mode(b))))
588 a = new_Const (mode, tarval_from_long (mode, 1));
589 b = new_Const (mode, tarval_from_long (mode, 0));
596 if (tarval_classify(tb) == 1) {
597 b = new_Const (mode, tarval_from_long (mode, 0));
601 resa = tarval_div (ta, tb);
602 if (!resa) break; /* Causes exception!!! Model by replacing through
603 Jmp for X result!? */
604 resb = tarval_mod (ta, tb);
605 if (!resb) break; /* Causes exception! */
606 a = new_Const (mode, resa);
607 b = new_Const (mode, resb);
610 } else if (tarval_classify (ta) == 0) {
615 if (evaluated) { /* replace by tuple */
616 ir_node *mem = get_DivMod_mem(n);
617 turn_into_tuple(n, 4);
618 set_Tuple_pred(n, 0, mem);
619 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
620 set_Tuple_pred(n, 2, a);
621 set_Tuple_pred(n, 3, b);
622 assert(get_nodes_Block(n));
628 /* Replace the Cond by a Jmp if it branches on a constant
631 a = get_Cond_selector(n);
634 if (ta && (get_irn_mode(a) == mode_b)) {
635 /* It's a boolean Cond, branching on a boolean constant.
636 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
637 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
638 turn_into_tuple(n, 2);
639 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
640 set_Tuple_pred(n, 0, new_Bad());
641 set_Tuple_pred(n, 1, jmp);
643 set_Tuple_pred(n, 0, jmp);
644 set_Tuple_pred(n, 1, new_Bad());
646 } else if (ta && (get_irn_mode(a) == mode_I)) {
647 /* I don't want to allow Tuples smaller than the biggest Proj.
648 Also this tuple might get really big...
649 I generate the Jmp here, and remember it in link. Link is used
650 when optimizing Proj. */
651 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
652 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
653 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
654 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
655 /* The Eor is a negate. Generate a new Cond without the negate,
656 simulate the negate by exchanging the results. */
657 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
659 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
660 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
661 /* A Not before the Cond. Generate a new Cond without the Not,
662 simulate the Not by exchanging the results. */
663 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
670 a = get_Proj_pred(n);
672 if ( (get_irn_op(a) == op_Cond)
674 && get_irn_op(get_irn_link(a)) == op_Cond) {
675 /* Use the better Cond if the Proj projs from a Cond which get's
676 its result from an Eor/Not. */
677 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
678 || (get_irn_op(get_Cond_selector(a)) == op_Not))
679 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
680 && (get_irn_op(get_irn_link(a)) == op_Cond)
681 && (get_Cond_selector(get_irn_link(a)) ==
682 get_Eor_left(get_Cond_selector(a))));
683 set_Proj_pred(n, get_irn_link(a));
684 if (get_Proj_proj(n) == 0)
688 } else if ( (get_irn_op(a) == op_Cond)
689 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
691 /* The Cond is a Switch on a Constant */
692 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
693 /* The always taken branch, reuse the existing Jmp. */
694 if (!get_irn_link(a)) /* well, if it exists ;-> */
695 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
696 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
699 /* a never taken branch */
705 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
707 b = get_Eor_right(n);
709 if ( (get_irn_mode(n) == mode_b)
710 && (get_irn_op(a) == op_Proj)
711 && (get_irn_mode(a) == mode_b)
712 && (tarval_classify (computed_value (b)) == 1)
713 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
714 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
715 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
716 mode_b, get_negated_pnc(get_Proj_proj(a)));
717 else if ( (get_irn_mode(n) == mode_b)
718 && (tarval_classify (computed_value (b)) == 1))
719 /* The Eor is a Not. Replace it by a Not. */
720 /* ????!!!Extend to bitfield 1111111. */
721 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
727 if ( (get_irn_mode(n) == mode_b)
728 && (get_irn_op(a) == op_Proj)
729 && (get_irn_mode(a) == mode_b)
730 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
731 /* We negate a Cmp. The Cmp has the negated result anyways! */
732 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
733 mode_b, get_negated_pnc(get_Proj_proj(a)));
741 /* **************** Common Subexpression Elimination **************** */
743 /* Compare function for two nodes in the hash table. Gets two */
744 /* nodes as parameters. */
745 /* @@@ a+b != b+a ? */
747 vt_cmp (const void *elt, const void *key)
755 if (a == b) return 0;
757 if ((get_irn_op(a) != get_irn_op(b)) ||
758 (get_irn_mode(a) != get_irn_mode(b))) return 1;
760 /* compare if a's in and b's in are equal */
761 /* GL: we optimize only nodes with in arrays of fixed sizes.
762 if (get_irn_arity (a) != -2) {
763 ins = get_irn_arity (a);
764 if (ins != get_irn_arity (b)) return 1;
765 ain = get_irn_in (a);
766 bin = get_irn_in (b);
769 if (get_irn_arity (a) != get_irn_arity(b))
772 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
773 /* do if (*ain++ != *bin++) return 1; while (ins--); */
774 for (i = -1; i < get_irn_arity(a); i++)
775 if (get_irn_n(a, i) != get_irn_n(b, i))
779 switch (get_irn_opcode(a)) {
781 return get_irn_const_attr (a) != get_irn_const_attr (b);
783 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
785 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
786 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
788 return (get_irn_free_attr(a) != get_irn_free_attr(b));
790 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
791 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
793 return (get_irn_call_attr(a) != get_irn_call_attr(b));
795 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
796 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
797 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
798 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
799 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
800 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
802 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
810 ir_node_hash (ir_node *node)
815 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
816 h = get_irn_arity(node);
818 /* consider all in nodes... except the block. */
819 for (i = 0; i < get_irn_arity(node); i++) {
820 h = 9*h + (unsigned long)get_irn_n(node, i);
824 h = 9*h + (unsigned long) get_irn_mode (node);
826 h = 9*h + (unsigned long) get_irn_op (node);
832 new_identities (void)
834 return new_pset (vt_cmp, TUNE_NIR_NODES);
838 del_identities (pset *value_table)
840 del_pset (value_table);
843 /* Return the canonical node computing the same value as n.
844 Looks up the node in a hash table. */
845 static inline ir_node *
846 identify (pset *value_table, ir_node *n)
850 if (!value_table) return n;
852 switch (get_irn_opcode (n)) {
859 /* for commutative operators perform a OP b == b OP a */
860 if (get_binop_left(n) > get_binop_right(n)) {
861 ir_node *h = get_binop_left(n);
862 set_binop_left(n, get_binop_right(n));
863 set_binop_right(n, h);
869 o = pset_find (value_table, n, ir_node_hash (n));
875 /* Return the canonical node computing the same value as n.
876 Looks up the node in a hash table, enters it in the table
877 if it isn't there yet. */
879 identify_remember (pset *value_table, ir_node *node)
883 if (!value_table) return node;
885 /* lookup or insert in hash table with given hash key. */
886 o = pset_insert (value_table, node, ir_node_hash (node));
888 if (o == node) return node;
893 /* garbage in, garbage out. If a node has a dead input, i.e., the
894 Bad node is input to the node, return the Bad node. */
895 static inline ir_node *
899 ir_op* op = get_irn_op(node);
901 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
902 blocks predecessors is dead. */
903 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
904 for (i = -1; i < get_irn_arity(node); i++) {
905 if (is_Bad(get_irn_n(node, i))) {
911 /* If Block has only Bads as predecessors it's garbage. */
912 /* If Phi has only Bads as predecessors it's garbage. */
913 if (op == op_Block || op == op_Phi) {
914 for (i = 0; i < get_irn_arity(node); i++) {
915 if (!is_Bad(get_irn_n(node, i))) break;
917 if (i = get_irn_arity(node)) node = new_Bad();
924 /* These optimizations deallocate nodes from the obstack.
925 It can only be called if it is guaranteed that no other nodes
926 reference this one, i.e., right after construction of a node. */
928 optimize (ir_node *n)
933 /* Allways optimize Phi nodes: part of the construction. */
934 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
936 /* if not optimize return n */
938 printf(" attention: empty node!!! \n");
942 /* constant expression evaluation / constant folding */
943 if (get_opt_constant_folding()) {
944 /* constants can not be evaluated */
945 if (get_irn_op(n) != op_Const) {
946 /* try to evaluate */
947 tv = computed_value (n);
949 /* evaluation was succesful -- replace the node. */
950 obstack_free (current_ir_graph->obst, n);
951 return new_Const (get_tv_mode (tv), tv);
956 /* remove unnecessary nodes */
957 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
958 n = equivalent_node (n);
960 /** common subexpression elimination **/
961 /* Checks whether n is already available. */
962 /* The block input is used to distinguish different subexpressions. Right
963 now all nodes are pinned to blocks, i.e., the cse only finds common
964 subexpressions within a block. */
966 n = identify (current_ir_graph->value_table, n);
967 /* identify found a cse, so deallocate the old node. */
969 obstack_free (current_ir_graph->obst, old_n);
970 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
973 /* Some more constant expression evaluation that does not allow to
975 if (get_opt_constant_folding())
976 n = transform_node (n);
978 /* Remove nodes with dead (Bad) input. */
980 /* Now we can verify the node, as it has no dead inputs any more. */
983 /* Now we have a legal, useful node. Enter it in hash table for cse */
985 n = identify_remember (current_ir_graph->value_table, n);
988 #if 0 /* GL: what's the use of this?? */
989 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
990 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
991 pdeq_putr (current_ir_graph->keep.living, n);
998 /* These optimizations never deallocate nodes. This can cause dead
999 nodes lying on the obstack. Remove these by a dead node elimination,
1000 i.e., a copying garbage collection. */
1002 optimize_in_place (ir_node *n)
1007 if (!get_optimize()) return n;
1009 /* if not optimize return n */
1011 /* Here this is possible. Why? */
1015 /* constant expression evaluation / constant folding */
1016 if (get_opt_constant_folding()) {
1017 /* constants can not be evaluated */
1018 if (get_irn_op(n) != op_Const) {
1019 /* try to evaluate */
1020 tv = computed_value (n);
1022 /* evaluation was succesful -- replace the node. */
1023 n = new_Const (get_tv_mode (tv), tv);
1024 deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1026 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1031 /* remove unnecessary nodes */
1032 /*if (get_opt_constant_folding()) */
1033 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1034 n = equivalent_node (n);
1036 /** common subexpression elimination **/
1037 /* Checks whether n is already available. */
1038 /* The block input is used to distinguish different subexpressions. Right
1039 now all nodes are pinned to blocks, i.e., the cse only finds common
1040 subexpressions within a block. */
1042 n = identify (current_ir_graph->value_table, n);
1044 /* identify found a cse, so deallocate the old node. */
1046 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1049 /* Some more constant expression evaluation. */
1050 if (get_opt_constant_folding())
1051 n = transform_node (n);
1053 /* Remove nodes with dead (Bad) input. */
1055 /* Now we can verify the node, as it has no dead inputs any more. */
1058 /* Now we have a legal, useful node. Enter it in hash table for cse.
1059 Blocks should be unique anyways. (Except the successor of start:
1060 is cse with the start block!) */
1061 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1062 n = identify_remember (current_ir_graph->value_table, n);