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(n);
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
1663   return n;
1664 }
1665
1666 /**
1667  * Does all optimizations on nodes that must be done on it's Proj's
1668  * because of creating new nodes.
1669  *
1670  * Transform a Div/Mod/DivMod with a non-zero constant.
1671  * Removes the exceptions and routes the memory to the NoMem node.
1672  *
1673  * Optimizes jump tables by removing all impossible cases.
1674  *
1675  * Normalizes and optimizes Cmp nodes.
1676  */
1677 static ir_node *transform_node_Proj(ir_node *proj)
1678 {
1679   ir_node *n = get_Proj_pred(proj);
1680   ir_node *b;
1681   tarval *tb;
1682   long proj_nr;
1683
1684   switch (get_irn_opcode(n)) {
1685   case iro_Div:
1686     b  = get_Div_right(n);
1687     tb = value_of(b);
1688
1689     if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* div(x, c) && c != 0 */
1690       proj_nr = get_Proj_proj(proj);
1691
1692       /* this node may float */
1693       set_irn_pinned(n, op_pin_state_floats);
1694
1695       if (proj_nr == pn_Div_X_except) {
1696         /* we found an exception handler, remove it */
1697         return new_Bad();
1698       } else {
1699         /* the memory Proj can be removed */
1700         ir_node *res = get_Div_mem(n);
1701         set_Div_mem(n, get_irg_no_mem(current_ir_graph));
1702         if (proj_nr == pn_Div_M)
1703           return res;
1704       }
1705     }
1706     break;
1707   case iro_Mod:
1708     b  = get_Mod_right(n);
1709     tb = value_of(b);
1710
1711     if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* mod(x, c) && c != 0 */
1712       proj_nr = get_Proj_proj(proj);
1713
1714       /* this node may float */
1715       set_irn_pinned(n, op_pin_state_floats);
1716
1717       if (proj_nr == pn_Mod_X_except) {
1718         /* we found an exception handler, remove it */
1719         return new_Bad();
1720       } else {
1721         /* the memory Proj can be removed */
1722         ir_node *res = get_Mod_mem(n);
1723         set_Mod_mem(n, get_irg_no_mem(current_ir_graph));
1724         if (proj_nr == pn_Mod_M)
1725           return res;
1726       }
1727     }
1728     break;
1729   case iro_DivMod:
1730     b  = get_DivMod_right(n);
1731     tb = value_of(b);
1732
1733     if (tb != tarval_bad && classify_tarval(tb) != TV_CLASSIFY_NULL) { /* DivMod(x, c) && c != 0 */
1734       proj_nr = get_Proj_proj(proj);
1735
1736       /* this node may float */
1737       set_irn_pinned(n, op_pin_state_floats);
1738
1739       if (proj_nr == pn_DivMod_X_except) {
1740         /* we found an exception handler, remove it */
1741         return new_Bad();
1742       }
1743       else {
1744         /* the memory Proj can be removed */
1745         ir_node *res = get_DivMod_mem(n);
1746         set_DivMod_mem(n, get_irg_no_mem(current_ir_graph));
1747         if (proj_nr == pn_DivMod_M)
1748           return res;
1749       }
1750     }
1751     break;
1752
1753   case iro_Cond:
1754     if (get_opt_unreachable_code()) {
1755       b = get_Cond_selector(n);
1756       tb = value_of(b);
1757
1758       if (tb != tarval_bad && mode_is_int(get_tarval_mode(tb))) {
1759         /* we have a constant switch */
1760         long num = get_Proj_proj(proj);
1761
1762         if (num != get_Cond_defaultProj(n)) { /* we cannot optimize default Proj's yet */
1763           if (get_tarval_long(tb) == num) {
1764             /* Do NOT create a jump here, or we will have 2 control flow ops
1765              * in a block. This case is optimized away in optimize_cf(). */
1766             return proj;
1767           }
1768           else
1769             return new_Bad();
1770         }
1771       }
1772     }
1773     return proj;
1774
1775   case iro_Cmp:
1776     if (get_opt_reassociation()) {
1777       ir_node *left  = get_Cmp_left(n);
1778       ir_node *right = get_Cmp_right(n);
1779       ir_node *c     = NULL;
1780       tarval *tv     = NULL;
1781       int changed    = 0;
1782       ir_mode *mode  = NULL;
1783
1784       proj_nr = get_Proj_proj(proj);
1785
1786       /*
1787        * First step: normalize the compare op
1788        * by placing the constant on the right site
1789        * or moving the lower address node to the left.
1790        * We ignore the case that both are constants, then
1791        * this compare should be optimized away.
1792        */
1793       if (get_irn_op(right) == op_Const)
1794         c = right;
1795       else if (get_irn_op(left) == op_Const) {
1796         c     = left;
1797         left  = right;
1798         right = c;
1799
1800         proj_nr = get_swapped_pnc(proj_nr);
1801         changed |= 1;
1802       }
1803       else if (left > right) {
1804         ir_node *t = left;
1805
1806         left  = right;
1807         right = t;
1808
1809         proj_nr = get_swapped_pnc(proj_nr);
1810         changed |= 1;
1811       }
1812
1813       /*
1814        * Second step: Try to reduce the magnitude
1815        * of a constant. This may help to generate better code
1816        * later and may help to normalize more compares.
1817        * Of course this is only possible for integer values.
1818        */
1819       if (c) {
1820         mode = get_irn_mode(c);
1821         tv = get_Const_tarval(c);
1822
1823         if (tv != tarval_bad) {
1824           /* the following optimization is possibe on modes without Overflow
1825            * on Unary Minus or on == and !=:
1826            * -a CMP c  ==>  a swap(CMP) -c
1827            *
1828            * Beware: for two-complement Overflow may occur, so only == and != can
1829            * be optimized, see this:
1830            * -MININT < 0 =/=> MININT > 0 !!!
1831            */
1832           if (get_opt_constant_folding() && get_irn_op(left) == op_Minus &&
1833               (!mode_overflow_on_unary_Minus(mode) ||
1834                (mode_is_int(mode) && (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg)))) {
1835             left = get_Minus_op(left);
1836             tv = tarval_sub(get_tarval_null(mode), tv);
1837
1838             proj_nr = get_swapped_pnc(proj_nr);
1839             changed |= 2;
1840           }
1841
1842           /* for integer modes, we have more */
1843           if (mode_is_int(mode)) {
1844             /* Ne includes Unordered which is not possible on integers.
1845              * However, frontends often use this wrong, so fix it here */
1846             if (proj_nr == pn_Cmp_Ne) {
1847               proj_nr = pn_Cmp_Lg;
1848               set_Proj_proj(proj, proj_nr);
1849             }
1850
1851             /* c > 0 : a < c  ==>  a <= (c-1)    a >= c  ==>  a > (c-1) */
1852             if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Ge) &&
1853                 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Gt) {
1854               tv = tarval_sub(tv, get_tarval_one(mode));
1855
1856               proj_nr ^= pn_Cmp_Eq;
1857               changed |= 2;
1858             }
1859             /* c < 0 : a > c  ==>  a >= (c+1)    a <= c  ==>  a < (c+1) */
1860             else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Le) &&
1861                 tarval_cmp(tv, get_tarval_null(mode)) == pn_Cmp_Lt) {
1862               tv = tarval_add(tv, get_tarval_one(mode));
1863
1864               proj_nr ^= pn_Cmp_Eq;
1865               changed |= 2;
1866             }
1867
1868             /* the following reassociations work only for == and != */
1869
1870             /* a-b == 0  ==>  a == b,  a-b != 0  ==>  a != b */
1871             if (classify_tarval(tv) == TV_CLASSIFY_NULL && get_irn_op(left) == op_Sub) {
1872               if (proj_nr == pn_Cmp_Eq || proj_nr == pn_Cmp_Lg) {
1873                 right = get_Sub_right(left);
1874                 left  = get_Sub_left(left);
1875
1876                 tv = value_of(right);
1877                 changed = 1;
1878               }
1879             }
1880
1881             if (tv != tarval_bad) {
1882               ir_op *op = get_irn_op(left);
1883
1884               /* a-c1 == c2  ==>  a == c2+c1,  a-c1 != c2  ==>  a != c2+c1 */
1885               if (op == op_Sub) {
1886                 ir_node *c1 = get_Sub_right(left);
1887                 tarval *tv2 = value_of(c1);
1888
1889                 if (tv2 != tarval_bad) {
1890                   tv2 = tarval_add(tv, value_of(c1));
1891
1892                   if (tv2 != tarval_bad) {
1893                     left    = get_Sub_left(left);
1894                     tv      = tv2;
1895                     changed = 2;
1896                   }
1897                 }
1898               }
1899               /* a+c1 == c2  ==>  a == c2-c1,  a+c1 != c2  ==>  a != c2-c1 */
1900               else if (op == op_Add) {
1901                 ir_node *a_l = get_Add_left(left);
1902                 ir_node *a_r = get_Add_right(left);
1903                 ir_node *a;
1904                 tarval *tv2;
1905
1906                 if (get_irn_op(a_l) == op_Const) {
1907                   a = a_r;
1908                   tv2 = value_of(a_l);
1909                 }
1910                 else {
1911                   a = a_l;
1912                   tv2 = value_of(a_r);
1913                 }
1914
1915                 if (tv2 != tarval_bad) {
1916                   tv2 = tarval_sub(tv, tv2);
1917
1918                   if (tv2 != tarval_bad) {
1919                     left    = a;
1920                     tv      = tv2;
1921                     changed = 2;
1922                   }
1923                 }
1924               }
1925             }
1926           }
1927         }
1928       }
1929
1930       if (changed) {
1931         ir_node *block = get_nodes_block(n);
1932
1933         if (changed & 2)      /* need a new Const */
1934           right = new_Const(mode, tv);
1935
1936         /* create a new compare */
1937         n = new_rd_Cmp(get_irn_dbg_info(n), current_ir_graph, block,
1938               left, right);
1939
1940         set_Proj_pred(proj, n);
1941         set_Proj_proj(proj, proj_nr);
1942       }
1943     }
1944     return proj;
1945
1946   case iro_Tuple:
1947     /* should not happen, but if it does will be optimized away */
1948     break;
1949
1950   default:
1951     /* do nothing */
1952     return proj;
1953   }
1954
1955   /* we have added a Tuple, optimize it for the current Proj away */
1956   return equivalent_node_Proj(proj);
1957 }
1958
1959 /**
1960  * returns the operands of a commutative bin-op, if one operand is
1961  * a const, it is returned as the second one.
1962  */
1963 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
1964 {
1965   ir_node *op_a = get_binop_left(binop);
1966   ir_node *op_b = get_binop_right(binop);
1967
1968   assert(is_op_commutative(get_irn_op(binop)));
1969
1970   if (get_irn_op(op_a) == op_Const) {
1971     *a = op_b;
1972     *c = op_a;
1973   }
1974   else {
1975     *a = op_a;
1976     *c = op_b;
1977   }
1978 }
1979
1980 /**
1981  * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
1982  * Such pattern may arise in bitfield stores.
1983  *
1984  * value  c4                  value      c4 & c2
1985  *    AND     c3                    AND           c1 | c3
1986  *        OR     c2      ===>               OR
1987  *           AND    c1
1988  *               OR
1989  */
1990 static ir_node *transform_node_Or_bf_store(ir_node *or)
1991 {
1992   ir_node *and, *c1;
1993   ir_node *or_l, *c2;
1994   ir_node *and_l, *c3;
1995   ir_node *value, *c4;
1996   ir_node *new_and, *new_const, *block;
1997   ir_mode *mode = get_irn_mode(or);
1998
1999   tarval *tv1, *tv2, *tv3, *tv4, *tv, *n_tv4, *n_tv2;
2000
2001   get_comm_Binop_Ops(or, &and, &c1);
2002   if ((get_irn_op(c1) != op_Const) || (get_irn_op(and) != op_And))
2003     return or;
2004
2005   get_comm_Binop_Ops(and, &or_l, &c2);
2006   if ((get_irn_op(c2) != op_Const) || (get_irn_op(or_l) != op_Or))
2007     return or;
2008
2009   get_comm_Binop_Ops(or_l, &and_l, &c3);
2010   if ((get_irn_op(c3) != op_Const) || (get_irn_op(and_l) != op_And))
2011     return or;
2012
2013   get_comm_Binop_Ops(and_l, &value, &c4);
2014   if (get_irn_op(c4) != op_Const)
2015     return or;
2016
2017   /* ok, found the pattern, check for conditions */
2018   assert(mode == get_irn_mode(and));
2019   assert(mode == get_irn_mode(or_l));
2020   assert(mode == get_irn_mode(and_l));
2021
2022   tv1 = get_Const_tarval(c1);
2023   tv2 = get_Const_tarval(c2);
2024   tv3 = get_Const_tarval(c3);
2025   tv4 = get_Const_tarval(c4);
2026
2027   tv = tarval_or(tv4, tv2);
2028   if (classify_tarval(tv) != TV_CLASSIFY_ALL_ONE) {
2029     /* have at least one 0 at the same bit position */
2030     return or;
2031   }
2032
2033   n_tv4 = tarval_not(tv4);
2034   if (tv3 != tarval_and(tv3, n_tv4)) {
2035     /* bit in the or_mask is outside the and_mask */
2036     return or;
2037   }
2038
2039   n_tv2 = tarval_not(tv2);
2040   if (tv1 != tarval_and(tv1, n_tv2)) {
2041     /* bit in the or_mask is outside the and_mask */
2042     return or;
2043   }
2044
2045   /* ok, all conditions met */
2046   block = get_nodes_block(or);
2047
2048   new_and = new_r_And(current_ir_graph, block,
2049       value, new_r_Const(current_ir_graph, block, mode, tarval_and(tv4, tv2)), mode);
2050
2051   new_const = new_r_Const(current_ir_graph, block, mode, tarval_or(tv3, tv1));
2052
2053   set_Or_left(or, new_and);
2054   set_Or_right(or, new_const);
2055
2056   /* check for more */
2057   return transform_node_Or_bf_store(or);
2058 }
2059
2060 /**
2061  * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rot
2062  */
2063 static ir_node *transform_node_Or_Rot(ir_node *or)
2064 {
2065   ir_mode *mode = get_irn_mode(or);
2066   ir_node *shl, *shr, *block;
2067   ir_node *irn, *x, *c1, *c2, *v, *sub, *n;
2068   tarval *tv1, *tv2;
2069
2070   if (! mode_is_int(mode))
2071     return or;
2072
2073   shl = get_binop_left(or);
2074   shr = get_binop_right(or);
2075
2076   if (get_irn_op(shl) == op_Shr) {
2077     if (get_irn_op(shr) != op_Shl)
2078       return or;
2079
2080     irn = shl;
2081     shl = shr;
2082     shr = irn;
2083   }
2084   else if (get_irn_op(shl) != op_Shl)
2085     return or;
2086   else if (get_irn_op(shr) != op_Shr)
2087     return or;
2088
2089   x = get_Shl_left(shl);
2090   if (x != get_Shr_left(shr))
2091     return or;
2092
2093   c1 = get_Shl_right(shl);
2094   c2 = get_Shr_right(shr);
2095   if (get_irn_op(c1) == op_Const && get_irn_op(c2) == op_Const) {
2096     tv1 = get_Const_tarval(c1);
2097     if (! tarval_is_long(tv1))
2098       return or;
2099
2100     tv2 = get_Const_tarval(c2);
2101     if (! tarval_is_long(tv2))
2102       return or;
2103
2104     if (get_tarval_long(tv1) + get_tarval_long(tv2)
2105         != get_mode_size_bits(mode))
2106       return or;
2107
2108     /* yet, condition met */
2109     block = get_nodes_block(or);
2110
2111     n = new_r_Rot(current_ir_graph, block, x, c1, mode);
2112
2113     DBG_OPT_ALGSIM1(or, shl, shr, n);
2114     return n;
2115   }
2116   else if (get_irn_op(c1) == op_Sub) {
2117     v   = c2;
2118     sub = c1;
2119
2120     if (get_Sub_right(sub) != v)
2121       return or;
2122
2123     c1 = get_Sub_left(sub);
2124     if (get_irn_op(c1) != op_Const)
2125       return or;
2126
2127     tv1 = get_Const_tarval(c1);
2128     if (! tarval_is_long(tv1))
2129       return or;
2130
2131     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2132       return or;
2133
2134     /* yet, condition met */
2135     block = get_nodes_block(or);
2136
2137     /* a Rot right is not supported, so use a rot left */
2138     n =  new_r_Rot(current_ir_graph, block, x, sub, mode);
2139
2140     DBG_OPT_ALGSIM0(or, n);
2141     return n;
2142   }
2143   else if (get_irn_op(c2) == op_Sub) {
2144     v   = c1;
2145     sub = c2;
2146
2147     c1 = get_Sub_left(sub);
2148     if (get_irn_op(c1) != op_Const)
2149       return or;
2150
2151     tv1 = get_Const_tarval(c1);
2152     if (! tarval_is_long(tv1))
2153       return or;
2154
2155     if (get_tarval_long(tv1) != get_mode_size_bits(mode))
2156       return or;
2157
2158     /* yet, condition met */
2159     block = get_nodes_block(or);
2160
2161     /* a Rot Left */
2162     n = new_r_Rot(current_ir_graph, block, x, v, mode);
2163
2164     DBG_OPT_ALGSIM0(or, n);
2165     return n;
2166   }
2167
2168   return or;
2169 }
2170
2171 /**
2172  * Optimize an Or
2173  */
2174 static ir_node *transform_node_Or(ir_node *or)
2175 {
2176   or = transform_node_Or_bf_store(or);
2177   or = transform_node_Or_Rot(or);
2178
2179   return or;
2180 }
2181
2182 /* forward */
2183 static ir_node *transform_node(ir_node *n);
2184
2185 /**
2186  * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl
2187  */
2188 static ir_node *transform_node_shift(ir_node *n)
2189 {
2190   ir_node *left, *right;
2191   tarval *tv1, *tv2, *res;
2192   ir_mode *mode;
2193   int modulo_shf, flag;
2194
2195   left = get_binop_left(n);
2196
2197   /* different operations */
2198   if (get_irn_op(left) != get_irn_op(n))
2199     return n;
2200
2201   right = get_binop_right(n);
2202   tv1 = value_of(right);
2203   if (tv1 == tarval_bad)
2204     return n;
2205
2206   tv2 = value_of(get_binop_right(left));
2207   if (tv2 == tarval_bad)
2208     return n;
2209
2210   res = tarval_add(tv1, tv2);
2211
2212   /* beware: a simple replacement works only, if res < modulo shift */
2213   mode = get_irn_mode(n);
2214
2215   flag = 0;
2216
2217   modulo_shf = get_mode_modulo_shift(mode);
2218   if (modulo_shf > 0) {
2219     tarval *modulo = new_tarval_from_long(modulo_shf, get_tarval_mode(res));
2220
2221     if (tarval_cmp(res, modulo) & pn_Cmp_Lt)
2222       flag = 1;
2223   }
2224   else
2225     flag = 1;
2226
2227   if (flag) {
2228     /* ok, we can replace it */
2229     ir_node *in[2], *irn, *block = get_nodes_block(n);
2230
2231     in[0] = get_binop_left(left);
2232     in[1] = new_r_Const(current_ir_graph, block, get_tarval_mode(res), res);
2233
2234     irn = new_ir_node(NULL, current_ir_graph, block, get_irn_op(n), mode, 2, in);
2235
2236     DBG_OPT_ALGSIM0(n, irn);
2237
2238     return transform_node(irn);
2239   }
2240   return n;
2241 }
2242
2243 #define transform_node_Shr  transform_node_shift
2244 #define transform_node_Shrs transform_node_shift
2245 #define transform_node_Shl  transform_node_shift
2246
2247 /**
2248  * Remove dead blocks in keepalive list.  We do not generate a new End node.
2249  */
2250 static ir_node *transform_node_End(ir_node *n) {
2251   int i, n_keepalives = get_End_n_keepalives(n);
2252
2253   for (i = 0; i < n_keepalives; ++i) {
2254     ir_node *ka = get_End_keepalive(n, i);
2255     if (is_Block(ka) && is_Block_dead(ka))
2256       set_End_keepalive(n, i, new_Bad());
2257   }
2258   return n;
2259 }
2260
2261 /**
2262  * Optimize a Mux into some simplier cases.
2263  */
2264 static ir_node *transform_node_Mux(ir_node *n)
2265 {
2266   ir_node *oldn = n, *sel = get_Mux_sel(n);
2267   ir_mode *mode = get_irn_mode(n);
2268
2269   if (get_irn_op(sel) == op_Proj && !mode_honor_signed_zeros(mode)) {
2270     ir_node *cmp = get_Proj_pred(sel);
2271     long proj_nr = get_Proj_proj(sel);
2272     ir_node *f   =  get_Mux_false(n);
2273     ir_node *t   = get_Mux_true(n);
2274
2275     if (get_irn_op(cmp) == op_Cmp && classify_Const(get_Cmp_right(cmp)) == CNST_NULL) {
2276       ir_node *block = get_nodes_block(n);
2277
2278       /*
2279        * Note: normalization puts the constant on the right site,
2280        * so we check only one case.
2281        *
2282        * Note further that these optimization work even for floating point
2283        * with NaN's because -NaN == NaN.
2284        * However, if +0 and -0 is handled differently, we cannot use the first one.
2285        */
2286       if (get_irn_op(f) == op_Minus &&
2287           get_Minus_op(f)   == t &&
2288           get_Cmp_left(cmp) == t) {
2289
2290         if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2291           /* Mux(a >=/> 0, -a, a)  ==>  Abs(a) */
2292           n = new_rd_Abs(get_irn_dbg_info(n),
2293                 current_ir_graph,
2294                 block,
2295                 t, mode);
2296           DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2297           return n;
2298         }
2299         else if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2300           /* Mux(a <=/< 0, -a, a)  ==>  Minus(Abs(a)) */
2301           n = new_rd_Abs(get_irn_dbg_info(n),
2302                 current_ir_graph,
2303                 block,
2304                 t, mode);
2305           n = new_rd_Minus(get_irn_dbg_info(n),
2306                 current_ir_graph,
2307                 block,
2308                 n, mode);
2309
2310           DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2311           return n;
2312         }
2313       }
2314       else if (get_irn_op(t) == op_Minus &&
2315           get_Minus_op(t)   == f &&
2316           get_Cmp_left(cmp) == f) {
2317
2318         if (proj_nr == pn_Cmp_Le || proj_nr == pn_Cmp_Lt) {
2319           /* Mux(a <=/< 0, a, -a)  ==>  Abs(a) */
2320           n = new_rd_Abs(get_irn_dbg_info(n),
2321                 current_ir_graph,
2322                 block,
2323                 f, mode);
2324           DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2325           return n;
2326         }
2327         else if (proj_nr == pn_Cmp_Ge || proj_nr == pn_Cmp_Gt) {
2328           /* Mux(a >=/> 0, a, -a)  ==>  Minus(Abs(a)) */
2329           n = new_rd_Abs(get_irn_dbg_info(n),
2330                 current_ir_graph,
2331                 block,
2332                 f, mode);
2333           n = new_rd_Minus(get_irn_dbg_info(n),
2334                 current_ir_graph,
2335                 block,
2336                 n, mode);
2337
2338           DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2339           return n;
2340         }
2341       }
2342
2343       if (mode_is_int(mode) && mode_is_signed(mode) &&
2344           get_mode_arithmetic(mode) == irma_twos_complement) {
2345         ir_node *x = get_Cmp_left(cmp);
2346
2347         /* the following optimization works only with signed integer two-complement mode */
2348
2349         if (mode == get_irn_mode(x)) {
2350           /*
2351            * FIXME: this restriction is two rigid, as it would still
2352            * work if mode(x) = Hs and mode == Is, but at least it removes
2353            * all wrong cases.
2354            */
2355           if ((proj_nr == pn_Cmp_Lt || proj_nr == pn_Cmp_Le) &&
2356               classify_Const(t) == CNST_ALL_ONE &&
2357               classify_Const(f) == CNST_NULL) {
2358             /*
2359              * Mux(x:T </<= 0, 0, -1) -> Shrs(x, sizeof_bits(T) - 1)
2360              * Conditions:
2361              * T must be signed.
2362              */
2363             n = new_rd_Shrs(get_irn_dbg_info(n),
2364                   current_ir_graph, block, x,
2365                   new_r_Const_long(current_ir_graph, block, mode_Iu,
2366                     get_mode_size_bits(mode) - 1),
2367                   mode);
2368             DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2369             return n;
2370           }
2371           else if ((proj_nr == pn_Cmp_Gt || proj_nr == pn_Cmp_Ge) &&
2372                    classify_Const(t) == CNST_ONE &&
2373                    classify_Const(f) == CNST_NULL) {
2374             /*
2375              * Mux(x:T >/>= 0, 0, 1) -> Shr(-x, sizeof_bits(T) - 1)
2376              * Conditions:
2377              * T must be signed.
2378              */
2379             n = new_rd_Shr(get_irn_dbg_info(n),
2380                   current_ir_graph, block,
2381                   new_r_Minus(current_ir_graph, block, x, mode),
2382                   new_r_Const_long(current_ir_graph, block, mode_Iu,
2383                     get_mode_size_bits(mode) - 1),
2384                   mode);
2385             DBG_OPT_ALGSIM1(oldn, cmp, sel, n);
2386             return n;
2387           }
2388         }
2389       }
2390     }
2391   }
2392   return arch_transform_node_Mux(n);
2393 }
2394
2395 /**
2396  * Tries several [inplace] [optimizing] transformations and returns an
2397  * equivalent node.  The difference to equivalent_node() is that these
2398  * transformations _do_ generate new nodes, and thus the old node must
2399  * not be freed even if the equivalent node isn't the old one.
2400  */
2401 static ir_node *transform_node(ir_node *n)
2402 {
2403   if (n->op->transform_node)
2404     n = n->op->transform_node(n);
2405   return n;
2406 }
2407
2408 /**
2409  * set the default transform node operation
2410  */
2411 static ir_op *firm_set_default_transform_node(ir_op *op)
2412 {
2413 #define CASE(a)                                 \
2414   case iro_##a:                                 \
2415     op->transform_node  = transform_node_##a;   \
2416     break
2417
2418   switch (op->code) {
2419   CASE(Add);
2420   CASE(Sub);
2421   CASE(Mul);
2422   CASE(Div);
2423   CASE(Mod);
2424   CASE(DivMod);
2425   CASE(Cond);
2426   CASE(Eor);
2427   CASE(Not);
2428   CASE(Cast);
2429   CASE(Proj);
2430   CASE(Sel);
2431   CASE(Or);
2432   CASE(Shr);
2433   CASE(Shrs);
2434   CASE(Shl);
2435   CASE(End);
2436   CASE(Mux);
2437   default:
2438     op->transform_node = NULL;
2439   }
2440
2441   return op;
2442 #undef CASE
2443 }
2444
2445
2446 /* **************** Common Subexpression Elimination **************** */
2447
2448 /** The size of the hash table used, should estimate the number of nodes
2449     in a graph. */
2450 #define N_IR_NODES 512
2451
2452 /** Compares the attributes of two Const nodes. */
2453 static int node_cmp_attr_Const(ir_node *a, ir_node *b)
2454 {
2455   return (get_Const_tarval(a) != get_Const_tarval(b))
2456       || (get_Const_type(a) != get_Const_type(b));
2457 }
2458
2459 /** Compares the attributes of two Proj nodes. */
2460 static int node_cmp_attr_Proj(ir_node *a, ir_node *b)
2461 {
2462     return get_irn_proj_attr (a) != get_irn_proj_attr (b);
2463 }
2464
2465 /** Compares the attributes of two Filter nodes. */
2466 static int node_cmp_attr_Filter(ir_node *a, ir_node *b)
2467 {
2468     return get_Filter_proj(a) != get_Filter_proj(b);
2469 }
2470
2471 /** Compares the attributes of two Alloc nodes. */
2472 static int node_cmp_attr_Alloc(ir_node *a, ir_node *b)
2473 {
2474     return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
2475         || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
2476 }
2477
2478 /** Compares the attributes of two Free nodes. */
2479 static int node_cmp_attr_Free(ir_node *a, ir_node *b)
2480 {
2481     return (get_irn_free_attr(a).where != get_irn_free_attr(b).where)
2482         || (get_irn_free_attr(a).type != get_irn_free_attr(b).type);
2483 }
2484
2485 /** Compares the attributes of two SymConst nodes. */
2486 static int node_cmp_attr_SymConst(ir_node *a, ir_node *b)
2487 {
2488     return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
2489       || (get_irn_symconst_attr(a).sym.type_p != get_irn_symconst_attr(b).sym.type_p)
2490       || (get_irn_symconst_attr(a).tp != get_irn_symconst_attr(b).tp);
2491 }
2492
2493 /** Compares the attributes of two Call nodes. */
2494 static int node_cmp_attr_Call(ir_node *a, ir_node *b)
2495 {
2496     return (get_irn_call_attr(a) != get_irn_call_attr(b));
2497 }
2498
2499 /** Compares the attributes of two Sel nodes. */
2500 static int node_cmp_attr_Sel(ir_node *a, ir_node *b)
2501 {
2502     return (get_irn_sel_attr(a).ent->kind  != get_irn_sel_attr(b).ent->kind)
2503       || (get_irn_sel_attr(a).ent->name    != get_irn_sel_attr(b).ent->name)
2504       || (get_irn_sel_attr(a).ent->owner   != get_irn_sel_attr(b).ent->owner)
2505       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
2506       || (get_irn_sel_attr(a).ent->type    != get_irn_sel_attr(b).ent->type);
2507 }
2508
2509 /** Compares the attributes of two Phi nodes. */
2510 static int node_cmp_attr_Phi(ir_node *a, ir_node *b)
2511 {
2512     return get_irn_phi_attr (a) != get_irn_phi_attr (b);
2513 }
2514
2515 /** Compares the attributes of two Cast nodes. */
2516 static int node_cmp_attr_Cast(ir_node *a, ir_node *b)
2517 {
2518     return get_Cast_type(a) != get_Cast_type(b);
2519 }
2520
2521 /** Compares the attributes of two Load nodes. */
2522 static int node_cmp_attr_Load(ir_node *a, ir_node *b)
2523 {
2524   if (get_Load_volatility(a) == volatility_is_volatile ||
2525       get_Load_volatility(b) == volatility_is_volatile)
2526     /* NEVER do CSE on volatile Loads */
2527     return 1;
2528
2529   return get_Load_mode(a) != get_Load_mode(b);
2530 }
2531
2532 /** Compares the attributes of two Store nodes. */
2533 static int node_cmp_attr_Store(ir_node *a, ir_node *b)
2534 {
2535   /* NEVER do CSE on volatile Stores */
2536   return (get_Store_volatility(a) == volatility_is_volatile ||
2537       get_Store_volatility(b) == volatility_is_volatile);
2538 }
2539
2540 /**
2541  * set the default node attribute compare operation
2542  */
2543 static ir_op *firm_set_default_node_cmp_attr(ir_op *op)
2544 {
2545 #define CASE(a)                             \
2546   case iro_##a:                             \
2547     op->node_cmp_attr  = node_cmp_attr_##a; \
2548     break
2549
2550   switch (op->code) {
2551   CASE(Const);
2552   CASE(Proj);
2553   CASE(Filter);
2554   CASE(Alloc);
2555   CASE(Free);
2556   CASE(SymConst);
2557   CASE(Call);
2558   CASE(Sel);
2559   CASE(Phi);
2560   CASE(Cast);
2561   CASE(Load);
2562   CASE(Store);
2563   default:
2564     op->node_cmp_attr  = NULL;
2565   }
2566
2567   return op;
2568 #undef CASE
2569 }
2570
2571 /**
2572  * Compare function for two nodes in the hash table. Gets two
2573  * nodes as parameters.  Returns 0 if the nodes are a cse.
2574  */
2575 static int
2576 vt_cmp (const void *elt, const void *key)
2577 {
2578   ir_node *a, *b;
2579   int i, irn_arity_a;
2580
2581   a = (void *)elt;
2582   b = (void *)key;
2583
2584   if (a == b) return 0;
2585
2586   if ((get_irn_op(a) != get_irn_op(b)) ||
2587       (get_irn_mode(a) != get_irn_mode(b))) return 1;
2588
2589   /* compare if a's in and b's in are of equal length */
2590   irn_arity_a = get_irn_intra_arity (a);
2591   if (irn_arity_a != get_irn_intra_arity(b))
2592     return 1;
2593
2594   /* for block-local cse and op_pin_state_pinned nodes: */
2595   if (!get_opt_global_cse() || (get_irn_pinned(a) == op_pin_state_pinned)) {
2596     if (get_irn_intra_n(a, -1) != get_irn_intra_n(b, -1))
2597       return 1;
2598   }
2599
2600   /* compare a->in[0..ins] with b->in[0..ins] */
2601   for (i = 0; i < irn_arity_a; i++)
2602     if (get_irn_intra_n(a, i) != get_irn_intra_n(b, i))
2603       return 1;
2604
2605   /*
2606    * here, we already now that the nodes are identical except their
2607    * attributes
2608    */
2609   if (a->op->node_cmp_attr)
2610     return a->op->node_cmp_attr(a, b);
2611
2612   return 0;
2613 }
2614
2615 /*
2616  * Calculate a hash value of a node.
2617  */
2618 unsigned
2619 ir_node_hash (ir_node *node)
2620 {
2621   unsigned h;
2622   int i, irn_arity;
2623
2624   if (node->op == op_Const) {
2625     /* special value for const, as they only differ in their tarval. */
2626     h = HASH_PTR(node->attr.con.tv);
2627     h = 9*h + HASH_PTR(get_irn_mode(node));
2628   } else if (node->op == op_SymConst) {
2629     /* special value for const, as they only differ in their symbol. */
2630     h = HASH_PTR(node->attr.i.sym.type_p);
2631     h = 9*h + HASH_PTR(get_irn_mode(node));
2632   } else {
2633
2634     /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
2635     h = irn_arity = get_irn_intra_arity(node);
2636
2637     /* consider all in nodes... except the block if not a control flow. */
2638     for (i =  is_cfop(node) ? -1 : 0;  i < irn_arity;  i++) {
2639       h = 9*h + HASH_PTR(get_irn_intra_n(node, i));
2640     }
2641
2642     /* ...mode,... */
2643     h = 9*h + HASH_PTR(get_irn_mode(node));
2644     /* ...and code */
2645     h = 9*h + HASH_PTR(get_irn_op(node));
2646   }
2647
2648   return h;
2649 }
2650
2651 pset *
2652 new_identities(void) {
2653   return new_pset(vt_cmp, N_IR_NODES);
2654 }
2655
2656 void
2657 del_identities(pset *value_table) {
2658   del_pset(value_table);
2659 }
2660
2661 /**
2662  * Return the canonical node computing the same value as n.
2663  * Looks up the node in a hash table.
2664  *
2665  * For Const nodes this is performed in the constructor, too.  Const
2666  * nodes are extremely time critical because of their frequent use in
2667  * constant string arrays.
2668  */
2669 static INLINE ir_node *
2670 identify (pset *value_table, ir_node *n)
2671 {
2672   ir_node *o = NULL;
2673
2674   if (!value_table) return n;
2675
2676   if (get_opt_reassociation()) {
2677     if (is_op_commutative(get_irn_op(n))) {
2678       ir_node *l = get_binop_left(n);
2679       ir_node *r = get_binop_right(n);
2680
2681       /* for commutative operators perform  a OP b == b OP a */
2682       if (l > r) {
2683         set_binop_left(n, r);
2684         set_binop_right(n, l);
2685       }
2686     }
2687   }
2688
2689   o = pset_find (value_table, n, ir_node_hash (n));
2690   if (!o) return n;
2691
2692   DBG_OPT_CSE(n, o);
2693
2694   return o;
2695 }
2696
2697 /**
2698  * During construction we set the op_pin_state_pinned flag in the graph right when the
2699  * optimization is performed.  The flag turning on procedure global cse could
2700  * be changed between two allocations.  This way we are safe.
2701  */
2702 static INLINE ir_node *
2703 identify_cons (pset *value_table, ir_node *n) {
2704   ir_node *old = n;
2705
2706   n = identify(value_table, n);
2707   if (get_irn_n(old, -1) != get_irn_n(n, -1))
2708     set_irg_pinned(current_ir_graph, op_pin_state_floats);
2709   return n;
2710 }
2711
2712 /**
2713  * Return the canonical node computing the same value as n.
2714  * Looks up the node in a hash table, enters it in the table
2715  * if it isn't there yet.
2716  */
2717 static ir_node *
2718 identify_remember (pset *value_table, ir_node *n)
2719 {
2720   ir_node *o = NULL;
2721
2722   if (!value_table) return n;
2723
2724   if (get_opt_reassociation()) {
2725     if (is_op_commutative(get_irn_op(n))) {
2726       ir_node *l = get_binop_left(n);
2727       ir_node *r = get_binop_right(n);
2728
2729       /* for commutative operators perform  a OP b == b OP a */
2730       if (l > r) {
2731         set_binop_left(n, r);
2732         set_binop_right(n, l);
2733       }
2734     }
2735   }
2736
2737   /* lookup or insert in hash table with given hash key. */
2738   o = pset_insert (value_table, n, ir_node_hash (n));
2739
2740   if (o != n) {
2741     DBG_OPT_CSE(n, o);
2742   }
2743
2744   return o;
2745 }
2746
2747 void
2748 add_identities (pset *value_table, ir_node *node) {
2749   if (get_opt_cse() && (get_irn_opcode(node) != iro_Block))
2750     identify_remember (value_table, node);
2751 }
2752
2753 /**
2754  * garbage in, garbage out. If a node has a dead input, i.e., the
2755  * Bad node is input to the node, return the Bad node.
2756  */
2757 static INLINE ir_node *
2758 gigo (ir_node *node)
2759 {
2760   int i, irn_arity;
2761   ir_op* op = get_irn_op(node);
2762
2763   /* remove garbage blocks by looking at control flow that leaves the block
2764      and replacing the control flow by Bad. */
2765   if (get_irn_mode(node) == mode_X) {
2766     ir_node *block = get_nodes_block(node);
2767     if (!get_Block_matured(block)) return node;  /* Don't optimize nodes in immature blocks. */
2768     if (op == op_End) return node;     /* Don't optimize End, may have Bads. */
2769
2770     if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
2771       irn_arity = get_irn_arity(block);
2772       for (i = 0; i < irn_arity; i++) {
2773         if (!is_Bad(get_irn_n(block, i))) break;
2774       }
2775       if (i == irn_arity) return new_Bad();
2776     }
2777   }
2778
2779   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
2780      blocks predecessors is dead. */
2781   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
2782     irn_arity = get_irn_arity(node);
2783
2784     if (is_Block_dead(get_nodes_block(node)))
2785       return new_Bad();
2786
2787     for (i = 0; i < irn_arity; i++) {
2788       if (is_Bad(get_irn_n(node, i))) {
2789         return new_Bad();
2790       }
2791     }
2792   }
2793 #if 0
2794   /* With this code we violate the agreement that local_optimize
2795      only leaves Bads in Block, Phi and Tuple nodes. */
2796   /* If Block has only Bads as predecessors it's garbage. */
2797   /* If Phi has only Bads as predecessors it's garbage. */
2798   if ((op == op_Block && get_Block_matured(node)) || op == op_Phi)  {
2799     irn_arity = get_irn_arity(node);
2800     for (i = 0; i < irn_arity; i++) {
2801       if (!is_Bad(get_irn_n(node, i))) break;
2802     }
2803     if (i == irn_arity) node = new_Bad();
2804   }
2805 #endif
2806   return node;
2807 }
2808
2809
2810 /**
2811  * These optimizations deallocate nodes from the obstack.
2812  * It can only be called if it is guaranteed that no other nodes
2813  * reference this one, i.e., right after construction of a node.
2814  */
2815 ir_node *
2816 optimize_node (ir_node *n)
2817 {
2818         tarval *tv;
2819         ir_node *oldn = n;
2820         opcode iro = get_irn_opcode(n);
2821
2822         type *old_tp = get_irn_type(n);
2823         {
2824                 int i, arity = get_irn_arity(n);
2825                 for (i = 0; i < arity && !old_tp; ++i)
2826                         old_tp = get_irn_type(get_irn_n(n, i));
2827         }
2828
2829         /* Always optimize Phi nodes: part of the construction. */
2830         if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
2831
2832         /* constant expression evaluation / constant folding */
2833         if (get_opt_constant_folding()) {
2834                 /* constants can not be evaluated */
2835                 if (iro != iro_Const) {
2836                         /* try to evaluate */
2837                         tv = computed_value(n);
2838                         if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2839                                 ir_node *nw;
2840
2841                                 /*
2842                                  * we MUST copy the node here temporary, because it's still needed
2843                                  * for DBG_OPT_CSTEVAL
2844                                  */
2845                                 int node_size = offsetof(ir_node, attr) +  n->op->attr_size;
2846                                 oldn = alloca(node_size);
2847
2848                                 memcpy(oldn, n, node_size);
2849                                 CLONE_ARR_A(ir_node *, oldn->in, n->in);
2850
2851                                 /* ARG, copy the in array, we need it for statistics */
2852                                 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
2853
2854
2855                                 edges_node_deleted(n, current_ir_graph);
2856
2857                                 /* evaluation was successful -- replace the node. */
2858                                 obstack_free (current_ir_graph->obst, n);
2859                                 nw = new_Const (get_tarval_mode (tv), tv);
2860
2861                                 if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2862                                         set_Const_type(nw, old_tp);
2863                                 DBG_OPT_CSTEVAL(oldn, nw);
2864                                 return nw;
2865                         }
2866                 }
2867         }
2868
2869         /* remove unnecessary nodes */
2870         if (get_opt_constant_folding() ||
2871                         (iro == iro_Phi)  ||   /* always optimize these nodes. */
2872                         (iro == iro_Id)   ||
2873                         (iro == iro_Proj) ||
2874                         (iro == iro_Block)  )  /* Flags tested local. */
2875                 n = equivalent_node (n);
2876
2877         optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
2878
2879         /** common subexpression elimination **/
2880         /* Checks whether n is already available. */
2881         /* The block input is used to distinguish different subexpressions. Right
2882                  now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2883                  subexpressions within a block. */
2884         if (get_opt_cse())
2885                 n = identify_cons (current_ir_graph->value_table, n);
2886
2887         if (n != oldn) {
2888                 edges_node_deleted(oldn, current_ir_graph);
2889
2890                 /* We found an existing, better node, so we can deallocate the old node. */
2891                 obstack_free (current_ir_graph->obst, oldn);
2892
2893                 return n;
2894         }
2895
2896         /* Some more constant expression evaluation that does not allow to
2897                  free the node. */
2898         iro = get_irn_opcode(n);
2899         if (get_opt_constant_folding() ||
2900             (iro == iro_Cond) ||
2901             (iro == iro_Proj) ||
2902             (iro == iro_Sel))     /* Flags tested local. */
2903           n = transform_node (n);
2904
2905         /* Remove nodes with dead (Bad) input.
2906            Run always for transformation induced Bads. */
2907         n = gigo (n);
2908
2909         /* Now we have a legal, useful node. Enter it in hash table for cse */
2910         if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
2911           n = identify_remember (current_ir_graph->value_table, n);
2912         }
2913
2914         return n;
2915 }
2916
2917
2918 /**
2919  * These optimizations never deallocate nodes (in place).  This can cause dead
2920  * nodes lying on the obstack.  Remove these by a dead node elimination,
2921  * i.e., a copying garbage collection.
2922  */
2923 ir_node *
2924 optimize_in_place_2 (ir_node *n)
2925 {
2926   tarval *tv;
2927   ir_node *oldn = n;
2928   opcode iro = get_irn_opcode(n);
2929
2930   type *old_tp = get_irn_type(n);
2931   {
2932     int i, arity = get_irn_arity(n);
2933     for (i = 0; i < arity && !old_tp; ++i)
2934       old_tp = get_irn_type(get_irn_n(n, i));
2935   }
2936
2937   if (!get_opt_optimize() && (get_irn_op(n) != op_Phi)) return n;
2938
2939   /* if not optimize return n */
2940   if (n == NULL) {
2941     assert(0);
2942     /* Here this is possible.  Why? */
2943     return n;
2944   }
2945
2946   /* constant expression evaluation / constant folding */
2947   if (get_opt_constant_folding()) {
2948     /* constants can not be evaluated */
2949     if (iro != iro_Const) {
2950       /* try to evaluate */
2951       tv = computed_value(n);
2952       if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
2953         /* evaluation was successful -- replace the node. */
2954         n = new_Const (get_tarval_mode (tv), tv);
2955
2956     if (old_tp && get_type_mode(old_tp) == get_tarval_mode (tv))
2957       set_Const_type(n, old_tp);
2958
2959         DBG_OPT_CSTEVAL(oldn, n);
2960         return n;
2961       }
2962     }
2963   }
2964
2965   /* remove unnecessary nodes */
2966   if (get_opt_constant_folding() ||
2967       (iro == iro_Phi)  ||   /* always optimize these nodes. */
2968       (iro == iro_Id)   ||   /* ... */
2969       (iro == iro_Proj) ||   /* ... */
2970       (iro == iro_Block)  )  /* Flags tested local. */
2971     n = equivalent_node (n);
2972
2973   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
2974
2975   /** common subexpression elimination **/
2976   /* Checks whether n is already available. */
2977   /* The block input is used to distinguish different subexpressions.  Right
2978      now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
2979      subexpressions within a block. */
2980   if (get_opt_cse()) {
2981     n = identify (current_ir_graph->value_table, n);
2982   }
2983
2984   /* Some more constant expression evaluation. */
2985   iro = get_irn_opcode(n);
2986   if (get_opt_constant_folding() ||
2987       (iro == iro_Cond) ||
2988       (iro == iro_Proj) ||
2989       (iro == iro_Sel))     /* Flags tested local. */
2990     n = transform_node (n);
2991
2992   /* Remove nodes with dead (Bad) input.
2993      Run always for transformation induced Bads.  */
2994   n = gigo (n);
2995
2996   /* Now we can verify the node, as it has no dead inputs any more. */
2997   irn_vrfy(n);
2998
2999   /* Now we have a legal, useful node. Enter it in hash table for cse.
3000      Blocks should be unique anyways.  (Except the successor of start:
3001      is cse with the start block!) */
3002   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
3003     n = identify_remember (current_ir_graph->value_table, n);
3004
3005   return n;
3006 }
3007
3008 /**
3009  * Wrapper for external use, set proper status bits after optimization.
3010  */
3011 ir_node *
3012 optimize_in_place (ir_node *n)
3013 {
3014   /* Handle graph state */
3015   assert(get_irg_phase_state(current_ir_graph) != phase_building);
3016
3017   if (get_opt_global_cse())
3018     set_irg_pinned(current_ir_graph, op_pin_state_floats);
3019   if (get_irg_outs_state(current_ir_graph) == outs_consistent)
3020     set_irg_outs_inconsistent(current_ir_graph);
3021
3022   /* Maybe we could also test whether optimizing the node can
3023      change the control graph. */
3024   if (get_irg_dom_state(current_ir_graph) == dom_consistent)
3025     set_irg_dom_inconsistent(current_ir_graph);
3026   return optimize_in_place_2 (n);
3027 }
3028
3029 /**
3030  * set the default ir op operations
3031  */
3032 ir_op *firm_set_default_operations(ir_op *op)
3033 {
3034   op = firm_set_default_computed_value(op);
3035   op = firm_set_default_equivalent_node(op);
3036   op = firm_set_default_transform_node(op);
3037   op = firm_set_default_node_cmp_attr(op);
3038   op = firm_set_default_get_type(op);
3039
3040   return op;
3041 }