added Rot detection
[libfirm] / ir / ir / iropt.c
1 /*
2  * Project:     libFIRM
3  * File name:   ir/ir/iropt.c
4  * Purpose:     iropt --- optimizations intertwined with IR construction.
5  * Author:      Christian Schaefer
6  * Modified by: Goetz Lindenmaier
7  * Created:
8  * CVS-ID:      $Id$
9  * Copyright:   (c) 1998-2003 Universität Karlsruhe
10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
11  */
12
13 #ifdef HAVE_CONFIG_H
14 # include "config.h"
15 #endif
16
17 #ifdef HAVE_ALLOCA_H
18 #include <alloca.h>
19 #endif
20 #ifdef HAVE_MALLOC_H
21 #include <malloc.h>
22 #endif
23 #ifdef HAVE_STRING_H
24 #include <string.h>
25 #endif
26
27 # include "irnode_t.h"
28 # include "irgraph_t.h"
29 # include "irmode_t.h"
30 # include "iropt_t.h"
31 # include "ircons_t.h"
32 # include "irgmod.h"
33 # include "irvrfy.h"
34 # include "tv_t.h"
35 # include "dbginfo_t.h"
36 # include "iropt_dbg.h"
37 # include "irflag_t.h"
38 # include "irhooks.h"
39 # include "irarch.h"
40 # include "hashptr.h"
41
42 /* Make types visible to allow most efficient access */
43 # include "entity_t.h"
44
45 /**
46  * Trivial INLINEable routine for copy propagation.
47  * Does follow Ids, needed to optimize INLINEd code.
48  */
49 static INLINE ir_node *
50 follow_Id (ir_node *n)
51 {
52   while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
53   return n;
54 }
55
56 /**
57  * return the value of a Constant
58  */
59 static tarval *computed_value_Const(ir_node *n)
60 {
61     return get_Const_tarval(n);
62 }
63
64 /**
65  * return the value of a 'sizeof' SymConst
66  */
67 static tarval *computed_value_SymConst(ir_node *n)
68 {
69   if ((get_SymConst_kind(n) == symconst_size) &&
70       (get_type_state(get_SymConst_type(n))) == layout_fixed)
71     return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
72   return tarval_bad;
73 }
74
75 /**
76  * return the value of an Add
77  */
78 static tarval *computed_value_Add(ir_node *n)
79 {
80   ir_node *a = get_Add_left(n);
81   ir_node *b = get_Add_right(n);
82
83   tarval *ta = value_of(a);
84   tarval *tb = value_of(b);
85
86   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
87     return tarval_add(ta, tb);
88
89   return tarval_bad;
90 }
91
92 /**
93  * return the value of a Sub
94  * Special case: a - a
95  */
96 static tarval *computed_value_Sub(ir_node *n)
97 {
98   ir_node *a = get_Sub_left(n);
99   ir_node *b = get_Sub_right(n);
100   tarval *ta;
101   tarval *tb;
102
103   /* a - a */
104   if (a == b && !is_Bad(a))
105     return get_tarval_null(get_irn_mode(n));
106
107   ta = value_of(a);
108   tb = value_of(b);
109
110   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
111     return tarval_sub(ta, tb);
112
113   return tarval_bad;
114 }
115
116 /**
117  * return the value of an unary Minus
118  */
119 static tarval *computed_value_Minus(ir_node *n)
120 {
121   ir_node *a = get_Minus_op(n);
122   tarval *ta = value_of(a);
123
124   if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
125     return tarval_neg(ta);
126
127   return tarval_bad;
128 }
129
130 /**
131  * return the value of a Mul
132  */
133 static tarval *computed_value_Mul(ir_node *n)
134 {
135   ir_node *a = get_Mul_left(n);
136   ir_node *b = get_Mul_right(n);
137
138   tarval *ta = value_of(a);
139   tarval *tb = value_of(b);
140
141   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
142     return tarval_mul(ta, tb);
143   } else {
144     /* a*0 = 0 or 0*b = 0:
145        calls computed_value recursive and returns the 0 with proper
146        mode. */
147     if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
148       return ta;
149     if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
150       return tb;
151   }
152   return tarval_bad;
153 }
154
155 /**
156  * return the value of a floating point Quot
157  */
158 static tarval *computed_value_Quot(ir_node *n)
159 {
160   ir_node *a = get_Quot_left(n);
161   ir_node *b = get_Quot_right(n);
162
163   tarval *ta = value_of(a);
164   tarval *tb = value_of(b);
165
166   /* This was missing in original implementation. Why? */
167   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
168     if (tb != get_mode_null(get_tarval_mode(tb)))   /* div by zero: return tarval_bad */
169       return tarval_quo(ta, tb);
170   }
171   return tarval_bad;
172 }
173
174 /**
175  * calculate the value of an integer Div of two nodes
176  * Special case: 0 / b
177  */
178 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
179 {
180   tarval *ta = value_of(a);
181   tarval *tb = value_of(b);
182
183   /* Compute c1 / c2 or 0 / a, a != 0 */
184   if (ta != tarval_bad) {
185     if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b))))   /* div by zero: return tarval_bad */
186       return tarval_div(ta, tb);
187     else if (ta == get_mode_null(get_tarval_mode(ta)))  /* 0 / b == 0 */
188       return ta;
189   }
190   return tarval_bad;
191 }
192
193 /**
194  * return the value of an integer Div
195  */
196 static tarval *computed_value_Div(ir_node *n)
197 {
198   return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
199 }
200
201 /**
202  * calculate the value of an integer Mod of two nodes
203  * Special case: a % 1
204  */
205 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
206 {
207   tarval *ta = value_of(a);
208   tarval *tb = value_of(b);
209
210   /* Compute c1 % c2 or a % 1 */
211   if (tb != tarval_bad) {
212     if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb))))   /* div by zero: return tarval_bad */
213       return tarval_mod(ta, tb);
214     else if (tb == get_mode_one(get_tarval_mode(tb)))    /* x mod 1 == 0 */
215       return get_mode_null(get_irn_mode(a));
216   }
217
218   return tarval_bad;
219 }
220
221 /**
222  * return the value of an integer Mod
223  */
224 static tarval *computed_value_Mod(ir_node *n)
225 {
226   return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
227 }
228
229 /**
230  * return the value of an Abs
231  */
232 static tarval *computed_value_Abs(ir_node *n)
233 {
234   ir_node *a = get_Abs_op(n);
235   tarval *ta = value_of(a);
236
237   if (ta != tarval_bad)
238     return tarval_abs(ta);
239
240   return tarval_bad;
241 }
242
243 /**
244  * return the value of an And
245  * Special case: a & 0, 0 & b
246  */
247 static tarval *computed_value_And(ir_node *n)
248 {
249   ir_node *a = get_And_left(n);
250   ir_node *b = get_And_right(n);
251
252   tarval *ta = value_of(a);
253   tarval *tb = value_of(b);
254
255   if ((ta != tarval_bad) && (tb != tarval_bad)) {
256     return tarval_and (ta, tb);
257   } else {
258     tarval *v;
259
260     if (   (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
261         || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
262       return v;
263     }
264   }
265   return tarval_bad;
266 }
267
268 /**
269  * return the value of an Or
270  * Special case: a | 1...1, 1...1 | b
271  */
272 static tarval *computed_value_Or(ir_node *n)
273 {
274   ir_node *a = get_Or_left(n);
275   ir_node *b = get_Or_right(n);
276
277   tarval *ta = value_of(a);
278   tarval *tb = value_of(b);
279
280   if ((ta != tarval_bad) && (tb != tarval_bad)) {
281     return tarval_or (ta, tb);
282   } else {
283     tarval *v;
284     if (   (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
285         || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
286       return v;
287     }
288   }
289   return tarval_bad;
290 }
291
292 /**
293  * return the value of an Eor
294  */
295 static tarval *computed_value_Eor(ir_node *n)
296 {
297   ir_node *a = get_Eor_left(n);
298   ir_node *b = get_Eor_right(n);
299
300   tarval *ta, *tb;
301
302   if (a == b)
303     return get_tarval_null(get_irn_mode(n));
304
305   ta = value_of(a);
306   tb = value_of(b);
307
308   if ((ta != tarval_bad) && (tb != tarval_bad)) {
309     return tarval_eor (ta, tb);
310   }
311   return tarval_bad;
312 }
313
314 /**
315  * return the value of a Not
316  */
317 static tarval *computed_value_Not(ir_node *n)
318 {
319   ir_node *a = get_Not_op(n);
320   tarval *ta = value_of(a);
321
322   if (ta != tarval_bad)
323     return tarval_not(ta);
324
325   return tarval_bad;
326 }
327
328 /**
329  * return the value of a Shl
330  */
331 static tarval *computed_value_Shl(ir_node *n)
332 {
333   ir_node *a = get_Shl_left(n);
334   ir_node *b = get_Shl_right(n);
335
336   tarval *ta = value_of(a);
337   tarval *tb = value_of(b);
338
339   if ((ta != tarval_bad) && (tb != tarval_bad)) {
340     return tarval_shl (ta, tb);
341   }
342   return tarval_bad;
343 }
344
345 /**
346  * return the value of a Shr
347  */
348 static tarval *computed_value_Shr(ir_node *n)
349 {
350   ir_node *a = get_Shr_left(n);
351   ir_node *b = get_Shr_right(n);
352
353   tarval *ta = value_of(a);
354   tarval *tb = value_of(b);
355
356   if ((ta != tarval_bad) && (tb != tarval_bad)) {
357     return tarval_shr (ta, tb);
358   }
359   return tarval_bad;
360 }
361
362 /**
363  * return the value of a Shrs
364  */
365 static tarval *computed_value_Shrs(ir_node *n)
366 {
367   ir_node *a = get_Shrs_left(n);
368   ir_node *b = get_Shrs_right(n);
369
370   tarval *ta = value_of(a);
371   tarval *tb = value_of(b);
372
373   if ((ta != tarval_bad) && (tb != tarval_bad)) {
374     return tarval_shrs (ta, tb);
375   }
376   return tarval_bad;
377 }
378
379 /**
380  * return the value of a Rot
381  */
382 static tarval *computed_value_Rot(ir_node *n)
383 {
384   ir_node *a = get_Rot_left(n);
385   ir_node *b = get_Rot_right(n);
386
387   tarval *ta = value_of(a);
388   tarval *tb = value_of(b);
389
390   if ((ta != tarval_bad) && (tb != tarval_bad)) {
391     return tarval_rot (ta, tb);
392   }
393   return tarval_bad;
394 }
395
396 /**
397  * return the value of a Conv
398  */
399 static tarval *computed_value_Conv(ir_node *n)
400 {
401   ir_node *a = get_Conv_op(n);
402   tarval *ta = value_of(a);
403
404   if (ta != tarval_bad)
405     return tarval_convert_to(ta, get_irn_mode(n));
406
407   return tarval_bad;
408 }
409
410 /**
411  * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
412  */
413 static tarval *computed_value_Proj(ir_node *n)
414 {
415   ir_node *a = get_Proj_pred(n);
416   ir_node *aa, *ab;
417   long proj_nr;
418
419   /* Optimize Cmp nodes.
420      This performs a first step of unreachable code elimination.
421      Proj can not be computed, but folding a Cmp above the Proj here is
422      not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
423      only 1 is used.
424      There are several case where we can evaluate a Cmp node:
425      1. The nodes compared are both the same.  If we compare for
426         equal, greater equal, ... this will return true, else it
427         will return false.  This step relies on cse.
428      2. The predecessors of Cmp are target values.  We can evaluate
429         the Cmp.
430      3. The predecessors are Allocs or void* constants.  Allocs never
431         return NULL, they raise an exception.   Therefore we can predict
432         the Cmp result. */
433   switch (get_irn_opcode(a)) {
434   case iro_Cmp:
435     aa = get_Cmp_left(a);
436     ab = get_Cmp_right(a);
437     proj_nr = get_Proj_proj(n);
438
439     if (aa == ab && !mode_is_float(get_irn_mode(aa))) { /* 1.: */
440       /* BEWARE: a == a is NOT always True for floating Point!!! */
441       /* This is a trick with the bits used for encoding the Cmp
442          Proj numbers, the following statement is not the same:
443       return new_tarval_from_long (proj_nr == Eq, mode_b) */
444       return new_tarval_from_long (proj_nr & Eq, mode_b);
445     } else {
446       tarval *taa = value_of(aa);
447       tarval *tab = value_of(ab);
448
449       if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
450         /* strange checks... */
451         pnc_number flags = tarval_cmp (taa, tab);
452         if (flags != False) {
453           return new_tarval_from_long (proj_nr & flags, mode_b);
454         }
455       } else {  /* check for 3.: */
456         ir_node *aaa = skip_Id(skip_Proj(aa));
457         ir_node *aba = skip_Id(skip_Proj(ab));
458
459         if (   (   (/* aa is ProjP and aaa is Alloc */
460                        (get_irn_op(aa) == op_Proj)
461                     && (mode_is_reference(get_irn_mode(aa)))
462                     && (get_irn_op(aaa) == op_Alloc))
463                 && (   (/* ab is constant void */
464                            (get_irn_op(ab) == op_Const)
465                         && (mode_is_reference(get_irn_mode(ab)))
466                         && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
467                     || (/* ab is other Alloc */
468                            (get_irn_op(ab) == op_Proj)
469                         && (mode_is_reference(get_irn_mode(ab)))
470                         && (get_irn_op(aba) == op_Alloc)
471                         && (aaa != aba))))
472             || (/* aa is void and aba is Alloc */
473                    (get_irn_op(aa) == op_Const)
474                 && (mode_is_reference(get_irn_mode(aa)))
475                 && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
476                 && (get_irn_op(ab) == op_Proj)
477                 && (mode_is_reference(get_irn_mode(ab)))
478                 && (get_irn_op(aba) == op_Alloc)))
479           /* 3.: */
480           return new_tarval_from_long (proj_nr & Ne, mode_b);
481       }
482     }
483     break;
484
485   case iro_DivMod:
486     /* compute either the Div or the Mod part */
487     proj_nr = get_Proj_proj(n);
488     if (proj_nr == pn_DivMod_res_div)
489       return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
490     else if (proj_nr == pn_DivMod_res_mod)
491       return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
492     break;
493
494   case iro_Div:
495     if (get_Proj_proj(n) == pn_Div_res)
496       return computed_value(a);
497     break;
498
499   case iro_Mod:
500     if (get_Proj_proj(n) == pn_Mod_res)
501       return computed_value(a);
502     break;
503
504   default:
505     return tarval_bad;
506   }
507   return tarval_bad;
508 }
509
510 /**
511  * calculate the value of a Mux: can be evaluated, if the
512  * sel and the right input are known
513  */
514 static tarval *computed_value_Mux(ir_node *n)
515 {
516   ir_node *sel = get_Mux_sel(n);
517   tarval *ts = value_of(sel);
518
519   if (ts == get_tarval_b_true()) {
520     ir_node *v = get_Mux_true(n);
521     return value_of(v);
522   }
523   else if (ts == get_tarval_b_false()) {
524     ir_node *v = get_Mux_false(n);
525     return value_of(v);
526   }
527   return tarval_bad;
528 }
529
530 /**
531  * If the parameter n can be computed, return its value, else tarval_bad.
532  * Performs constant folding.
533  *
534  * @param n  The node this should be evaluated
535  */
536 tarval *computed_value(ir_node *n)
537 {
538   if (n->op->computed_value)
539     return n->op->computed_value(n);
540   return tarval_bad;
541 }
542
543 /**
544  * set the default computed_value evaluator
545  */
546 static ir_op *firm_set_default_computed_value(ir_op *op)
547 {
548 #define CASE(a)                               \
549   case iro_##a:                               \
550     op->computed_value  = computed_value_##a; \
551     break
552
553   switch (op->code) {
554   CASE(Const);
555   CASE(SymConst);
556   CASE(Add);
557   CASE(Sub);
558   CASE(Minus);
559   CASE(Mul);
560   CASE(Quot);
561   CASE(Div);
562   CASE(Mod);
563   CASE(Abs);
564   CASE(And);
565   CASE(Or);
566   CASE(Eor);
567   CASE(Not);
568   CASE(Shl);
569   CASE(Shr);
570   CASE(Shrs);
571   CASE(Rot);
572   CASE(Conv);
573   CASE(Proj);
574   CASE(Mux);
575   default:
576     op->computed_value  = NULL;
577   }
578
579   return op;
580 #undef CASE
581 }
582
583 #if 0
584 /* returns 1 if the a and b are pointers to different locations. */
585 static bool
586 different_identity (ir_node *a, ir_node *b)
587 {
588   assert (mode_is_reference(get_irn_mode (a))
589           && mode_is_reference(get_irn_mode (b)));
590
591   if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
592     ir_node *a1 = get_Proj_pred (a);
593     ir_node *b1 = get_Proj_pred (b);
594     if (a1 != b1 && get_irn_op (a1) == op_Alloc
595                 && get_irn_op (b1) == op_Alloc)
596       return 1;
597   }
598   return 0;
599 }
600 #endif
601
602 static ir_node *equivalent_node_Block(ir_node *n)
603 {
604   ir_node *oldn = n;
605
606   /* The Block constructor does not call optimize, but mature_immBlock
607      calls the optimization. */
608   assert(get_Block_matured(n));
609
610   /* Straightening: a single entry Block following a single exit Block
611      can be merged, if it is not the Start block. */
612   /* !!! Beware, all Phi-nodes of n must have been optimized away.
613      This should be true, as the block is matured before optimize is called.
614      But what about Phi-cycles with the Phi0/Id that could not be resolved?
615      Remaining Phi nodes are just Ids. */
616    if ((get_Block_n_cfgpreds(n) == 1) &&
617        (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
618      ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
619      if (predblock == oldn) {
620        /* Jmp jumps into the block it is in -- deal self cycle. */
621        n = set_Block_dead(n);
622        DBG_OPT_DEAD(oldn, n);
623      } else if (get_opt_control_flow_straightening()) {
624        n = predblock;
625        DBG_OPT_STG(oldn, n);
626      }
627    }
628    else if ((get_Block_n_cfgpreds(n) == 1) &&
629             (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
630      ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
631      if (predblock == oldn) {
632        /* Jmp jumps into the block it is in -- deal self cycle. */
633        n = set_Block_dead(n);
634        DBG_OPT_DEAD(oldn, n);
635      }
636    }
637    else if ((get_Block_n_cfgpreds(n) == 2) &&
638             (get_opt_control_flow_weak_simplification())) {
639     /* Test whether Cond jumps twice to this block
640        @@@ we could do this also with two loops finding two preds from several ones. */
641     ir_node *a = get_Block_cfgpred(n, 0);
642     ir_node *b = get_Block_cfgpred(n, 1);
643
644     if ((get_irn_op(a) == op_Proj) &&
645         (get_irn_op(b) == op_Proj) &&
646         (get_Proj_pred(a) == get_Proj_pred(b)) &&
647         (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
648         (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
649       /* Also a single entry Block following a single exit Block.  Phis have
650          twice the same operand and will be optimized away. */
651       n = get_nodes_block(a);
652       DBG_OPT_IFSIM(oldn, a, b, n);
653     }
654   } else if (get_opt_unreachable_code() &&
655              (n != current_ir_graph->start_block) &&
656              (n != current_ir_graph->end_block)     ) {
657     int i, n_cfg = get_Block_n_cfgpreds(n);
658
659     /* If all inputs are dead, this block is dead too, except if it is
660        the start or end block.  This is a step of unreachable code
661        elimination */
662     for (i = 0; i < n_cfg; i++) {
663       ir_node *pred = get_Block_cfgpred(n, i);
664       ir_node *pred_blk;
665
666       if (is_Bad(pred)) continue;
667       pred_blk = get_nodes_block(pred);
668
669       if (is_Block_dead(pred_blk)) continue;
670
671       if (pred_blk != n) {
672         /* really found a living input */
673         break;
674       }
675     }
676     if (i == n_cfg)
677       n = set_Block_dead(n);
678   }
679
680   return n;
681 }
682
683 /**
684  * Returns a equivalent node for a Jmp, a Bad :-)
685  * Of course this only happens if the Block of the Jmp is Bad.
686  */
687 static ir_node *equivalent_node_Jmp(ir_node *n)
688 {
689   /* GL: Why not same for op_Raise?? */
690   /* unreachable code elimination */
691   if (is_Block_dead(get_nodes_block(n)))
692     n = new_Bad();
693
694   return n;
695 }
696
697 static ir_node *equivalent_node_Cond(ir_node *n)
698 {
699   /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
700      See cases for iro_Cond and iro_Proj in transform_node. */
701   return n;
702 }
703
704 /**
705  * optimize operations that are commutative and have neutral 0,
706  * so a op 0 = 0 op a = a.
707  */
708 static ir_node *equivalent_node_neutral_zero(ir_node *n)
709 {
710   ir_node *oldn = n;
711
712   ir_node *a = get_binop_left(n);
713   ir_node *b = get_binop_right(n);
714
715   tarval *tv;
716   ir_node *on;
717
718   /* After running compute_node there is only one constant predecessor.
719      Find this predecessors value and remember the other node: */
720   if ((tv = value_of(a)) != tarval_bad) {
721     on = b;
722   } else if ((tv = value_of(b)) != tarval_bad) {
723     on = a;
724   } else
725     return n;
726
727   /* If this predecessors constant value is zero, the operation is
728      unnecessary. Remove it: */
729   if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
730     n = on;
731
732     DBG_OPT_ALGSIM1(oldn, a, b, n);
733   }
734
735   return n;
736 }
737
738 #define equivalent_node_Add  equivalent_node_neutral_zero
739 #define equivalent_node_Eor  equivalent_node_neutral_zero
740
741 /**
742  * optimize operations that are not commutative but have neutral 0 on left,
743  * so a op 0 = a.
744  */
745 static ir_node *equivalent_node_left_zero(ir_node *n)
746 {
747   ir_node *oldn = n;
748
749   ir_node *a = get_binop_left(n);
750   ir_node *b = get_binop_right(n);
751
752   if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
753     n = a;
754
755     DBG_OPT_ALGSIM1(oldn, a, b, n);
756   }
757
758   return n;
759 }
760
761 #define equivalent_node_Sub   equivalent_node_left_zero
762 #define equivalent_node_Shl   equivalent_node_left_zero
763 #define equivalent_node_Shr   equivalent_node_left_zero
764 #define equivalent_node_Shrs  equivalent_node_left_zero
765 #define equivalent_node_Rot   equivalent_node_left_zero
766
767 /**
768  * Er, a "symmetic unop", ie op(op(n)) = n.
769  */
770 static ir_node *equivalent_node_symmetric_unop(ir_node *n)
771 {
772   ir_node *oldn = n;
773   ir_node *pred = get_unop_op(n);
774
775   /* optimize symmetric unop */
776   if (get_irn_op(pred) == get_irn_op(n)) {
777     n = get_unop_op(pred);
778     DBG_OPT_ALGSIM2(oldn, pred, n);
779   }
780   return n;
781 }
782
783 /* NotNot x == x */
784 #define equivalent_node_Not    equivalent_node_symmetric_unop
785
786 /* --x == x */  /* ??? Is this possible or can --x raise an
787                        out of bounds exception if min =! max? */
788 #define equivalent_node_Minus  equivalent_node_symmetric_unop
789
790 /**
791  * Optimize a * 1 = 1 * a = a.
792  */
793 static ir_node *equivalent_node_Mul(ir_node *n)
794 {
795   ir_node *oldn = n;
796
797   ir_node *a = get_Mul_left(n);
798   ir_node *b = get_Mul_right(n);
799
800   /* Mul is commutative and has again an other neutral element. */
801   if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
802     n = b;
803     DBG_OPT_ALGSIM1(oldn, a, b, n);
804   } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
805     n = a;
806     DBG_OPT_ALGSIM1(oldn, a, b, n);
807   }
808   return n;
809 }
810
811 /**
812  * Optimize a / 1 = a.
813  */
814 static ir_node *equivalent_node_Div(ir_node *n)
815 {
816   ir_node *a = get_Div_left(n);
817   ir_node *b = get_Div_right(n);
818
819   /* Div is not commutative. */
820   if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
821     /* Turn Div into a tuple (mem, bad, a) */
822     ir_node *mem = get_Div_mem(n);
823     turn_into_tuple(n, 3);
824     set_Tuple_pred(n, pn_Div_M,        mem);
825     set_Tuple_pred(n, pn_Div_X_except, new_Bad());        /* no exception */
826     set_Tuple_pred(n, pn_Div_res,      a);
827   }
828   return n;
829 }
830
831 /**
832  * Optimize a / 1 = a.
833  */
834 static ir_node *equivalent_node_DivMod(ir_node *n)
835 {
836   ir_node *a = get_DivMod_left(n);
837   ir_node *b = get_DivMod_right(n);
838
839   /* Div is not commutative. */
840   if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
841     /* Turn DivMod into a tuple (mem, bad, a, 0) */
842     ir_node *mem = get_Div_mem(n);
843     ir_mode *mode = get_irn_mode(b);
844
845     turn_into_tuple(n, 4);
846     set_Tuple_pred(n, pn_DivMod_M,        mem);
847     set_Tuple_pred(n, pn_DivMod_X_except, new_Bad());        /* no exception */
848     set_Tuple_pred(n, pn_DivMod_res_div,  a);
849     set_Tuple_pred(n, pn_DivMod_res_mod,  new_Const(mode, get_mode_null(mode)));
850   }
851   return n;
852 }
853
854 /**
855  * Use algebraic simplification a | a = a | 0 = 0 | a = a.
856  */
857 static ir_node *equivalent_node_Or(ir_node *n)
858 {
859   ir_node *oldn = n;
860
861   ir_node *a = get_Or_left(n);
862   ir_node *b = get_Or_right(n);
863
864   if (a == b) {
865     n = a;    /* Or has it's own neutral element */
866   } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
867     n = b;
868     DBG_OPT_ALGSIM1(oldn, a, b, n);
869   } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
870     n = a;
871     DBG_OPT_ALGSIM1(oldn, a, b, n);
872   }
873
874   return n;
875 }
876
877 /**
878  * Optimize a & 0b1...1 = 0b1...1 & a =  a & a = a.
879  */
880 static ir_node *equivalent_node_And(ir_node *n)
881 {
882   ir_node *oldn = n;
883
884   ir_node *a = get_And_left(n);
885   ir_node *b = get_And_right(n);
886
887   if (a == b) {
888     n = a;    /* And has it's own neutral element */
889   } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
890     n = b;
891     DBG_OPT_ALGSIM1(oldn, a, b, n);
892   } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
893     n = a;
894     DBG_OPT_ALGSIM1(oldn, a, b, n);
895   }
896   return n;
897 }
898
899 /**
900  * Try to remove useless conv's:
901  */
902 static ir_node *equivalent_node_Conv(ir_node *n)
903 {
904   ir_node *oldn = n;
905   ir_node *a = get_Conv_op(n);
906   ir_node *b;
907
908   ir_mode *n_mode = get_irn_mode(n);
909   ir_mode *a_mode = get_irn_mode(a);
910
911   if (n_mode == a_mode) { /* No Conv necessary */
912     n = a;
913     DBG_OPT_ALGSIM3(oldn, a, n);
914   } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
915     ir_mode *b_mode;
916
917     b = get_Conv_op(a);
918     n_mode = get_irn_mode(n);
919     b_mode = get_irn_mode(b);
920
921     if (n_mode == b_mode) {
922       if (n_mode == mode_b) {
923         n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
924     DBG_OPT_ALGSIM1(oldn, a, b, n);
925       }
926       else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
927         if (smaller_mode(b_mode, a_mode)){
928           n = b;        /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
929       DBG_OPT_ALGSIM1(oldn, a, b, n);
930         }
931       }
932     }
933   }
934   return n;
935 }
936
937 /**
938  * A Cast may be removed if the type of the previous node
939  * is already to type of the Cast.
940  */
941 static ir_node *equivalent_node_Cast(ir_node *n) {
942   ir_node *pred = get_Cast_op(n);
943   if (get_irn_type(pred) == get_Cast_type(n))
944     n = pred;
945   return n;
946 }
947
948 /* Several optimizations:
949    - no Phi in start block.
950    - remove Id operators that are inputs to Phi
951    - fold Phi-nodes, iff they have only one predecessor except
952            themselves.
953 */
954 static ir_node *equivalent_node_Phi(ir_node *n)
955 {
956   int i, n_preds;
957
958   ir_node *oldn = n;
959   ir_node *block = NULL;     /* to shutup gcc */
960   ir_node *first_val = NULL; /* to shutup gcc */
961   ir_node *scnd_val = NULL;  /* to shutup gcc */
962
963   if (!get_opt_normalize()) return n;
964
965   n_preds = get_Phi_n_preds(n);
966
967   block = get_nodes_block(n);
968   /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
969      assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
970   if ((is_Block_dead(block)) ||                  /* Control dead */
971       (block == current_ir_graph->start_block))  /* There should be no Phi nodes */
972     return new_Bad();                            /* in the Start Block. */
973
974   if (n_preds == 0) return n;           /* Phi of dead Region without predecessors. */
975
976 #if 0
977   /* first we test for a special case: */
978   /* Confirm is a special node fixing additional information for a
979      value that is known at a certain point.  This is useful for
980      dataflow analysis. */
981   if (n_preds == 2) {
982     ir_node *a = get_Phi_pred(n, 0);
983     ir_node *b = get_Phi_pred(n, 1);
984     if (   (get_irn_op(a) == op_Confirm)
985         && (get_irn_op(b) == op_Confirm)
986         && follow_Id (get_irn_n(a, 0) == get_irn_n(b, 0))
987         && (get_irn_n(a, 1) == get_irn_n (b, 1))
988         && (a->data.num == (~b->data.num & irpn_True) )) {
989       return get_irn_n(a, 0);
990     }
991   }
992 #endif
993
994   /* If the Block has a Bad pred, we also have one. */
995   for (i = 0;  i < n_preds;  ++i)
996     if (is_Bad (get_Block_cfgpred(block, i)))
997       set_Phi_pred(n, i, new_Bad());
998
999   /* Find first non-self-referencing input */
1000   for (i = 0;  i < n_preds;  ++i) {
1001     first_val = get_Phi_pred(n, i);
1002     if (   (first_val != n)                            /* not self pointer */
1003 #if 1
1004         && (get_irn_op(first_val) != op_Bad)
1005 #endif
1006            ) {        /* value not dead */
1007       break;          /* then found first value. */
1008     }
1009   }
1010
1011   /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
1012   if (i >= n_preds) { return new_Bad(); }
1013
1014   scnd_val = NULL;
1015
1016   /* follow_Id () for rest of inputs, determine if any of these
1017      are non-self-referencing */
1018   while (++i < n_preds) {
1019     scnd_val = get_Phi_pred(n, i);
1020     if (   (scnd_val != n)
1021         && (scnd_val != first_val)
1022 #if 1
1023         && (get_irn_op(scnd_val) != op_Bad)
1024 #endif
1025            ) {
1026       break;
1027     }
1028   }
1029
1030   /* Fold, if no multiple distinct non-self-referencing inputs */
1031   if (i >= n_preds) {
1032     n = first_val;
1033     DBG_OPT_PHI(oldn, first_val, n);
1034   } else {
1035     /* skip the remaining Ids (done in get_Phi_pred). */
1036     /* superfluous, since we walk all to propagate Block's Bads.
1037        while (++i < n_preds) get_Phi_pred(n, i);     */
1038   }
1039   return n;
1040 }
1041
1042 /**
1043  * optimize Proj(Tuple) and gigo for ProjX in Bad block
1044  */
1045 static ir_node *equivalent_node_Proj(ir_node *n)
1046 {
1047   ir_node *oldn = n;
1048
1049   ir_node *a = get_Proj_pred(n);
1050
1051   if ( get_irn_op(a) == op_Tuple) {
1052     /* Remove the Tuple/Proj combination. */
1053     if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1054       n = get_Tuple_pred(a, get_Proj_proj(n));
1055       DBG_OPT_TUPLE(oldn, a, n);
1056     } else {
1057       assert(0); /* This should not happen! */
1058       n = new_Bad();
1059     }
1060   } else if (get_irn_mode(n) == mode_X &&
1061              is_Block_dead(get_nodes_block(n))) {
1062     /* Remove dead control flow -- early gigo. */
1063     n = new_Bad();
1064   }
1065   return n;
1066 }
1067
1068 /**
1069  * Remove Id's.
1070  */
1071 static ir_node *equivalent_node_Id(ir_node *n)
1072 {
1073   ir_node *oldn = n;
1074
1075   n = follow_Id(n);
1076   DBG_OPT_ID(oldn, n);
1077   return n;
1078 }
1079
1080 /**
1081  * optimize a Mux
1082  */
1083 static ir_node *equivalent_node_Mux(ir_node *n)
1084 {
1085   ir_node *sel = get_Mux_sel(n);
1086   tarval *ts = value_of(sel);
1087
1088   if (ts == get_tarval_b_true())
1089     return get_Mux_true(n);
1090   else if (ts == get_tarval_b_false())
1091     return get_Mux_false(n);
1092
1093   return n;
1094 }
1095
1096 /**
1097  * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1098  * perform no actual computation, as, e.g., the Id nodes.  It does not create
1099  * new nodes.  It is therefore safe to free n if the node returned is not n.
1100  * If a node returns a Tuple we can not just skip it.  If the size of the
1101  * in array fits, we transform n into a tuple (e.g., Div).
1102  */
1103 ir_node *
1104 equivalent_node(ir_node *n)
1105 {
1106   if (n->op->equivalent_node)
1107     return n->op->equivalent_node(n);
1108   return n;
1109 }
1110
1111 /**
1112  * set the default equivalent node operation
1113  */
1114 static ir_op *firm_set_default_equivalent_node(ir_op *op)
1115 {
1116 #define CASE(a)                                 \
1117   case iro_##a:                                 \
1118     op->equivalent_node  = equivalent_node_##a; \
1119     break
1120
1121   switch (op->code) {
1122   CASE(Block);
1123   CASE(Jmp);
1124   CASE(Cond);
1125   CASE(Or);
1126   CASE(Add);
1127   CASE(Eor);
1128   CASE(Sub);
1129   CASE(Shl);
1130   CASE(Shr);
1131   CASE(Shrs);
1132   CASE(Rot);
1133   CASE(Not);
1134   CASE(Minus);
1135   CASE(Mul);
1136   CASE(Div);
1137   CASE(DivMod);
1138   CASE(And);
1139   CASE(Conv);
1140   CASE(Cast);
1141   CASE(Phi);
1142   CASE(Proj);
1143   CASE(Id);
1144   CASE(Mux);
1145   default:
1146     op->equivalent_node  = NULL;
1147   }
1148
1149   return op;
1150 #undef CASE
1151 }
1152
1153 /**
1154  * Do node specific optimizations of nodes predecessors.
1155  */
1156 static void
1157 optimize_preds(ir_node *n) {
1158   ir_node *a = NULL, *b = NULL;
1159
1160   /* get the operands we will work on for simple cases. */
1161   if (is_binop(n)) {
1162     a = get_binop_left(n);
1163     b = get_binop_right(n);
1164   } else if (is_unop(n)) {
1165     a = get_unop_op(n);
1166   }
1167
1168   switch (get_irn_opcode(n)) {
1169
1170   case iro_Cmp:
1171     /* We don't want Cast as input to Cmp. */
1172     if (get_irn_op(a) == op_Cast) {
1173       a = get_Cast_op(a);
1174       set_Cmp_left(n, a);
1175     }
1176     if (get_irn_op(b) == op_Cast) {
1177       b = get_Cast_op(b);
1178       set_Cmp_right(n, b);
1179     }
1180     break;
1181
1182   default: break;
1183   } /* end switch */
1184 }
1185
1186 /**
1187  * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1188  * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)) if possible.
1189  */
1190 static ir_node *transform_node_AddSub(ir_node *n)
1191 {
1192   ir_mode *mode = get_irn_mode(n);
1193
1194   if (mode_is_reference(mode)) {
1195     ir_node *left  = get_binop_left(n);
1196     ir_node *right = get_binop_right(n);
1197     int ref_bits   = get_mode_size_bits(mode);
1198
1199     if (get_irn_op(left) == op_Conv) {
1200       ir_mode *mode = get_irn_mode(left);
1201       int bits      = get_mode_size_bits(mode);
1202
1203       if (ref_bits == bits &&
1204           mode_is_int(mode) &&
1205           get_mode_arithmetic(mode) == irma_twos_complement) {
1206         ir_node *pre      = get_Conv_op(left);
1207         ir_mode *pre_mode = get_irn_mode(pre);
1208
1209         if (mode_is_int(pre_mode) &&
1210             get_mode_size_bits(pre_mode) == bits &&
1211             get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1212           /* ok, this conv just changes to sign, moreover the calculation
1213            * is done with same number of bits as our address mode, so
1214            * we can ignore the conv as address calculation can be viewed
1215            * as either signed or unsigned
1216            */
1217           set_binop_left(n, pre);
1218         }
1219       }
1220     }
1221
1222     if (get_irn_op(right) == op_Conv) {
1223       ir_mode *mode = get_irn_mode(right);
1224       int bits      = get_mode_size_bits(mode);
1225
1226       if (ref_bits == bits &&
1227           mode_is_int(mode) &&
1228           get_mode_arithmetic(mode) == irma_twos_complement) {
1229         ir_node *pre      = get_Conv_op(right);
1230         ir_mode *pre_mode = get_irn_mode(pre);
1231
1232         if (mode_is_int(pre_mode) &&
1233             get_mode_size_bits(pre_mode) == bits &&
1234             get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1235           /* ok, this conv just changes to sign, moreover the calculation
1236            * is done with same number of bits as our address mode, so
1237            * we can ignore the conv as address calculation can be viewed
1238            * as either signed or unsigned
1239            */
1240           set_binop_right(n, pre);
1241         }
1242       }
1243     }
1244   }
1245   return n;
1246 }
1247
1248 #define transform_node_Add      transform_node_AddSub
1249 #define transform_node_Sub      transform_node_AddSub
1250
1251 /** Do architecture dependend optimizations on Mul nodes */
1252 static ir_node *transform_node_Mul(ir_node *n) {
1253   return arch_dep_replace_mul_with_shifts(n);
1254 }
1255
1256 static ir_node *transform_node_Div(ir_node *n)
1257 {
1258   tarval *tv = value_of(n);
1259   ir_node *value = n;
1260
1261   /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1262
1263   if (tv != tarval_bad)
1264     value = new_Const(get_tarval_mode(tv), tv);
1265   else /* Try architecture dependand optimization */
1266     value = arch_dep_replace_div_by_const(n);
1267
1268   if (value != n) {
1269     /* Turn Div into a tuple (mem, bad, value) */
1270     ir_node *mem = get_Div_mem(n);
1271
1272     turn_into_tuple(n, 3);
1273     set_Tuple_pred(n, pn_Div_M, mem);
1274     set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1275     set_Tuple_pred(n, pn_Div_res, value);
1276   }
1277   return n;
1278 }
1279
1280 static ir_node *transform_node_Mod(ir_node *n)
1281 {
1282   tarval *tv = value_of(n);
1283   ir_node *value = n;
1284
1285   /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1286
1287   if (tv != tarval_bad)
1288     value = new_Const(get_tarval_mode(tv), tv);
1289   else /* Try architecture dependand optimization */
1290     value = arch_dep_replace_mod_by_const(n);
1291
1292   if (value != n) {
1293     /* Turn Mod into a tuple (mem, bad, value) */
1294     ir_node *mem = get_Mod_mem(n);
1295
1296     turn_into_tuple(n, 3);
1297     set_Tuple_pred(n, pn_Mod_M, mem);
1298     set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1299     set_Tuple_pred(n, pn_Mod_res, value);
1300   }
1301   return n;
1302 }
1303
1304 static ir_node *transform_node_DivMod(ir_node *n)
1305 {
1306   int evaluated = 0;
1307
1308   ir_node *a = get_DivMod_left(n);
1309   ir_node *b = get_DivMod_right(n);
1310   ir_mode *mode = get_irn_mode(a);
1311   tarval *ta = value_of(a);
1312   tarval *tb = value_of(b);
1313
1314   if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
1315     return n;
1316
1317   /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1318
1319   if (tb != tarval_bad) {
1320     if (tb == get_mode_one(get_tarval_mode(tb))) {
1321       b = new_Const (mode, get_mode_null(mode));
1322       evaluated = 1;
1323     } else if (ta != tarval_bad) {
1324       tarval *resa, *resb;
1325       resa = tarval_div (ta, tb);
1326       if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
1327                                         Jmp for X result!? */
1328       resb = tarval_mod (ta, tb);
1329       if (resb == tarval_bad) return n; /* Causes exception! */
1330       a = new_Const (mode, resa);
1331       b = new_Const (mode, resb);
1332       evaluated = 1;
1333     }
1334     else { /* Try architecture dependand optimization */
1335       arch_dep_replace_divmod_by_const(&a, &b, n);
1336       evaluated = a != NULL;
1337     }
1338   } else if (ta == get_mode_null(mode)) {
1339     /* 0 / non-Const = 0 */
1340     b = a;
1341     evaluated = 1;
1342   }
1343
1344   if (evaluated) { /* replace by tuple */
1345     ir_node *mem = get_DivMod_mem(n);
1346     turn_into_tuple(n, 4);
1347     set_Tuple_pred(n, pn_DivMod_M,        mem);
1348     set_Tuple_pred(n, pn_DivMod_X_except, new_Bad());  /* no exception */
1349     set_Tuple_pred(n, pn_DivMod_res_div,  a);
1350     set_Tuple_pred(n, pn_DivMod_res_mod,  b);
1351     assert(get_nodes_block(n));
1352   }
1353
1354   return n;
1355 }
1356
1357 static ir_node *transform_node_Cond(ir_node *n)
1358 {
1359   /* Replace the Cond by a Jmp if it branches on a constant
1360      condition. */
1361   ir_node *jmp;
1362   ir_node *a = get_Cond_selector(n);
1363   tarval *ta = value_of(a);
1364
1365   if ((ta != tarval_bad) &&
1366       (get_irn_mode(a) == mode_b) &&
1367       (get_opt_unreachable_code())) {
1368     /* It's a boolean Cond, branching on a boolean constant.
1369                Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
1370     jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
1371     turn_into_tuple(n, 2);
1372     if (ta == tarval_b_true) {
1373       set_Tuple_pred(n, pn_Cond_false, new_Bad());
1374       set_Tuple_pred(n, pn_Cond_true, jmp);
1375     } else {
1376       set_Tuple_pred(n, pn_Cond_false, jmp);
1377       set_Tuple_pred(n, pn_Cond_true, new_Bad());
1378     }
1379     /* We might generate an endless loop, so keep it alive. */
1380     add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1381   } else if ((ta != tarval_bad) &&
1382              (get_irn_mode(a) == mode_Iu) &&
1383              (get_Cond_kind(n) == dense) &&
1384              (get_opt_unreachable_code())) {
1385     /* I don't want to allow Tuples smaller than the biggest Proj.
1386        Also this tuple might get really big...
1387        I generate the Jmp here, and remember it in link.  Link is used
1388        when optimizing Proj. */
1389     set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_block(n)));
1390     /* We might generate an endless loop, so keep it alive. */
1391     add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
1392   } else if ((get_irn_op(a) == op_Eor)
1393              && (get_irn_mode(a) == mode_b)
1394              && (classify_tarval(value_of(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
1395     /* The Eor is a negate.  Generate a new Cond without the negate,
1396        simulate the negate by exchanging the results. */
1397     set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1398                                get_Eor_left(a)));
1399   } else if ((get_irn_op(a) == op_Not)
1400              && (get_irn_mode(a) == mode_b)) {
1401     /* A Not before the Cond.  Generate a new Cond without the Not,
1402        simulate the Not by exchanging the results. */
1403     set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_block(n),
1404                                get_Not_op(a)));
1405   }
1406   return n;
1407 }
1408
1409 /**
1410  * Transform an Eor.
1411  */
1412 static ir_node *transform_node_Eor(ir_node *n)
1413 {
1414   ir_node *a = get_Eor_left(n);
1415   ir_node *b = get_Eor_right(n);
1416
1417   if ((get_irn_mode(n) == mode_b)
1418       && (get_irn_op(a) == op_Proj)
1419       && (get_irn_mode(a) == mode_b)
1420       && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
1421       && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1422     /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
1423     n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1424                    mode_b, get_negated_pnc(get_Proj_proj(a)));
1425   else if ((get_irn_mode(n) == mode_b)
1426            && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE))
1427     /* The Eor is a Not. Replace it by a Not. */
1428     /*   ????!!!Extend to bitfield 1111111. */
1429     n = new_r_Not(current_ir_graph, get_nodes_block(n), a, mode_b);
1430
1431   return n;
1432 }
1433
1434 /**
1435  * Transform a boolean Not.
1436  */
1437 static ir_node *transform_node_Not(ir_node *n)
1438 {
1439   ir_node *a = get_Not_op(n);
1440
1441   if (   (get_irn_mode(n) == mode_b)
1442       && (get_irn_op(a) == op_Proj)
1443       && (get_irn_mode(a) == mode_b)
1444       && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
1445     /* We negate a Cmp. The Cmp has the negated result anyways! */
1446     n = new_r_Proj(current_ir_graph, get_nodes_block(n), get_Proj_pred(a),
1447                    mode_b, get_negated_pnc(get_Proj_proj(a)));
1448
1449   return n;
1450 }
1451
1452 /**
1453  * Transform a Cast of a Const into a new Const
1454  */
1455 static ir_node *transform_node_Cast(ir_node *n) {
1456   ir_node *pred = get_Cast_op(n);
1457   type *tp = get_irn_type(pred);
1458
1459   if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
1460     n = new_rd_Const_type(NULL, current_ir_graph, get_nodes_block(pred), get_irn_mode(pred),
1461               get_Const_tarval(pred), tp);
1462   } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
1463     n = new_rd_SymConst_type(NULL, current_ir_graph, get_nodes_block(pred), get_SymConst_symbol(pred),
1464                  get_SymConst_kind(pred), tp);
1465   }
1466   return n;
1467 }
1468
1469 /**
1470  * Transform a Div/Mod/DivMod with a non-zero constant. Must be
1471  * done here instead of equivalent node because it creates new
1472  * nodes.
1473  * Removes the exceptions and routes the memory to the NoMem node.
1474  *
1475  * Further, it optimizes jump tables by removing all impossible cases.
1476  */
1477 static ir_node *transform_node_Proj(ir_node *proj)
1478 {
1479   ir_node *n = get_Proj_pred(proj);
1480   ir_node *b;
1481   tarval *tb;
1482   long proj_nr;
1483
1484   switch (get_irn_opcode(n)) {
1485   case iro_Div:
1486     b  = get_Div_right(n);
1487     tb = value_of(b);
1488
1489     if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1490       proj_nr = get_Proj_proj(proj);
1491
1492       /* this node may float */
1493       set_irn_pinned(n, op_pin_state_floats);
1494
1495       if (proj_nr == pn_Div_X_except) {
1496         /* we found an exception handler, remove it */
1497         return new_Bad();
1498       } else {
1499         /* the memory Proj can be removed */
1500         ir_node *res = get_Div_mem(n);
1501         set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1502         if (proj_nr == pn_Div_M)
1503           return res;
1504       }
1505     }
1506     break;
1507   case iro_Mod:
1508     b  = get_Mod_right(n);
1509     tb = value_of(b);
1510
1511     if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1512       proj_nr = get_Proj_proj(proj);
1513
1514       /* this node may float */
1515       set_irn_pinned(n, op_pin_state_floats);
1516
1517       if (proj_nr == pn_Mod_X_except) {
1518         /* we found an exception handler, remove it */
1519         return new_Bad();
1520       } else {
1521         /* the memory Proj can be removed */
1522         ir_node *res = get_Mod_mem(n);
1523         set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1524         if (proj_nr == pn_Mod_M)
1525           return res;
1526       }
1527     }
1528     break;
1529   case iro_DivMod:
1530     b  = get_DivMod_right(n);
1531     tb = value_of(b);
1532
1533     if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1534       proj_nr = get_Proj_proj(proj);
1535
1536       /* this node may float */
1537       set_irn_pinned(n, op_pin_state_floats);
1538
1539       if (proj_nr == pn_DivMod_X_except) {
1540         /* we found an exception handler, remove it */
1541         return new_Bad();
1542       }
1543       else {
1544         /* the memory Proj can be removed */
1545         ir_node *res = get_DivMod_mem(n);
1546         set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1547         if (proj_nr == pn_DivMod_M)
1548           return res;
1549       }
1550     }
1551     break;
1552
1553   case iro_Cond:
1554     if (get_opt_unreachable_code()) {
1555       b = get_Cond_selector(n);
1556       tb = value_of(b);
1557
1558       if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1559         /* we have a constant switch */
1560         long num = get_Proj_proj(proj);
1561
1562         if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1563           if (get_tarval_long(tb) == num) {
1564             /* Do NOT create a jump here, or we will have 2 control flow ops
1565              * in a block. This case is optimized away in optimize_cf(). */
1566             return proj;
1567           }
1568           else
1569             return new_Bad();
1570         }
1571       }
1572     }
1573     return proj;
1574
1575   case iro_Tuple:
1576     /* should not happen, but if it does will be optimized away */
1577     break;
1578
1579   default:
1580     /* do nothing */
1581     return proj;
1582   }
1583
1584   /* we have added a Tuple, optimize it for the current Proj away */
1585   return equivalent_node_Proj(proj);
1586 }
1587
1588 /**
1589  * returns the operands of a commutative bin-op, if one operand is
1590  * a const, it is returned as the second one.
1591  */
1592 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1593 {
1594   ir_node *op_a = get_binop_left(binop);
1595   ir_node *op_b = get_binop_right(binop);
1596
1597   assert(is_op_commutative(get_irn_op(binop)));
1598
1599   if (get_irn_op(op_a) == op_Const) {
1600     *a = op_b;
1601     *c = op_a;
1602   }
1603   else {
1604     *a = op_a;
1605     *c = op_b;
1606   }
1607 }
1608
1609 /**
1610  * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1611  * Such pattern may arise in bitfield stores.
1612  *
1613  * value  c4                  value      c4 & c2
1614  *    AND     c3                    AND           c1 | c3
1615  *        OR     c2      ===>               OR
1616  *           AND    c1
1617  *               OR
1618  */
1619 static ir_node *transform_node_Or_bf_store(ir_node *or)
1620 {
1621   ir_node *and, *c1;
1622   ir_node *or_l, *c2;
1623   ir_node *and_l, *c3;
1624   ir_node *value, *c4;
1625   ir_node *new_and, *new_const, *block;
1626   ir_mode *mode = get_irn_mode(or);
1627
1628   tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
1629
1630   get_comm_Binop_Ops(or, &and, &c1);
1631   if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
1632     return or;
1633
1634   get_comm_Binop_Ops(and, &or_l, &c2);
1635   if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
1636     return or;
1637
1638   get_comm_Binop_Ops(or_l, &and_l, &c3);
1639   if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
1640     return or;
1641
1642   get_comm_Binop_Ops(and_l, &value, &c4);
1643   if (get_irn_op(c4) != op_Const)
1644     return or;
1645
1646   /* ok, found the pattern, check for conditions */
1647   assert(mode == get_irn_mode(and));
1648   assert(mode == get_irn_mode(or_l));
1649   assert(mode == get_irn_mode(and_l));
1650
1651   tv1 = get_Const_tarval(c1);
1652   tv2 = get_Const_tarval(c2);
1653   tv3 = get_Const_tarval(c3);
1654   tv4 = get_Const_tarval(c4);
1655
1656   tv = tarval_or(tv4, tv2);
1657   if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
1658     /* have at least one 0 at the same bit position */
1659     return or;
1660   }
1661
1662   n_tv4 = tarval_not(tv4);
1663   if (tv3 != tarval_and(tv3, n_tv4)) {
1664     /* bit in the or_mask is outside the and_mask */
1665     return or;
1666   }
1667
1668   n_tv2 = tarval_not(tv2);
1669   if (tv1 != tarval_and(tv1, n_tv2)) {
1670     /* bit in the or_mask is outside the and_mask */
1671     return or;
1672   }
1673
1674   /* ok, all conditions met */
1675   block = get_nodes_block(or);
1676
1677   new_and = new_r_And(current_ir_graph, block,
1678       value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
1679
1680   new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
1681
1682   set_Or_left(or, new_and);
1683   set_Or_right(or, new_const);
1684
1685   /* check for more */
1686   return transform_node_Or_bf_store(or);
1687 }
1688
1689 /**
1690  * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
1691  */
1692 static ir_node *transform_node_Or_Rot(ir_node *or)
1693 {
1694   ir_mode *mode = get_irn_mode(or);
1695   ir_node *shl, *shr, *block;
1696   ir_node *irn, *x, *c1, *c2, *v, *sub;
1697   tarval *tv1, *tv2;
1698
1699   if (! mode_is_int(mode))
1700     return or;
1701
1702   shl = get_binop_left(or);
1703   shr = get_binop_right(or);
1704
1705   if (get_irn_op(shl) == op_Shr) {
1706     if (get_irn_op(shr) != op_Shl)
1707       return or;
1708
1709     irn = shl;
1710     shl = shr;
1711     shr = irn;
1712   }
1713   else if (get_irn_op(shl) != op_Shl)
1714     return or;
1715   else if (get_irn_op(shr) != op_Shr)
1716     return or;
1717
1718   x = get_Shl_left(shl);
1719   if (x != get_Shr_left(shr))
1720     return or;
1721
1722   c1 = get_Shl_right(shl);
1723   c2 = get_Shr_right(shr);
1724   if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
1725     tv1 = get_Const_tarval(c1);
1726     if (! tarval_is_long(tv1))
1727       return or;
1728
1729     tv2 = get_Const_tarval(c2);
1730     if (! tarval_is_long(tv2))
1731       return or;
1732
1733     if (get_tarval_long(tv1) + get_tarval_long(tv2)
1734         != get_mode_size_bits(mode))
1735       return or;
1736
1737     /* yet, condition met */
1738     block = get_nodes_block(or);
1739
1740     return new_r_Rot(current_ir_graph, block, x, c1, mode);
1741   }
1742   else if (get_irn_op(c1) == op_Sub) {
1743     v   = c2;
1744     sub = c1;
1745
1746     if (get_Sub_right(sub) != v)
1747       return or;
1748
1749     c1 = get_Sub_left(sub);
1750     if (get_irn_op(c1) != op_Const)
1751       return or;
1752
1753     tv1 = get_Const_tarval(c1);
1754     if (! tarval_is_long(tv1))
1755       return or;
1756
1757     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1758       return or;
1759
1760     /* yet, condition met */
1761     block = get_nodes_block(or);
1762
1763     /* a Rot right is not supported, so use a rot left */
1764     return new_r_Rot(current_ir_graph, block, x, sub, mode);
1765   }
1766   else if (get_irn_op(c2) == op_Sub) {
1767     v   = c1;
1768     sub = c2;
1769
1770     c1 = get_Sub_left(sub);
1771     if (get_irn_op(c1) != op_Const)
1772       return or;
1773
1774     tv1 = get_Const_tarval(c1);
1775     if (! tarval_is_long(tv1))
1776       return or;
1777
1778     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
1779       return or;
1780
1781     /* yet, condition met */
1782     block = get_nodes_block(or);
1783
1784     /* a Rot Left */
1785     return new_r_Rot(current_ir_graph, block, x, v, mode);
1786   }
1787
1788   return or;
1789 }
1790
1791 /**
1792  * Optimize an Or
1793  */
1794 static ir_node *transform_node_Or(ir_node *or)
1795 {
1796   or = transform_node_Or_bf_store(or);
1797   or = transform_node_Or_Rot(or);
1798
1799   return or;
1800 }
1801
1802 /* forward */
1803 static ir_node *transform_node(ir_node *n);
1804
1805 /**
1806  * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
1807  */
1808 static ir_node * transform_node_shift(ir_node *n)
1809 {
1810   ir_node *left;
1811   tarval *tv1, *tv2, *res;
1812   ir_mode *mode;
1813   int modulo_shf, flag;
1814
1815   left = get_binop_left(n);
1816
1817   /* different operations */
1818   if (get_irn_op(left) != get_irn_op(n))
1819     return n;
1820
1821   tv1 = value_of(get_binop_right(n));
1822   if (tv1 == tarval_bad)
1823     return n;
1824
1825   tv2 = value_of(get_binop_right(left));
1826   if (tv2 == tarval_bad)
1827     return n;
1828
1829   res = tarval_add(tv1, tv2);
1830
1831   /* beware: a simple replacement works only, if res < modulo shift */
1832   mode = get_irn_mode(n);
1833
1834   flag = 0;
1835
1836   modulo_shf = get_mode_modulo_shift(mode);
1837   if (modulo_shf > 0) {
1838     tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
1839
1840     if (tarval_cmp(res, modulo) & Lt)
1841       flag = 1;
1842   }
1843   else
1844     flag = 1;
1845
1846   if (flag) {
1847     /* ok, we can replace it */
1848     ir_node *in[2], *irn, *block = get_nodes_block(n);
1849
1850     in[0] = get_binop_left(left);
1851     in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
1852
1853     irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
1854
1855     return transform_node(irn);
1856   }
1857   return n;
1858 }
1859
1860 static ir_node * transform_node_End(ir_node *n) {
1861   int i, n_keepalives = get_End_n_keepalives(n);
1862
1863   /* Remove dead blocks in keepalive list.
1864      We do not generate a new End node. */
1865   for (i = 0; i < n_keepalives; ++i) {
1866     ir_node *ka = get_End_keepalive(n, i);
1867     if (is_Block(ka) && is_Block_dead(ka))
1868       set_End_keepalive(n, i, new_Bad());
1869   }
1870   return n;
1871 }
1872
1873
1874 /**
1875  * Tries several [inplace] [optimizing] transformations and returns an
1876  * equivalent node.  The difference to equivalent_node() is that these
1877  * transformations _do_ generate new nodes, and thus the old node must
1878  * not be freed even if the equivalent node isn't the old one.
1879  */
1880 static ir_node *transform_node(ir_node *n)
1881 {
1882   if (n->op->transform_node)
1883     n = n->op->transform_node(n);
1884   return n;
1885 }
1886
1887 /**
1888  * set the default transform node operation
1889  */
1890 static ir_op *firm_set_default_transform_node(ir_op *op)
1891 {
1892 #define CASE(a)                                 \
1893   case iro_##a:                                 \
1894     op->transform_node  = transform_node_##a;   \
1895     break
1896
1897   switch (op->code) {
1898   CASE(Add);
1899   CASE(Sub);
1900   CASE(Mul);
1901   CASE(Div);
1902   CASE(Mod);
1903   CASE(DivMod);
1904   CASE(Cond);
1905   CASE(Eor);
1906   CASE(Not);
1907   CASE(Cast);
1908   CASE(Proj);
1909   CASE(Or);
1910   CASE(End);
1911   case iro_Shr:
1912   case iro_Shrs:
1913   case iro_Shl:
1914     op->transform_node  = transform_node_shift;
1915     break;
1916   default:
1917     op->transform_node  = NULL;
1918   }
1919
1920   return op;
1921 #undef CASE
1922 }
1923
1924
1925 /* **************** Common Subexpression Elimination **************** */
1926
1927 /** The size of the hash table used, should estimate the number of nodes
1928     in a graph. */
1929 #define N_IR_NODES 512
1930
1931 /** Compares the attributes of two Const nodes. */
1932 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
1933 {
1934   return (get_Const_tarval(a) != get_Const_tarval(b))
1935       || (get_Const_type(a) != get_Const_type(b));
1936 }
1937
1938 /** Compares the attributes of two Proj nodes. */
1939 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
1940 {
1941     return get_irn_proj_attr (a) != get_irn_proj_attr (b);
1942 }
1943
1944 /** Compares the attributes of two Filter nodes. */
1945 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
1946 {
1947     return get_Filter_proj(a) != get_Filter_proj(b);
1948 }
1949
1950 /** Compares the attributes of two Alloc nodes. */
1951 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
1952 {
1953     return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
1954         || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
1955 }
1956
1957 /** Compares the attributes of two Free nodes. */
1958 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
1959 {
1960     return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
1961         || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
1962 }
1963
1964 /** Compares the attributes of two SymConst nodes. */
1965 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
1966 {
1967     return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
1968       || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
1969       || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
1970 }
1971
1972 /** Compares the attributes of two Call nodes. */
1973 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
1974 {
1975     return (get_irn_call_attr(a) != get_irn_call_attr(b));
1976 }
1977
1978 /** Compares the attributes of two Sel nodes. */
1979 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
1980 {
1981     return (get_irn_sel_attr(a).ent->kind  != get_irn_sel_attr(b).ent->kind)
1982       || (get_irn_sel_attr(a).ent->name    != get_irn_sel_attr(b).ent->name)
1983       || (get_irn_sel_attr(a).ent->owner   != get_irn_sel_attr(b).ent->owner)
1984       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
1985       || (get_irn_sel_attr(a).ent->type    != get_irn_sel_attr(b).ent->type);
1986 }
1987
1988 /** Compares the attributes of two Phi nodes. */
1989 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
1990 {
1991     return get_irn_phi_attr (a) != get_irn_phi_attr (b);
1992 }
1993
1994 /** Compares the attributes of two Cast nodes. */
1995 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
1996 {
1997     return get_Cast_type(a) != get_Cast_type(b);
1998 }
1999
2000 /** Compares the attributes of two Load nodes. */
2001 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2002 {
2003   if (get_Load_volatility(a) == volatility_is_volatile ||
2004       get_Load_volatility(b) == volatility_is_volatile)
2005     /* NEVER do CSE on volatile Loads */
2006     return 1;
2007
2008   return get_Load_mode(a) != get_Load_mode(b);
2009 }
2010
2011 /** Compares the attributes of two Store nodes. */
2012 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2013 {
2014   /* NEVER do CSE on volatile Stores */
2015   return (get_Store_volatility(a) == volatility_is_volatile ||
2016       get_Store_volatility(b) == volatility_is_volatile);
2017 }
2018
2019 /**
2020  * set the default node attribute compare operation
2021  */
2022 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2023 {
2024 #define CASE(a)                             \
2025   case iro_##a:                             \
2026     op->node_cmp_attr  = node_cmp_attr_##a; \
2027     break
2028
2029   switch (op->code) {
2030   CASE(Const);
2031   CASE(Proj);
2032   CASE(Filter);
2033   CASE(Alloc);
2034   CASE(Free);
2035   CASE(SymConst);
2036   CASE(Call);
2037   CASE(Sel);
2038   CASE(Phi);
2039   CASE(Cast);
2040   CASE(Load);
2041   CASE(Store);
2042   default:
2043     op->node_cmp_attr  = NULL;
2044   }
2045
2046   return op;
2047 #undef CASE
2048 }
2049
2050 /**
2051  * Compare function for two nodes in the hash table. Gets two
2052  * nodes as parameters.  Returns 0 if the nodes are a cse.
2053  */
2054 static int
2055 vt_cmp (const void *elt, const void *key)
2056 {
2057   ir_node *a, *b;
2058   int i, irn_arity_a;
2059
2060   a = (void *)elt;
2061   b = (void *)key;
2062
2063   if (a == b) return 0;
2064
2065   if ((get_irn_op(a) != get_irn_op(b)) ||
2066       (get_irn_mode(a) != get_irn_mode(b))) return 1;
2067
2068   /* compare if a's in and b's in are of equal length */
2069   irn_arity_a = get_irn_intra_arity (a);
2070   if (irn_arity_a != get_irn_intra_arity(b))
2071     return 1;
2072
2073   /* for block-local cse and op_pin_state_pinned nodes: */
2074   if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2075     if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2076       return 1;
2077   }
2078
2079   /* compare a->in[0..ins] with b->in[0..ins] */
2080   for (i = 0; i < irn_arity_a; i++)
2081     if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2082       return 1;
2083
2084   /*
2085    * here, we already now that the nodes are identical except their
2086    * attributes
2087    */
2088   if (a->op->node_cmp_attr)
2089     return a->op->node_cmp_attr(a, b);
2090
2091   return 0;
2092 }
2093
2094 /*
2095  * Calculate a hash value of a node.
2096  */
2097 unsigned
2098 ir_node_hash (ir_node *node)
2099 {
2100   unsigned h;
2101   int i, irn_arity;
2102
2103   if (node->op == op_Const) {
2104     /* special value for const, as they only differ in their tarval. */
2105     h = HASH_PTR(node->attr.con.tv);
2106     h = 9*h + HASH_PTR(get_irn_mode(node));
2107   } else if (node->op == op_SymConst) {
2108     /* special value for const, as they only differ in their symbol. */
2109     h = HASH_PTR(node->attr.i.sym.type_p);
2110     h = 9*h + HASH_PTR(get_irn_mode(node));
2111   } else {
2112
2113     /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2114     h = irn_arity = get_irn_intra_arity(node);
2115
2116     /* consider all in nodes... except the block if not a control flow. */
2117     for (i =  is_cfop(node) ? -1 : 0;  i < irn_arity;  i++) {
2118       h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2119     }
2120
2121     /* ...mode,... */
2122     h = 9*h + HASH_PTR(get_irn_mode(node));
2123     /* ...and code */
2124     h = 9*h + HASH_PTR(get_irn_op(node));
2125   }
2126
2127   return h;
2128 }
2129
2130 pset *
2131 new_identities(void) {
2132   return new_pset(vt_cmp, N_IR_NODES);
2133 }
2134
2135 void
2136 del_identities(pset *value_table) {
2137   del_pset(value_table);
2138 }
2139
2140 /**
2141  * Return the canonical node computing the same value as n.
2142  * Looks up the node in a hash table.
2143  *
2144  * For Const nodes this is performed in the constructor, too.  Const
2145  * nodes are extremely time critical because of their frequent use in
2146  * constant string arrays.
2147  */
2148 static INLINE ir_node *
2149 identify (pset *value_table, ir_node *n)
2150 {
2151   ir_node *o = NULL;
2152
2153   if (!value_table) return n;
2154
2155   if (get_opt_reassociation()) {
2156     if (is_op_commutative(get_irn_op(n))) {
2157       ir_node *l = get_binop_left(n);
2158       ir_node *r = get_binop_right(n);
2159
2160       /* for commutative operators perform  a OP b == b OP a */
2161       if (l > r) {
2162         set_binop_left(n, r);
2163         set_binop_right(n, l);
2164       }
2165     }
2166   }
2167
2168   o = pset_find (value_table, n, ir_node_hash (n));
2169   if (!o) return n;
2170
2171   DBG_OPT_CSE(n, o);
2172
2173   return o;
2174 }
2175
2176 /**
2177  * During construction we set the op_pin_state_pinned flag in the graph right when the
2178  * optimization is performed.  The flag turning on procedure global cse could
2179  * be changed between two allocations.  This way we are safe.
2180  */
2181 static INLINE ir_node *
2182 identify_cons (pset *value_table, ir_node *n) {
2183   ir_node *old = n;
2184
2185   n = identify(value_table, n);
2186   if (get_irn_n(old, -1) != get_irn_n(n, -1))
2187     set_irg_pinned(current_ir_graph, op_pin_state_floats);
2188   return n;
2189 }
2190
2191 /**
2192  * Return the canonical node computing the same value as n.
2193  * Looks up the node in a hash table, enters it in the table
2194  * if it isn't there yet.
2195  */
2196 static ir_node *
2197 identify_remember (pset *value_table, ir_node *n)
2198 {
2199   ir_node *o = NULL;
2200
2201   if (!value_table) return n;
2202
2203   if (get_opt_reassociation()) {
2204     if (is_op_commutative(get_irn_op(n))) {
2205       ir_node *l = get_binop_left(n);
2206       ir_node *r = get_binop_right(n);
2207
2208       /* for commutative operators perform  a OP b == b OP a */
2209       if (l > r) {
2210         set_binop_left(n, r);
2211         set_binop_right(n, l);
2212       }
2213     }
2214   }
2215
2216   /* lookup or insert in hash table with given hash key. */
2217   o = pset_insert (value_table, n, ir_node_hash (n));
2218
2219   if (o != n) {
2220     DBG_OPT_CSE(n, o);
2221   }
2222
2223   return o;
2224 }
2225
2226 void
2227 add_identities (pset *value_table, ir_node *node) {
2228   if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2229     identify_remember (value_table, node);
2230 }
2231
2232 /**
2233  * garbage in, garbage out. If a node has a dead input, i.e., the
2234  * Bad node is input to the node, return the Bad node.
2235  */
2236 static INLINE ir_node *
2237 gigo (ir_node *node)
2238 {
2239   int i, irn_arity;
2240   ir_op* op = get_irn_op(node);
2241
2242   /* remove garbage blocks by looking at control flow that leaves the block
2243      and replacing the control flow by Bad. */
2244   if (get_irn_mode(node) == mode_X) {
2245     ir_node *block = get_nodes_block(node);
2246     if (!get_Block_matured(block)) return node;  /* Don't optimize nodes in immature blocks. */
2247     if (op == op_End) return node;     /* Don't optimize End, may have Bads. */
2248
2249     if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2250       irn_arity = get_irn_arity(block);
2251       for (i = 0; i < irn_arity; i++) {
2252         if (!is_Bad(get_irn_n(block, i))) break;
2253       }
2254       if (i == irn_arity) return new_Bad();
2255     }
2256   }
2257
2258   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2259      blocks predecessors is dead. */
2260   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2261     irn_arity = get_irn_arity(node);
2262
2263     if (is_Block_dead(get_nodes_block(node)))
2264       return new_Bad();
2265
2266     for (i = 0; i < irn_arity; i++) {
2267       if (is_Bad(get_irn_n(node, i))) {
2268         return new_Bad();
2269       }
2270     }
2271   }
2272 #if 0
2273   /* With this code we violate the agreement that local_optimize
2274      only leaves Bads in Block, Phi and Tuple nodes. */
2275   /* If Block has only Bads as predecessors it's garbage. */
2276   /* If Phi has only Bads as predecessors it's garbage. */
2277   if ((op == op_Block && get_Block_matured(node)) || op == op_Phi)  {
2278     irn_arity = get_irn_arity(node);
2279     for (i = 0; i < irn_arity; i++) {
2280       if (!is_Bad(get_irn_n(node, i))) break;
2281     }
2282     if (i == irn_arity) node = new_Bad();
2283   }
2284 #endif
2285   return node;
2286 }
2287
2288
2289 /**
2290  * These optimizations deallocate nodes from the obstack.
2291  * It can only be called if it is guaranteed that no other nodes
2292  * reference this one, i.e., right after construction of a node.
2293  */
2294 ir_node *
2295 optimize_node (ir_node *n)
2296 {
2297   tarval *tv;
2298   ir_node *oldn = n;
2299   opcode iro = get_irn_opcode(n);
2300
2301   type *old_tp = get_irn_type(n);
2302   {
2303     int i, arity = get_irn_arity(n);
2304     for (i = 0; i < arity && !old_tp; ++i)
2305       old_tp = get_irn_type(get_irn_n(n, i));
2306   }
2307
2308   /* Allways optimize Phi nodes: part of the construction. */
2309   if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2310
2311   /* constant expression evaluation / constant folding */
2312   if (get_opt_constant_folding()) {
2313     /* constants can not be evaluated */
2314     if (iro != iro_Const) {
2315       /* try to evaluate */
2316       tv = computed_value(n);
2317       if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2318         /*
2319          * we MUST copy the node here temporary, because it's still needed
2320          * for DBG_OPT_CSTEVAL
2321          */
2322         int node_size = offsetof(ir_node, attr) +  n->op->attr_size;
2323         oldn = alloca(node_size);
2324
2325         memcpy(oldn, n, node_size);
2326     CLONE_ARR_A(ir_node *, oldn->in, n->in);
2327
2328     /* ARG, copy the in array, we need it for statistics */
2329     memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2330
2331         /* evaluation was successful -- replace the node. */
2332         obstack_free (current_ir_graph->obst, n);
2333         n = new_Const (get_tarval_mode (tv), tv);
2334     if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2335       set_Const_type(n, old_tp);
2336                                                  DBG_OPT_CSTEVAL(oldn, n);
2337         return n;
2338       }
2339     }
2340   }
2341
2342   /* remove unnecessary nodes */
2343   if (get_opt_constant_folding() ||
2344       (iro == iro_Phi)  ||   /* always optimize these nodes. */
2345       (iro == iro_Id)   ||
2346       (iro == iro_Proj) ||
2347       (iro == iro_Block)  )  /* Flags tested local. */
2348     n = equivalent_node (n);
2349
2350   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
2351
2352   /** common subexpression elimination **/
2353   /* Checks whether n is already available. */
2354   /* The block input is used to distinguish different subexpressions. Right
2355      now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2356      subexpressions within a block. */
2357   if (get_opt_cse())
2358     n = identify_cons (current_ir_graph->value_table, n);
2359
2360   if (n != oldn) {
2361     /* We found an existing, better node, so we can deallocate the old node. */
2362     obstack_free (current_ir_graph->obst, oldn);
2363
2364     return n;
2365   }
2366
2367   /* Some more constant expression evaluation that does not allow to
2368      free the node. */
2369   iro = get_irn_opcode(n);
2370   if (get_opt_constant_folding() ||
2371       (iro == iro_Cond) ||
2372       (iro == iro_Proj))     /* Flags tested local. */
2373     n = transform_node (n);
2374
2375   /* Remove nodes with dead (Bad) input.
2376      Run always for transformation induced Bads. */
2377   n = gigo (n);
2378
2379   /* Now we have a legal, useful node. Enter it in hash table for cse */
2380   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2381     n = identify_remember (current_ir_graph->value_table, n);
2382   }
2383
2384   return n;
2385 }
2386
2387
2388 /**
2389  * These optimizations never deallocate nodes (in place).  This can cause dead
2390  * nodes lying on the obstack.  Remove these by a dead node elimination,
2391  * i.e., a copying garbage collection.
2392  */
2393 ir_node *
2394 optimize_in_place_2 (ir_node *n)
2395 {
2396   tarval *tv;
2397   ir_node *oldn = n;
2398   opcode iro = get_irn_opcode(n);
2399
2400   type *old_tp = get_irn_type(n);
2401   {
2402     int i, arity = get_irn_arity(n);
2403     for (i = 0; i < arity && !old_tp; ++i)
2404       old_tp = get_irn_type(get_irn_n(n, i));
2405   }
2406
2407   if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2408
2409   /* if not optimize return n */
2410   if (n == NULL) {
2411     assert(0);
2412     /* Here this is possible.  Why? */
2413     return n;
2414   }
2415
2416   /* constant expression evaluation / constant folding */
2417   if (get_opt_constant_folding()) {
2418     /* constants can not be evaluated */
2419     if (iro != iro_Const) {
2420       /* try to evaluate */
2421       tv = computed_value(n);
2422       if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2423         /* evaluation was successful -- replace the node. */
2424         n = new_Const (get_tarval_mode (tv), tv);
2425
2426     if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2427       set_Const_type(n, old_tp);
2428
2429         DBG_OPT_CSTEVAL(oldn, n);
2430         return n;
2431       }
2432     }
2433   }
2434
2435   /* remove unnecessary nodes */
2436   if (get_opt_constant_folding() ||
2437       (iro == iro_Phi)  ||   /* always optimize these nodes. */
2438       (iro == iro_Id)   ||   /* ... */
2439       (iro == iro_Proj) ||   /* ... */
2440       (iro == iro_Block)  )  /* Flags tested local. */
2441     n = equivalent_node (n);
2442
2443   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
2444
2445   /** common subexpression elimination **/
2446   /* Checks whether n is already available. */
2447   /* The block input is used to distinguish different subexpressions.  Right
2448      now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2449      subexpressions within a block. */
2450   if (get_opt_cse()) {
2451     n = identify (current_ir_graph->value_table, n);
2452   }
2453
2454   /* Some more constant expression evaluation. */
2455   iro = get_irn_opcode(n);
2456   if (get_opt_constant_folding() ||
2457       (iro == iro_Cond) ||
2458       (iro == iro_Proj))     /* Flags tested local. */
2459     n = transform_node (n);
2460
2461   /* Remove nodes with dead (Bad) input.
2462      Run always for transformation induced Bads.  */
2463   n = gigo (n);
2464
2465   /* Now we can verify the node, as it has no dead inputs any more. */
2466   irn_vrfy(n);
2467
2468   /* Now we have a legal, useful node. Enter it in hash table for cse.
2469      Blocks should be unique anyways.  (Except the successor of start:
2470      is cse with the start block!) */
2471   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
2472     n = identify_remember (current_ir_graph->value_table, n);
2473
2474   return n;
2475 }
2476
2477 /**
2478  * Wrapper for external use, set proper status bits after optimization.
2479  */
2480 ir_node *
2481 optimize_in_place (ir_node *n)
2482 {
2483   /* Handle graph state */
2484   assert(get_irg_phase_state(current_ir_graph) != phase_building);
2485
2486   if (get_opt_global_cse())
2487     set_irg_pinned(current_ir_graph, op_pin_state_floats);
2488   if (get_irg_outs_state(current_ir_graph) == outs_consistent)
2489     set_irg_outs_inconsistent(current_ir_graph);
2490
2491   /* Maybe we could also test whether optimizing the node can
2492      change the control graph. */
2493   if (get_irg_dom_state(current_ir_graph) == dom_consistent)
2494     set_irg_dom_inconsistent(current_ir_graph);
2495   return optimize_in_place_2 (n);
2496 }
2497
2498 /**
2499  * set the default ir op operations
2500  */
2501 ir_op *firm_set_default_operations(ir_op *op)
2502 {
2503   op = firm_set_default_computed_value(op);
2504   op = firm_set_default_equivalent_node(op);
2505   op = firm_set_default_transform_node(op);
2506   op = firm_set_default_node_cmp_attr(op);
2507
2508   return op;
2509 }