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 # include "irnode_t.h"
16 # include "irgraph_t.h"
23 # include "dbginfo_t.h"
24 # include "iropt_dbg.c"
26 /* Make types visible to allow most efficient access */
27 # include "entity_t.h"
29 /* Trivial inlineable routine for copy propagation.
30 Does follow Ids, needed to optimize inlined code. */
31 static inline ir_node *
32 follow_Id (ir_node *n)
34 while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
38 static inline tarval *
41 if ((n != NULL) && (get_irn_op(n) == op_Const))
42 return get_Const_tarval(n);
47 /* if n can be computed, return the value, else NULL. Performs
48 constant folding. GL: Only if n is arithmetic operator? */
50 computed_value (ir_node *n)
54 ir_node *a = NULL, *b = NULL; /* initialized to shut up gcc */
55 tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
59 /* get the operands we will work on for simple cases. */
61 a = get_binop_left(n);
62 b = get_binop_right(n);
63 } else if (is_unop(n)) {
67 /* if the operands are constants, get the target value, else set it NULL.
68 (a and b may be NULL if we treat a node that is no computation.) */
72 /* Perform the constant evaluation / computation. */
73 switch (get_irn_opcode(n)) {
75 res = get_Const_tarval(n);
78 if ((get_SymConst_kind(n) == size) &&
79 (get_type_state(get_SymConst_type(n))) == layout_fixed)
80 res = tarval_from_long (mode_i, get_type_size(get_SymConst_type(n)));
83 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
84 && (get_irn_mode(a) != mode_p)) {
85 res = tarval_add (ta, tb);
89 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
90 && (get_irn_mode(a) != mode_p)) {
91 res = tarval_sub (ta, tb);
93 res = tarval_mode_null [get_irn_modecode (n)];
97 if (ta && mode_is_float(get_irn_mode(a)))
98 res = tarval_neg (ta);
101 if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
102 res = tarval_mul (ta, tb);
104 /* a*0 = 0 or 0*b = 0:
105 calls computed_value recursive and returns the 0 with proper
108 if ( (tarval_classify ((v = computed_value (a))) == 0)
109 || (tarval_classify ((v = computed_value (b))) == 0)) {
115 /* This was missing in original implementation. Why? */
116 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
117 if (tarval_classify(tb) == 0) {res = NULL; break;}
118 res = tarval_quo(ta, tb);
122 /* This was missing in original implementation. Why? */
123 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
124 if (tarval_classify(tb) == 0) {res = NULL; break;}
125 res = tarval_div(ta, tb);
129 /* This was missing in original implementation. Why? */
130 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
131 if (tarval_classify(tb) == 0) {res = NULL; break;}
132 res = tarval_mod(ta, tb);
135 /* for iro_DivMod see iro_Proj */
138 res = tarval_abs (ta);
142 res = tarval_and (ta, tb);
145 if ( (tarval_classify ((v = computed_value (a))) == 0)
146 || (tarval_classify ((v = computed_value (b))) == 0)) {
153 res = tarval_or (ta, tb);
156 if ( (tarval_classify ((v = computed_value (a))) == -1)
157 || (tarval_classify ((v = computed_value (b))) == -1)) {
162 case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
163 case iro_Not: if (ta) { res = tarval_neg (ta); } break;
164 case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
165 /* tarval_shr is faulty !! */
166 case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
167 case iro_Shrs:if (ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
168 case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
169 case iro_Conv:if (ta) { res = tarval_convert_to (ta, get_irn_mode (n)); }
171 case iro_Proj: /* iro_Cmp */
175 a = get_Proj_pred(n);
176 /* Optimize Cmp nodes.
177 This performs a first step of unreachable code elimination.
178 Proj can not be computed, but folding a Cmp above the Proj here is
179 not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
181 There are several case where we can evaluate a Cmp node:
182 1. The nodes compared are both the same. If we compare for
183 equal, this will return true, else it will return false.
184 This step relies on cse.
185 2. The predecessors of Cmp are target values. We can evaluate
187 3. The predecessors are Allocs or void* constants. Allocs never
188 return NULL, they raise an exception. Therefore we can predict
190 if (get_irn_op(a) == op_Cmp) {
191 aa = get_Cmp_left(a);
192 ab = get_Cmp_right(a);
193 if (aa == ab) { /* 1.: */
194 /* This is a tric with the bits used for encoding the Cmp
195 Proj numbers, the following statement is not the same:
196 res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)): */
197 res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
199 tarval *taa = computed_value (aa);
200 tarval *tab = computed_value (ab);
201 if (taa && tab) { /* 2.: */
202 /* strange checks... */
203 ir_pncmp flags = tarval_comp (taa, tab);
204 if (flags != irpn_False) {
205 res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
207 } else { /* check for 3.: */
208 ir_node *aaa = skip_nop(skip_Proj(aa));
209 ir_node *aba = skip_nop(skip_Proj(ab));
210 if ( ( (/* aa is ProjP and aaa is Alloc */
211 (get_irn_op(aa) == op_Proj)
212 && (get_irn_mode(aa) == mode_p)
213 && (get_irn_op(aaa) == op_Alloc))
214 && ( (/* ab is constant void */
215 (get_irn_op(ab) == op_Const)
216 && (get_irn_mode(ab) == mode_p)
217 && (get_Const_tarval(ab) == tarval_p_void))
218 || (/* ab is other Alloc */
219 (get_irn_op(ab) == op_Proj)
220 && (get_irn_mode(ab) == mode_p)
221 && (get_irn_op(aba) == op_Alloc)
223 || (/* aa is void and aba is Alloc */
224 (get_irn_op(aa) == op_Const)
225 && (get_irn_mode(aa) == mode_p)
226 && (get_Const_tarval(aa) == tarval_p_void)
227 && (get_irn_op(ab) == op_Proj)
228 && (get_irn_mode(ab) == mode_p)
229 && (get_irn_op(aba) == op_Alloc)))
231 res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
234 } else if (get_irn_op(a) == op_DivMod) {
235 ta = value_of(get_DivMod_left(a));
236 tb = value_of(get_DivMod_right(a));
237 if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))) {
238 if (tarval_classify(tb) == 0) {res = NULL; break;}
239 if (get_Proj_proj(n)== 0) /* Div */
240 res = tarval_div(ta, tb);
242 res = tarval_mod(ta, tb);
255 /* returns 1 if the a and b are pointers to different locations. */
257 different_identity (ir_node *a, ir_node *b)
259 assert (get_irn_mode (a) == mode_p
260 && get_irn_mode (b) == mode_p);
262 if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
263 ir_node *a1 = get_Proj_pred (a);
264 ir_node *b1 = get_Proj_pred (b);
265 if (a1 != b1 && get_irn_op (a1) == op_Alloc
266 && get_irn_op (b1) == op_Alloc)
273 /* equivalent_node returns a node equivalent to N. It skips all nodes that
274 perform no actual computation, as, e.g., the Id nodes. It does not create
275 new nodes. It is therefore safe to free N if the node returned is not N.
276 If a node returns a Tuple we can not just skip it. If the size of the
277 in array fits, we transform n into a tuple (e.g., Div). */
279 equivalent_node (ir_node *n)
282 ir_node *a = NULL; /* to shutup gcc */
283 ir_node *b = NULL; /* to shutup gcc */
284 ir_node *c = NULL; /* to shutup gcc */
287 ins = get_irn_arity (n);
289 /* get the operands we will work on */
291 a = get_binop_left(n);
292 b = get_binop_right(n);
293 } else if (is_unop(n)) {
297 /* skip unnecessary nodes. */
298 switch (get_irn_opcode (n)) {
301 /* The Block constructor does not call optimize, but mature_block
302 calls the optimization. */
303 assert(get_Block_matured(n));
305 /* Straightening: a single entry Block following a single exit Block
306 can be merged, if it is not the Start block. */
307 /* !!! Beware, all Phi-nodes of n must have been optimized away.
308 This should be true, as the block is matured before optimize is called.
309 But what about Phi-cycles with the Phi0/Id that could not be resolved?
310 Remaining Phi nodes are just Ids. */
311 if ((get_Block_n_cfgpreds(n) == 1) &&
312 (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
313 (get_opt_control_flow())) {
314 n = get_nodes_Block(get_Block_cfgpred(n, 0)); DBG_OPT_STG;
315 } else if ((get_Block_n_cfgpreds(n) == 2) &&
316 (get_opt_control_flow())) {
317 /* Test whether Cond jumps twice to this block
318 @@@ we could do this also with two loops finding two preds from several ones. */
319 a = get_Block_cfgpred(n, 0);
320 b = get_Block_cfgpred(n, 1);
321 if ((get_irn_op(a) == op_Proj) &&
322 (get_irn_op(b) == op_Proj) &&
323 (get_Proj_pred(a) == get_Proj_pred(b)) &&
324 (get_irn_op(get_Proj_pred(a)) == op_Cond)) {
325 /* Also a single entry Block following a single exit Block. Phis have
326 twice the same operand and will be optimized away. */
327 n = get_nodes_Block(a); DBG_OPT_IFSIM;
329 } else if (get_opt_unreachable_code() &&
330 (n != current_ir_graph->start_block) &&
331 (n != current_ir_graph->end_block) ) {
333 /* If all inputs are dead, this block is dead too, except if it is
334 the start or end block. This is a step of unreachable code
336 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
337 if (!is_Bad(get_Block_cfgpred(n, i))) break;
339 if (i == get_Block_n_cfgpreds(n))
345 case iro_Jmp: /* GL: Why not same for op_Raise?? */
346 /* unreachable code elimination */
347 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
349 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
350 See cases for iro_Cond and iro_Proj in transform_node. */
351 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
352 case iro_Or: if (a == b) {n = a; break;}
357 /* After running compute_node there is only one constant predecessor.
358 Find this predecessors value and remember the other node: */
359 if ((tv = computed_value (a))) {
361 } else if ((tv = computed_value (b))) {
365 /* If this predecessors constant value is zero, the operation is
366 unnecessary. Remove it: */
367 if (tarval_classify (tv) == 0) {
368 n = on; DBG_OPT_ALGSIM1;
376 /* these operations are not commutative. Test only one predecessor. */
377 if (tarval_classify (computed_value (b)) == 0) {
378 n = a; DBG_OPT_ALGSIM1;
379 /* Test if b > #bits of a ==> return 0 / divide b by #bits
380 --> transform node? */
383 case iro_Not: /* NotNot x == x */
384 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
385 out of bounds exception if min =! max? */
386 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
387 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2
391 /* Mul is commutative and has again an other neutral element. */
392 if (tarval_classify (computed_value (a)) == 1) {
393 n = b; DBG_OPT_ALGSIM1
394 } else if (tarval_classify (computed_value (b)) == 1) {
395 n = a; DBG_OPT_ALGSIM1
399 /* Div is not commutative. */
400 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
401 /* Turn Div into a tuple (mem, bad, a) */
402 ir_node *mem = get_Div_mem(n);
403 turn_into_tuple(n, 3);
404 set_Tuple_pred(n, 0, mem);
405 set_Tuple_pred(n, 1, new_Bad());
406 set_Tuple_pred(n, 2, a);
409 /* GL: Why are they skipped? DivMod allocates new nodes --> it's
410 treated in transform node.
411 case iro_Mod, Quot, DivMod
415 n = a; /* And has it's own neutral element */
416 } else if (tarval_classify (computed_value (a)) == -1) {
418 } else if (tarval_classify (computed_value (b)) == -1) {
421 if (n != oldn) DBG_OPT_ALGSIM1;
424 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
425 n = a; DBG_OPT_ALGSIM3;
426 } else if (get_irn_mode(n) == mode_b) {
427 if (get_irn_op(a) == op_Conv &&
428 get_irn_mode (get_Conv_op(a)) == mode_b) {
429 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM2;
436 /* Several optimizations:
437 - no Phi in start block.
438 - remove Id operators that are inputs to Phi
439 - fold Phi-nodes, iff they have only one predecessor except
444 ir_node *block = NULL; /* to shutup gcc */
445 ir_node *first_val = NULL; /* to shutup gcc */
446 ir_node *scnd_val = NULL; /* to shutup gcc */
448 n_preds = get_Phi_n_preds(n);
450 block = get_nodes_Block(n);
451 if ((is_Bad(block)) || /* Control dead */
452 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
453 return new_Bad(); /* in the Start Block. */
455 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
458 /* first we test for a special case: */
459 /* Confirm is a special node fixing additional information for a
460 value that is known at a certain point. This is useful for
461 dataflow analysis. */
463 ir_node *a = follow_Id (get_Phi_pred(n, 0));
464 ir_node *b = follow_Id (get_Phi_pred(n, 1));
465 if ( (get_irn_op(a) == op_Confirm)
466 && (get_irn_op(b) == op_Confirm)
467 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
468 && (get_irn_n(a, 1) == get_irn_n (b, 1))
469 && (a->data.num == (~b->data.num & irpn_True) )) {
470 n = follow_Id (get_irn_n(a, 0));
476 /* Find first non-self-referencing input */
477 for (i = 0; i < n_preds; ++i) {
478 first_val = follow_Id(get_Phi_pred(n, i));
480 set_Phi_pred(n, i, first_val);
481 if ( (first_val != n) /* not self pointer */
482 && (get_irn_op(first_val) != op_Bad) /* value not dead */
483 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
484 break; /* then found first value. */
488 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
489 if (i >= n_preds) { n = new_Bad(); break; }
493 /* follow_Id () for rest of inputs, determine if any of these
494 are non-self-referencing */
495 while (++i < n_preds) {
496 scnd_val = follow_Id(get_Phi_pred(n, i));
498 set_Phi_pred(n, i, scnd_val);
500 && (scnd_val != first_val)
501 && (get_irn_op(scnd_val) != op_Bad)
502 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
507 /* Fold, if no multiple distinct non-self-referencing inputs */
509 n = first_val; DBG_OPT_PHI;
511 /* skip the remaining Ids. */
512 while (++i < n_preds) {
513 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
521 #if 0 /* Is an illegal transformation: different nodes can
522 represent the same pointer value!! */
523 a = skip_Proj(get_Load_mem(n));
526 if (get_irn_op(a) == op_Store) {
527 if ( different_identity (b, get_Store_ptr(a))) {
528 /* load and store use different pointers, therefore load
529 needs not take store's memory but the state before. */
530 set_Load_mem (n, get_Store_mem(a));
531 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
538 /* remove unnecessary store. */
540 a = skip_Proj(get_Store_mem(n));
541 b = get_Store_ptr(n);
542 c = skip_Proj(get_Store_value(n));
544 if (get_irn_op(a) == op_Store
545 && get_Store_ptr(a) == b
546 && skip_Proj(get_Store_value(a)) == c) {
547 /* We have twice exactly the same store -- a write after write. */
549 } else if (get_irn_op(c) == op_Load
550 && (a == c || skip_Proj(get_Load_mem(c)) == a)
551 && get_Load_ptr(c) == b ) {
552 /* We just loaded the value from the same memory, i.e., the store
553 doesn't change the memory -- a write after read. */
554 a = get_Store_mem(n);
555 turn_into_tuple(n, 2);
556 set_Tuple_pred(n, 0, a);
557 set_Tuple_pred(n, 1, new_Bad()); DBG_OPT_WAR;
564 a = get_Proj_pred(n);
566 if ( get_irn_op(a) == op_Tuple) {
567 /* Remove the Tuple/Proj combination. */
568 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
569 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
571 assert(0); /* This should not happen! */
574 } else if (get_irn_mode(n) == mode_X &&
575 is_Bad(get_nodes_Block(n))) {
576 /* Remove dead control flow. */
583 n = follow_Id (n); DBG_OPT_ID;
590 } /* end equivalent_node() */
593 /* tries several [inplace] [optimizing] transformations and returns an
594 equivalent node. The difference to equivalent_node is that these
595 transformations _do_ generate new nodes, and thus the old node must
596 not be freed even if the equivalent node isn't the old one. */
598 transform_node (ir_node *n)
601 ir_node *a = NULL, *b;
604 switch (get_irn_opcode(n)) {
606 ta = computed_value(n);
608 /* Turn Div into a tuple (mem, bad, value) */
609 ir_node *mem = get_Div_mem(n);
610 turn_into_tuple(n, 3);
611 set_Tuple_pred(n, 0, mem);
612 set_Tuple_pred(n, 1, new_Bad());
613 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
617 ta = computed_value(n);
619 /* Turn Div into a tuple (mem, bad, value) */
620 ir_node *mem = get_Mod_mem(n);
621 turn_into_tuple(n, 3);
622 set_Tuple_pred(n, 0, mem);
623 set_Tuple_pred(n, 1, new_Bad());
624 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
632 a = get_DivMod_left(n);
633 b = get_DivMod_right(n);
634 mode = get_irn_mode(a);
636 if (!(mode_is_int(get_irn_mode(a)) &&
637 mode_is_int(get_irn_mode(b))))
641 a = new_Const (mode, tarval_from_long (mode, 1));
642 b = new_Const (mode, tarval_from_long (mode, 0));
649 if (tarval_classify(tb) == 1) {
650 b = new_Const (mode, tarval_from_long (mode, 0));
654 resa = tarval_div (ta, tb);
655 if (!resa) break; /* Causes exception!!! Model by replacing through
656 Jmp for X result!? */
657 resb = tarval_mod (ta, tb);
658 if (!resb) break; /* Causes exception! */
659 a = new_Const (mode, resa);
660 b = new_Const (mode, resb);
663 } else if (tarval_classify (ta) == 0) {
668 if (evaluated) { /* replace by tuple */
669 ir_node *mem = get_DivMod_mem(n);
670 turn_into_tuple(n, 4);
671 set_Tuple_pred(n, 0, mem);
672 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
673 set_Tuple_pred(n, 2, a);
674 set_Tuple_pred(n, 3, b);
675 assert(get_nodes_Block(n));
681 /* Replace the Cond by a Jmp if it branches on a constant
684 a = get_Cond_selector(n);
688 (get_irn_mode(a) == mode_b) &&
689 (get_opt_unreachable_code())) {
690 /* It's a boolean Cond, branching on a boolean constant.
691 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
692 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
693 turn_into_tuple(n, 2);
694 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
695 set_Tuple_pred(n, 0, new_Bad());
696 set_Tuple_pred(n, 1, jmp);
698 set_Tuple_pred(n, 0, jmp);
699 set_Tuple_pred(n, 1, new_Bad());
701 /* We might generate an endless loop, so keep it alive. */
702 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
704 (get_irn_mode(a) == mode_I) &&
705 (get_Cond_kind(n) == dense) &&
706 (get_opt_unreachable_code())) {
707 /* I don't want to allow Tuples smaller than the biggest Proj.
708 Also this tuple might get really big...
709 I generate the Jmp here, and remember it in link. Link is used
710 when optimizing Proj. */
711 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
712 /* We might generate an endless loop, so keep it alive. */
713 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
714 } else if ((get_irn_op(get_Cond_selector(n)) == op_Eor)
715 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
716 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
717 /* The Eor is a negate. Generate a new Cond without the negate,
718 simulate the negate by exchanging the results. */
719 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
721 } else if ((get_irn_op(get_Cond_selector(n)) == op_Not)
722 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
723 /* A Not before the Cond. Generate a new Cond without the Not,
724 simulate the Not by exchanging the results. */
725 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
732 a = get_Proj_pred(n);
734 if ((get_irn_op(a) == op_Cond)
736 && get_irn_op(get_irn_link(a)) == op_Cond) {
737 /* Use the better Cond if the Proj projs from a Cond which get's
738 its result from an Eor/Not. */
739 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
740 || (get_irn_op(get_Cond_selector(a)) == op_Not))
741 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
742 && (get_irn_op(get_irn_link(a)) == op_Cond)
743 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
744 set_Proj_pred(n, get_irn_link(a));
745 if (get_Proj_proj(n) == 0)
749 } else if ((get_irn_op(a) == op_Cond)
750 && (get_irn_mode(get_Cond_selector(a)) == mode_I)
752 && (get_Cond_kind(a) == dense)
753 && (get_opt_unreachable_code())) {
754 /* The Cond is a Switch on a Constant */
755 if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
756 /* The always taken branch, reuse the existing Jmp. */
757 if (!get_irn_link(a)) /* well, if it exists ;-> */
758 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
759 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
761 } else {/* Not taken control flow, but be careful with the default! */
762 if (get_Proj_proj(n) < a->attr.c.default_proj){
763 /* a never taken branch */
766 a->attr.c.default_proj = get_Proj_proj(n);
771 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
773 b = get_Eor_right(n);
775 if ((get_irn_mode(n) == mode_b)
776 && (get_irn_op(a) == op_Proj)
777 && (get_irn_mode(a) == mode_b)
778 && (tarval_classify (computed_value (b)) == 1)
779 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
780 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
781 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
782 mode_b, get_negated_pnc(get_Proj_proj(a)));
783 else if ((get_irn_mode(n) == mode_b)
784 && (tarval_classify (computed_value (b)) == 1))
785 /* The Eor is a Not. Replace it by a Not. */
786 /* ????!!!Extend to bitfield 1111111. */
787 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
793 if ( (get_irn_mode(n) == mode_b)
794 && (get_irn_op(a) == op_Proj)
795 && (get_irn_mode(a) == mode_b)
796 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
797 /* We negate a Cmp. The Cmp has the negated result anyways! */
798 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
799 mode_b, get_negated_pnc(get_Proj_proj(a)));
807 /* **************** Common Subexpression Elimination **************** */
809 /* Compare function for two nodes in the hash table. Gets two */
810 /* nodes as parameters. Returns 0 if the nodes are a cse. */
812 vt_cmp (const void *elt, const void *key)
820 if (a == b) return 0;
822 if ((get_irn_op(a) != get_irn_op(b)) ||
823 (get_irn_mode(a) != get_irn_mode(b))) return 1;
825 /* compare if a's in and b's in are equal */
826 /* GL: we optimize only nodes with in arrays of fixed sizes.
827 if (get_irn_arity (a) != -2) {
828 ins = get_irn_arity (a);
829 if (ins != get_irn_arity (b)) return 1;
830 ain = get_irn_in (a);
831 bin = get_irn_in (b);
834 if (get_irn_arity (a) != get_irn_arity(b))
837 /* for block-local cse and pinned nodes: */
838 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
839 if (get_irn_n(a, -1) != get_irn_n(b, -1))
843 /* compare a->in[0..ins] with b->in[0..ins] */
844 for (i = 0; i < get_irn_arity(a); i++)
845 if (get_irn_n(a, i) != get_irn_n(b, i))
848 switch (get_irn_opcode(a)) {
850 return get_irn_const_attr (a) != get_irn_const_attr (b);
852 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
854 return get_Filter_proj(a) != get_Filter_proj(b);
856 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
857 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
859 return (get_irn_free_attr(a) != get_irn_free_attr(b));
861 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
862 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
864 return (get_irn_call_attr(a) != get_irn_call_attr(b));
866 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
867 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
868 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
869 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
870 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
871 || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
873 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
881 ir_node_hash (ir_node *node)
886 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
887 h = get_irn_arity(node);
889 /* consider all in nodes... except the block. */
890 for (i = 0; i < get_irn_arity(node); i++) {
891 h = 9*h + (unsigned long)get_irn_n(node, i);
895 h = 9*h + (unsigned long) get_irn_mode (node);
897 h = 9*h + (unsigned long) get_irn_op (node);
903 new_identities (void)
905 return new_pset (vt_cmp, TUNE_NIR_NODES);
909 del_identities (pset *value_table)
911 del_pset (value_table);
914 /* Return the canonical node computing the same value as n.
915 Looks up the node in a hash table. */
916 static inline ir_node *
917 identify (pset *value_table, ir_node *n)
921 if (!value_table) return n;
923 if (get_opt_reassociation()) {
924 switch (get_irn_opcode (n)) {
931 /* for commutative operators perform a OP b == b OP a */
932 if (get_binop_left(n) > get_binop_right(n)) {
933 ir_node *h = get_binop_left(n);
934 set_binop_left(n, get_binop_right(n));
935 set_binop_right(n, h);
943 o = pset_find (value_table, n, ir_node_hash (n));
949 /* During construction we set the pinned flag in the graph right when the
950 optimizatin is performed. The flag turning on procedure global cse could
951 be changed between two allocations. This way we are safe. */
952 static inline ir_node *
953 identify_cons (pset *value_table, ir_node *n) {
955 n = identify(value_table, n);
956 if (get_irn_n(old, -1) != get_irn_n(n, -1))
957 set_irg_pinned(current_ir_graph, floats);
961 /* Return the canonical node computing the same value as n.
962 Looks up the node in a hash table, enters it in the table
963 if it isn't there yet. */
965 identify_remember (pset *value_table, ir_node *node)
969 if (!value_table) return node;
971 /* lookup or insert in hash table with given hash key. */
972 o = pset_insert (value_table, node, ir_node_hash (node));
974 if (o == node) return node;
980 add_identities (pset *value_table, ir_node *node) {
981 identify_remember (value_table, node);
984 /* garbage in, garbage out. If a node has a dead input, i.e., the
985 Bad node is input to the node, return the Bad node. */
986 static inline ir_node *
990 ir_op* op = get_irn_op(node);
992 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
993 blocks predecessors is dead. */
994 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
995 for (i = -1; i < get_irn_arity(node); i++) {
996 if (is_Bad(get_irn_n(node, i))) {
1002 /* If Block has only Bads as predecessors it's garbage. */
1003 /* If Phi has only Bads as predecessors it's garbage. */
1004 if (op == op_Block || op == op_Phi) {
1005 for (i = 0; i < get_irn_arity(node); i++) {
1006 if (!is_Bad(get_irn_n(node, i))) break;
1008 if (i = get_irn_arity(node)) node = new_Bad();
1015 /* These optimizations deallocate nodes from the obstack.
1016 It can only be called if it is guaranteed that no other nodes
1017 reference this one, i.e., right after construction of a node. */
1019 optimize (ir_node *n)
1024 /* Allways optimize Phi nodes: part of the construction. */
1025 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1027 /* constant expression evaluation / constant folding */
1028 if (get_opt_constant_folding()) {
1029 /* constants can not be evaluated */
1030 if (get_irn_op(n) != op_Const) {
1031 /* try to evaluate */
1032 tv = computed_value (n);
1033 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1034 /* evaluation was succesful -- replace the node. */
1035 obstack_free (current_ir_graph->obst, n);
1036 return new_Const (get_tv_mode (tv), tv);
1041 /* remove unnecessary nodes */
1042 if (get_opt_constant_folding() ||
1043 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1044 (get_irn_op(n) == op_Id) ||
1045 (get_irn_op(n) == op_Proj) ||
1046 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1047 n = equivalent_node (n);
1049 /** common subexpression elimination **/
1050 /* Checks whether n is already available. */
1051 /* The block input is used to distinguish different subexpressions. Right
1052 now all nodes are pinned to blocks, i.e., the cse only finds common
1053 subexpressions within a block. */
1055 n = identify_cons (current_ir_graph->value_table, n);
1058 /* We found an existing, better node, so we can deallocate the old node. */
1059 obstack_free (current_ir_graph->obst, old_n);
1062 /* Some more constant expression evaluation that does not allow to
1064 if (get_opt_constant_folding() ||
1065 (get_irn_op(n) == op_Cond) ||
1066 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1067 n = transform_node (n);
1069 /* Remove nodes with dead (Bad) input.
1070 Run always for transformation induced Bads. */
1073 /* Now we can verify the node, as it has no dead inputs any more. */
1076 /* Now we have a legal, useful node. Enter it in hash table for cse */
1077 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1078 n = identify_remember (current_ir_graph->value_table, n);
1085 /* These optimizations never deallocate nodes. This can cause dead
1086 nodes lying on the obstack. Remove these by a dead node elimination,
1087 i.e., a copying garbage collection. */
1089 optimize_in_place_2 (ir_node *n)
1094 if (!get_optimize() && (get_irn_op(n) != op_Phi)) return n;
1096 /* if not optimize return n */
1099 /* Here this is possible. Why? */
1104 /* constant expression evaluation / constant folding */
1105 if (get_opt_constant_folding()) {
1106 /* constants can not be evaluated */
1107 if (get_irn_op(n) != op_Const) {
1108 /* try to evaluate */
1109 tv = computed_value (n);
1110 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1111 /* evaluation was succesful -- replace the node. */
1112 n = new_Const (get_tv_mode (tv), tv);
1113 __dbg_info_merge_pair(n, old_n, dbg_const_eval);
1119 /* remove unnecessary nodes */
1120 /*if (get_opt_constant_folding()) */
1121 if (get_opt_constant_folding() ||
1122 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1123 (get_irn_op(n) == op_Id) || /* ... */
1124 (get_irn_op(n) == op_Proj) || /* ... */
1125 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1126 n = equivalent_node (n);
1128 /** common subexpression elimination **/
1129 /* Checks whether n is already available. */
1130 /* The block input is used to distinguish different subexpressions. Right
1131 now all nodes are pinned to blocks, i.e., the cse only finds common
1132 subexpressions within a block. */
1133 if (get_opt_cse()) {
1134 n = identify (current_ir_graph->value_table, n);
1137 /* Some more constant expression evaluation. */
1138 if (get_opt_constant_folding() ||
1139 (get_irn_op(n) == op_Cond) ||
1140 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1141 n = transform_node (n);
1143 /* Remove nodes with dead (Bad) input.
1144 Run always for transformation induced Bads. */
1147 /* Now we can verify the node, as it has no dead inputs any more. */
1150 /* Now we have a legal, useful node. Enter it in hash table for cse.
1151 Blocks should be unique anyways. (Except the successor of start:
1152 is cse with the start block!) */
1153 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1154 n = identify_remember (current_ir_graph->value_table, n);
1159 /* Wrapper for external use, set proper status bits after optimization */
1161 optimize_in_place (ir_node *n) {
1162 /* Handle graph state */
1163 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1164 if (get_opt_global_cse())
1165 set_irg_pinned(current_ir_graph, floats);
1166 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1167 set_irg_outs_inconsistent(current_ir_graph);
1168 /* Maybe we could also test whether optimizing the node can
1169 change the control graph. */
1170 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1171 set_irg_dom_inconsistent(current_ir_graph);
1172 return optimize_in_place_2 (n);