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   if (mode_is_num(mode) && (classify_Const(a) == CNST_NULL)) {
2043     n = new_rd_Minus(
2044           get_irn_dbg_info(n),
2045           current_ir_graph,
2046           get_irn_n(n, -1),
2047           b,
2048           mode);
2049     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_0_A);
2050   }
2051   /* do NOT execute this code if reassociation is enabled, it does the inverse! */
2052   else if (get_opt_reassociation() && get_irn_op(a) == op_Mul) {
2053     ir_node *ma = get_Mul_left(a);
2054     ir_node *mb = get_Mul_right(a);
2055
2056     if (ma == b) {
2057       ir_node *blk = get_irn_n(n, -1);
2058       n = new_rd_Mul(
2059         get_irn_dbg_info(n),
2060         current_ir_graph, blk,
2061         ma,
2062         new_rd_Sub(
2063           get_irn_dbg_info(n),
2064           current_ir_graph, blk,
2065           mb,
2066           new_r_Const_long(current_ir_graph, blk, mode, 1),
2067           mode),
2068         mode);
2069       DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
2070     }
2071     else if (mb == b) {
2072       ir_node *blk = get_irn_n(n, -1);
2073       n = new_rd_Mul(
2074         get_irn_dbg_info(n),
2075         current_ir_graph, blk,
2076         mb,
2077         new_rd_Sub(
2078           get_irn_dbg_info(n),
2079           current_ir_graph, blk,
2080           ma,
2081           new_r_Const_long(current_ir_graph, blk, mode, 1),
2082           mode),
2083         mode);
2084       DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
2085     }
2086   }
2087   else if (get_irn_op(a) == op_Sub) {
2088     ir_node *x   = get_Sub_left(a);
2089     ir_node *y   = get_Sub_right(a);
2090     ir_node *blk = get_irn_n(n, -1);
2091     ir_mode *m_b = get_irn_mode(b);
2092     ir_mode *m_y = get_irn_mode(y);
2093     ir_node *add;
2094
2095     /* Determine the right mode for the Add. */
2096     if (m_b == m_y)
2097       mode = m_b;
2098     else if (mode_is_reference(m_b))
2099       mode = m_b;
2100     else if (mode_is_reference(m_y))
2101       mode = m_y;
2102     else {
2103       /*
2104        * Both modes are different but none is reference,
2105        * happens for instance in SubP(SubP(P, Iu), Is).
2106        * We have two possibilities here: Cast or ignore.
2107        * Currently we ignore this case.
2108        */
2109       return n;
2110     }
2111
2112     add = new_r_Add(current_ir_graph, blk, y, b, mode);
2113
2114     set_Sub_left(n, x);
2115     set_Sub_right(n, add);
2116     DBG_OPT_ALGSIM0(n, n, FS_OPT_SUB_SUB_X_Y_Z);
2117   }
2118
2119   return n;
2120 }  /* transform_node_Sub */
2121
2122 /**
2123  * Transform Mul(a,-1) into -a.
2124  * Do constant evaluation of Phi nodes.
2125  * Do architecture dependent optimizations on Mul nodes
2126  */
2127 static ir_node *transform_node_Mul(ir_node *n) {
2128   ir_node *c, *oldn = n;
2129   ir_node *a = get_Mul_left(n);
2130   ir_node *b = get_Mul_right(n);
2131   ir_mode *mode;
2132
2133   HANDLE_BINOP_PHI(tarval_mul, a,b,c);
2134
2135   mode = get_irn_mode(n);
2136   if (mode_is_signed(mode)) {
2137     ir_node *r = NULL;
2138
2139     if (value_of(a) == get_mode_minus_one(mode))
2140       r = b;
2141     else if (value_of(b) == get_mode_minus_one(mode))
2142       r = a;
2143     if (r) {
2144       n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1), r, mode);
2145       DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS_1);
2146       return n;
2147     }
2148   }
2149   return arch_dep_replace_mul_with_shifts(n);
2150 }  /* transform_node_Mul */
2151
2152 /**
2153  * Transform a Div Node.
2154  */
2155 static ir_node *transform_node_Div(ir_node *n)
2156 {
2157   tarval *tv = value_of(n);
2158   ir_node *value = n;
2159
2160   /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
2161
2162   if (tv != tarval_bad) {
2163     value = new_Const(get_tarval_mode(tv), tv);
2164
2165     DBG_OPT_CSTEVAL(n, value);
2166   }
2167   else /* Try architecture dependent optimization */
2168     value = arch_dep_replace_div_by_const(n);
2169
2170   if (value != n) {
2171     /* Turn Div into a tuple (mem, bad, value) */
2172     ir_node *mem = get_Div_mem(n);
2173
2174     turn_into_tuple(n, pn_Div_max);
2175     set_Tuple_pred(n, pn_Div_M, mem);
2176     set_Tuple_pred(n, pn_Div_X_except, new_Bad());
2177     set_Tuple_pred(n, pn_Div_res, value);
2178   }
2179   return n;
2180 }  /* transform_node_Div */
2181
2182 /**
2183  * Transform a Mod node.
2184  */
2185 static ir_node *transform_node_Mod(ir_node *n)
2186 {
2187   tarval *tv = value_of(n);
2188   ir_node *value = n;
2189
2190   /* BEWARE: it is NOT possible to optimize a%a to 0, as this may cause a exception */
2191
2192   if (tv != tarval_bad) {
2193     value = new_Const(get_tarval_mode(tv), tv);
2194
2195     DBG_OPT_CSTEVAL(n, value);
2196   }
2197   else /* Try architecture dependent optimization */
2198     value = arch_dep_replace_mod_by_const(n);
2199
2200   if (value != n) {
2201     /* Turn Mod into a tuple (mem, bad, value) */
2202     ir_node *mem = get_Mod_mem(n);
2203
2204     turn_into_tuple(n, pn_Mod_max);
2205     set_Tuple_pred(n, pn_Mod_M, mem);
2206     set_Tuple_pred(n, pn_Mod_X_except, new_Bad());
2207     set_Tuple_pred(n, pn_Mod_res, value);
2208   }
2209   return n;
2210 }  /* transform_node_Mod */
2211
2212 /**
2213  * Transform a DivMod node.
2214  */
2215 static ir_node *transform_node_DivMod(ir_node *n)
2216 {
2217   int evaluated = 0;
2218
2219   ir_node *a = get_DivMod_left(n);
2220   ir_node *b = get_DivMod_right(n);
2221   ir_mode *mode = get_irn_mode(a);
2222   tarval *ta = value_of(a);
2223   tarval *tb = value_of(b);
2224
2225   if (!(mode_is_int(mode) && mode_is_int(get_irn_mode(b))))
2226     return n;
2227
2228   /* BEWARE: it is NOT possible to optimize a/a to 1, as this may cause a exception */
2229
2230   if (tb != tarval_bad) {
2231     if (tb == get_mode_one(get_tarval_mode(tb))) {
2232       b = new_Const (mode, get_mode_null(mode));
2233       evaluated = 1;
2234
2235       DBG_OPT_CSTEVAL(n, b);
2236     }
2237     else if (ta != tarval_bad) {
2238       tarval *resa, *resb;
2239       resa = tarval_div (ta, tb);
2240       if (resa == tarval_bad) return n; /* Causes exception!!! Model by replacing through
2241                                         Jmp for X result!? */
2242       resb = tarval_mod (ta, tb);
2243       if (resb == tarval_bad) return n; /* Causes exception! */
2244       a = new_Const (mode, resa);
2245       b = new_Const (mode, resb);
2246       evaluated = 1;
2247
2248       DBG_OPT_CSTEVAL(n, a);
2249       DBG_OPT_CSTEVAL(n, b);
2250     }
2251     else { /* Try architecture dependent optimization */
2252       arch_dep_replace_divmod_by_const(&a, &b, n);
2253       evaluated = a != NULL;
2254     }
2255   } else if (ta == get_mode_null(mode)) {
2256     /* 0 / non-Const = 0 */
2257     b = a;
2258     evaluated = 1;
2259   }
2260
2261   if (evaluated) { /* replace by tuple */
2262     ir_node *mem = get_DivMod_mem(n);
2263     turn_into_tuple(n, pn_DivMod_max);
2264     set_Tuple_pred(n, pn_DivMod_M,        mem);
2265     set_Tuple_pred(n, pn_DivMod_X_except, new_Bad());  /* no exception */
2266     set_Tuple_pred(n, pn_DivMod_res_div,  a);
2267     set_Tuple_pred(n, pn_DivMod_res_mod,  b);
2268   }
2269
2270   return n;
2271 }  /* transform_node_DivMod */
2272
2273 /**
2274  * Optimize Abs(x) into  x if x is Confirmed >= 0
2275  * Optimize Abs(x) into -x if x is Confirmed <= 0
2276  */
2277 static ir_node *transform_node_Abs(ir_node *n)
2278 {
2279   ir_node        *oldn = n;
2280   ir_node        *a = get_Abs_op(n);
2281   value_classify_sign sign = classify_value_sign(a);
2282
2283   if (sign == value_classified_negative) {
2284     ir_mode *mode = get_irn_mode(n);
2285
2286     /*
2287      * We can replace the Abs by -x here.
2288      * We even could add a new Confirm here.
2289      *
2290      * Note that -x would create a new node, so we could
2291      * not run it in the equivalent_node() context.
2292      */
2293     n = new_rd_Minus(get_irn_dbg_info(n), current_ir_graph,
2294                      get_irn_n(n, -1), a, mode);
2295
2296     DBG_OPT_CONFIRM(oldn, n);
2297   }
2298   else if (sign == value_classified_positive) {
2299     /* n is positive, Abs is not needed */
2300     n = a;
2301
2302     DBG_OPT_CONFIRM(oldn, n);
2303   }
2304
2305   return n;
2306 }  /* transform_node_Abs */
2307
2308 /**
2309  * Transform a Cond node.
2310  */
2311 static ir_node *transform_node_Cond(ir_node *n)
2312 {
2313   /* Replace the Cond by a Jmp if it branches on a constant
2314      condition. */
2315   ir_node *jmp;
2316   ir_node *a = get_Cond_selector(n);
2317   tarval *ta = value_of(a);
2318
2319   /* we need block info which is not available in floating irgs */
2320   if (get_irg_pinned(current_ir_graph) == op_pin_state_floats)
2321      return n;
2322
2323   if ((ta != tarval_bad) &&
2324       (get_irn_mode(a) == mode_b) &&
2325       (get_opt_unreachable_code())) {
2326     /* It's a boolean Cond, branching on a boolean constant.
2327                Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
2328     jmp = new_r_Jmp(current_ir_graph, get_nodes_block(n));
2329     turn_into_tuple(n, pn_Cond_max);
2330     if (ta == tarval_b_true) {
2331       set_Tuple_pred(n, pn_Cond_false, new_Bad());
2332       set_Tuple_pred(n, pn_Cond_true, jmp);
2333     } else {
2334       set_Tuple_pred(n, pn_Cond_false, jmp);
2335       set_Tuple_pred(n, pn_Cond_true, new_Bad());
2336     }
2337     /* We might generate an endless loop, so keep it alive. */
2338     add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_block(n));
2339   }
2340   return n;
2341 }  /* transform_node_Cond */
2342
2343 /**
2344  * Transform an And.
2345  */
2346 static ir_node *transform_node_And(ir_node *n)
2347 {
2348   ir_node *c, *oldn = n;
2349   ir_node *a = get_And_left(n);
2350   ir_node *b = get_And_right(n);
2351
2352   HANDLE_BINOP_PHI(tarval_and, a,b,c);
2353   return n;
2354 }  /* transform_node_And */
2355
2356 /**
2357  * Transform an Eor.
2358  */
2359 static ir_node *transform_node_Eor(ir_node *n)
2360 {
2361   ir_node *c, *oldn = n;
2362   ir_node *a = get_Eor_left(n);
2363   ir_node *b = get_Eor_right(n);
2364   ir_mode *mode = get_irn_mode(n);
2365
2366   HANDLE_BINOP_PHI(tarval_eor, a,b,c);
2367
2368   if (a == b) {
2369     /* a ^ a = 0 */
2370     n = new_rd_Const(get_irn_dbg_info(n), current_ir_graph, get_irn_n(n, -1),
2371                      mode, get_mode_null(mode));
2372     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_A_A);
2373   }
2374   else if ((mode == mode_b)
2375       && (get_irn_op(a) == op_Proj)
2376       && (get_irn_mode(a) == mode_b)
2377       && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)
2378       && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
2379     /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
2380     n = new_r_Proj(current_ir_graph, get_irn_n(n, -1), get_Proj_pred(a),
2381                    mode_b, get_negated_pnc(get_Proj_proj(a), mode));
2382
2383     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT_BOOL);
2384   }
2385   else if ((mode == mode_b)
2386         && (classify_tarval (value_of(b)) == TV_CLASSIFY_ONE)) {
2387     /* The Eor is a Not. Replace it by a Not. */
2388     /*   ????!!!Extend to bitfield 1111111. */
2389     n = new_r_Not(current_ir_graph, get_irn_n(n, -1), a, mode_b);
2390
2391     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
2392   }
2393
2394   return n;
2395 }  /* transform_node_Eor */
2396
2397 /**
2398  * Transform a Not.
2399  */
2400 static ir_node *transform_node_Not(ir_node *n)
2401 {
2402   ir_node *c, *oldn = n;
2403   ir_node *a = get_Not_op(n);
2404
2405   HANDLE_UNOP_PHI(tarval_not,a,c);
2406
2407   /* check for a boolean Not */
2408   if (   (get_irn_mode(n) == mode_b)
2409       && (get_irn_op(a) == op_Proj)
2410       && (get_irn_mode(a) == mode_b)
2411       && (get_irn_op(get_Proj_pred(a)) == op_Cmp)) {
2412     /* We negate a Cmp. The Cmp has the negated result anyways! */
2413     n = new_r_Proj(current_ir_graph, get_irn_n(n, -1), get_Proj_pred(a),
2414                    mode_b, get_negated_pnc(get_Proj_proj(a), mode_b));
2415     DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_CMP);
2416   }
2417   return n;
2418 }  /* transform_node_Not */
2419
2420 /**
2421  * Transform a Minus.
2422  */
2423 static ir_node *transform_node_Minus(ir_node *n)
2424 {
2425   ir_node *c, *oldn = n;
2426   ir_node *a = get_Minus_op(n);
2427
2428   HANDLE_UNOP_PHI(tarval_neg,a,c);
2429   return n;
2430 }  /* transform_node_Minus */
2431
2432 /**
2433  * Transform a Cast_type(Const) into a new Const_type
2434  */
2435 static ir_node *transform_node_Cast(ir_node *n) {
2436   ir_node *oldn = n;
2437   ir_node *pred = get_Cast_op(n);
2438   ir_type *tp = get_irn_type(n);
2439
2440   if (get_irn_op(pred) == op_Const && get_Const_type(pred) != tp) {
2441     n = new_rd_Const_type(NULL, current_ir_graph, get_irn_n(pred, -1), get_irn_mode(pred),
2442               get_Const_tarval(pred), tp);
2443     DBG_OPT_CSTEVAL(oldn, n);
2444   } else if ((get_irn_op(pred) == op_SymConst) && (get_SymConst_value_type(pred) != tp)) {
2445     n = new_rd_SymConst_type(NULL, current_ir_graph, get_irn_n(pred, -1), get_SymConst_symbol(pred),
2446                  get_SymConst_kind(pred), tp);
2447     DBG_OPT_CSTEVAL(oldn, n);
2448   }
2449
2450   return n;
2451 }  /* transform_node_Cast */
2452
2453 /**
2454  * Transform a Proj(Div) with a non-zero value.
2455  * Removes the exceptions and routes the memory to the NoMem node.
2456  */
2457 static ir_node *transform_node_Proj_Div(ir_node *proj)
2458 {
2459   ir_node *n = get_Proj_pred(proj);
2460   ir_node *b = get_Div_right(n);
2461   ir_node *confirm;
2462   long proj_nr;
2463
2464   if (value_not_zero(b, &confirm)) {
2465     /* div(x, y) && y != 0 */
2466     proj_nr = get_Proj_proj(proj);
2467     if (proj_nr == pn_Div_X_except) {
2468       /* we found an exception handler, remove it */
2469       DBG_OPT_EXC_REM(proj);
2470       return new_Bad();
2471     }
2472     else if (proj_nr == pn_Div_M) {
2473       ir_node *res = get_Div_mem(n);
2474       ir_node *new_mem = get_irg_no_mem(current_ir_graph);
2475
2476       if (confirm) {
2477         /* This node can only float up to the Confirm block */
2478         new_mem = new_r_Pin(current_ir_graph, get_nodes_block(confirm), new_mem);
2479       }
2480       set_irn_pinned(n, op_pin_state_floats);
2481       /* this is a Div without exception, we can remove the memory edge */
2482       set_Div_mem(n, new_mem);
2483       return res;
2484     }
2485   }
2486   return proj;
2487 }  /* transform_node_Proj_Div */
2488
2489 /**
2490  * Transform a Proj(Mod) with a non-zero value.
2491  * Removes the exceptions and routes the memory to the NoMem node.
2492  */
2493 static ir_node *transform_node_Proj_Mod(ir_node *proj)
2494 {
2495   ir_node *n = get_Proj_pred(proj);
2496   ir_node *b = get_Mod_right(n);
2497   ir_node *confirm;
2498   long proj_nr;
2499
2500   if (value_not_zero(b, &confirm)) {
2501     /* mod(x, y) && y != 0 */
2502     proj_nr = get_Proj_proj(proj);
2503
2504     if (proj_nr == pn_Mod_X_except) {
2505       /* we found an exception handler, remove it */
2506       DBG_OPT_EXC_REM(proj);
2507       return new_Bad();
2508     } else if (proj_nr == pn_Mod_M) {
2509       ir_node *res = get_Mod_mem(n);
2510       ir_node *new_mem = get_irg_no_mem(current_ir_graph);
2511
2512       if (confirm) {
2513         /* This node can only float up to the Confirm block */
2514         new_mem = new_r_Pin(current_ir_graph, get_nodes_block(confirm), new_mem);
2515       }
2516       set_irn_pinned(n, op_pin_state_floats);
2517       /* this is a Mod without exception, we can remove the memory edge */
2518       set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
2519       return res;
2520     }
2521     else if (proj_nr == pn_Mod_res && get_Mod_left(n) == b) {
2522       /* a % a = 0 if a != 0 */
2523       ir_mode *mode = get_irn_mode(proj);
2524       ir_node *res  = new_Const(mode, get_mode_null(mode));
2525
2526       DBG_OPT_CSTEVAL(n, res);
2527       return res;
2528     }
2529   }
2530   return proj;
2531 }  /* transform_node_Proj_Mod */
2532
2533 /**
2534  * Transform a Proj(DivMod) with a non-zero value.
2535  * Removes the exceptions and routes the memory to the NoMem node.
2536  */
2537 static ir_node *transform_node_Proj_DivMod(ir_node *proj)
2538 {
2539   ir_node *n = get_Proj_pred(proj);
2540   ir_node *b = get_DivMod_right(n);
2541   ir_node *confirm;
2542   long proj_nr;
2543
2544   if (value_not_zero(b, &confirm)) {
2545     /* DivMod(x, y) && y != 0 */
2546     proj_nr = get_Proj_proj(proj);
2547
2548     if (proj_nr == pn_DivMod_X_except) {
2549       /* we found an exception handler, remove it */
2550       DBG_OPT_EXC_REM(proj);
2551       return new_Bad();
2552     }
2553     else if (proj_nr == pn_DivMod_M) {
2554       ir_node *res = get_DivMod_mem(n);
2555       ir_node *new_mem = get_irg_no_mem(current_ir_graph);
2556
2557       if (confirm) {
2558         /* This node can only float up to the Confirm block */
2559         new_mem = new_r_Pin(current_ir_graph, get_nodes_block(confirm), new_mem);
2560       }
2561       set_irn_pinned(n, op_pin_state_floats);
2562       /* this is a DivMod without exception, we can remove the memory edge */
2563       set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
2564       return res;
2565     }
2566     else if (proj_nr == pn_DivMod_res_mod && get_DivMod_left(n) == b) {
2567       /* a % a = 0 if a != 0 */
2568       ir_mode *mode = get_irn_mode(proj);
2569       ir_node *res  = new_Const(mode, get_mode_null(mode));
2570
2571       DBG_OPT_CSTEVAL(n, res);
2572       return res;
2573     }
2574   }
2575   return proj;
2576 }  /* transform_node_Proj_DivMod */
2577
2578 /**
2579  * Optimizes jump tables (CondIs or CondIu) by removing all impossible cases.
2580  */
2581 static ir_node *transform_node_Proj_Cond(ir_node *proj)
2582 {
2583   if (get_opt_unreachable_code()) {
2584     ir_node *n = get_Proj_pred(proj);
2585     ir_node *b = get_Cond_selector(n);
2586
2587     if (mode_is_int(get_irn_mode(b))) {
2588       tarval *tb = value_of(b);
2589
2590       if (tb != tarval_bad) {
2591         /* we have a constant switch */
2592         long num = get_Proj_proj(proj);
2593
2594         if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
2595           if (get_tarval_long(tb) == num) {
2596             /* Do NOT create a jump here, or we will have 2 control flow ops
2597              * in a block. This case is optimized away in optimize_cf(). */
2598             return proj;
2599           }
2600           else {
2601             /* this case will NEVER be taken, kill it */
2602             return new_Bad();
2603           }
2604         }
2605       }
2606     }
2607   }
2608   return proj;
2609 }  /* transform_node_Proj_Cond */
2610
2611 /**
2612  * Normalizes and optimizes Cmp nodes.
2613  */
2614 static ir_node *transform_node_Proj_Cmp(ir_node *proj)
2615 {
2616   if (get_opt_reassociation()) {
2617     ir_node *n     = get_Proj_pred(proj);
2618     ir_node *left  = get_Cmp_left(n);
2619     ir_node *right = get_Cmp_right(n);
2620     ir_node *c     = NULL;
2621     tarval *tv     = NULL;
2622     int changed    = 0;
2623     ir_mode *mode  = NULL;
2624     long proj_nr   = get_Proj_proj(proj);
2625
2626     /*
2627      * First step: normalize the compare op
2628      * by placing the constant on the right site
2629      * or moving the lower address node to the left.
2630      * We ignore the case that both are constants
2631      * this case should be optimized away.
2632      */
2633     if (get_irn_op(right) == op_Const)
2634       c = right;
2635     else if (get_irn_op(left) == op_Const) {
2636       c     = left;
2637       left  = right;
2638       right = c;
2639
2640       proj_nr = get_inversed_pnc(proj_nr);
2641       changed |= 1;
2642     }
2643     else if (get_irn_idx(left) > get_irn_idx(right)) {
2644       ir_node *t = left;
2645
2646       left  = right;
2647       right = t;
2648
2649       proj_nr = get_inversed_pnc(proj_nr);
2650       changed |= 1;
2651     }
2652
2653     /*
2654      * Second step: Try to reduce the magnitude
2655      * of a constant. This may help to generate better code
2656      * later and may help to normalize more compares.
2657      * Of course this is only possible for integer values.
2658      */
2659     if (c) {
2660       mode = get_irn_mode(c);
2661       tv = get_Const_tarval(c);
2662
2663       if (tv != tarval_bad) {
2664         /* the following optimization is possible on modes without Overflow
2665          * on Unary Minus or on == and !=:
2666          * -a CMP c  ==>  a swap(CMP) -c
2667          *
2668          * Beware: for two-complement Overflow may occur, so only == and != can
2669          * be optimized, see this:
2670          * -MININT < 0 =/=> MININT > 0 !!!
2671          */
2672         if (get_opt_constant_folding() && get_irn_op(left) == op_Minus &&
2673             (!mode_overflow_on_unary_Minus(mode) ||
2674              (mode_is_int(mode) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)))) {
2675           left = get_Minus_op(left);
2676           tv = tarval_sub(get_mode_null(mode), tv);
2677
2678           proj_nr = get_inversed_pnc(proj_nr);
2679           changed |= 2;
2680         }
2681
2682         /* for integer modes, we have more */
2683         if (mode_is_int(mode)) {
2684           /* Ne includes Unordered which is not possible on integers.
2685            * However, frontends often use this wrong, so fix it here */
2686           if (proj_nr & pn_Cmp_Uo) {
2687             proj_nr &= ~pn_Cmp_Uo;
2688             set_Proj_proj(proj, proj_nr);
2689           }
2690
2691           /* c > 0 : a < c  ==>  a <= (c-1)    a >= c  ==>  a > (c-1) */
2692           if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Ge) &&
2693               tarval_cmp(tv, get_mode_null(mode)) == pn_Cmp_Gt) {
2694             tv = tarval_sub(tv, get_mode_one(mode));
2695
2696             proj_nr ^= pn_Cmp_Eq;
2697             changed |= 2;
2698           }
2699           /* c < 0 : a > c  ==>  a >= (c+1)    a <= c  ==>  a < (c+1) */
2700           else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Le) &&
2701               tarval_cmp(tv, get_mode_null(mode)) == pn_Cmp_Lt) {
2702             tv = tarval_add(tv, get_mode_one(mode));
2703
2704             proj_nr ^= pn_Cmp_Eq;
2705             changed |= 2;
2706           }
2707
2708           /* the following reassociations work only for == and != */
2709           if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
2710
2711             /* a-b == 0  ==>  a == b,  a-b != 0  ==>  a != b */
2712             if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
2713               right = get_Sub_right(left);
2714               left  = get_Sub_left(left);
2715
2716               tv = value_of(right);
2717               changed = 1;
2718             }
2719
2720             if (tv != tarval_bad) {
2721               ir_op *op = get_irn_op(left);
2722
2723               /* a-c1 == c2  ==>  a == c2+c1,  a-c1 != c2  ==>  a != c2+c1 */
2724               if (op == op_Sub) {
2725                 ir_node *c1 = get_Sub_right(left);
2726                 tarval *tv2 = value_of(c1);
2727
2728                 if (tv2 != tarval_bad) {
2729                   tv2 = tarval_add(tv, value_of(c1));
2730
2731                   if (tv2 != tarval_bad) {
2732                     left    = get_Sub_left(left);
2733                     tv      = tv2;
2734                     changed |= 2;
2735                   }
2736                 }
2737               }
2738               /* a+c1 == c2  ==>  a == c2-c1,  a+c1 != c2  ==>  a != c2-c1 */
2739               else if (op == op_Add) {
2740                 ir_node *a_l = get_Add_left(left);
2741                 ir_node *a_r = get_Add_right(left);
2742                 ir_node *a;
2743                 tarval *tv2;
2744
2745                 if (get_irn_op(a_l) == op_Const) {
2746                   a = a_r;
2747                   tv2 = value_of(a_l);
2748                 }
2749                 else {
2750                   a = a_l;
2751                   tv2 = value_of(a_r);
2752                 }
2753
2754                 if (tv2 != tarval_bad) {
2755                   tv2 = tarval_sub(tv, tv2);
2756
2757                   if (tv2 != tarval_bad) {
2758                     left    = a;
2759                     tv      = tv2;
2760                     changed |= 2;
2761                   }
2762                 }
2763               }
2764               /* -a == c ==> a == -c, -a != c ==> a != -c */
2765               else if (op == op_Minus) {
2766                 tarval *tv2 = tarval_sub(get_mode_null(mode), tv);
2767
2768                 if (tv2 != tarval_bad) {
2769                   left    = get_Minus_op(left);
2770                   tv      = tv2;
2771                   changed |= 2;
2772                 }
2773               }
2774             }
2775           } /* == or != */
2776           /* the following reassociations work only for <= */
2777           else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2778             if (tv != tarval_bad) {
2779               ir_op *op = get_irn_op(left);
2780
2781               /* c >= 0 : Abs(a) <= c  ==>  (unsigned)(a + c) <= 2*c */
2782               if (op == op_Abs) {
2783               }
2784             }
2785           }
2786         } /* mode_is_int */
2787
2788         /*
2789          * optimization for AND:
2790          * Optimize:
2791          *   And(x, C) == C  ==>  And(x, C) != 0
2792          *   And(x, C) != C  ==>  And(X, C) == 0
2793          *
2794          * if C is a single Bit constant.
2795          */
2796         if ((proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) &&
2797             (get_irn_op(left) == op_And)) {
2798           if (is_single_bit_tarval(tv)) {
2799             /* check for Constant's match. We have check hare the tarvals,
2800                because our const might be changed */
2801             ir_node *la = get_And_left(left);
2802             ir_node *ra = get_And_right(left);
2803             if ((is_Const(la) && get_Const_tarval(la) == tv) ||
2804                 (is_Const(ra) && get_Const_tarval(ra) == tv)) {
2805               /* fine: do the transformation */
2806               tv = get_mode_null(get_tarval_mode(tv));
2807               proj_nr ^= pn_Cmp_Leg;
2808               changed |= 2;
2809             }
2810           }
2811         }
2812       } /* tarval != bad */
2813     }
2814
2815     if (changed) {
2816       ir_node *block = get_irn_n(n, -1); /* Beware of get_nodes_Block() */
2817
2818       if (changed & 2)      /* need a new Const */
2819         right = new_Const(mode, tv);
2820
2821       /* create a new compare */
2822       n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
2823             left, right);
2824
2825       set_Proj_pred(proj, n);
2826       set_Proj_proj(proj, proj_nr);
2827     }
2828   }
2829   return proj;
2830 }  /* transform_node_Proj_Cmp */
2831
2832 /**
2833  * Does all optimizations on nodes that must be done on it's Proj's
2834  * because of creating new nodes.
2835  */
2836 static ir_node *transform_node_Proj(ir_node *proj)
2837 {
2838   ir_node *n = get_Proj_pred(proj);
2839
2840   switch (get_irn_opcode(n)) {
2841   case iro_Div:
2842     return transform_node_Proj_Div(proj);
2843
2844   case iro_Mod:
2845     return transform_node_Proj_Mod(proj);
2846
2847   case iro_DivMod:
2848     return transform_node_Proj_DivMod(proj);
2849
2850   case iro_Cond:
2851     return transform_node_Proj_Cond(proj);
2852
2853   case iro_Cmp:
2854     return transform_node_Proj_Cmp(proj);
2855
2856   case iro_Tuple:
2857     /* should not happen, but if it does will be optimized away */
2858     return equivalent_node_Proj(proj);
2859
2860   default:
2861     /* do nothing */
2862     return proj;
2863   }
2864 }  /* transform_node_Proj */
2865
2866 /**
2867  * Move Confirms down through Phi nodes.
2868  */
2869 static ir_node *transform_node_Phi(ir_node *phi) {
2870   int i, n;
2871   ir_mode *mode = get_irn_mode(phi);
2872
2873   if (mode_is_reference(mode)) {
2874     n = get_irn_arity(phi);
2875
2876     /* Beware of Phi0 */
2877     if (n > 0) {
2878       ir_node *pred = get_irn_n(phi, 0);
2879       ir_node *bound, *new_Phi, *block, **in;
2880       pn_Cmp  pnc;
2881
2882       if (! is_Confirm(pred))
2883         return phi;
2884
2885       bound = get_Confirm_bound(pred);
2886       pnc   = get_Confirm_cmp(pred);
2887
2888       NEW_ARR_A(ir_node *, in, n);
2889       in[0] = get_Confirm_value(pred);
2890
2891       for (i = 1; i < n; ++i) {
2892         pred = get_irn_n(phi, i);
2893
2894         if (! is_Confirm(pred) ||
2895             get_Confirm_bound(pred) != bound ||
2896             get_Confirm_cmp(pred) != pnc)
2897           return phi;
2898         in[i] = get_Confirm_value(pred);
2899       }
2900       /* move the Confirm nodes "behind" the Phi */
2901       block = get_irn_n(phi, -1);
2902       new_Phi = new_r_Phi(current_ir_graph, block, n, in, get_irn_mode(phi));
2903       return new_r_Confirm(current_ir_graph, block, new_Phi, bound, pnc);
2904     }
2905   }
2906   return phi;
2907 }  /* transform_node_Phi */
2908
2909 /**
2910  * Returns the operands of a commutative bin-op, if one operand is
2911  * a const, it is returned as the second one.
2912  */
2913 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
2914 {
2915   ir_node *op_a = get_binop_left(binop);
2916   ir_node *op_b = get_binop_right(binop);
2917
2918   assert(is_op_commutative(get_irn_op(binop)));
2919
2920   if (get_irn_op(op_a) == op_Const) {
2921     *a = op_b;
2922     *c = op_a;
2923   }
2924   else {
2925     *a = op_a;
2926     *c = op_b;
2927   }
2928 }  /* get_comm_Binop_Ops */
2929
2930 /**
2931  * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
2932  * Such pattern may arise in bitfield stores.
2933  *
2934  * value  c4                  value      c4 & c2
2935  *    AND     c3                    AND           c1 | c3
2936  *        OR     c2      ===>               OR
2937  *           AND    c1
2938  *               OR
2939  */
2940 static ir_node *transform_node_Or_bf_store(ir_node *or)
2941 {
2942   ir_node *and, *c1;
2943   ir_node *or_l, *c2;
2944   ir_node *and_l, *c3;
2945   ir_node *value, *c4;
2946   ir_node *new_and, *new_const, *block;
2947   ir_mode *mode = get_irn_mode(or);
2948
2949   tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
2950
2951   get_comm_Binop_Ops(or, &and, &c1);
2952   if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
2953     return or;
2954
2955   get_comm_Binop_Ops(and, &or_l, &c2);
2956   if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
2957     return or;
2958
2959   get_comm_Binop_Ops(or_l, &and_l, &c3);
2960   if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
2961     return or;
2962
2963   get_comm_Binop_Ops(and_l, &value, &c4);
2964   if (get_irn_op(c4) != op_Const)
2965     return or;
2966
2967   /* ok, found the pattern, check for conditions */
2968   assert(mode == get_irn_mode(and));
2969   assert(mode == get_irn_mode(or_l));
2970   assert(mode == get_irn_mode(and_l));
2971
2972   tv1 = get_Const_tarval(c1);
2973   tv2 = get_Const_tarval(c2);
2974   tv3 = get_Const_tarval(c3);
2975   tv4 = get_Const_tarval(c4);
2976
2977   tv = tarval_or(tv4, tv2);
2978   if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
2979     /* have at least one 0 at the same bit position */
2980     return or;
2981   }
2982
2983   n_tv4 = tarval_not(tv4);
2984   if (tv3 != tarval_and(tv3, n_tv4)) {
2985     /* bit in the or_mask is outside the and_mask */
2986     return or;
2987   }
2988
2989   n_tv2 = tarval_not(tv2);
2990   if (tv1 != tarval_and(tv1, n_tv2)) {
2991     /* bit in the or_mask is outside the and_mask */
2992     return or;
2993   }
2994
2995   /* ok, all conditions met */
2996   block = get_irn_n(or, -1);
2997
2998   new_and = new_r_And(current_ir_graph, block,
2999       value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
3000
3001   new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
3002
3003   set_Or_left(or, new_and);
3004   set_Or_right(or, new_const);
3005
3006   /* check for more */
3007   return transform_node_Or_bf_store(or);
3008 }  /* transform_node_Or_bf_store */
3009
3010 /**
3011  * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
3012  */
3013 static ir_node *transform_node_Or_Rot(ir_node *or)
3014 {
3015   ir_mode *mode = get_irn_mode(or);
3016   ir_node *shl, *shr, *block;
3017   ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
3018   tarval *tv1, *tv2;
3019
3020   if (! mode_is_int(mode))
3021     return or;
3022
3023   shl = get_binop_left(or);
3024   shr = get_binop_right(or);
3025
3026   if (get_irn_op(shl) == op_Shr) {
3027     if (get_irn_op(shr) != op_Shl)
3028       return or;
3029
3030     irn = shl;
3031     shl = shr;
3032     shr = irn;
3033   }
3034   else if (get_irn_op(shl) != op_Shl)
3035     return or;
3036   else if (get_irn_op(shr) != op_Shr)
3037     return or;
3038
3039   x = get_Shl_left(shl);
3040   if (x != get_Shr_left(shr))
3041     return or;
3042
3043   c1 = get_Shl_right(shl);
3044   c2 = get_Shr_right(shr);
3045   if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
3046     tv1 = get_Const_tarval(c1);
3047     if (! tarval_is_long(tv1))
3048       return or;
3049
3050     tv2 = get_Const_tarval(c2);
3051     if (! tarval_is_long(tv2))
3052       return or;
3053
3054     if (get_tarval_long(tv1) + get_tarval_long(tv2)
3055         != get_mode_size_bits(mode))
3056       return or;
3057
3058     /* yet, condition met */
3059     block = get_irn_n(or, -1);
3060
3061     n = new_r_Rot(current_ir_graph, block, x, c1, mode);
3062
3063     DBG_OPT_ALGSIM1(or, shl, shr, n, FS_OPT_OR_SHFT_TO_ROT);
3064     return n;
3065   }
3066   else if (get_irn_op(c1) == op_Sub) {
3067     v   = c2;
3068     sub = c1;
3069
3070     if (get_Sub_right(sub) != v)
3071       return or;
3072
3073     c1 = get_Sub_left(sub);
3074     if (get_irn_op(c1) != op_Const)
3075       return or;
3076
3077     tv1 = get_Const_tarval(c1);
3078     if (! tarval_is_long(tv1))
3079       return or;
3080
3081     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
3082       return or;
3083
3084     /* yet, condition met */
3085     block = get_nodes_block(or);
3086
3087     /* a Rot right is not supported, so use a rot left */
3088     n =  new_r_Rot(current_ir_graph, block, x, sub, mode);
3089
3090     DBG_OPT_ALGSIM0(or, n, FS_OPT_OR_SHFT_TO_ROT);
3091     return n;
3092   }
3093   else if (get_irn_op(c2) == op_Sub) {
3094     v   = c1;
3095     sub = c2;
3096
3097     c1 = get_Sub_left(sub);
3098     if (get_irn_op(c1) != op_Const)
3099       return or;
3100
3101     tv1 = get_Const_tarval(c1);
3102     if (! tarval_is_long(tv1))
3103       return or;
3104
3105     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
3106       return or;
3107
3108     /* yet, condition met */
3109     block = get_irn_n(or, -1);
3110
3111     /* a Rot Left */
3112     n = new_r_Rot(current_ir_graph, block, x, v, mode);
3113
3114     DBG_OPT_ALGSIM0(or, n, FS_OPT_OR_SHFT_TO_ROT);
3115     return n;
3116   }
3117
3118   return or;
3119 }  /* transform_node_Or_Rot */
3120
3121 /**
3122  * Transform an Or.
3123  */
3124 static ir_node *transform_node_Or(ir_node *n)
3125 {
3126   ir_node *c, *oldn = n;
3127   ir_node *a = get_Or_left(n);
3128   ir_node *b = get_Or_right(n);
3129
3130   HANDLE_BINOP_PHI(tarval_or, a,b,c);
3131
3132   n = transform_node_Or_bf_store(n);
3133   n = transform_node_Or_Rot(n);
3134
3135   return n;
3136 }  /* transform_node_Or */
3137
3138
3139 /* forward */
3140 static ir_node *transform_node(ir_node *n);
3141
3142 /**
3143  * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl.
3144  *
3145  * Should be moved to reassociation?
3146  */
3147 static ir_node *transform_node_shift(ir_node *n)
3148 {
3149   ir_node *left, *right;
3150   tarval *tv1, *tv2, *res;
3151   ir_mode *mode;
3152   int modulo_shf, flag;
3153
3154   left = get_binop_left(n);
3155
3156   /* different operations */
3157   if (get_irn_op(left) != get_irn_op(n))
3158     return n;
3159
3160   right = get_binop_right(n);
3161   tv1 = value_of(right);
3162   if (tv1 == tarval_bad)
3163     return n;
3164
3165   tv2 = value_of(get_binop_right(left));
3166   if (tv2 == tarval_bad)
3167     return n;
3168
3169   res = tarval_add(tv1, tv2);
3170
3171   /* beware: a simple replacement works only, if res < modulo shift */
3172   mode = get_irn_mode(n);
3173
3174   flag = 0;
3175
3176   modulo_shf = get_mode_modulo_shift(mode);
3177   if (modulo_shf > 0) {
3178     tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
3179
3180     if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
3181       flag = 1;
3182   }
3183   else
3184     flag = 1;
3185
3186   if (flag) {
3187     /* ok, we can replace it */
3188     ir_node *in[2], *irn, *block = get_irn_n(n, -1);
3189
3190     in[0] = get_binop_left(left);
3191     in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
3192
3193     irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
3194
3195     DBG_OPT_ALGSIM0(n, irn, FS_OPT_REASSOC_SHIFT);
3196
3197     return transform_node(irn);
3198   }
3199   return n;
3200 }  /* transform_node_shift */
3201
3202 /**
3203  * Transform a Shr.
3204  */
3205 static ir_node *transform_node_Shr(ir_node *n)
3206 {
3207   ir_node *c, *oldn = n;
3208   ir_node *a = get_Shr_left(n);
3209   ir_node *b = get_Shr_right(n);
3210
3211   HANDLE_BINOP_PHI(tarval_shr, a, b, c);
3212   return transform_node_shift(n);
3213 }  /* transform_node_Shr */
3214
3215 /**
3216  * Transform a Shrs.
3217  */
3218 static ir_node *transform_node_Shrs(ir_node *n)
3219 {
3220   ir_node *c, *oldn = n;
3221   ir_node *a = get_Shrs_left(n);
3222   ir_node *b = get_Shrs_right(n);
3223
3224   HANDLE_BINOP_PHI(tarval_shrs, a, b, c);
3225   return transform_node_shift(n);
3226 }  /* transform_node_Shrs */
3227
3228 /**
3229  * Transform a Shl.
3230  */
3231 static ir_node *transform_node_Shl(ir_node *n)
3232 {
3233   ir_node *c, *oldn = n;
3234   ir_node *a = get_Shl_left(n);
3235   ir_node *b = get_Shl_right(n);
3236
3237   HANDLE_BINOP_PHI(tarval_shl, a, b, c);
3238   return transform_node_shift(n);
3239 }  /* transform_node_Shl */
3240
3241 /**
3242  * Remove dead blocks and nodes in dead blocks
3243  * in keep alive list.  We do not generate a new End node.
3244  */
3245 static ir_node *transform_node_End(ir_node *n) {
3246   int i, n_keepalives = get_End_n_keepalives(n);
3247
3248   for (i = 0; i < n_keepalives; ++i) {
3249     ir_node *ka = get_End_keepalive(n, i);
3250     if (is_Block(ka)) {
3251       if (is_Block_dead(ka)) {
3252         set_End_keepalive(n, i, new_Bad());
3253       }
3254     }
3255     else if (is_irn_pinned_in_irg(ka) && is_Block_dead(get_nodes_block(ka)))
3256       set_End_keepalive(n, i, new_Bad());
3257   }
3258   return n;
3259 }  /* transform_node_End */
3260
3261 /**
3262  * Optimize a Mux into some simpler cases.
3263  */
3264 static ir_node *transform_node_Mux(ir_node *n)
3265 {
3266   ir_node *oldn = n, *sel = get_Mux_sel(n);
3267   ir_mode *mode = get_irn_mode(n);
3268
3269   if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(mode)) {
3270     ir_node *cmp = get_Proj_pred(sel);
3271     long proj_nr = get_Proj_proj(sel);
3272     ir_node *f   =  get_Mux_false(n);
3273     ir_node *t   = get_Mux_true(n);
3274
3275     if (get_irn_op(cmp) == op_Cmp && classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
3276       ir_node *block = get_irn_n(n, -1);
3277
3278       /*
3279        * Note: normalization puts the constant on the right site,
3280        * so we check only one case.
3281        *
3282        * Note further that these optimization work even for floating point
3283        * with NaN's because -NaN == NaN.
3284        * However, if +0 and -0 is handled differently, we cannot use the first one.
3285        */
3286       if (get_irn_op(f) == op_Minus &&
3287           get_Minus_op(f)   == t &&
3288           get_Cmp_left(cmp) == t) {
3289
3290         if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
3291           /* Mux(a >=/> 0, -a, a)  ==>  Abs(a) */
3292           n = new_rd_Abs(get_irn_dbg_info(n),
3293                 current_ir_graph,
3294                 block,
3295                 t, mode);
3296           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
3297           return n;
3298         }
3299         else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
3300           /* Mux(a <=/< 0, -a, a)  ==>  Minus(Abs(a)) */
3301           n = new_rd_Abs(get_irn_dbg_info(n),
3302                 current_ir_graph,
3303                 block,
3304                 t, mode);
3305           n = new_rd_Minus(get_irn_dbg_info(n),
3306                 current_ir_graph,
3307                 block,
3308                 n, mode);
3309
3310           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
3311           return n;
3312         }
3313       }
3314       else if (get_irn_op(t) == op_Minus &&
3315           get_Minus_op(t)   == f &&
3316           get_Cmp_left(cmp) == f) {
3317
3318         if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
3319           /* Mux(a <=/< 0, a, -a)  ==>  Abs(a) */
3320           n = new_rd_Abs(get_irn_dbg_info(n),
3321                 current_ir_graph,
3322                 block,
3323                 f, mode);
3324           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
3325           return n;
3326         }
3327         else if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
3328           /* Mux(a >=/> 0, a, -a)  ==>  Minus(Abs(a)) */
3329           n = new_rd_Abs(get_irn_dbg_info(n),
3330                 current_ir_graph,
3331                 block,
3332                 f, mode);
3333           n = new_rd_Minus(get_irn_dbg_info(n),
3334                 current_ir_graph,
3335                 block,
3336                 n, mode);
3337
3338           DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_ABS);
3339           return n;
3340         }
3341       }
3342
3343       if (mode_is_int(mode) && mode_is_signed(mode) &&
3344           get_mode_arithmetic(mode) == irma_twos_complement) {
3345         ir_node *x = get_Cmp_left(cmp);
3346
3347         /* the following optimization works only with signed integer two-complement mode */
3348
3349         if (mode == get_irn_mode(x)) {
3350           /*
3351            * FIXME: this restriction is two rigid, as it would still
3352            * work if mode(x) = Hs and mode == Is, but at least it removes
3353            * all wrong cases.
3354            */
3355           if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Le) &&
3356               classify_Const(t) == CNST_ALL_ONE &&
3357               classify_Const(f) == CNST_NULL) {
3358             /*
3359              * Mux(x:T </<= 0, 0, -1) -> Shrs(x, sizeof_bits(T) - 1)
3360              * Conditions:
3361              * T must be signed.
3362              */
3363             n = new_rd_Shrs(get_irn_dbg_info(n),
3364                   current_ir_graph, block, x,
3365                   new_r_Const_long(current_ir_graph, block, mode_Iu,
3366                     get_mode_size_bits(mode) - 1),
3367                   mode);
3368             DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_SHR);
3369             return n;
3370           }
3371           else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Ge) &&
3372                    classify_Const(t) == CNST_ONE &&
3373                    classify_Const(f) == CNST_NULL) {
3374             /*
3375              * Mux(x:T >/>= 0, 0, 1) -> Shr(-x, sizeof_bits(T) - 1)
3376              * Conditions:
3377              * T must be signed.
3378              */
3379             n = new_rd_Shr(get_irn_dbg_info(n),
3380                   current_ir_graph, block,
3381                   new_r_Minus(current_ir_graph, block, x, mode),
3382                   new_r_Const_long(current_ir_graph, block, mode_Iu,
3383                     get_mode_size_bits(mode) - 1),
3384                   mode);
3385             DBG_OPT_ALGSIM1(oldn, cmp, sel, n, FS_OPT_MUX_TO_SHR);
3386             return n;
3387           }
3388         }
3389       }
3390     }
3391   }
3392   return arch_transform_node_Mux(n);
3393 }  /* transform_node_Mux */
3394
3395 /**
3396  * Optimize a Psi into some simpler cases.
3397  */
3398 static ir_node *transform_node_Psi(ir_node *n) {
3399   if (is_Mux(n))
3400     return transform_node_Mux(n);
3401
3402   return n;
3403 }  /* transform_node_Psi */
3404
3405 /**
3406  * Tries several [inplace] [optimizing] transformations and returns an
3407  * equivalent node.  The difference to equivalent_node() is that these
3408  * transformations _do_ generate new nodes, and thus the old node must
3409  * not be freed even if the equivalent node isn't the old one.
3410  */
3411 static ir_node *transform_node(ir_node *n)
3412 {
3413   if (n->op->ops.transform_node)
3414     n = n->op->ops.transform_node(n);
3415   return n;
3416 }  /* transform_node */
3417
3418 /**
3419  * sSets the default transform node operation for an ir_op_ops.
3420  *
3421  * @param code   the opcode for the default operation
3422  * @param ops    the operations initialized
3423  *
3424  * @return
3425  *    The operations.
3426  */
3427 static ir_op_ops *firm_set_default_transform_node(opcode code, ir_op_ops *ops)
3428 {
3429 #define CASE(a)                                 \
3430   case iro_##a:                                 \
3431     ops->transform_node  = transform_node_##a;   \
3432     break
3433
3434   switch (code) {
3435   CASE(Add);
3436   CASE(Sub);
3437   CASE(Mul);
3438   CASE(Div);
3439   CASE(Mod);
3440   CASE(DivMod);
3441   CASE(Abs);
3442   CASE(Cond);
3443   CASE(And);
3444   CASE(Or);
3445   CASE(Eor);
3446   CASE(Minus);
3447   CASE(Not);
3448   CASE(Cast);
3449   CASE(Proj);
3450   CASE(Phi);
3451   CASE(Sel);
3452   CASE(Shr);
3453   CASE(Shrs);
3454   CASE(Shl);
3455   CASE(End);
3456   CASE(Mux);
3457   CASE(Psi);
3458   default:
3459     /* leave NULL */;
3460   }
3461
3462   return ops;
3463 #undef CASE
3464 }  /* firm_set_default_transform_node */
3465
3466
3467 /* **************** Common Subexpression Elimination **************** */
3468
3469 /** The size of the hash table used, should estimate the number of nodes
3470     in a graph. */
3471 #define N_IR_NODES 512
3472
3473 /** Compares the attributes of two Const nodes. */
3474 static int node_cmp_attr_Const(ir_node *a, ir_node *b) {
3475   return (get_Const_tarval(a) != get_Const_tarval(b))
3476       || (get_Const_type(a) != get_Const_type(b));
3477 }  /* node_cmp_attr_Const */
3478
3479 /** Compares the attributes of two Proj nodes. */
3480 static int node_cmp_attr_Proj(ir_node *a, ir_node *b) {
3481   return get_irn_proj_attr (a) != get_irn_proj_attr (b);
3482 }  /* node_cmp_attr_Proj */
3483
3484 /** Compares the attributes of two Filter nodes. */
3485 static int node_cmp_attr_Filter(ir_node *a, ir_node *b) {
3486   return get_Filter_proj(a) != get_Filter_proj(b);
3487 }  /* node_cmp_attr_Filter */
3488
3489 /** Compares the attributes of two Alloc nodes. */
3490 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b) {
3491   return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
3492       || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
3493 }  /* node_cmp_attr_Alloc */
3494
3495 /** Compares the attributes of two Free nodes. */
3496 static int node_cmp_attr_Free(ir_node *a, ir_node *b) {
3497   return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
3498       || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
3499 }  /* node_cmp_attr_Free */
3500
3501 /** Compares the attributes of two SymConst nodes. */
3502 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b) {
3503   return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
3504       || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
3505       || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
3506 }  /* node_cmp_attr_SymConst */
3507
3508 /** Compares the attributes of two Call nodes. */
3509 static int node_cmp_attr_Call(ir_node *a, ir_node *b) {
3510   return (get_irn_call_attr(a) != get_irn_call_attr(b));
3511 }  /* node_cmp_attr_Call */
3512
3513 /** Compares the attributes of two Sel nodes. */
3514 static int node_cmp_attr_Sel(ir_node *a, ir_node *b) {
3515   return (get_irn_sel_attr(a).ent->kind  != get_irn_sel_attr(b).ent->kind)
3516       || (get_irn_sel_attr(a).ent->name    != get_irn_sel_attr(b).ent->name)
3517       || (get_irn_sel_attr(a).ent->owner   != get_irn_sel_attr(b).ent->owner)
3518       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
3519       || (get_irn_sel_attr(a).ent->type    != get_irn_sel_attr(b).ent->type);
3520 }  /* node_cmp_attr_Sel */
3521
3522 /** Compares the attributes of two Phi nodes. */
3523 static int node_cmp_attr_Phi(ir_node *a, ir_node *b) {
3524   return get_irn_phi_attr (a) != get_irn_phi_attr (b);
3525 }  /* node_cmp_attr_Phi */
3526
3527 /** Compares the attributes of two Conv nodes. */
3528 static int node_cmp_attr_Conv(ir_node *a, ir_node *b) {
3529   return get_Conv_strict(a) != get_Conv_strict(b);
3530 }  /* node_cmp_attr_Conv */
3531
3532 /** Compares the attributes of two Cast nodes. */
3533 static int node_cmp_attr_Cast(ir_node *a, ir_node *b) {
3534   return get_Cast_type(a) != get_Cast_type(b);
3535 }  /* node_cmp_attr_Cast */
3536
3537 /** Compares the attributes of two Load nodes. */
3538 static int node_cmp_attr_Load(ir_node *a, ir_node *b) {
3539   if (get_Load_volatility(a) == volatility_is_volatile ||
3540       get_Load_volatility(b) == volatility_is_volatile)
3541     /* NEVER do CSE on volatile Loads */
3542     return 1;
3543
3544   return get_Load_mode(a) != get_Load_mode(b);
3545 }  /* node_cmp_attr_Load */
3546
3547 /** Compares the attributes of two Store nodes. */
3548 static int node_cmp_attr_Store(ir_node *a, ir_node *b) {
3549   /* NEVER do CSE on volatile Stores */
3550   return (get_Store_volatility(a) == volatility_is_volatile ||
3551           get_Store_volatility(b) == volatility_is_volatile);
3552 }  /* node_cmp_attr_Store */
3553
3554 /** Compares the attributes of two Confirm nodes. */
3555 static int node_cmp_attr_Confirm(ir_node *a, ir_node *b) {
3556   return (get_Confirm_cmp(a) != get_Confirm_cmp(b));
3557 }  /* node_cmp_attr_Confirm */
3558
3559 /**
3560  * Set the default node attribute compare operation for an ir_op_ops.
3561  *
3562  * @param code   the opcode for the default operation
3563  * @param ops    the operations initialized
3564  *
3565  * @return
3566  *    The operations.
3567  */
3568 static ir_op_ops *firm_set_default_node_cmp_attr(opcode code, ir_op_ops *ops)
3569 {
3570 #define CASE(a)                              \
3571   case iro_##a:                              \
3572     ops->node_cmp_attr  = node_cmp_attr_##a; \
3573     break
3574
3575   switch (code) {
3576   CASE(Const);
3577   CASE(Proj);
3578   CASE(Filter);
3579   CASE(Alloc);
3580   CASE(Free);
3581   CASE(SymConst);
3582   CASE(Call);
3583   CASE(Sel);
3584   CASE(Phi);
3585   CASE(Conv);
3586   CASE(Cast);
3587   CASE(Load);
3588   CASE(Store);
3589   CASE(Confirm);
3590   default:
3591     /* leave NULL */;
3592   }
3593
3594   return ops;
3595 #undef CASE
3596 }  /* firm_set_default_node_cmp_attr */
3597
3598 /*
3599  * Compare function for two nodes in the hash table. Gets two
3600  * nodes as parameters.  Returns 0 if the nodes are a cse.
3601  */
3602 int identities_cmp(const void *elt, const void *key)
3603 {
3604   ir_node *a, *b;
3605   int i, irn_arity_a;
3606
3607   a = (void *)elt;
3608   b = (void *)key;
3609
3610   if (a == b) return 0;
3611
3612   if ((get_irn_op(a) != get_irn_op(b)) ||
3613       (get_irn_mode(a) != get_irn_mode(b))) return 1;
3614
3615   /* compare if a's in and b's in are of equal length */
3616   irn_arity_a = get_irn_intra_arity (a);
3617   if (irn_arity_a != get_irn_intra_arity(b))
3618     return 1;
3619
3620   /* for block-local cse and op_pin_state_pinned nodes: */
3621   if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
3622     if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
3623       return 1;
3624   }
3625
3626   /* compare a->in[0..ins] with b->in[0..ins] */
3627   for (i = 0; i < irn_arity_a; i++)
3628     if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
3629       return 1;
3630
3631   /*
3632    * here, we already now that the nodes are identical except their
3633    * attributes
3634    */
3635   if (a->op->ops.node_cmp_attr)
3636     return a->op->ops.node_cmp_attr(a, b);
3637
3638   return 0;
3639 }  /* identities_cmp */
3640
3641 /*
3642  * Calculate a hash value of a node.
3643  */
3644 unsigned ir_node_hash(ir_node *node)
3645 {
3646   unsigned h;
3647   int i, irn_arity;
3648
3649   if (node->op == op_Const) {
3650     /* special value for const, as they only differ in their tarval. */
3651     h = HASH_PTR(node->attr.con.tv);
3652     h = 9*h + HASH_PTR(get_irn_mode(node));
3653   } else if (node->op == op_SymConst) {
3654     /* special value for const, as they only differ in their symbol. */
3655     h = HASH_PTR(node->attr.symc.sym.type_p);
3656     h = 9*h + HASH_PTR(get_irn_mode(node));
3657   } else {
3658
3659     /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
3660     h = irn_arity = get_irn_intra_arity(node);
3661
3662     /* consider all in nodes... except the block if not a control flow. */
3663     for (i = is_cfop(node) ? -1 : 0;  i < irn_arity;  i++) {
3664       h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
3665     }
3666
3667     /* ...mode,... */
3668     h = 9*h + HASH_PTR(get_irn_mode(node));
3669     /* ...and code */
3670     h = 9*h + HASH_PTR(get_irn_op(node));
3671   }
3672
3673   return h;
3674 }  /* ir_node_hash */
3675
3676 pset *new_identities(void) {
3677   return new_pset(identities_cmp, N_IR_NODES);
3678 }  /* new_identities */
3679
3680 void del_identities(pset *value_table) {
3681   del_pset(value_table);
3682 }  /* del_identities */
3683
3684 /**
3685  * Return the canonical node computing the same value as n.
3686  * Looks up the node in a hash table.
3687  *
3688  * For Const nodes this is performed in the constructor, too.  Const
3689  * nodes are extremely time critical because of their frequent use in
3690  * constant string arrays.
3691  */
3692 static INLINE ir_node *identify(pset *value_table, ir_node *n)
3693 {
3694   ir_node *o = NULL;
3695
3696   if (!value_table) return n;
3697
3698   if (get_opt_reassociation()) {
3699     if (is_op_commutative(get_irn_op(n))) {
3700       ir_node *l = get_binop_left(n);
3701       ir_node *r = get_binop_right(n);
3702
3703       /* for commutative operators perform  a OP b == b OP a */
3704       if (get_irn_idx(l) > get_irn_idx(r)) {
3705         set_binop_left(n, r);
3706         set_binop_right(n, l);
3707       }
3708     }
3709   }
3710
3711   o = pset_find(value_table, n, ir_node_hash(n));
3712   if (!o) return n;
3713
3714   DBG_OPT_CSE(n, o);
3715
3716   return o;
3717 }  /* identify */
3718
3719 /**
3720  * During construction we set the op_pin_state_pinned flag in the graph right when the
3721  * optimization is performed.  The flag turning on procedure global cse could
3722  * be changed between two allocations.  This way we are safe.
3723  */
3724 static INLINE ir_node *identify_cons(pset *value_table, ir_node *n) {
3725   ir_node *old = n;
3726
3727   n = identify(value_table, n);
3728   if (get_irn_n(old, -1) != get_irn_n(n, -1))
3729     set_irg_pinned(current_ir_graph, op_pin_state_floats);
3730   return n;
3731 }  /* identify_cons */
3732
3733 /*
3734  * Return the canonical node computing the same value as n.
3735  * Looks up the node in a hash table, enters it in the table
3736  * if it isn't there yet.
3737  */
3738 ir_node *identify_remember(pset *value_table, ir_node *n)
3739 {
3740   ir_node *o = NULL;
3741
3742   if (!value_table) return n;
3743
3744   if (get_opt_reassociation()) {
3745     if (is_op_commutative(get_irn_op(n))) {
3746       ir_node *l = get_binop_left(n);
3747       ir_node *r = get_binop_right(n);
3748
3749       /* for commutative operators perform  a OP b == b OP a */
3750       if (l > r) {
3751         set_binop_left(n, r);
3752         set_binop_right(n, l);
3753       }
3754     }
3755   }
3756
3757   /* lookup or insert in hash table with given hash key. */
3758   o = pset_insert (value_table, n, ir_node_hash (n));
3759
3760   if (o != n) {
3761     DBG_OPT_CSE(n, o);
3762   }
3763
3764   return o;
3765 }  /* identify_remember */
3766
3767 /* Add a node to the identities value table. */
3768 void add_identities(pset *value_table, ir_node *node) {
3769   if (get_opt_cse() && is_no_Block(node))
3770     identify_remember(value_table, node);
3771 }  /* add_identities */
3772
3773 /* Visit each node in the value table of a graph. */
3774 void visit_all_identities(ir_graph *irg, irg_walk_func visit, void *env) {
3775   ir_node *node;
3776   ir_graph *rem = current_ir_graph;
3777
3778   current_ir_graph = irg;
3779   foreach_pset(irg->value_table, node)
3780     visit(node, env);
3781   current_ir_graph = rem;
3782 }  /* visit_all_identities */
3783
3784 /**
3785  * Garbage in, garbage out. If a node has a dead input, i.e., the
3786  * Bad node is input to the node, return the Bad node.
3787  */
3788 static INLINE ir_node *gigo(ir_node *node)
3789 {
3790   int i, irn_arity;
3791   ir_op *op = get_irn_op(node);
3792
3793   /* remove garbage blocks by looking at control flow that leaves the block
3794      and replacing the control flow by Bad. */
3795   if (get_irn_mode(node) == mode_X) {
3796     ir_node *block = get_nodes_block(skip_Proj(node));
3797
3798     /* Don't optimize nodes in immature blocks. */
3799     if (!get_Block_matured(block)) return node;
3800      /* Don't optimize End, may have Bads. */
3801     if (op == op_End) return node;
3802
3803     if (is_Block(block)) {
3804       irn_arity = get_irn_arity(block);
3805       for (i = 0; i < irn_arity; i++) {
3806         if (!is_Bad(get_irn_n(block, i)))
3807           break;
3808       }
3809       if (i == irn_arity) return new_Bad();
3810     }
3811   }
3812
3813   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
3814      blocks predecessors is dead. */
3815   if (op != op_Block && op != op_Phi && op != op_Tuple) {
3816     irn_arity = get_irn_arity(node);
3817
3818     /*
3819      * Beware: we can only read the block of a non-floating node.
3820      */
3821     if (is_irn_pinned_in_irg(node) &&
3822         is_Block_dead(get_nodes_block(node)))
3823       return new_Bad();
3824
3825     for (i = 0; i < irn_arity; i++) {
3826       ir_node *pred = get_irn_n(node, i);
3827
3828       if (is_Bad(pred))
3829         return new_Bad();
3830 #if 0
3831       /* Propagating Unknowns here seems to be a bad idea, because
3832          sometimes we need a node as a input and did not want that
3833          it kills it's user.
3834          However, it might be useful to move this into a later phase
3835          (if you think that optimizing such code is useful). */
3836       if (is_Unknown(pred) && mode_is_data(get_irn_mode(node)))
3837         return new_Unknown(get_irn_mode(node));
3838 #endif
3839     }
3840   }
3841 #if 0
3842   /* With this code we violate the agreement that local_optimize
3843      only leaves Bads in Block, Phi and Tuple nodes. */
3844   /* If Block has only Bads as predecessors it's garbage. */
3845   /* If Phi has only Bads as predecessors it's garbage. */
3846   if ((op == op_Block && get_Block_matured(node)) || op == op_Phi)  {
3847     irn_arity = get_irn_arity(node);
3848     for (i = 0; i < irn_arity; i++) {
3849       if (!is_Bad(get_irn_n(node, i))) break;
3850     }
3851     if (i == irn_arity) node = new_Bad();
3852   }
3853 #endif
3854   return node;
3855 }  /* gigo */
3856
3857 /**
3858  * These optimizations deallocate nodes from the obstack.
3859  * It can only be called if it is guaranteed that no other nodes
3860  * reference this one, i.e., right after construction of a node.
3861  *
3862  * current_ir_graph must be set to the graph of the node!
3863  */
3864 ir_node *optimize_node(ir_node *n)
3865 {
3866   tarval *tv;
3867   ir_node *oldn = n;
3868   opcode iro = get_irn_opcode(n);
3869
3870   /* Always optimize Phi nodes: part of the construction. */
3871   if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
3872
3873   /* constant expression evaluation / constant folding */
3874   if (get_opt_constant_folding()) {
3875     /* neither constants nor Tuple values can be evaluated */
3876     if (iro != iro_Const && (get_irn_mode(n) != mode_T)) {
3877       /* try to evaluate */
3878       tv = computed_value(n);
3879       if (tv != tarval_bad) {
3880         ir_node *nw;
3881         ir_type *old_tp = get_irn_type(n);
3882         int i, arity = get_irn_arity(n);
3883         int node_size;
3884
3885         /*
3886          * Try to recover the type of the new expression.
3887          */
3888         for (i = 0; i < arity && !old_tp; ++i)
3889           old_tp = get_irn_type(get_irn_n(n, i));
3890
3891         /*
3892          * we MUST copy the node here temporary, because it's still needed
3893          * for DBG_OPT_CSTEVAL
3894          */
3895         node_size = offsetof(ir_node, attr) +  n->op->attr_size;
3896         oldn = alloca(node_size);
3897
3898         memcpy(oldn, n, node_size);
3899         CLONE_ARR_A(ir_node *, oldn->in, n->in);
3900
3901         /* ARG, copy the in array, we need it for statistics */
3902         memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
3903
3904         /* note the inplace edges module */
3905         edges_node_deleted(n, current_ir_graph);
3906
3907         /* evaluation was successful -- replace the node. */
3908         irg_kill_node(current_ir_graph, n);
3909         nw = new_Const(get_tarval_mode (tv), tv);
3910
3911         if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
3912           set_Const_type(nw, old_tp);
3913         DBG_OPT_CSTEVAL(oldn, nw);
3914         return nw;
3915       }
3916     }
3917   }
3918
3919   /* remove unnecessary nodes */
3920   if (get_opt_constant_folding() ||
3921     (iro == iro_Phi)  ||   /* always optimize these nodes. */
3922     (iro == iro_Id)   ||
3923     (iro == iro_Proj) ||
3924     (iro == iro_Block)  )  /* Flags tested local. */
3925     n = equivalent_node(n);
3926
3927   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
3928
3929   /* Common Subexpression Elimination.
3930    *
3931    * Checks whether n is already available.
3932    * The block input is used to distinguish different subexpressions. Right
3933    * now all nodes are op_pin_state_pinned to blocks, i.e., the CSE only finds common
3934    * subexpressions within a block.
3935    */
3936   if (get_opt_cse())
3937     n = identify_cons(current_ir_graph->value_table, n);
3938
3939   if (n != oldn) {
3940     edges_node_deleted(oldn, current_ir_graph);
3941
3942     /* We found an existing, better node, so we can deallocate the old node. */
3943     irg_kill_node(current_ir_graph, oldn);
3944     return n;
3945   }
3946
3947   /* Some more constant expression evaluation that does not allow to
3948      free the node. */
3949   iro = get_irn_opcode(n);
3950   if (get_opt_constant_folding() ||
3951     (iro == iro_Cond) ||
3952     (iro == iro_Proj))     /* Flags tested local. */
3953     n = transform_node(n);
3954
3955   /* Remove nodes with dead (Bad) input.
3956      Run always for transformation induced Bads. */
3957   n = gigo (n);
3958
3959   /* Now we have a legal, useful node. Enter it in hash table for CSE */
3960   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
3961     n = identify_remember(current_ir_graph->value_table, n);
3962   }
3963
3964   return n;
3965 }  /* optimize_node */
3966
3967
3968 /**
3969  * These optimizations never deallocate nodes (in place).  This can cause dead
3970  * nodes lying on the obstack.  Remove these by a dead node elimination,
3971  * i.e., a copying garbage collection.
3972  */
3973 ir_node *optimize_in_place_2(ir_node *n)
3974 {
3975   tarval *tv;
3976   ir_node *oldn = n;
3977   opcode iro = get_irn_opcode(n);
3978
3979   if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
3980
3981   /* constant expression evaluation / constant folding */
3982   if (get_opt_constant_folding()) {
3983     /* neither constants nor Tuple values can be evaluated */
3984     if (iro != iro_Const && get_irn_mode(n) != mode_T) {
3985       /* try to evaluate */
3986       tv = computed_value(n);
3987       if (tv != tarval_bad) {
3988         /* evaluation was successful -- replace the node. */
3989         ir_type *old_tp = get_irn_type(n);
3990         int i, arity = get_irn_arity(n);
3991
3992         /*
3993          * Try to recover the type of the new expression.
3994          */
3995         for (i = 0; i < arity && !old_tp; ++i)
3996           old_tp = get_irn_type(get_irn_n(n, i));
3997
3998         n = new_Const(get_tarval_mode(tv), tv);
3999
4000         if (old_tp && get_type_mode(old_tp) == get_tarval_mode(tv))
4001           set_Const_type(n, old_tp);
4002
4003         DBG_OPT_CSTEVAL(oldn, n);
4004         return n;
4005       }
4006     }
4007   }
4008
4009   /* remove unnecessary nodes */
4010   if (get_opt_constant_folding() ||
4011       (iro == iro_Phi)  ||   /* always optimize these nodes. */
4012       (iro == iro_Id)   ||   /* ... */
4013       (iro == iro_Proj) ||   /* ... */
4014       (iro == iro_Block)  )  /* Flags tested local. */
4015     n = equivalent_node(n);
4016
4017   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
4018
4019   /** common subexpression elimination **/
4020   /* Checks whether n is already available. */
4021   /* The block input is used to distinguish different subexpressions.  Right
4022      now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
4023      subexpressions within a block. */
4024   if (get_opt_cse()) {
4025     n = identify(current_ir_graph->value_table, n);
4026   }
4027
4028   /* Some more constant expression evaluation. */
4029   iro = get_irn_opcode(n);
4030   if (get_opt_constant_folding() ||
4031       (iro == iro_Cond) ||
4032       (iro == iro_Proj))     /* Flags tested local. */
4033     n = transform_node(n);
4034
4035   /* Remove nodes with dead (Bad) input.
4036      Run always for transformation induced Bads.  */
4037   n = gigo(n);
4038
4039   /* Now we can verify the node, as it has no dead inputs any more. */
4040   irn_vrfy(n);
4041
4042   /* Now we have a legal, useful node. Enter it in hash table for cse.
4043      Blocks should be unique anyways.  (Except the successor of start:
4044      is cse with the start block!) */
4045   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
4046     n = identify_remember(current_ir_graph->value_table, n);
4047
4048   return n;
4049 }  /* optimize_in_place_2 */
4050
4051 /**
4052  * Wrapper for external use, set proper status bits after optimization.
4053  */
4054 ir_node *optimize_in_place(ir_node *n)
4055 {
4056   /* Handle graph state */
4057   assert(get_irg_phase_state(current_ir_graph) != phase_building);
4058
4059   if (get_opt_global_cse())
4060     set_irg_pinned(current_ir_graph, op_pin_state_floats);
4061   if (get_irg_outs_state(current_ir_graph) == outs_consistent)
4062     set_irg_outs_inconsistent(current_ir_graph);
4063
4064   /* FIXME: Maybe we could also test whether optimizing the node can
4065      change the control graph. */
4066   set_irg_doms_inconsistent(current_ir_graph);
4067   return optimize_in_place_2 (n);
4068 }  /* optimize_in_place */
4069
4070 /*
4071  * Sets the default operation for an ir_ops.
4072  */
4073 ir_op_ops *firm_set_default_operations(opcode code, ir_op_ops *ops)
4074 {
4075   ops = firm_set_default_computed_value(code, ops);
4076   ops = firm_set_default_equivalent_node(code, ops);
4077   ops = firm_set_default_transform_node(code, ops);
4078   ops = firm_set_default_node_cmp_attr(code, ops);
4079   ops = firm_set_default_get_type(code, ops);
4080   ops = firm_set_default_get_type_attr(code, ops);
4081   ops = firm_set_default_get_entity_attr(code, ops);
4082
4083   return ops;
4084 }  /* firm_set_default_operations */