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