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.
14 /* Trivial inlineable routine for copy propagation.
15 Does follow Ids, needed to optimize inlined code. */
16 static inline ir_node *
17 follow_Id (ir_node *n)
19 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
24 static inline tarval *
27 if ((n != NULL) && (get_irn_op(n) == op_Const))
28 return get_Const_tarval(n);
34 /* if n can be computed, return the value, else NULL. Performs
35 constant Folding. GL: Only if n is arithmetic operator? */
37 computed_value (ir_node *n)
41 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
42 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
46 /* get the operands we will work on for simple cases. */
48 a = get_binop_left(n);
49 b = get_binop_right(n);
50 } else if (is_unop(n)) {
54 /* if the operands are constants, get the target value, else set it NULL.
55 (a and b may be NULL if we treat a node that is no computation.) */
59 /* Perform the constant evaluation / computation. */
60 switch (get_irn_opcode(n)) {
62 res = get_Const_tarval(n);
64 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
65 && (get_irn_mode(a) != mode_p)) {
66 res = tarval_add (ta, tb);
70 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
71 && (get_irn_mode(a) != mode_p)) {
72 res = tarval_sub (ta, tb);
74 res = tarval_mode_null [get_irn_modecode (n)];
78 if (ta && mode_is_float(get_irn_mode(a)))
79 res = /*tarval_minus (ta);*/ res;
82 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
83 res = tarval_mul (ta, tb);
85 /* calls computed_value recursive and returns the 0 with proper
86 mode. Why is this an extra case? */
88 if ( (tarval_classify ((v = computed_value (a))) == 0)
89 || (tarval_classify ((v = computed_value (b))) == 0)) {
96 res = /*tarval_abs (ta);*/ res;
97 /* allowded or problems with max/min ?? */
101 res = tarval_and (ta, tb);
104 if ( (tarval_classify ((v = computed_value (a))) == 0)
105 || (tarval_classify ((v = computed_value (b))) == 0)) {
112 res = tarval_or (ta, tb);
115 if ( (tarval_classify ((v = computed_value (a))) == -1)
116 || (tarval_classify ((v = computed_value (b))) == -1)) {
121 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
122 case iro_Not: if(ta) { /*res = tarval_not (ta)*/; } break;
123 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
124 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
125 case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
126 case iro_Rot: if(ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
127 case iro_Conv: if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
133 a = get_Proj_pred(n);
134 /* Optimize Cmp nodes.
135 This performs a first step of unreachable code elimination.
136 Proj can not be computed, but folding a Cmp above the Proj here is
137 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
139 There are several case where we can evaluate a Cmp node:
140 1. The nodes compared are both the same. If we compare for
141 equal, this will return true, else it will return false.
142 This step relies on cse.
143 2. The predecessors of Cmp are target values. We can evaluate
145 3. The predecessors are Allocs or void* constants. Allocs never
146 return NULL, they raise an exception. Therefore we can predict
148 if (get_irn_op(a) == op_Cmp) {
149 aa = get_Cmp_left(a);
150 ab = get_Cmp_right(a);
151 if (aa == ab) { /* 1.: */
152 /* This is a tric with the bits used for encoding the Cmp
153 Proj numbers, the following statement is not the same:
154 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
155 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
157 tarval *taa = computed_value (aa);
158 tarval *tab = computed_value (ab);
159 if (taa && tab) { /* 2.: */
160 /* strange checks... */
161 ir_pncmp flags = tarval_comp (taa, tab);
162 if (flags != irpn_False) {
163 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
165 } else { /* check for 3.: */
166 ir_node *aaa = skip_nop(skip_Proj(aa));
167 ir_node *aba = skip_nop(skip_Proj(ab));
168 if ( ( (/* aa is ProjP and aaa is Alloc */
169 (get_irn_op(aa) == op_Proj)
170 && (get_irn_mode(aa) == mode_p)
171 && (get_irn_op(aaa) == op_Alloc))
172 && ( (/* ab is constant void */
173 (get_irn_op(ab) == op_Const)
174 && (get_irn_mode(ab) == mode_p)
175 && (get_Const_tarval(ab) == tarval_p_void))
176 || (/* ab is other Alloc */
177 (get_irn_op(ab) == op_Proj)
178 && (get_irn_mode(ab) == mode_p)
179 && (get_irn_op(aba) == op_Alloc)
181 || (/* aa is void and aba is Alloc */
182 (get_irn_op(aa) == op_Const)
183 && (get_irn_mode(aa) == mode_p)
184 && (get_Const_tarval(aa) == tarval_p_void)
185 && (get_irn_op(ab) == op_Proj)
186 && (get_irn_mode(ab) == mode_p)
187 && (get_irn_op(aba) == op_Alloc)))
189 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
193 /* printf(" # comp_val: Proj node, not optimized\n"); */
205 /* returns 1 if the a and b are pointers to different locations. */
207 different_identity (ir_node *a, ir_node *b)
209 assert (get_irn_mode (a) == mode_p
210 && get_irn_mode (b) == mode_p);
212 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
213 ir_node *a1 = get_Proj_pred (a);
214 ir_node *b1 = get_Proj_pred (b);
215 if (a1 != b1 && get_irn_op (a1) == op_Alloc
216 && get_irn_op (b1) == op_Alloc)
223 /* equivalent_node returns a node equivalent to N. It skips all nodes that
224 perform no actual computation, as, e.g., the Id nodes. It does not create
225 new nodes. It is therefore safe to free N if the node returned is not N.
226 If a node returns a Tuple we can not just skip it. If the size of the
227 in array fits, we transform n into a tuple (e.g., Div). */
229 equivalent_node (ir_node *n)
232 ir_node *a = NULL; /* to shutup gcc */
233 ir_node *b = NULL; /* to shutup gcc */
234 ir_node *c = NULL; /* to shutup gcc */
236 ins = get_irn_arity (n);
238 /* get the operands we will work on */
240 a = get_binop_left(n);
241 b = get_binop_right(n);
242 } else if (is_unop(n)) {
247 /* skip unnecessary nodes. */
248 switch (get_irn_opcode (n)) {
251 /* The Block constructor does not call optimize, therefore
252 dead blocks are not removed without an extra optimizing
253 pass through the graph. */
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));
262 } 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 */
268 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
269 if (!is_Bad(get_Block_cfgpred(n, i))) break;
271 if (i == get_Block_n_cfgpreds(n))
277 case iro_Jmp: /* GL: ??? Why not same for op_Raise?? */
278 /* unreachable code elimination */
279 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
281 /* GL: Why isn't there a case that checks whether input ot Cond is
282 constant true or false? For unreachable code elimination
283 is this done in Proj? It's not here as it generates a new node,
284 a Jmp. It is in transform_node. *
288 /* remove stuff as x+0, x*1 x&true ... constant expression evaluation */
289 case iro_Or: if (a == b) {n = a; break;}
294 /* After running compute_node there is only one constant predecessor.
295 Find this predecessors value and remember the other node: */
296 if ((tv = computed_value (a))) {
298 } else if ((tv = computed_value (b))) {
302 /* If this predecessors constant value is zero, the operation is
303 unnecessary. Remove it: */
304 if (tarval_classify (tv) == 0) {
314 /* these operations are not commutative. Test only one predecessor. */
315 if (tarval_classify (computed_value (b)) == 0) {
317 /* Test if b > #bits of a ==> return 0 / divide b by #bits
318 --> transform node? */
321 case iro_Not: /* NotNot x == x */
322 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
323 out of bounds exception if min =! max? */
324 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
325 n = get_unop_op(get_unop_op(n));
328 /* Mul is commutative and has again an other neutral element. */
329 if (tarval_classify (computed_value (a)) == 1) {
331 } else if (tarval_classify (computed_value (b)) == 1) {
336 /* Div is not commutative. */
337 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
338 /* Turn Div into a tuple (mem, bad, a) */
339 ir_node *mem = get_Div_mem(n);
340 turn_into_tuple(n, 3);
341 set_Tuple_pred(n, 0, mem);
342 set_Tuple_pred(n, 1, new_Bad());
343 set_Tuple_pred(n, 2, a);
346 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
347 teated in transform node.
348 case iro_Mod, Quot, DivMod
352 /* And has it's own neutral element */
353 else if (tarval_classify (computed_value (a)) == -1) {
355 } else if (tarval_classify (computed_value (b)) == -1) {
360 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
362 } else if (get_irn_mode(n) == mode_b) {
363 if (get_irn_op(a) == op_Conv &&
364 get_irn_mode (get_Conv_op(a)) == mode_b) {
365 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
372 /* Several optimizations:
373 - no Phi in start block.
374 - remove Id operators that are inputs to Phi
375 - fold Phi-nodes, iff they have only one predecessor except
379 ir_node *block = NULL; /* to shutup gcc */
380 ir_node *first_val = NULL; /* to shutup gcc */
381 ir_node *scnd_val = NULL; /* to shutup gcc */
383 n_preds = get_Phi_n_preds(n);
385 block = get_nodes_Block(n);
386 assert(get_irn_op (block) == op_Block);
388 /* there should be no Phi nodes in the Start region. */
389 if (block == current_ir_graph->start_block) {
394 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
395 /* GL: why not return new_Bad? */
400 /* first we test for a special case: */
401 /* Confirm is a special node fixing additional information for a
402 value that is known at a certain point. This is useful for
403 dataflow analysis. */
405 ir_node *a = follow_Id (get_Phi_pred(n, 0));
406 ir_node *b = follow_Id (get_Phi_pred(n, 1));
407 if ( (get_irn_op(a) == op_Confirm)
408 && (get_irn_op(b) == op_Confirm)
409 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
410 && (get_irn_n(a, 1) == get_irn_n (b, 1))
411 && (a->data.num == (~b->data.num & irpn_True) )) {
412 n = follow_Id (get_irn_n(a, 0));
418 /* Find first non-self-referencing input */
419 for (i = 0; i < n_preds; ++i) {
420 first_val = follow_Id(get_Phi_pred(n, i));
422 set_Phi_pred(n, i, first_val);
423 if ( (first_val != n) /* not self pointer */
424 && (get_irn_op(first_val) != op_Bad) /* value not dead */
425 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
426 break; /* then found first value. */
430 /* A totally Bad or self-referencing Phi */
431 if (i > n_preds) { n = new_Bad(); break; }
435 /* follow_Id () for rest of inputs, determine if any of these
436 are non-self-referencing */
437 while (++i < n_preds) {
438 scnd_val = follow_Id(get_Phi_pred(n, i));
440 set_Phi_pred(n, i, scnd_val);
442 && (scnd_val != first_val)
443 && (get_irn_op(scnd_val) != op_Bad)
444 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
449 /* Fold, if no multiple distinct non-self-referencing inputs */
453 /* skip the remaining Ids. */
454 while (++i < n_preds)
455 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
462 a = skip_Proj(get_Load_mem(n));
463 b = skip_Proj(get_Load_ptr(n));
465 if (get_irn_op(a) == op_Store) {
466 if ( different_identity (b, get_Store_ptr(a))) {
467 /* load and store use different pointers, therefore load
468 needs not take store's memory but the state before. */
469 set_Load_mem (n, get_Store_mem(a));
470 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
476 /* remove unnecessary store. */
478 a = skip_Proj(get_Store_mem(n));
479 b = get_Store_ptr(n);
480 c = skip_Proj(get_Store_value(n));
482 if (get_irn_op(a) == op_Store
483 && get_Store_ptr(a) == b
484 && skip_Proj(get_Store_value(a)) == c) {
485 /* We have twice exactly the same store -- a write after write. */
487 } else if (get_irn_op(c) == op_Load
488 && (a == c || skip_Proj(get_Load_mem(c)) == a)
489 && get_Load_ptr(c) == b )
490 /* !!!??? and a cryptic test */ {
491 /* We just loaded the value from the same memory, i.e., the store
492 doesn't change the memory -- a write after read. */
493 turn_into_tuple(n, 2);
494 set_Tuple_pred(n, 0, a);
495 set_Tuple_pred(n, 1, new_Bad());
502 a = get_Proj_pred(n);
504 if ( get_irn_op(a) == op_Tuple) {
505 /* Remove the Tuple/Proj combination. */
506 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
507 n = get_Tuple_pred(a, get_Proj_proj(n));
509 assert(0); /* This should not happen?! (GL added this assert) */
512 } else if (get_irn_mode(n) == mode_X &&
513 is_Bad(get_nodes_Block(n))) {
514 /* Remove dead control flow. */
528 } /* end equivalent_node() */
532 /* tries several [inplace] [optimizing] transformations and returns a
533 equivalent node. The difference to equivalent_node is that these
534 transformations _do_ generate new nodes, and thus the old node must
535 not be freed even if the equivalent node isn't the old one. */
537 transform_node (ir_node *n)
543 switch (get_irn_opcode(n)) {
546 ir_mode *mode = get_irn_mode(a);
548 a = get_DivMod_left(n);
549 b = get_DivMod_right(n);
551 if (!( mode_is_int(get_irn_mode(a))
552 && mode_is_int(get_irn_mode(b))))
556 a = new_Const (mode, tarval_from_long (mode, 1));
557 b = new_Const (mode, tarval_from_long (mode, 0));
564 if (tarval_classify(tb) == 1) {
565 b = new_Const (mode, tarval_from_long (mode, 0));
569 resa = tarval_div (ta, tb);
570 if (!resa) break; /* Causes exception!!! Model by replacing through
571 Jmp for X result!? */
572 resb = tarval_mod (ta, tb);
573 if (!resb) break; /* Causes exception! */
574 a = new_Const (mode, resa);
575 b = new_Const (mode, resb);
578 } else if (tarval_classify (ta) == 0) {
583 if (evaluated) { /* replace by tuple */
584 ir_node *mem = get_DivMod_mem(n);
585 turn_into_tuple(n, 4);
586 set_Tuple_pred(n, 0, mem);
587 set_Tuple_pred(n, 1, new_Bad());
588 set_Tuple_pred(n, 2, a);
589 set_Tuple_pred(n, 3, b);
595 /* Replace the Cond by a Jmp if it branches on a constant
599 a = get_Cond_selector(n);
602 if (ta && (get_irn_mode(a) == mode_b)) {
603 /* It's a boolean Cond, branching on a boolean constant.
604 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
605 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
606 turn_into_tuple(n, 2);
607 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
608 set_Tuple_pred(n, 0, new_Bad());
609 set_Tuple_pred(n, 1, jmp);
611 set_Tuple_pred(n, 0, jmp);
612 set_Tuple_pred(n, 1, new_Bad());
614 } else if (ta && (get_irn_mode(a) == mode_I)) {
615 /* I don't want to allow Tuples smaller than the biggest Proj.
616 Also this tuple might get really big...
617 I generate the Jmp here, and remember it in link. Link is used
618 when optimizing Proj. */
619 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
620 } else if ( ((get_irn_op(get_Cond_selector(n)) == op_Eor)
621 /* || (get_irn_op(get_Cond_selector(a)) == op_Not)*/)
622 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
623 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
624 /* The Eor is a negate. Generate a new Cond without the negate,
625 simulate the negate 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 */
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)) == iro_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);
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)) == iro_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 not optimize return n */
890 printf(" attention: empty node!!! \n");
894 /* constant expression evaluation / constant folding */
895 if (get_opt_constant_folding()) {
896 /* constants can not be evaluated */
897 if (get_irn_op(n) != op_Const) {
898 /* try to evaluate */
899 tv = computed_value (n);
901 /* evaluation was succesful -- replace the node. */
902 obstack_free (current_ir_graph->obst, n);
903 return new_Const (get_tv_mode (tv), tv);
904 /* xprintf("* optimize: computed node %I\n", n->op->name); */
908 /* remove unnecessary nodes */
909 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
910 n = equivalent_node (n);
912 /** common subexpression elimination **/
913 /* Checks whether n is already available. */
914 /* The block input is used to distinguish different subexpressions. Right
915 now all nodes are pinned to blocks, i.e., the cse only finds common
916 subexpressions within a block. */
919 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. */
928 /* Some more constant expression evaluation. */
929 if (get_opt_constant_folding())
930 n = transform_node (n);
933 /* Remove nodes with dead (Bad) input. */
935 /* Now we can verify the node, as it has no dead inputs any more. */
938 /* Now we have a legal, useful node. Enter it in hash table for cse */
940 /* aborts ??! set/pset can not handle several hash tables??!
941 No, suddenly it works. */
942 n = identify_remember (current_ir_graph->value_table, n);
945 #if 0 /* GL: what's the use of this?? */
946 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
947 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
948 pdeq_putr (current_ir_graph->keep.living, n);
956 /* These optimizations never deallocate nodes. This can cause dead
957 nodes lying on the obstack. Remove these by a dead node elimination,
958 i.e., a copying garbage collection. */
960 optimize_in_place (ir_node *n)
966 /* if not optimize return n */
968 /* Here this is possible. Why? */
972 /* constant expression evaluation / constant folding */
973 if (get_opt_constant_folding()) {
974 /* constants can not be evaluated */
975 if (get_irn_op(n) != op_Const) {
976 /* try to evaluate */
977 tv = computed_value (n);
979 /* evaluation was succesful -- replace the node. */
980 return new_Const (get_tv_mode (tv), tv);
981 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
985 /* remove unnecessary nodes */
986 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
987 n = equivalent_node (n);
989 /** common subexpression elimination **/
990 /* Checks whether n is already available. */
991 /* The block input is used to distinguish different subexpressions. Right
992 now all nodes are pinned to blocks, i.e., the cse only finds common
993 subexpressions within a block. */
996 n = identify (current_ir_graph->value_table, n);
998 /* identify found a cse, so deallocate the old node. */
1000 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1004 /* Some more constant expression evaluation. */
1005 if (get_opt_constant_folding())
1006 n = transform_node (n);
1009 /* Remove nodes with dead (Bad) input. */
1011 /* Now we can verify the node, as it has no dead inputs any more. */
1014 /* Now we have a legal, useful node. Enter it in hash table for cse */
1015 if (get_opt_cse()) {
1016 /* aborts ??! set/pset can not handle several hash tables??!
1017 No, suddenly it works. */
1018 n = identify_remember (current_ir_graph->value_table, n);