1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
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_Is, 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, greater equal, ... this will return true, else it
184 will return false. 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_straightening())) {
314 n = get_nodes_Block(get_Block_cfgpred(n, 0)); DBG_OPT_STG;
316 } else if ((get_Block_n_cfgpreds(n) == 2) &&
317 (get_opt_control_flow_weak_simplification())) {
318 /* Test whether Cond jumps twice to this block
319 @@@ we could do this also with two loops finding two preds from several ones. */
320 a = get_Block_cfgpred(n, 0);
321 b = get_Block_cfgpred(n, 1);
322 if ((get_irn_op(a) == op_Proj) &&
323 (get_irn_op(b) == op_Proj) &&
324 (get_Proj_pred(a) == get_Proj_pred(b)) &&
325 (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
326 (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
327 /* Also a single entry Block following a single exit Block. Phis have
328 twice the same operand and will be optimized away. */
329 n = get_nodes_Block(a); DBG_OPT_IFSIM;
331 } else if (get_opt_unreachable_code() &&
332 (n != current_ir_graph->start_block) &&
333 (n != current_ir_graph->end_block) ) {
335 /* If all inputs are dead, this block is dead too, except if it is
336 the start or end block. This is a step of unreachable code
338 for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
339 if (!is_Bad(get_Block_cfgpred(n, i))) break;
341 if (i == get_Block_n_cfgpreds(n))
347 case iro_Jmp: /* GL: Why not same for op_Raise?? */
348 /* unreachable code elimination */
349 if (is_Bad(get_nodes_Block(n))) n = new_Bad();
351 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
352 See cases for iro_Cond and iro_Proj in transform_node. */
353 /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
354 case iro_Or: if (a == b) {n = a; break;}
359 /* After running compute_node there is only one constant predecessor.
360 Find this predecessors value and remember the other node: */
361 if ((tv = computed_value (a))) {
363 } else if ((tv = computed_value (b))) {
367 /* If this predecessors constant value is zero, the operation is
368 unnecessary. Remove it: */
369 if (tarval_classify (tv) == 0) {
370 n = on; DBG_OPT_ALGSIM1;
378 /* these operations are not commutative. Test only one predecessor. */
379 if (tarval_classify (computed_value (b)) == 0) {
380 n = a; DBG_OPT_ALGSIM1;
381 /* Test if b > #bits of a ==> return 0 / divide b by #bits
382 --> transform node? */
385 case iro_Not: /* NotNot x == x */
386 case iro_Minus: /* --x == x */ /* ??? Is this possible or can --x raise an
387 out of bounds exception if min =! max? */
388 if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
389 n = get_unop_op(get_unop_op(n)); DBG_OPT_ALGSIM2;
393 /* Mul is commutative and has again an other neutral element. */
394 if (tarval_classify (computed_value (a)) == 1) {
395 n = b; DBG_OPT_ALGSIM1;
396 } else if (tarval_classify (computed_value (b)) == 1) {
397 n = a; DBG_OPT_ALGSIM1;
401 /* Div is not commutative. */
402 if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
403 /* Turn Div into a tuple (mem, bad, a) */
404 ir_node *mem = get_Div_mem(n);
405 turn_into_tuple(n, 3);
406 set_Tuple_pred(n, 0, mem);
407 set_Tuple_pred(n, 1, new_Bad());
408 set_Tuple_pred(n, 2, a);
412 case iro_Mod, Quot, DivMod
413 DivMod allocates new nodes --> it's treated in transform node.
414 What about Quot, DivMod?
418 n = a; /* And has it's own neutral element */
419 } else if (tarval_classify (computed_value (a)) == -1) {
421 } else if (tarval_classify (computed_value (b)) == -1) {
424 if (n != oldn) DBG_OPT_ALGSIM1;
427 if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
428 n = a; DBG_OPT_ALGSIM3;
429 } else if (get_irn_mode(n) == mode_b) {
430 if (get_irn_op(a) == op_Conv &&
431 get_irn_mode (get_Conv_op(a)) == mode_b) {
432 n = get_Conv_op(a); /* Convb(Conv*(xxxb(...))) == xxxb(...) */ DBG_OPT_ALGSIM2;
439 /* Several optimizations:
440 - no Phi in start block.
441 - remove Id operators that are inputs to Phi
442 - fold Phi-nodes, iff they have only one predecessor except
447 ir_node *block = NULL; /* to shutup gcc */
448 ir_node *first_val = NULL; /* to shutup gcc */
449 ir_node *scnd_val = NULL; /* to shutup gcc */
451 if (!get_opt_normalize()) return;
453 n_preds = get_Phi_n_preds(n);
455 block = get_nodes_Block(n);
456 /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
457 assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
458 if ((is_Bad(block)) || /* Control dead */
459 (block == current_ir_graph->start_block)) /* There should be no Phi nodes */
460 return new_Bad(); /* in the Start Block. */
462 if (n_preds == 0) break; /* Phi of dead Region without predecessors. */
465 /* first we test for a special case: */
466 /* Confirm is a special node fixing additional information for a
467 value that is known at a certain point. This is useful for
468 dataflow analysis. */
470 ir_node *a = follow_Id (get_Phi_pred(n, 0));
471 ir_node *b = follow_Id (get_Phi_pred(n, 1));
472 if ( (get_irn_op(a) == op_Confirm)
473 && (get_irn_op(b) == op_Confirm)
474 && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
475 && (get_irn_n(a, 1) == get_irn_n (b, 1))
476 && (a->data.num == (~b->data.num & irpn_True) )) {
477 n = follow_Id (get_irn_n(a, 0));
483 /* Find first non-self-referencing input */
484 for (i = 0; i < n_preds; ++i) {
485 first_val = follow_Id(get_Phi_pred(n, i));
487 set_Phi_pred(n, i, first_val);
488 if ( (first_val != n) /* not self pointer */
489 && (get_irn_op(first_val) != op_Bad) /* value not dead */
490 && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
491 break; /* then found first value. */
495 /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
496 if (i >= n_preds) { n = new_Bad(); break; }
500 /* follow_Id () for rest of inputs, determine if any of these
501 are non-self-referencing */
502 while (++i < n_preds) {
503 scnd_val = follow_Id(get_Phi_pred(n, i));
505 set_Phi_pred(n, i, scnd_val);
507 && (scnd_val != first_val)
508 && (get_irn_op(scnd_val) != op_Bad)
509 && !(is_Bad (get_Block_cfgpred(block, i))) ) {
514 /* Fold, if no multiple distinct non-self-referencing inputs */
516 n = first_val; DBG_OPT_PHI;
518 /* skip the remaining Ids. */
519 while (++i < n_preds) {
520 set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
528 #if 0 /* Is an illegal transformation: different nodes can
529 represent the same pointer value!! */
530 a = skip_Proj(get_Load_mem(n));
533 if (get_irn_op(a) == op_Store) {
534 if ( different_identity (b, get_Store_ptr(a))) {
535 /* load and store use different pointers, therefore load
536 needs not take store's memory but the state before. */
537 set_Load_mem (n, get_Store_mem(a));
538 } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
545 /* remove unnecessary store. */
547 a = skip_Proj(get_Store_mem(n));
548 b = get_Store_ptr(n);
549 c = skip_Proj(get_Store_value(n));
551 if (get_irn_op(a) == op_Store
552 && get_Store_ptr(a) == b
553 && skip_Proj(get_Store_value(a)) == c) {
554 /* We have twice exactly the same store -- a write after write. */
556 } else if (get_irn_op(c) == op_Load
557 && (a == c || skip_Proj(get_Load_mem(c)) == a)
558 && get_Load_ptr(c) == b ) {
559 /* We just loaded the value from the same memory, i.e., the store
560 doesn't change the memory -- a write after read. */
561 a = get_Store_mem(n);
562 turn_into_tuple(n, 2);
563 set_Tuple_pred(n, 0, a);
564 set_Tuple_pred(n, 1, new_Bad()); DBG_OPT_WAR;
571 a = get_Proj_pred(n);
573 if ( get_irn_op(a) == op_Tuple) {
574 /* Remove the Tuple/Proj combination. */
575 if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
576 n = get_Tuple_pred(a, get_Proj_proj(n)); DBG_OPT_TUPLE;
578 assert(0); /* This should not happen! */
581 } else if (get_irn_mode(n) == mode_X &&
582 is_Bad(get_nodes_Block(n))) {
583 /* Remove dead control flow -- early gigo. */
590 n = follow_Id (n); DBG_OPT_ID;
597 } /* end equivalent_node() */
600 /* tries several [inplace] [optimizing] transformations and returns an
601 equivalent node. The difference to equivalent_node is that these
602 transformations _do_ generate new nodes, and thus the old node must
603 not be freed even if the equivalent node isn't the old one. */
605 transform_node (ir_node *n)
608 ir_node *a = NULL, *b;
611 switch (get_irn_opcode(n)) {
613 ta = computed_value(n);
615 /* Turn Div into a tuple (mem, bad, value) */
616 ir_node *mem = get_Div_mem(n);
617 turn_into_tuple(n, 3);
618 set_Tuple_pred(n, 0, mem);
619 set_Tuple_pred(n, 1, new_Bad());
620 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
624 ta = computed_value(n);
626 /* Turn Div into a tuple (mem, bad, value) */
627 ir_node *mem = get_Mod_mem(n);
628 turn_into_tuple(n, 3);
629 set_Tuple_pred(n, 0, mem);
630 set_Tuple_pred(n, 1, new_Bad());
631 set_Tuple_pred(n, 2, new_Const(get_tv_mode(ta), ta));
639 a = get_DivMod_left(n);
640 b = get_DivMod_right(n);
641 mode = get_irn_mode(a);
643 if (!(mode_is_int(get_irn_mode(a)) &&
644 mode_is_int(get_irn_mode(b))))
648 a = new_Const (mode, tarval_from_long (mode, 1));
649 b = new_Const (mode, tarval_from_long (mode, 0));
656 if (tarval_classify(tb) == 1) {
657 b = new_Const (mode, tarval_from_long (mode, 0));
661 resa = tarval_div (ta, tb);
662 if (!resa) break; /* Causes exception!!! Model by replacing through
663 Jmp for X result!? */
664 resb = tarval_mod (ta, tb);
665 if (!resb) break; /* Causes exception! */
666 a = new_Const (mode, resa);
667 b = new_Const (mode, resb);
670 } else if (tarval_classify (ta) == 0) {
675 if (evaluated) { /* replace by tuple */
676 ir_node *mem = get_DivMod_mem(n);
677 turn_into_tuple(n, 4);
678 set_Tuple_pred(n, 0, mem);
679 set_Tuple_pred(n, 1, new_Bad()); /* no exception */
680 set_Tuple_pred(n, 2, a);
681 set_Tuple_pred(n, 3, b);
682 assert(get_nodes_Block(n));
688 /* Replace the Cond by a Jmp if it branches on a constant
691 a = get_Cond_selector(n);
695 (get_irn_mode(a) == mode_b) &&
696 (get_opt_unreachable_code())) {
697 /* It's a boolean Cond, branching on a boolean constant.
698 Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
699 jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
700 turn_into_tuple(n, 2);
701 if (tv_val_b(ta) == 1) /* GL: I hope this returns 1 if true */ {
702 set_Tuple_pred(n, 0, new_Bad());
703 set_Tuple_pred(n, 1, jmp);
705 set_Tuple_pred(n, 0, jmp);
706 set_Tuple_pred(n, 1, new_Bad());
708 /* We might generate an endless loop, so keep it alive. */
709 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
711 (get_irn_mode(a) == mode_Iu) &&
712 (get_Cond_kind(n) == dense) &&
713 (get_opt_unreachable_code())) {
714 /* I don't want to allow Tuples smaller than the biggest Proj.
715 Also this tuple might get really big...
716 I generate the Jmp here, and remember it in link. Link is used
717 when optimizing Proj. */
718 set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
719 /* We might generate an endless loop, so keep it alive. */
720 add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
721 } else if ((get_irn_op(get_Cond_selector(n)) == op_Eor)
722 && (get_irn_mode(get_Cond_selector(n)) == mode_b)
723 && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
724 /* The Eor is a negate. Generate a new Cond without the negate,
725 simulate the negate by exchanging the results. */
726 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
728 } else if ((get_irn_op(get_Cond_selector(n)) == op_Not)
729 && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
730 /* A Not before the Cond. Generate a new Cond without the Not,
731 simulate the Not by exchanging the results. */
732 set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
739 a = get_Proj_pred(n);
741 if ((get_irn_op(a) == op_Cond)
743 && get_irn_op(get_irn_link(a)) == op_Cond) {
744 /* Use the better Cond if the Proj projs from a Cond which get's
745 its result from an Eor/Not. */
746 assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
747 || (get_irn_op(get_Cond_selector(a)) == op_Not))
748 && (get_irn_mode(get_Cond_selector(a)) == mode_b)
749 && (get_irn_op(get_irn_link(a)) == op_Cond)
750 && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
751 set_Proj_pred(n, get_irn_link(a));
752 if (get_Proj_proj(n) == 0)
756 } else if ((get_irn_op(a) == op_Cond)
757 && (get_irn_mode(get_Cond_selector(a)) == mode_Iu)
759 && (get_Cond_kind(a) == dense)
760 && (get_opt_unreachable_code())) {
761 /* The Cond is a Switch on a Constant */
762 if (get_Proj_proj(n) == tv_val_uInt(value_of(a))) {
763 /* The always taken branch, reuse the existing Jmp. */
764 if (!get_irn_link(a)) /* well, if it exists ;-> */
765 set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
766 assert(get_irn_op(get_irn_link(a)) == op_Jmp);
768 } else {/* Not taken control flow, but be careful with the default! */
769 if (get_Proj_proj(n) < a->attr.c.default_proj){
770 /* a never taken branch */
773 a->attr.c.default_proj = get_Proj_proj(n);
778 case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
780 b = get_Eor_right(n);
782 if ((get_irn_mode(n) == mode_b)
783 && (get_irn_op(a) == op_Proj)
784 && (get_irn_mode(a) == mode_b)
785 && (tarval_classify (computed_value (b)) == 1)
786 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
787 /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
788 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
789 mode_b, get_negated_pnc(get_Proj_proj(a)));
790 else if ((get_irn_mode(n) == mode_b)
791 && (tarval_classify (computed_value (b)) == 1))
792 /* The Eor is a Not. Replace it by a Not. */
793 /* ????!!!Extend to bitfield 1111111. */
794 n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
800 if ( (get_irn_mode(n) == mode_b)
801 && (get_irn_op(a) == op_Proj)
802 && (get_irn_mode(a) == mode_b)
803 && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
804 /* We negate a Cmp. The Cmp has the negated result anyways! */
805 n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
806 mode_b, get_negated_pnc(get_Proj_proj(a)));
814 /* **************** Common Subexpression Elimination **************** */
816 /* Compare function for two nodes in the hash table. Gets two */
817 /* nodes as parameters. Returns 0 if the nodes are a cse. */
819 vt_cmp (const void *elt, const void *key)
827 if (a == b) return 0;
829 if ((get_irn_op(a) != get_irn_op(b)) ||
830 (get_irn_mode(a) != get_irn_mode(b))) return 1;
832 /* compare if a's in and b's in are equal */
833 if (get_irn_arity (a) != get_irn_arity(b))
836 /* for block-local cse and pinned nodes: */
837 if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
838 if (get_irn_n(a, -1) != get_irn_n(b, -1))
842 /* compare a->in[0..ins] with b->in[0..ins] */
843 for (i = 0; i < get_irn_arity(a); i++)
844 if (get_irn_n(a, i) != get_irn_n(b, i))
847 switch (get_irn_opcode(a)) {
849 return get_irn_const_attr (a) != get_irn_const_attr (b);
851 return get_irn_proj_attr (a) != get_irn_proj_attr (b);
853 return get_Filter_proj(a) != get_Filter_proj(b);
855 return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
856 || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
858 return (get_irn_free_attr(a) != get_irn_free_attr(b));
860 return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
861 || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
863 return (get_irn_call_attr(a) != get_irn_call_attr(b));
865 return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
866 || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
867 || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
868 || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
869 || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
871 return get_irn_phi_attr (a) != get_irn_phi_attr (b);
879 ir_node_hash (ir_node *node)
884 /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
885 h = get_irn_arity(node);
887 /* consider all in nodes... except the block. */
888 for (i = 0; i < get_irn_arity(node); i++) {
889 h = 9*h + (unsigned long)get_irn_n(node, i);
893 h = 9*h + (unsigned long) get_irn_mode (node);
895 h = 9*h + (unsigned long) get_irn_op (node);
901 new_identities (void)
903 return new_pset (vt_cmp, TUNE_NIR_NODES);
907 del_identities (pset *value_table)
909 del_pset (value_table);
912 /* Return the canonical node computing the same value as n.
913 Looks up the node in a hash table. */
914 static INLINE ir_node *
915 identify (pset *value_table, ir_node *n)
919 if (!value_table) return n;
921 if (get_opt_reassociation()) {
922 switch (get_irn_opcode (n)) {
929 /* for commutative operators perform a OP b == b OP a */
930 if (get_binop_left(n) > get_binop_right(n)) {
931 ir_node *h = get_binop_left(n);
932 set_binop_left(n, get_binop_right(n));
933 set_binop_right(n, h);
941 o = pset_find (value_table, n, ir_node_hash (n));
947 /* During construction we set the pinned flag in the graph right when the
948 optimizatin is performed. The flag turning on procedure global cse could
949 be changed between two allocations. This way we are safe. */
950 static INLINE ir_node *
951 identify_cons (pset *value_table, ir_node *n) {
953 n = identify(value_table, n);
954 if (get_irn_n(old, -1) != get_irn_n(n, -1))
955 set_irg_pinned(current_ir_graph, floats);
959 /* Return the canonical node computing the same value as n.
960 Looks up the node in a hash table, enters it in the table
961 if it isn't there yet. */
963 identify_remember (pset *value_table, ir_node *node)
967 if (!value_table) return node;
969 /* lookup or insert in hash table with given hash key. */
970 o = pset_insert (value_table, node, ir_node_hash (node));
972 if (o == node) return node;
978 add_identities (pset *value_table, ir_node *node) {
979 identify_remember (value_table, node);
982 /* garbage in, garbage out. If a node has a dead input, i.e., the
983 Bad node is input to the node, return the Bad node. */
984 static INLINE ir_node *
988 ir_op* op = get_irn_op(node);
990 /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
991 blocks predecessors is dead. */
992 if ( op != op_Block && op != op_Phi && op != op_Tuple) {
993 for (i = -1; i < get_irn_arity(node); i++) {
994 if (is_Bad(get_irn_n(node, i))) {
1000 /* If Block has only Bads as predecessors it's garbage. */
1001 /* If Phi has only Bads as predecessors it's garbage. */
1002 if (op == op_Block || op == op_Phi) {
1003 for (i = 0; i < get_irn_arity(node); i++) {
1004 if (!is_Bad(get_irn_n(node, i))) break;
1006 if (i = get_irn_arity(node)) node = new_Bad();
1013 /* These optimizations deallocate nodes from the obstack.
1014 It can only be called if it is guaranteed that no other nodes
1015 reference this one, i.e., right after construction of a node. */
1017 optimize_node (ir_node *n)
1022 /* Allways optimize Phi nodes: part of the construction. */
1023 if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1025 /* constant expression evaluation / constant folding */
1026 if (get_opt_constant_folding()) {
1027 /* constants can not be evaluated */
1028 if (get_irn_op(n) != op_Const) {
1029 /* try to evaluate */
1030 tv = computed_value (n);
1031 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1032 /* evaluation was succesful -- replace the node. */
1033 obstack_free (current_ir_graph->obst, n);
1034 return new_Const (get_tv_mode (tv), tv);
1039 /* remove unnecessary nodes */
1040 if (get_opt_constant_folding() ||
1041 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1042 (get_irn_op(n) == op_Id) ||
1043 (get_irn_op(n) == op_Proj) ||
1044 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1045 n = equivalent_node (n);
1047 /** common subexpression elimination **/
1048 /* Checks whether n is already available. */
1049 /* The block input is used to distinguish different subexpressions. Right
1050 now all nodes are pinned to blocks, i.e., the cse only finds common
1051 subexpressions within a block. */
1053 n = identify_cons (current_ir_graph->value_table, n);
1056 /* We found an existing, better node, so we can deallocate the old node. */
1057 obstack_free (current_ir_graph->obst, old_n);
1060 /* Some more constant expression evaluation that does not allow to
1062 if (get_opt_constant_folding() ||
1063 (get_irn_op(n) == op_Cond) ||
1064 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1065 n = transform_node (n);
1067 /* Remove nodes with dead (Bad) input.
1068 Run always for transformation induced Bads. */
1071 /* Now we can verify the node, as it has no dead inputs any more. */
1074 /* Now we have a legal, useful node. Enter it in hash table for cse */
1075 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1076 n = identify_remember (current_ir_graph->value_table, n);
1083 /* These optimizations never deallocate nodes. This can cause dead
1084 nodes lying on the obstack. Remove these by a dead node elimination,
1085 i.e., a copying garbage collection. */
1087 optimize_in_place_2 (ir_node *n)
1092 if (!get_optimize() && (get_irn_op(n) != op_Phi)) return n;
1094 /* if not optimize return n */
1097 /* Here this is possible. Why? */
1102 /* constant expression evaluation / constant folding */
1103 if (get_opt_constant_folding()) {
1104 /* constants can not be evaluated */
1105 if (get_irn_op(n) != op_Const) {
1106 /* try to evaluate */
1107 tv = computed_value (n);
1108 if ((get_irn_mode(n) != mode_T) && (tv != NULL)) {
1109 /* evaluation was succesful -- replace the node. */
1110 n = new_Const (get_tv_mode (tv), tv);
1111 __dbg_info_merge_pair(n, old_n, dbg_const_eval);
1117 /* remove unnecessary nodes */
1118 /*if (get_opt_constant_folding()) */
1119 if (get_opt_constant_folding() ||
1120 (get_irn_op(n) == op_Phi) || /* always optimize these nodes. */
1121 (get_irn_op(n) == op_Id) || /* ... */
1122 (get_irn_op(n) == op_Proj) || /* ... */
1123 (get_irn_op(n) == op_Block) ) /* Flags tested local. */
1124 n = equivalent_node (n);
1126 /** common subexpression elimination **/
1127 /* Checks whether n is already available. */
1128 /* The block input is used to distinguish different subexpressions. Right
1129 now all nodes are pinned to blocks, i.e., the cse only finds common
1130 subexpressions within a block. */
1131 if (get_opt_cse()) {
1132 n = identify (current_ir_graph->value_table, n);
1135 /* Some more constant expression evaluation. */
1136 if (get_opt_constant_folding() ||
1137 (get_irn_op(n) == op_Cond) ||
1138 (get_irn_op(n) == op_Proj)) /* Flags tested local. */
1139 n = transform_node (n);
1141 /* Remove nodes with dead (Bad) input.
1142 Run always for transformation induced Bads. */
1145 /* Now we can verify the node, as it has no dead inputs any more. */
1148 /* Now we have a legal, useful node. Enter it in hash table for cse.
1149 Blocks should be unique anyways. (Except the successor of start:
1150 is cse with the start block!) */
1151 if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1152 n = identify_remember (current_ir_graph->value_table, n);
1157 /* Wrapper for external use, set proper status bits after optimization */
1159 optimize_in_place (ir_node *n) {
1160 /* Handle graph state */
1161 assert(get_irg_phase_state(current_ir_graph) != phase_building);
1162 if (get_opt_global_cse())
1163 set_irg_pinned(current_ir_graph, floats);
1164 if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1165 set_irg_outs_inconsistent(current_ir_graph);
1166 /* Maybe we could also test whether optimizing the node can
1167 change the control graph. */
1168 if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1169 set_irg_dom_inconsistent(current_ir_graph);
1170 return optimize_in_place_2 (n);