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