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);
27 static inline tarval *
30 if ((n != NULL) && (get_irn_op(n) == op_Const))
31 return get_Const_tarval(n);
36 /* if n can be computed, return the value, else NULL. Performs
37 constant folding. GL: Only if n is arithmetic operator? */
39 computed_value (ir_node *n)
43 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
44 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
48 /* get the operands we will work on for simple cases. */
50 a = get_binop_left(n);
51 b = get_binop_right(n);
52 } else if (is_unop(n)) {
56 /* if the operands are constants, get the target value, else set it NULL.
57 (a and b may be NULL if we treat a node that is no computation.) */
61 /* Perform the constant evaluation / computation. */
62 switch (get_irn_opcode(n)) {
64 res = get_Const_tarval(n);
66 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
67 && (get_irn_mode(a) != mode_p)) {
68 res = tarval_add (ta, tb);
72 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
73 && (get_irn_mode(a) != mode_p)) {
74 res = tarval_sub (ta, tb);
76 res = tarval_mode_null [get_irn_modecode (n)];
80 if (ta && mode_is_float(get_irn_mode(a)))
81 res = /*tarval_minus (ta);*/ res;
84 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
85 res = tarval_mul (ta, tb);
87 /* calls computed_value recursive and returns the 0 with proper
88 mode. Why is this an extra case? */
90 if ( (tarval_classify ((v = computed_value (a))) == 0)
91 || (tarval_classify ((v = computed_value (b))) == 0)) {
98 res = /*tarval_abs (ta);*/ res;
99 /* allowed or problems with max/min ?? */
103 res = tarval_and (ta, tb);
106 if ( (tarval_classify ((v = computed_value (a))) == 0)
107 || (tarval_classify ((v = computed_value (b))) == 0)) {
114 res = tarval_or (ta, tb);
117 if ( (tarval_classify ((v = computed_value (a))) == -1)
118 || (tarval_classify ((v = computed_value (b))) == -1)) {
123 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
124 case iro_Not: if(ta) { /*res = tarval_not (ta)*/; } break;
125 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
126 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
127 case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
128 case iro_Rot: if(ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
129 case iro_Conv: if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
135 a = get_Proj_pred(n);
136 /* Optimize Cmp nodes.
137 This performs a first step of unreachable code elimination.
138 Proj can not be computed, but folding a Cmp above the Proj here is
139 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
141 There are several case where we can evaluate a Cmp node:
142 1. The nodes compared are both the same. If we compare for
143 equal, this will return true, else it will return false.
144 This step relies on cse.
145 2. The predecessors of Cmp are target values. We can evaluate
147 3. The predecessors are Allocs or void* constants. Allocs never
148 return NULL, they raise an exception. Therefore we can predict
150 if (get_irn_op(a) == op_Cmp) {
151 aa = get_Cmp_left(a);
152 ab = get_Cmp_right(a);
153 if (aa == ab) { /* 1.: */
154 /* This is a tric with the bits used for encoding the Cmp
155 Proj numbers, the following statement is not the same:
156 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
157 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
159 tarval *taa = computed_value (aa);
160 tarval *tab = computed_value (ab);
161 if (taa && tab) { /* 2.: */
162 /* strange checks... */
163 ir_pncmp flags = tarval_comp (taa, tab);
164 if (flags != irpn_False) {
165 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
167 } else { /* check for 3.: */
168 ir_node *aaa = skip_nop(skip_Proj(aa));
169 ir_node *aba = skip_nop(skip_Proj(ab));
170 if ( ( (/* aa is ProjP and aaa is Alloc */
171 (get_irn_op(aa) == op_Proj)
172 && (get_irn_mode(aa) == mode_p)
173 && (get_irn_op(aaa) == op_Alloc))
174 && ( (/* ab is constant void */
175 (get_irn_op(ab) == op_Const)
176 && (get_irn_mode(ab) == mode_p)
177 && (get_Const_tarval(ab) == tarval_p_void))
178 || (/* ab is other Alloc */
179 (get_irn_op(ab) == op_Proj)
180 && (get_irn_mode(ab) == mode_p)
181 && (get_irn_op(aba) == op_Alloc)
183 || (/* aa is void and aba is Alloc */
184 (get_irn_op(aa) == op_Const)
185 && (get_irn_mode(aa) == mode_p)
186 && (get_Const_tarval(aa) == tarval_p_void)
187 && (get_irn_op(ab) == op_Proj)
188 && (get_irn_mode(ab) == mode_p)
189 && (get_irn_op(aba) == op_Alloc)))
191 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
195 /* printf(" # comp_val: Proj node, not optimized\n"); */
207 /* returns 1 if the a and b are pointers to different locations. */
209 different_identity (ir_node *a, ir_node *b)
211 assert (get_irn_mode (a) == mode_p
212 && get_irn_mode (b) == mode_p);
214 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
215 ir_node *a1 = get_Proj_pred (a);
216 ir_node *b1 = get_Proj_pred (b);
217 if (a1 != b1 && get_irn_op (a1) == op_Alloc
218 && get_irn_op (b1) == op_Alloc)
225 /* equivalent_node returns a node equivalent to N. It skips all nodes that
226 perform no actual computation, as, e.g., the Id nodes. It does not create
227 new nodes. It is therefore safe to free N if the node returned is not N.
228 If a node returns a Tuple we can not just skip it. If the size of the
229 in array fits, we transform n into a tuple (e.g., Div). */
231 equivalent_node (ir_node *n)
234 ir_node *a = NULL; /* to shutup gcc */
235 ir_node *b = NULL; /* to shutup gcc */
236 ir_node *c = NULL; /* to shutup gcc */
238 ins = get_irn_arity (n);
240 /* get the operands we will work on */
242 a = get_binop_left(n);
243 b = get_binop_right(n);
244 } else if (is_unop(n)) {
248 /* skip unnecessary nodes. */
249 switch (get_irn_opcode (n)) {
252 /* The Block constructor does not call optimize, but mature_block
253 calls the optimization. */
254 assert(get_Block_matured(n));
256 /* a single entry Region following a single exit Region can be merged */
257 /* !!! Beware, all Phi-nodes of n must have been optimized away.
258 This is true, as the block is matured before optimize is called. */
259 if (get_Block_n_cfgpreds(n) == 1
260 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
261 n = get_nodes_Block(get_Block_cfgpred(n, 0));
263 } else if (n != current_ir_graph->start_block) {
265 /* If all inputs are dead, this block is dead too, except if it is
266 the start block. This is a step of unreachable code elimination */
267 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
268 if (!is_Bad(get_Block_cfgpred(n, i))) break;
270 if (i == get_Block_n_cfgpreds(n))
276 case iro_Jmp: /* GL: Why not same for op_Raise?? */
277 /* unreachable code elimination */
278 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
280 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
281 See cases for iro_Cond and iro_Proj in transform_node. */
282 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
283 case iro_Or: if (a == b) {n = a; break;}
288 /* After running compute_node there is only one constant predecessor.
289 Find this predecessors value and remember the other node: */
290 if ((tv = computed_value (a))) {
292 } else if ((tv = computed_value (b))) {
296 /* If this predecessors constant value is zero, the operation is
297 unnecessary. Remove it: */
298 if (tarval_classify (tv) == 0) {
308 /* these operations are not commutative. Test only one predecessor. */
309 if (tarval_classify (computed_value (b)) == 0) {
311 /* Test if b > #bits of a ==> return 0 / divide b by #bits
312 --> transform node? */
315 case iro_Not: /* NotNot x == x */
316 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
317 out of bounds exception if min =! max? */
318 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
319 n = get_unop_op(get_unop_op(n));
322 /* Mul is commutative and has again an other neutral element. */
323 if (tarval_classify (computed_value (a)) == 1) {
325 } else if (tarval_classify (computed_value (b)) == 1) {
330 /* Div is not commutative. */
331 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
332 /* Turn Div into a tuple (mem, bad, a) */
333 ir_node *mem = get_Div_mem(n);
334 turn_into_tuple(n, 3);
335 set_Tuple_pred(n, 0, mem);
336 set_Tuple_pred(n, 1, new_Bad());
337 set_Tuple_pred(n, 2, a);
340 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
341 teated in transform node.
342 case iro_Mod, Quot, DivMod
346 /* And has it's own neutral element */
347 else if (tarval_classify (computed_value (a)) == -1) {
349 } else if (tarval_classify (computed_value (b)) == -1) {
354 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
356 } else if (get_irn_mode(n) == mode_b) {
357 if (get_irn_op(a) == op_Conv &&
358 get_irn_mode (get_Conv_op(a)) == mode_b) {
359 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
366 /* Several optimizations:
367 - no Phi in start block.
368 - remove Id operators that are inputs to Phi
369 - fold Phi-nodes, iff they have only one predecessor except
373 ir_node *block = NULL; /* to shutup gcc */
374 ir_node *first_val = NULL; /* to shutup gcc */
375 ir_node *scnd_val = NULL; /* to shutup gcc */
377 n_preds = get_Phi_n_preds(n);
379 block = get_nodes_Block(n);
380 assert(get_irn_op (block) == op_Block);
382 /* there should be no Phi nodes in the Start region. */
383 if (block == current_ir_graph->start_block) {
388 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
389 /* GL: why not return new_Bad? */
394 /* first we test for a special case: */
395 /* Confirm is a special node fixing additional information for a
396 value that is known at a certain point. This is useful for
397 dataflow analysis. */
399 ir_node *a = follow_Id (get_Phi_pred(n, 0));
400 ir_node *b = follow_Id (get_Phi_pred(n, 1));
401 if ( (get_irn_op(a) == op_Confirm)
402 && (get_irn_op(b) == op_Confirm)
403 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
404 && (get_irn_n(a, 1) == get_irn_n (b, 1))
405 && (a->data.num == (~b->data.num & irpn_True) )) {
406 n = follow_Id (get_irn_n(a, 0));
411 /* Find first non-self-referencing input */
412 for (i = 0; i < n_preds; ++i) {
413 first_val = follow_Id(get_Phi_pred(n, i));
415 set_Phi_pred(n, i, first_val);
416 if ( (first_val != n) /* not self pointer */
417 && (get_irn_op(first_val) != op_Bad) /* value not dead */
418 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
419 break; /* then found first value. */
423 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
424 if (i > n_preds) { n = new_Bad(); break; }
428 /* follow_Id () for rest of inputs, determine if any of these
429 are non-self-referencing */
430 while (++i < n_preds) {
431 scnd_val = follow_Id(get_Phi_pred(n, i));
433 set_Phi_pred(n, i, scnd_val);
435 && (scnd_val != first_val)
436 && (get_irn_op(scnd_val) != op_Bad)
437 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
442 /* Fold, if no multiple distinct non-self-referencing inputs */
446 /* skip the remaining Ids. */
447 while (++i < n_preds) {
448 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
456 a = skip_Proj(get_Load_mem(n));
457 b = skip_Proj(get_Load_ptr(n));
459 if (get_irn_op(a) == op_Store) {
460 if ( different_identity (b, get_Store_ptr(a))) {
461 /* load and store use different pointers, therefore load
462 needs not take store's memory but the state before. */
463 set_Load_mem (n, get_Store_mem(a));
464 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
470 /* remove unnecessary store. */
472 a = skip_Proj(get_Store_mem(n));
473 b = get_Store_ptr(n);
474 c = skip_Proj(get_Store_value(n));
476 if (get_irn_op(a) == op_Store
477 && get_Store_ptr(a) == b
478 && skip_Proj(get_Store_value(a)) == c) {
479 /* We have twice exactly the same store -- a write after write. */
481 } else if (get_irn_op(c) == op_Load
482 && (a == c || skip_Proj(get_Load_mem(c)) == a)
483 && get_Load_ptr(c) == b )
484 /* !!!??? and a cryptic test */ {
485 /* We just loaded the value from the same memory, i.e., the store
486 doesn't change the memory -- a write after read. */
487 turn_into_tuple(n, 2);
488 set_Tuple_pred(n, 0, a);
489 set_Tuple_pred(n, 1, new_Bad());
496 a = get_Proj_pred(n);
498 if ( get_irn_op(a) == op_Tuple) {
499 /* Remove the Tuple/Proj combination. */
500 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
501 n = get_Tuple_pred(a, get_Proj_proj(n));
503 assert(0); /* This should not happen! (GL added this assert) */
506 } else if (get_irn_mode(n) == mode_X &&
507 is_Bad(get_nodes_Block(n))) {
508 /* Remove dead control flow. */
522 } /* end equivalent_node() */
525 /* tries several [inplace] [optimizing] transformations and returns a
526 equivalent node. The difference to equivalent_node is that these
527 transformations _do_ generate new nodes, and thus the old node must
528 not be freed even if the equivalent node isn't the old one. */
530 transform_node (ir_node *n)
533 ir_node *a = NULL, *b;
536 switch (get_irn_opcode(n)) {
542 a = get_DivMod_left(n);
543 b = get_DivMod_right(n);
544 mode = get_irn_mode(a);
546 if (!( mode_is_int(get_irn_mode(a))
547 && mode_is_int(get_irn_mode(b))))
551 a = new_Const (mode, tarval_from_long (mode, 1));
552 b = new_Const (mode, tarval_from_long (mode, 0));
559 if (tarval_classify(tb) == 1) {
560 b = new_Const (mode, tarval_from_long (mode, 0));
564 resa = tarval_div (ta, tb);
565 if (!resa) break; /* Causes exception!!! Model by replacing through
566 Jmp for X result!? */
567 resb = tarval_mod (ta, tb);
568 if (!resb) break; /* Causes exception! */
569 a = new_Const (mode, resa);
570 b = new_Const (mode, resb);
573 } else if (tarval_classify (ta) == 0) {
578 if (evaluated) { /* replace by tuple */
579 ir_node *mem = get_DivMod_mem(n);
580 turn_into_tuple(n, 4);
581 set_Tuple_pred(n, 0, mem);
582 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
583 set_Tuple_pred(n, 2, a);
584 set_Tuple_pred(n, 3, b);
585 assert(get_nodes_Block(n));
591 /* Replace the Cond by a Jmp if it branches on a constant
594 a = get_Cond_selector(n);
597 if (ta && (get_irn_mode(a) == mode_b)) {
598 /* It's a boolean Cond, branching on a boolean constant.
599 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
600 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
601 turn_into_tuple(n, 2);
602 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
603 set_Tuple_pred(n, 0, new_Bad());
604 set_Tuple_pred(n, 1, jmp);
606 set_Tuple_pred(n, 0, jmp);
607 set_Tuple_pred(n, 1, new_Bad());
609 } else if (ta && (get_irn_mode(a) == mode_I)) {
610 /* I don't want to allow Tuples smaller than the biggest Proj.
611 Also this tuple might get really big...
612 I generate the Jmp here, and remember it in link. Link is used
613 when optimizing Proj. */
614 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
615 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Eor)
616 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
617 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
618 /* The Eor is a negate. Generate a new Cond without the negate,
619 simulate the negate by exchanging the results. */
620 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
622 } else if ( (get_irn_op(get_Cond_selector(n)) == op_Not)
623 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
624 /* A Not before the Cond. Generate a new Cond without the Not,
625 simulate the Not by exchanging the results. */
626 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
633 a = get_Proj_pred(n);
635 if ( (get_irn_op(a) == op_Cond)
637 && get_irn_op(get_irn_link(a)) == op_Cond) {
638 /* Use the better Cond if the Proj projs from a Cond which get's
639 its result from an Eor/Not. */
640 assert ( ( (get_irn_op(get_Cond_selector(a)) == op_Eor)
641 || (get_irn_op(get_Cond_selector(a)) == op_Not))
642 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
643 && (get_irn_op(get_irn_link(a)) == op_Cond)
644 && (get_Cond_selector(get_irn_link(a)) ==
645 get_Eor_left(get_Cond_selector(a))));
646 set_Proj_pred(n, get_irn_link(a));
647 if (get_Proj_proj(n) == 0)
651 } else if ( (get_irn_op(a) == op_Cond)
652 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
654 /* The Cond is a Switch on a Constant */
655 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
656 /* The always taken branch, reuse the existing Jmp. */
657 if (!get_irn_link(a)) /* well, if it exists ;-> */
658 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
659 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
662 /* a never taken branch */
668 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
670 b = get_Eor_right(n);
672 if ( (get_irn_mode(n) == mode_b)
673 && (get_irn_op(a) == op_Proj)
674 && (get_irn_mode(a) == mode_b)
675 && (tarval_classify (computed_value (b)) == 1)
676 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
677 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
678 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
679 mode_b, get_negated_pnc(get_Proj_proj(a)));
680 else if ( (get_irn_mode(n) == mode_b)
681 && (tarval_classify (computed_value (b)) == 1))
682 /* The Eor is a Not. Replace it by a Not. */
683 /* ????!!!Extend to bitfield 1111111. */
684 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
687 case iro_Not: { /* @@@ not tested as boolean Eor not allowed any more. */
690 if ( (get_irn_mode(n) == mode_b)
691 && (get_irn_op(a) == op_Proj)
692 && (get_irn_mode(a) == mode_b)
693 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
694 /* We negate a Cmp. The Cmp has the negated result anyways! */
695 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
696 mode_b, get_negated_pnc(get_Proj_proj(a)));
704 /***************** Common Subexpression Elimination *****************/
706 /* Compare function for two nodes in the hash table. Gets two */
707 /* nodes as parameters. */
708 /* @@@ a+b != b+a ? */
710 vt_cmp (const void *elt, const void *key)
718 if (a == b) return 0;
720 if ((get_irn_op(a) != get_irn_op(b)) ||
721 (get_irn_mode(a) != get_irn_mode(b))) return 1;
723 /* compare if a's in and b's in are equal */
724 /* GL: we optimize only nodes with in arrays of fixed sizes.
725 if (get_irn_arity (a) != -2) {
726 ins = get_irn_arity (a);
727 if (ins != get_irn_arity (b)) return 1;
728 ain = get_irn_in (a);
729 bin = get_irn_in (b);
732 if (get_irn_arity (a) != get_irn_arity(b))
735 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
736 /* do if (*ain++ != *bin++) return 1; while (ins--); */
737 for (i = -1; i < get_irn_arity(a); i++)
738 if (get_irn_n(a, i) != get_irn_n(b, i))
742 switch (get_irn_opcode(a)) {
744 return get_irn_const_attr (a) != get_irn_const_attr (b);
746 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
748 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
749 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
751 return (get_irn_free_attr(a) != get_irn_free_attr(b));
753 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
754 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
756 return (get_irn_call_attr(a)->kind != get_irn_call_attr(b)->kind)
757 || (get_irn_call_attr(a)->arity != get_irn_call_attr(b)->arity);
759 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
760 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
761 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
762 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
763 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
764 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
766 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
774 ir_node_hash (ir_node *node)
779 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
780 h = get_irn_arity(node);
782 /* consider all in nodes... except the block. */
783 for (i = 0; i < get_irn_arity(node); i++) {
784 h = 9*h + (unsigned long)get_irn_n(node, i);
788 h = 9*h + (unsigned long) get_irn_mode (node);
790 h = 9*h + (unsigned long) get_irn_op (node);
796 new_identities (void)
798 return new_pset (vt_cmp, TUNE_NIR_NODES);
802 del_identities (pset *value_table)
804 del_pset (value_table);
807 /* Return the canonical node computing the same value as n.
808 Looks up the node in a hash table. */
809 static inline ir_node *
810 identify (pset *value_table, ir_node *n)
814 if (!value_table) return n;
816 switch (get_irn_opcode (n)) {
823 /* for commutative operators perform a OP b == b OP a */
824 if (get_binop_left(n) > get_binop_right(n)) {
825 ir_node *h = get_binop_left(n);
826 set_binop_left(n, get_binop_right(n));
827 set_binop_right(n, h);
833 o = pset_find (value_table, n, ir_node_hash (n));
839 /* Return the canonical node computing the same value as n.
840 Looks up the node in a hash table, enters it in the table
841 if it isn't there yet. */
843 identify_remember (pset *value_table, ir_node *node)
847 if (!value_table) return node;
849 /* lookup or insert in hash table with given hash key. */
850 o = pset_insert (value_table, node, ir_node_hash (node));
852 if (o == node) return node;
857 /* garbage in, garbage out. If a node has a dead input, i.e., the
858 Bad node is input to the node, return the Bad node. */
859 static inline ir_node *
863 ir_op* op = get_irn_op(node);
865 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
866 blocks predecessors is dead. */
867 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
868 for (i = -1; i < get_irn_arity(node); i++) {
869 if (is_Bad(get_irn_n(node, i))) {
879 /* These optimizations deallocate nodes from the obstack.
880 It can only be called if it is guaranteed that no other nodes
881 reference this one, i.e., right after construction of a node. */
883 optimize (ir_node *n)
888 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
890 /* if not optimize return n */
892 printf(" attention: empty node!!! \n");
896 /* constant expression evaluation / constant folding */
897 if (get_opt_constant_folding()) {
898 /* constants can not be evaluated */
899 if (get_irn_op(n) != op_Const) {
900 /* try to evaluate */
901 tv = computed_value (n);
903 /* evaluation was succesful -- replace the node. */
904 obstack_free (current_ir_graph->obst, n);
905 return new_Const (get_tv_mode (tv), tv);
910 /* remove unnecessary nodes */
911 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
912 n = equivalent_node (n);
914 /** common subexpression elimination **/
915 /* Checks whether n is already available. */
916 /* The block input is used to distinguish different subexpressions. Right
917 now all nodes are pinned to blocks, i.e., the cse only finds common
918 subexpressions within a block. */
920 n = identify (current_ir_graph->value_table, n);
921 /* identify found a cse, so deallocate the old node. */
923 obstack_free (current_ir_graph->obst, old_n);
924 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
927 /* Some more constant expression evaluation that does not allow to
929 if (get_opt_constant_folding())
930 n = transform_node (n);
932 /* Remove nodes with dead (Bad) input. */
934 /* Now we can verify the node, as it has no dead inputs any more. */
937 /* Now we have a legal, useful node. Enter it in hash table for cse */
939 n = identify_remember (current_ir_graph->value_table, n);
942 #if 0 /* GL: what's the use of this?? */
943 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
944 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
945 pdeq_putr (current_ir_graph->keep.living, n);
952 /* These optimizations never deallocate nodes. This can cause dead
953 nodes lying on the obstack. Remove these by a dead node elimination,
954 i.e., a copying garbage collection. */
956 optimize_in_place (ir_node *n)
962 /* if not optimize return n */
964 /* Here this is possible. Why? */
968 /* constant expression evaluation / constant folding */
969 if (get_opt_constant_folding()) {
970 /* constants can not be evaluated */
971 if (get_irn_op(n) != op_Const) {
972 /* try to evaluate */
973 tv = computed_value (n);
975 /* evaluation was succesful -- replace the node. */
976 return new_Const (get_tv_mode (tv), tv);
977 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
982 /* remove unnecessary nodes */
983 if (get_opt_constant_folding())
984 // if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
985 n = equivalent_node (n);
987 /** common subexpression elimination **/
988 /* Checks whether n is already available. */
989 /* The block input is used to distinguish different subexpressions. Right
990 now all nodes are pinned to blocks, i.e., the cse only finds common
991 subexpressions within a block. */
993 n = identify (current_ir_graph->value_table, n);
995 /* identify found a cse, so deallocate the old node. */
997 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1001 /* Some more constant expression evaluation. */
1002 if (get_opt_constant_folding())
1003 n = transform_node (n);
1006 /* Remove nodes with dead (Bad) input. */
1008 /* Now we can verify the node, as it has no dead inputs any more. */
1011 /* Now we have a legal, useful node. Enter it in hash table for cse */
1012 if (get_opt_cse()) {
1013 /* aborts ??! set/pset can not handle several hash tables??!
1014 No, suddenly it works. */
1015 n = identify_remember (current_ir_graph->value_table, n);