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 /* Trivial inlineable routine for copy propagation.
16 Does follow Ids, needed to optimize inlined code. */
17 static inline ir_node *
18 follow_Id (ir_node *n)
20 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
25 static inline tarval *
28 if ((n != NULL) && (get_irn_op(n) == op_Const))
29 return get_Const_tarval(n);
35 /* if n can be computed, return the value, else NULL. Performs
36 constant Folding. GL: Only if n is arithmetic operator? */
38 computed_value (ir_node *n)
42 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
43 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
47 /* get the operands we will work on for simple cases. */
49 a = get_binop_left(n);
50 b = get_binop_right(n);
51 } else if (is_unop(n)) {
55 /* if the operands are constants, get the target value, else set it NULL.
56 (a and b may be NULL if we treat a node that is no computation.) */
60 /* Perform the constant evaluation / computation. */
61 switch (get_irn_opcode(n)) {
63 res = get_Const_tarval(n);
65 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
66 && (get_irn_mode(a) != mode_p)) {
67 res = tarval_add (ta, tb);
71 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
72 && (get_irn_mode(a) != mode_p)) {
73 res = tarval_sub (ta, tb);
75 res = tarval_mode_null [get_irn_modecode (n)];
79 if (ta && mode_is_float(get_irn_mode(a)))
80 res = /*tarval_minus (ta);*/ res;
83 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
84 res = tarval_mul (ta, tb);
86 /* calls computed_value recursive and returns the 0 with proper
87 mode. Why is this an extra case? */
89 if ( (tarval_classify ((v = computed_value (a))) == 0)
90 || (tarval_classify ((v = computed_value (b))) == 0)) {
97 res = /*tarval_abs (ta);*/ res;
98 /* allowded or problems with max/min ?? */
102 res = tarval_and (ta, tb);
105 if ( (tarval_classify ((v = computed_value (a))) == 0)
106 || (tarval_classify ((v = computed_value (b))) == 0)) {
113 res = tarval_or (ta, tb);
116 if ( (tarval_classify ((v = computed_value (a))) == -1)
117 || (tarval_classify ((v = computed_value (b))) == -1)) {
122 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
123 case iro_Not: if(ta) { /*res = tarval_not (ta)*/; } break;
124 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
125 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
126 case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
127 case iro_Rot: if(ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
128 case iro_Conv: if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
134 a = get_Proj_pred(n);
135 /* Optimize Cmp nodes.
136 This performs a first step of unreachable code elimination.
137 Proj can not be computed, but folding a Cmp above the Proj here is
138 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
140 There are several case where we can evaluate a Cmp node:
141 1. The nodes compared are both the same. If we compare for
142 equal, this will return true, else it will return false.
143 This step relies on cse.
144 2. The predecessors of Cmp are target values. We can evaluate
146 3. The predecessors are Allocs or void* constants. Allocs never
147 return NULL, they raise an exception. Therefore we can predict
149 if (get_irn_op(a) == op_Cmp) {
150 aa = get_Cmp_left(a);
151 ab = get_Cmp_right(a);
152 if (aa == ab) { /* 1.: */
153 /* This is a tric with the bits used for encoding the Cmp
154 Proj numbers, the following statement is not the same:
155 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
156 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
158 tarval *taa = computed_value (aa);
159 tarval *tab = computed_value (ab);
160 if (taa && tab) { /* 2.: */
161 /* strange checks... */
162 ir_pncmp flags = tarval_comp (taa, tab);
163 if (flags != irpn_False) {
164 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
166 } else { /* check for 3.: */
167 ir_node *aaa = skip_nop(skip_Proj(aa));
168 ir_node *aba = skip_nop(skip_Proj(ab));
169 if ( ( (/* aa is ProjP and aaa is Alloc */
170 (get_irn_op(aa) == op_Proj)
171 && (get_irn_mode(aa) == mode_p)
172 && (get_irn_op(aaa) == op_Alloc))
173 && ( (/* ab is constant void */
174 (get_irn_op(ab) == op_Const)
175 && (get_irn_mode(ab) == mode_p)
176 && (get_Const_tarval(ab) == tarval_p_void))
177 || (/* ab is other Alloc */
178 (get_irn_op(ab) == op_Proj)
179 && (get_irn_mode(ab) == mode_p)
180 && (get_irn_op(aba) == op_Alloc)
182 || (/* aa is void and aba is Alloc */
183 (get_irn_op(aa) == op_Const)
184 && (get_irn_mode(aa) == mode_p)
185 && (get_Const_tarval(aa) == tarval_p_void)
186 && (get_irn_op(ab) == op_Proj)
187 && (get_irn_mode(ab) == mode_p)
188 && (get_irn_op(aba) == op_Alloc)))
190 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
194 /* printf(" # comp_val: Proj node, not optimized\n"); */
206 /* returns 1 if the a and b are pointers to different locations. */
208 different_identity (ir_node *a, ir_node *b)
210 assert (get_irn_mode (a) == mode_p
211 && get_irn_mode (b) == mode_p);
213 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
214 ir_node *a1 = get_Proj_pred (a);
215 ir_node *b1 = get_Proj_pred (b);
216 if (a1 != b1 && get_irn_op (a1) == op_Alloc
217 && get_irn_op (b1) == op_Alloc)
224 /* equivalent_node returns a node equivalent to N. It skips all nodes that
225 perform no actual computation, as, e.g., the Id nodes. It does not create
226 new nodes. It is therefore safe to free N if the node returned is not N.
227 If a node returns a Tuple we can not just skip it. If the size of the
228 in array fits, we transform n into a tuple (e.g., Div). */
230 equivalent_node (ir_node *n)
233 ir_node *a = NULL; /* to shutup gcc */
234 ir_node *b = NULL; /* to shutup gcc */
235 ir_node *c = NULL; /* to shutup gcc */
237 ins = get_irn_arity (n);
239 /* get the operands we will work on */
241 a = get_binop_left(n);
242 b = get_binop_right(n);
243 } else if (is_unop(n)) {
248 /* skip unnecessary nodes. */
249 switch (get_irn_opcode (n)) {
252 /* The Block constructor does not call optimize, therefore
253 dead blocks are not removed without an extra optimizing
254 pass through the graph. */
255 assert(get_Block_matured(n));
257 /* a single entry Region following a single exit Region can be merged */
258 /* !!! Beware, all Phi-nodes of n must have been optimized away.
259 This is true, as the block is matured before optimize is called. */
260 if (get_Block_n_cfgpreds(n) == 1
261 && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
262 n = get_nodes_Block(get_Block_cfgpred(n, 0));
263 } else if (n != current_ir_graph->start_block) {
266 /* If all inputs are dead, this block is dead too, except if it is
267 the start block. This is a step of unreachable code elimination */
269 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
270 if (!is_Bad(get_Block_cfgpred(n, i))) break;
272 if (i == get_Block_n_cfgpreds(n))
278 case iro_Jmp: /* GL: ??? Why not same for op_Raise?? */
279 /* unreachable code elimination */
280 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
282 /* GL: Why isn't there a case that checks whether input ot Cond is
283 constant true or false? For unreachable code elimination
284 is this done in Proj? It's not here as it generates a new node,
285 a Jmp. It is in transform_node. *
289 /* remove stuff as x+0, x*1 x&true ... constant expression evaluation */
290 case iro_Or: if (a == b) {n = a; break;}
295 /* After running compute_node there is only one constant predecessor.
296 Find this predecessors value and remember the other node: */
297 if ((tv = computed_value (a))) {
299 } else if ((tv = computed_value (b))) {
303 /* If this predecessors constant value is zero, the operation is
304 unnecessary. Remove it: */
305 if (tarval_classify (tv) == 0) {
315 /* these operations are not commutative. Test only one predecessor. */
316 if (tarval_classify (computed_value (b)) == 0) {
318 /* Test if b > #bits of a ==> return 0 / divide b by #bits
319 --> transform node? */
322 case iro_Not: /* NotNot x == x */
323 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
324 out of bounds exception if min =! max? */
325 if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
326 n = get_unop_op(get_unop_op(n));
329 /* Mul is commutative and has again an other neutral element. */
330 if (tarval_classify (computed_value (a)) == 1) {
332 } else if (tarval_classify (computed_value (b)) == 1) {
337 /* Div is not commutative. */
338 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
339 /* Turn Div into a tuple (mem, bad, a) */
340 ir_node *mem = get_Div_mem(n);
341 turn_into_tuple(n, 3);
342 set_Tuple_pred(n, 0, mem);
343 set_Tuple_pred(n, 1, new_Bad());
344 set_Tuple_pred(n, 2, a);
347 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
348 teated in transform node.
349 case iro_Mod, Quot, DivMod
353 /* And has it's own neutral element */
354 else if (tarval_classify (computed_value (a)) == -1) {
356 } else if (tarval_classify (computed_value (b)) == -1) {
361 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
363 } else if (get_irn_mode(n) == mode_b) {
364 if (get_irn_op(a) == op_Conv &&
365 get_irn_mode (get_Conv_op(a)) == mode_b) {
366 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */
373 /* Several optimizations:
374 - no Phi in start block.
375 - remove Id operators that are inputs to Phi
376 - fold Phi-nodes, iff they have only one predecessor except
380 ir_node *block = NULL; /* to shutup gcc */
381 ir_node *first_val = NULL; /* to shutup gcc */
382 ir_node *scnd_val = NULL; /* to shutup gcc */
384 n_preds = get_Phi_n_preds(n);
386 block = get_nodes_Block(n);
387 assert(get_irn_op (block) == op_Block);
389 /* there should be no Phi nodes in the Start region. */
390 if (block == current_ir_graph->start_block) {
395 if (n_preds == 0) { /* Phi of dead Region without predecessors. */
396 /* GL: why not return new_Bad? */
401 /* first we test for a special case: */
402 /* Confirm is a special node fixing additional information for a
403 value that is known at a certain point. This is useful for
404 dataflow analysis. */
406 ir_node *a = follow_Id (get_Phi_pred(n, 0));
407 ir_node *b = follow_Id (get_Phi_pred(n, 1));
408 if ( (get_irn_op(a) == op_Confirm)
409 && (get_irn_op(b) == op_Confirm)
410 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
411 && (get_irn_n(a, 1) == get_irn_n (b, 1))
412 && (a->data.num == (~b->data.num & irpn_True) )) {
413 n = follow_Id (get_irn_n(a, 0));
419 /* Find first non-self-referencing input */
420 for (i = 0; i < n_preds; ++i) {
421 first_val = follow_Id(get_Phi_pred(n, i));
423 set_Phi_pred(n, i, first_val);
424 if ( (first_val != n) /* not self pointer */
425 && (get_irn_op(first_val) != op_Bad) /* value not dead */
426 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
427 break; /* then found first value. */
431 /* A totally Bad or self-referencing Phi */
432 if (i > n_preds) { n = new_Bad(); break; }
436 /* follow_Id () for rest of inputs, determine if any of these
437 are non-self-referencing */
438 while (++i < n_preds) {
439 scnd_val = follow_Id(get_Phi_pred(n, i));
441 set_Phi_pred(n, i, scnd_val);
443 && (scnd_val != first_val)
444 && (get_irn_op(scnd_val) != op_Bad)
445 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
450 /* Fold, if no multiple distinct non-self-referencing inputs */
454 /* skip the remaining Ids. */
455 while (++i < n_preds)
456 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
463 a = skip_Proj(get_Load_mem(n));
464 b = skip_Proj(get_Load_ptr(n));
466 if (get_irn_op(a) == op_Store) {
467 if ( different_identity (b, get_Store_ptr(a))) {
468 /* load and store use different pointers, therefore load
469 needs not take store's memory but the state before. */
470 set_Load_mem (n, get_Store_mem(a));
471 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
477 /* remove unnecessary store. */
479 a = skip_Proj(get_Store_mem(n));
480 b = get_Store_ptr(n);
481 c = skip_Proj(get_Store_value(n));
483 if (get_irn_op(a) == op_Store
484 && get_Store_ptr(a) == b
485 && skip_Proj(get_Store_value(a)) == c) {
486 /* We have twice exactly the same store -- a write after write. */
488 } else if (get_irn_op(c) == op_Load
489 && (a == c || skip_Proj(get_Load_mem(c)) == a)
490 && get_Load_ptr(c) == b )
491 /* !!!??? and a cryptic test */ {
492 /* We just loaded the value from the same memory, i.e., the store
493 doesn't change the memory -- a write after read. */
494 turn_into_tuple(n, 2);
495 set_Tuple_pred(n, 0, a);
496 set_Tuple_pred(n, 1, new_Bad());
503 a = get_Proj_pred(n);
505 if ( get_irn_op(a) == op_Tuple) {
506 /* Remove the Tuple/Proj combination. */
507 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
508 n = get_Tuple_pred(a, get_Proj_proj(n));
510 assert(0); /* This should not happen?! (GL added this assert) */
513 } else if (get_irn_mode(n) == mode_X &&
514 is_Bad(get_nodes_Block(n))) {
515 /* Remove dead control flow. */
529 } /* end equivalent_node() */
533 /* tries several [inplace] [optimizing] transformations and returns a
534 equivalent node. The difference to equivalent_node is that these
535 transformations _do_ generate new nodes, and thus the old node must
536 not be freed even if the equivalent node isn't the old one. */
538 transform_node (ir_node *n)
544 switch (get_irn_opcode(n)) {
547 ir_mode *mode = get_irn_mode(a);
549 a = get_DivMod_left(n);
550 b = get_DivMod_right(n);
552 if (!( mode_is_int(get_irn_mode(a))
553 && mode_is_int(get_irn_mode(b))))
557 a = new_Const (mode, tarval_from_long (mode, 1));
558 b = new_Const (mode, tarval_from_long (mode, 0));
565 if (tarval_classify(tb) == 1) {
566 b = new_Const (mode, tarval_from_long (mode, 0));
570 resa = tarval_div (ta, tb);
571 if (!resa) break; /* Causes exception!!! Model by replacing through
572 Jmp for X result!? */
573 resb = tarval_mod (ta, tb);
574 if (!resb) break; /* Causes exception! */
575 a = new_Const (mode, resa);
576 b = new_Const (mode, resb);
579 } else if (tarval_classify (ta) == 0) {
584 if (evaluated) { /* replace by tuple */
585 ir_node *mem = get_DivMod_mem(n);
586 turn_into_tuple(n, 4);
587 set_Tuple_pred(n, 0, mem);
588 set_Tuple_pred(n, 1, new_Bad());
589 set_Tuple_pred(n, 2, a);
590 set_Tuple_pred(n, 3, b);
596 /* Replace the Cond by a Jmp if it branches on a constant
600 a = get_Cond_selector(n);
603 if (ta && (get_irn_mode(a) == mode_b)) {
604 /* It's a boolean Cond, branching on a boolean constant.
605 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
606 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
607 turn_into_tuple(n, 2);
608 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
609 set_Tuple_pred(n, 0, new_Bad());
610 set_Tuple_pred(n, 1, jmp);
612 set_Tuple_pred(n, 0, jmp);
613 set_Tuple_pred(n, 1, new_Bad());
615 } else if (ta && (get_irn_mode(a) == mode_I)) {
616 /* I don't want to allow Tuples smaller than the biggest Proj.
617 Also this tuple might get really big...
618 I generate the Jmp here, and remember it in link. Link is used
619 when optimizing Proj. */
620 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
621 } else if ( ((get_irn_op(get_Cond_selector(n)) == op_Eor)
622 /* || (get_irn_op(get_Cond_selector(a)) == op_Not)*/)
623 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
624 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
625 /* The Eor is a negate. Generate a new Cond without the negate,
626 simulate the negate by exchanging the results. */
627 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
634 a = get_Proj_pred(n);
636 if ( (get_irn_op(a) == op_Cond)
638 && get_irn_op(get_irn_link(a)) == op_Cond) {
639 /* Use the better Cond if the Proj projs from a Cond which get's
640 its result from an Eor/Not. */
641 assert ( ((get_irn_op(get_Cond_selector(a)) == op_Eor)
642 /* || (get_irn_op(get_Cond_selector(a)) == op_Not)*/)
643 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
644 && (get_irn_op(get_irn_link(a)) == op_Cond)
645 && (get_Cond_selector(get_irn_link(a)) ==
646 get_Eor_left(get_Cond_selector(a))));
647 set_Proj_pred(n, get_irn_link(a));
648 if (get_Proj_proj(n) == 0)
652 } else if ( (get_irn_op(a) == op_Cond)
653 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
655 /* The Cond is a Switch on a Constant */
656 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
657 /* The always taken branch, reuse the existing Jmp. */
658 if (!get_irn_link(a)) /* well, if it exists ;-> */
659 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
660 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
663 /* a never taken branch */
671 b = get_Eor_right(n);
673 if ( (get_irn_mode(n) == mode_b)
674 && (get_irn_op(a) == op_Proj)
675 && (get_irn_mode(a) == mode_b)
676 && (tarval_classify (computed_value (b)) == 1)
677 && (get_irn_op(get_Proj_pred(a)) == iro_Cmp))
678 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
679 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
680 mode_b, get_negated_pnc(get_Proj_proj(a)));
681 else if ( (get_irn_mode(n) == mode_b)
682 && (tarval_classify (computed_value (b)) == 1))
683 /* The Eor is a Not. Replace it by a Not. */
684 /* ????!!!Extend to bitfield 1111111. */
685 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
691 if ( (get_irn_mode(n) == mode_b)
692 && (get_irn_op(a) == op_Proj)
693 && (get_irn_mode(a) == mode_b)
694 && (get_irn_op(get_Proj_pred(a)) == iro_Cmp))
695 /* We negate a Cmp. The Cmp has the negated result anyways! */
696 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
697 mode_b, get_negated_pnc(get_Proj_proj(a)));
705 /***************** Common Subexpression Elimination *****************/
707 /* Compare function for two nodes in the hash table. Gets two */
708 /* nodes as parameters. */
709 /* @@@ a+b != b+a ? */
711 vt_cmp (const void *elt, const void *key)
719 if (a == b) return 0;
721 if ((get_irn_op(a) != get_irn_op(b)) ||
722 (get_irn_mode(a) != get_irn_mode(b))) return 1;
724 /* compare if a's in and b's in are equal */
725 /* GL: we optimize only nodes with in arrays of fixed sizes.
726 if (get_irn_arity (a) != -2) {
727 ins = get_irn_arity (a);
728 if (ins != get_irn_arity (b)) return 1;
729 ain = get_irn_in (a);
730 bin = get_irn_in (b);
733 if (get_irn_arity (a) != get_irn_arity(b))
736 /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
737 /* do if (*ain++ != *bin++) return 1; while (ins--); */
738 for (i = -1; i < get_irn_arity(a); i++)
739 if (get_irn_n(a, i) != get_irn_n(b, i))
743 switch (get_irn_opcode(a)) {
745 return get_irn_const_attr (a) != get_irn_const_attr (b);
747 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
749 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
750 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
752 return (get_irn_free_attr(a) != get_irn_free_attr(b));
754 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
755 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
757 return (get_irn_call_attr(a)->kind != get_irn_call_attr(b)->kind)
758 || (get_irn_call_attr(a)->arity != get_irn_call_attr(b)->arity);
760 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
761 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
762 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
763 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
764 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
765 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
767 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
775 ir_node_hash (ir_node *node)
780 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
781 h = get_irn_arity(node);
783 /* consider all in nodes... except the block. */
784 for (i = 0; i < get_irn_arity(node); i++) {
785 h = 9*h + (unsigned long)get_irn_n(node, i);
789 h = 9*h + (unsigned long) get_irn_mode (node);
791 h = 9*h + (unsigned long) get_irn_op (node);
797 new_identities (void)
799 return new_pset (vt_cmp, TUNE_NIR_NODES);
803 del_identities (pset *value_table)
805 del_pset (value_table);
808 /* Return the canonical node computing the same value as n.
809 Looks up the node in a hash table. */
810 static inline ir_node *
811 identify (pset *value_table, ir_node *n)
815 if (!value_table) return n;
817 switch (get_irn_opcode (n)) {
824 /* for commutative operators perform a OP b == b OP a */
825 if (get_binop_left(n) > get_binop_right(n)) {
826 ir_node *h = get_binop_left(n);
827 set_binop_left(n, get_binop_right(n));
828 set_binop_right(n, h);
834 o = pset_find (value_table, n, ir_node_hash (n));
840 /* Return the canonical node computing the same value as n.
841 Looks up the node in a hash table, enters it in the table
842 if it isn't there yet. */
844 identify_remember (pset *value_table, ir_node *node)
848 if (!value_table) return node;
850 /* lookup or insert in hash table with given hash key. */
851 o = pset_insert (value_table, node, ir_node_hash (node));
853 if (o == node) return node;
858 /* garbage in, garbage out. If a node has a dead input, i.e., the
859 Bad node is input to the node, return the Bad node. */
860 static inline ir_node *
864 ir_op* op = get_irn_op(node);
866 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
867 blocks predecessors is dead. */
868 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
869 for (i = -1; i < get_irn_arity(node); i++) {
870 if (is_Bad(get_irn_n(node, i))) {
880 /* These optimizations deallocate nodes from the obstack.
881 It can only be called if it is guaranteed that no other nodes
882 reference this one, i.e., right after construction of a node. */
884 optimize (ir_node *n)
889 /* if not optimize return n */
891 printf(" attention: empty node!!! \n");
895 /* constant expression evaluation / constant folding */
896 if (get_opt_constant_folding()) {
897 /* constants can not be evaluated */
898 if (get_irn_op(n) != op_Const) {
899 /* try to evaluate */
900 tv = computed_value (n);
902 /* evaluation was succesful -- replace the node. */
903 obstack_free (current_ir_graph->obst, n);
904 return new_Const (get_tv_mode (tv), tv);
905 /* xprintf("* optimize: computed node %I\n", n->op->name); */
909 /* remove unnecessary nodes */
910 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
911 n = equivalent_node (n);
913 /** common subexpression elimination **/
914 /* Checks whether n is already available. */
915 /* The block input is used to distinguish different subexpressions. Right
916 now all nodes are pinned to blocks, i.e., the cse only finds common
917 subexpressions within a block. */
920 n = identify (current_ir_graph->value_table, n);
922 /* identify found a cse, so deallocate the old node. */
924 obstack_free (current_ir_graph->obst, old_n);
925 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
929 /* Some more constant expression evaluation. */
930 if (get_opt_constant_folding())
931 n = transform_node (n);
934 /* Remove nodes with dead (Bad) input. */
936 /* Now we can verify the node, as it has no dead inputs any more. */
939 /* Now we have a legal, useful node. Enter it in hash table for cse */
941 /* aborts ??! set/pset can not handle several hash tables??!
942 No, suddenly it works. */
943 n = identify_remember (current_ir_graph->value_table, n);
946 #if 0 /* GL: what's the use of this?? */
947 if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
948 assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
949 pdeq_putr (current_ir_graph->keep.living, n);
957 /* These optimizations never deallocate nodes. This can cause dead
958 nodes lying on the obstack. Remove these by a dead node elimination,
959 i.e., a copying garbage collection. */
961 optimize_in_place (ir_node *n)
967 /* if not optimize return n */
969 /* Here this is possible. Why? */
973 /* constant expression evaluation / constant folding */
974 if (get_opt_constant_folding()) {
975 /* constants can not be evaluated */
976 if (get_irn_op(n) != op_Const) {
977 /* try to evaluate */
978 tv = computed_value (n);
980 /* evaluation was succesful -- replace the node. */
981 return new_Const (get_tv_mode (tv), tv);
982 /* xprintf("* optimize: computed node %I\n", n->op->name);*/
986 /* remove unnecessary nodes */
987 if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
988 n = equivalent_node (n);
990 /** common subexpression elimination **/
991 /* Checks whether n is already available. */
992 /* The block input is used to distinguish different subexpressions. Right
993 now all nodes are pinned to blocks, i.e., the cse only finds common
994 subexpressions within a block. */
997 n = identify (current_ir_graph->value_table, n);
999 /* identify found a cse, so deallocate the old node. */
1001 /* The AmRoq fiasco returns n here. Martin's version doesn't. */
1005 /* Some more constant expression evaluation. */
1006 if (get_opt_constant_folding())
1007 n = transform_node (n);
1010 /* Remove nodes with dead (Bad) input. */
1012 /* Now we can verify the node, as it has no dead inputs any more. */
1015 /* Now we have a legal, useful node. Enter it in hash table for cse */
1016 if (get_opt_cse()) {
1017 /* aborts ??! set/pset can not handle several hash tables??!
1018 No, suddenly it works. */
1019 n = identify_remember (current_ir_graph->value_table, n);