nsz Git - libfirm/blob - ir/ir/iropt.c

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