nsz Git - libfirm/blob - 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, Michael Beck
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1998-2005 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 "iredges_t.h"
  30 #include "irmode_t.h"
  31 #include "iropt_t.h"
  32 #include "ircons_t.h"
  33 #include "irgmod.h"
  34 #include "irvrfy.h"
  35 #include "tv_t.h"
  36 #include "dbginfo_t.h"
  37 #include "iropt_dbg.h"
  38 #include "irflag_t.h"
  39 #include "irhooks.h"
  40 #include "irarch.h"
  41 #include "hashptr.h"
  42 #include "archop.h"
  43 #include "opt_polymorphy.h"
  44 #include "opt_confirms.h"
  45
  46 /* Make types visible to allow most efficient access */
  47 # include "entity_t.h"
  48
  49 /**
  50  * return the value of a Constant
  51  */
  52 static tarval *computed_value_Const(ir_node *n)
  53 {
  54   return get_Const_tarval(n);
  55 }
  56
  57 /**
  58  * return the value of a 'sizeof' SymConst
  59  */
  60 static tarval *computed_value_SymConst(ir_node *n)
  61 {
  62   if ((get_SymConst_kind(n) == symconst_size) &&
  63       (get_type_state(get_SymConst_type(n))) == layout_fixed)
  64     return new_tarval_from_long(get_type_size_bytes(get_SymConst_type(n)), get_irn_mode(n));
  65   return tarval_bad;
  66 }
  67
  68 /**
  69  * return the value of an Add
  70  */
  71 static tarval *computed_value_Add(ir_node *n)
  72 {
  73   ir_node *a = get_Add_left(n);
  74   ir_node *b = get_Add_right(n);
  75
  76   tarval *ta = value_of(a);
  77   tarval *tb = value_of(b);
  78
  79   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
  80     return tarval_add(ta, tb);
  81
  82   return tarval_bad;
  83 }
  84
  85 /**
  86  * return the value of a Sub
  87  * Special case: a - a
  88  */
  89 static tarval *computed_value_Sub(ir_node *n)
  90 {
  91   ir_node *a = get_Sub_left(n);
  92   ir_node *b = get_Sub_right(n);
  93   tarval *ta;
  94   tarval *tb;
  95
  96   /* a - a */
  97   if (a == b && !is_Bad(a))
  98     return get_mode_null(get_irn_mode(n));
  99
 100   ta = value_of(a);
 101   tb = value_of(b);
 102
 103   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b)))
 104     return tarval_sub(ta, tb);
 105
 106   return tarval_bad;
 107 }
 108
 109 /**
 110  * return the value of a Carry
 111  * Special : a op 0, 0 op b
 112  */
 113 static tarval *computed_value_Carry(ir_node *n)
 114 {
 115   ir_node *a = get_binop_left(n);
 116   ir_node *b = get_binop_right(n);
 117   ir_mode *m = get_irn_mode(n);
 118
 119   tarval *ta = value_of(a);
 120   tarval *tb = value_of(b);
 121
 122   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 123     tarval_add(ta, tb);
 124     return tarval_carry() ? get_mode_one(m) : get_mode_null(m);
 125   } else {
 126     if (   (classify_tarval(ta) == TV_CLASSIFY_NULL)
 127         || (classify_tarval(tb) == TV_CLASSIFY_NULL))
 128       return get_mode_null(m);
 129   }
 130   return tarval_bad;
 131 }
 132
 133 /**
 134  * return the value of a Borrow
 135  * Special : a op 0
 136  */
 137 static tarval *computed_value_Borrow(ir_node *n)
 138 {
 139   ir_node *a = get_binop_left(n);
 140   ir_node *b = get_binop_right(n);
 141   ir_mode *m = get_irn_mode(n);
 142
 143   tarval *ta = value_of(a);
 144   tarval *tb = value_of(b);
 145
 146   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 147     return tarval_cmp(ta, tb) == pn_Cmp_Lt ? get_mode_one(m) : get_mode_null(m);
 148   } else if (classify_tarval(ta) == TV_CLASSIFY_NULL) {
 149       return get_mode_null(m);
 150   }
 151   return tarval_bad;
 152 }
 153
 154 /**
 155  * return the value of an unary Minus
 156  */
 157 static tarval *computed_value_Minus(ir_node *n)
 158 {
 159   ir_node *a = get_Minus_op(n);
 160   tarval *ta = value_of(a);
 161
 162   if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
 163     return tarval_neg(ta);
 164
 165   return tarval_bad;
 166 }
 167
 168 /**
 169  * return the value of a Mul
 170  */
 171 static tarval *computed_value_Mul(ir_node *n)
 172 {
 173   ir_node *a = get_Mul_left(n);
 174   ir_node *b = get_Mul_right(n);
 175
 176   tarval *ta = value_of(a);
 177   tarval *tb = value_of(b);
 178
 179   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
 180     return tarval_mul(ta, tb);
 181   } else {
 182     /* a*0 = 0 or 0*b = 0:
 183        calls computed_value recursive and returns the 0 with proper
 184        mode. */
 185     if ((ta != tarval_bad) && (ta == get_mode_null(get_tarval_mode(ta))))
 186       return ta;
 187     if ((tb != tarval_bad) && (tb == get_mode_null(get_tarval_mode(tb))))
 188       return tb;
 189   }
 190   return tarval_bad;
 191 }
 192
 193 /**
 194  * return the value of a floating point Quot
 195  */
 196 static tarval *computed_value_Quot(ir_node *n)
 197 {
 198   ir_node *a = get_Quot_left(n);
 199   ir_node *b = get_Quot_right(n);
 200
 201   tarval *ta = value_of(a);
 202   tarval *tb = value_of(b);
 203
 204   /* This was missing in original implementation. Why? */
 205   if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
 206     if (tb != get_mode_null(get_tarval_mode(tb)))   /* div by zero: return tarval_bad */
 207       return tarval_quo(ta, tb);
 208   }
 209   return tarval_bad;
 210 }
 211
 212 /**
 213  * calculate the value of an integer Div of two nodes
 214  * Special case: 0 / b
 215  */
 216 static tarval *do_computed_value_Div(ir_node *a, ir_node *b)
 217 {
 218   tarval *ta = value_of(a);
 219   tarval *tb = value_of(b);
 220
 221   /* Compute c1 / c2 or 0 / a, a != 0 */
 222   if (ta != tarval_bad) {
 223     if ((tb != tarval_bad) && (tb != get_mode_null(get_irn_mode(b))))   /* div by zero: return tarval_bad */
 224       return tarval_div(ta, tb);
 225     else if (ta == get_mode_null(get_tarval_mode(ta)))  /* 0 / b == 0 */
 226       return ta;
 227   }
 228   return tarval_bad;
 229 }
 230
 231 /**
 232  * return the value of an integer Div
 233  */
 234 static tarval *computed_value_Div(ir_node *n)
 235 {
 236   return do_computed_value_Div(get_Div_left(n), get_Div_right(n));
 237 }
 238
 239 /**
 240  * calculate the value of an integer Mod of two nodes
 241  * Special case: a % 1
 242  */
 243 static tarval *do_computed_value_Mod(ir_node *a, ir_node *b)
 244 {
 245   tarval *ta = value_of(a);
 246   tarval *tb = value_of(b);
 247
 248   /* Compute c1 % c2 or a % 1 */
 249   if (tb != tarval_bad) {
 250     if ((ta != tarval_bad) && (tb != get_mode_null(get_tarval_mode(tb))))   /* div by zero: return tarval_bad */
 251       return tarval_mod(ta, tb);
 252     else if (tb == get_mode_one(get_tarval_mode(tb)))    /* x mod 1 == 0 */
 253       return get_mode_null(get_irn_mode(a));
 254   }
 255
 256   return tarval_bad;
 257 }
 258
 259 /**
 260  * return the value of an integer Mod
 261  */
 262 static tarval *computed_value_Mod(ir_node *n)
 263 {
 264   return do_computed_value_Mod(get_Mod_left(n), get_Mod_right(n));
 265 }
 266
 267 /**
 268  * return the value of an Abs
 269  */
 270 static tarval *computed_value_Abs(ir_node *n)
 271 {
 272   ir_node *a = get_Abs_op(n);
 273   tarval *ta = value_of(a);
 274
 275   if (ta != tarval_bad)
 276     return tarval_abs(ta);
 277
 278   return tarval_bad;
 279 }
 280
 281 /**
 282  * return the value of an And
 283  * Special case: a & 0, 0 & b
 284  */
 285 static tarval *computed_value_And(ir_node *n)
 286 {
 287   ir_node *a = get_And_left(n);
 288   ir_node *b = get_And_right(n);
 289
 290   tarval *ta = value_of(a);
 291   tarval *tb = value_of(b);
 292
 293   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 294     return tarval_and (ta, tb);
 295   } else {
 296     tarval *v;
 297
 298     if (   (classify_tarval ((v = ta)) == TV_CLASSIFY_NULL)
 299         || (classify_tarval ((v = tb)) == TV_CLASSIFY_NULL)) {
 300       return v;
 301     }
 302   }
 303   return tarval_bad;
 304 }
 305
 306 /**
 307  * return the value of an Or
 308  * Special case: a | 1...1, 1...1 | b
 309  */
 310 static tarval *computed_value_Or(ir_node *n)
 311 {
 312   ir_node *a = get_Or_left(n);
 313   ir_node *b = get_Or_right(n);
 314
 315   tarval *ta = value_of(a);
 316   tarval *tb = value_of(b);
 317
 318   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 319     return tarval_or (ta, tb);
 320   } else {
 321     tarval *v;
 322     if (   (classify_tarval ((v = ta)) == TV_CLASSIFY_ALL_ONE)
 323         || (classify_tarval ((v = tb)) == TV_CLASSIFY_ALL_ONE)) {
 324       return v;
 325     }
 326   }
 327   return tarval_bad;
 328 }
 329
 330 /**
 331  * return the value of an Eor
 332  */
 333 static tarval *computed_value_Eor(ir_node *n)
 334 {
 335   ir_node *a = get_Eor_left(n);
 336   ir_node *b = get_Eor_right(n);
 337
 338   tarval *ta, *tb;
 339
 340   if (a == b)
 341     return get_mode_null(get_irn_mode(n));
 342
 343   ta = value_of(a);
 344   tb = value_of(b);
 345
 346   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 347     return tarval_eor (ta, tb);
 348   }
 349   return tarval_bad;
 350 }
 351
 352 /**
 353  * return the value of a Not
 354  */
 355 static tarval *computed_value_Not(ir_node *n)
 356 {
 357   ir_node *a = get_Not_op(n);
 358   tarval *ta = value_of(a);
 359
 360   if (ta != tarval_bad)
 361     return tarval_not(ta);
 362
 363   return tarval_bad;
 364 }
 365
 366 /**
 367  * return the value of a Shl
 368  */
 369 static tarval *computed_value_Shl(ir_node *n)
 370 {
 371   ir_node *a = get_Shl_left(n);
 372   ir_node *b = get_Shl_right(n);
 373
 374   tarval *ta = value_of(a);
 375   tarval *tb = value_of(b);
 376
 377   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 378     return tarval_shl (ta, tb);
 379   }
 380   return tarval_bad;
 381 }
 382
 383 /**
 384  * return the value of a Shr
 385  */
 386 static tarval *computed_value_Shr(ir_node *n)
 387 {
 388   ir_node *a = get_Shr_left(n);
 389   ir_node *b = get_Shr_right(n);
 390
 391   tarval *ta = value_of(a);
 392   tarval *tb = value_of(b);
 393
 394   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 395     return tarval_shr (ta, tb);
 396   }
 397   return tarval_bad;
 398 }
 399
 400 /**
 401  * return the value of a Shrs
 402  */
 403 static tarval *computed_value_Shrs(ir_node *n)
 404 {
 405   ir_node *a = get_Shrs_left(n);
 406   ir_node *b = get_Shrs_right(n);
 407
 408   tarval *ta = value_of(a);
 409   tarval *tb = value_of(b);
 410
 411   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 412     return tarval_shrs (ta, tb);
 413   }
 414   return tarval_bad;
 415 }
 416
 417 /**
 418  * return the value of a Rot
 419  */
 420 static tarval *computed_value_Rot(ir_node *n)
 421 {
 422   ir_node *a = get_Rot_left(n);
 423   ir_node *b = get_Rot_right(n);
 424
 425   tarval *ta = value_of(a);
 426   tarval *tb = value_of(b);
 427
 428   if ((ta != tarval_bad) && (tb != tarval_bad)) {
 429     return tarval_rot (ta, tb);
 430   }
 431   return tarval_bad;
 432 }
 433
 434 /**
 435  * return the value of a Conv
 436  */
 437 static tarval *computed_value_Conv(ir_node *n)
 438 {
 439   ir_node *a = get_Conv_op(n);
 440   tarval *ta = value_of(a);
 441
 442   if (ta != tarval_bad)
 443     return tarval_convert_to(ta, get_irn_mode(n));
 444
 445   return tarval_bad;
 446 }
 447
 448 /**
 449  * return the value of a Proj(Cmp)
 450  *
 451  * This performs a first step of unreachable code elimination.
 452  * Proj can not be computed, but folding a Cmp above the Proj here is
 453  * not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
 454  * only 1 is used.
 455  * There are several case where we can evaluate a Cmp node, see later.
 456  */
 457 static tarval *computed_value_Proj_Cmp(ir_node *n)
 458 {
 459   ir_node *a   = get_Proj_pred(n);
 460   ir_node *aa  = get_Cmp_left(a);
 461   ir_node *ab  = get_Cmp_right(a);
 462   long proj_nr = get_Proj_proj(n);
 463
 464   /*
 465    * BEWARE: a == a is NOT always True for floating Point values, as
 466    * NaN != NaN is defined, so we must check this here.
 467    */
 468   if (aa == ab && (
 469       !mode_is_float(get_irn_mode(aa)) || proj_nr == pn_Cmp_Lt ||  proj_nr == pn_Cmp_Gt)
 470       ) { /* 1.: */
 471
 472     /* This is a trick with the bits used for encoding the Cmp
 473        Proj numbers, the following statement is not the same:
 474     return new_tarval_from_long (proj_nr == pn_Cmp_Eq, mode_b) */
 475     return new_tarval_from_long (proj_nr & pn_Cmp_Eq, mode_b);
 476   }
 477   else {
 478     tarval *taa = value_of(aa);
 479     tarval *tab = value_of(ab);
 480     ir_mode *mode = get_irn_mode(aa);
 481
 482     /*
 483      * The predecessors of Cmp are target values.  We can evaluate
 484      * the Cmp.
 485      */
 486     if ((taa != tarval_bad) && (tab != tarval_bad)) {
 487       /* strange checks... */
 488       pn_Cmp flags = tarval_cmp(taa, tab);
 489       if (flags != pn_Cmp_False) {
 490         return new_tarval_from_long (proj_nr & flags, mode_b);
 491       }
 492     }
 493     /* for integer values, we can check against MIN/MAX */
 494     else if (mode_is_int(mode)) {
 495       /* MIN <=/> x.  This results in true/false. */
 496       if (taa == get_mode_min(mode)) {
 497         /* a compare with the MIN value */
 498         if (proj_nr == pn_Cmp_Le)
 499           return get_tarval_b_true();
 500         else if (proj_nr == pn_Cmp_Gt)
 501           return get_tarval_b_false();
 502       }
 503       /* x >=/< MIN.  This results in true/false. */
 504       else
 505       if (tab == get_mode_min(mode)) {
 506         /* a compare with the MIN value */
 507         if (proj_nr == pn_Cmp_Ge)
 508           return get_tarval_b_true();
 509         else if (proj_nr == pn_Cmp_Lt)
 510           return get_tarval_b_false();
 511       }
 512       /* MAX >=/< x.  This results in true/false. */
 513       else if (taa == get_mode_max(mode)) {
 514         if (proj_nr == pn_Cmp_Ge)
 515           return get_tarval_b_true();
 516         else if (proj_nr == pn_Cmp_Lt)
 517           return get_tarval_b_false();
 518       }
 519       /* x <=/> MAX.  This results in true/false. */
 520       else if (tab == get_mode_max(mode)) {
 521         if (proj_nr == pn_Cmp_Le)
 522           return get_tarval_b_true();
 523         else if (proj_nr == pn_Cmp_Gt)
 524           return get_tarval_b_false();
 525       }
 526     }
 527     /*
 528      * The predecessors are Allocs or (void*)(0) constants.  Allocs never
 529      * return NULL, they raise an exception.   Therefore we can predict
 530      * the Cmp result.
 531      */
 532     else {
 533       ir_node *aaa = skip_Id(skip_Proj(aa));
 534       ir_node *aba = skip_Id(skip_Proj(ab));
 535
 536       if (   (   (/* aa is ProjP and aaa is Alloc */
 537                      (get_irn_op(aa) == op_Proj)
 538                   && (mode_is_reference(get_irn_mode(aa)))
 539                   && (get_irn_op(aaa) == op_Alloc))
 540               && (   (/* ab is NULL */
 541                          (get_irn_op(ab) == op_Const)
 542                       && (mode_is_reference(get_irn_mode(ab)))
 543                       && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
 544                   || (/* ab is other Alloc */
 545                          (get_irn_op(ab) == op_Proj)
 546                       && (mode_is_reference(get_irn_mode(ab)))
 547                       && (get_irn_op(aba) == op_Alloc)
 548                       && (aaa != aba))))
 549           || (/* aa is NULL and aba is Alloc */
 550                  (get_irn_op(aa) == op_Const)
 551               && (mode_is_reference(get_irn_mode(aa)))
 552               && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
 553               && (get_irn_op(ab) == op_Proj)
 554               && (mode_is_reference(get_irn_mode(ab)))
 555               && (get_irn_op(aba) == op_Alloc)))
 556         /* 3.: */
 557         return new_tarval_from_long(proj_nr & pn_Cmp_Ne, mode_b);
 558     }
 559   }
 560
 561   return computed_value_Cmp_Confirm(a, aa, ab, proj_nr);
 562 }
 563
 564 /**
 565  * return the value of a Proj, handle Proj(Cmp), Proj(Div), Proj(Mod), Proj(DivMod)
 566  */
 567 static tarval *computed_value_Proj(ir_node *n)
 568 {
 569   ir_node *a = get_Proj_pred(n);
 570   long proj_nr;
 571
 572   switch (get_irn_opcode(a)) {
 573   case iro_Cmp:
 574     return computed_value_Proj_Cmp(n);
 575
 576   case iro_DivMod:
 577     /* compute either the Div or the Mod part */
 578     proj_nr = get_Proj_proj(n);
 579     if (proj_nr == pn_DivMod_res_div)
 580       return do_computed_value_Div(get_DivMod_left(a), get_DivMod_right(a));
 581     else if (proj_nr == pn_DivMod_res_mod)
 582       return do_computed_value_Mod(get_DivMod_left(a), get_DivMod_right(a));
 583     break;
 584
 585   case iro_Div:
 586     if (get_Proj_proj(n) == pn_Div_res)
 587       return computed_value(a);
 588     break;
 589
 590   case iro_Mod:
 591     if (get_Proj_proj(n) == pn_Mod_res)
 592       return computed_value(a);
 593     break;
 594
 595   default:
 596     return tarval_bad;
 597   }
 598   return tarval_bad;
 599 }
 600
 601 /**
 602  * calculate the value of a Mux: can be evaluated, if the
 603  * sel and the right input are known
 604  */
 605 static tarval *computed_value_Mux(ir_node *n)
 606 {
 607   ir_node *sel = get_Mux_sel(n);
 608   tarval *ts = value_of(sel);
 609
 610   if (ts == get_tarval_b_true()) {
 611     ir_node *v = get_Mux_true(n);
 612     return value_of(v);
 613   }
 614   else if (ts == get_tarval_b_false()) {
 615     ir_node *v = get_Mux_false(n);
 616     return value_of(v);
 617   }
 618   return tarval_bad;
 619 }
 620
 621 /**
 622  * calculate the value of a Confirm: can be evaluated,
 623  * if it has the form Confirm(x, '=', Const).
 624  */
 625 static tarval *computed_value_Confirm(ir_node *n)
 626 {
 627   return get_Confirm_cmp(n) == pn_Cmp_Eq ?
 628     value_of(get_Confirm_bound(n)) : tarval_bad;
 629 }
 630
 631 /**
 632  * If the parameter n can be computed, return its value, else tarval_bad.
 633  * Performs constant folding.
 634  *
 635  * @param n  The node this should be evaluated
 636  */
 637 tarval *computed_value(ir_node *n)
 638 {
 639   if (n->op->ops.computed_value)
 640     return n->op->ops.computed_value(n);
 641   return tarval_bad;
 642 }
 643
 644 /**
 645  * set the default computed_value evaluator in an ir_op_ops.
 646  *
 647  * @param code   the opcode for the default operation
 648  * @param ops    the operations initialized
 649  *
 650  * @return
 651  *    The operations.
 652  */
 653 static ir_op_ops *firm_set_default_computed_value(opcode code, ir_op_ops *ops)
 654 {
 655 #define CASE(a)                               \
 656   case iro_##a:                               \
 657     ops->computed_value  = computed_value_##a; \
 658     break
 659
 660   switch (code) {
 661   CASE(Const);
 662   CASE(SymConst);
 663   CASE(Add);
 664   CASE(Sub);
 665   CASE(Minus);
 666   CASE(Mul);
 667   CASE(Quot);
 668   CASE(Div);
 669   CASE(Mod);
 670   CASE(Abs);
 671   CASE(And);
 672   CASE(Or);
 673   CASE(Eor);
 674   CASE(Not);
 675   CASE(Shl);
 676   CASE(Shr);
 677   CASE(Shrs);
 678   CASE(Rot);
 679   CASE(Carry);
 680   CASE(Borrow);
 681   CASE(Conv);
 682   CASE(Proj);
 683   CASE(Mux);
 684   CASE(Confirm);
 685   default:
 686     /* leave NULL */;
 687   }
 688
 689   return ops;
 690 #undef CASE
 691 }
 692
 693 #if 0
 694 /* returns 1 if the a and b are pointers to different locations. */
 695 static bool
 696 different_identity (ir_node *a, ir_node *b)
 697 {
 698   assert (mode_is_reference(get_irn_mode (a))
 699           && mode_is_reference(get_irn_mode (b)));
 700
 701   if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
 702     ir_node *a1 = get_Proj_pred (a);
 703     ir_node *b1 = get_Proj_pred (b);
 704     if (a1 != b1 && get_irn_op (a1) == op_Alloc
 705                 && get_irn_op (b1) == op_Alloc)
 706       return 1;
 707   }
 708   return 0;
 709 }
 710 #endif
 711
 712 /**
 713  * Returns a equivalent block for another block.
 714  * If the block has only one predecessor, this is
 715  * the equivalent one. If the only predecessor of a block is
 716  * the block itself, this is a dead block.
 717  *
 718  * If both predecessors of a block are the branches of a binary
 719  * Cond, the equivalent block is Cond's block.
 720  *
 721  * If all predecessors of a block are bad or lies in a dead
 722  * block, the current block is dead as well.
 723  *
 724  * Note, that blocks are NEVER turned into Bad's, instead
 725  * the dead_block flag is set. So, never test for is_Bad(block),
 726  * always use is_dead_Block(block).
 727  */
 728 static ir_node *equivalent_node_Block(ir_node *n)
 729 {
 730   ir_node *oldn = n;
 731   int n_preds   = get_Block_n_cfgpreds(n);
 732
 733   /* The Block constructor does not call optimize, but mature_immBlock
 734      calls the optimization. */
 735   assert(get_Block_matured(n));
 736
 737   /* Straightening: a single entry Block following a single exit Block
 738      can be merged, if it is not the Start block. */
 739   /* !!! Beware, all Phi-nodes of n must have been optimized away.
 740      This should be true, as the block is matured before optimize is called.
 741      But what about Phi-cycles with the Phi0/Id that could not be resolved?
 742      Remaining Phi nodes are just Ids. */
 743    if ((n_preds == 1) && (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp)) {
 744      ir_node *predblock = get_nodes_block(get_Block_cfgpred(n, 0));
 745      if (predblock == oldn) {
 746        /* Jmp jumps into the block it is in -- deal self cycle. */
 747        n = set_Block_dead(n);
 748        DBG_OPT_DEAD_BLOCK(oldn, n);
 749      } else if (get_opt_control_flow_straightening()) {
 750        n = predblock;
 751        DBG_OPT_STG(oldn, n);
 752      }
 753    }
 754    else if ((n_preds == 1) &&
 755             (get_irn_op(skip_Proj(get_Block_cfgpred(n, 0))) == op_Cond)) {
 756      ir_node *predblock = get_Block_cfgpred_block(n, 0);
 757      if (predblock == oldn) {
 758        /* Jmp jumps into the block it is in -- deal self cycle. */
 759        n = set_Block_dead(n);
 760        DBG_OPT_DEAD_BLOCK(oldn, n);
 761      }
 762    }
 763    else if ((n_preds == 2) &&
 764             (get_opt_control_flow_weak_simplification())) {
 765     /* Test whether Cond jumps twice to this block
 766      * The more general case which more than 2 predecessors is handles
 767      * in optimize_cf(), we handle only this special case for speed here.
 768      */
 769     ir_node *a = get_Block_cfgpred(n, 0);
 770     ir_node *b = get_Block_cfgpred(n, 1);
 771
 772     if ((get_irn_op(a) == op_Proj) &&
 773         (get_irn_op(b) == op_Proj) &&
 774         (get_Proj_pred(a) == get_Proj_pred(b)) &&
 775         (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
 776         (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
 777       /* Also a single entry Block following a single exit Block.  Phis have
 778          twice the same operand and will be optimized away. */
 779       n = get_nodes_block(get_Proj_pred(a));
 780       DBG_OPT_IFSIM1(oldn, a, b, n);
 781     }
 782   }
 783   else if (get_opt_unreachable_code() &&
 784            (n != current_ir_graph->start_block) &&
 785            (n != current_ir_graph->end_block)     ) {
 786     int i;
 787
 788     /* If all inputs are dead, this block is dead too, except if it is
 789        the start or end block.  This is one step of unreachable code
 790        elimination */
 791     for (i = get_Block_n_cfgpreds(n) - 1; i >= 0; --i) {
 792       ir_node *pred = get_Block_cfgpred(n, i);
 793       ir_node *pred_blk;
 794
 795       if (is_Bad(pred)) continue;
 796       pred_blk = get_nodes_block(skip_Proj(pred));
 797
 798       if (is_Block_dead(pred_blk)) continue;
 799
 800       if (pred_blk != n) {
 801         /* really found a living input */
 802         break;
 803       }
 804     }
 805     if (i < 0) {
 806       n = set_Block_dead(n);
 807       DBG_OPT_DEAD_BLOCK(oldn, n);
 808     }
 809   }
 810
 811   return n;
 812 }
 813
 814 /**
 815  * Returns a equivalent node for a Jmp, a Bad :-)
 816  * Of course this only happens if the Block of the Jmp is Bad.
 817  */
 818 static ir_node *equivalent_node_Jmp(ir_node *n)
 819 {
 820   /* unreachable code elimination */
 821   if (is_Block_dead(get_nodes_block(n)))
 822     n = new_Bad();
 823
 824   return n;
 825 }
 826
 827 /* Same for op_Raise */
 828 #define equivalent_node_Raise   equivalent_node_Jmp
 829
 830
 831 /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
 832    See transform_node_Proj_Cond(). */
 833
 834 /**
 835  * optimize operations that are commutative and have neutral 0,
 836  * so a op 0 = 0 op a = a.
 837  */
 838 static ir_node *equivalent_node_neutral_zero(ir_node *n)
 839 {
 840   ir_node *oldn = n;
 841
 842   ir_node *a = get_binop_left(n);
 843   ir_node *b = get_binop_right(n);
 844
 845   tarval *tv;
 846   ir_node *on;
 847
 848   /* After running compute_node there is only one constant predecessor.
 849      Find this predecessors value and remember the other node: */
 850   if ((tv = value_of(a)) != tarval_bad) {
 851     on = b;
 852   } else if ((tv = value_of(b)) != tarval_bad) {
 853     on = a;
 854   } else
 855     return n;
 856
 857   /* If this predecessors constant value is zero, the operation is
 858    * unnecessary. Remove it.
 859    *
 860    * Beware: If n is a Add, the mode of on and n might be different
 861    * which happens in this rare construction: NULL + 3.
 862    * Then, a Conv would be needed which we cannot include here.
 863    */
 864   if (classify_tarval (tv) == TV_CLASSIFY_NULL) {
 865     if (get_irn_mode(on) == get_irn_mode(n)) {
 866       n = on;
 867
 868       DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
 869     }
 870   }
 871
 872   return n;
 873 }
 874
 875 #define equivalent_node_Eor  equivalent_node_neutral_zero
 876
 877 /*
 878  * Optimize a - 0 and (a - x) + x (for modes with wrap-around).
 879  *
 880  * The second one looks strange, but this construct
 881  * is used heavily in the LCC sources :-).
 882  *
 883  * Beware: The Mode of an Add may be different than the mode of its
 884  * predecessors, so we could not return a predecessors in all cases.
 885  */
 886 static ir_node *equivalent_node_Add(ir_node *n)
 887 {
 888   ir_node *oldn = n;
 889   ir_node *left, *right;
 890
 891   n = equivalent_node_neutral_zero(n);
 892   if (n != oldn)
 893     return n;
 894
 895   left  = get_Add_left(n);
 896   right = get_Add_right(n);
 897
 898   if (get_irn_op(left) == op_Sub) {
 899     if (get_Sub_right(left) == right) {
 900       /* (a - x) + x */
 901
 902       n = get_Sub_left(left);
 903       if (get_irn_mode(oldn) == get_irn_mode(n)) {
 904         DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
 905         return n;
 906       }
 907     }
 908   }
 909   if (get_irn_op(right) == op_Sub) {
 910     if (get_Sub_right(right) == left) {
 911       /* x + (a - x) */
 912
 913       n = get_Sub_left(right);
 914       if (get_irn_mode(oldn) == get_irn_mode(n)) {
 915         DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
 916         return n;
 917       }
 918     }
 919   }
 920   return n;
 921 }
 922
 923 /**
 924  * optimize operations that are not commutative but have neutral 0 on left,
 925  * so a op 0 = a.
 926  */
 927 static ir_node *equivalent_node_left_zero(ir_node *n)
 928 {
 929   ir_node *oldn = n;
 930
 931   ir_node *a = get_binop_left(n);
 932   ir_node *b = get_binop_right(n);
 933
 934   if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
 935     n = a;
 936
 937     DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
 938   }
 939
 940   return n;
 941 }
 942
 943 #define equivalent_node_Shl   equivalent_node_left_zero
 944 #define equivalent_node_Shr   equivalent_node_left_zero
 945 #define equivalent_node_Shrs  equivalent_node_left_zero
 946 #define equivalent_node_Rot   equivalent_node_left_zero
 947
 948 /**
 949  * Optimize a - 0 and (a + x) - x (for modes with wrap-around).
 950  *
 951  * The second one looks strange, but this construct
 952  * is used heavily in the LCC sources :-).
 953  *
 954  * Beware: The Mode of a Sub may be different than the mode of its
 955  * predecessors, so we could not return a predecessors in all cases.
 956  */
 957 static ir_node *equivalent_node_Sub(ir_node *n)
 958 {
 959   ir_node *oldn = n;
 960
 961   ir_node *a = get_Sub_left(n);
 962   ir_node *b = get_Sub_right(n);
 963
 964   /* Beware: modes might be different */
 965   if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
 966     if (get_irn_mode(n) == get_irn_mode(a)) {
 967       n = a;
 968
 969       DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
 970     }
 971   }
 972   else if (get_irn_op(a) == op_Add) {
 973     ir_mode *mode = get_irn_mode(n);
 974
 975     if (mode_wrap_around(mode)) {
 976       ir_node *left  = get_Add_left(a);
 977       ir_node *right = get_Add_right(a);
 978
 979       if (left == b) {
 980         if (get_irn_mode(n) == get_irn_mode(right)) {
 981           n = right;
 982           DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
 983         }
 984       }
 985       else if (right == b) {
 986         if (get_irn_mode(n) == get_irn_mode(left)) {
 987           n = left;
 988           DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
 989         }
 990       }
 991     }
 992   }
 993
 994   return n;
 995 }
 996
 997
 998 /**
 999  * Optimize an "idempotent unary op", ie op(op(n)) = n.
1000  *
1001  * @todo
1002  *   -(-a) == a, but might overflow two times.
1003  *   We handle it anyway here but the better way would be a
1004  *   flag. This would be needed for Pascal for instance.
1005  */
1006 static ir_node *equivalent_node_idempotent_unop(ir_node *n)
1007 {
1008   ir_node *oldn = n;
1009   ir_node *pred = get_unop_op(n);
1010
1011   /* optimize symmetric unop */
1012   if (get_irn_op(pred) == get_irn_op(n)) {
1013     n = get_unop_op(pred);
1014     DBG_OPT_ALGSIM2(oldn, pred, n);
1015   }
1016   return n;
1017 }
1018
1019 /* Not(Not(x)) == x */
1020 #define equivalent_node_Not    equivalent_node_idempotent_unop
1021
1022 /* --x == x */  /* ??? Is this possible or can --x raise an
1023                        out of bounds exception if min =! max? */
1024 #define equivalent_node_Minus  equivalent_node_idempotent_unop
1025
1026 /**
1027  * Optimize a * 1 = 1 * a = a.
1028  */
1029 static ir_node *equivalent_node_Mul(ir_node *n)
1030 {
1031   ir_node *oldn = n;
1032
1033   ir_node *a = get_Mul_left(n);
1034   ir_node *b = get_Mul_right(n);
1035
1036   /* Mul is commutative and has again an other neutral element. */
1037   if (classify_tarval(value_of(a)) == TV_CLASSIFY_ONE) {
1038     n = b;
1039     DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
1040   } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) {
1041     n = a;
1042     DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
1043   }
1044   return n;
1045 }
1046
1047 /**
1048  * Optimize a / 1 = a.
1049  */
1050 static ir_node *equivalent_node_Div(ir_node *n)
1051 {
1052   ir_node *a = get_Div_left(n);
1053   ir_node *b = get_Div_right(n);
1054
1055   /* Div is not commutative. */
1056   if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
1057     /* Turn Div into a tuple (mem, bad, a) */
1058     ir_node *mem = get_Div_mem(n);
1059     turn_into_tuple(n, pn_Div_max);
1060     set_Tuple_pred(n, pn_Div_M,        mem);
1061     set_Tuple_pred(n, pn_Div_X_except, new_Bad());        /* no exception */
1062     set_Tuple_pred(n, pn_Div_res,      a);
1063   }
1064   return n;
1065 }
1066
1067 /**
1068  * Optimize a / 1 = a.
1069  */
1070 static ir_node *equivalent_node_DivMod(ir_node *n)
1071 {
1072   ir_node *a = get_DivMod_left(n);
1073   ir_node *b = get_DivMod_right(n);
1074
1075   /* Div is not commutative. */
1076   if (classify_tarval(value_of(b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
1077     /* Turn DivMod into a tuple (mem, bad, a, 0) */
1078     ir_node *mem = get_Div_mem(n);
1079     ir_mode *mode = get_irn_mode(b);
1080
1081     turn_into_tuple(n, pn_DivMod_max);
1082     set_Tuple_pred(n, pn_DivMod_M,        mem);
1083     set_Tuple_pred(n, pn_DivMod_X_except, new_Bad());        /* no exception */
1084     set_Tuple_pred(n, pn_DivMod_res_div,  a);
1085     set_Tuple_pred(n, pn_DivMod_res_mod,  new_Const(mode, get_mode_null(mode)));
1086   }
1087   return n;
1088 }
1089
1090 /**
1091  * Use algebraic simplification a | a = a | 0 = 0 | a = a.
1092  */
1093 static ir_node *equivalent_node_Or(ir_node *n)
1094 {
1095   ir_node *oldn = n;
1096
1097   ir_node *a = get_Or_left(n);
1098   ir_node *b = get_Or_right(n);
1099
1100   if (a == b) {
1101     n = a;    /* Or has it's own neutral element */
1102     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_OR);
1103   } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_NULL) {
1104     n = b;
1105     DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_OR);
1106   } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_NULL) {
1107     n = a;
1108     DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_OR);
1109   }
1110
1111   return n;
1112 }
1113
1114 /**
1115  * Optimize a & 0b1...1 = 0b1...1 & a =  a & a = a.
1116  */
1117 static ir_node *equivalent_node_And(ir_node *n)
1118 {
1119   ir_node *oldn = n;
1120
1121   ir_node *a = get_And_left(n);
1122   ir_node *b = get_And_right(n);
1123
1124   if (a == b) {
1125     n = a;    /* And has it's own neutral element */
1126     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_AND);
1127   } else if (classify_tarval(value_of(a)) == TV_CLASSIFY_ALL_ONE) {
1128     n = b;
1129     DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
1130   } else if (classify_tarval(value_of(b)) == TV_CLASSIFY_ALL_ONE) {
1131     n = a;
1132     DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
1133   }
1134   return n;
1135 }
1136
1137 /**
1138  * Try to remove useless Conv's:
1139  */
1140 static ir_node *equivalent_node_Conv(ir_node *n)
1141 {
1142   ir_node *oldn = n;
1143   ir_node *a = get_Conv_op(n);
1144   ir_node *b;
1145
1146   ir_mode *n_mode = get_irn_mode(n);
1147   ir_mode *a_mode = get_irn_mode(a);
1148
1149   if (n_mode == a_mode) { /* No Conv necessary */
1150     n = a;
1151     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CONV);
1152   } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
1153     ir_mode *b_mode;
1154
1155     b = get_Conv_op(a);
1156     n_mode = get_irn_mode(n);
1157     b_mode = get_irn_mode(b);
1158
1159     if (n_mode == b_mode) {
1160       if (n_mode == mode_b) {
1161         n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
1162         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
1163       }
1164       else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
1165         if (smaller_mode(b_mode, a_mode)){
1166           n = b;        /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
1167           DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
1168         }
1169       }
1170     }
1171   }
1172   return n;
1173 }
1174
1175 /**
1176  * A Cast may be removed if the type of the previous node
1177  * is already the type of the Cast.
1178  */
1179 static ir_node *equivalent_node_Cast(ir_node *n) {
1180   ir_node *oldn = n;
1181   ir_node *pred = get_Cast_op(n);
1182
1183   if (get_irn_type(pred) == get_Cast_type(n)) {
1184     n = pred;
1185     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CAST);
1186   }
1187   return n;
1188 }
1189
1190 /**
1191   Several optimizations:
1192    - no Phi in start block.
1193    - remove Id operators that are inputs to Phi
1194    - fold Phi-nodes, iff they have only one predecessor except
1195            themselves.
1196  */
1197 static ir_node *equivalent_node_Phi(ir_node *n)
1198 {
1199   int i, n_preds;
1200
1201   ir_node *oldn = n;
1202   ir_node *block = NULL;     /* to shutup gcc */
1203   ir_node *first_val = NULL; /* to shutup gcc */
1204
1205   if (!get_opt_normalize()) return n;
1206
1207   n_preds = get_Phi_n_preds(n);
1208
1209   block = get_nodes_block(n);
1210   /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
1211      assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
1212   if ((is_Block_dead(block)) ||                  /* Control dead */
1213       (block == current_ir_graph->start_block))  /* There should be no Phi nodes */
1214     return new_Bad();                            /* in the Start Block. */
1215
1216   if (n_preds == 0) return n;           /* Phi of dead Region without predecessors. */
1217
1218   /* If the Block has a Bad pred, we also have one. */
1219   for (i = 0;  i < n_preds;  ++i)
1220     if (is_Bad(get_Block_cfgpred(block, i)))
1221       set_Phi_pred(n, i, new_Bad());
1222
1223   /* Find first non-self-referencing input */
1224   for (i = 0; i < n_preds; ++i) {
1225     first_val = get_Phi_pred(n, i);
1226     if (   (first_val != n)                            /* not self pointer */
1227 #if 1
1228         && (! is_Bad(first_val))
1229 #endif
1230            ) {        /* value not dead */
1231       break;          /* then found first value. */
1232     }
1233   }
1234
1235   if (i >= n_preds) {
1236     /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
1237     return new_Bad();
1238   }
1239
1240   /* search for rest of inputs, determine if any of these
1241      are non-self-referencing */
1242   while (++i < n_preds) {
1243     ir_node *scnd_val = get_Phi_pred(n, i);
1244     if (   (scnd_val != n)
1245         && (scnd_val != first_val)
1246 #if 1
1247         && (! is_Bad(scnd_val))
1248 #endif
1249            ) {
1250       break;
1251     }
1252   }
1253
1254   if (i >= n_preds) {
1255     /* Fold, if no multiple distinct non-self-referencing inputs */
1256     n = first_val;
1257     DBG_OPT_PHI(oldn, n);
1258   }
1259   return n;
1260 }
1261
1262 /**
1263   Several optimizations:
1264    - no Sync in start block.
1265    - fold Sync-nodes, iff they have only one predecessor except
1266            themselves.
1267   @fixme: are there loop's in Sync's
1268  */
1269 static ir_node *equivalent_node_Sync(ir_node *n)
1270 {
1271   int i, n_preds;
1272
1273   ir_node *oldn = n;
1274   ir_node *first_val = NULL; /* to shutup gcc */
1275
1276   if (!get_opt_normalize()) return n;
1277
1278   n_preds = get_Sync_n_preds(n);
1279
1280   /* Find first non-self-referencing input */
1281   for (i = 0; i < n_preds; ++i) {
1282     first_val = get_Sync_pred(n, i);
1283     if ((first_val != n)  /* not self pointer */ &&
1284         (! is_Bad(first_val))
1285        ) {            /* value not dead */
1286       break;          /* then found first value. */
1287     }
1288   }
1289
1290   if (i >= n_preds)
1291     /* A totally Bad or self-referencing Sync (we didn't break the above loop) */
1292     return new_Bad();
1293
1294   /* search the rest of inputs, determine if any of these
1295      are non-self-referencing */
1296   while (++i < n_preds) {
1297     ir_node *scnd_val = get_Sync_pred(n, i);
1298     if ((scnd_val != n) &&
1299         (scnd_val != first_val) &&
1300         (! is_Bad(scnd_val))
1301        )
1302       break;
1303   }
1304
1305   if (i >= n_preds) {
1306     /* Fold, if no multiple distinct non-self-referencing inputs */
1307     n = first_val;
1308     DBG_OPT_SYNC(oldn, n);
1309   }
1310   return n;
1311 }
1312
1313 /**
1314  * optimize Proj(Tuple) and gigo() for ProjX in Bad block,
1315  * ProjX(Load) and ProjX(Store)
1316  */
1317 static ir_node *equivalent_node_Proj(ir_node *n)
1318 {
1319   ir_node *oldn = n;
1320
1321   ir_node *a = get_Proj_pred(n);
1322
1323   if ( get_irn_op(a) == op_Tuple) {
1324     /* Remove the Tuple/Proj combination. */
1325     if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
1326       n = get_Tuple_pred(a, get_Proj_proj(n));
1327       DBG_OPT_TUPLE(oldn, a, n);
1328     } else {
1329       assert(0); /* This should not happen! */
1330       n = new_Bad();
1331     }
1332   }
1333   else if (get_irn_mode(n) == mode_X) {
1334     if (is_Block_dead(get_nodes_block(skip_Proj(n)))) {
1335       /* Remove dead control flow -- early gigo(). */
1336       n = new_Bad();
1337     }
1338     else if (get_opt_ldst_only_null_ptr_exceptions()) {
1339       ir_op *op = get_irn_op(a);
1340
1341       if (op == op_Load || op == op_Store) {
1342         /* get the load/store address */
1343         ir_node *addr = get_irn_n(a, 1);
1344         if (value_not_null(addr)) {
1345           /* this node may float */
1346           set_irn_pinned(a, op_pin_state_floats);
1347           DBG_OPT_EXC_REM(n);
1348           return new_Bad();
1349         }
1350       }
1351     }
1352   }
1353
1354   return n;
1355 }
1356
1357 /**
1358  * Remove Id's.
1359  */
1360 static ir_node *equivalent_node_Id(ir_node *n)
1361 {
1362   ir_node *oldn = n;
1363
1364   do {
1365     n = get_Id_pred(n);
1366   } while (get_irn_op(n) == op_Id);
1367
1368   DBG_OPT_ID(oldn, n);
1369   return n;
1370 }
1371
1372 /**
1373  * optimize a Mux
1374  */
1375 static ir_node *equivalent_node_Mux(ir_node *n)
1376 {
1377   ir_node *oldn = n, *sel = get_Mux_sel(n);
1378   tarval *ts = value_of(sel);
1379
1380   /* Mux(true, f, t) == t */
1381   if (ts == tarval_b_true) {
1382     n = get_Mux_true(n);
1383     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_C);
1384   }
1385   /* Mux(false, f, t) == f */
1386   else if (ts == tarval_b_false) {
1387     n = get_Mux_false(n);
1388     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_C);
1389   }
1390   /* Mux(v, x, x) == x */
1391   else if (get_Mux_false(n) == get_Mux_true(n)) {
1392     n = get_Mux_true(n);
1393     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_EQ);
1394   }
1395   else if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(get_irn_mode(n))) {
1396     ir_node *cmp = get_Proj_pred(sel);
1397     long proj_nr = get_Proj_proj(sel);
1398     ir_node *b   = get_Mux_false(n);
1399     ir_node *a   = get_Mux_true(n);
1400
1401     /*
1402      * Note: normalization puts the constant on the right site,
1403      * so we check only one case.
1404      *
1405      * Note further that these optimization work even for floating point
1406      * with NaN's because -NaN == NaN.
1407      * However, if +0 and -0 is handled differently, we cannot use the first one.
1408      */
1409     if (get_irn_op(cmp) == op_Cmp && get_Cmp_left(cmp) == a) {
1410       if (classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
1411         /* Mux(a CMP 0, X, a) */
1412         if (get_irn_op(b) == op_Minus && get_Minus_op(b) == a) {
1413           /* Mux(a CMP 0, -a, a) */
1414           if (proj_nr == pn_Cmp_Eq) {
1415             /* Mux(a == 0, -a, a)  ==>  -a */
1416             n = b;
1417             DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1418           }
1419           else if (proj_nr == pn_Cmp_Lg || proj_nr == pn_Cmp_Ne) {
1420             /* Mux(a != 0, -a, a)  ==> a */
1421             n = a;
1422             DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1423           }
1424         }
1425         else if (classify_Const(b) == CNST_NULL) {
1426           /* Mux(a CMP 0, 0, a) */
1427           if (proj_nr == pn_Cmp_Lg || proj_nr == pn_Cmp_Ne) {
1428             /* Mux(a != 0, 0, a) ==> a */
1429             n = a;
1430             DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1431           }
1432           else if (proj_nr == pn_Cmp_Eq) {
1433             /* Mux(a == 0, 0, a) ==> 0 */
1434             n = b;
1435             DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1436           }
1437         }
1438       }
1439     }
1440   }
1441   return n;
1442 }
1443
1444 /**
1445  * Optimize -a CMP -b into b CMP a.
1446  * This works only for for modes where unary Minus
1447  * cannot Overflow.
1448  * Note that two-complement integers can Overflow
1449  * so it will NOT work.
1450  */
1451 static ir_node *equivalent_node_Cmp(ir_node *n)
1452 {
1453   ir_node *left  = get_Cmp_left(n);
1454   ir_node *right = get_Cmp_right(n);
1455
1456   if (get_irn_op(left) == op_Minus && get_irn_op(right) == op_Minus &&
1457       !mode_overflow_on_unary_Minus(get_irn_mode(left))) {
1458     left  = get_Minus_op(left);
1459     right = get_Minus_op(right);
1460     set_Cmp_left(n, right);
1461     set_Cmp_right(n, left);
1462   }
1463   return n;
1464 }
1465
1466 /**
1467  * Remove Confirm nodes if setting is on.
1468  * Replace Confirms(x, '=', Constlike) by Constlike.
1469  */
1470 static ir_node *equivalent_node_Confirm(ir_node *n)
1471 {
1472   ir_node *pred = get_Confirm_value(n);
1473   pn_Cmp  pnc   = get_Confirm_cmp(n);
1474
1475   if (get_irn_op(pred) == op_Confirm && pnc == get_Confirm_cmp(pred)) {
1476     /*
1477      * rare case: two identical Confirms one after another,
1478      * replace the second one with the first.
1479      */
1480     n = pred;
1481   }
1482   if (pnc == pn_Cmp_Eq) {
1483     ir_node *bound = get_Confirm_bound(n);
1484
1485     /*
1486      * Optimize a rare case:
1487      * Confirm(x, '=', Constlike) ==> Constlike
1488      */
1489     if (is_irn_constlike(bound)) {
1490       DBG_OPT_CONFIRM(n, bound);
1491       return bound;
1492     }
1493   }
1494   return get_opt_remove_confirm() ? get_Confirm_value(n) : n;
1495 }
1496
1497 /**
1498  * Optimize CopyB(mem, x, x) into a Nop
1499  */
1500 static ir_node *equivalent_node_CopyB(ir_node *n)
1501 {
1502   ir_node *a = get_CopyB_dst(n);
1503   ir_node *b = get_CopyB_src(n);
1504
1505   if (a == b) {
1506     /* Turn CopyB into a tuple (mem, bad, bad) */
1507     ir_node *mem = get_CopyB_mem(n);
1508     turn_into_tuple(n, pn_CopyB_max);
1509     set_Tuple_pred(n, pn_CopyB_M,        mem);
1510     set_Tuple_pred(n, pn_CopyB_X_except, new_Bad());        /* no exception */
1511     set_Tuple_pred(n, pn_Call_M_except,  new_Bad());
1512   }
1513   return n;
1514 }
1515
1516 /**
1517  * Optimize Bounds(idx, idx, upper) into idx.
1518  */
1519 static ir_node *equivalent_node_Bound(ir_node *n)
1520 {
1521   ir_node *idx   = get_Bound_index(n);
1522   ir_node *lower = get_Bound_lower(n);
1523   int ret_tuple = 0;
1524
1525   /* By definition lower < upper, so if idx == lower -->
1526      lower <= idx && idx < upper */
1527   if (idx == lower) {
1528     /* Turn Bound into a tuple (mem, bad, idx) */
1529     ret_tuple = 1;
1530   }
1531   else {
1532     ir_node *pred = skip_Proj(idx);
1533
1534     if (get_irn_op(pred) == op_Bound) {
1535       /*
1536        * idx was Bounds_check previously, it is still valid if
1537        * lower <= pred_lower && pred_upper <= upper.
1538        */
1539       ir_node *upper = get_Bound_upper(n);
1540        if (get_Bound_lower(pred) == lower &&
1541            get_Bound_upper(pred) == upper) {
1542          /*
1543           * One could expect that we simple return the previous
1544           * Bound here. However, this would be wrong, as we could
1545           * add an exception Proj to a new location than.
1546           * So, we must turn in into a tuple
1547           */
1548          ret_tuple = 1;
1549        }
1550     }
1551   }
1552   if (ret_tuple) {
1553     /* Turn Bound into a tuple (mem, bad, idx) */
1554     ir_node *mem = get_Bound_mem(n);
1555     turn_into_tuple(n, pn_Bound_max);
1556     set_Tuple_pred(n, pn_Bound_M_regular, mem);
1557     set_Tuple_pred(n, pn_Bound_X_except,  new_Bad());       /* no exception */
1558     set_Tuple_pred(n, pn_Bound_res,       idx);
1559     set_Tuple_pred(n, pn_Bound_M_except,  mem);
1560   }
1561   return n;
1562 }
1563
1564 /**
1565  * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1566  * perform no actual computation, as, e.g., the Id nodes.  It does not create
1567  * new nodes.  It is therefore safe to free n if the node returned is not n.
1568  * If a node returns a Tuple we can not just skip it.  If the size of the
1569  * in array fits, we transform n into a tuple (e.g., Div).
1570  */
1571 ir_node *
1572 equivalent_node(ir_node *n)
1573 {
1574   if (n->op->ops.equivalent_node)
1575     return n->op->ops.equivalent_node(n);
1576   return n;
1577 }
1578
1579 /**
1580  * sets the default equivalent node operation for an ir_op_ops.
1581  *
1582  * @param code   the opcode for the default operation
1583  * @param ops    the operations initialized
1584  *
1585  * @return
1586  *    The operations.
1587  */
1588 static ir_op_ops *firm_set_default_equivalent_node(opcode code, ir_op_ops *ops)
1589 {
1590 #define CASE(a)                                 \
1591   case iro_##a:                                 \
1592     ops->equivalent_node  = equivalent_node_##a; \
1593     break
1594
1595   switch (code) {
1596   CASE(Block);
1597   CASE(Jmp);
1598   CASE(Raise);
1599   CASE(Or);
1600   CASE(Add);
1601   CASE(Eor);
1602   CASE(Sub);
1603   CASE(Shl);
1604   CASE(Shr);
1605   CASE(Shrs);
1606   CASE(Rot);
1607   CASE(Not);
1608   CASE(Minus);
1609   CASE(Mul);
1610   CASE(Div);
1611   CASE(DivMod);
1612   CASE(And);
1613   CASE(Conv);
1614   CASE(Cast);
1615   CASE(Phi);
1616   CASE(Sync);
1617   CASE(Proj);
1618   CASE(Id);
1619   CASE(Mux);
1620   CASE(Cmp);
1621   CASE(Confirm);
1622   CASE(CopyB);
1623   CASE(Bound);
1624   default:
1625     /* leave NULL */;
1626   }
1627
1628   return ops;
1629 #undef CASE
1630 }
1631
1632 /**
1633  * Do node specific optimizations of nodes predecessors.
1634  */
1635 static void
1636 optimize_preds(ir_node *n) {
1637   ir_node *a = NULL, *b = NULL;
1638
1639   /* get the operands we will work on for simple cases. */
1640   if (is_binop(n)) {
1641     a = get_binop_left(n);
1642     b = get_binop_right(n);
1643   } else if (is_unop(n)) {
1644     a = get_unop_op(n);
1645   }
1646
1647   switch (get_irn_opcode(n)) {
1648
1649   case iro_Cmp:
1650     /* We don't want Cast as input to Cmp. */
1651     if (get_irn_op(a) == op_Cast) {
1652       a = get_Cast_op(a);
1653       set_Cmp_left(n, a);
1654     }
1655     if (get_irn_op(b) == op_Cast) {
1656       b = get_Cast_op(b);
1657       set_Cmp_right(n, b);
1658     }
1659     break;
1660
1661   default: break;
1662   } /* end switch */
1663 }
1664
1665 /**
1666  * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1667  * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)).
1668  * If possible, remove the Conv's.
1669  */
1670 static ir_node *transform_node_AddSub(ir_node *n)
1671 {
1672   ir_mode *mode = get_irn_mode(n);
1673
1674   if (mode_is_reference(mode)) {
1675     ir_node *left  = get_binop_left(n);
1676     ir_node *right = get_binop_right(n);
1677     int ref_bits   = get_mode_size_bits(mode);
1678
1679     if (get_irn_op(left) == op_Conv) {
1680       ir_mode *mode = get_irn_mode(left);
1681       int bits      = get_mode_size_bits(mode);
1682
1683       if (ref_bits == bits &&
1684           mode_is_int(mode) &&
1685           get_mode_arithmetic(mode) == irma_twos_complement) {
1686         ir_node *pre      = get_Conv_op(left);
1687         ir_mode *pre_mode = get_irn_mode(pre);
1688
1689         if (mode_is_int(pre_mode) &&
1690             get_mode_size_bits(pre_mode) == bits &&
1691             get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1692           /* ok, this conv just changes to sign, moreover the calculation
1693            * is done with same number of bits as our address mode, so
1694            * we can ignore the conv as address calculation can be viewed
1695            * as either signed or unsigned
1696            */
1697           set_binop_left(n, pre);
1698         }
1699       }
1700     }
1701
1702     if (get_irn_op(right) == op_Conv) {
1703       ir_mode *mode = get_irn_mode(right);
1704       int bits      = get_mode_size_bits(mode);
1705
1706       if (ref_bits == bits &&
1707           mode_is_int(mode) &&
1708           get_mode_arithmetic(mode) == irma_twos_complement) {
1709         ir_node *pre      = get_Conv_op(right);
1710         ir_mode *pre_mode = get_irn_mode(pre);
1711
1712         if (mode_is_int(pre_mode) &&
1713             get_mode_size_bits(pre_mode) == bits &&
1714             get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1715           /* ok, this conv just changes to sign, moreover the calculation
1716            * is done with same number of bits as our address mode, so
1717            * we can ignore the conv as address calculation can be viewed
1718            * as either signed or unsigned
1719            */
1720           set_binop_right(n, pre);
1721         }
1722       }
1723     }
1724   }
1725   return n;
1726 }
1727
1728 /**
1729  * Do the AddSub optimization, then Transform
1730  *   Add(a,a)          -> Mul(a, 2)
1731  *   Add(Mul(a, x), a) -> Mul(a, x+1)
1732  * if the mode is integer or float.
1733  * Transform Add(a,-b) into Sub(a,b).
1734  * Reassociation might fold this further.
1735  */
1736 static ir_node *transform_node_Add(ir_node *n)
1737 {
1738   ir_mode *mode;
1739   ir_node *oldn = n;
1740
1741   n = transform_node_AddSub(n);
1742
1743   mode = get_irn_mode(n);
1744   if (mode_is_num(mode)) {
1745     ir_node *a = get_Add_left(n);
1746     ir_node *b = get_Add_right(n);
1747
1748     if (a == b) {
1749       ir_node *block = get_irn_n(n, -1);
1750
1751       n = new_rd_Mul(
1752             get_irn_dbg_info(n),
1753             current_ir_graph,
1754             block,
1755             a,
1756             new_r_Const_long(current_ir_graph, block, mode, 2),
1757             mode);
1758       DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_A);
1759     }
1760     else if (get_irn_op(a) == op_Minus) {
1761       n = new_rd_Sub(
1762           get_irn_dbg_info(n),
1763           current_ir_graph,
1764           get_irn_n(n, -1),
1765           b,
1766           get_Minus_op(a),
1767           mode);
1768       DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
1769     }
1770     else if (get_irn_op(b) == op_Minus) {
1771       n = new_rd_Sub(
1772           get_irn_dbg_info(n),
1773           current_ir_graph,
1774           get_irn_n(n, -1),
1775           a,
1776           get_Minus_op(b),
1777           mode);
1778       DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
1779     }
1780     /* do NOT execute this code if reassociation is enabled, it does the inverse! */
1781     else if (!get_opt_reassociation() && get_irn_op(a) == op_Mul) {
1782       ir_node *ma = get_Mul_left(a);
1783       ir_node *mb = get_Mul_right(a);
1784
1785       if (b == ma) {
1786         ir_node *blk = get_irn_n(n, -1);
1787         n = new_rd_Mul(
1788           get_irn_dbg_info(n), current_ir_graph, blk,
1789           ma,
1790           new_rd_Add(
1791             get_irn_dbg_info(n), current_ir_graph, blk,
1792             mb,
1793             new_r_Const_long(current_ir_graph, blk, mode, 1),
1794             mode),
1795           mode);
1796         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
1797       }
1798       else if (b == mb) {
1799         ir_node *blk = get_irn_n(n, -1);
1800         n = new_rd_Mul(
1801           get_irn_dbg_info(n), current_ir_graph, blk,
1802           mb,
1803           new_rd_Add(
1804             get_irn_dbg_info(n), current_ir_graph, blk,
1805             ma,
1806             new_r_Const_long(current_ir_graph, blk, mode, 1),
1807             mode),
1808           mode);
1809         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
1810       }
1811     }
1812     /* do NOT execute this code if reassociation is enabled, it does the inverse! */
1813     else if (!get_opt_reassociation() && get_irn_op(b) == op_Mul) {
1814       ir_node *ma = get_Mul_left(b);
1815       ir_node *mb = get_Mul_right(b);
1816
1817       if (a == ma) {
1818         ir_node *blk = get_irn_n(n, -1);
1819         n = new_rd_Mul(
1820           get_irn_dbg_info(n), current_ir_graph, blk,
1821           ma,
1822           new_rd_Add(
1823             get_irn_dbg_info(n), current_ir_graph, blk,
1824             mb,
1825             new_r_Const_long(current_ir_graph, blk, mode, 1),
1826             mode),
1827           mode);
1828         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
1829       }
1830       else if (a == mb) {
1831         ir_node *blk = get_irn_n(n, -1);
1832         n = new_rd_Mul(
1833           get_irn_dbg_info(n), current_ir_graph, blk,
1834           mb,
1835           new_rd_Add(
1836             get_irn_dbg_info(n), current_ir_graph, blk,
1837             ma,
1838             new_r_Const_long(current_ir_graph, blk, mode, 1),
1839             mode),
1840           mode);
1841         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_MUL_A_X_A);
1842       }
1843     }
1844   }
1845   return n;
1846 }
1847
1848 /**
1849  * Do the AddSub optimization, then Transform
1850  *   Sub(0,a)          -> Minus(a)
1851  *   Sub(Mul(a, x), a) -> Mul(a, x-1)
1852  */
1853 static ir_node *transform_node_Sub(ir_node *n)
1854 {
1855   ir_mode *mode;
1856   ir_node *oldn = n;
1857   ir_node *a, *b;
1858
1859   n = transform_node_AddSub(n);
1860
1861   mode = get_irn_mode(n);
1862   a    = get_Sub_left(n);
1863   b    = get_Sub_right(n);
1864   if (mode_is_num(mode) && (classify_Const(a) == CNST_NULL)) {
1865     n = new_rd_Minus(
1866           get_irn_dbg_info(n),
1867           current_ir_graph,
1868           get_irn_n(n, -1),
1869           b,
1870           mode);
1871     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_0_A);
1872   }
1873   /* do NOT execute this code if reassociation is enabled, it does the inverse! */
1874   else if (get_opt_reassociation() && get_irn_op(a) == op_Mul) {
1875     ir_node *ma = get_Mul_left(a);
1876     ir_node *mb = get_Mul_right(a);
1877
1878     if (ma == b) {
1879       ir_node *blk = get_irn_n(n, -1);
1880       n = new_rd_Mul(
1881         get_irn_dbg_info(n),
1882         current_ir_graph, blk,
1883         ma,
1884         new_rd_Sub(
1885           get_irn_dbg_info(n),
1886           current_ir_graph, blk,
1887           mb,
1888           new_r_Const_long(current_ir_graph, blk, mode, 1),
1889           mode),
1890         mode);
1891       DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
1892     }
1893     else if (mb == b) {
1894       ir_node *blk = get_irn_n(n, -1);
1895       n = new_rd_Mul(
1896         get_irn_dbg_info(n),
1897         current_ir_graph, blk,
1898         mb,
1899         new_rd_Sub(
1900           get_irn_dbg_info(n),
1901           current_ir_graph, blk,
1902           ma,
1903           new_r_Const_long(current_ir_graph, blk, mode, 1),
1904           mode),
1905         mode);
1906       DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
1907     }
1908   }
1909
1910   return n;
1911 }
1912
1913 /**
1914  * Transform Mul(a,-1) into -a.
1915  * Do architecture dependent optimizations on Mul nodes
1916  */
1917 static ir_node *transform_node_Mul(ir_node *n) {
1918   ir_node *oldn = n;
1919   ir_mode *mode = get_irn_mode(n);
1920
1921   if (mode_is_signed(mode)) {
1922     ir_node *r = NULL;
1923     ir_node *a = get_Mul_left(n);
1924     ir_node *b = get_Mul_right(n);
1925
1926     if (value_of(a) == get_mode_minus_one(mode))
1927       r = b;
1928     else if (value_of(b) == get_mode_minus_one(mode))
1929       r = a;
1930     if (r) {
1931       n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1), r, mode);
1932       DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS_1);
1933       return n;
1934     }
1935   }
1936   return arch_dep_replace_mul_with_shifts(n);
1937 }
1938
1939 /**
1940  * transform a Div Node
1941  */
1942 static ir_node *transform_node_Div(ir_node *n)
1943 {
1944   tarval *tv = value_of(n);
1945   ir_node *value = n;
1946
1947   /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
1948
1949   if (tv != tarval_bad) {
1950     value = new_Const(get_tarval_mode(tv), tv);
1951
1952     DBG_OPT_CSTEVAL(n, value);
1953   }
1954   else /* Try architecture dependent optimization */
1955     value = arch_dep_replace_div_by_const(n);
1956
1957   if (value != n) {
1958     /* Turn Div into a tuple (mem, bad, value) */
1959     ir_node *mem = get_Div_mem(n);
1960
1961     turn_into_tuple(n, pn_Div_max);
1962     set_Tuple_pred(n, pn_Div_M, mem);
1963     set_Tuple_pred(n, pn_Div_X_except, new_Bad());
1964     set_Tuple_pred(n, pn_Div_res, value);
1965   }
1966   return n;
1967 }
1968
1969 /**
1970  * transform a Mod node
1971  */
1972 static ir_node *transform_node_Mod(ir_node *n)
1973 {
1974   tarval *tv = value_of(n);
1975   ir_node *value = n;
1976
1977   /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
1978
1979   if (tv != tarval_bad) {
1980     value = new_Const(get_tarval_mode(tv), tv);
1981
1982     DBG_OPT_CSTEVAL(n, value);
1983   }
1984   else /* Try architecture dependent optimization */
1985     value = arch_dep_replace_mod_by_const(n);
1986
1987   if (value != n) {
1988     /* Turn Mod into a tuple (mem, bad, value) */
1989     ir_node *mem = get_Mod_mem(n);
1990
1991     turn_into_tuple(n, pn_Mod_max);
1992     set_Tuple_pred(n, pn_Mod_M, mem);
1993     set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
1994     set_Tuple_pred(n, pn_Mod_res, value);
1995   }
1996   return n;
1997 }
1998
1999 /**
2000  * transform a DivMod node
2001  */
2002 static ir_node *transform_node_DivMod(ir_node *n)
2003 {
2004   int evaluated = 0;
2005
2006   ir_node *a = get_DivMod_left(n);
2007   ir_node *b = get_DivMod_right(n);
2008   ir_mode *mode = get_irn_mode(a);
2009   tarval *ta = value_of(a);
2010   tarval *tb = value_of(b);
2011
2012   if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
2013     return n;
2014
2015   /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
2016
2017   if (tb != tarval_bad) {
2018     if (tb == get_mode_one(get_tarval_mode(tb))) {
2019       b = new_Const (mode, get_mode_null(mode));
2020       evaluated = 1;
2021
2022       DBG_OPT_CSTEVAL(n, b);
2023     }
2024     else if (ta != tarval_bad) {
2025       tarval *resa, *resb;
2026       resa = tarval_div (ta, tb);
2027       if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
2028                                         Jmp for X result!? */
2029       resb = tarval_mod (ta, tb);
2030       if (resb == tarval_bad) return n; /* Causes exception! */
2031       a = new_Const (mode, resa);
2032       b = new_Const (mode, resb);
2033       evaluated = 1;
2034
2035       DBG_OPT_CSTEVAL(n, a);
2036       DBG_OPT_CSTEVAL(n, b);
2037     }
2038     else { /* Try architecture dependent optimization */
2039       arch_dep_replace_divmod_by_const(&a, &b, n);
2040       evaluated = a != NULL;
2041     }
2042   } else if (ta == get_mode_null(mode)) {
2043     /* 0 / non-Const = 0 */
2044     b = a;
2045     evaluated = 1;
2046   }
2047
2048   if (evaluated) { /* replace by tuple */
2049     ir_node *mem = get_DivMod_mem(n);
2050     turn_into_tuple(n, pn_DivMod_max);
2051     set_Tuple_pred(n, pn_DivMod_M,        mem);
2052     set_Tuple_pred(n, pn_DivMod_X_except, new_Bad());  /* no exception */
2053     set_Tuple_pred(n, pn_DivMod_res_div,  a);
2054     set_Tuple_pred(n, pn_DivMod_res_mod,  b);
2055   }
2056
2057   return n;
2058 }
2059
2060 /**
2061  * Optimize Abs(x) into  x if x is Confirmed >= 0
2062  * Optimize Abs(x) into -x if x is Confirmed <= 0
2063  */
2064 static ir_node *transform_node_Abs(ir_node *n)
2065 {
2066   ir_node        *oldn = n;
2067   ir_node        *a = get_Abs_op(n);
2068   value_classify sign = classify_value_sign(a);
2069
2070   if (sign == VALUE_NEGATIVE) {
2071     ir_mode *mode = get_irn_mode(n);
2072
2073     /*
2074      * We can replace the Abs by -x here.
2075      * We even could add a new Confirm here.
2076      *
2077      * Note that -x would create a new node, so we could
2078      * not run it in the equivalent_node() context.
2079      */
2080     n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph,
2081                      get_irn_n(n, -1), a, mode);
2082
2083     DBG_OPT_CONFIRM(oldn, n);
2084   }
2085   else if (sign == VALUE_POSITIVE) {
2086     /* n is positive, Abs is not needed */
2087     n = a;
2088
2089     DBG_OPT_CONFIRM(oldn, n);
2090   }
2091
2092   return n;
2093 }
2094
2095 /**
2096  * transform a Cond node
2097  */
2098 static ir_node *transform_node_Cond(ir_node *n)
2099 {
2100   /* Replace the Cond by a Jmp if it branches on a constant
2101      condition. */
2102   ir_node *jmp;
2103   ir_node *a = get_Cond_selector(n);
2104   tarval *ta = value_of(a);
2105
2106   /* we need block info which is not available in floating irgs */
2107   if (get_irg_pinned(current_ir_graph) == op_pin_state_floats)
2108      return n;
2109
2110   if ((ta != tarval_bad) &&
2111       (get_irn_mode(a) == mode_b) &&
2112       (get_opt_unreachable_code())) {
2113     /* It's a boolean Cond, branching on a boolean constant.
2114                Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
2115     jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
2116     turn_into_tuple(n, pn_Cond_max);
2117     if (ta == tarval_b_true) {
2118       set_Tuple_pred(n, pn_Cond_false, new_Bad());
2119       set_Tuple_pred(n, pn_Cond_true, jmp);
2120     } else {
2121       set_Tuple_pred(n, pn_Cond_false, jmp);
2122       set_Tuple_pred(n, pn_Cond_true, new_Bad());
2123     }
2124     /* We might generate an endless loop, so keep it alive. */
2125     add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
2126   }
2127   return n;
2128 }
2129
2130 /**
2131  * Transform an Eor.
2132  */
2133 static ir_node *transform_node_Eor(ir_node *n)
2134 {
2135   ir_node *oldn = n;
2136   ir_node *a = get_Eor_left(n);
2137   ir_node *b = get_Eor_right(n);
2138   ir_mode *mode = get_irn_mode(n);
2139
2140   if (a == b) {
2141     /* a ^ a = 0 */
2142     n = new_rd_Const(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1),
2143                      mode, get_mode_null(mode));
2144     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_A_A);
2145   }
2146   else if ((mode == mode_b)
2147       && (get_irn_op(a) == op_Proj)
2148       && (get_irn_mode(a) == mode_b)
2149       && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
2150       && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
2151     /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
2152     n = new_r_Proj(current_ir_graph, get_irn_n(n, -1), get_Proj_pred(a),
2153                    mode_b, get_negated_pnc(get_Proj_proj(a), mode));
2154
2155     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT_BOOL);
2156   }
2157   else if ((mode == mode_b)
2158         && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)) {
2159     /* The Eor is a Not. Replace it by a Not. */
2160     /*   ????!!!Extend to bitfield 1111111. */
2161     n = new_r_Not(current_ir_graph, get_irn_n(n, -1), a, mode_b);
2162
2163     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
2164   }
2165
2166   return n;
2167 }
2168
2169 /**
2170  * Transform a boolean Not.
2171  */
2172 static ir_node *transform_node_Not(ir_node *n)
2173 {
2174   ir_node *oldn = n;
2175   ir_node *a = get_Not_op(n);
2176
2177   if (   (get_irn_mode(n) == mode_b)
2178       && (get_irn_op(a) == op_Proj)
2179       && (get_irn_mode(a) == mode_b)
2180       && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
2181     /* We negate a Cmp. The Cmp has the negated result anyways! */
2182     n = new_r_Proj(current_ir_graph, get_irn_n(n, -1), get_Proj_pred(a),
2183                    mode_b, get_negated_pnc(get_Proj_proj(a), mode_b));
2184     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_CMP);
2185   }
2186
2187   return n;
2188 }
2189
2190 /**
2191  * Transform a Cast_type(Const) into a new Const_type
2192  */
2193 static ir_node *transform_node_Cast(ir_node *n) {
2194   ir_node *oldn = n;
2195   ir_node *pred = get_Cast_op(n);
2196   ir_type *tp = get_irn_type(n);
2197
2198   if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
2199     n = new_rd_Const_type(NULL, current_ir_graph, get_irn_n(pred, -1), get_irn_mode(pred),
2200               get_Const_tarval(pred), tp);
2201     DBG_OPT_CSTEVAL(oldn, n);
2202   } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
2203     n = new_rd_SymConst_type(NULL, current_ir_graph, get_irn_n(pred, -1), get_SymConst_symbol(pred),
2204                  get_SymConst_kind(pred), tp);
2205     DBG_OPT_CSTEVAL(oldn, n);
2206   }
2207
2208   return n;
2209 }
2210
2211 /**
2212  * Transform a Proj(Div) with a non-zero value.
2213  * Removes the exceptions and routes the memory to the NoMem node.
2214  */
2215 static ir_node *transform_node_Proj_Div(ir_node *proj)
2216 {
2217   ir_node *n = get_Proj_pred(proj);
2218   ir_node *b = get_Div_right(n);
2219   long proj_nr;
2220
2221   if (value_not_zero(b)) {
2222     /* div(x, y) && y != 0 */
2223     proj_nr = get_Proj_proj(proj);
2224
2225     /* this node may float */
2226     set_irn_pinned(n, op_pin_state_floats);
2227
2228     if (proj_nr == pn_Div_X_except) {
2229       /* we found an exception handler, remove it */
2230       DBG_OPT_EXC_REM(proj);
2231       return new_Bad();
2232     } else if (proj_nr == pn_Div_M) {
2233       /* the memory Proj can be removed */
2234       ir_node *res = get_Div_mem(n);
2235       set_Div_mem(n, get_irg_no_mem(current_ir_graph));
2236
2237       return res;
2238     }
2239   }
2240   return proj;
2241 }
2242
2243 /**
2244  * Transform a Proj(Mod) with a non-zero value.
2245  * Removes the exceptions and routes the memory to the NoMem node.
2246  */
2247 static ir_node *transform_node_Proj_Mod(ir_node *proj)
2248 {
2249   ir_node *n = get_Proj_pred(proj);
2250   ir_node *b = get_Mod_right(n);
2251   long proj_nr;
2252
2253   if (value_not_zero(b)) {
2254     /* mod(x, y) && y != 0 */
2255     proj_nr = get_Proj_proj(proj);
2256
2257     /* this node may float */
2258     set_irn_pinned(n, op_pin_state_floats);
2259
2260     if (proj_nr == pn_Mod_X_except) {
2261       /* we found an exception handler, remove it */
2262       DBG_OPT_EXC_REM(proj);
2263       return new_Bad();
2264     } else if (proj_nr == pn_Mod_M) {
2265       /* the memory Proj can be removed */
2266       ir_node *res = get_Mod_mem(n);
2267       set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
2268
2269       return res;
2270     }
2271     else if (proj_nr == pn_Mod_res && get_Mod_left(n) == b) {
2272       /* a % a = 0 if a != 0 */
2273       ir_mode *mode = get_irn_mode(proj);
2274       ir_node *res  = new_Const(mode, get_mode_null(mode));
2275
2276       DBG_OPT_CSTEVAL(n, res);
2277       return res;
2278     }
2279   }
2280   return proj;
2281 }
2282
2283 /**
2284  * Transform a Proj(DivMod) with a non-zero value.
2285  * Removes the exceptions and routes the memory to the NoMem node.
2286  */
2287 static ir_node *transform_node_Proj_DivMod(ir_node *proj)
2288 {
2289   ir_node *n = get_Proj_pred(proj);
2290   ir_node *b = get_DivMod_right(n);
2291   long proj_nr;
2292
2293   if (value_not_zero(b)) {
2294     /* DivMod(x, y) && y != 0 */
2295     proj_nr = get_Proj_proj(proj);
2296
2297     /* this node may float */
2298     set_irn_pinned(n, op_pin_state_floats);
2299
2300     if (proj_nr == pn_DivMod_X_except) {
2301       /* we found an exception handler, remove it */
2302       DBG_OPT_EXC_REM(proj);
2303       return new_Bad();
2304     }
2305     else if (proj_nr == pn_DivMod_M) {
2306       /* the memory Proj can be removed */
2307       ir_node *res = get_DivMod_mem(n);
2308       set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
2309
2310       return res;
2311     }
2312     else if (proj_nr == pn_DivMod_res_mod && get_DivMod_left(n) == b) {
2313       /* a % a = 0 if a != 0 */
2314       ir_mode *mode = get_irn_mode(proj);
2315       ir_node *res  = new_Const(mode, get_mode_null(mode));
2316
2317       DBG_OPT_CSTEVAL(n, res);
2318       return res;
2319     }
2320   }
2321   return proj;
2322 }
2323
2324 /**
2325  * Optimizes jump tables (CondIs or CondIu) by removing all impossible cases.
2326  */
2327 static ir_node *transform_node_Proj_Cond(ir_node *proj)
2328 {
2329   if (get_opt_unreachable_code()) {
2330     ir_node *n = get_Proj_pred(proj);
2331     ir_node *b = get_Cond_selector(n);
2332
2333     if (mode_is_int(get_irn_mode(b))) {
2334       tarval *tb = value_of(b);
2335
2336       if (tb != tarval_bad) {
2337         /* we have a constant switch */
2338         long num = get_Proj_proj(proj);
2339
2340         if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
2341           if (get_tarval_long(tb) == num) {
2342             /* Do NOT create a jump here, or we will have 2 control flow ops
2343              * in a block. This case is optimized away in optimize_cf(). */
2344             return proj;
2345           }
2346           else {
2347             /* this case will NEVER be taken, kill it */
2348             return new_Bad();
2349           }
2350         }
2351       }
2352     }
2353   }
2354   return proj;
2355 }
2356
2357 /**
2358  * Normalizes and optimizes Cmp nodes.
2359  */
2360 static ir_node *transform_node_Proj_Cmp(ir_node *proj)
2361 {
2362   if (get_opt_reassociation()) {
2363     ir_node *n     = get_Proj_pred(proj);
2364     ir_node *left  = get_Cmp_left(n);
2365     ir_node *right = get_Cmp_right(n);
2366     ir_node *c     = NULL;
2367     tarval *tv     = NULL;
2368     int changed    = 0;
2369     ir_mode *mode  = NULL;
2370     long proj_nr   = get_Proj_proj(proj);
2371
2372     /*
2373      * First step: normalize the compare op
2374      * by placing the constant on the right site
2375      * or moving the lower address node to the left.
2376      * We ignore the case that both are constants
2377      * this case should be optimized away.
2378      */
2379     if (get_irn_op(right) == op_Const)
2380       c = right;
2381     else if (get_irn_op(left) == op_Const) {
2382       c     = left;
2383       left  = right;
2384       right = c;
2385
2386       proj_nr = get_inversed_pnc(proj_nr);
2387       changed |= 1;
2388     }
2389     else if (left > right) {
2390       ir_node *t = left;
2391
2392       left  = right;
2393       right = t;
2394
2395       proj_nr = get_inversed_pnc(proj_nr);
2396       changed |= 1;
2397     }
2398
2399     /*
2400      * Second step: Try to reduce the magnitude
2401      * of a constant. This may help to generate better code
2402      * later and may help to normalize more compares.
2403      * Of course this is only possible for integer values.
2404      */
2405     if (c) {
2406       mode = get_irn_mode(c);
2407       tv = get_Const_tarval(c);
2408
2409       if (tv != tarval_bad) {
2410         /* the following optimization is possible on modes without Overflow
2411          * on Unary Minus or on == and !=:
2412          * -a CMP c  ==>  a swap(CMP) -c
2413          *
2414          * Beware: for two-complement Overflow may occur, so only == and != can
2415          * be optimized, see this:
2416          * -MININT < 0 =/=> MININT > 0 !!!
2417          */
2418         if (get_opt_constant_folding() && get_irn_op(left) == op_Minus &&
2419             (!mode_overflow_on_unary_Minus(mode) ||
2420              (mode_is_int(mode) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)))) {
2421           left = get_Minus_op(left);
2422           tv = tarval_sub(get_mode_null(mode), tv);
2423
2424           proj_nr = get_inversed_pnc(proj_nr);
2425           changed |= 2;
2426         }
2427
2428         /* for integer modes, we have more */
2429         if (mode_is_int(mode)) {
2430           /* Ne includes Unordered which is not possible on integers.
2431            * However, frontends often use this wrong, so fix it here */
2432           if (proj_nr & pn_Cmp_Uo) {
2433             proj_nr &= ~pn_Cmp_Uo;
2434             set_Proj_proj(proj, proj_nr);
2435           }
2436
2437           /* c > 0 : a < c  ==>  a <= (c-1)    a >= c  ==>  a > (c-1) */
2438           if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Ge) &&
2439               tarval_cmp(tv, get_mode_null(mode)) == pn_Cmp_Gt) {
2440             tv = tarval_sub(tv, get_mode_one(mode));
2441
2442             proj_nr ^= pn_Cmp_Eq;
2443             changed |= 2;
2444           }
2445           /* c < 0 : a > c  ==>  a >= (c+1)    a <= c  ==>  a < (c+1) */
2446           else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Le) &&
2447               tarval_cmp(tv, get_mode_null(mode)) == pn_Cmp_Lt) {
2448             tv = tarval_add(tv, get_mode_one(mode));
2449
2450             proj_nr ^= pn_Cmp_Eq;
2451             changed |= 2;
2452           }
2453
2454           /* the following reassociations work only for == and != */
2455           if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
2456
2457             /* a-b == 0  ==>  a == b,  a-b != 0  ==>  a != b */
2458             if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
2459               right = get_Sub_right(left);
2460               left  = get_Sub_left(left);
2461
2462               tv = value_of(right);
2463               changed = 1;
2464             }
2465
2466             if (tv != tarval_bad) {
2467               ir_op *op = get_irn_op(left);
2468
2469               /* a-c1 == c2  ==>  a == c2+c1,  a-c1 != c2  ==>  a != c2+c1 */
2470               if (op == op_Sub) {
2471                 ir_node *c1 = get_Sub_right(left);
2472                 tarval *tv2 = value_of(c1);
2473
2474                 if (tv2 != tarval_bad) {
2475                   tv2 = tarval_add(tv, value_of(c1));
2476
2477                   if (tv2 != tarval_bad) {
2478                     left    = get_Sub_left(left);
2479                     tv      = tv2;
2480                     changed |= 2;
2481                   }
2482                 }
2483               }
2484               /* a+c1 == c2  ==>  a == c2-c1,  a+c1 != c2  ==>  a != c2-c1 */
2485               else if (op == op_Add) {
2486                 ir_node *a_l = get_Add_left(left);
2487                 ir_node *a_r = get_Add_right(left);
2488                 ir_node *a;
2489                 tarval *tv2;
2490
2491                 if (get_irn_op(a_l) == op_Const) {
2492                   a = a_r;
2493                   tv2 = value_of(a_l);
2494                 }
2495                 else {
2496                   a = a_l;
2497                   tv2 = value_of(a_r);
2498                 }
2499
2500                 if (tv2 != tarval_bad) {
2501                   tv2 = tarval_sub(tv, tv2);
2502
2503                   if (tv2 != tarval_bad) {
2504                     left    = a;
2505                     tv      = tv2;
2506                     changed |= 2;
2507                   }
2508                 }
2509               }
2510               /* -a == c ==> a == -c, -a != c ==> a != -c */
2511               else if (op == op_Minus) {
2512                 tarval *tv2 = tarval_sub(get_mode_null(mode), tv);
2513
2514                 if (tv2 != tarval_bad) {
2515                   left    = get_Minus_op(left);
2516                   tv      = tv2;
2517                   changed |= 2;
2518                 }
2519               }
2520             }
2521           } /* == or != */
2522           /* the following reassociations work only for <= */
2523           else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2524             if (tv != tarval_bad) {
2525               ir_op *op = get_irn_op(left);
2526
2527               /* c >= 0 : Abs(a) <= c  ==>  (unsigned)(a + c) <= 2*c */
2528               if (op == op_Abs) {
2529               }
2530             }
2531           }
2532         } /* mode_is_int */
2533
2534         /*
2535          * optimization for AND:
2536          * Optimize:
2537          *   And(x, C) == C  ==>  And(x, C) != 0
2538          *   And(x, C) != C  ==>  And(X, C) == 0
2539          *
2540          * if C is a single Bit constant.
2541          */
2542         if ((proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) &&
2543             (get_irn_op(left) == op_And)) {
2544           if (is_single_bit_tarval(tv)) {
2545             /* check for Constant's match. We have check hare the tarvals,
2546                because our const might be changed */
2547             ir_node *la = get_And_left(left);
2548             ir_node *ra = get_And_right(left);
2549             if ((is_Const(la) && get_Const_tarval(la) == tv) ||
2550                 (is_Const(ra) && get_Const_tarval(ra) == tv)) {
2551               /* fine: do the transformation */
2552               tv = get_mode_null(get_tarval_mode(tv));
2553               proj_nr ^= pn_Cmp_Leg;
2554               changed |= 2;
2555             }
2556           }
2557         }
2558       } /* tarval != bad */
2559     }
2560
2561     if (changed) {
2562       ir_node *block = get_irn_n(n, -1); /* Beware of get_nodes_Block() */
2563
2564       if (changed & 2)      /* need a new Const */
2565         right = new_Const(mode, tv);
2566
2567       /* create a new compare */
2568       n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
2569             left, right);
2570
2571       set_Proj_pred(proj, n);
2572       set_Proj_proj(proj, proj_nr);
2573     }
2574   }
2575   return proj;
2576 }
2577
2578 /**
2579  * Does all optimizations on nodes that must be done on it's Proj's
2580  * because of creating new nodes.
2581  */
2582 static ir_node *transform_node_Proj(ir_node *proj)
2583 {
2584   ir_node *n = get_Proj_pred(proj);
2585
2586   switch (get_irn_opcode(n)) {
2587   case iro_Div:
2588     return transform_node_Proj_Div(proj);
2589
2590   case iro_Mod:
2591     return transform_node_Proj_Mod(proj);
2592
2593   case iro_DivMod:
2594     return transform_node_Proj_DivMod(proj);
2595
2596   case iro_Cond:
2597     return transform_node_Proj_Cond(proj);
2598
2599   case iro_Cmp:
2600     return transform_node_Proj_Cmp(proj);
2601
2602   case iro_Tuple:
2603     /* should not happen, but if it does will be optimized away */
2604     return equivalent_node_Proj(proj);
2605
2606   default:
2607     /* do nothing */
2608     return proj;
2609   }
2610 }
2611
2612 /**
2613  * returns the operands of a commutative bin-op, if one operand is
2614  * a const, it is returned as the second one.
2615  */
2616 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
2617 {
2618   ir_node *op_a = get_binop_left(binop);
2619   ir_node *op_b = get_binop_right(binop);
2620
2621   assert(is_op_commutative(get_irn_op(binop)));
2622
2623   if (get_irn_op(op_a) == op_Const) {
2624     *a = op_b;
2625     *c = op_a;
2626   }
2627   else {
2628     *a = op_a;
2629     *c = op_b;
2630   }
2631 }
2632
2633 /**
2634  * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
2635  * Such pattern may arise in bitfield stores.
2636  *
2637  * value  c4                  value      c4 & c2
2638  *    AND     c3                    AND           c1 | c3
2639  *        OR     c2      ===>               OR
2640  *           AND    c1
2641  *               OR
2642  */
2643 static ir_node *transform_node_Or_bf_store(ir_node *or)
2644 {
2645   ir_node *and, *c1;
2646   ir_node *or_l, *c2;
2647   ir_node *and_l, *c3;
2648   ir_node *value, *c4;
2649   ir_node *new_and, *new_const, *block;
2650   ir_mode *mode = get_irn_mode(or);
2651
2652   tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
2653
2654   get_comm_Binop_Ops(or, &and, &c1);
2655   if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
2656     return or;
2657
2658   get_comm_Binop_Ops(and, &or_l, &c2);
2659   if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
2660     return or;
2661
2662   get_comm_Binop_Ops(or_l, &and_l, &c3);
2663   if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
2664     return or;
2665
2666   get_comm_Binop_Ops(and_l, &value, &c4);
2667   if (get_irn_op(c4) != op_Const)
2668     return or;
2669
2670   /* ok, found the pattern, check for conditions */
2671   assert(mode == get_irn_mode(and));
2672   assert(mode == get_irn_mode(or_l));
2673   assert(mode == get_irn_mode(and_l));
2674
2675   tv1 = get_Const_tarval(c1);
2676   tv2 = get_Const_tarval(c2);
2677   tv3 = get_Const_tarval(c3);
2678   tv4 = get_Const_tarval(c4);
2679
2680   tv = tarval_or(tv4, tv2);
2681   if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
2682     /* have at least one 0 at the same bit position */
2683     return or;
2684   }
2685
2686   n_tv4 = tarval_not(tv4);
2687   if (tv3 != tarval_and(tv3, n_tv4)) {
2688     /* bit in the or_mask is outside the and_mask */
2689     return or;
2690   }
2691
2692   n_tv2 = tarval_not(tv2);
2693   if (tv1 != tarval_and(tv1, n_tv2)) {
2694     /* bit in the or_mask is outside the and_mask */
2695     return or;
2696   }
2697
2698   /* ok, all conditions met */
2699   block = get_irn_n(or, -1);
2700
2701   new_and = new_r_And(current_ir_graph, block,
2702       value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
2703
2704   new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
2705
2706   set_Or_left(or, new_and);
2707   set_Or_right(or, new_const);
2708
2709   /* check for more */
2710   return transform_node_Or_bf_store(or);
2711 }
2712
2713 /**
2714  * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
2715  */
2716 static ir_node *transform_node_Or_Rot(ir_node *or)
2717 {
2718   ir_mode *mode = get_irn_mode(or);
2719   ir_node *shl, *shr, *block;
2720   ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
2721   tarval *tv1, *tv2;
2722
2723   if (! mode_is_int(mode))
2724     return or;
2725
2726   shl = get_binop_left(or);
2727   shr = get_binop_right(or);
2728
2729   if (get_irn_op(shl) == op_Shr) {
2730     if (get_irn_op(shr) != op_Shl)
2731       return or;
2732
2733     irn = shl;
2734     shl = shr;
2735     shr = irn;
2736   }
2737   else if (get_irn_op(shl) != op_Shl)
2738     return or;
2739   else if (get_irn_op(shr) != op_Shr)
2740     return or;
2741
2742   x = get_Shl_left(shl);
2743   if (x != get_Shr_left(shr))
2744     return or;
2745
2746   c1 = get_Shl_right(shl);
2747   c2 = get_Shr_right(shr);
2748   if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
2749     tv1 = get_Const_tarval(c1);
2750     if (! tarval_is_long(tv1))
2751       return or;
2752
2753     tv2 = get_Const_tarval(c2);
2754     if (! tarval_is_long(tv2))
2755       return or;
2756
2757     if (get_tarval_long(tv1) + get_tarval_long(tv2)
2758         != get_mode_size_bits(mode))
2759       return or;
2760
2761     /* yet, condition met */
2762     block = get_irn_n(or, -1);
2763
2764     n = new_r_Rot(current_ir_graph, block, x, c1, mode);
2765
2766     DBG_OPT_ALGSIM1(or, shl, shr, n, FS_OPT_OR_SHFT_TO_ROT);
2767     return n;
2768   }
2769   else if (get_irn_op(c1) == op_Sub) {
2770     v   = c2;
2771     sub = c1;
2772
2773     if (get_Sub_right(sub) != v)
2774       return or;
2775
2776     c1 = get_Sub_left(sub);
2777     if (get_irn_op(c1) != op_Const)
2778       return or;
2779
2780     tv1 = get_Const_tarval(c1);
2781     if (! tarval_is_long(tv1))
2782       return or;
2783
2784     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2785       return or;
2786
2787     /* yet, condition met */
2788     block = get_nodes_block(or);
2789
2790     /* a Rot right is not supported, so use a rot left */
2791     n =  new_r_Rot(current_ir_graph, block, x, sub, mode);
2792
2793     DBG_OPT_ALGSIM0(or, n, FS_OPT_OR_SHFT_TO_ROT);
2794     return n;
2795   }
2796   else if (get_irn_op(c2) == op_Sub) {
2797     v   = c1;
2798     sub = c2;
2799
2800     c1 = get_Sub_left(sub);
2801     if (get_irn_op(c1) != op_Const)
2802       return or;
2803
2804     tv1 = get_Const_tarval(c1);
2805     if (! tarval_is_long(tv1))
2806       return or;
2807
2808     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2809       return or;
2810
2811     /* yet, condition met */
2812     block = get_irn_n(or, -1);
2813
2814     /* a Rot Left */
2815     n = new_r_Rot(current_ir_graph, block, x, v, mode);
2816
2817     DBG_OPT_ALGSIM0(or, n, FS_OPT_OR_SHFT_TO_ROT);
2818     return n;
2819   }
2820
2821   return or;
2822 }
2823
2824 /**
2825  * Optimize an Or
2826  */
2827 static ir_node *transform_node_Or(ir_node *or)
2828 {
2829   or = transform_node_Or_bf_store(or);
2830   or = transform_node_Or_Rot(or);
2831
2832   return or;
2833 }
2834
2835 /* forward */
2836 static ir_node *transform_node(ir_node *n);
2837
2838 /**
2839  * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl.
2840  *
2841  * Should be moved to reassociation?
2842  */
2843 static ir_node *transform_node_shift(ir_node *n)
2844 {
2845   ir_node *left, *right;
2846   tarval *tv1, *tv2, *res;
2847   ir_mode *mode;
2848   int modulo_shf, flag;
2849
2850   left = get_binop_left(n);
2851
2852   /* different operations */
2853   if (get_irn_op(left) != get_irn_op(n))
2854     return n;
2855
2856   right = get_binop_right(n);
2857   tv1 = value_of(right);
2858   if (tv1 == tarval_bad)
2859     return n;
2860
2861   tv2 = value_of(get_binop_right(left));
2862   if (tv2 == tarval_bad)
2863     return n;
2864
2865   res = tarval_add(tv1, tv2);
2866
2867   /* beware: a simple replacement works only, if res < modulo shift */
2868   mode = get_irn_mode(n);
2869
2870   flag = 0;
2871
2872   modulo_shf = get_mode_modulo_shift(mode);
2873   if (modulo_shf > 0) {
2874     tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
2875
2876     if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
2877       flag = 1;
2878   }
2879   else
2880     flag = 1;
2881
2882   if (flag) {
2883     /* ok, we can replace it */
2884     ir_node *in[2], *irn, *block = get_irn_n(n, -1);
2885
2886     in[0] = get_binop_left(left);
2887     in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
2888
2889     irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
2890
2891     DBG_OPT_ALGSIM0(n, irn, FS_OPT_REASSOC_SHIFT);
2892
2893     return transform_node(irn);
2894   }
2895   return n;
2896 }
2897
2898 #define transform_node_Shr  transform_node_shift
2899 #define transform_node_Shrs transform_node_shift
2900 #define transform_node_Shl  transform_node_shift
2901
2902 /**
2903  * Remove dead blocks and nodes in dead blocks
2904  * in keep alive list.  We do not generate a new End node.
2905  */
2906 static ir_node *transform_node_End(ir_node *n) {
2907   int i, n_keepalives = get_End_n_keepalives(n);
2908
2909   for (i = 0; i < n_keepalives; ++i) {
2910     ir_node *ka = get_End_keepalive(n, i);
2911     if (is_Block(ka)) {
2912       if (is_Block_dead(ka)) {
2913         set_End_keepalive(n, i, new_Bad());
2914       }
2915     }
2916     else if (is_irn_pinned_in_irg(ka) && is_Block_dead(get_nodes_block(ka)))
2917       set_End_keepalive(n, i, new_Bad());
2918   }
2919   return n;
2920 }
2921
2922 /**
2923  * Optimize a Mux into some simpler cases.
2924  */
2925 static ir_node *transform_node_Mux(ir_node *n)
2926 {
2927   ir_node *oldn = n, *sel = get_Mux_sel(n);
2928   ir_mode *mode = get_irn_mode(n);
2929
2930   if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(mode)) {
2931     ir_node *cmp = get_Proj_pred(sel);
2932     long proj_nr = get_Proj_proj(sel);
2933     ir_node *f   =  get_Mux_false(n);
2934     ir_node *t   = get_Mux_true(n);
2935
2936     if (get_irn_op(cmp) == op_Cmp && classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
2937       ir_node *block = get_irn_n(n, -1);
2938
2939       /*
2940        * Note: normalization puts the constant on the right site,
2941        * so we check only one case.
2942        *
2943        * Note further that these optimization work even for floating point
2944        * with NaN's because -NaN == NaN.
2945        * However, if +0 and -0 is handled differently, we cannot use the first one.
2946        */
2947       if (get_irn_op(f) == op_Minus &&
2948           get_Minus_op(f)   == t &&
2949           get_Cmp_left(cmp) == t) {
2950
2951         if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2952           /* Mux(a >=/> 0, -a, a)  ==>  Abs(a) */
2953           n = new_rd_Abs(get_irn_dbg_info(n),
2954                 current_ir_graph,
2955                 block,
2956                 t, mode);
2957           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
2958           return n;
2959         }
2960         else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2961           /* Mux(a <=/< 0, -a, a)  ==>  Minus(Abs(a)) */
2962           n = new_rd_Abs(get_irn_dbg_info(n),
2963                 current_ir_graph,
2964                 block,
2965                 t, mode);
2966           n = new_rd_Minus(get_irn_dbg_info(n),
2967                 current_ir_graph,
2968                 block,
2969                 n, mode);
2970
2971           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
2972           return n;
2973         }
2974       }
2975       else if (get_irn_op(t) == op_Minus &&
2976           get_Minus_op(t)   == f &&
2977           get_Cmp_left(cmp) == f) {
2978
2979         if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2980           /* Mux(a <=/< 0, a, -a)  ==>  Abs(a) */
2981           n = new_rd_Abs(get_irn_dbg_info(n),
2982                 current_ir_graph,
2983                 block,
2984                 f, mode);
2985           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
2986           return n;
2987         }
2988         else if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2989           /* Mux(a >=/> 0, a, -a)  ==>  Minus(Abs(a)) */
2990           n = new_rd_Abs(get_irn_dbg_info(n),
2991                 current_ir_graph,
2992                 block,
2993                 f, mode);
2994           n = new_rd_Minus(get_irn_dbg_info(n),
2995                 current_ir_graph,
2996                 block,
2997                 n, mode);
2998
2999           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
3000           return n;
3001         }
3002       }
3003
3004       if (mode_is_int(mode) && mode_is_signed(mode) &&
3005           get_mode_arithmetic(mode) == irma_twos_complement) {
3006         ir_node *x = get_Cmp_left(cmp);
3007
3008         /* the following optimization works only with signed integer two-complement mode */
3009
3010         if (mode == get_irn_mode(x)) {
3011           /*
3012            * FIXME: this restriction is two rigid, as it would still
3013            * work if mode(x) = Hs and mode == Is, but at least it removes
3014            * all wrong cases.
3015            */
3016           if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Le) &&
3017               classify_Const(t) == CNST_ALL_ONE &&
3018               classify_Const(f) == CNST_NULL) {
3019             /*
3020              * Mux(x:T </<= 0, 0, -1) -> Shrs(x, sizeof_bits(T) - 1)
3021              * Conditions:
3022              * T must be signed.
3023              */
3024             n = new_rd_Shrs(get_irn_dbg_info(n),
3025                   current_ir_graph, block, x,
3026                   new_r_Const_long(current_ir_graph, block, mode_Iu,
3027                     get_mode_size_bits(mode) - 1),
3028                   mode);
3029             DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_SHR);
3030             return n;
3031           }
3032           else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Ge) &&
3033                    classify_Const(t) == CNST_ONE &&
3034                    classify_Const(f) == CNST_NULL) {
3035             /*
3036              * Mux(x:T >/>= 0, 0, 1) -> Shr(-x, sizeof_bits(T) - 1)
3037              * Conditions:
3038              * T must be signed.
3039              */
3040             n = new_rd_Shr(get_irn_dbg_info(n),
3041                   current_ir_graph, block,
3042                   new_r_Minus(current_ir_graph, block, x, mode),
3043                   new_r_Const_long(current_ir_graph, block, mode_Iu,
3044                     get_mode_size_bits(mode) - 1),
3045                   mode);
3046             DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_SHR);
3047             return n;
3048           }
3049         }
3050       }
3051     }
3052   }
3053   return arch_transform_node_Mux(n);
3054 }
3055
3056 /**
3057  * Tries several [inplace] [optimizing] transformations and returns an
3058  * equivalent node.  The difference to equivalent_node() is that these
3059  * transformations _do_ generate new nodes, and thus the old node must
3060  * not be freed even if the equivalent node isn't the old one.
3061  */
3062 static ir_node *transform_node(ir_node *n)
3063 {
3064   if (n->op->ops.transform_node)
3065     n = n->op->ops.transform_node(n);
3066   return n;
3067 }
3068
3069 /**
3070  * sSets the default transform node operation for an ir_op_ops.
3071  *
3072  * @param code   the opcode for the default operation
3073  * @param ops    the operations initialized
3074  *
3075  * @return
3076  *    The operations.
3077  */
3078 static ir_op_ops *firm_set_default_transform_node(opcode code, ir_op_ops *ops)
3079 {
3080 #define CASE(a)                                 \
3081   case iro_##a:                                 \
3082     ops->transform_node  = transform_node_##a;   \
3083     break
3084
3085   switch (code) {
3086   CASE(Add);
3087   CASE(Sub);
3088   CASE(Mul);
3089   CASE(Div);
3090   CASE(Mod);
3091   CASE(DivMod);
3092   CASE(Abs);
3093   CASE(Cond);
3094   CASE(Eor);
3095   CASE(Not);
3096   CASE(Cast);
3097   CASE(Proj);
3098   CASE(Sel);
3099   CASE(Or);
3100   CASE(Shr);
3101   CASE(Shrs);
3102   CASE(Shl);
3103   CASE(End);
3104   CASE(Mux);
3105   default:
3106     /* leave NULL */;
3107   }
3108
3109   return ops;
3110 #undef CASE
3111 }
3112
3113
3114 /* **************** Common Subexpression Elimination **************** */
3115
3116 /** The size of the hash table used, should estimate the number of nodes
3117     in a graph. */
3118 #define N_IR_NODES 512
3119
3120 /** Compares the attributes of two Const nodes. */
3121 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
3122 {
3123   return (get_Const_tarval(a) != get_Const_tarval(b))
3124       || (get_Const_type(a) != get_Const_type(b));
3125 }
3126
3127 /** Compares the attributes of two Proj nodes. */
3128 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
3129 {
3130   return get_irn_proj_attr (a) != get_irn_proj_attr (b);
3131 }
3132
3133 /** Compares the attributes of two Filter nodes. */
3134 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
3135 {
3136   return get_Filter_proj(a) != get_Filter_proj(b);
3137 }
3138
3139 /** Compares the attributes of two Alloc nodes. */
3140 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
3141 {
3142   return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
3143       || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
3144 }
3145
3146 /** Compares the attributes of two Free nodes. */
3147 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
3148 {
3149   return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
3150       || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
3151 }
3152
3153 /** Compares the attributes of two SymConst nodes. */
3154 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
3155 {
3156   return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
3157       || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
3158       || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
3159 }
3160
3161 /** Compares the attributes of two Call nodes. */
3162 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
3163 {
3164   return (get_irn_call_attr(a) != get_irn_call_attr(b));
3165 }
3166
3167 /** Compares the attributes of two Sel nodes. */
3168 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
3169 {
3170   return (get_irn_sel_attr(a).ent->kind  != get_irn_sel_attr(b).ent->kind)
3171       || (get_irn_sel_attr(a).ent->name    != get_irn_sel_attr(b).ent->name)
3172       || (get_irn_sel_attr(a).ent->owner   != get_irn_sel_attr(b).ent->owner)
3173       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
3174       || (get_irn_sel_attr(a).ent->type    != get_irn_sel_attr(b).ent->type);
3175 }
3176
3177 /** Compares the attributes of two Phi nodes. */
3178 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
3179 {
3180   return get_irn_phi_attr (a) != get_irn_phi_attr (b);
3181 }
3182
3183 /** Compares the attributes of two Cast nodes. */
3184 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
3185 {
3186   return get_Cast_type(a) != get_Cast_type(b);
3187 }
3188
3189 /** Compares the attributes of two Load nodes. */
3190 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
3191 {
3192   if (get_Load_volatility(a) == volatility_is_volatile ||
3193       get_Load_volatility(b) == volatility_is_volatile)
3194     /* NEVER do CSE on volatile Loads */
3195     return 1;
3196
3197   return get_Load_mode(a) != get_Load_mode(b);
3198 }
3199
3200 /** Compares the attributes of two Store nodes. */
3201 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
3202 {
3203   /* NEVER do CSE on volatile Stores */
3204   return (get_Store_volatility(a) == volatility_is_volatile ||
3205           get_Store_volatility(b) == volatility_is_volatile);
3206 }
3207
3208 /** Compares the attributes of two Confirm nodes. */
3209 static int node_cmp_attr_Confirm(ir_node *a, ir_node *b)
3210 {
3211   return (get_Confirm_cmp(a) != get_Confirm_cmp(b));
3212 }
3213
3214 /**
3215  * Set the default node attribute compare operation for an ir_op_ops.
3216  *
3217  * @param code   the opcode for the default operation
3218  * @param ops    the operations initialized
3219  *
3220  * @return
3221  *    The operations.
3222  */
3223 static ir_op_ops *firm_set_default_node_cmp_attr(opcode code, ir_op_ops *ops)
3224 {
3225 #define CASE(a)                              \
3226   case iro_##a:                              \
3227     ops->node_cmp_attr  = node_cmp_attr_##a; \
3228     break
3229
3230   switch (code) {
3231   CASE(Const);
3232   CASE(Proj);
3233   CASE(Filter);
3234   CASE(Alloc);
3235   CASE(Free);
3236   CASE(SymConst);
3237   CASE(Call);
3238   CASE(Sel);
3239   CASE(Phi);
3240   CASE(Cast);
3241   CASE(Load);
3242   CASE(Store);
3243   CASE(Confirm);
3244   default:
3245     /* leave NULL */;
3246   }
3247
3248   return ops;
3249 #undef CASE
3250 }
3251
3252 /*
3253  * Compare function for two nodes in the hash table. Gets two
3254  * nodes as parameters.  Returns 0 if the nodes are a cse.
3255  */
3256 int identities_cmp(const void *elt, const void *key)
3257 {
3258   ir_node *a, *b;
3259   int i, irn_arity_a;
3260
3261   a = (void *)elt;
3262   b = (void *)key;
3263
3264   if (a == b) return 0;
3265
3266   if ((get_irn_op(a) != get_irn_op(b)) ||
3267       (get_irn_mode(a) != get_irn_mode(b))) return 1;
3268
3269   /* compare if a's in and b's in are of equal length */
3270   irn_arity_a = get_irn_intra_arity (a);
3271   if (irn_arity_a != get_irn_intra_arity(b))
3272     return 1;
3273
3274   /* for block-local cse and op_pin_state_pinned nodes: */
3275   if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
3276     if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
3277       return 1;
3278   }
3279
3280   /* compare a->in[0..ins] with b->in[0..ins] */
3281   for (i = 0; i < irn_arity_a; i++)
3282     if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
3283       return 1;
3284
3285   /*
3286    * here, we already now that the nodes are identical except their
3287    * attributes
3288    */
3289   if (a->op->ops.node_cmp_attr)
3290     return a->op->ops.node_cmp_attr(a, b);
3291
3292   return 0;
3293 }
3294
3295 /*
3296  * Calculate a hash value of a node.
3297  */
3298 unsigned
3299 ir_node_hash (ir_node *node)
3300 {
3301   unsigned h;
3302   int i, irn_arity;
3303
3304   if (node->op == op_Const) {
3305     /* special value for const, as they only differ in their tarval. */
3306     h = HASH_PTR(node->attr.con.tv);
3307     h = 9*h + HASH_PTR(get_irn_mode(node));
3308   } else if (node->op == op_SymConst) {
3309     /* special value for const, as they only differ in their symbol. */
3310     h = HASH_PTR(node->attr.i.sym.type_p);
3311     h = 9*h + HASH_PTR(get_irn_mode(node));
3312   } else {
3313
3314     /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
3315     h = irn_arity = get_irn_intra_arity(node);
3316
3317     /* consider all in nodes... except the block if not a control flow. */
3318     for (i =  is_cfop(node) ? -1 : 0;  i < irn_arity;  i++) {
3319       h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
3320     }
3321
3322     /* ...mode,... */
3323     h = 9*h + HASH_PTR(get_irn_mode(node));
3324     /* ...and code */
3325     h = 9*h + HASH_PTR(get_irn_op(node));
3326   }
3327
3328   return h;
3329 }
3330
3331 pset *
3332 new_identities(void) {
3333   return new_pset(identities_cmp, N_IR_NODES);
3334 }
3335
3336 void
3337 del_identities(pset *value_table) {
3338   del_pset(value_table);
3339 }
3340
3341 /**
3342  * Return the canonical node computing the same value as n.
3343  * Looks up the node in a hash table.
3344  *
3345  * For Const nodes this is performed in the constructor, too.  Const
3346  * nodes are extremely time critical because of their frequent use in
3347  * constant string arrays.
3348  */
3349 static INLINE ir_node *
3350 identify (pset *value_table, ir_node *n)
3351 {
3352   ir_node *o = NULL;
3353
3354   if (!value_table) return n;
3355
3356   if (get_opt_reassociation()) {
3357     if (is_op_commutative(get_irn_op(n))) {
3358       ir_node *l = get_binop_left(n);
3359       ir_node *r = get_binop_right(n);
3360
3361       /* for commutative operators perform  a OP b == b OP a */
3362       if (l > r) {
3363         set_binop_left(n, r);
3364         set_binop_right(n, l);
3365       }
3366     }
3367   }
3368
3369   o = pset_find (value_table, n, ir_node_hash (n));
3370   if (!o) return n;
3371
3372   DBG_OPT_CSE(n, o);
3373
3374   return o;
3375 }
3376
3377 /**
3378  * During construction we set the op_pin_state_pinned flag in the graph right when the
3379  * optimization is performed.  The flag turning on procedure global cse could
3380  * be changed between two allocations.  This way we are safe.
3381  */
3382 static INLINE ir_node *
3383 identify_cons (pset *value_table, ir_node *n) {
3384   ir_node *old = n;
3385
3386   n = identify(value_table, n);
3387   if (get_irn_n(old, -1) != get_irn_n(n, -1))
3388     set_irg_pinned(current_ir_graph, op_pin_state_floats);
3389   return n;
3390 }
3391
3392 /*
3393  * Return the canonical node computing the same value as n.
3394  * Looks up the node in a hash table, enters it in the table
3395  * if it isn't there yet.
3396  */
3397 ir_node *
3398 identify_remember (pset *value_table, ir_node *n)
3399 {
3400   ir_node *o = NULL;
3401
3402   if (!value_table) return n;
3403
3404   if (get_opt_reassociation()) {
3405     if (is_op_commutative(get_irn_op(n))) {
3406       ir_node *l = get_binop_left(n);
3407       ir_node *r = get_binop_right(n);
3408
3409       /* for commutative operators perform  a OP b == b OP a */
3410       if (l > r) {
3411         set_binop_left(n, r);
3412         set_binop_right(n, l);
3413       }
3414     }
3415   }
3416
3417   /* lookup or insert in hash table with given hash key. */
3418   o = pset_insert (value_table, n, ir_node_hash (n));
3419
3420   if (o != n) {
3421     DBG_OPT_CSE(n, o);
3422   }
3423
3424   return o;
3425 }
3426
3427 void
3428 add_identities (pset *value_table, ir_node *node) {
3429   if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
3430     identify_remember (value_table, node);
3431 }
3432
3433 /**
3434  * garbage in, garbage out. If a node has a dead input, i.e., the
3435  * Bad node is input to the node, return the Bad node.
3436  */
3437 static INLINE ir_node *
3438 gigo (ir_node *node)
3439 {
3440   int i, irn_arity;
3441   ir_op *op = get_irn_op(node);
3442
3443   /* remove garbage blocks by looking at control flow that leaves the block
3444      and replacing the control flow by Bad. */
3445   if (get_irn_mode(node) == mode_X) {
3446     ir_node *block = get_nodes_block(skip_Proj(node));
3447
3448     /* Don't optimize nodes in immature blocks. */
3449     if (!get_Block_matured(block)) return node;
3450      /* Don't optimize End, may have Bads. */
3451     if (op == op_End) return node;
3452
3453     if (is_Block(block)) {
3454       irn_arity = get_irn_arity(block);
3455       for (i = 0; i < irn_arity; i++) {
3456         if (!is_Bad(get_irn_n(block, i)))
3457           break;
3458       }
3459       if (i == irn_arity) return new_Bad();
3460     }
3461   }
3462
3463   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
3464      blocks predecessors is dead. */
3465   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
3466     irn_arity = get_irn_arity(node);
3467
3468     /*
3469      * Beware: we can only read the block of a non-floating node.
3470      */
3471     if (is_irn_pinned_in_irg(node) &&
3472         is_Block_dead(get_nodes_block(node)))
3473       return new_Bad();
3474
3475     for (i = 0; i < irn_arity; i++) {
3476       ir_node *pred = get_irn_n(node, i);
3477
3478       if (is_Bad(pred))
3479         return new_Bad();
3480       if (is_Unknown(pred) && mode_is_data(get_irn_mode(node)))
3481         return new_Unknown(get_irn_mode(node));
3482     }
3483   }
3484 #if 0
3485   /* With this code we violate the agreement that local_optimize
3486      only leaves Bads in Block, Phi and Tuple nodes. */
3487   /* If Block has only Bads as predecessors it's garbage. */
3488   /* If Phi has only Bads as predecessors it's garbage. */
3489   if ((op == op_Block && get_Block_matured(node)) || op == op_Phi)  {
3490     irn_arity = get_irn_arity(node);
3491     for (i = 0; i < irn_arity; i++) {
3492       if (!is_Bad(get_irn_n(node, i))) break;
3493     }
3494     if (i == irn_arity) node = new_Bad();
3495   }
3496 #endif
3497   return node;
3498 }
3499
3500
3501 /**
3502  * These optimizations deallocate nodes from the obstack.
3503  * It can only be called if it is guaranteed that no other nodes
3504  * reference this one, i.e., right after construction of a node.
3505  *
3506  * current_ir_graph must be set to the graph of the node!
3507  */
3508 ir_node *
3509 optimize_node(ir_node *n)
3510 {
3511   tarval *tv;
3512   ir_node *oldn = n;
3513   opcode iro = get_irn_opcode(n);
3514
3515   /* Always optimize Phi nodes: part of the construction. */
3516   if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
3517
3518   /* constant expression evaluation / constant folding */
3519   if (get_opt_constant_folding()) {
3520     /* neither constants nor Tuple values can be evaluated */
3521     if (iro != iro_Const && (get_irn_mode(n) != mode_T)) {
3522       /* try to evaluate */
3523       tv = computed_value(n);
3524       if (tv != tarval_bad) {
3525         ir_node *nw;
3526         ir_type *old_tp = get_irn_type(n);
3527         int i, arity = get_irn_arity(n);
3528         int node_size;
3529
3530         /*
3531          * Try to recover the type of the new expression.
3532          */
3533         for (i = 0; i < arity && !old_tp; ++i)
3534           old_tp = get_irn_type(get_irn_n(n, i));
3535
3536         /*
3537          * we MUST copy the node here temporary, because it's still needed
3538          * for DBG_OPT_CSTEVAL
3539          */
3540         node_size = offsetof(ir_node, attr) +  n->op->attr_size;
3541         oldn = alloca(node_size);
3542
3543         memcpy(oldn, n, node_size);
3544         CLONE_ARR_A(ir_node *, oldn->in, n->in);
3545
3546         /* ARG, copy the in array, we need it for statistics */
3547         memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
3548
3549         /* note the inplace edges module */
3550         edges_node_deleted(n, current_ir_graph);
3551
3552         /* evaluation was successful -- replace the node. */
3553         obstack_free(current_ir_graph->obst, n);
3554         nw = new_Const(get_tarval_mode (tv), tv);
3555
3556         if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
3557           set_Const_type(nw, old_tp);
3558         DBG_OPT_CSTEVAL(oldn, nw);
3559         return nw;
3560       }
3561     }
3562   }
3563
3564   /* remove unnecessary nodes */
3565   if (get_opt_constant_folding() ||
3566     (iro == iro_Phi)  ||   /* always optimize these nodes. */
3567     (iro == iro_Id)   ||
3568     (iro == iro_Proj) ||
3569     (iro == iro_Block)  )  /* Flags tested local. */
3570     n = equivalent_node (n);
3571
3572   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
3573
3574   /* Common Subexpression Elimination.
3575    *
3576    * Checks whether n is already available.
3577    * The block input is used to distinguish different subexpressions. Right
3578    * now all nodes are op_pin_state_pinned to blocks, i.e., the CSE only finds common
3579    * subexpressions within a block.
3580    */
3581   if (get_opt_cse())
3582     n = identify_cons (current_ir_graph->value_table, n);
3583
3584   if (n != oldn) {
3585     edges_node_deleted(oldn, current_ir_graph);
3586
3587     /* We found an existing, better node, so we can deallocate the old node. */
3588     obstack_free (current_ir_graph->obst, oldn);
3589
3590     return n;
3591   }
3592
3593   /* Some more constant expression evaluation that does not allow to
3594      free the node. */
3595   iro = get_irn_opcode(n);
3596   if (get_opt_constant_folding() ||
3597     (iro == iro_Cond) ||
3598     (iro == iro_Proj) ||
3599     (iro == iro_Sel))     /* Flags tested local. */
3600     n = transform_node (n);
3601
3602   /* Remove nodes with dead (Bad) input.
3603      Run always for transformation induced Bads. */
3604   n = gigo (n);
3605
3606   /* Now we have a legal, useful node. Enter it in hash table for CSE */
3607   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
3608     n = identify_remember (current_ir_graph->value_table, n);
3609   }
3610
3611   return n;
3612 }
3613
3614
3615 /**
3616  * These optimizations never deallocate nodes (in place).  This can cause dead
3617  * nodes lying on the obstack.  Remove these by a dead node elimination,
3618  * i.e., a copying garbage collection.
3619  */
3620 ir_node *
3621 optimize_in_place_2 (ir_node *n)
3622 {
3623   tarval *tv;
3624   ir_node *oldn = n;
3625   opcode iro = get_irn_opcode(n);
3626
3627   if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
3628
3629   /* constant expression evaluation / constant folding */
3630   if (get_opt_constant_folding()) {
3631     /* neither constants nor Tuple values can be evaluated */
3632     if (iro != iro_Const && get_irn_mode(n) != mode_T) {
3633       /* try to evaluate */
3634       tv = computed_value(n);
3635       if (tv != tarval_bad) {
3636         /* evaluation was successful -- replace the node. */
3637         ir_type *old_tp = get_irn_type(n);
3638         int i, arity = get_irn_arity(n);
3639
3640         /*
3641          * Try to recover the type of the new expression.
3642          */
3643         for (i = 0; i < arity && !old_tp; ++i)
3644           old_tp = get_irn_type(get_irn_n(n, i));
3645
3646         n = new_Const(get_tarval_mode(tv), tv);
3647
3648         if (old_tp && get_type_mode(old_tp) == get_tarval_mode(tv))
3649           set_Const_type(n, old_tp);
3650
3651         DBG_OPT_CSTEVAL(oldn, n);
3652         return n;
3653       }
3654     }
3655   }
3656
3657   /* remove unnecessary nodes */
3658   if (get_opt_constant_folding() ||
3659       (iro == iro_Phi)  ||   /* always optimize these nodes. */
3660       (iro == iro_Id)   ||   /* ... */
3661       (iro == iro_Proj) ||   /* ... */
3662       (iro == iro_Block)  )  /* Flags tested local. */
3663     n = equivalent_node(n);
3664
3665   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
3666
3667   /** common subexpression elimination **/
3668   /* Checks whether n is already available. */
3669   /* The block input is used to distinguish different subexpressions.  Right
3670      now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
3671      subexpressions within a block. */
3672   if (get_opt_cse()) {
3673     n = identify(current_ir_graph->value_table, n);
3674   }
3675
3676   /* Some more constant expression evaluation. */
3677   iro = get_irn_opcode(n);
3678   if (get_opt_constant_folding() ||
3679       (iro == iro_Cond) ||
3680       (iro == iro_Proj) ||
3681       (iro == iro_Sel))     /* Flags tested local. */
3682     n = transform_node(n);
3683
3684   /* Remove nodes with dead (Bad) input.
3685      Run always for transformation induced Bads.  */
3686   n = gigo(n);
3687
3688   /* Now we can verify the node, as it has no dead inputs any more. */
3689   irn_vrfy(n);
3690
3691   /* Now we have a legal, useful node. Enter it in hash table for cse.
3692      Blocks should be unique anyways.  (Except the successor of start:
3693      is cse with the start block!) */
3694   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
3695     n = identify_remember(current_ir_graph->value_table, n);
3696
3697   return n;
3698 }
3699
3700 /**
3701  * Wrapper for external use, set proper status bits after optimization.
3702  */
3703 ir_node *
3704 optimize_in_place (ir_node *n)
3705 {
3706   /* Handle graph state */
3707   assert(get_irg_phase_state(current_ir_graph) != phase_building);
3708
3709   if (get_opt_global_cse())
3710     set_irg_pinned(current_ir_graph, op_pin_state_floats);
3711   if (get_irg_outs_state(current_ir_graph) == outs_consistent)
3712     set_irg_outs_inconsistent(current_ir_graph);
3713
3714   /* FIXME: Maybe we could also test whether optimizing the node can
3715      change the control graph. */
3716   set_irg_doms_inconsistent(current_ir_graph);
3717   return optimize_in_place_2 (n);
3718 }
3719
3720 /*
3721  * Sets the default operation for an ir_ops.
3722  */
3723 ir_op_ops *firm_set_default_operations(opcode code, ir_op_ops *ops)
3724 {
3725   ops = firm_set_default_computed_value(code, ops);
3726   ops = firm_set_default_equivalent_node(code, ops);
3727   ops = firm_set_default_transform_node(code, ops);
3728   ops = firm_set_default_node_cmp_attr(code, ops);
3729   ops = firm_set_default_get_type(code, ops);
3730   ops = firm_set_default_get_type_attr(code, ops);
3731   ops = firm_set_default_get_entity_attr(code, ops);
3732
3733   return ops;
3734 }