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