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