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

   1 /*
   2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   iropt --- optimizations intertwined with IR construction.
  23  * @author  Christian Schaefer, Goetz Lindenmaier, Michael Beck
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include <string.h>
  29 #include <stdbool.h>
  30
  31 #include "irnode_t.h"
  32 #include "irgraph_t.h"
  33 #include "iredges_t.h"
  34 #include "irmode_t.h"
  35 #include "iropt_t.h"
  36 #include "ircons_t.h"
  37 #include "irgmod.h"
  38 #include "irverify.h"
  39 #include "iroptimize.h"
  40 #include "tv_t.h"
  41 #include "dbginfo_t.h"
  42 #include "iropt_dbg.h"
  43 #include "irflag_t.h"
  44 #include "irhooks.h"
  45 #include "irarch.h"
  46 #include "hashptr.h"
  47 #include "opt_polymorphy.h"
  48 #include "irtools.h"
  49 #include "irhooks.h"
  50 #include "array_t.h"
  51 #include "vrp.h"
  52 #include "firm_types.h"
  53 #include "bitfiddle.h"
  54 #include "be.h"
  55
  56 /* Make types visible to allow most efficient access */
  57 #include "entity_t.h"
  58
  59 /**
  60  * Returns the tarval of a Const node or tarval_bad for all other nodes.
  61  */
  62 static ir_tarval *default_value_of(const ir_node *n)
  63 {
  64         if (is_Const(n))
  65                 return get_Const_tarval(n); /* might return tarval_bad */
  66         else
  67                 return tarval_bad;
  68 }
  69
  70 value_of_func value_of_ptr = default_value_of;
  71
  72 /* * Set a new value_of function. */
  73 void set_value_of_func(value_of_func func)
  74 {
  75         if (func != NULL)
  76                 value_of_ptr = func;
  77         else
  78                 value_of_ptr = default_value_of;
  79 }
  80
  81 /**
  82  * Return the value of a Constant.
  83  */
  84 static ir_tarval *computed_value_Const(const ir_node *n)
  85 {
  86         return get_Const_tarval(n);
  87 }  /* computed_value_Const */
  88
  89 /**
  90  * Return the value of a 'sizeof', 'alignof' or 'offsetof' SymConst.
  91  */
  92 static ir_tarval *computed_value_SymConst(const ir_node *n)
  93 {
  94         ir_type   *type;
  95         ir_entity *ent;
  96
  97         switch (get_SymConst_kind(n)) {
  98         case symconst_type_size:
  99                 type = get_SymConst_type(n);
 100                 if (get_type_state(type) == layout_fixed)
 101                         return new_tarval_from_long(get_type_size_bytes(type), get_irn_mode(n));
 102                 break;
 103         case symconst_type_align:
 104                 type = get_SymConst_type(n);
 105                 if (get_type_state(type) == layout_fixed)
 106                         return new_tarval_from_long(get_type_alignment_bytes(type), get_irn_mode(n));
 107                 break;
 108         case symconst_ofs_ent:
 109                 ent  = get_SymConst_entity(n);
 110                 type = get_entity_owner(ent);
 111                 if (get_type_state(type) == layout_fixed)
 112                         return new_tarval_from_long(get_entity_offset(ent), get_irn_mode(n));
 113                 break;
 114         default:
 115                 break;
 116         }
 117         return tarval_bad;
 118 }  /* computed_value_SymConst */
 119
 120 /**
 121  * Return the value of an Add.
 122  */
 123 static ir_tarval *computed_value_Add(const ir_node *n)
 124 {
 125         ir_node *a = get_Add_left(n);
 126         ir_node *b = get_Add_right(n);
 127
 128         ir_tarval *ta = value_of(a);
 129         ir_tarval *tb = value_of(b);
 130
 131         if ((ta != tarval_bad) && (tb != tarval_bad))
 132                 return tarval_add(ta, tb);
 133
 134         return tarval_bad;
 135 }  /* computed_value_Add */
 136
 137 /**
 138  * Return the value of a Sub.
 139  * Special case: a - a
 140  */
 141 static ir_tarval *computed_value_Sub(const ir_node *n)
 142 {
 143         ir_mode   *mode = get_irn_mode(n);
 144         ir_node   *a    = get_Sub_left(n);
 145         ir_node   *b    = get_Sub_right(n);
 146         ir_tarval *ta;
 147         ir_tarval *tb;
 148
 149         /* NaN - NaN != 0 */
 150         if (! mode_is_float(mode)) {
 151                 /* a - a = 0 */
 152                 if (a == b)
 153                         return get_mode_null(mode);
 154         }
 155
 156         ta = value_of(a);
 157         tb = value_of(b);
 158
 159         if ((ta != tarval_bad) && (tb != tarval_bad))
 160                 return tarval_sub(ta, tb, mode);
 161
 162         return tarval_bad;
 163 }  /* computed_value_Sub */
 164
 165 /**
 166  * Return the value of a Carry.
 167  * Special : a op 0, 0 op b
 168  */
 169 static ir_tarval *computed_value_Carry(const ir_node *n)
 170 {
 171         ir_node   *a  = get_binop_left(n);
 172         ir_node   *b  = get_binop_right(n);
 173         ir_mode   *m  = get_irn_mode(n);
 174         ir_tarval *ta = value_of(a);
 175         ir_tarval *tb = value_of(b);
 176
 177         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 178                 tarval_add(ta, tb);
 179                 return tarval_carry() ? get_mode_one(m) : get_mode_null(m);
 180         } else {
 181                 if (tarval_is_null(ta) || tarval_is_null(tb))
 182                         return get_mode_null(m);
 183         }
 184         return tarval_bad;
 185 }  /* computed_value_Carry */
 186
 187 /**
 188  * Return the value of a Borrow.
 189  * Special : a op 0
 190  */
 191 static ir_tarval *computed_value_Borrow(const ir_node *n)
 192 {
 193         ir_node   *a  = get_binop_left(n);
 194         ir_node   *b  = get_binop_right(n);
 195         ir_mode   *m  = get_irn_mode(n);
 196         ir_tarval *ta = value_of(a);
 197         ir_tarval *tb = value_of(b);
 198
 199         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 200                 return tarval_cmp(ta, tb) == ir_relation_less ? get_mode_one(m) : get_mode_null(m);
 201         } else if (tarval_is_null(ta)) {
 202                 return get_mode_null(m);
 203         }
 204         return tarval_bad;
 205 }  /* computed_value_Borrow */
 206
 207 /**
 208  * Return the value of an unary Minus.
 209  */
 210 static ir_tarval *computed_value_Minus(const ir_node *n)
 211 {
 212         ir_node   *a  = get_Minus_op(n);
 213         ir_tarval *ta = value_of(a);
 214
 215         if (ta != tarval_bad)
 216                 return tarval_neg(ta);
 217
 218         return tarval_bad;
 219 }  /* computed_value_Minus */
 220
 221 /**
 222  * Return the value of a Mul.
 223  */
 224 static ir_tarval *computed_value_Mul(const ir_node *n)
 225 {
 226         ir_node   *a  = get_Mul_left(n);
 227         ir_node   *b  = get_Mul_right(n);
 228         ir_tarval *ta = value_of(a);
 229         ir_tarval *tb = value_of(b);
 230         ir_mode   *mode;
 231
 232         mode = get_irn_mode(n);
 233         if (mode != get_irn_mode(a)) {
 234                 /* n * n = 2n bit multiplication */
 235                 ta = tarval_convert_to(ta, mode);
 236                 tb = tarval_convert_to(tb, mode);
 237         }
 238
 239         if (ta != tarval_bad && tb != tarval_bad) {
 240                 return tarval_mul(ta, tb);
 241         } else {
 242                 /* a * 0 != 0 if a == NaN or a == Inf */
 243                 if (!mode_is_float(mode)) {
 244                         /* a*0 = 0 or 0*b = 0 */
 245                         if (ta == get_mode_null(mode))
 246                                 return ta;
 247                         if (tb == get_mode_null(mode))
 248                                 return tb;
 249                 }
 250         }
 251         return tarval_bad;
 252 }  /* computed_value_Mul */
 253
 254 /**
 255  * Return the value of an And.
 256  * Special case: a & 0, 0 & b
 257  */
 258 static ir_tarval *computed_value_And(const ir_node *n)
 259 {
 260         ir_node   *a  = get_And_left(n);
 261         ir_node   *b  = get_And_right(n);
 262         ir_tarval *ta = value_of(a);
 263         ir_tarval *tb = value_of(b);
 264
 265         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 266                 return tarval_and (ta, tb);
 267         } else {
 268                 if (tarval_is_null(ta)) return ta;
 269                 if (tarval_is_null(tb)) return tb;
 270         }
 271         return tarval_bad;
 272 }  /* computed_value_And */
 273
 274 /**
 275  * Return the value of an Or.
 276  * Special case: a | 1...1, 1...1 | b
 277  */
 278 static ir_tarval *computed_value_Or(const ir_node *n)
 279 {
 280         ir_node   *a  = get_Or_left(n);
 281         ir_node   *b  = get_Or_right(n);
 282         ir_tarval *ta = value_of(a);
 283         ir_tarval *tb = value_of(b);
 284
 285         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 286                 return tarval_or (ta, tb);
 287         } else {
 288                 if (tarval_is_all_one(ta)) return ta;
 289                 if (tarval_is_all_one(tb)) return tb;
 290         }
 291         return tarval_bad;
 292 }  /* computed_value_Or */
 293
 294 /**
 295  * Return the value of an Eor.
 296  */
 297 static ir_tarval *computed_value_Eor(const ir_node *n)
 298 {
 299         ir_node *a = get_Eor_left(n);
 300         ir_node *b = get_Eor_right(n);
 301
 302         ir_tarval *ta, *tb;
 303
 304         if (a == b)
 305                 return get_mode_null(get_irn_mode(n));
 306
 307         ta = value_of(a);
 308         tb = value_of(b);
 309
 310         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 311                 return tarval_eor(ta, tb);
 312         }
 313         return tarval_bad;
 314 }  /* computed_value_Eor */
 315
 316 /**
 317  * Return the value of a Not.
 318  */
 319 static ir_tarval *computed_value_Not(const ir_node *n)
 320 {
 321         ir_node   *a  = get_Not_op(n);
 322         ir_tarval *ta = value_of(a);
 323
 324         if (ta != tarval_bad)
 325                 return tarval_not(ta);
 326
 327         return tarval_bad;
 328 }  /* computed_value_Not */
 329
 330 /**
 331  * Return the value of a Shl.
 332  */
 333 static ir_tarval *computed_value_Shl(const ir_node *n)
 334 {
 335         ir_node *a = get_Shl_left(n);
 336         ir_node *b = get_Shl_right(n);
 337
 338         ir_tarval *ta = value_of(a);
 339         ir_tarval *tb = value_of(b);
 340
 341         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 342                 return tarval_shl(ta, tb);
 343         }
 344         return tarval_bad;
 345 }  /* computed_value_Shl */
 346
 347 /**
 348  * Return the value of a Shr.
 349  */
 350 static ir_tarval *computed_value_Shr(const ir_node *n)
 351 {
 352         ir_node *a = get_Shr_left(n);
 353         ir_node *b = get_Shr_right(n);
 354
 355         ir_tarval *ta = value_of(a);
 356         ir_tarval *tb = value_of(b);
 357
 358         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 359                 return tarval_shr(ta, tb);
 360         }
 361         return tarval_bad;
 362 }  /* computed_value_Shr */
 363
 364 /**
 365  * Return the value of a Shrs.
 366  */
 367 static ir_tarval *computed_value_Shrs(const ir_node *n)
 368 {
 369         ir_node *a = get_Shrs_left(n);
 370         ir_node *b = get_Shrs_right(n);
 371
 372         ir_tarval *ta = value_of(a);
 373         ir_tarval *tb = value_of(b);
 374
 375         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 376                 return tarval_shrs(ta, tb);
 377         }
 378         return tarval_bad;
 379 }  /* computed_value_Shrs */
 380
 381 /**
 382  * Return the value of a Rotl.
 383  */
 384 static ir_tarval *computed_value_Rotl(const ir_node *n)
 385 {
 386         ir_node *a = get_Rotl_left(n);
 387         ir_node *b = get_Rotl_right(n);
 388
 389         ir_tarval *ta = value_of(a);
 390         ir_tarval *tb = value_of(b);
 391
 392         if ((ta != tarval_bad) && (tb != tarval_bad)) {
 393                 return tarval_rotl(ta, tb);
 394         }
 395         return tarval_bad;
 396 }  /* computed_value_Rotl */
 397
 398 /**
 399  * Return the value of a Conv.
 400  */
 401 static ir_tarval *computed_value_Conv(const ir_node *n)
 402 {
 403         ir_node *a = get_Conv_op(n);
 404         ir_tarval *ta = value_of(a);
 405
 406         if (ta != tarval_bad)
 407                 return tarval_convert_to(ta, get_irn_mode(n));
 408
 409         return tarval_bad;
 410 }  /* computed_value_Conv */
 411
 412 /**
 413  * Calculate the value of a Mux: can be evaluated, if the
 414  * sel and the right input are known.
 415  */
 416 static ir_tarval *computed_value_Mux(const ir_node *n)
 417 {
 418         ir_node *sel = get_Mux_sel(n);
 419         ir_tarval *ts = value_of(sel);
 420
 421         if (ts == get_tarval_b_true()) {
 422                 ir_node *v = get_Mux_true(n);
 423                 return value_of(v);
 424         }
 425         else if (ts == get_tarval_b_false()) {
 426                 ir_node *v = get_Mux_false(n);
 427                 return value_of(v);
 428         }
 429         return tarval_bad;
 430 }  /* computed_value_Mux */
 431
 432 /**
 433  * Calculate the value of a Confirm: can be evaluated,
 434  * if it has the form Confirm(x, '=', Const).
 435  */
 436 static ir_tarval *computed_value_Confirm(const ir_node *n)
 437 {
 438         if (get_Confirm_relation(n) == ir_relation_equal) {
 439                 ir_tarval *tv = value_of(get_Confirm_bound(n));
 440                 if (tv != tarval_bad)
 441                         return tv;
 442         }
 443         return value_of(get_Confirm_value(n));
 444 }  /* computed_value_Confirm */
 445
 446 /**
 447  * gives a (conservative) estimation of possible relation when comparing
 448  * left+right
 449  */
 450 ir_relation ir_get_possible_cmp_relations(const ir_node *left,
 451                                           const ir_node *right)
 452 {
 453         ir_relation possible = ir_relation_true;
 454         ir_tarval  *tv_l     = value_of(left);
 455         ir_tarval  *tv_r     = value_of(right);
 456         ir_mode    *mode     = get_irn_mode(left);
 457         ir_tarval  *min      = mode == mode_b ? tarval_b_false : get_mode_min(mode);
 458         ir_tarval  *max      = mode == mode_b ? tarval_b_true  : get_mode_max(mode);
 459
 460         /* both values known - evaluate them */
 461         if ((tv_l != tarval_bad) && (tv_r != tarval_bad)) {
 462                 possible = tarval_cmp(tv_l, tv_r);
 463                 /* we can return now, won't get any better */
 464                 return possible;
 465         }
 466         /* a == a is never less or greater (but might be equal or unordered) */
 467         if (left == right)
 468                 possible &= ~ir_relation_less_greater;
 469         /* unordered results only happen for float compares */
 470         if (!mode_is_float(mode))
 471                 possible &= ~ir_relation_unordered;
 472         /* values can never be less than the least representable number or
 473          * greater than the greatest representable number */
 474         if (tv_l == min)
 475                 possible &= ~ir_relation_greater;
 476         if (tv_l == max)
 477                 possible &= ~ir_relation_less;
 478         if (tv_r == max)
 479                 possible &= ~ir_relation_greater;
 480         if (tv_r == min)
 481                 possible &= ~ir_relation_less;
 482         /* maybe vrp can tell us more */
 483         possible &= vrp_cmp(left, right);
 484         /* Alloc nodes never return null (but throw an exception) */
 485         if (is_Alloc(left) && tarval_is_null(tv_r))
 486                 possible &= ~ir_relation_equal;
 487
 488         return possible;
 489 }
 490
 491 /**
 492  * Return the value of a Cmp.
 493  *
 494  * The basic idea here is to determine which relations are possible and which
 495  * one are definitely impossible.
 496  */
 497 static ir_tarval *computed_value_Cmp(const ir_node *cmp)
 498 {
 499         ir_node    *left     = get_Cmp_left(cmp);
 500         ir_node    *right    = get_Cmp_right(cmp);
 501         ir_relation possible = ir_get_possible_cmp_relations(left, right);
 502         ir_relation relation = get_Cmp_relation(cmp);
 503
 504         /* if none of the requested relations is possible, return false */
 505         if ((possible & relation) == ir_relation_false)
 506                 return tarval_b_false;
 507         /* if possible relations are a subset of the requested ones return true */
 508         if ((possible & ~relation) == ir_relation_false)
 509                 return tarval_b_true;
 510
 511         return computed_value_Cmp_Confirm(cmp, left, right, relation);
 512 }
 513
 514 /**
 515  * Calculate the value of an integer Div.
 516  * Special case: 0 / b
 517  */
 518 static ir_tarval *do_computed_value_Div(const ir_node *div)
 519 {
 520         const ir_node *a    = get_Div_left(div);
 521         const ir_node *b    = get_Div_right(div);
 522         const ir_mode *mode = get_Div_resmode(div);
 523         ir_tarval     *ta   = value_of(a);
 524         ir_tarval     *tb;
 525         const ir_node *dummy;
 526
 527         /* cannot optimize 0 / b = 0 because of NaN */
 528         if (!mode_is_float(mode)) {
 529                 if (tarval_is_null(ta) && value_not_zero(b, &dummy))
 530                         return ta;  /* 0 / b == 0 if b != 0 */
 531         }
 532         tb = value_of(b);
 533         if (ta != tarval_bad && tb != tarval_bad)
 534                 return tarval_div(ta, tb);
 535         return tarval_bad;
 536 }  /* do_computed_value_Div */
 537
 538 /**
 539  * Calculate the value of an integer Mod of two nodes.
 540  * Special case: a % 1
 541  */
 542 static ir_tarval *do_computed_value_Mod(const ir_node *a, const ir_node *b)
 543 {
 544         ir_tarval *ta = value_of(a);
 545         ir_tarval *tb = value_of(b);
 546
 547         /* Compute a % 1 or c1 % c2 */
 548         if (tarval_is_one(tb))
 549                 return get_mode_null(get_irn_mode(a));
 550         if (ta != tarval_bad && tb != tarval_bad)
 551                 return tarval_mod(ta, tb);
 552         return tarval_bad;
 553 }  /* do_computed_value_Mod */
 554
 555 /**
 556  * Return the value of a Proj(Div).
 557  */
 558 static ir_tarval *computed_value_Proj_Div(const ir_node *n)
 559 {
 560         long proj_nr = get_Proj_proj(n);
 561         if (proj_nr != pn_Div_res)
 562                 return tarval_bad;
 563
 564         return do_computed_value_Div(get_Proj_pred(n));
 565 }  /* computed_value_Proj_Div */
 566
 567 /**
 568  * Return the value of a Proj(Mod).
 569  */
 570 static ir_tarval *computed_value_Proj_Mod(const ir_node *n)
 571 {
 572         long proj_nr = get_Proj_proj(n);
 573
 574         if (proj_nr == pn_Mod_res) {
 575                 const ir_node *mod = get_Proj_pred(n);
 576                 return do_computed_value_Mod(get_Mod_left(mod), get_Mod_right(mod));
 577         }
 578         return tarval_bad;
 579 }  /* computed_value_Proj_Mod */
 580
 581 /**
 582  * Return the value of a Proj.
 583  */
 584 static ir_tarval *computed_value_Proj(const ir_node *proj)
 585 {
 586         ir_node *n = get_Proj_pred(proj);
 587
 588         if (n->op->ops.computed_value_Proj != NULL)
 589                 return n->op->ops.computed_value_Proj(proj);
 590         return tarval_bad;
 591 }  /* computed_value_Proj */
 592
 593 /**
 594  * If the parameter n can be computed, return its value, else tarval_bad.
 595  * Performs constant folding.
 596  *
 597  * @param n  The node this should be evaluated
 598  */
 599 ir_tarval *computed_value(const ir_node *n)
 600 {
 601         vrp_attr *vrp = vrp_get_info(n);
 602         if (vrp && vrp->valid && tarval_cmp(vrp->bits_set, vrp->bits_not_set) == ir_relation_equal) {
 603                 return vrp->bits_set;
 604         }
 605         if (n->op->ops.computed_value)
 606                 return n->op->ops.computed_value(n);
 607         return tarval_bad;
 608 }  /* computed_value */
 609
 610 /**
 611  * Set the default computed_value evaluator in an ir_op_ops.
 612  *
 613  * @param code   the opcode for the default operation
 614  * @param ops    the operations initialized
 615  *
 616  * @return
 617  *    The operations.
 618  */
 619 static ir_op_ops *firm_set_default_computed_value(ir_opcode code, ir_op_ops *ops)
 620 {
 621 #define CASE(a)                                        \
 622         case iro_##a:                                      \
 623                 ops->computed_value      = computed_value_##a; \
 624                 break
 625 #define CASE_PROJ(a)                                        \
 626         case iro_##a:                                           \
 627                 ops->computed_value_Proj = computed_value_Proj_##a; \
 628                 break
 629
 630         switch (code) {
 631         CASE(Add);
 632         CASE(And);
 633         CASE(Borrow);
 634         CASE(Carry);
 635         CASE(Cmp);
 636         CASE(Confirm);
 637         CASE(Const);
 638         CASE(Conv);
 639         CASE(Eor);
 640         CASE(Minus);
 641         CASE(Mul);
 642         CASE(Mux);
 643         CASE(Not);
 644         CASE(Or);
 645         CASE(Proj);
 646         CASE(Rotl);
 647         CASE(Shl);
 648         CASE(Shr);
 649         CASE(Shrs);
 650         CASE(Sub);
 651         CASE(SymConst);
 652         CASE_PROJ(Div);
 653         CASE_PROJ(Mod);
 654         default:
 655                 /* leave NULL */
 656                 break;
 657         }
 658
 659         return ops;
 660 #undef CASE_PROJ
 661 #undef CASE
 662 }  /* firm_set_default_computed_value */
 663
 664 /**
 665  * Optimize operations that are commutative and have neutral 0,
 666  * so a op 0 = 0 op a = a.
 667  */
 668 static ir_node *equivalent_node_neutral_zero(ir_node *n)
 669 {
 670         ir_node *oldn = n;
 671
 672         ir_node *a = get_binop_left(n);
 673         ir_node *b = get_binop_right(n);
 674
 675         ir_tarval *tv;
 676         ir_node *on;
 677
 678         /* After running compute_node there is only one constant predecessor.
 679            Find this predecessors value and remember the other node: */
 680         if ((tv = value_of(a)) != tarval_bad) {
 681                 on = b;
 682         } else if ((tv = value_of(b)) != tarval_bad) {
 683                 on = a;
 684         } else
 685                 return n;
 686
 687         /* If this predecessors constant value is zero, the operation is
 688          * unnecessary. Remove it.
 689          *
 690          * Beware: If n is a Add, the mode of on and n might be different
 691          * which happens in this rare construction: NULL + 3.
 692          * Then, a Conv would be needed which we cannot include here.
 693          */
 694         if (tarval_is_null(tv) && get_irn_mode(on) == get_irn_mode(n)) {
 695                 n = on;
 696
 697                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
 698         }
 699
 700         return n;
 701 }  /* equivalent_node_neutral_zero */
 702
 703 /**
 704  * Eor is commutative and has neutral 0.
 705  */
 706 static ir_node *equivalent_node_Eor(ir_node *n)
 707 {
 708         ir_node *oldn = n;
 709         ir_node *a;
 710         ir_node *b;
 711
 712         n = equivalent_node_neutral_zero(n);
 713         if (n != oldn) return n;
 714
 715         a = get_Eor_left(n);
 716         b = get_Eor_right(n);
 717
 718         if (is_Eor(a)) {
 719                 ir_node *aa = get_Eor_left(a);
 720                 ir_node *ab = get_Eor_right(a);
 721
 722                 if (aa == b) {
 723                         /* (a ^ b) ^ a -> b */
 724                         n = ab;
 725                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
 726                         return n;
 727                 } else if (ab == b) {
 728                         /* (a ^ b) ^ b -> a */
 729                         n = aa;
 730                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
 731                         return n;
 732                 }
 733         }
 734         if (is_Eor(b)) {
 735                 ir_node *ba = get_Eor_left(b);
 736                 ir_node *bb = get_Eor_right(b);
 737
 738                 if (ba == a) {
 739                         /* a ^ (a ^ b) -> b */
 740                         n = bb;
 741                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
 742                         return n;
 743                 } else if (bb == a) {
 744                         /* a ^ (b ^ a) -> b */
 745                         n = ba;
 746                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_EOR_A_B_A);
 747                         return n;
 748                 }
 749         }
 750         return n;
 751 }
 752
 753 /*
 754  * Optimize a - 0 and (a - x) + x (for modes with wrap-around).
 755  *
 756  * The second one looks strange, but this construct
 757  * is used heavily in the LCC sources :-).
 758  *
 759  * Beware: The Mode of an Add may be different than the mode of its
 760  * predecessors, so we could not return a predecessors in all cases.
 761  */
 762 static ir_node *equivalent_node_Add(ir_node *n)
 763 {
 764         ir_node *oldn = n;
 765         ir_node *left, *right;
 766         ir_mode *mode = get_irn_mode(n);
 767
 768         n = equivalent_node_neutral_zero(n);
 769         if (n != oldn)
 770                 return n;
 771
 772         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
 773         if (mode_is_float(mode)) {
 774                 ir_graph *irg = get_irn_irg(n);
 775                 if (get_irg_fp_model(irg) & fp_strict_algebraic)
 776                         return n;
 777         }
 778
 779         left  = get_Add_left(n);
 780         right = get_Add_right(n);
 781
 782         if (is_Sub(left)) {
 783                 if (get_Sub_right(left) == right) {
 784                         /* (a - x) + x */
 785
 786                         n = get_Sub_left(left);
 787                         if (mode == get_irn_mode(n)) {
 788                                 DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
 789                                 return n;
 790                         }
 791                 }
 792         }
 793         if (is_Sub(right)) {
 794                 if (get_Sub_right(right) == left) {
 795                         /* x + (a - x) */
 796
 797                         n = get_Sub_left(right);
 798                         if (mode == get_irn_mode(n)) {
 799                                 DBG_OPT_ALGSIM1(oldn, left, right, n, FS_OPT_ADD_SUB);
 800                                 return n;
 801                         }
 802                 }
 803         }
 804         return n;
 805 }  /* equivalent_node_Add */
 806
 807 /**
 808  * optimize operations that are not commutative but have neutral 0 on left,
 809  * so a op 0 = a.
 810  */
 811 static ir_node *equivalent_node_left_zero(ir_node *n)
 812 {
 813         ir_node *oldn = n;
 814
 815         ir_node   *a  = get_binop_left(n);
 816         ir_node   *b  = get_binop_right(n);
 817         ir_tarval *tb = value_of(b);
 818
 819         if (tarval_is_null(tb)) {
 820                 n = a;
 821
 822                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
 823         }
 824         return n;
 825 }  /* equivalent_node_left_zero */
 826
 827 #define equivalent_node_Shl   equivalent_node_left_zero
 828 #define equivalent_node_Shr   equivalent_node_left_zero
 829 #define equivalent_node_Shrs  equivalent_node_left_zero
 830 #define equivalent_node_Rotl  equivalent_node_left_zero
 831
 832 /**
 833  * Optimize a - 0 and (a + x) - x (for modes with wrap-around).
 834  *
 835  * The second one looks strange, but this construct
 836  * is used heavily in the LCC sources :-).
 837  *
 838  * Beware: The Mode of a Sub may be different than the mode of its
 839  * predecessors, so we could not return a predecessors in all cases.
 840  */
 841 static ir_node *equivalent_node_Sub(ir_node *n)
 842 {
 843         ir_node   *oldn = n;
 844         ir_node   *b;
 845         ir_mode   *mode = get_irn_mode(n);
 846         ir_tarval *tb;
 847
 848         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
 849         if (mode_is_float(mode)) {
 850                 ir_graph *irg = get_irn_irg(n);
 851                 if (get_irg_fp_model(irg) & fp_strict_algebraic)
 852                         return n;
 853         }
 854
 855         b  = get_Sub_right(n);
 856         tb = value_of(b);
 857
 858         /* Beware: modes might be different */
 859         if (tarval_is_null(tb)) {
 860                 ir_node *a = get_Sub_left(n);
 861                 if (mode == get_irn_mode(a)) {
 862                         n = a;
 863
 864                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_0);
 865                 }
 866         }
 867         return n;
 868 }  /* equivalent_node_Sub */
 869
 870
 871 /**
 872  * Optimize an "self-inverse unary op", ie op(op(n)) = n.
 873  *
 874  * @todo
 875  *   -(-a) == a, but might overflow two times.
 876  *   We handle it anyway here but the better way would be a
 877  *   flag. This would be needed for Pascal for instance.
 878  */
 879 static ir_node *equivalent_node_idempotent_unop(ir_node *n)
 880 {
 881         ir_node *oldn = n;
 882         ir_node *pred = get_unop_op(n);
 883
 884         /* optimize symmetric unop */
 885         if (get_irn_op(pred) == get_irn_op(n)) {
 886                 n = get_unop_op(pred);
 887                 DBG_OPT_ALGSIM2(oldn, pred, n, FS_OPT_IDEM_UNARY);
 888         }
 889         return n;
 890 }  /* equivalent_node_idempotent_unop */
 891
 892 /** Optimize Not(Not(x)) == x. */
 893 #define equivalent_node_Not    equivalent_node_idempotent_unop
 894
 895 /** -(-x) == x       ??? Is this possible or can --x raise an
 896                        out of bounds exception if min =! max? */
 897 #define equivalent_node_Minus  equivalent_node_idempotent_unop
 898
 899 /**
 900  * Optimize a * 1 = 1 * a = a.
 901  */
 902 static ir_node *equivalent_node_Mul(ir_node *n)
 903 {
 904         ir_node *oldn = n;
 905         ir_node *a = get_Mul_left(n);
 906
 907         /* we can handle here only the n * n = n bit cases */
 908         if (get_irn_mode(n) == get_irn_mode(a)) {
 909                 ir_node   *b = get_Mul_right(n);
 910                 ir_tarval *tv;
 911
 912                 /*
 913                  * Mul is commutative and has again an other neutral element.
 914                  * Constants are place right, so check this case first.
 915                  */
 916                 tv = value_of(b);
 917                 if (tarval_is_one(tv)) {
 918                         n = a;
 919                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
 920                 } else {
 921                         tv = value_of(a);
 922                         if (tarval_is_one(tv)) {
 923                                 n = b;
 924                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
 925                         }
 926                 }
 927         }
 928         return n;
 929 }  /* equivalent_node_Mul */
 930
 931 /**
 932  * Use algebraic simplification a | a = a | 0 = 0 | a = a.
 933  */
 934 static ir_node *equivalent_node_Or(ir_node *n)
 935 {
 936         ir_node *oldn = n;
 937
 938         ir_node   *a = get_Or_left(n);
 939         ir_node   *b = get_Or_right(n);
 940         ir_tarval *tv;
 941
 942         if (a == b) {
 943                 n = a;    /* idempotence */
 944                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_OR);
 945                 return n;
 946         }
 947         /* constants are normalized to right, check this side first */
 948         tv = value_of(b);
 949         if (tarval_is_null(tv)) {
 950                 n = a;
 951                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_OR);
 952                 return n;
 953         }
 954         tv = value_of(a);
 955         if (tarval_is_null(tv)) {
 956                 n = b;
 957                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_OR);
 958                 return n;
 959         }
 960
 961         return n;
 962 }  /* equivalent_node_Or */
 963
 964 /**
 965  * Optimize a & 0b1...1 = 0b1...1 & a = a & a = (a|X) & a = a.
 966  */
 967 static ir_node *equivalent_node_And(ir_node *n)
 968 {
 969         ir_node *oldn = n;
 970
 971         ir_node   *a = get_And_left(n);
 972         ir_node   *b = get_And_right(n);
 973         ir_tarval *tv;
 974
 975         if (a == b) {
 976                 n = a;    /* idempotence */
 977                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_AND);
 978                 return n;
 979         }
 980         /* constants are normalized to right, check this side first */
 981         tv = value_of(b);
 982         if (tarval_is_all_one(tv)) {
 983                 n = a;
 984                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
 985                 return n;
 986         }
 987         if (tv != get_tarval_bad()) {
 988                 ir_mode *mode = get_irn_mode(n);
 989                 if (!mode_is_signed(mode) && is_Conv(a)) {
 990                         ir_node *convop     = get_Conv_op(a);
 991                         ir_mode *convopmode = get_irn_mode(convop);
 992                         if (!mode_is_signed(convopmode)) {
 993                                 if (tarval_is_all_one(tarval_convert_to(tv, convopmode))) {
 994                                         /* Conv(X) & all_one(mode(X)) = Conv(X) */
 995                                         n = a;
 996                                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
 997                                         return n;
 998                                 }
 999                         }
1000                 }
1001         }
1002         tv = value_of(a);
1003         if (tarval_is_all_one(tv)) {
1004                 n = b;
1005                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
1006                 return n;
1007         }
1008         if (is_Or(a)) {
1009                 if (b == get_Or_left(a) || b == get_Or_right(a)) {
1010                         /* (a|X) & a */
1011                         n = b;
1012                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
1013                         return n;
1014                 }
1015         }
1016         if (is_Or(b)) {
1017                 if (a == get_Or_left(b) || a == get_Or_right(b)) {
1018                         /* a & (a|X) */
1019                         n = a;
1020                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_AND);
1021                         return n;
1022                 }
1023         }
1024         return n;
1025 }  /* equivalent_node_And */
1026
1027 /**
1028  * Try to remove useless Conv's:
1029  */
1030 static ir_node *equivalent_node_Conv(ir_node *n)
1031 {
1032         ir_node *oldn = n;
1033         ir_node *a = get_Conv_op(n);
1034
1035         ir_mode *n_mode = get_irn_mode(n);
1036         ir_mode *a_mode = get_irn_mode(a);
1037
1038 restart:
1039         if (n_mode == a_mode) { /* No Conv necessary */
1040                 if (get_Conv_strict(n)) {
1041                         ir_node *p = a;
1042
1043                         /* neither Minus nor Confirm change the precision,
1044                            so we can "look-through" */
1045                         for (;;) {
1046                                 if (is_Minus(p)) {
1047                                         p = get_Minus_op(p);
1048                                 } else if (is_Confirm(p)) {
1049                                         p = get_Confirm_value(p);
1050                                 } else {
1051                                         /* stop here */
1052                                         break;
1053                                 }
1054                         }
1055                         if (is_Conv(p) && get_Conv_strict(p)) {
1056                                 /* we known already, that a_mode == n_mode, and neither
1057                                    Minus change the mode, so the second Conv
1058                                    can be kicked */
1059                                 assert(get_irn_mode(p) == n_mode);
1060                                 n = a;
1061                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CONV);
1062                                 return n;
1063                         }
1064                         if (is_Proj(p)) {
1065                                 ir_node *pred = get_Proj_pred(p);
1066                                 if (is_Load(pred)) {
1067                                         /* Loads always return with the exact precision of n_mode */
1068                                         assert(get_Load_mode(pred) == n_mode);
1069                                         n = a;
1070                                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CONV);
1071                                         return n;
1072                                 }
1073                                 if (is_Proj(pred) && get_Proj_proj(pred) == pn_Start_T_args) {
1074                                         pred = get_Proj_pred(pred);
1075                                         if (is_Start(pred)) {
1076                                                 /* Arguments always return with the exact precision,
1077                                                    as strictConv's are place before Call -- if the
1078                                                    caller was compiled with the same setting.
1079                                                    Otherwise, the semantics is probably still right. */
1080                                                 assert(get_irn_mode(p) == n_mode);
1081                                                 n = a;
1082                                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CONV);
1083                                                 return n;
1084                                         }
1085                                 }
1086                         }
1087                         if (is_Conv(a)) {
1088                                 /* special case: the immediate predecessor is also a Conv */
1089                                 if (! get_Conv_strict(a)) {
1090                                         /* first one is not strict, kick it */
1091                                         a = get_Conv_op(a);
1092                                         a_mode = get_irn_mode(a);
1093                                         set_Conv_op(n, a);
1094                                         goto restart;
1095                                 }
1096                                 /* else both are strict conv, second is superfluous */
1097                                 n = a;
1098                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CONV);
1099                                 return n;
1100                         }
1101                 } else {
1102                         n = a;
1103                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_CONV);
1104                         return n;
1105                 }
1106         } else if (is_Conv(a)) { /* Conv(Conv(b)) */
1107                 ir_node *b      = get_Conv_op(a);
1108                 ir_mode *b_mode = get_irn_mode(b);
1109
1110                 if (get_Conv_strict(n) && get_Conv_strict(a)) {
1111                         /* both are strict conv */
1112                         if (smaller_mode(a_mode, n_mode)) {
1113                                 /* both are strict, but the first is smaller, so
1114                                    the second cannot remove more precision, remove the
1115                                    strict bit */
1116                                 set_Conv_strict(n, 0);
1117                         }
1118                 }
1119                 if (n_mode == b_mode) {
1120                         if (! get_Conv_strict(n) && ! get_Conv_strict(a)) {
1121                                 if (n_mode == mode_b) {
1122                                         n = b; /* Convb(Conv*(xxxb(...))) == xxxb(...) */
1123                                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
1124                                         return n;
1125                                 } else if (get_mode_arithmetic(n_mode) == get_mode_arithmetic(a_mode)) {
1126                                         if (values_in_mode(b_mode, a_mode)) {
1127                                                 n = b;        /* ConvS(ConvL(xxxS(...))) == xxxS(...) */
1128                                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
1129                                                 return n;
1130                                         }
1131                                 }
1132                         }
1133                         if (mode_is_int(n_mode) && get_mode_arithmetic(a_mode) == irma_ieee754) {
1134                                 /* ConvI(ConvF(I)) -> I, iff float mantissa >= int mode */
1135                                 unsigned int_mantissa   = get_mode_size_bits(n_mode) - (mode_is_signed(n_mode) ? 1 : 0);
1136                                 unsigned float_mantissa = tarval_ieee754_get_mantissa_size(a_mode);
1137
1138                                 if (float_mantissa >= int_mantissa) {
1139                                         n = b;
1140                                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
1141                                         return n;
1142                                 }
1143                         }
1144                         if (is_Conv(b)) {
1145                                 if (smaller_mode(b_mode, a_mode)) {
1146                                         if (get_Conv_strict(n))
1147                                                 set_Conv_strict(b, 1);
1148                                         n = b; /* ConvA(ConvB(ConvA(...))) == ConvA(...) */
1149                                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
1150                                         return n;
1151                                 }
1152                         }
1153                 }
1154         }
1155         return n;
1156 }  /* equivalent_node_Conv */
1157
1158 /**
1159  * - fold Phi-nodes, iff they have only one predecessor except
1160  *   themselves.
1161  */
1162 static ir_node *equivalent_node_Phi(ir_node *n)
1163 {
1164         int i, n_preds;
1165
1166         ir_node *oldn = n;
1167         ir_node *block;
1168         ir_node *first_val = NULL; /* to shutup gcc */
1169
1170         if (!get_opt_optimize() &&
1171                         get_irg_phase_state(get_irn_irg(n)) != phase_building)
1172                 return n;
1173
1174         n_preds = get_Phi_n_preds(n);
1175
1176         block = get_nodes_block(n);
1177
1178         /* Phi of dead Region without predecessors. */
1179         if (n_preds == 0)
1180                 return n;
1181
1182         /* Find first non-self-referencing input */
1183         for (i = 0; i < n_preds; ++i) {
1184                 first_val = get_Phi_pred(n, i);
1185                 /* not self pointer */
1186                 if (first_val != n) {
1187                         /* then found first value. */
1188                         break;
1189                 }
1190         }
1191
1192         /* search for rest of inputs, determine if any of these
1193         are non-self-referencing */
1194         while (++i < n_preds) {
1195                 ir_node *scnd_val = get_Phi_pred(n, i);
1196                 if (scnd_val != n && scnd_val != first_val) {
1197                         break;
1198                 }
1199         }
1200
1201         if (i >= n_preds && !is_Dummy(first_val)) {
1202                 /* Fold, if no multiple distinct non-self-referencing inputs */
1203                 n = first_val;
1204                 DBG_OPT_PHI(oldn, n);
1205         }
1206         return n;
1207 }  /* equivalent_node_Phi */
1208
1209 /**
1210  * Optimize Proj(Tuple).
1211  */
1212 static ir_node *equivalent_node_Proj_Tuple(ir_node *proj)
1213 {
1214         ir_node *oldn  = proj;
1215         ir_node *tuple = get_Proj_pred(proj);
1216
1217         /* Remove the Tuple/Proj combination. */
1218         proj = get_Tuple_pred(tuple, get_Proj_proj(proj));
1219         DBG_OPT_TUPLE(oldn, tuple, proj);
1220
1221         return proj;
1222 }  /* equivalent_node_Proj_Tuple */
1223
1224 /**
1225  * Optimize a / 1 = a.
1226  */
1227 static ir_node *equivalent_node_Proj_Div(ir_node *proj)
1228 {
1229         ir_node   *oldn = proj;
1230         ir_node   *div  = get_Proj_pred(proj);
1231         ir_node   *b    = get_Div_right(div);
1232         ir_tarval *tb   = value_of(b);
1233
1234         /* Div is not commutative. */
1235         if (tarval_is_one(tb)) { /* div(x, 1) == x */
1236                 switch (get_Proj_proj(proj)) {
1237                 case pn_Div_M:
1238                         proj = get_Div_mem(div);
1239                         DBG_OPT_ALGSIM0(oldn, proj, FS_OPT_NEUTRAL_1);
1240                         return proj;
1241
1242                 case pn_Div_res:
1243                         proj = get_Div_left(div);
1244                         DBG_OPT_ALGSIM0(oldn, proj, FS_OPT_NEUTRAL_1);
1245                         return proj;
1246
1247                 default:
1248                         /* we cannot replace the exception Proj's here, this is done in
1249                            transform_node_Proj_Div() */
1250                         return proj;
1251                 }
1252         }
1253         return proj;
1254 }  /* equivalent_node_Proj_Div */
1255
1256 /**
1257  * Optimize CopyB(mem, x, x) into a Nop.
1258  */
1259 static ir_node *equivalent_node_Proj_CopyB(ir_node *proj)
1260 {
1261         ir_node *oldn  = proj;
1262         ir_node *copyb = get_Proj_pred(proj);
1263         ir_node *a     = get_CopyB_dst(copyb);
1264         ir_node *b     = get_CopyB_src(copyb);
1265
1266         if (a == b) {
1267                 /* Turn CopyB into a tuple (mem, jmp, bad, bad) */
1268                 switch (get_Proj_proj(proj)) {
1269                 case pn_CopyB_M:
1270                         proj = get_CopyB_mem(copyb);
1271                         DBG_OPT_ALGSIM0(oldn, proj, FS_OPT_NOP);
1272                         break;
1273                 }
1274         }
1275         return proj;
1276 }  /* equivalent_node_Proj_CopyB */
1277
1278 /**
1279  * Optimize Bounds(idx, idx, upper) into idx.
1280  */
1281 static ir_node *equivalent_node_Proj_Bound(ir_node *proj)
1282 {
1283         ir_node *oldn  = proj;
1284         ir_node *bound = get_Proj_pred(proj);
1285         ir_node *idx   = get_Bound_index(bound);
1286         ir_node *pred  = skip_Proj(idx);
1287         int ret_tuple  = 0;
1288
1289         if (idx == get_Bound_lower(bound))
1290                 ret_tuple = 1;
1291         else if (is_Bound(pred)) {
1292                 /*
1293                  * idx was Bounds checked previously, it is still valid if
1294                  * lower <= pred_lower && pred_upper <= upper.
1295                  */
1296                 ir_node *lower = get_Bound_lower(bound);
1297                 ir_node *upper = get_Bound_upper(bound);
1298                 if (get_Bound_lower(pred) == lower &&
1299                         get_Bound_upper(pred) == upper) {
1300                         /*
1301                          * One could expect that we simply return the previous
1302                          * Bound here. However, this would be wrong, as we could
1303                          * add an exception Proj to a new location then.
1304                          * So, we must turn in into a tuple.
1305                          */
1306                         ret_tuple = 1;
1307                 }
1308         }
1309         if (ret_tuple) {
1310                 /* Turn Bound into a tuple (mem, jmp, bad, idx) */
1311                 switch (get_Proj_proj(proj)) {
1312                 case pn_Bound_M:
1313                         DBG_OPT_EXC_REM(proj);
1314                         proj = get_Bound_mem(bound);
1315                         break;
1316                 case pn_Bound_res:
1317                         proj = idx;
1318                         DBG_OPT_ALGSIM0(oldn, proj, FS_OPT_NOP);
1319                         break;
1320                 default:
1321                         /* cannot optimize pn_Bound_X_regular, handled in transform ... */
1322                         break;
1323                 }
1324         }
1325         return proj;
1326 }  /* equivalent_node_Proj_Bound */
1327
1328 /**
1329  * Does all optimizations on nodes that must be done on its Projs
1330  * because of creating new nodes.
1331  */
1332 static ir_node *equivalent_node_Proj(ir_node *proj)
1333 {
1334         ir_node *n = get_Proj_pred(proj);
1335         if (n->op->ops.equivalent_node_Proj)
1336                 return n->op->ops.equivalent_node_Proj(proj);
1337         return proj;
1338 }  /* equivalent_node_Proj */
1339
1340 /**
1341  * Remove Id's.
1342  */
1343 static ir_node *equivalent_node_Id(ir_node *n)
1344 {
1345         ir_node *oldn = n;
1346
1347         do {
1348                 n = get_Id_pred(n);
1349         } while (is_Id(n));
1350
1351         DBG_OPT_ID(oldn, n);
1352         return n;
1353 }  /* equivalent_node_Id */
1354
1355 /**
1356  * Optimize a Mux.
1357  */
1358 static ir_node *equivalent_node_Mux(ir_node *n)
1359 {
1360         ir_node   *oldn = n, *sel = get_Mux_sel(n);
1361         ir_node   *n_t, *n_f;
1362         ir_tarval *ts = value_of(sel);
1363
1364         /* Mux(true, f, t) == t */
1365         if (ts == tarval_b_true) {
1366                 n = get_Mux_true(n);
1367                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_C);
1368                 return n;
1369         }
1370         /* Mux(false, f, t) == f */
1371         if (ts == tarval_b_false) {
1372                 n = get_Mux_false(n);
1373                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_C);
1374                 return n;
1375         }
1376         n_t = get_Mux_true(n);
1377         n_f = get_Mux_false(n);
1378
1379         /* Mux(v, x, T) == x */
1380         if (is_Unknown(n_f)) {
1381                 n = n_t;
1382                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_EQ);
1383                 return n;
1384         }
1385         /* Mux(v, T, x) == x */
1386         if (is_Unknown(n_t)) {
1387                 n = n_f;
1388                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_EQ);
1389                 return n;
1390         }
1391
1392         /* Mux(v, x, x) == x */
1393         if (n_t == n_f) {
1394                 n = n_t;
1395                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_EQ);
1396                 return n;
1397         }
1398         if (is_Cmp(sel) && !mode_honor_signed_zeros(get_irn_mode(n))) {
1399                 ir_relation relation = get_Cmp_relation(sel);
1400                 ir_node    *f        = get_Mux_false(n);
1401                 ir_node    *t        = get_Mux_true(n);
1402
1403                 /*
1404                  * Note further that these optimization work even for floating point
1405                  * with NaN's because -NaN == NaN.
1406                  * However, if +0 and -0 is handled differently, we cannot use the first one.
1407                  */
1408                 ir_node *const cmp_l = get_Cmp_left(sel);
1409                 ir_node *const cmp_r = get_Cmp_right(sel);
1410
1411                 switch (relation) {
1412                 case ir_relation_equal:
1413                         if ((cmp_l == t && cmp_r == f) || /* Mux(t == f, t, f) -> f */
1414                                         (cmp_l == f && cmp_r == t)) { /* Mux(f == t, t, f) -> f */
1415                                 n = f;
1416                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1417                                 return n;
1418                         }
1419                         break;
1420
1421                 case ir_relation_less_greater:
1422                 case ir_relation_unordered_less_greater:
1423                         if ((cmp_l == t && cmp_r == f) || /* Mux(t != f, t, f) -> t */
1424                                         (cmp_l == f && cmp_r == t)) { /* Mux(f != t, t, f) -> t */
1425                                 n = t;
1426                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1427                                 return n;
1428                         }
1429                         break;
1430                 default:
1431                         break;
1432                 }
1433
1434                 /*
1435                  * Note: normalization puts the constant on the right side,
1436                  * so we check only one case.
1437                  */
1438                 if (cmp_l == t && tarval_is_null(value_of(cmp_r))) {
1439                         /* Mux(t CMP 0, X, t) */
1440                         if (is_Minus(f) && get_Minus_op(f) == t) {
1441                                 /* Mux(t CMP 0, -t, t) */
1442                                 if (relation == ir_relation_equal) {
1443                                         /* Mux(t == 0, -t, t)  ==>  -t */
1444                                         n = f;
1445                                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1446                                 } else if (relation == ir_relation_less_greater || relation == ir_relation_unordered_less_greater) {
1447                                         /* Mux(t != 0, -t, t)  ==> t */
1448                                         n = t;
1449                                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_TRANSFORM);
1450                                 }
1451                         }
1452                 }
1453         }
1454
1455         return n;
1456 }
1457
1458 /**
1459  * Remove Confirm nodes if setting is on.
1460  * Replace Confirms(x, '=', Constlike) by Constlike.
1461  */
1462 static ir_node *equivalent_node_Confirm(ir_node *n)
1463 {
1464         ir_node    *pred     = get_Confirm_value(n);
1465         ir_relation relation = get_Confirm_relation(n);
1466
1467         while (is_Confirm(pred) && relation == get_Confirm_relation(pred)) {
1468                 /*
1469                  * rare case: two identical Confirms one after another,
1470                  * replace the second one with the first.
1471                  */
1472                 n    = pred;
1473                 pred = get_Confirm_value(n);
1474         }
1475         return n;
1476 }
1477
1478 /**
1479  * equivalent_node() returns a node equivalent to input n. It skips all nodes that
1480  * perform no actual computation, as, e.g., the Id nodes.  It does not create
1481  * new nodes.  It is therefore safe to free n if the node returned is not n.
1482  * If a node returns a Tuple we can not just skip it.  If the size of the
1483  * in array fits, we transform n into a tuple (e.g., Div).
1484  */
1485 ir_node *equivalent_node(ir_node *n)
1486 {
1487         if (n->op->ops.equivalent_node)
1488                 return n->op->ops.equivalent_node(n);
1489         return n;
1490 }  /* equivalent_node */
1491
1492 /**
1493  * Sets the default equivalent node operation for an ir_op_ops.
1494  *
1495  * @param code   the opcode for the default operation
1496  * @param ops    the operations initialized
1497  *
1498  * @return
1499  *    The operations.
1500  */
1501 static ir_op_ops *firm_set_default_equivalent_node(ir_opcode code, ir_op_ops *ops)
1502 {
1503 #define CASE(a)                                      \
1504         case iro_##a:                                    \
1505                 ops->equivalent_node  = equivalent_node_##a; \
1506                 break
1507 #define CASE_PROJ(a)                                          \
1508         case iro_##a:                                             \
1509                 ops->equivalent_node_Proj = equivalent_node_Proj_##a; \
1510                 break
1511
1512         switch (code) {
1513         CASE(Eor);
1514         CASE(Add);
1515         CASE(Shl);
1516         CASE(Shr);
1517         CASE(Shrs);
1518         CASE(Rotl);
1519         CASE(Sub);
1520         CASE(Not);
1521         CASE(Minus);
1522         CASE(Mul);
1523         CASE(Or);
1524         CASE(And);
1525         CASE(Conv);
1526         CASE(Phi);
1527         CASE_PROJ(Tuple);
1528         CASE_PROJ(Div);
1529         CASE_PROJ(CopyB);
1530         CASE_PROJ(Bound);
1531         CASE(Proj);
1532         CASE(Id);
1533         CASE(Mux);
1534         CASE(Confirm);
1535         default:
1536                 /* leave NULL */
1537                 break;
1538         }
1539
1540         return ops;
1541 #undef CASE
1542 #undef CASE_PROJ
1543 }  /* firm_set_default_equivalent_node */
1544
1545 /**
1546  * Returns non-zero if a node is a Phi node
1547  * with all predecessors constant.
1548  */
1549 static int is_const_Phi(ir_node *n)
1550 {
1551         int i;
1552
1553         if (! is_Phi(n) || get_irn_arity(n) == 0)
1554                 return 0;
1555         for (i = get_irn_arity(n) - 1; i >= 0; --i) {
1556                 if (! is_Const(get_irn_n(n, i)))
1557                         return 0;
1558         }
1559         return 1;
1560 }  /* is_const_Phi */
1561
1562 typedef ir_tarval *(*tarval_sub_type)(ir_tarval *a, ir_tarval *b, ir_mode *mode);
1563 typedef ir_tarval *(*tarval_binop_type)(ir_tarval *a, ir_tarval *b);
1564
1565 /**
1566  * in reality eval_func should be tarval (*eval_func)() but incomplete
1567  * declarations are bad style and generate noisy warnings
1568  */
1569 typedef void (*eval_func)(void);
1570
1571 /**
1572  * Wrapper for the tarval binop evaluation, tarval_sub has one more parameter.
1573  */
1574 static ir_tarval *do_eval(eval_func eval, ir_tarval *a, ir_tarval *b, ir_mode *mode)
1575 {
1576         if (eval == (eval_func) tarval_sub) {
1577                 tarval_sub_type func = (tarval_sub_type)eval;
1578
1579                 return func(a, b, mode);
1580         } else {
1581                 tarval_binop_type func = (tarval_binop_type)eval;
1582
1583                 return func(a, b);
1584         }
1585 }
1586
1587 /**
1588  * Apply an evaluator on a binop with a constant operators (and one Phi).
1589  *
1590  * @param phi    the Phi node
1591  * @param other  the other operand
1592  * @param eval   an evaluator function
1593  * @param mode   the mode of the result, may be different from the mode of the Phi!
1594  * @param left   if non-zero, other is the left operand, else the right
1595  *
1596  * @return a new Phi node if the conversion was successful, NULL else
1597  */
1598 static ir_node *apply_binop_on_phi(ir_node *phi, ir_tarval *other, eval_func eval, ir_mode *mode, int left)
1599 {
1600         ir_tarval *tv;
1601         void      **res;
1602         ir_node   *pred;
1603         ir_graph  *irg;
1604         int       i, n = get_irn_arity(phi);
1605
1606         NEW_ARR_A(void *, res, n);
1607         if (left) {
1608                 for (i = 0; i < n; ++i) {
1609                         pred = get_irn_n(phi, i);
1610                         tv   = get_Const_tarval(pred);
1611                         tv   = do_eval(eval, other, tv, mode);
1612
1613                         if (tv == tarval_bad) {
1614                                 /* folding failed, bad */
1615                                 return NULL;
1616                         }
1617                         res[i] = tv;
1618                 }
1619         } else {
1620                 for (i = 0; i < n; ++i) {
1621                         pred = get_irn_n(phi, i);
1622                         tv   = get_Const_tarval(pred);
1623                         tv   = do_eval(eval, tv, other, mode);
1624
1625                         if (tv == tarval_bad) {
1626                                 /* folding failed, bad */
1627                                 return 0;
1628                         }
1629                         res[i] = tv;
1630                 }
1631         }
1632         irg = get_irn_irg(phi);
1633         for (i = 0; i < n; ++i) {
1634                 pred = get_irn_n(phi, i);
1635                 res[i] = new_r_Const(irg, (ir_tarval*)res[i]);
1636         }
1637         return new_r_Phi(get_nodes_block(phi), n, (ir_node **)res, mode);
1638 }  /* apply_binop_on_phi */
1639
1640 /**
1641  * Apply an evaluator on a binop with two constant Phi.
1642  *
1643  * @param a      the left Phi node
1644  * @param b      the right Phi node
1645  * @param eval   an evaluator function
1646  * @param mode   the mode of the result, may be different from the mode of the Phi!
1647  *
1648  * @return a new Phi node if the conversion was successful, NULL else
1649  */
1650 static ir_node *apply_binop_on_2_phis(ir_node *a, ir_node *b, eval_func eval, ir_mode *mode)
1651 {
1652         ir_tarval *tv_l, *tv_r, *tv;
1653         void     **res;
1654         ir_node  *pred;
1655         ir_graph *irg;
1656         int      i, n;
1657
1658         if (get_nodes_block(a) != get_nodes_block(b))
1659                 return NULL;
1660
1661         n = get_irn_arity(a);
1662         NEW_ARR_A(void *, res, n);
1663
1664         for (i = 0; i < n; ++i) {
1665                 pred = get_irn_n(a, i);
1666                 tv_l = get_Const_tarval(pred);
1667                 pred = get_irn_n(b, i);
1668                 tv_r = get_Const_tarval(pred);
1669                 tv   = do_eval(eval, tv_l, tv_r, mode);
1670
1671                 if (tv == tarval_bad) {
1672                         /* folding failed, bad */
1673                         return NULL;
1674                 }
1675                 res[i] = tv;
1676         }
1677         irg = get_irn_irg(a);
1678         for (i = 0; i < n; ++i) {
1679                 pred = get_irn_n(a, i);
1680                 res[i] = new_r_Const(irg, (ir_tarval*)res[i]);
1681         }
1682         return new_r_Phi(get_nodes_block(a), n, (ir_node **)res, mode);
1683 }  /* apply_binop_on_2_phis */
1684
1685 /**
1686  * Apply an evaluator on a unop with a constant operator (a Phi).
1687  *
1688  * @param phi    the Phi node
1689  * @param eval   an evaluator function
1690  *
1691  * @return a new Phi node if the conversion was successful, NULL else
1692  */
1693 static ir_node *apply_unop_on_phi(ir_node *phi, ir_tarval *(*eval)(ir_tarval *))
1694 {
1695         ir_tarval *tv;
1696         void     **res;
1697         ir_node  *pred;
1698         ir_mode  *mode;
1699         ir_graph *irg;
1700         int      i, n = get_irn_arity(phi);
1701
1702         NEW_ARR_A(void *, res, n);
1703         for (i = 0; i < n; ++i) {
1704                 pred = get_irn_n(phi, i);
1705                 tv   = get_Const_tarval(pred);
1706                 tv   = eval(tv);
1707
1708                 if (tv == tarval_bad) {
1709                         /* folding failed, bad */
1710                         return 0;
1711                 }
1712                 res[i] = tv;
1713         }
1714         mode = get_irn_mode(phi);
1715         irg  = get_irn_irg(phi);
1716         for (i = 0; i < n; ++i) {
1717                 pred = get_irn_n(phi, i);
1718                 res[i] = new_r_Const(irg, (ir_tarval*)res[i]);
1719         }
1720         return new_r_Phi(get_nodes_block(phi), n, (ir_node **)res, mode);
1721 }  /* apply_unop_on_phi */
1722
1723 /**
1724  * Apply a conversion on a constant operator (a Phi).
1725  *
1726  * @param phi    the Phi node
1727  *
1728  * @return a new Phi node if the conversion was successful, NULL else
1729  */
1730 static ir_node *apply_conv_on_phi(ir_node *phi, ir_mode *mode)
1731 {
1732         ir_tarval *tv;
1733         void     **res;
1734         ir_node  *pred;
1735         ir_graph *irg;
1736         int      i, n = get_irn_arity(phi);
1737
1738         NEW_ARR_A(void *, res, n);
1739         for (i = 0; i < n; ++i) {
1740                 pred = get_irn_n(phi, i);
1741                 tv   = get_Const_tarval(pred);
1742                 tv   = tarval_convert_to(tv, mode);
1743
1744                 if (tv == tarval_bad) {
1745                         /* folding failed, bad */
1746                         return 0;
1747                 }
1748                 res[i] = tv;
1749         }
1750         irg = get_irn_irg(phi);
1751         for (i = 0; i < n; ++i) {
1752                 pred = get_irn_n(phi, i);
1753                 res[i] = new_r_Const(irg, (ir_tarval*)res[i]);
1754         }
1755         return new_r_Phi(get_nodes_block(phi), n, (ir_node **)res, mode);
1756 }  /* apply_conv_on_phi */
1757
1758 /**
1759  * Transform AddP(P, ConvIs(Iu)), AddP(P, ConvIu(Is)) and
1760  * SubP(P, ConvIs(Iu)), SubP(P, ConvIu(Is)).
1761  * If possible, remove the Conv's.
1762  */
1763 static ir_node *transform_node_AddSub(ir_node *n)
1764 {
1765         ir_mode *mode = get_irn_mode(n);
1766
1767         if (mode_is_reference(mode)) {
1768                 ir_node *left     = get_binop_left(n);
1769                 ir_node *right    = get_binop_right(n);
1770                 unsigned ref_bits = get_mode_size_bits(mode);
1771
1772                 if (is_Conv(left)) {
1773                         ir_mode *lmode = get_irn_mode(left);
1774                         unsigned bits = get_mode_size_bits(lmode);
1775
1776                         if (ref_bits == bits &&
1777                             mode_is_int(lmode) &&
1778                             get_mode_arithmetic(lmode) == irma_twos_complement) {
1779                                 ir_node *pre      = get_Conv_op(left);
1780                                 ir_mode *pre_mode = get_irn_mode(pre);
1781
1782                                 if (mode_is_int(pre_mode) &&
1783                                     get_mode_size_bits(pre_mode) == bits &&
1784                                     get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1785                                         /* ok, this conv just changes to sign, moreover the calculation
1786                                          * is done with same number of bits as our address mode, so
1787                                          * we can ignore the conv as address calculation can be viewed
1788                                          * as either signed or unsigned
1789                                          */
1790                                         set_binop_left(n, pre);
1791                                 }
1792                         }
1793                 }
1794
1795                 if (is_Conv(right)) {
1796                         ir_mode *rmode = get_irn_mode(right);
1797                         unsigned bits = get_mode_size_bits(rmode);
1798
1799                         if (ref_bits == bits &&
1800                             mode_is_int(rmode) &&
1801                             get_mode_arithmetic(rmode) == irma_twos_complement) {
1802                                 ir_node *pre      = get_Conv_op(right);
1803                                 ir_mode *pre_mode = get_irn_mode(pre);
1804
1805                                 if (mode_is_int(pre_mode) &&
1806                                     get_mode_size_bits(pre_mode) == bits &&
1807                                     get_mode_arithmetic(pre_mode) == irma_twos_complement) {
1808                                         /* ok, this conv just changes to sign, moreover the calculation
1809                                          * is done with same number of bits as our address mode, so
1810                                          * we can ignore the conv as address calculation can be viewed
1811                                          * as either signed or unsigned
1812                                          */
1813                                         set_binop_right(n, pre);
1814                                 }
1815                         }
1816                 }
1817
1818                 /* let address arithmetic use unsigned modes */
1819                 if (is_Const(right)) {
1820                         ir_mode *rmode = get_irn_mode(right);
1821
1822                         if (mode_is_signed(rmode) && get_mode_arithmetic(rmode) == irma_twos_complement) {
1823                                 /* convert a AddP(P, *s) into AddP(P, *u) */
1824                                 ir_mode *nm = get_reference_mode_unsigned_eq(mode);
1825
1826                                 ir_node *pre = new_r_Conv(get_nodes_block(n), right, nm);
1827                                 set_binop_right(n, pre);
1828                         }
1829                 }
1830         }
1831
1832         return n;
1833 }  /* transform_node_AddSub */
1834
1835 #define HANDLE_BINOP_PHI(eval, a, b, c, mode)                     \
1836   do {                                                            \
1837   c = NULL;                                                       \
1838   if (is_Const(b) && is_const_Phi(a)) {                           \
1839     /* check for Op(Phi, Const) */                                \
1840     c = apply_binop_on_phi(a, get_Const_tarval(b), eval, mode, 0);\
1841   }                                                               \
1842   else if (is_Const(a) && is_const_Phi(b)) {                      \
1843     /* check for Op(Const, Phi) */                                \
1844     c = apply_binop_on_phi(b, get_Const_tarval(a), eval, mode, 1);\
1845   }                                                               \
1846   else if (is_const_Phi(a) && is_const_Phi(b)) {                  \
1847     /* check for Op(Phi, Phi) */                                  \
1848     c = apply_binop_on_2_phis(a, b, eval, mode);                  \
1849   }                                                               \
1850   if (c) {                                                        \
1851     DBG_OPT_ALGSIM0(oldn, c, FS_OPT_CONST_PHI);                   \
1852     return c;                                                     \
1853   }                                                               \
1854   } while(0)
1855
1856 #define HANDLE_UNOP_PHI(eval, a, c)               \
1857   do {                                            \
1858   c = NULL;                                       \
1859   if (is_const_Phi(a)) {                          \
1860     /* check for Op(Phi) */                       \
1861     c = apply_unop_on_phi(a, eval);               \
1862     if (c) {                                      \
1863       DBG_OPT_ALGSIM0(oldn, c, FS_OPT_CONST_PHI); \
1864       return c;                                   \
1865     }                                             \
1866   }                                               \
1867   } while(0)
1868
1869 /**
1870  * Do the AddSub optimization, then Transform
1871  *   Constant folding on Phi
1872  *   Add(a,a)          -> Mul(a, 2)
1873  *   Add(Mul(a, x), a) -> Mul(a, x+1)
1874  * if the mode is integer or float.
1875  * Transform Add(a,-b) into Sub(a,b).
1876  * Reassociation might fold this further.
1877  */
1878 static ir_node *transform_node_Add(ir_node *n)
1879 {
1880         ir_mode *mode;
1881         ir_node *a, *b, *c, *oldn = n;
1882         vrp_attr *a_vrp, *b_vrp;
1883
1884         n = transform_node_AddSub(n);
1885
1886         a = get_Add_left(n);
1887         b = get_Add_right(n);
1888
1889         mode = get_irn_mode(n);
1890
1891         if (mode_is_reference(mode)) {
1892                 ir_mode *lmode = get_irn_mode(a);
1893
1894                 if (is_Const(b) && is_Const_null(b) && mode_is_int(lmode)) {
1895                         /* an Add(a, NULL) is a hidden Conv */
1896                         dbg_info *dbg = get_irn_dbg_info(n);
1897                         return new_rd_Conv(dbg, get_nodes_block(n), a, mode);
1898                 }
1899         }
1900
1901         HANDLE_BINOP_PHI((eval_func) tarval_add, a, b, c, mode);
1902
1903         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
1904         if (mode_is_float(mode)) {
1905                 ir_graph *irg = get_irn_irg(n);
1906                 if (get_irg_fp_model(irg) & fp_strict_algebraic)
1907                         return n;
1908         }
1909
1910         if (mode_is_num(mode)) {
1911                 ir_graph *irg = get_irn_irg(n);
1912                 /* the following code leads to endless recursion when Mul are replaced by a simple instruction chain */
1913                 if (!is_irg_state(irg, IR_GRAPH_STATE_ARCH_DEP)
1914                                 && a == b && mode_is_int(mode)) {
1915                         ir_node *block = get_nodes_block(n);
1916
1917                         n = new_rd_Mul(
1918                                 get_irn_dbg_info(n),
1919                                 block,
1920                                 a,
1921                                 new_r_Const_long(irg, mode, 2),
1922                                 mode);
1923                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_A);
1924                         return n;
1925                 }
1926                 if (is_Minus(a)) {
1927                         n = new_rd_Sub(
1928                                         get_irn_dbg_info(n),
1929                                         get_nodes_block(n),
1930                                         b,
1931                                         get_Minus_op(a),
1932                                         mode);
1933                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
1934                         return n;
1935                 }
1936                 if (is_Minus(b)) {
1937                         n = new_rd_Sub(
1938                                         get_irn_dbg_info(n),
1939                                         get_nodes_block(n),
1940                                         a,
1941                                         get_Minus_op(b),
1942                                         mode);
1943                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_A_MINUS_B);
1944                         return n;
1945                 }
1946                 if (get_mode_arithmetic(mode) == irma_twos_complement) {
1947                         /* Here we rely on constants be on the RIGHT side */
1948                         if (is_Not(a)) {
1949                                 ir_node *op = get_Not_op(a);
1950
1951                                 if (is_Const(b) && is_Const_one(b)) {
1952                                         /* ~x + 1 = -x */
1953                                         ir_node *blk = get_nodes_block(n);
1954                                         n = new_rd_Minus(get_irn_dbg_info(n), blk, op, mode);
1955                                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_PLUS_1);
1956                                         return n;
1957                                 }
1958                                 if (op == b) {
1959                                         /* ~x + x = -1 */
1960                                         n = new_r_Const(irg, get_mode_minus_one(mode));
1961                                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_X_NOT_X);
1962                                         return n;
1963                                 }
1964                         }
1965                         if (is_Not(b)) {
1966                                 ir_node *op = get_Not_op(b);
1967
1968                                 if (op == a) {
1969                                         /* x + ~x = -1 */
1970                                         n = new_r_Const(irg, get_mode_minus_one(mode));
1971                                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_ADD_X_NOT_X);
1972                                         return n;
1973                                 }
1974                         }
1975                 }
1976         }
1977
1978         a_vrp = vrp_get_info(a);
1979         b_vrp = vrp_get_info(b);
1980
1981         if (a_vrp && b_vrp) {
1982                 ir_tarval *c = tarval_and(a_vrp->bits_not_set, b_vrp->bits_not_set);
1983
1984                 if (tarval_is_null(c)) {
1985                         dbg_info *dbgi  = get_irn_dbg_info(n);
1986                         return new_rd_Or(dbgi, get_nodes_block(n), a, b, mode);
1987                 }
1988         }
1989         return n;
1990 }  /* transform_node_Add */
1991
1992 /**
1993  * returns -cnst or NULL if impossible
1994  */
1995 static ir_node *const_negate(ir_node *cnst)
1996 {
1997         ir_tarval *tv    = tarval_neg(get_Const_tarval(cnst));
1998         dbg_info  *dbgi  = get_irn_dbg_info(cnst);
1999         ir_graph  *irg   = get_irn_irg(cnst);
2000         if (tv == tarval_bad) return NULL;
2001         return new_rd_Const(dbgi, irg, tv);
2002 }
2003
2004 /**
2005  * Do the AddSub optimization, then Transform
2006  *   Constant folding on Phi
2007  *   Sub(0,a)          -> Minus(a)
2008  *   Sub(Mul(a, x), a) -> Mul(a, x-1)
2009  *   Sub(Sub(x, y), b) -> Sub(x, Add(y,b))
2010  *   Sub(Add(a, x), x) -> a
2011  *   Sub(x, Add(x, a)) -> -a
2012  *   Sub(x, Const)     -> Add(x, -Const)
2013  */
2014 static ir_node *transform_node_Sub(ir_node *n)
2015 {
2016         ir_mode *mode;
2017         ir_node *oldn = n;
2018         ir_node *a, *b, *c;
2019
2020         n = transform_node_AddSub(n);
2021
2022         a = get_Sub_left(n);
2023         b = get_Sub_right(n);
2024
2025         mode = get_irn_mode(n);
2026
2027         if (mode_is_int(mode)) {
2028                 ir_mode *lmode = get_irn_mode(a);
2029
2030                 if (is_Const(b) && is_Const_null(b) && mode_is_reference(lmode)) {
2031                         /* a Sub(a, NULL) is a hidden Conv */
2032                         dbg_info *dbg = get_irn_dbg_info(n);
2033                         n = new_rd_Conv(dbg, get_nodes_block(n), a, mode);
2034                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_TO_CONV);
2035                         return n;
2036                 }
2037
2038                 if (mode == lmode                                     &&
2039                     get_mode_arithmetic(mode) == irma_twos_complement &&
2040                     is_Const(a)                                       &&
2041                     get_Const_tarval(a) == get_mode_minus_one(mode)) {
2042                         /* -1 - x -> ~x */
2043                         dbg_info *dbg = get_irn_dbg_info(n);
2044                         n = new_rd_Not(dbg, get_nodes_block(n), b, mode);
2045                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_TO_NOT);
2046                         return n;
2047                 }
2048         }
2049
2050 restart:
2051         HANDLE_BINOP_PHI((eval_func) tarval_sub, a, b, c, mode);
2052
2053         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
2054         if (mode_is_float(mode)) {
2055                 ir_graph *irg = get_irn_irg(n);
2056                 if (get_irg_fp_model(irg) & fp_strict_algebraic)
2057                         return n;
2058         }
2059
2060         if (is_Const(b) && !mode_is_reference(get_irn_mode(b))) {
2061                 /* a - C -> a + (-C) */
2062                 ir_node *cnst = const_negate(b);
2063                 if (cnst != NULL) {
2064                         ir_node  *block = get_nodes_block(n);
2065                         dbg_info *dbgi  = get_irn_dbg_info(n);
2066
2067                         n = new_rd_Add(dbgi, block, a, cnst, mode);
2068                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_TO_ADD);
2069                         return n;
2070                 }
2071         }
2072
2073         if (is_Minus(a)) { /* (-a) - b -> -(a + b) */
2074                 dbg_info *dbg   = get_irn_dbg_info(n);
2075                 ir_node  *block = get_nodes_block(n);
2076                 ir_node  *left  = get_Minus_op(a);
2077                 ir_node  *add   = new_rd_Add(dbg, block, left, b, mode);
2078
2079                 n = new_rd_Minus(dbg, block, add, mode);
2080                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_TO_ADD);
2081                 return n;
2082         } else if (is_Minus(b)) { /* a - (-b) -> a + b */
2083                 dbg_info *dbg   = get_irn_dbg_info(n);
2084                 ir_node  *block = get_nodes_block(n);
2085                 ir_node  *right = get_Minus_op(b);
2086
2087                 n = new_rd_Add(dbg, block, a, right, mode);
2088                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MINUS);
2089                 return n;
2090         } else if (is_Sub(b)) {
2091                 /* a - (b - c) -> a + (c - b)
2092                  *             -> (a - b) + c iff (b - c) is a pointer */
2093                 dbg_info *s_dbg   = get_irn_dbg_info(b);
2094                 ir_node  *s_left  = get_Sub_left(b);
2095                 ir_node  *s_right = get_Sub_right(b);
2096                 ir_mode  *s_mode  = get_irn_mode(b);
2097                 if (mode_is_reference(s_mode)) {
2098                         ir_node  *lowest_block = get_nodes_block(n); /* a and b are live here */
2099                         ir_node  *sub     = new_rd_Sub(s_dbg, lowest_block, a, s_left, mode);
2100                         dbg_info *a_dbg   = get_irn_dbg_info(n);
2101
2102                         if (s_mode != mode)
2103                                 s_right = new_r_Conv(lowest_block, s_right, mode);
2104                         n = new_rd_Add(a_dbg, lowest_block, sub, s_right, mode);
2105                 } else {
2106                         ir_node  *s_block = get_nodes_block(b);
2107                         ir_node  *sub     = new_rd_Sub(s_dbg, s_block, s_right, s_left, s_mode);
2108                         dbg_info *a_dbg   = get_irn_dbg_info(n);
2109                         ir_node  *a_block = get_nodes_block(n);
2110
2111                         n = new_rd_Add(a_dbg, a_block, a, sub, mode);
2112                 }
2113                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_TO_ADD);
2114                 return n;
2115         } else if (is_Mul(b)) { /* a - (b * C) -> a + (b * -C) */
2116                 ir_node *m_right = get_Mul_right(b);
2117                 if (is_Const(m_right)) {
2118                         ir_node *cnst2 = const_negate(m_right);
2119                         if (cnst2 != NULL) {
2120                                 dbg_info *m_dbg   = get_irn_dbg_info(b);
2121                                 ir_node  *m_block = get_nodes_block(b);
2122                                 ir_node  *m_left  = get_Mul_left(b);
2123                                 ir_mode  *m_mode  = get_irn_mode(b);
2124                                 ir_node  *mul     = new_rd_Mul(m_dbg, m_block, m_left, cnst2, m_mode);
2125                                 dbg_info *a_dbg   = get_irn_dbg_info(n);
2126                                 ir_node  *a_block = get_nodes_block(n);
2127
2128                                 n = new_rd_Add(a_dbg, a_block, a, mul, mode);
2129                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_TO_ADD);
2130                                 return n;
2131                         }
2132                 }
2133         }
2134
2135         /* Beware of Sub(P, P) which cannot be optimized into a simple Minus ... */
2136         if (mode_is_num(mode) && mode == get_irn_mode(a) && is_Const(a) && is_Const_null(a)) {
2137                 n = new_rd_Minus(
2138                                 get_irn_dbg_info(n),
2139                                 get_nodes_block(n),
2140                                 b,
2141                                 mode);
2142                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_0_A);
2143                 return n;
2144         }
2145         if (is_Add(a)) {
2146                 if (mode_wrap_around(mode)) {
2147                         ir_node *left  = get_Add_left(a);
2148                         ir_node *right = get_Add_right(a);
2149
2150                         /* FIXME: Does the Conv's work only for two complement or generally? */
2151                         if (left == b) {
2152                                 if (mode != get_irn_mode(right)) {
2153                                         /* This Sub is an effective Cast */
2154                                         right = new_r_Conv(get_nodes_block(n), right, mode);
2155                                 }
2156                                 n = right;
2157                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
2158                                 return n;
2159                         } else if (right == b) {
2160                                 if (mode != get_irn_mode(left)) {
2161                                         /* This Sub is an effective Cast */
2162                                         left = new_r_Conv(get_nodes_block(n), left, mode);
2163                                 }
2164                                 n = left;
2165                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
2166                                 return n;
2167                         }
2168                 }
2169         }
2170         if (is_Add(b)) {
2171                 if (mode_wrap_around(mode)) {
2172                         ir_node *left  = get_Add_left(b);
2173                         ir_node *right = get_Add_right(b);
2174
2175                         /* FIXME: Does the Conv's work only for two complement or generally? */
2176                         if (left == a) {
2177                                 ir_mode *r_mode = get_irn_mode(right);
2178
2179                                 n = new_r_Minus(get_nodes_block(n), right, r_mode);
2180                                 if (mode != r_mode) {
2181                                         /* This Sub is an effective Cast */
2182                                         n = new_r_Conv(get_nodes_block(n), n, mode);
2183                                 }
2184                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
2185                                 return n;
2186                         } else if (right == a) {
2187                                 ir_mode *l_mode = get_irn_mode(left);
2188
2189                                 n = new_r_Minus(get_nodes_block(n), left, l_mode);
2190                                 if (mode != l_mode) {
2191                                         /* This Sub is an effective Cast */
2192                                         n = new_r_Conv(get_nodes_block(n), n, mode);
2193                                 }
2194                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_SUB);
2195                                 return n;
2196                         }
2197                 }
2198         }
2199         if (mode_is_int(mode) && is_Conv(a) && is_Conv(b)) {
2200                 ir_mode *mode = get_irn_mode(a);
2201
2202                 if (mode == get_irn_mode(b)) {
2203                         ir_mode *ma, *mb;
2204                         ir_node *op_a = get_Conv_op(a);
2205                         ir_node *op_b = get_Conv_op(b);
2206
2207                         /* check if it's allowed to skip the conv */
2208                         ma = get_irn_mode(op_a);
2209                         mb = get_irn_mode(op_b);
2210
2211                         if (mode_is_reference(ma) && mode_is_reference(mb)) {
2212                                 /* SubInt(ConvInt(aP), ConvInt(bP)) -> SubInt(aP,bP) */
2213                                 a = op_a; b = op_b;
2214                                 set_Sub_left(n, a);
2215                                 set_Sub_right(n, b);
2216
2217                                 goto restart;
2218                         }
2219                 }
2220         }
2221         /* do NOT execute this code if reassociation is enabled, it does the inverse! */
2222         if (!is_reassoc_running() && is_Mul(a)) {
2223                 ir_node *ma = get_Mul_left(a);
2224                 ir_node *mb = get_Mul_right(a);
2225
2226                 if (ma == b) {
2227                         ir_node  *blk = get_nodes_block(n);
2228                         ir_graph *irg = get_irn_irg(n);
2229                         n = new_rd_Mul(
2230                                         get_irn_dbg_info(n),
2231                                         blk,
2232                                         ma,
2233                                         new_rd_Sub(
2234                                                 get_irn_dbg_info(n),
2235                                                 blk,
2236                                                 mb,
2237                                                 new_r_Const(irg, get_mode_one(mode)),
2238                                                 mode),
2239                                         mode);
2240                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
2241                         return n;
2242                 } else if (mb == b) {
2243                         ir_node  *blk = get_nodes_block(n);
2244                         ir_graph *irg = get_irn_irg(n);
2245                         n = new_rd_Mul(
2246                                         get_irn_dbg_info(n),
2247                                         blk,
2248                                         mb,
2249                                         new_rd_Sub(
2250                                                 get_irn_dbg_info(n),
2251                                                 blk,
2252                                                 ma,
2253                                                 new_r_Const(irg, get_mode_one(mode)),
2254                                                 mode),
2255                                         mode);
2256                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_MUL_A_X_A);
2257                         return n;
2258                 }
2259         }
2260         if (is_Sub(a)) { /* (x - y) - b -> x - (y + b) */
2261                 ir_node *x        = get_Sub_left(a);
2262                 ir_node *y        = get_Sub_right(a);
2263                 ir_node *blk      = get_nodes_block(n);
2264                 ir_mode *m_b      = get_irn_mode(b);
2265                 ir_mode *m_y      = get_irn_mode(y);
2266                 ir_mode *add_mode;
2267                 ir_node *add;
2268
2269                 /* Determine the right mode for the Add. */
2270                 if (m_b == m_y)
2271                         add_mode = m_b;
2272                 else if (mode_is_reference(m_b))
2273                         add_mode = m_b;
2274                 else if (mode_is_reference(m_y))
2275                         add_mode = m_y;
2276                 else {
2277                         /*
2278                          * Both modes are different but none is reference,
2279                          * happens for instance in SubP(SubP(P, Iu), Is).
2280                          * We have two possibilities here: Cast or ignore.
2281                          * Currently we ignore this case.
2282                          */
2283                         return n;
2284                 }
2285
2286                 add = new_r_Add(blk, y, b, add_mode);
2287
2288                 n = new_rd_Sub(get_irn_dbg_info(n), blk, x, add, mode);
2289                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_SUB_X_Y_Z);
2290                 return n;
2291         }
2292
2293         if (get_mode_arithmetic(mode) == irma_twos_complement) {
2294                 if (is_Const(a) && is_Not(b)) {
2295                         /* c - ~X = X + (c+1) */
2296                         ir_tarval *tv = get_Const_tarval(a);
2297
2298                         tv = tarval_add(tv, get_mode_one(mode));
2299                         if (tv != tarval_bad) {
2300                                 ir_node  *blk = get_nodes_block(n);
2301                                 ir_graph *irg = get_irn_irg(n);
2302                                 ir_node *c = new_r_Const(irg, tv);
2303                                 n = new_rd_Add(get_irn_dbg_info(n), blk, get_Not_op(b), c, mode);
2304                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_SUB_C_NOT_X);
2305                                 return n;
2306                         }
2307                 }
2308         }
2309         return n;
2310 }  /* transform_node_Sub */
2311
2312 /**
2313  * Several transformation done on n*n=2n bits mul.
2314  * These transformations must be done here because new nodes may be produced.
2315  */
2316 static ir_node *transform_node_Mul2n(ir_node *n, ir_mode *mode)
2317 {
2318         ir_node   *oldn  = n;
2319         ir_node   *a     = get_Mul_left(n);
2320         ir_node   *b     = get_Mul_right(n);
2321         ir_tarval *ta    = value_of(a);
2322         ir_tarval *tb    = value_of(b);
2323         ir_mode   *smode = get_irn_mode(a);
2324
2325         if (ta == get_mode_one(smode)) {
2326                 /* (L)1 * (L)b = (L)b */
2327                 ir_node *blk = get_nodes_block(n);
2328                 n = new_rd_Conv(get_irn_dbg_info(n), blk, b, mode);
2329                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
2330                 return n;
2331         }
2332         else if (ta == get_mode_minus_one(smode)) {
2333                 /* (L)-1 * (L)b = (L)b */
2334                 ir_node *blk = get_nodes_block(n);
2335                 n = new_rd_Minus(get_irn_dbg_info(n), blk, b, smode);
2336                 n = new_rd_Conv(get_irn_dbg_info(n), blk, n, mode);
2337                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS_1);
2338                 return n;
2339         }
2340         if (tb == get_mode_one(smode)) {
2341                 /* (L)a * (L)1 = (L)a */
2342                 ir_node *blk = get_irn_n(a, -1);
2343                 n = new_rd_Conv(get_irn_dbg_info(n), blk, a, mode);
2344                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_NEUTRAL_1);
2345                 return n;
2346         }
2347         else if (tb == get_mode_minus_one(smode)) {
2348                 /* (L)a * (L)-1 = (L)-a */
2349                 ir_node *blk = get_nodes_block(n);
2350                 n = new_rd_Minus(get_irn_dbg_info(n), blk, a, smode);
2351                 n = new_rd_Conv(get_irn_dbg_info(n), blk, n, mode);
2352                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS_1);
2353                 return n;
2354         }
2355         return n;
2356 }
2357
2358 /**
2359  * Transform Mul(a,-1) into -a.
2360  * Do constant evaluation of Phi nodes.
2361  * Do architecture dependent optimizations on Mul nodes
2362  */
2363 static ir_node *transform_node_Mul(ir_node *n)
2364 {
2365         ir_node *c, *oldn = n;
2366         ir_mode *mode = get_irn_mode(n);
2367         ir_node *a = get_Mul_left(n);
2368         ir_node *b = get_Mul_right(n);
2369
2370         if (is_Bad(a) || is_Bad(b))
2371                 return n;
2372
2373         if (mode != get_irn_mode(a))
2374                 return transform_node_Mul2n(n, mode);
2375
2376         HANDLE_BINOP_PHI((eval_func) tarval_mul, a, b, c, mode);
2377
2378         if (mode_is_signed(mode)) {
2379                 ir_node *r = NULL;
2380
2381                 if (value_of(a) == get_mode_minus_one(mode))
2382                         r = b;
2383                 else if (value_of(b) == get_mode_minus_one(mode))
2384                         r = a;
2385                 if (r) {
2386                         n = new_rd_Minus(get_irn_dbg_info(n), get_nodes_block(n), r, mode);
2387                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS_1);
2388                         return n;
2389                 }
2390         }
2391         if (is_Minus(a)) {
2392                 if (is_Const(b)) { /* (-a) * const -> a * -const */
2393                         ir_node *cnst = const_negate(b);
2394                         if (cnst != NULL) {
2395                                 dbg_info *dbgi  = get_irn_dbg_info(n);
2396                                 ir_node  *block = get_nodes_block(n);
2397                                 n = new_rd_Mul(dbgi, block, get_Minus_op(a), cnst, mode);
2398                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS_1);
2399                                 return n;
2400                         }
2401                 } else if (is_Minus(b)) { /* (-a) * (-b) -> a * b */
2402                         dbg_info *dbgi  = get_irn_dbg_info(n);
2403                         ir_node  *block = get_nodes_block(n);
2404                         n = new_rd_Mul(dbgi, block, get_Minus_op(a), get_Minus_op(b), mode);
2405                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS_MINUS);
2406                         return n;
2407                 } else if (is_Sub(b)) { /* (-a) * (b - c) -> a * (c - b) */
2408                         ir_node  *sub_l = get_Sub_left(b);
2409                         ir_node  *sub_r = get_Sub_right(b);
2410                         dbg_info *dbgi  = get_irn_dbg_info(n);
2411                         ir_node  *block = get_nodes_block(n);
2412                         ir_node  *new_b = new_rd_Sub(dbgi, block, sub_r, sub_l, mode);
2413                         n = new_rd_Mul(dbgi, block, get_Minus_op(a), new_b, mode);
2414                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS);
2415                         return n;
2416                 }
2417         } else if (is_Minus(b)) {
2418                 if (is_Sub(a)) { /* (a - b) * (-c) -> (b - a) * c */
2419                         ir_node  *sub_l = get_Sub_left(a);
2420                         ir_node  *sub_r = get_Sub_right(a);
2421                         dbg_info *dbgi  = get_irn_dbg_info(n);
2422                         ir_node  *block = get_nodes_block(n);
2423                         ir_node  *new_a = new_rd_Sub(dbgi, block, sub_r, sub_l, mode);
2424                         n = new_rd_Mul(dbgi, block, new_a, get_Minus_op(b), mode);
2425                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_MINUS);
2426                         return n;
2427                 }
2428         } else if (is_Shl(a)) {
2429                 ir_node *const shl_l = get_Shl_left(a);
2430                 if (is_Const(shl_l) && is_Const_one(shl_l)) {
2431                         /* (1 << x) * b -> b << x */
2432                         dbg_info *const dbgi  = get_irn_dbg_info(n);
2433                         ir_node  *const block = get_nodes_block(n);
2434                         ir_node  *const shl_r = get_Shl_right(a);
2435                         n = new_rd_Shl(dbgi, block, b, shl_r, mode);
2436                         // TODO add me DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_SHIFT);
2437                         return n;
2438                 }
2439         } else if (is_Shl(b)) {
2440                 ir_node *const shl_l = get_Shl_left(b);
2441                 if (is_Const(shl_l) && is_Const_one(shl_l)) {
2442                         /* a * (1 << x) -> a << x */
2443                         dbg_info *const dbgi  = get_irn_dbg_info(n);
2444                         ir_node  *const block = get_nodes_block(n);
2445                         ir_node  *const shl_r = get_Shl_right(b);
2446                         n = new_rd_Shl(dbgi, block, a, shl_r, mode);
2447                         // TODO add me DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_MUL_SHIFT);
2448                         return n;
2449                 }
2450         }
2451         if (get_mode_arithmetic(mode) == irma_ieee754) {
2452                 if (is_Const(a)) {
2453                         ir_tarval *tv = get_Const_tarval(a);
2454                         if (tarval_ieee754_get_exponent(tv) == 1 && tarval_ieee754_zero_mantissa(tv)
2455                                         && !tarval_is_negative(tv)) {
2456                                 /* 2.0 * b = b + b */
2457                                 n = new_rd_Add(get_irn_dbg_info(n), get_nodes_block(n), b, b, mode);
2458                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_A_A);
2459                                 return n;
2460                         }
2461                 }
2462                 else if (is_Const(b)) {
2463                         ir_tarval *tv = get_Const_tarval(b);
2464                         if (tarval_ieee754_get_exponent(tv) == 1 && tarval_ieee754_zero_mantissa(tv)
2465                                         && !tarval_is_negative(tv)) {
2466                                 /* a * 2.0 = a + a */
2467                                 n = new_rd_Add(get_irn_dbg_info(n), get_nodes_block(n), a, a, mode);
2468                                 DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_ADD_A_A);
2469                                 return n;
2470                         }
2471                 }
2472         }
2473         return arch_dep_replace_mul_with_shifts(n);
2474 }  /* transform_node_Mul */
2475
2476 /**
2477  * Transform a Div Node.
2478  */
2479 static ir_node *transform_node_Div(ir_node *n)
2480 {
2481         ir_mode *mode = get_Div_resmode(n);
2482         ir_node *a = get_Div_left(n);
2483         ir_node *b = get_Div_right(n);
2484         ir_node *value = n;
2485         const ir_node *dummy;
2486
2487         if (mode_is_int(mode)) {
2488                 if (is_Const(b) && is_const_Phi(a)) {
2489                         /* check for Div(Phi, Const) */
2490                         value = apply_binop_on_phi(a, get_Const_tarval(b), (eval_func) tarval_div, mode, 0);
2491                         if (value) {
2492                                 DBG_OPT_ALGSIM0(n, value, FS_OPT_CONST_PHI);
2493                                 goto make_tuple;
2494                         }
2495                 } else if (is_Const(a) && is_const_Phi(b)) {
2496                         /* check for Div(Const, Phi) */
2497                         value = apply_binop_on_phi(b, get_Const_tarval(a), (eval_func) tarval_div, mode, 1);
2498                         if (value) {
2499                                 DBG_OPT_ALGSIM0(n, value, FS_OPT_CONST_PHI);
2500                                 goto make_tuple;
2501                         }
2502                 } else if (is_const_Phi(a) && is_const_Phi(b)) {
2503                         /* check for Div(Phi, Phi) */
2504                         value = apply_binop_on_2_phis(a, b, (eval_func) tarval_div, mode);
2505                         if (value) {
2506                                 DBG_OPT_ALGSIM0(n, value, FS_OPT_CONST_PHI);
2507                                 goto make_tuple;
2508                         }
2509                 }
2510
2511                 if (a == b && value_not_zero(a, &dummy)) {
2512                         ir_graph *irg = get_irn_irg(n);
2513                         /* BEWARE: we can optimize a/a to 1 only if this cannot cause a exception */
2514                         value = new_r_Const(irg, get_mode_one(mode));
2515                         DBG_OPT_CSTEVAL(n, value);
2516                         goto make_tuple;
2517                 } else {
2518                         if (mode_is_signed(mode) && is_Const(b)) {
2519                                 ir_tarval *tv = get_Const_tarval(b);
2520
2521                                 if (tv == get_mode_minus_one(mode)) {
2522                                         /* a / -1 */
2523                                         value = new_rd_Minus(get_irn_dbg_info(n), get_nodes_block(n), a, mode);
2524                                         DBG_OPT_CSTEVAL(n, value);
2525                                         goto make_tuple;
2526                                 }
2527                         }
2528                         /* Try architecture dependent optimization */
2529                         value = arch_dep_replace_div_by_const(n);
2530                 }
2531         } else {
2532                 assert(mode_is_float(mode));
2533
2534                 /* Optimize x/c to x*(1/c) */
2535                 if (get_mode_arithmetic(mode) == irma_ieee754) {
2536                         ir_tarval *tv = value_of(b);
2537
2538                         if (tv != tarval_bad) {
2539                                 int rem = tarval_fp_ops_enabled();
2540
2541                                 /*
2542                                  * Floating point constant folding might be disabled here to
2543                                  * prevent rounding.
2544                                  * However, as we check for exact result, doing it is safe.
2545                                  * Switch it on.
2546                                  */
2547                                 tarval_enable_fp_ops(1);
2548                                 tv = tarval_div(get_mode_one(mode), tv);
2549                                 tarval_enable_fp_ops(rem);
2550
2551                                 /* Do the transformation if the result is either exact or we are
2552                                    not using strict rules. */
2553                                 if (tv != tarval_bad &&
2554                                         (tarval_ieee754_get_exact() || (get_irg_fp_model(get_irn_irg(n)) & fp_strict_algebraic) == 0)) {
2555                                         ir_node  *block = get_nodes_block(n);
2556                                         ir_graph *irg   = get_irn_irg(block);
2557                                         ir_node  *c     = new_r_Const(irg, tv);
2558                                         dbg_info *dbgi  = get_irn_dbg_info(n);
2559                                         value = new_rd_Mul(dbgi, block, a, c, mode);
2560
2561                                         goto make_tuple;
2562                                 }
2563                         }
2564                 }
2565         }
2566
2567         if (value != n) {
2568                 ir_node *mem, *blk;
2569                 ir_graph *irg;
2570
2571 make_tuple:
2572                 /* Turn Div into a tuple (mem, jmp, bad, value) */
2573                 mem = get_Div_mem(n);
2574                 blk = get_nodes_block(n);
2575                 irg = get_irn_irg(blk);
2576
2577                 /* skip a potential Pin */
2578                 mem = skip_Pin(mem);
2579                 turn_into_tuple(n, pn_Div_max);
2580                 set_Tuple_pred(n, pn_Div_M,         mem);
2581                 set_Tuple_pred(n, pn_Div_X_regular, new_r_Jmp(blk));
2582                 set_Tuple_pred(n, pn_Div_X_except,  new_r_Bad(irg, mode_X));
2583                 set_Tuple_pred(n, pn_Div_res,       value);
2584         }
2585         return n;
2586 }  /* transform_node_Div */
2587
2588 /**
2589  * Transform a Mod node.
2590  */
2591 static ir_node *transform_node_Mod(ir_node *n)
2592 {
2593         ir_mode   *mode = get_Mod_resmode(n);
2594         ir_node   *a    = get_Mod_left(n);
2595         ir_node   *b    = get_Mod_right(n);
2596         ir_graph  *irg;
2597         ir_node   *value;
2598         ir_tarval *tv;
2599
2600         if (is_Const(b) && is_const_Phi(a)) {
2601                 /* check for Div(Phi, Const) */
2602                 value = apply_binop_on_phi(a, get_Const_tarval(b), (eval_func) tarval_mod, mode, 0);
2603                 if (value) {
2604                         DBG_OPT_ALGSIM0(n, value, FS_OPT_CONST_PHI);
2605                         goto make_tuple;
2606                 }
2607         }
2608         else if (is_Const(a) && is_const_Phi(b)) {
2609                 /* check for Div(Const, Phi) */
2610                 value = apply_binop_on_phi(b, get_Const_tarval(a), (eval_func) tarval_mod, mode, 1);
2611                 if (value) {
2612                         DBG_OPT_ALGSIM0(n, value, FS_OPT_CONST_PHI);
2613                         goto make_tuple;
2614                 }
2615         }
2616         else if (is_const_Phi(a) && is_const_Phi(b)) {
2617                 /* check for Div(Phi, Phi) */
2618                 value = apply_binop_on_2_phis(a, b, (eval_func) tarval_mod, mode);
2619                 if (value) {
2620                         DBG_OPT_ALGSIM0(n, value, FS_OPT_CONST_PHI);
2621                         goto make_tuple;
2622                 }
2623         }
2624
2625         value = n;
2626         tv = value_of(n);
2627         irg = get_irn_irg(n);
2628         if (tv != tarval_bad) {
2629                 value = new_r_Const(irg, tv);
2630
2631                 DBG_OPT_CSTEVAL(n, value);
2632                 goto make_tuple;
2633         } else {
2634                 ir_node       *a = get_Mod_left(n);
2635                 ir_node       *b = get_Mod_right(n);
2636                 const ir_node *dummy;
2637
2638                 if (a == b && value_not_zero(a, &dummy)) {
2639                         /* BEWARE: we can optimize a%a to 0 only if this cannot cause a exception */
2640                         value = new_r_Const(irg, get_mode_null(mode));
2641                         DBG_OPT_CSTEVAL(n, value);
2642                         goto make_tuple;
2643                 } else {
2644                         if (mode_is_signed(mode) && is_Const(b)) {
2645                                 ir_tarval *tv = get_Const_tarval(b);
2646
2647                                 if (tv == get_mode_minus_one(mode)) {
2648                                         /* a % -1 = 0 */
2649                                         value = new_r_Const(irg, get_mode_null(mode));
2650                                         DBG_OPT_CSTEVAL(n, value);
2651                                         goto make_tuple;
2652                                 }
2653                         }
2654                         /* Try architecture dependent optimization */
2655                         value = arch_dep_replace_mod_by_const(n);
2656                 }
2657         }
2658
2659         if (value != n) {
2660                 ir_node *mem, *blk;
2661                 ir_graph *irg;
2662
2663 make_tuple:
2664                 /* Turn Mod into a tuple (mem, jmp, bad, value) */
2665                 mem = get_Mod_mem(n);
2666                 blk = get_nodes_block(n);
2667                 irg = get_irn_irg(blk);
2668
2669                 /* skip a potential Pin */
2670                 mem = skip_Pin(mem);
2671                 turn_into_tuple(n, pn_Mod_max);
2672                 set_Tuple_pred(n, pn_Mod_M,         mem);
2673                 set_Tuple_pred(n, pn_Mod_X_regular, new_r_Jmp(blk));
2674                 set_Tuple_pred(n, pn_Mod_X_except,  new_r_Bad(irg, mode_X));
2675                 set_Tuple_pred(n, pn_Mod_res,       value);
2676         }
2677         return n;
2678 }  /* transform_node_Mod */
2679
2680 /**
2681  * Transform a Cond node.
2682  *
2683  * Replace the Cond by a Jmp if it branches on a constant
2684  * condition.
2685  */
2686 static ir_node *transform_node_Cond(ir_node *n)
2687 {
2688
2689         ir_node   *a   = get_Cond_selector(n);
2690         ir_tarval *ta  = value_of(a);
2691         ir_graph  *irg = get_irn_irg(n);
2692         ir_node   *jmp;
2693
2694         /* we need block info which is not available in floating irgs */
2695         if (get_irg_pinned(irg) == op_pin_state_floats)
2696                 return n;
2697
2698         if ((ta != tarval_bad) &&
2699             (get_irn_mode(a) == mode_b) &&
2700             (get_opt_unreachable_code())) {
2701                 /* It's a boolean Cond, branching on a boolean constant.
2702                    Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
2703                 ir_node *blk = get_nodes_block(n);
2704                 jmp = new_r_Jmp(blk);
2705                 turn_into_tuple(n, pn_Cond_max);
2706                 if (ta == tarval_b_true) {
2707                         set_Tuple_pred(n, pn_Cond_false, new_r_Bad(irg, mode_X));
2708                         set_Tuple_pred(n, pn_Cond_true, jmp);
2709                 } else {
2710                         set_Tuple_pred(n, pn_Cond_false, jmp);
2711                         set_Tuple_pred(n, pn_Cond_true, new_r_Bad(irg, mode_X));
2712                 }
2713                 /* We might generate an endless loop, so keep it alive. */
2714                 add_End_keepalive(get_irg_end(irg), blk);
2715         }
2716         return n;
2717 }  /* transform_node_Cond */
2718
2719 /**
2720  * Prototype of a recursive transform function
2721  * for bitwise distributive transformations.
2722  */
2723 typedef ir_node* (*recursive_transform)(ir_node *n);
2724
2725 /**
2726  * makes use of distributive laws for and, or, eor
2727  *     and(a OP c, b OP c) -> and(a, b) OP c
2728  * note, might return a different op than n
2729  */
2730 static ir_node *transform_bitwise_distributive(ir_node *n,
2731                                                recursive_transform trans_func)
2732 {
2733         ir_node *oldn    = n;
2734         ir_node *a       = get_binop_left(n);
2735         ir_node *b       = get_binop_right(n);
2736         ir_op   *op      = get_irn_op(a);
2737         ir_op   *op_root = get_irn_op(n);
2738
2739         if (op != get_irn_op(b))
2740                 return n;
2741
2742         /* and(conv(a), conv(b)) -> conv(and(a,b)) */
2743         if (op == op_Conv) {
2744                 ir_node *a_op   = get_Conv_op(a);
2745                 ir_node *b_op   = get_Conv_op(b);
2746                 ir_mode *a_mode = get_irn_mode(a_op);
2747                 ir_mode *b_mode = get_irn_mode(b_op);
2748                 if (a_mode == b_mode && (mode_is_int(a_mode) || a_mode == mode_b)) {
2749                         ir_node *blk = get_nodes_block(n);
2750
2751                         n = exact_copy(n);
2752                         set_binop_left(n, a_op);
2753                         set_binop_right(n, b_op);
2754                         set_irn_mode(n, a_mode);
2755                         n = trans_func(n);
2756                         n = new_r_Conv(blk, n, get_irn_mode(oldn));
2757
2758                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_CONV);
2759                         return n;
2760                 }
2761         }
2762
2763         if (op == op_Eor) {
2764                 /* nothing to gain here */
2765                 return n;
2766         }
2767
2768         if (op == op_Shrs || op == op_Shr || op == op_Shl
2769                         || op == op_And || op == op_Or || op == op_Eor) {
2770                 ir_node *a_left  = get_binop_left(a);
2771                 ir_node *a_right = get_binop_right(a);
2772                 ir_node *b_left  = get_binop_left(b);
2773                 ir_node *b_right = get_binop_right(b);
2774                 ir_node *c       = NULL;
2775                 ir_node *op1     = NULL;
2776                 ir_node *op2     = NULL;
2777
2778                 if (is_op_commutative(op)) {
2779                         if (a_left == b_left) {
2780                                 c   = a_left;
2781                                 op1 = a_right;
2782                                 op2 = b_right;
2783                         } else if (a_left == b_right) {
2784                                 c   = a_left;
2785                                 op1 = a_right;
2786                                 op2 = b_left;
2787                         } else if (a_right == b_left) {
2788                                 c   = a_right;
2789                                 op1 = a_left;
2790                                 op2 = b_right;
2791                         }
2792                 }
2793                 if (a_right == b_right) {
2794                         c   = a_right;
2795                         op1 = a_left;
2796                         op2 = b_left;
2797                 }
2798
2799                 if (c != NULL) {
2800                         /* (a sop c) & (b sop c) => (a & b) sop c */
2801                         ir_node *blk = get_nodes_block(n);
2802
2803                         ir_node *new_n = exact_copy(n);
2804                         set_binop_left(new_n, op1);
2805                         set_binop_right(new_n, op2);
2806                         new_n = trans_func(new_n);
2807
2808                         if (op_root == op_Eor && op == op_Or) {
2809                                 dbg_info  *dbgi = get_irn_dbg_info(n);
2810                                 ir_mode   *mode = get_irn_mode(c);
2811
2812                                 c = new_rd_Not(dbgi, blk, c, mode);
2813                                 n = new_rd_And(dbgi, blk, new_n, c, mode);
2814                         } else {
2815                                 n = exact_copy(a);
2816                                 set_nodes_block(n, blk);
2817                                 set_binop_left(n, new_n);
2818                                 set_binop_right(n, c);
2819                                 add_identities(n);
2820                         }
2821
2822                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_SHIFT_AND);
2823                         return n;
2824                 }
2825         }
2826
2827         return n;
2828 }
2829
2830 /**
2831  * Create a 0 constant of given mode.
2832  */
2833 static ir_node *create_zero_const(ir_graph *irg, ir_mode *mode)
2834 {
2835         ir_tarval *tv   = get_mode_null(mode);
2836         ir_node   *cnst = new_r_Const(irg, tv);
2837
2838         return cnst;
2839 }
2840
2841 /**
2842  * Transform an And.
2843  */
2844 static ir_node *transform_node_And(ir_node *n)
2845 {
2846         ir_node *c, *oldn = n;
2847         ir_node *a = get_And_left(n);
2848         ir_node *b = get_And_right(n);
2849         ir_mode *mode;
2850         vrp_attr *a_vrp, *b_vrp;
2851
2852         if (is_Cmp(a) && is_Cmp(b)) {
2853                 ir_node    *a_left     = get_Cmp_left(a);
2854                 ir_node    *a_right    = get_Cmp_right(a);
2855                 ir_node    *b_left     = get_Cmp_left(b);
2856                 ir_node    *b_right    = get_Cmp_right(b);
2857                 ir_relation a_relation = get_Cmp_relation(a);
2858                 ir_relation b_relation = get_Cmp_relation(b);
2859                 /* we can combine the relations of two compares with the same
2860                  * operands */
2861                 if (a_left == b_left && b_left == b_right) {
2862                         dbg_info   *dbgi         = get_irn_dbg_info(n);
2863                         ir_node    *block        = get_nodes_block(n);
2864                         ir_relation new_relation = a_relation & b_relation;
2865                         return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation);
2866                 }
2867                 /* Cmp(a==0) and Cmp(b==0) can be optimized to Cmp(a|b==0) */
2868                 if (is_Const(a_right) && is_Const_null(a_right)
2869                                 && is_Const(b_right) && is_Const_null(b_right)
2870                                 && a_relation == b_relation && a_relation == ir_relation_equal
2871                                 && !mode_is_float(get_irn_mode(a_left))
2872                                 && !mode_is_float(get_irn_mode(b_left))) {
2873                         dbg_info *dbgi     = get_irn_dbg_info(n);
2874                         ir_node  *block    = get_nodes_block(n);
2875                         ir_mode  *mode     = get_irn_mode(a_left);
2876                         ir_node  *n_b_left = get_irn_mode(b_left) != mode ?
2877                                 new_rd_Conv(dbgi, block, b_left, mode) : b_left;
2878                         ir_node  *or       = new_rd_Or(dbgi, block, a_left, n_b_left, mode);
2879                         ir_graph *irg      = get_irn_irg(n);
2880                         ir_node  *zero     = create_zero_const(irg, mode);
2881                         return new_rd_Cmp(dbgi, block, or, zero, ir_relation_equal);
2882                 }
2883         }
2884
2885         mode = get_irn_mode(n);
2886         HANDLE_BINOP_PHI((eval_func) tarval_and, a, b, c, mode);
2887
2888         if (is_Or(a)) {
2889                 if (is_Not(b)) {
2890                         ir_node *op = get_Not_op(b);
2891                         if (is_And(op)) {
2892                                 ir_node *ba = get_And_left(op);
2893                                 ir_node *bb = get_And_right(op);
2894
2895                                 /* it's enough to test the following cases due to normalization! */
2896                                 if (get_Or_left(a) == ba && get_Or_right(a) == bb) {
2897                                         /* (a|b) & ~(a&b) = a^b */
2898                                         ir_node *block = get_nodes_block(n);
2899
2900                                         n = new_rd_Eor(get_irn_dbg_info(n), block, ba, bb, mode);
2901                                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_TO_EOR);
2902                                         return n;
2903                                 }
2904                         }
2905                 }
2906         }
2907         if (is_Or(b)) {
2908                 if (is_Not(a)) {
2909                         ir_node *op = get_Not_op(a);
2910                         if (is_And(op)) {
2911                                 ir_node *aa = get_And_left(op);
2912                                 ir_node *ab = get_And_right(op);
2913
2914                                 /* it's enough to test the following cases due to normalization! */
2915                                 if (get_Or_left(b) == aa && get_Or_right(b) == ab) {
2916                                         /* (a|b) & ~(a&b) = a^b */
2917                                         ir_node *block = get_nodes_block(n);
2918
2919                                         n = new_rd_Eor(get_irn_dbg_info(n), block, aa, ab, mode);
2920                                         DBG_OPT_ALGSIM1(oldn, a, b, n, FS_OPT_TO_EOR);
2921                                         return n;
2922                                 }
2923                         }
2924                 }
2925         }
2926         if (is_Eor(a)) {
2927                 ir_node *al = get_Eor_left(a);
2928                 ir_node *ar = get_Eor_right(a);
2929
2930                 if (al == b) {
2931                         /* (b ^ a) & b -> ~a & b */
2932                         dbg_info *dbg  = get_irn_dbg_info(n);
2933                         ir_node *block = get_nodes_block(n);
2934
2935                         ar = new_rd_Not(dbg, block, ar, mode);
2936                         n  = new_rd_And(dbg, block, ar, b, mode);
2937                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
2938                         return n;
2939                 }
2940                 if (ar == b) {
2941                         /* (a ^ b) & b -> ~a & b */
2942                         dbg_info *dbg  = get_irn_dbg_info(n);
2943                         ir_node *block = get_nodes_block(n);
2944
2945                         al = new_rd_Not(dbg, block, al, mode);
2946                         n  = new_rd_And(dbg, block, al, b, mode);
2947                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
2948                         return n;
2949                 }
2950         }
2951         if (is_Eor(b)) {
2952                 ir_node *bl = get_Eor_left(b);
2953                 ir_node *br = get_Eor_right(b);
2954
2955                 if (bl == a) {
2956                         /* a & (a ^ b) -> a & ~b */
2957                         dbg_info *dbg  = get_irn_dbg_info(n);
2958                         ir_node *block = get_nodes_block(n);
2959
2960                         br = new_rd_Not(dbg, block, br, mode);
2961                         n  = new_rd_And(dbg, block, br, a, mode);
2962                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
2963                         return n;
2964                 }
2965                 if (br == a) {
2966                         /* a & (b ^ a) -> a & ~b */
2967                         dbg_info *dbg  = get_irn_dbg_info(n);
2968                         ir_node *block = get_nodes_block(n);
2969
2970                         bl = new_rd_Not(dbg, block, bl, mode);
2971                         n  = new_rd_And(dbg, block, bl, a, mode);
2972                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
2973                         return n;
2974                 }
2975         }
2976         if (is_Not(a) && is_Not(b)) {
2977                 /* ~a & ~b = ~(a|b) */
2978                 ir_node *block = get_nodes_block(n);
2979                 ir_mode *mode = get_irn_mode(n);
2980
2981                 a = get_Not_op(a);
2982                 b = get_Not_op(b);
2983                 n = new_rd_Or(get_irn_dbg_info(n), block, a, b, mode);
2984                 n = new_rd_Not(get_irn_dbg_info(n), block, n, mode);
2985                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_DEMORGAN);
2986                 return n;
2987         }
2988
2989         b_vrp = vrp_get_info(b);
2990         if (is_Const(a) && b_vrp && (tarval_cmp(tarval_or(get_Const_tarval(a),
2991                                                 b_vrp->bits_not_set), get_Const_tarval(a)) == ir_relation_equal)) {
2992
2993                 return b;
2994
2995         }
2996
2997         a_vrp = vrp_get_info(a);
2998         if (is_Const(b) && a_vrp && (tarval_cmp(tarval_or(get_Const_tarval(b),
2999                                                 a_vrp->bits_not_set), get_Const_tarval(b)) == ir_relation_equal)) {
3000                 return a;
3001         }
3002
3003         n = transform_bitwise_distributive(n, transform_node_And);
3004
3005         return n;
3006 }  /* transform_node_And */
3007
3008 /* the order of the values is important! */
3009 typedef enum const_class {
3010         const_const = 0,
3011         const_like  = 1,
3012         const_other = 2
3013 } const_class;
3014
3015 static const_class classify_const(const ir_node* n)
3016 {
3017         if (is_Const(n))         return const_const;
3018         if (is_irn_constlike(n)) return const_like;
3019         return const_other;
3020 }
3021
3022 /**
3023  * Determines whether r is more constlike or has a larger index (in that order)
3024  * than l.
3025  */
3026 static bool operands_are_normalized(const ir_node *l, const ir_node *r)
3027 {
3028         const const_class l_order = classify_const(l);
3029         const const_class r_order = classify_const(r);
3030         return
3031                 l_order > r_order ||
3032                 (l_order == r_order && get_irn_idx(l) <= get_irn_idx(r));
3033 }
3034
3035 /**
3036  * Transform an Eor.
3037  */
3038 static ir_node *transform_node_Eor(ir_node *n)
3039 {
3040         ir_node *c, *oldn = n;
3041         ir_node *a = get_Eor_left(n);
3042         ir_node *b = get_Eor_right(n);
3043         ir_mode *mode = get_irn_mode(n);
3044
3045         /* we can combine the relations of two compares with the same operands */
3046         if (is_Cmp(a) && is_Cmp(b)) {
3047                 ir_node *a_left  = get_Cmp_left(a);
3048                 ir_node *a_right = get_Cmp_left(a);
3049                 ir_node *b_left  = get_Cmp_left(b);
3050                 ir_node *b_right = get_Cmp_right(b);
3051                 if (a_left == b_left && b_left == b_right) {
3052                         dbg_info   *dbgi         = get_irn_dbg_info(n);
3053                         ir_node    *block        = get_nodes_block(n);
3054                         ir_relation a_relation   = get_Cmp_relation(a);
3055                         ir_relation b_relation   = get_Cmp_relation(b);
3056                         ir_relation new_relation = a_relation ^ b_relation;
3057                         return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation);
3058                 }
3059         }
3060
3061         HANDLE_BINOP_PHI((eval_func) tarval_eor, a, b, c, mode);
3062
3063         /* normalize not nodes... ~a ^ b <=> a ^ ~b */
3064         if (is_Not(a) && operands_are_normalized(get_Not_op(a), b)) {
3065                 dbg_info *dbg      = get_irn_dbg_info(n);
3066                 ir_node  *block    = get_nodes_block(n);
3067                 ir_node  *new_not  = new_rd_Not(dbg, block, b, mode);
3068                 ir_node  *new_left = get_Not_op(a);
3069                 n = new_rd_Eor(dbg, block, new_left, new_not, mode);
3070                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
3071                 return n;
3072         } else if (is_Not(b) && !operands_are_normalized(a, get_Not_op(b))) {
3073                 dbg_info *dbg       = get_irn_dbg_info(n);
3074                 ir_node  *block     = get_nodes_block(n);
3075                 ir_node  *new_not   = new_rd_Not(dbg, block, a, mode);
3076                 ir_node  *new_right = get_Not_op(b);
3077                 n = new_rd_Eor(dbg, block, new_not, new_right, mode);
3078                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
3079                 return n;
3080         }
3081
3082         /* x ^ 1...1 -> ~1 */
3083         if (is_Const(b) && is_Const_all_one(b)) {
3084                 n = new_r_Not(get_nodes_block(n), a, mode);
3085                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_EOR_TO_NOT);
3086                 return n;
3087         }
3088
3089         n = transform_bitwise_distributive(n, transform_node_Eor);
3090         return n;
3091 }  /* transform_node_Eor */
3092
3093 /**
3094  * Transform a Not.
3095  */
3096 static ir_node *transform_node_Not(ir_node *n)
3097 {
3098         ir_node *c, *oldn = n;
3099         ir_node *a    = get_Not_op(n);
3100         ir_mode *mode = get_irn_mode(n);
3101
3102         HANDLE_UNOP_PHI(tarval_not,a,c);
3103
3104         /* check for a boolean Not */
3105         if (is_Cmp(a)) {
3106                 dbg_info *dbgi  = get_irn_dbg_info(a);
3107                 ir_node  *block = get_nodes_block(a);
3108                 ir_relation relation = get_Cmp_relation(a);
3109                 relation = get_negated_relation(relation);
3110                 n = new_rd_Cmp(dbgi, block, get_Cmp_left(a), get_Cmp_right(a), relation);
3111                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_CMP);
3112                 return n;
3113         }
3114
3115         /* normalize ~(a ^ b) => a ^ ~b */
3116         if (is_Eor(a)) {
3117                 dbg_info *dbg       = get_irn_dbg_info(n);
3118                 ir_node  *block     = get_nodes_block(n);
3119                 ir_node  *eor_right = get_Eor_right(a);
3120                 ir_node  *eor_left  = get_Eor_left(a);
3121                 eor_right = new_rd_Not(dbg, block, eor_right, mode);
3122                 n = new_rd_Eor(dbg, block, eor_left, eor_right, mode);
3123                 return n;
3124         }
3125
3126         if (get_mode_arithmetic(mode) == irma_twos_complement) {
3127                 if (is_Minus(a)) { /* ~-x -> x + -1 */
3128                         dbg_info *dbg   = get_irn_dbg_info(n);
3129                         ir_graph *irg   = get_irn_irg(n);
3130                         ir_node  *block = get_nodes_block(n);
3131                         ir_node  *add_l = get_Minus_op(a);
3132                         ir_node  *add_r = new_rd_Const(dbg, irg, get_mode_minus_one(mode));
3133                         n = new_rd_Add(dbg, block, add_l, add_r, mode);
3134                 } else if (is_Add(a)) {
3135                         ir_node *add_r = get_Add_right(a);
3136                         if (is_Const(add_r) && is_Const_all_one(add_r)) {
3137                                 /* ~(x + -1) = -x */
3138                                 ir_node *op = get_Add_left(a);
3139                                 ir_node *blk = get_nodes_block(n);
3140                                 n = new_rd_Minus(get_irn_dbg_info(n), blk, op, get_irn_mode(n));
3141                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_NOT_MINUS_1);
3142                         }
3143                 }
3144         }
3145         return n;
3146 }
3147
3148 /**
3149  * Transform a Minus.
3150  * Optimize:
3151  *   -(~x) = x + 1
3152  *   -(a-b) = b - a
3153  *   -(a >>u (size-1)) = a >>s (size-1)
3154  *   -(a >>s (size-1)) = a >>u (size-1)
3155  *   -(a * const) -> a * -const
3156  */
3157 static ir_node *transform_node_Minus(ir_node *n)
3158 {
3159         ir_node *c, *oldn = n;
3160         ir_node *a = get_Minus_op(n);
3161         ir_mode *mode;
3162
3163         HANDLE_UNOP_PHI(tarval_neg,a,c);
3164
3165         mode = get_irn_mode(a);
3166         if (get_mode_arithmetic(mode) == irma_twos_complement) {
3167                 /* the following rules are only to twos-complement */
3168                 if (is_Not(a)) {
3169                         /* -(~x) = x + 1 */
3170                         ir_node   *op  = get_Not_op(a);
3171                         ir_tarval *tv  = get_mode_one(mode);
3172                         ir_node   *blk = get_nodes_block(n);
3173                         ir_graph  *irg = get_irn_irg(blk);
3174                         ir_node   *c   = new_r_Const(irg, tv);
3175                         n = new_rd_Add(get_irn_dbg_info(n), blk, op, c, mode);
3176                         DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_NOT);
3177                         return n;
3178                 }
3179                 if (is_Shr(a)) {
3180                         ir_node *c = get_Shr_right(a);
3181
3182                         if (is_Const(c)) {
3183                                 ir_tarval *tv = get_Const_tarval(c);
3184
3185                                 if (tarval_is_long(tv) && get_tarval_long(tv) == (int) get_mode_size_bits(mode) - 1) {
3186                                         /* -(a >>u (size-1)) = a >>s (size-1) */
3187                                         ir_node *v = get_Shr_left(a);
3188
3189                                         n = new_rd_Shrs(get_irn_dbg_info(n), get_nodes_block(n), v, c, mode);
3190                                         DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_PREDICATE);
3191                                         return n;
3192                                 }
3193                         }
3194                 }
3195                 if (is_Shrs(a)) {
3196                         ir_node *c = get_Shrs_right(a);
3197
3198                         if (is_Const(c)) {
3199                                 ir_tarval *tv = get_Const_tarval(c);
3200
3201                                 if (tarval_is_long(tv) && get_tarval_long(tv) == (int) get_mode_size_bits(mode) - 1) {
3202                                         /* -(a >>s (size-1)) = a >>u (size-1) */
3203                                         ir_node *v = get_Shrs_left(a);
3204
3205                                         n = new_rd_Shr(get_irn_dbg_info(n), get_nodes_block(n), v, c, mode);
3206                                         DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_PREDICATE);
3207                                         return n;
3208                                 }
3209                         }
3210                 }
3211         }
3212         if (is_Sub(a)) {
3213                 /* - (a-b) = b - a */
3214                 ir_node *la  = get_Sub_left(a);
3215                 ir_node *ra  = get_Sub_right(a);
3216                 ir_node *blk = get_nodes_block(n);
3217
3218                 n = new_rd_Sub(get_irn_dbg_info(n), blk, ra, la, mode);
3219                 DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_SUB);
3220                 return n;
3221         }
3222
3223         if (is_Mul(a)) { /* -(a * const) -> a * -const */
3224                 ir_node   *mul_l = get_Mul_left(a);
3225                 ir_node   *mul_r = get_Mul_right(a);
3226                 ir_tarval *tv    = value_of(mul_r);
3227                 if (tv != tarval_bad) {
3228                         tv = tarval_neg(tv);
3229                         if (tv != tarval_bad) {
3230                                 ir_graph *irg   = get_irn_irg(n);
3231                                 ir_node  *cnst  = new_r_Const(irg, tv);
3232                                 dbg_info *dbg   = get_irn_dbg_info(a);
3233                                 ir_node  *block = get_nodes_block(a);
3234                                 n = new_rd_Mul(dbg, block, mul_l, cnst, mode);
3235                                 DBG_OPT_ALGSIM2(oldn, a, n, FS_OPT_MINUS_MUL_C);
3236                                 return n;
3237                         }
3238                 }
3239         }
3240
3241         return n;
3242 }  /* transform_node_Minus */
3243
3244 /**
3245  * Transform a Proj(Load) with a non-null address.
3246  */
3247 static ir_node *transform_node_Proj_Load(ir_node *proj)
3248 {
3249         if (get_opt_ldst_only_null_ptr_exceptions()) {
3250                 if (get_irn_mode(proj) == mode_X) {
3251                         ir_node *load = get_Proj_pred(proj);
3252
3253                         /* get the Load address */
3254                         const ir_node *addr = get_Load_ptr(load);
3255                         const ir_node *confirm;
3256
3257                         if (value_not_null(addr, &confirm)) {
3258                                 if (confirm == NULL) {
3259                                         /* this node may float if it did not depend on a Confirm */
3260                                         set_irn_pinned(load, op_pin_state_floats);
3261                                 }
3262                                 if (get_Proj_proj(proj) == pn_Load_X_except) {
3263                                         ir_graph *irg = get_irn_irg(proj);
3264                                         DBG_OPT_EXC_REM(proj);
3265                                         return new_r_Bad(irg, mode_X);
3266                                 } else {
3267                                         ir_node *blk = get_nodes_block(load);
3268                                         return new_r_Jmp(blk);
3269                                 }
3270                         }
3271                 }
3272         }
3273         return proj;
3274 }  /* transform_node_Proj_Load */
3275
3276 /**
3277  * Transform a Proj(Store) with a non-null address.
3278  */
3279 static ir_node *transform_node_Proj_Store(ir_node *proj)
3280 {
3281         if (get_opt_ldst_only_null_ptr_exceptions()) {
3282                 if (get_irn_mode(proj) == mode_X) {
3283                         ir_node *store = get_Proj_pred(proj);
3284
3285                         /* get the load/store address */
3286                         const ir_node *addr = get_Store_ptr(store);
3287                         const ir_node *confirm;
3288
3289                         if (value_not_null(addr, &confirm)) {
3290                                 if (confirm == NULL) {
3291                                         /* this node may float if it did not depend on a Confirm */
3292                                         set_irn_pinned(store, op_pin_state_floats);
3293                                 }
3294                                 if (get_Proj_proj(proj) == pn_Store_X_except) {
3295                                         ir_graph *irg = get_irn_irg(proj);
3296                                         DBG_OPT_EXC_REM(proj);
3297                                         return new_r_Bad(irg, mode_X);
3298                                 } else {
3299                                         ir_node *blk = get_nodes_block(store);
3300                                         return new_r_Jmp(blk);
3301                                 }
3302                         }
3303                 }
3304         }
3305         return proj;
3306 }  /* transform_node_Proj_Store */
3307
3308 /**
3309  * Transform a Proj(Div) with a non-zero value.
3310  * Removes the exceptions and routes the memory to the NoMem node.
3311  */
3312 static ir_node *transform_node_Proj_Div(ir_node *proj)
3313 {
3314         ir_node *div = get_Proj_pred(proj);
3315         ir_node *b   = get_Div_right(div);
3316         ir_node *res, *new_mem;
3317         const ir_node *confirm;
3318         long proj_nr;
3319
3320         if (value_not_zero(b, &confirm)) {
3321                 /* div(x, y) && y != 0 */
3322                 if (confirm == NULL) {
3323                         /* we are sure we have a Const != 0 */
3324                         new_mem = get_Div_mem(div);
3325                         new_mem = skip_Pin(new_mem);
3326                         set_Div_mem(div, new_mem);
3327                         set_irn_pinned(div, op_pin_state_floats);
3328                 }
3329
3330                 proj_nr = get_Proj_proj(proj);
3331                 switch (proj_nr) {
3332                 case pn_Div_X_regular:
3333                         return new_r_Jmp(get_nodes_block(div));
3334
3335                 case pn_Div_X_except: {
3336                         ir_graph *irg = get_irn_irg(proj);
3337                         /* we found an exception handler, remove it */
3338                         DBG_OPT_EXC_REM(proj);
3339                         return new_r_Bad(irg, mode_X);
3340                 }
3341
3342                 case pn_Div_M: {
3343                         ir_graph *irg = get_irn_irg(proj);
3344                         res = get_Div_mem(div);
3345                         new_mem = get_irg_no_mem(irg);
3346
3347                         if (confirm) {
3348                                 /* This node can only float up to the Confirm block */
3349                                 new_mem = new_r_Pin(get_nodes_block(confirm), new_mem);
3350                         }
3351                         set_irn_pinned(div, op_pin_state_floats);
3352                         /* this is a Div without exception, we can remove the memory edge */
3353                         set_Div_mem(div, new_mem);
3354                         return res;
3355                 }
3356                 }
3357         }
3358         return proj;
3359 }  /* transform_node_Proj_Div */
3360
3361 /**
3362  * Transform a Proj(Mod) with a non-zero value.
3363  * Removes the exceptions and routes the memory to the NoMem node.
3364  */
3365 static ir_node *transform_node_Proj_Mod(ir_node *proj)
3366 {
3367         ir_node *mod = get_Proj_pred(proj);
3368         ir_node *b   = get_Mod_right(mod);
3369         ir_node *res, *new_mem;
3370         const ir_node *confirm;
3371         long proj_nr;
3372
3373         if (value_not_zero(b, &confirm)) {
3374                 /* mod(x, y) && y != 0 */
3375                 proj_nr = get_Proj_proj(proj);
3376
3377                 if (confirm == NULL) {
3378                         /* we are sure we have a Const != 0 */
3379                         new_mem = get_Mod_mem(mod);
3380                         new_mem = skip_Pin(new_mem);
3381                         set_Mod_mem(mod, new_mem);
3382                         set_irn_pinned(mod, op_pin_state_floats);
3383                 }
3384
3385                 switch (proj_nr) {
3386
3387                 case pn_Mod_X_regular:
3388                         return new_r_Jmp(get_irn_n(mod, -1));
3389
3390                 case pn_Mod_X_except: {
3391                         ir_graph *irg = get_irn_irg(proj);
3392                         /* we found an exception handler, remove it */
3393                         DBG_OPT_EXC_REM(proj);
3394                         return new_r_Bad(irg, mode_X);
3395                 }
3396
3397                 case pn_Mod_M: {
3398                         ir_graph *irg = get_irn_irg(proj);
3399                         res = get_Mod_mem(mod);
3400                         new_mem = get_irg_no_mem(irg);
3401
3402                         if (confirm) {
3403                                 /* This node can only float up to the Confirm block */
3404                                 new_mem = new_r_Pin(get_nodes_block(confirm), new_mem);
3405                         }
3406                         /* this is a Mod without exception, we can remove the memory edge */
3407                         set_Mod_mem(mod, new_mem);
3408                         return res;
3409                 }
3410                 case pn_Mod_res:
3411                         if (get_Mod_left(mod) == b) {
3412                                 /* a % a = 0 if a != 0 */
3413                                 ir_graph *irg  = get_irn_irg(proj);
3414                                 ir_mode  *mode = get_irn_mode(proj);
3415                                 ir_node  *res  = new_r_Const(irg, get_mode_null(mode));
3416
3417                                 DBG_OPT_CSTEVAL(mod, res);
3418                                 return res;
3419                         }
3420                 }
3421         }
3422         return proj;
3423 }  /* transform_node_Proj_Mod */
3424
3425 /**
3426  * Optimizes jump tables (CondIs or CondIu) by removing all impossible cases.
3427  */
3428 static ir_node *transform_node_Proj_Cond(ir_node *proj)
3429 {
3430         ir_node *n = get_Proj_pred(proj);
3431         ir_node *b = get_Cond_selector(n);
3432
3433         if (!get_opt_unreachable_code())
3434                 return n;
3435
3436         if (mode_is_int(get_irn_mode(b))) {
3437                 ir_tarval *tb = value_of(b);
3438
3439                 if (tb != tarval_bad) {
3440                         /* we have a constant switch */
3441                         long num = get_Proj_proj(proj);
3442
3443                         if (num != get_Cond_default_proj(n)) { /* we cannot optimize default Proj's yet */
3444                                 if (get_tarval_long(tb) == num) {
3445                                         /* Do NOT create a jump here, or we will have 2 control flow ops
3446                                          * in a block. This case is optimized away in optimize_cf(). */
3447                                         return proj;
3448                                 } else {
3449                                         ir_graph *irg = get_irn_irg(proj);
3450                                         /* this case will NEVER be taken, kill it */
3451                                         return new_r_Bad(irg, mode_X);
3452                                 }
3453                         }
3454                 } else {
3455                         long num = get_Proj_proj(proj);
3456                         vrp_attr *b_vrp = vrp_get_info(b);
3457                         if (num != get_Cond_default_proj(n) && b_vrp) {
3458                                 /* Try handling with vrp data. We only remove dead parts. */
3459                                 ir_tarval *tp = new_tarval_from_long(num, get_irn_mode(b));
3460
3461                                 if (b_vrp->range_type == VRP_RANGE) {
3462                                         ir_relation cmp_result = tarval_cmp(b_vrp->range_bottom, tp);
3463                                         ir_relation cmp_result2 = tarval_cmp(b_vrp->range_top, tp);
3464
3465                                         if ((cmp_result & ir_relation_greater) == cmp_result
3466                                             && (cmp_result2 & ir_relation_less) == cmp_result2) {
3467                                                 ir_graph *irg = get_irn_irg(proj);
3468                                                 return new_r_Bad(irg, mode_X);
3469                                         }
3470                                 } else if (b_vrp->range_type == VRP_ANTIRANGE) {
3471                                         ir_relation cmp_result = tarval_cmp(b_vrp->range_bottom, tp);
3472                                         ir_relation cmp_result2 = tarval_cmp(b_vrp->range_top, tp);
3473
3474                                         if ((cmp_result & ir_relation_less_equal) == cmp_result
3475                                              && (cmp_result2 & ir_relation_greater_equal) == cmp_result2) {
3476                                                 ir_graph *irg = get_irn_irg(proj);
3477                                                 return new_r_Bad(irg, mode_X);
3478                                         }
3479                                 }
3480
3481                                 if (!(tarval_cmp(
3482                                                                 tarval_and( b_vrp->bits_set, tp),
3483                                                                 b_vrp->bits_set
3484                                                                 ) == ir_relation_equal)) {
3485                                         ir_graph *irg = get_irn_irg(proj);
3486                                         return new_r_Bad(irg, mode_X);
3487                                 }
3488
3489                                 if (!(tarval_cmp(
3490                                                                 tarval_and(
3491                                                                         tarval_not(tp),
3492                                                                         tarval_not(b_vrp->bits_not_set)),
3493                                                                 tarval_not(b_vrp->bits_not_set))
3494                                                                  == ir_relation_equal)) {
3495                                         ir_graph *irg = get_irn_irg(proj);
3496                                         return new_r_Bad(irg, mode_X);
3497                                 }
3498                         }
3499                 }
3500         }
3501         return proj;
3502 }
3503
3504 /**
3505  * return true if the operation returns a value with exactly 1 bit set
3506  */
3507 static bool is_single_bit(const ir_node *node)
3508 {
3509         /* a first implementation, could be extended with vrp and others... */
3510         if (is_Shl(node)) {
3511                 ir_node *shl_l  = get_Shl_left(node);
3512                 ir_mode *mode   = get_irn_mode(node);
3513                 int      modulo = get_mode_modulo_shift(mode);
3514                 /* this works if we shift a 1 and we have modulo shift */
3515                 if (is_Const(shl_l) && is_Const_one(shl_l)
3516                                 && 0 < modulo && modulo <= (int)get_mode_size_bits(mode)) {
3517                         return true;
3518                 }
3519         } else if (is_Const(node)) {
3520                 ir_tarval *tv = get_Const_tarval(node);
3521                 return tarval_is_single_bit(tv);
3522         }
3523         return false;
3524 }
3525
3526 /**
3527  * Normalizes and optimizes Cmp nodes.
3528  */
3529 static ir_node *transform_node_Cmp(ir_node *n)
3530 {
3531         ir_node    *left     = get_Cmp_left(n);
3532         ir_node    *right    = get_Cmp_right(n);
3533         ir_mode    *mode     = get_irn_mode(left);
3534         ir_tarval  *tv       = NULL;
3535         bool        changed  = false;
3536         bool        changedc = false;
3537         ir_relation relation = get_Cmp_relation(n);
3538         ir_relation possible = ir_get_possible_cmp_relations(left, right);
3539
3540         /* mask out impossible relations */
3541         ir_relation new_relation = relation & possible;
3542         if (new_relation != relation) {
3543                 relation = new_relation;
3544                 changed  = true;
3545         }
3546
3547         /* Remove unnecessary conversions */
3548         /* TODO handle conv+constant */
3549         if (is_Conv(left) && is_Conv(right)) {
3550                 ir_node *op_left     = get_Conv_op(left);
3551                 ir_node *op_right    = get_Conv_op(right);
3552                 ir_mode *mode_left   = get_irn_mode(op_left);
3553                 ir_mode *mode_right  = get_irn_mode(op_right);
3554
3555                 if (smaller_mode(mode_left, mode) && smaller_mode(mode_right, mode)
3556                                 && mode_left != mode_b && mode_right != mode_b) {
3557                         ir_node  *block = get_nodes_block(n);
3558
3559                         if (mode_left == mode_right) {
3560                                 left  = op_left;
3561                                 right = op_right;
3562                                 changed = true;
3563                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV_CONV);
3564                         } else if (smaller_mode(mode_left, mode_right)) {
3565                                 left  = new_r_Conv(block, op_left, mode_right);
3566                                 right = op_right;
3567                                 changed = true;
3568                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV);
3569                         } else if (smaller_mode(mode_right, mode_left)) {
3570                                 left  = op_left;
3571                                 right = new_r_Conv(block, op_right, mode_left);
3572                                 changed = true;
3573                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV);
3574                         }
3575                 }
3576         }
3577
3578         /*
3579          * Optimize -a CMP -b into b CMP a.
3580          * This works only for modes where unary Minus cannot Overflow.
3581          * Note that two-complement integers can Overflow so it will NOT work.
3582          */
3583         if (!mode_overflow_on_unary_Minus(mode) &&
3584                         is_Minus(left) && is_Minus(right)) {
3585                 left     = get_Minus_op(left);
3586                 right    = get_Minus_op(right);
3587                 relation = get_inversed_relation(relation);
3588                 changed  = true;
3589                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3590         }
3591
3592         /* remove operation on both sides if possible */
3593         if (relation == ir_relation_equal || relation == ir_relation_less_greater) {
3594                 /*
3595                  * The following operations are NOT safe for floating point operations, for instance
3596                  * 1.0 + inf == 2.0 + inf, =/=> x == y
3597                  */
3598                 if (mode_is_int(mode)) {
3599                         unsigned lop = get_irn_opcode(left);
3600
3601                         if (lop == get_irn_opcode(right)) {
3602                                 ir_node *ll, *lr, *rl, *rr;
3603
3604                                 /* same operation on both sides, try to remove */
3605                                 switch (lop) {
3606                                 case iro_Not:
3607                                 case iro_Minus:
3608                                         /* ~a CMP ~b => a CMP b, -a CMP -b ==> a CMP b */
3609                                         left  = get_unop_op(left);
3610                                         right = get_unop_op(right);
3611                                         changed = true;
3612                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3613                                         break;
3614                                 case iro_Add:
3615                                         ll = get_Add_left(left);
3616                                         lr = get_Add_right(left);
3617                                         rl = get_Add_left(right);
3618                                         rr = get_Add_right(right);
3619
3620                                         if (ll == rl) {
3621                                                 /* X + a CMP X + b ==> a CMP b */
3622                                                 left  = lr;
3623                                                 right = rr;
3624                                                 changed = true;
3625                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3626                                         } else if (ll == rr) {
3627                                                 /* X + a CMP b + X ==> a CMP b */
3628                                                 left  = lr;
3629                                                 right = rl;
3630                                                 changed = true;
3631                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3632                                         } else if (lr == rl) {
3633                                                 /* a + X CMP X + b ==> a CMP b */
3634                                                 left  = ll;
3635                                                 right = rr;
3636                                                 changed = true;
3637                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3638                                         } else if (lr == rr) {
3639                                                 /* a + X CMP b + X ==> a CMP b */
3640                                                 left  = ll;
3641                                                 right = rl;
3642                                                 changed = true;
3643                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3644                                         }
3645                                         break;
3646                                 case iro_Sub:
3647                                         ll = get_Sub_left(left);
3648                                         lr = get_Sub_right(left);
3649                                         rl = get_Sub_left(right);
3650                                         rr = get_Sub_right(right);
3651
3652                                         if (ll == rl) {
3653                                                 /* X - a CMP X - b ==> a CMP b */
3654                                                 left  = lr;
3655                                                 right = rr;
3656                                                 changed = true;
3657                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3658                                         } else if (lr == rr) {
3659                                                 /* a - X CMP b - X ==> a CMP b */
3660                                                 left  = ll;
3661                                                 right = rl;
3662                                                 changed = true;
3663                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3664                                         }
3665                                         break;
3666                                 case iro_Rotl:
3667                                         if (get_Rotl_right(left) == get_Rotl_right(right)) {
3668                                                 /* a ROTL X CMP b ROTL X ==> a CMP b */
3669                                                 left  = get_Rotl_left(left);
3670                                                 right = get_Rotl_left(right);
3671                                                 changed = true;
3672                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3673                                         }
3674                                         break;
3675                                 default:
3676                                         break;
3677                                 }
3678                         }
3679
3680                         /* X+A == A, A+X == A, A-X == A -> X == 0 */
3681                         if (is_Add(left) || is_Sub(left)) {
3682                                 ir_node *ll = get_binop_left(left);
3683                                 ir_node *lr = get_binop_right(left);
3684
3685                                 if (lr == right && is_Add(left)) {
3686                                         ir_node *tmp = ll;
3687                                         ll = lr;
3688                                         lr = tmp;
3689                                 }
3690                                 if (ll == right) {
3691                                         ir_graph *irg = get_irn_irg(n);
3692                                         left     = lr;
3693                                         right   = create_zero_const(irg, mode);
3694                                         changed = true;
3695                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3696                                 }
3697                         }
3698                         if (is_Add(right) || is_Sub(right)) {
3699                                 ir_node *rl = get_binop_left(right);
3700                                 ir_node *rr = get_binop_right(right);
3701
3702                                 if (rr == left && is_Add(right)) {
3703                                         ir_node *tmp = rl;
3704                                         rl = rr;
3705                                         rr = tmp;
3706                                 }
3707                                 if (rl == left) {
3708                                         ir_graph *irg = get_irn_irg(n);
3709                                         left     = rr;
3710                                         right   = create_zero_const(irg, mode);
3711                                         changed = true;
3712                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_OP);
3713                                 }
3714                         }
3715
3716                         if (is_And(left) && is_Const(right)) {
3717                                 ir_node *ll = get_binop_left(left);
3718                                 ir_node *lr = get_binop_right(left);
3719                                 if (is_Shr(ll) && is_Const(lr)) {
3720                                         /* Cmp((x >>u c1) & c2, c3) = Cmp(x & (c2 << c1), c3 << c1) */
3721                                         ir_node *block = get_nodes_block(n);
3722                                         ir_mode *mode = get_irn_mode(left);
3723
3724                                         ir_node *llr = get_Shr_right(ll);
3725                                         if (is_Const(llr)) {
3726                                                 dbg_info *dbg = get_irn_dbg_info(left);
3727                                                 ir_graph *irg = get_irn_irg(left);
3728
3729                                                 ir_tarval *c1    = get_Const_tarval(llr);
3730                                                 ir_tarval *c2    = get_Const_tarval(lr);
3731                                                 ir_tarval *c3    = get_Const_tarval(right);
3732                                                 ir_tarval *mask  = tarval_shl(c2, c1);
3733                                                 ir_tarval *value = tarval_shl(c3, c1);
3734
3735                                                 left  = new_rd_And(dbg, block, get_Shr_left(ll), new_r_Const(irg, mask), mode);
3736                                                 right = new_r_Const(irg, value);
3737                                                 changed = true;
3738                                         }
3739                                 }
3740                         }
3741                         /* Cmp(Eor(x, y), 0) <=> Cmp(x, y) at least for the ==0,!=0
3742                          * cases */
3743                         if (is_Const(right) && is_Const_null(right) && is_Eor(left)) {
3744                                 right = get_Eor_right(left);
3745                                 left  = get_Eor_left(left);
3746                                 changed = true;
3747                         }
3748                 }  /* mode_is_int(...) */
3749         }
3750
3751         /* Cmp(And(1bit, val), 1bit) "bit-testing" can be replaced
3752          * by the simpler Cmp(And(1bit), val), 0) negated pnc */
3753         if (mode_is_int(mode) && is_And(left)
3754             && (relation == ir_relation_equal
3755                 || (mode_is_signed(mode) && relation == ir_relation_less_greater)
3756                 || (!mode_is_signed(mode) && (relation & ir_relation_less_equal) == ir_relation_less))) {
3757                 ir_node *and0 = get_And_left(left);
3758                 ir_node *and1 = get_And_right(left);
3759                 if (and1 == right) {
3760                         ir_node *tmp = and0;
3761                         and0 = and1;
3762                         and1 = tmp;
3763                 }
3764                 if (and0 == right && is_single_bit(and0)) {
3765                         ir_graph *irg = get_irn_irg(n);
3766                         relation =
3767                                 relation == ir_relation_equal ? ir_relation_less_greater : ir_relation_equal;
3768                         right = create_zero_const(irg, mode);
3769                         changed |= 1;
3770                 }
3771         }
3772
3773         /* replace mode_b compares with ands/ors */
3774         if (mode == mode_b) {
3775                 ir_node  *block = get_nodes_block(n);
3776                 ir_node  *bres;
3777
3778                 switch (relation) {
3779                         case ir_relation_less_equal:
3780                                 bres = new_r_Or(block, new_r_Not(block, left, mode_b), right, mode_b);
3781                                 break;
3782                         case ir_relation_less:
3783                                 bres = new_r_And(block, new_r_Not(block, left, mode_b), right, mode_b);
3784                                 break;
3785                         case ir_relation_greater_equal:
3786                                 bres = new_r_Or(block, left, new_r_Not(block, right, mode_b), mode_b);
3787                                 break;
3788                         case ir_relation_greater:
3789                                 bres = new_r_And(block, left, new_r_Not(block, right, mode_b), mode_b);
3790                                 break;
3791                         case ir_relation_less_greater:
3792                                 bres = new_r_Eor(block, left, right, mode_b);
3793                                 break;
3794                         case ir_relation_equal:
3795                                 bres = new_r_Not(block, new_r_Eor(block, left, right, mode_b), mode_b);
3796                                 break;
3797                         default:
3798 #ifdef DEBUG_libfirm
3799                                 ir_fprintf(stderr, "Optimisation warning, unexpected mode_b Cmp %+F\n", n);
3800 #endif
3801                                 bres = NULL;
3802                 }
3803                 if (bres != NULL) {
3804                         DBG_OPT_ALGSIM0(n, bres, FS_OPT_CMP_TO_BOOL);
3805                         return bres;
3806                 }
3807         }
3808
3809         /*
3810          * First step: normalize the compare op
3811          * by placing the constant on the right side
3812          * or moving the lower address node to the left.
3813          */
3814         if (!operands_are_normalized(left, right)) {
3815                 ir_node *t = left;
3816                 left  = right;
3817                 right = t;
3818
3819                 relation = get_inversed_relation(relation);
3820                 changed  = true;
3821         }
3822
3823         /*
3824          * Second step: Try to reduce the magnitude
3825          * of a constant. This may help to generate better code
3826          * later and may help to normalize more compares.
3827          * Of course this is only possible for integer values.
3828          */
3829         tv = value_of(right);
3830         if (tv != tarval_bad) {
3831                 ir_mode *mode = get_irn_mode(right);
3832
3833                 /* TODO extend to arbitrary constants */
3834                 if (is_Conv(left) && tarval_is_null(tv)) {
3835                         ir_node *op      = get_Conv_op(left);
3836                         ir_mode *op_mode = get_irn_mode(op);
3837
3838                         /*
3839                          * UpConv(x) REL 0  ==> x REL 0
3840                          * Don't do this for float values as it's unclear whether it is a
3841                          * win. (on the other side it makes detection/creation of fabs hard)
3842                          */
3843                         if (get_mode_size_bits(mode) > get_mode_size_bits(op_mode) &&
3844                             ((relation == ir_relation_equal || relation == ir_relation_less_greater) ||
3845                                  mode_is_signed(mode) || !mode_is_signed(op_mode)) &&
3846                                 !mode_is_float(mode)) {
3847                                 tv   = get_mode_null(op_mode);
3848                                 left = op;
3849                                 mode = op_mode;
3850                                 changedc = true;
3851                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CONV);
3852                         }
3853                 }
3854
3855                 if (tv != tarval_bad) {
3856                         /* the following optimization is possible on modes without Overflow
3857                          * on Unary Minus or on == and !=:
3858                          * -a CMP c  ==>  a swap(CMP) -c
3859                          *
3860                          * Beware: for two-complement Overflow may occur, so only == and != can
3861                          * be optimized, see this:
3862                          * -MININT < 0 =/=> MININT > 0 !!!
3863                          */
3864                         if (is_Minus(left) &&
3865                                 (!mode_overflow_on_unary_Minus(mode) ||
3866                                 (mode_is_int(mode) && (relation == ir_relation_equal || relation == ir_relation_less_greater)))) {
3867                                 tv = tarval_neg(tv);
3868
3869                                 if (tv != tarval_bad) {
3870                                         left = get_Minus_op(left);
3871                                         relation = get_inversed_relation(relation);
3872                                         changedc = true;
3873                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
3874                                 }
3875                         } else if (is_Not(left) && (relation == ir_relation_equal || relation == ir_relation_less_greater)) {
3876                                 /* Not(a) ==/!= c  ==>  a ==/!= Not(c) */
3877                                 tv = tarval_not(tv);
3878
3879                                 if (tv != tarval_bad) {
3880                                         left = get_Not_op(left);
3881                                         changedc = true;
3882                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
3883                                 }
3884                         }
3885
3886                         /* for integer modes, we have more */
3887                         if (mode_is_int(mode)) {
3888                                 /* c > 0 : a < c  ==>  a <= (c-1)    a >= c  ==>  a > (c-1) */
3889                                 if ((relation == ir_relation_less || relation == ir_relation_greater_equal) &&
3890                                         tarval_cmp(tv, get_mode_null(mode)) == ir_relation_greater) {
3891                                         tv = tarval_sub(tv, get_mode_one(mode), NULL);
3892
3893                                         if (tv != tarval_bad) {
3894                                                 relation ^= ir_relation_equal;
3895                                                 changedc = true;
3896                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CNST_MAGN);
3897                                         }
3898                                 }
3899                                 /* c < 0 : a > c  ==>  a >= (c+1)    a <= c  ==>  a < (c+1) */
3900                                 else if ((relation == ir_relation_greater || relation == ir_relation_less_equal) &&
3901                                         tarval_cmp(tv, get_mode_null(mode)) == ir_relation_less) {
3902                                         tv = tarval_add(tv, get_mode_one(mode));
3903
3904                                         if (tv != tarval_bad) {
3905                                                 relation ^= ir_relation_equal;
3906                                                 changedc = true;
3907                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CNST_MAGN);
3908                                         }
3909                                 }
3910
3911                                 /* the following reassociations work only for == and != */
3912                                 if (relation == ir_relation_equal || relation == ir_relation_less_greater) {
3913                                         if (tv != tarval_bad) {
3914                                                 /* a-c1 == c2  ==>  a == c2+c1,  a-c1 != c2  ==>  a != c2+c1 */
3915                                                 if (is_Sub(left)) {
3916                                                         ir_node *c1 = get_Sub_right(left);
3917                                                         ir_tarval *tv2 = value_of(c1);
3918
3919                                                         if (tv2 != tarval_bad) {
3920                                                                 tv2 = tarval_add(tv, value_of(c1));
3921
3922                                                                 if (tv2 != tarval_bad) {
3923                                                                         left    = get_Sub_left(left);
3924                                                                         tv      = tv2;
3925                                                                         changedc = true;
3926                                                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
3927                                                                 }
3928                                                         }
3929                                                 }
3930                                                 /* a+c1 == c2  ==>  a == c2-c1,  a+c1 != c2  ==>  a != c2-c1 */
3931                                                 else if (is_Add(left)) {
3932                                                         ir_node *a_l = get_Add_left(left);
3933                                                         ir_node *a_r = get_Add_right(left);
3934                                                         ir_node *a;
3935                                                         ir_tarval *tv2;
3936
3937                                                         if (is_Const(a_l)) {
3938                                                                 a = a_r;
3939                                                                 tv2 = value_of(a_l);
3940                                                         } else {
3941                                                                 a = a_l;
3942                                                                 tv2 = value_of(a_r);
3943                                                         }
3944
3945                                                         if (tv2 != tarval_bad) {
3946                                                                 tv2 = tarval_sub(tv, tv2, NULL);
3947
3948                                                                 if (tv2 != tarval_bad) {
3949                                                                         left    = a;
3950                                                                         tv      = tv2;
3951                                                                         changedc = true;
3952                                                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
3953                                                                 }
3954                                                         }
3955                                                 }
3956                                                 /* -a == c ==> a == -c, -a != c ==> a != -c */
3957                                                 else if (is_Minus(left)) {
3958                                                         ir_tarval *tv2 = tarval_sub(get_mode_null(mode), tv, NULL);
3959
3960                                                         if (tv2 != tarval_bad) {
3961                                                                 left    = get_Minus_op(left);
3962                                                                 tv      = tv2;
3963                                                                 changedc = true;
3964                                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_OP_C);
3965                                                         }
3966                                                 }
3967                                         }
3968                                 } /* == or != */
3969                         } /* mode_is_int */
3970
3971                         if (relation == ir_relation_equal || relation == ir_relation_less_greater) {
3972                                 switch (get_irn_opcode(left)) {
3973                                         ir_node *c1;
3974
3975                                 case iro_And:
3976                                         c1 = get_And_right(left);
3977                                         if (is_Const(c1)) {
3978                                                 /*
3979                                                  * And(x, C1) == C2 ==> FALSE if C2 & C1 != C2
3980                                                  * And(x, C1) != C2 ==> TRUE if C2 & C1 != C2
3981                                                  */
3982                                                 ir_tarval *mask = tarval_and(get_Const_tarval(c1), tv);
3983                                                 if (mask != tv) {
3984                                                         /* TODO: move to constant evaluation */
3985                                                         ir_graph *irg = get_irn_irg(n);
3986                                                         tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
3987                                                         c1 = new_r_Const(irg, tv);
3988                                                         DBG_OPT_CSTEVAL(n, c1);
3989                                                         return c1;
3990                                                 }
3991
3992                                                 if (tarval_is_single_bit(tv)) {
3993                                                         /*
3994                                                          * optimization for AND:
3995                                                          * Optimize:
3996                                                          *   And(x, C) == C  ==>  And(x, C) != 0
3997                                                          *   And(x, C) != C  ==>  And(X, C) == 0
3998                                                          *
3999                                                          * if C is a single Bit constant.
4000                                                          */
4001
4002                                                         /* check for Constant's match. We have check hare the tarvals,
4003                                                            because our const might be changed */
4004                                                         if (get_Const_tarval(c1) == tv) {
4005                                                                 /* fine: do the transformation */
4006                                                                 tv = get_mode_null(get_tarval_mode(tv));
4007                                                                 relation ^= ir_relation_less_equal_greater;
4008                                                                 changedc = true;
4009                                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_CNST_MAGN);
4010                                                         }
4011                                                 }
4012                                         }
4013                                         break;
4014                                 case iro_Or:
4015                                         c1 = get_Or_right(left);
4016                                         if (is_Const(c1) && tarval_is_null(tv)) {
4017                                                 /*
4018                                                  * Or(x, C) == 0  && C != 0 ==> FALSE
4019                                                  * Or(x, C) != 0  && C != 0 ==> TRUE
4020                                                  */
4021                                                 if (! tarval_is_null(get_Const_tarval(c1))) {
4022                                                         /* TODO: move to constant evaluation */
4023                                                         ir_graph *irg = get_irn_irg(n);
4024                                                         tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
4025                                                         c1 = new_r_Const(irg, tv);
4026                                                         DBG_OPT_CSTEVAL(n, c1);
4027                                                         return c1;
4028                                                 }
4029                                         }
4030                                         break;
4031                                 case iro_Shl:
4032                                         /*
4033                                          * optimize x << c1 == c into x & (-1 >>u c1) == c >> c1  if  c & (-1 << c1) == c
4034                                          *                             FALSE                       else
4035                                          * optimize x << c1 != c into x & (-1 >>u c1) != c >> c1  if  c & (-1 << c1) == c
4036                                          *                             TRUE                        else
4037                                          */
4038                                         c1 = get_Shl_right(left);
4039                                         if (is_Const(c1)) {
4040                                                 ir_graph  *irg    = get_irn_irg(c1);
4041                                                 ir_tarval *tv1    = get_Const_tarval(c1);
4042                                                 ir_mode   *mode   = get_irn_mode(left);
4043                                                 ir_tarval *minus1 = get_mode_all_one(mode);
4044                                                 ir_tarval *amask  = tarval_shr(minus1, tv1);
4045                                                 ir_tarval *cmask  = tarval_shl(minus1, tv1);
4046                                                 ir_node   *sl, *blk;
4047
4048                                                 if (tarval_and(tv, cmask) != tv) {
4049                                                         /* condition not met */
4050                                                         tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
4051                                                         c1 = new_r_Const(irg, tv);
4052                                                         DBG_OPT_CSTEVAL(n, c1);
4053                                                         return c1;
4054                                                 }
4055                                                 sl   = get_Shl_left(left);
4056                                                 blk  = get_nodes_block(n);
4057                                                 left = new_rd_And(get_irn_dbg_info(left), blk, sl, new_r_Const(irg, amask), mode);
4058                                                 tv   = tarval_shr(tv, tv1);
4059                                                 changedc = true;
4060                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_SHF_TO_AND);
4061                                         }
4062                                         break;
4063                                 case iro_Shr:
4064                                         /*
4065                                          * optimize x >>u c1 == c into x & (-1 << c1) == c << c1  if  c & (-1 >>u c1) == c
4066                                          *                             FALSE                       else
4067                                          * optimize x >>u c1 != c into x & (-1 << c1) != c << c1  if  c & (-1 >>u c1) == c
4068                                          *                             TRUE                        else
4069                                          */
4070                                         c1 = get_Shr_right(left);
4071                                         if (is_Const(c1)) {
4072                                                 ir_graph  *irg    = get_irn_irg(c1);
4073                                                 ir_tarval *tv1    = get_Const_tarval(c1);
4074                                                 ir_mode   *mode   = get_irn_mode(left);
4075                                                 ir_tarval *minus1 = get_mode_all_one(mode);
4076                                                 ir_tarval *amask  = tarval_shl(minus1, tv1);
4077                                                 ir_tarval *cmask  = tarval_shr(minus1, tv1);
4078                                                 ir_node   *sl, *blk;
4079
4080                                                 if (tarval_and(tv, cmask) != tv) {
4081                                                         /* condition not met */
4082                                                         tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
4083                                                         c1 = new_r_Const(irg, tv);
4084                                                         DBG_OPT_CSTEVAL(n, c1);
4085                                                         return c1;
4086                                                 }
4087                                                 sl   = get_Shr_left(left);
4088                                                 blk  = get_nodes_block(n);
4089                                                 left = new_rd_And(get_irn_dbg_info(left), blk, sl, new_r_Const(irg, amask), mode);
4090                                                 tv   = tarval_shl(tv, tv1);
4091                                                 changedc = true;
4092                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_SHF_TO_AND);
4093                                         }
4094                                         break;
4095                                 case iro_Shrs:
4096                                         /*
4097                                          * optimize x >>s c1 == c into x & (-1 << c1) == c << c1  if  (c >>s (BITS - c1)) \in {0,-1}
4098                                          *                             FALSE                       else
4099                                          * optimize x >>s c1 != c into x & (-1 << c1) != c << c1  if  (c >>s (BITS - c1)) \in {0,-1}
4100                                          *                             TRUE                        else
4101                                          */
4102                                         c1 = get_Shrs_right(left);
4103                                         if (is_Const(c1)) {
4104                                                 ir_graph  *irg    = get_irn_irg(c1);
4105                                                 ir_tarval *tv1    = get_Const_tarval(c1);
4106                                                 ir_mode   *mode   = get_irn_mode(left);
4107                                                 ir_tarval *minus1 = get_mode_all_one(mode);
4108                                                 ir_tarval *amask  = tarval_shl(minus1, tv1);
4109                                                 ir_tarval *cond   = new_tarval_from_long(get_mode_size_bits(mode), get_tarval_mode(tv1));
4110                                                 ir_node *sl, *blk;
4111
4112                                                 cond = tarval_sub(cond, tv1, NULL);
4113                                                 cond = tarval_shrs(tv, cond);
4114
4115                                                 if (!tarval_is_all_one(cond) && !tarval_is_null(cond)) {
4116                                                         /* condition not met */
4117                                                         tv = relation == ir_relation_equal ? get_tarval_b_false() : get_tarval_b_true();
4118                                                         c1 = new_r_Const(irg, tv);
4119                                                         DBG_OPT_CSTEVAL(n, c1);
4120                                                         return c1;
4121                                                 }
4122                                                 sl   = get_Shrs_left(left);
4123                                                 blk  = get_nodes_block(n);
4124                                                 left = new_rd_And(get_irn_dbg_info(left), blk, sl, new_r_Const(irg, amask), mode);
4125                                                 tv   = tarval_shl(tv, tv1);
4126                                                 changedc = true;
4127                                                 DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_SHF_TO_AND);
4128                                         }
4129                                         break;
4130                                 }  /* switch */
4131                         }
4132                 } /* tarval != bad */
4133         }
4134
4135         if (changedc) {     /* need a new Const */
4136                 ir_graph *irg = get_irn_irg(n);
4137                 right = new_r_Const(irg, tv);
4138                 changed = true;
4139         }
4140
4141         if ((relation == ir_relation_equal || relation == ir_relation_less_greater) && is_Const(right) && is_Const_null(right) && is_Proj(left)) {
4142                 ir_node *op = get_Proj_pred(left);
4143
4144                 if (is_Mod(op) && get_Proj_proj(left) == pn_Mod_res) {
4145                         ir_node *c = get_binop_right(op);
4146
4147                         if (is_Const(c)) {
4148                                 ir_tarval *tv = get_Const_tarval(c);
4149
4150                                 if (tarval_is_single_bit(tv)) {
4151                                         /* special case: (x % 2^n) CMP 0 ==> x & (2^n-1) CMP 0 */
4152                                         ir_node *v    = get_binop_left(op);
4153                                         ir_node *blk  = get_irn_n(op, -1);
4154                                         ir_graph *irg = get_irn_irg(op);
4155                                         ir_mode *mode = get_irn_mode(v);
4156
4157                                         tv = tarval_sub(tv, get_mode_one(mode), NULL);
4158                                         left = new_rd_And(get_irn_dbg_info(op), blk, v, new_r_Const(irg, tv), mode);
4159                                         changed = true;
4160                                         DBG_OPT_ALGSIM0(n, n, FS_OPT_CMP_MOD_TO_AND);
4161                                 }
4162                         }
4163                 }
4164         }
4165
4166         if (changed) {
4167                 dbg_info *dbgi  = get_irn_dbg_info(n);
4168                 ir_node  *block = get_nodes_block(n);
4169
4170                 /* create a new compare */
4171                 n = new_rd_Cmp(dbgi, block, left, right, relation);
4172         }
4173
4174         return n;
4175 }
4176
4177 /**
4178  * Optimize CopyB(mem, x, x) into a Nop.
4179  */
4180 static ir_node *transform_node_Proj_CopyB(ir_node *proj)
4181 {
4182         ir_node *copyb = get_Proj_pred(proj);
4183         ir_node *a     = get_CopyB_dst(copyb);
4184         ir_node *b     = get_CopyB_src(copyb);
4185
4186         if (a == b) {
4187                 switch (get_Proj_proj(proj)) {
4188                 case pn_CopyB_X_regular:
4189                         /* Turn CopyB into a tuple (mem, jmp, bad, bad) */
4190                         DBG_OPT_EXC_REM(proj);
4191                         proj = new_r_Jmp(get_nodes_block(copyb));
4192                         break;
4193                 case pn_CopyB_X_except: {
4194                         ir_graph *irg = get_irn_irg(proj);
4195                         DBG_OPT_EXC_REM(proj);
4196                         proj = new_r_Bad(irg, mode_X);
4197                         break;
4198                 }
4199                 default:
4200                         break;
4201                 }
4202         }
4203         return proj;
4204 }  /* transform_node_Proj_CopyB */
4205
4206 /**
4207  * Optimize Bounds(idx, idx, upper) into idx.
4208  */
4209 static ir_node *transform_node_Proj_Bound(ir_node *proj)
4210 {
4211         ir_node *oldn  = proj;
4212         ir_node *bound = get_Proj_pred(proj);
4213         ir_node *idx   = get_Bound_index(bound);
4214         ir_node *pred  = skip_Proj(idx);
4215         int ret_tuple  = 0;
4216
4217         if (idx == get_Bound_lower(bound))
4218                 ret_tuple = 1;
4219         else if (is_Bound(pred)) {
4220                 /*
4221                 * idx was Bounds checked previously, it is still valid if
4222                 * lower <= pred_lower && pred_upper <= upper.
4223                 */
4224                 ir_node *lower = get_Bound_lower(bound);
4225                 ir_node *upper = get_Bound_upper(bound);
4226                 if (get_Bound_lower(pred) == lower &&
4227                         get_Bound_upper(pred) == upper) {
4228                         /*
4229                          * One could expect that we simply return the previous
4230                          * Bound here. However, this would be wrong, as we could
4231                          * add an exception Proj to a new location then.
4232                          * So, we must turn in into a tuple.
4233                          */
4234                         ret_tuple = 1;
4235                 }
4236         }
4237         if (ret_tuple) {
4238                 /* Turn Bound into a tuple (mem, jmp, bad, idx) */
4239                 switch (get_Proj_proj(proj)) {
4240                 case pn_Bound_M:
4241                         DBG_OPT_EXC_REM(proj);
4242                         proj = get_Bound_mem(bound);
4243                         break;
4244                 case pn_Bound_X_except:
4245                         DBG_OPT_EXC_REM(proj);
4246                         proj = new_r_Bad(get_irn_irg(proj), mode_X);
4247                         break;
4248                 case pn_Bound_res:
4249                         proj = idx;
4250                         DBG_OPT_ALGSIM0(oldn, proj, FS_OPT_NOP);
4251                         break;
4252                 case pn_Bound_X_regular:
4253                         DBG_OPT_EXC_REM(proj);
4254                         proj = new_r_Jmp(get_nodes_block(bound));
4255                         break;
4256                 default:
4257                         break;
4258                 }
4259         }
4260         return proj;
4261 }  /* transform_node_Proj_Bound */
4262
4263 /**
4264  * Does all optimizations on nodes that must be done on its Projs
4265  * because of creating new nodes.
4266  */
4267 static ir_node *transform_node_Proj(ir_node *proj)
4268 {
4269         ir_node *n = get_Proj_pred(proj);
4270
4271         if (n->op->ops.transform_node_Proj)
4272                 return n->op->ops.transform_node_Proj(proj);
4273         return proj;
4274 }  /* transform_node_Proj */
4275
4276 static bool is_block_unreachable(const ir_node *block)
4277 {
4278         const ir_graph *irg = get_irn_irg(block);
4279         if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK))
4280                 return false;
4281         return get_Block_dom_depth(block) < 0;
4282 }
4283
4284 static ir_node *transform_node_Block(ir_node *block)
4285 {
4286         ir_graph *irg   = get_irn_irg(block);
4287         int       arity = get_irn_arity(block);
4288         ir_node  *bad   = NULL;
4289         int       i;
4290
4291         if (!is_irg_state(irg, IR_GRAPH_STATE_BAD_BLOCK))
4292                 return block;
4293
4294         for (i = 0; i < arity; ++i) {
4295                 ir_node *pred       = get_Block_cfgpred(block, i);
4296                 ir_node *pred_block = get_nodes_block(pred);
4297                 if (!is_Bad(pred) && !is_block_unreachable(pred_block))
4298                         continue;
4299                 if (bad == NULL)
4300                         bad = new_r_Bad(irg, mode_X);
4301                 set_irn_n(block, i, bad);
4302         }
4303
4304         return block;
4305 }
4306
4307 static ir_node *transform_node_Phi(ir_node *phi)
4308 {
4309         int       n     = get_irn_arity(phi);
4310         ir_mode  *mode  = get_irn_mode(phi);
4311         ir_node  *block = get_nodes_block(phi);
4312         ir_graph *irg   = get_irn_irg(phi);
4313         ir_node  *bad   = NULL;
4314         int       i;
4315
4316         /* Set phi-operands for bad-block inputs to bad */
4317         for (i = 0; i < n; ++i) {
4318                 ir_node *pred = get_Block_cfgpred(block, i);
4319                 if (is_Bad(pred) || is_block_unreachable(get_nodes_block(pred))) {
4320                         if (bad == NULL)
4321                                 bad = new_r_Bad(irg, mode);
4322                         set_irn_n(phi, i, bad);
4323                 }
4324         }
4325
4326         /* Move Confirms down through Phi nodes. */
4327         if (mode_is_reference(mode)) {
4328                 n = get_irn_arity(phi);
4329
4330                 /* Beware of Phi0 */
4331                 if (n > 0) {
4332                         ir_node    *pred = get_irn_n(phi, 0);
4333                         ir_node    *bound, *new_phi, *block, **in;
4334                         ir_relation relation;
4335
4336                         if (! is_Confirm(pred))
4337                                 return phi;
4338
4339                         bound    = get_Confirm_bound(pred);
4340                         relation = get_Confirm_relation(pred);
4341
4342                         NEW_ARR_A(ir_node *, in, n);
4343                         in[0] = get_Confirm_value(pred);
4344
4345                         for (i = 1; i < n; ++i) {
4346                                 pred = get_irn_n(phi, i);
4347
4348                                 if (! is_Confirm(pred) ||
4349                                         get_Confirm_bound(pred) != bound ||
4350                                         get_Confirm_relation(pred) != relation)
4351                                         return phi;
4352                                 in[i] = get_Confirm_value(pred);
4353                         }
4354                         /* move the Confirm nodes "behind" the Phi */
4355                         block = get_irn_n(phi, -1);
4356                         new_phi = new_r_Phi(block, n, in, get_irn_mode(phi));
4357                         return new_r_Confirm(block, new_phi, bound, relation);
4358                 }
4359         }
4360         return phi;
4361 }
4362
4363 /**
4364  * Returns the operands of a commutative bin-op, if one operand is
4365  * a const, it is returned as the second one.
4366  */
4367 static void get_comm_Binop_Ops(ir_node *binop, ir_node **a, ir_node **c)
4368 {
4369         ir_node *op_a = get_binop_left(binop);
4370         ir_node *op_b = get_binop_right(binop);
4371
4372         assert(is_op_commutative(get_irn_op(binop)));
4373
4374         if (is_Const(op_a)) {
4375                 *a = op_b;
4376                 *c = op_a;
4377         } else {
4378                 *a = op_a;
4379                 *c = op_b;
4380         }
4381 }  /* get_comm_Binop_Ops */
4382
4383 /**
4384  * Optimize a Or(And(Or(And(v,c4),c3),c2),c1) pattern if possible.
4385  * Such pattern may arise in bitfield stores.
4386  *
4387  * value  c4                  value      c4 & c2
4388  *    AND     c3                    AND           c1 | c3
4389  *        OR     c2      ===>               OR
4390  *           AND    c1
4391  *               OR
4392  *
4393  *
4394  * value  c2                 value  c1
4395  *     AND   c1    ===>           OR     if (c1 | c2) == 0x111..11
4396  *        OR
4397  */
4398 static ir_node *transform_node_Or_bf_store(ir_node *irn_or)
4399 {
4400         ir_node *irn_and, *c1;
4401         ir_node *or_l, *c2;
4402         ir_node *and_l, *c3;
4403         ir_node *value, *c4;
4404         ir_node *new_and, *new_const, *block;
4405         ir_mode *mode = get_irn_mode(irn_or);
4406
4407         ir_tarval *tv1, *tv2, *tv3, *tv4, *tv;
4408
4409         for (;;) {
4410                 ir_graph *irg;
4411                 get_comm_Binop_Ops(irn_or, &irn_and, &c1);
4412                 if (!is_Const(c1) || !is_And(irn_and))
4413                         return irn_or;
4414
4415                 get_comm_Binop_Ops(irn_and, &or_l, &c2);
4416                 if (!is_Const(c2))
4417                         return irn_or;
4418
4419                 tv1 = get_Const_tarval(c1);
4420                 tv2 = get_Const_tarval(c2);
4421
4422                 tv = tarval_or(tv1, tv2);
4423                 if (tarval_is_all_one(tv)) {
4424                         /* the AND does NOT clear a bit with isn't set by the OR */
4425                         set_Or_left(irn_or, or_l);
4426                         set_Or_right(irn_or, c1);
4427
4428                         /* check for more */
4429                         continue;
4430                 }
4431
4432                 if (!is_Or(or_l))
4433                         return irn_or;
4434
4435                 get_comm_Binop_Ops(or_l, &and_l, &c3);
4436                 if (!is_Const(c3) || !is_And(and_l))
4437                         return irn_or;
4438
4439                 get_comm_Binop_Ops(and_l, &value, &c4);
4440                 if (!is_Const(c4))
4441                         return irn_or;
4442
4443                 /* ok, found the pattern, check for conditions */
4444                 assert(mode == get_irn_mode(irn_and));
4445                 assert(mode == get_irn_mode(or_l));
4446                 assert(mode == get_irn_mode(and_l));
4447
4448                 tv3 = get_Const_tarval(c3);
4449                 tv4 = get_Const_tarval(c4);
4450
4451                 tv = tarval_or(tv4, tv2);
4452                 if (!tarval_is_all_one(tv)) {
4453                         /* have at least one 0 at the same bit position */
4454                         return irn_or;
4455                 }
4456
4457                 if (tv3 != tarval_andnot(tv3, tv4)) {
4458                         /* bit in the or_mask is outside the and_mask */
4459                         return irn_or;
4460                 }
4461
4462                 if (tv1 != tarval_andnot(tv1, tv2)) {
4463                         /* bit in the or_mask is outside the and_mask */
4464                         return irn_or;
4465                 }
4466
4467                 /* ok, all conditions met */
4468                 block = get_irn_n(irn_or, -1);
4469                 irg   = get_irn_irg(block);
4470
4471                 new_and = new_r_And(block, value, new_r_Const(irg, tarval_and(tv4, tv2)), mode);
4472
4473                 new_const = new_r_Const(irg, tarval_or(tv3, tv1));
4474
4475                 set_Or_left(irn_or, new_and);
4476                 set_Or_right(irn_or, new_const);
4477
4478                 /* check for more */
4479         }
4480 }  /* transform_node_Or_bf_store */
4481
4482 /**
4483  * Optimize an Or(shl(x, c), shr(x, bits - c)) into a Rotl
4484  */
4485 static ir_node *transform_node_Or_Rotl(ir_node *irn_or)
4486 {
4487         ir_mode *mode = get_irn_mode(irn_or);
4488         ir_node *shl, *shr, *block;
4489         ir_node *irn, *x, *c1, *c2, *n;
4490         ir_tarval *tv1, *tv2;
4491
4492         /* some backends can't handle rotl */
4493         if (!be_get_backend_param()->support_rotl)
4494                 return irn_or;
4495
4496         if (! mode_is_int(mode))
4497                 return irn_or;
4498
4499         shl = get_binop_left(irn_or);
4500         shr = get_binop_right(irn_or);
4501
4502         if (is_Shr(shl)) {
4503                 if (!is_Shl(shr))
4504                         return irn_or;
4505
4506                 irn = shl;
4507                 shl = shr;
4508                 shr = irn;
4509         } else if (!is_Shl(shl)) {
4510                 return irn_or;
4511         } else if (!is_Shr(shr)) {
4512                 return irn_or;
4513         }
4514         x = get_Shl_left(shl);
4515         if (x != get_Shr_left(shr))
4516                 return irn_or;
4517
4518         c1 = get_Shl_right(shl);
4519         c2 = get_Shr_right(shr);
4520         if (is_Const(c1) && is_Const(c2)) {
4521                 tv1 = get_Const_tarval(c1);
4522                 if (! tarval_is_long(tv1))
4523                         return irn_or;
4524
4525                 tv2 = get_Const_tarval(c2);
4526                 if (! tarval_is_long(tv2))
4527                         return irn_or;
4528
4529                 if (get_tarval_long(tv1) + get_tarval_long(tv2)
4530                                 != (int) get_mode_size_bits(mode))
4531                         return irn_or;
4532
4533                 /* yet, condition met */
4534                 block = get_nodes_block(irn_or);
4535
4536                 n = new_r_Rotl(block, x, c1, mode);
4537
4538                 DBG_OPT_ALGSIM1(irn_or, shl, shr, n, FS_OPT_OR_SHFT_TO_ROTL);
4539                 return n;
4540         }
4541
4542         /* Note: the obvious rot formulation (a << x) | (a >> (32-x)) gets
4543          * transformed to (a << x) | (a >> -x) by transform_node_shift_modulo() */
4544         if (!ir_is_negated_value(c1, c2)) {
4545                 return irn_or;
4546         }
4547
4548         /* yet, condition met */
4549         block = get_nodes_block(irn_or);
4550         n = new_r_Rotl(block, x, c1, mode);
4551         DBG_OPT_ALGSIM0(irn_or, n, FS_OPT_OR_SHFT_TO_ROTL);
4552         return n;
4553 }  /* transform_node_Or_Rotl */
4554
4555 static bool is_cmp_unequal_zero(const ir_node *node)
4556 {
4557         ir_relation relation = get_Cmp_relation(node);
4558         ir_node    *left     = get_Cmp_left(node);
4559         ir_node    *right    = get_Cmp_right(node);
4560         ir_mode    *mode     = get_irn_mode(left);
4561
4562         if (!is_Const(right) || !is_Const_null(right))
4563                 return false;
4564         if (mode_is_signed(mode)) {
4565                 return relation == ir_relation_less_greater;
4566         } else {
4567                 return relation == ir_relation_greater;
4568         }
4569 }
4570
4571 /**
4572  * Transform an Or.
4573  */
4574 static ir_node *transform_node_Or(ir_node *n)
4575 {
4576         ir_node *c, *oldn = n;
4577         ir_node *a = get_Or_left(n);
4578         ir_node *b = get_Or_right(n);
4579         ir_mode *mode;
4580
4581         if (is_Not(a) && is_Not(b)) {
4582                 /* ~a | ~b = ~(a&b) */
4583                 ir_node *block = get_nodes_block(n);
4584
4585                 mode = get_irn_mode(n);
4586                 a = get_Not_op(a);
4587                 b = get_Not_op(b);
4588                 n = new_rd_And(get_irn_dbg_info(n), block, a, b, mode);
4589                 n = new_rd_Not(get_irn_dbg_info(n), block, n, mode);
4590                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_DEMORGAN);
4591                 return n;
4592         }
4593
4594         /* we can combine the relations of two compares with the same operands */
4595         if (is_Cmp(a) && is_Cmp(b)) {
4596                 ir_node *a_left  = get_Cmp_left(a);
4597                 ir_node *a_right = get_Cmp_left(a);
4598                 ir_node *b_left  = get_Cmp_left(b);
4599                 ir_node *b_right = get_Cmp_right(b);
4600                 if (a_left == b_left && b_left == b_right) {
4601                         dbg_info   *dbgi         = get_irn_dbg_info(n);
4602                         ir_node    *block        = get_nodes_block(n);
4603                         ir_relation a_relation   = get_Cmp_relation(a);
4604                         ir_relation b_relation   = get_Cmp_relation(b);
4605                         ir_relation new_relation = a_relation | b_relation;
4606                         return new_rd_Cmp(dbgi, block, a_left, a_right, new_relation);
4607                 }
4608                 /* Cmp(a!=0) or Cmp(b!=0) => Cmp(a|b != 0) */
4609                 if (is_cmp_unequal_zero(a) && is_cmp_unequal_zero(b)
4610                                 && !mode_is_float(get_irn_mode(a_left))
4611                                 && !mode_is_float(get_irn_mode(b_left))) {
4612                         ir_graph *irg      = get_irn_irg(n);
4613                         dbg_info *dbgi     = get_irn_dbg_info(n);
4614                         ir_node  *block    = get_nodes_block(n);
4615                         ir_mode  *mode     = get_irn_mode(a_left);
4616                         ir_node  *n_b_left = get_irn_mode(b_left) != mode ?
4617                                 new_rd_Conv(dbgi, block, b_left, mode) : b_left;
4618                         ir_node  *or   = new_rd_Or(dbgi, block, a_left, n_b_left, mode);
4619                         ir_node  *zero = create_zero_const(irg, mode);
4620                         return new_rd_Cmp(dbgi, block, or, zero, ir_relation_less_greater);
4621                 }
4622         }
4623
4624         mode = get_irn_mode(n);
4625         HANDLE_BINOP_PHI((eval_func) tarval_or, a, b, c, mode);
4626
4627         n = transform_node_Or_bf_store(n);
4628         n = transform_node_Or_Rotl(n);
4629         if (n != oldn)
4630                 return n;
4631
4632         n = transform_bitwise_distributive(n, transform_node_Or);
4633
4634         return n;
4635 }  /* transform_node_Or */
4636
4637
4638 /* forward */
4639 static ir_node *transform_node(ir_node *n);
4640
4641 /**
4642  * Optimize (a >> c1) >> c2), works for Shr, Shrs, Shl, Rotl.
4643  *
4644  * Should be moved to reassociation?
4645  */
4646 static ir_node *transform_node_shift(ir_node *n)
4647 {
4648         ir_node *left, *right;
4649         ir_mode *mode;
4650         ir_tarval *tv1, *tv2, *res;
4651         ir_node *in[2], *irn, *block;
4652         ir_graph *irg;
4653         int       modulo_shf;
4654
4655         left = get_binop_left(n);
4656
4657         /* different operations */
4658         if (get_irn_op(left) != get_irn_op(n))
4659                 return n;
4660
4661         right = get_binop_right(n);
4662         tv1   = value_of(right);
4663         if (tv1 == tarval_bad)
4664                 return n;
4665
4666         tv2 = value_of(get_binop_right(left));
4667         if (tv2 == tarval_bad)
4668                 return n;
4669
4670         mode       = get_irn_mode(n);
4671         modulo_shf = get_mode_modulo_shift(mode);
4672
4673         if (modulo_shf > 0) {
4674                 ir_mode   *sc_mode     = get_tarval_mode(tv1);
4675                 ir_tarval *modulo_mask = new_tarval_from_long(modulo_shf-1, sc_mode);
4676
4677                 /* modulo shifts should always be a power of 2 (otherwise modulo_mask
4678                  * above will be invalid) */
4679                 assert(modulo_shf<=0 || is_po2(modulo_shf));
4680
4681                 tv1 = tarval_and(tv1, modulo_mask);
4682                 tv2 = tarval_and(tv2, modulo_mask);
4683         }
4684         res  = tarval_add(tv1, tv2);
4685         irg  = get_irn_irg(n);
4686
4687         /* beware: a simple replacement works only, if res < modulo shift */
4688         if (!is_Rotl(n)) {
4689                 if (modulo_shf > 0) {
4690                         ir_tarval *modulo = new_tarval_from_long(modulo_shf,
4691                                                                  get_tarval_mode(res));
4692
4693                         assert(modulo_shf >= (int) get_mode_size_bits(mode));
4694
4695                         /* shifting too much */
4696                         if (!(tarval_cmp(res, modulo) & ir_relation_less)) {
4697                                 if (is_Shrs(n)) {
4698                                         ir_node  *block = get_nodes_block(n);
4699                                         dbg_info *dbgi  = get_irn_dbg_info(n);
4700                                         ir_mode  *smode = get_irn_mode(right);
4701                                         ir_node  *cnst  = new_r_Const_long(irg, smode, get_mode_size_bits(mode) - 1);
4702                                         return new_rd_Shrs(dbgi, block, get_binop_left(left), cnst, mode);
4703                                 }
4704
4705                                 return new_r_Const(irg, get_mode_null(mode));
4706                         }
4707                 }
4708         } else {
4709                 res = tarval_mod(res, new_tarval_from_long(get_mode_size_bits(mode), get_tarval_mode(res)));
4710         }
4711
4712         /* ok, we can replace it */
4713         block = get_nodes_block(n);
4714
4715         in[0] = get_binop_left(left);
4716         in[1] = new_r_Const(irg, res);
4717
4718         irn = new_ir_node(NULL, get_Block_irg(block), block, get_irn_op(n), mode, 2, in);
4719
4720         DBG_OPT_ALGSIM0(n, irn, FS_OPT_REASSOC_SHIFT);
4721
4722         return transform_node(irn);
4723 }  /* transform_node_shift */
4724
4725 /**
4726  * normalisation: (x & c1) >> c2   to   (x >> c2) & (c1 >> c2)
4727  *  (we can use:
4728  *    - and, or, xor          instead of &
4729  *    - Shl, Shr, Shrs, rotl  instead of >>
4730  *    (with a special case for Or/Xor + Shrs)
4731  */
4732 static ir_node *transform_node_bitop_shift(ir_node *n)
4733 {
4734         ir_node   *left;
4735         ir_node   *right = get_binop_right(n);
4736         ir_mode   *mode  = get_irn_mode(n);
4737         ir_node   *bitop_left;
4738         ir_node   *bitop_right;
4739         ir_op     *op_left;
4740         ir_node   *block;
4741         dbg_info  *dbgi;
4742         ir_graph  *irg;
4743         ir_node   *new_shift;
4744         ir_node   *new_bitop;
4745         ir_node   *new_const;
4746         ir_tarval *tv1;
4747         ir_tarval *tv2;
4748         ir_tarval *tv_shift;
4749
4750         assert(is_Shrs(n) || is_Shr(n) || is_Shl(n) || is_Rotl(n));
4751
4752         if (!is_Const(right))
4753                 return n;
4754
4755         left    = get_binop_left(n);
4756         op_left = get_irn_op(left);
4757         if (op_left != op_And && op_left != op_Or && op_left != op_Eor)
4758                 return n;
4759
4760         /* doing it with Shrs is not legal if the Or/Eor affects the topmost bit */
4761         if (is_Shrs(n) && (op_left == op_Or || op_left == op_Eor)) {
4762                 /* TODO: test if sign bit is affectes */
4763                 return n;
4764         }
4765
4766         bitop_right = get_binop_right(left);
4767         if (!is_Const(bitop_right))
4768                 return n;
4769
4770         bitop_left = get_binop_left(left);
4771
4772         block = get_nodes_block(n);
4773         dbgi  = get_irn_dbg_info(n);
4774         tv1   = get_Const_tarval(bitop_right);
4775         tv2   = get_Const_tarval(right);
4776
4777         assert(get_tarval_mode(tv1) == mode);
4778
4779         if (is_Shl(n)) {
4780                 new_shift = new_rd_Shl(dbgi, block, bitop_left, right, mode);
4781                 tv_shift  = tarval_shl(tv1, tv2);
4782         } else if (is_Shr(n)) {
4783                 new_shift = new_rd_Shr(dbgi, block, bitop_left, right, mode);
4784                 tv_shift  = tarval_shr(tv1, tv2);
4785         } else if (is_Shrs(n)) {
4786                 new_shift = new_rd_Shrs(dbgi, block, bitop_left, right, mode);
4787                 tv_shift  = tarval_shrs(tv1, tv2);
4788         } else {
4789                 assert(is_Rotl(n));
4790                 new_shift = new_rd_Rotl(dbgi, block, bitop_left, right, mode);
4791                 tv_shift  = tarval_rotl(tv1, tv2);
4792         }
4793
4794         assert(get_tarval_mode(tv_shift) == mode);
4795         irg       = get_irn_irg(n);
4796         new_const = new_r_Const(irg, tv_shift);
4797
4798         if (op_left == op_And) {
4799                 new_bitop = new_rd_And(dbgi, block, new_shift, new_const, mode);
4800         } else if (op_left == op_Or) {
4801                 new_bitop = new_rd_Or(dbgi, block, new_shift, new_const, mode);
4802         } else {
4803                 assert(op_left == op_Eor);
4804                 new_bitop = new_rd_Eor(dbgi, block, new_shift, new_const, mode);
4805         }
4806
4807         return new_bitop;
4808 }
4809
4810 /**
4811  * normalisation:
4812  *    (x << c1) >> c2  <=>  x OP (c2-c1) & ((-1 << c1) >> c2)
4813  *    also:
4814  *    (x >> c1) << c2  <=>  x OP (c2-c1) & ((-1 >> c1) << c2)
4815  *      (also with x >>s c1  when c1>=c2)
4816  */
4817 static ir_node *transform_node_shl_shr(ir_node *n)
4818 {
4819         ir_node   *left;
4820         ir_node   *right = get_binop_right(n);
4821         ir_node   *x;
4822         ir_node   *block;
4823         ir_mode   *mode;
4824         dbg_info  *dbgi;
4825         ir_node   *new_const;
4826         ir_node   *new_shift;
4827         ir_node   *new_and;
4828         ir_tarval *tv_shl;
4829         ir_tarval *tv_shr;
4830         ir_tarval *tv_shift;
4831         ir_tarval *tv_mask;
4832         ir_graph  *irg;
4833         ir_relation relation;
4834         int        need_shrs = 0;
4835
4836         assert(is_Shl(n) || is_Shr(n) || is_Shrs(n));
4837
4838         if (!is_Const(right))
4839                 return n;
4840
4841         left = get_binop_left(n);
4842         mode = get_irn_mode(n);
4843         if (is_Shl(n) && (is_Shr(left) || is_Shrs(left))) {
4844                 ir_node *shr_right = get_binop_right(left);
4845
4846                 if (!is_Const(shr_right))
4847                         return n;
4848
4849                 x      = get_binop_left(left);
4850                 tv_shr = get_Const_tarval(shr_right);
4851                 tv_shl = get_Const_tarval(right);
4852
4853                 if (is_Shrs(left)) {
4854                         /* shrs variant only allowed if c1 >= c2 */
4855                         if (! (tarval_cmp(tv_shl, tv_shr) & ir_relation_greater_equal))
4856                                 return n;
4857
4858                         tv_mask = tarval_shrs(get_mode_all_one(mode), tv_shr);
4859                         need_shrs = 1;
4860                 } else {
4861                         tv_mask = tarval_shr(get_mode_all_one(mode), tv_shr);
4862                 }
4863                 tv_mask = tarval_shl(tv_mask, tv_shl);
4864         } else if (is_Shr(n) && is_Shl(left)) {
4865                 ir_node *shl_right = get_Shl_right(left);
4866
4867                 if (!is_Const(shl_right))
4868                         return n;
4869
4870                 x      = get_Shl_left(left);
4871                 tv_shr = get_Const_tarval(right);
4872                 tv_shl = get_Const_tarval(shl_right);
4873
4874                 tv_mask = tarval_shl(get_mode_all_one(mode), tv_shl);
4875                 tv_mask = tarval_shr(tv_mask, tv_shr);
4876         } else {
4877                 return n;
4878         }
4879
4880         if (get_tarval_mode(tv_shl) != get_tarval_mode(tv_shr)) {
4881                 tv_shl = tarval_convert_to(tv_shl, get_tarval_mode(tv_shr));
4882         }
4883
4884         assert(tv_mask != tarval_bad);
4885         assert(get_tarval_mode(tv_mask) == mode);
4886
4887         block = get_nodes_block(n);
4888         irg   = get_irn_irg(block);
4889         dbgi  = get_irn_dbg_info(n);
4890
4891         relation = tarval_cmp(tv_shl, tv_shr);
4892         if (relation == ir_relation_less || relation == ir_relation_equal) {
4893                 tv_shift  = tarval_sub(tv_shr, tv_shl, NULL);
4894                 new_const = new_r_Const(irg, tv_shift);
4895                 if (need_shrs) {
4896                         new_shift = new_rd_Shrs(dbgi, block, x, new_const, mode);
4897                 } else {
4898                         new_shift = new_rd_Shr(dbgi, block, x, new_const, mode);
4899                 }
4900         } else {
4901                 assert(relation == ir_relation_greater);
4902                 tv_shift  = tarval_sub(tv_shl, tv_shr, NULL);
4903                 new_const = new_r_Const(irg, tv_shift);
4904                 new_shift = new_rd_Shl(dbgi, block, x, new_const, mode);
4905         }
4906
4907         new_const = new_r_Const(irg, tv_mask);
4908         new_and   = new_rd_And(dbgi, block, new_shift, new_const, mode);
4909
4910         return new_and;
4911 }
4912
4913 static ir_tarval *get_modulo_tv_value(ir_tarval *tv, int modulo_val)
4914 {
4915         ir_mode   *mode      = get_tarval_mode(tv);
4916         ir_tarval *modulo_tv = new_tarval_from_long(modulo_val, mode);
4917         return tarval_mod(tv, modulo_tv);
4918 }
4919
4920 typedef ir_node*(*new_shift_func)(dbg_info *dbgi, ir_node *block,
4921                                   ir_node *left, ir_node *right, ir_mode *mode);
4922
4923 /**
4924  * Normalisation: if we have a shl/shr with modulo_shift behaviour
4925  * then we can use that to minimize the value of Add(x, const) or
4926  * Sub(Const, x). In particular this often avoids 1 instruction in some
4927  * backends for the Shift(x, Sub(Const, y)) case because it can be replaced
4928  * by Shift(x, Minus(y)) which doesnt't need an explicit Const constructed.
4929  */
4930 static ir_node *transform_node_shift_modulo(ir_node *n,
4931                                             new_shift_func new_shift)
4932 {
4933         ir_mode  *mode   = get_irn_mode(n);
4934         int       modulo = get_mode_modulo_shift(mode);
4935         ir_node  *newop  = NULL;
4936         ir_mode  *mode_right;
4937         ir_node  *block;
4938         ir_node  *right;
4939         ir_graph *irg;
4940
4941         if (modulo == 0)
4942                 return n;
4943         if (get_mode_arithmetic(mode) != irma_twos_complement)
4944                 return n;
4945         if (!is_po2(modulo))
4946                 return n;
4947
4948         irg        = get_irn_irg(n);
4949         block      = get_nodes_block(n);
4950         right      = get_binop_right(n);
4951         mode_right = get_irn_mode(right);
4952         if (is_Const(right)) {
4953                 ir_tarval *tv     = get_Const_tarval(right);
4954                 ir_tarval *tv_mod = get_modulo_tv_value(tv, modulo);
4955
4956                 if (tv_mod == tv)
4957                         return n;
4958
4959                 newop = new_r_Const(irg, tv_mod);
4960         } else if (is_Add(right)) {
4961                 ir_node *add_right = get_Add_right(right);
4962                 if (is_Const(add_right)) {
4963                         ir_tarval *tv     = get_Const_tarval(add_right);
4964                         ir_tarval *tv_mod = get_modulo_tv_value(tv, modulo);
4965                         ir_node   *newconst;
4966                         if (tv_mod == tv)
4967                                 return n;
4968
4969                         newconst = new_r_Const(irg, tv_mod);
4970                         newop    = new_r_Add(block, get_Add_left(right), newconst,
4971                                              mode_right);
4972                 }
4973         } else if (is_Sub(right)) {
4974                 ir_node *sub_left = get_Sub_left(right);
4975                 if (is_Const(sub_left)) {
4976                         ir_tarval *tv     = get_Const_tarval(sub_left);
4977                         ir_tarval *tv_mod = get_modulo_tv_value(tv, modulo);
4978                         ir_node  *newconst;
4979                         if (tv_mod == tv)
4980                                 return n;
4981
4982                         newconst = new_r_Const(irg, tv_mod);
4983                         newop    = new_r_Sub(block, newconst, get_Sub_right(right),
4984                                              mode_right);
4985                 }
4986         } else {
4987                 return n;
4988         }
4989
4990         if (newop != NULL) {
4991                 dbg_info *dbgi = get_irn_dbg_info(n);
4992                 ir_node  *left = get_binop_left(n);
4993                 return new_shift(dbgi, block, left, newop, mode);
4994         }
4995         return n;
4996 }
4997
4998 /**
4999  * Transform a Shr.
5000  */
5001 static ir_node *transform_node_Shr(ir_node *n)
5002 {
5003         ir_node *c, *oldn = n;
5004         ir_node *left  = get_Shr_left(n);
5005         ir_node *right = get_Shr_right(n);
5006         ir_mode *mode  = get_irn_mode(n);
5007
5008         HANDLE_BINOP_PHI((eval_func) tarval_shr, left, right, c, mode);
5009         n = transform_node_shift(n);
5010
5011         if (is_Shr(n))
5012                 n = transform_node_shift_modulo(n, new_rd_Shr);
5013         if (is_Shr(n))
5014                 n = transform_node_shl_shr(n);
5015         if (is_Shr(n))
5016                 n = transform_node_bitop_shift(n);
5017
5018         return n;
5019 }  /* transform_node_Shr */
5020
5021 /**
5022  * Transform a Shrs.
5023  */
5024 static ir_node *transform_node_Shrs(ir_node *n)
5025 {
5026         ir_node *c, *oldn = n;
5027         ir_node *a    = get_Shrs_left(n);
5028         ir_node *b    = get_Shrs_right(n);
5029         ir_mode *mode = get_irn_mode(n);
5030
5031         HANDLE_BINOP_PHI((eval_func) tarval_shrs, a, b, c, mode);
5032         n = transform_node_shift(n);
5033
5034         if (is_Shrs(n))
5035                 n = transform_node_shift_modulo(n, new_rd_Shrs);
5036         if (is_Shrs(n))
5037                 n = transform_node_bitop_shift(n);
5038
5039         return n;
5040 }  /* transform_node_Shrs */
5041
5042 /**
5043  * Transform a Shl.
5044  */
5045 static ir_node *transform_node_Shl(ir_node *n)
5046 {
5047         ir_node *c, *oldn = n;
5048         ir_node *a    = get_Shl_left(n);
5049         ir_node *b    = get_Shl_right(n);
5050         ir_mode *mode = get_irn_mode(n);
5051
5052         HANDLE_BINOP_PHI((eval_func) tarval_shl, a, b, c, mode);
5053         n = transform_node_shift(n);
5054
5055         if (is_Shl(n))
5056                 n = transform_node_shift_modulo(n, new_rd_Shl);
5057         if (is_Shl(n))
5058                 n = transform_node_shl_shr(n);
5059         if (is_Shl(n))
5060                 n = transform_node_bitop_shift(n);
5061
5062         return n;
5063 }  /* transform_node_Shl */
5064
5065 /**
5066  * Transform a Rotl.
5067  */
5068 static ir_node *transform_node_Rotl(ir_node *n)
5069 {
5070         ir_node *c, *oldn = n;
5071         ir_node *a    = get_Rotl_left(n);
5072         ir_node *b    = get_Rotl_right(n);
5073         ir_mode *mode = get_irn_mode(n);
5074
5075         HANDLE_BINOP_PHI((eval_func) tarval_rotl, a, b, c, mode);
5076         n = transform_node_shift(n);
5077
5078         if (is_Rotl(n))
5079                 n = transform_node_bitop_shift(n);
5080
5081         return n;
5082 }  /* transform_node_Rotl */
5083
5084 /**
5085  * Transform a Conv.
5086  */
5087 static ir_node *transform_node_Conv(ir_node *n)
5088 {
5089         ir_node *c, *oldn = n;
5090         ir_mode *mode = get_irn_mode(n);
5091         ir_node *a    = get_Conv_op(n);
5092
5093         if (mode != mode_b && is_const_Phi(a)) {
5094                 /* Do NOT optimize mode_b Conv's, this leads to remaining
5095                  * Phib nodes later, because the conv_b_lower operation
5096                  * is instantly reverted, when it tries to insert a Convb.
5097                  */
5098                 c = apply_conv_on_phi(a, mode);
5099                 if (c) {
5100                         DBG_OPT_ALGSIM0(oldn, c, FS_OPT_CONST_PHI);
5101                         return c;
5102                 }
5103         }
5104
5105         if (is_Unknown(a)) { /* Conv_A(Unknown_B) -> Unknown_A */
5106                 ir_graph *irg = get_irn_irg(n);
5107                 return new_r_Unknown(irg, mode);
5108         }
5109
5110         if (mode_is_reference(mode) &&
5111                 get_mode_size_bits(mode) == get_mode_size_bits(get_irn_mode(a)) &&
5112                 is_Add(a)) {
5113                 ir_node *l = get_Add_left(a);
5114                 ir_node *r = get_Add_right(a);
5115                 dbg_info *dbgi = get_irn_dbg_info(a);
5116                 ir_node *block = get_nodes_block(n);
5117                 if (is_Conv(l)) {
5118                         ir_node *lop = get_Conv_op(l);
5119                         if (get_irn_mode(lop) == mode) {
5120                                 /* ConvP(AddI(ConvI(P), x)) -> AddP(P, x) */
5121                                 n = new_rd_Add(dbgi, block, lop, r, mode);
5122                                 return n;
5123                         }
5124                 }
5125                 if (is_Conv(r)) {
5126                         ir_node *rop = get_Conv_op(r);
5127                         if (get_irn_mode(rop) == mode) {
5128                                 /* ConvP(AddI(x, ConvI(P))) -> AddP(x, P) */
5129                                 n = new_rd_Add(dbgi, block, l, rop, mode);
5130                                 return n;
5131                         }
5132                 }
5133         }
5134
5135         return n;
5136 }  /* transform_node_Conv */
5137
5138 /**
5139  * Remove dead blocks and nodes in dead blocks
5140  * in keep alive list.  We do not generate a new End node.
5141  */
5142 static ir_node *transform_node_End(ir_node *n)
5143 {
5144         int i, j, n_keepalives = get_End_n_keepalives(n);
5145         ir_node **in;
5146
5147         NEW_ARR_A(ir_node *, in, n_keepalives);
5148
5149         for (i = j = 0; i < n_keepalives; ++i) {
5150                 ir_node *ka = get_End_keepalive(n, i);
5151                 ir_node *block;
5152                 /* no need to keep Bad */
5153                 if (is_Bad(ka))
5154                         continue;
5155                 /* dont keep unreachable code */
5156                 block = is_Block(ka) ? ka : get_nodes_block(ka);
5157                 if (is_block_unreachable(block))
5158                         continue;
5159                 in[j++] = ka;
5160         }
5161         if (j != n_keepalives)
5162                 set_End_keepalives(n, j, in);
5163         return n;
5164 }  /* transform_node_End */
5165
5166 int ir_is_negated_value(const ir_node *a, const ir_node *b)
5167 {
5168         if (is_Minus(a) && get_Minus_op(a) == b)
5169                 return true;
5170         if (is_Minus(b) && get_Minus_op(b) == a)
5171                 return true;
5172         if (is_Sub(a) && is_Sub(b)) {
5173                 ir_node *a_left  = get_Sub_left(a);
5174                 ir_node *a_right = get_Sub_right(a);
5175                 ir_node *b_left  = get_Sub_left(b);
5176                 ir_node *b_right = get_Sub_right(b);
5177
5178                 if (a_left == b_right && a_right == b_left)
5179                         return true;
5180         }
5181
5182         return false;
5183 }
5184
5185 /**
5186  * Optimize a Mux into some simpler cases.
5187  */
5188 static ir_node *transform_node_Mux(ir_node *n)
5189 {
5190         ir_node *oldn = n, *sel = get_Mux_sel(n);
5191         ir_mode *mode = get_irn_mode(n);
5192         ir_node  *t   = get_Mux_true(n);
5193         ir_node  *f   = get_Mux_false(n);
5194         ir_graph *irg = get_irn_irg(n);
5195
5196         if (is_irg_state(irg, IR_GRAPH_STATE_KEEP_MUX))
5197                 return n;
5198
5199         if (is_Mux(t)) {
5200                 ir_node*  block = get_nodes_block(n);
5201                 ir_node*  c0    = sel;
5202                 ir_node*  c1    = get_Mux_sel(t);
5203                 ir_node*  t1    = get_Mux_true(t);
5204                 ir_node*  f1    = get_Mux_false(t);
5205                 if (f == f1) {
5206                         /* Mux(cond0, Mux(cond1, x, y), y) -> typical if (cond0 && cond1) x else y */
5207                         ir_node* and_    = new_r_And(block, c0, c1, mode_b);
5208                         ir_node* new_mux = new_r_Mux(block, and_, f1, t1, mode);
5209                         n   = new_mux;
5210                         sel = and_;
5211                         f   = f1;
5212                         t   = t1;
5213                         DBG_OPT_ALGSIM0(oldn, t, FS_OPT_MUX_COMBINE);
5214                 } else if (f == t1) {
5215                         /* Mux(cond0, Mux(cond1, x, y), x) */
5216                         ir_node* not_c1  = new_r_Not(block, c1, mode_b);
5217                         ir_node* and_    = new_r_And(block, c0, not_c1, mode_b);
5218                         ir_node* new_mux = new_r_Mux(block, and_, t1, f1, mode);
5219                         n   = new_mux;
5220                         sel = and_;
5221                         f   = t1;
5222                         t   = f1;
5223                         DBG_OPT_ALGSIM0(oldn, t, FS_OPT_MUX_COMBINE);
5224                 }
5225         } else if (is_Mux(f)) {
5226                 ir_node*  block = get_nodes_block(n);
5227                 ir_node*  c0    = sel;
5228                 ir_node*  c1    = get_Mux_sel(f);
5229                 ir_node*  t1    = get_Mux_true(f);
5230                 ir_node*  f1    = get_Mux_false(f);
5231                 if (t == t1) {
5232                         /* Mux(cond0, x, Mux(cond1, x, y)) -> typical if (cond0 || cond1) x else y */
5233                         ir_node* or_     = new_r_Or(block, c0, c1, mode_b);
5234                         ir_node* new_mux = new_r_Mux(block, or_, f1, t1, mode);
5235                         n   = new_mux;
5236                         sel = or_;
5237                         f   = f1;
5238                         t   = t1;
5239                         DBG_OPT_ALGSIM0(oldn, f, FS_OPT_MUX_COMBINE);
5240                 } else if (t == f1) {
5241                         /* Mux(cond0, x, Mux(cond1, y, x)) */
5242                         ir_node* not_c1  = new_r_Not(block, c1, mode_b);
5243                         ir_node* or_     = new_r_Or(block, c0, not_c1, mode_b);
5244                         ir_node* new_mux = new_r_Mux(block, or_, t1, f1, mode);
5245                         n   = new_mux;
5246                         sel = or_;
5247                         f   = t1;
5248                         t   = f1;
5249                         DBG_OPT_ALGSIM0(oldn, f, FS_OPT_MUX_COMBINE);
5250                 }
5251         }
5252
5253         /* first normalization step: try to move a constant to the false side,
5254          * 0 preferred on false side too */
5255         if (is_Cmp(sel) && is_Const(t) &&
5256                         (!is_Const(f) || (is_Const_null(t) && !is_Const_null(f)))) {
5257                 dbg_info *seldbgi = get_irn_dbg_info(sel);
5258                 ir_node  *block   = get_nodes_block(sel);
5259                 ir_relation relation = get_Cmp_relation(sel);
5260                 ir_node *tmp = t;
5261                 t = f;
5262                 f = tmp;
5263
5264                 /* Mux(x, a, b) => Mux(not(x), b, a) */
5265                 relation = get_negated_relation(relation);
5266                 sel = new_rd_Cmp(seldbgi, block, get_Cmp_left(sel),
5267                                 get_Cmp_right(sel), relation);
5268                 n = new_rd_Mux(get_irn_dbg_info(n), get_nodes_block(n), sel, f, t, mode);
5269         }
5270
5271         /* note: after normalization, false can only happen on default */
5272         if (mode == mode_b) {
5273                 dbg_info *dbg   = get_irn_dbg_info(n);
5274                 ir_node  *block = get_nodes_block(n);
5275
5276                 if (is_Const(t)) {
5277                         ir_tarval *tv_t = get_Const_tarval(t);
5278                         if (tv_t == tarval_b_true) {
5279                                 if (is_Const(f)) {
5280                                         /* Muxb(sel, true, false) = sel */
5281                                         assert(get_Const_tarval(f) == tarval_b_false);
5282                                         DBG_OPT_ALGSIM0(oldn, sel, FS_OPT_MUX_BOOL);
5283                                         return sel;
5284                                 } else {
5285                                         /* Muxb(sel, true, x) = Or(sel, x) */
5286                                         n = new_rd_Or(dbg, block, sel, f, mode_b);
5287                                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_OR_BOOL);
5288                                         return n;
5289                                 }
5290                         }
5291                 } else if (is_Const(f)) {
5292                         ir_tarval *tv_f = get_Const_tarval(f);
5293                         if (tv_f == tarval_b_true) {
5294                                 /* Muxb(sel, x, true) = Or(Not(sel), x) */
5295                                 ir_node* not_sel = new_rd_Not(dbg, block, sel, mode_b);
5296                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_ORNOT_BOOL);
5297                                 n = new_rd_Or(dbg, block, not_sel, t, mode_b);
5298                                 return n;
5299                         } else {
5300                                 /* Muxb(sel, x, false) = And(sel, x) */
5301                                 assert(tv_f == tarval_b_false);
5302                                 n = new_rd_And(dbg, block, sel, t, mode_b);
5303                                 DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_AND_BOOL);
5304                                 return n;
5305                         }
5306                 }
5307         }
5308
5309         /* more normalization: Mux(sel, 0, 1) is simply a conv from the mode_b
5310          * value to integer. */
5311         if (is_Const(t) && is_Const(f) && mode_is_int(mode)) {
5312                 ir_tarval *a = get_Const_tarval(t);
5313                 ir_tarval *b = get_Const_tarval(f);
5314
5315                 if (tarval_is_one(a) && tarval_is_null(b)) {
5316                         ir_node *block = get_nodes_block(n);
5317                         ir_node *conv  = new_r_Conv(block, sel, mode);
5318                         n = conv;
5319                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_CONV);
5320                         return n;
5321                 } else if (tarval_is_null(a) && tarval_is_one(b)) {
5322                         ir_node *block = get_nodes_block(n);
5323                         ir_node *not_  = new_r_Not(block, sel, mode_b);
5324                         ir_node *conv  = new_r_Conv(block, not_, mode);
5325                         n = conv;
5326                         DBG_OPT_ALGSIM0(oldn, n, FS_OPT_MUX_CONV);
5327                         return n;
5328                 }
5329         }
5330
5331         if (is_Cmp(sel)) {
5332                 ir_node    *cmp_r    = get_Cmp_right(sel);
5333                 if (is_Const(cmp_r) && is_Const_null(cmp_r)) {
5334                         ir_node *block = get_nodes_block(n);
5335                         ir_node *cmp_l = get_Cmp_left(sel);
5336
5337                         if (mode_is_int(mode)) {
5338                                 ir_relation relation = get_Cmp_relation(sel);
5339                                 /* integer only */
5340                                 if ((relation == ir_relation_less_greater || relation == ir_relation_equal) && is_And(cmp_l)) {
5341                                         /* Mux((a & b) != 0, c, 0) */
5342                                         ir_node *and_r = get_And_right(cmp_l);
5343                                         ir_node *and_l;
5344
5345                                         if (and_r == t && f == cmp_r) {
5346                                                 if (is_Const(t) && tarval_is_single_bit(get_Const_tarval(t))) {
5347                                                         if (relation == ir_relation_less_greater) {
5348                                                                 /* Mux((a & 2^C) != 0, 2^C, 0) */
5349                                                                 n = cmp_l;
5350                                                                 DBG_OPT_ALGSIM1(oldn, sel, sel, n, FS_OPT_MUX_TO_BITOP);
5351                                                         } else {
5352                                                                 /* Mux((a & 2^C) == 0, 2^C, 0) */
5353                                                                 n = new_rd_Eor(get_irn_dbg_info(n),
5354                                                                         block, cmp_l, t, mode);
5355                                                                 DBG_OPT_ALGSIM1(oldn, sel, sel, n, FS_OPT_MUX_TO_BITOP);
5356                                                         }
5357                                                         return n;
5358                                                 }
5359                                         }
5360                                         if (is_Shl(and_r)) {
5361                                                 ir_node *shl_l = get_Shl_left(and_r);
5362                                                 if (is_Const(shl_l) && is_Const_one(shl_l)) {
5363                                                         if (and_r == t && f == cmp_r) {
5364                                                                 if (relation == ir_relation_less_greater) {
5365                                                                         /* (a & (1 << n)) != 0, (1 << n), 0) */
5366                                                                         n = cmp_l;
5367                                                                         DBG_OPT_ALGSIM1(oldn, sel, sel, n, FS_OPT_MUX_TO_BITOP);
5368                                                                 } else {
5369                                                                         /* (a & (1 << n)) == 0, (1 << n), 0) */
5370                                                                         n = new_rd_Eor(get_irn_dbg_info(n),
5371                                                                                 block, cmp_l, t, mode);
5372                                                                         DBG_OPT_ALGSIM1(oldn, sel, sel, n, FS_OPT_MUX_TO_BITOP);
5373                                                                 }
5374                                                                 return n;
5375                                                         }
5376                                                 }
5377                                         }
5378                                         and_l = get_And_left(cmp_l);
5379                                         if (is_Shl(and_l)) {
5380                                                 ir_node *shl_l = get_Shl_left(and_l);
5381                                                 if (is_Const(shl_l) && is_Const_one(shl_l)) {
5382                                                         if (and_l == t && f == cmp_r) {
5383                                                                 if (relation == ir_relation_less_greater) {
5384                                                                         /* ((1 << n) & a) != 0, (1 << n), 0) */
5385                                                                         n = cmp_l;
5386                                                                         DBG_OPT_ALGSIM1(oldn, sel, sel, n, FS_OPT_MUX_TO_BITOP);
5387                                                                 } else {
5388                                                                         /* ((1 << n) & a) == 0, (1 << n), 0) */
5389                                                                         n = new_rd_Eor(get_irn_dbg_info(n),
5390                                                                                 block, cmp_l, t, mode);
5391                                                                         DBG_OPT_ALGSIM1(oldn, sel, sel, n, FS_OPT_MUX_TO_BITOP);
5392                                                                 }
5393                                                                 return n;
5394                                                         }
5395                                                 }
5396                                         }
5397                                 }
5398                         }
5399                 }
5400         }
5401
5402         return n;
5403 }
5404
5405 /**
5406  * optimize Sync nodes that have other syncs as input we simply add the inputs
5407  * of the other sync to our own inputs
5408  */
5409 static ir_node *transform_node_Sync(ir_node *n)
5410 {
5411         int arity = get_Sync_n_preds(n);
5412         int i;
5413
5414         for (i = 0; i < arity;) {
5415                 ir_node *pred = get_Sync_pred(n, i);
5416                 int      pred_arity;
5417                 int      j;
5418
5419                 /* Remove Bad predecessors */
5420                 if (is_Bad(pred)) {
5421                         del_Sync_n(n, i);
5422                         --arity;
5423                         continue;
5424                 }
5425
5426                 /* Remove duplicate predecessors */
5427                 for (j = 0; j < i; ++j) {
5428                         if (get_Sync_pred(n, j) == pred) {
5429                                 del_Sync_n(n, i);
5430                                 --arity;
5431                                 break;
5432                         }
5433                 }
5434                 if (j < i)
5435                         continue;
5436
5437                 if (!is_Sync(pred)) {
5438                         ++i;
5439                         continue;
5440                 }
5441
5442                 del_Sync_n(n, i);
5443                 --arity;
5444
5445                 pred_arity = get_Sync_n_preds(pred);
5446                 for (j = 0; j < pred_arity; ++j) {
5447                         ir_node *pred_pred = get_Sync_pred(pred, j);
5448                         int      k;
5449
5450                         for (k = 0;; ++k) {
5451                                 if (k >= arity) {
5452                                         add_irn_n(n, pred_pred);
5453                                         ++arity;
5454                                         break;
5455                                 }
5456                                 if (get_Sync_pred(n, k) == pred_pred) break;
5457                         }
5458                 }
5459         }
5460
5461         if (arity == 0) {
5462                 ir_graph *irg = get_irn_irg(n);
5463                 return new_r_Bad(irg, mode_M);
5464         }
5465         if (arity == 1) {
5466                 return get_Sync_pred(n, 0);
5467         }
5468
5469         /* rehash the sync node */
5470         add_identities(n);
5471         return n;
5472 }
5473
5474 static ir_node *transform_node_Load(ir_node *n)
5475 {
5476         /* if our memory predecessor is a load from the same address, then reuse the
5477          * previous result */
5478         ir_node *mem = get_Load_mem(n);
5479         ir_node *mem_pred;
5480
5481         if (!is_Proj(mem))
5482                 return n;
5483         /* don't touch volatile loads */
5484         if (get_Load_volatility(n) == volatility_is_volatile)
5485                 return n;
5486         mem_pred = get_Proj_pred(mem);
5487         if (is_Load(mem_pred)) {
5488                 ir_node *pred_load = mem_pred;
5489
5490                 /* conservatively compare the 2 loads. TODO: This could be less strict
5491                  * with fixup code in some situations (like smaller/bigger modes) */
5492                 if (get_Load_ptr(pred_load) != get_Load_ptr(n))
5493                         return n;
5494                 if (get_Load_mode(pred_load) != get_Load_mode(n))
5495                         return n;
5496                 /* all combinations of aligned/unaligned pred/n should be fine so we do
5497                  * not compare the unaligned attribute */
5498                 {
5499                         ir_node  *block = get_nodes_block(n);
5500                         ir_node  *jmp   = new_r_Jmp(block);
5501                         ir_graph *irg   = get_irn_irg(n);
5502                         ir_node  *bad   = new_r_Bad(irg, mode_X);
5503                         ir_mode  *mode  = get_Load_mode(n);
5504                         ir_node  *res   = new_r_Proj(pred_load, mode, pn_Load_res);
5505                         ir_node  *in[pn_Load_max] = { mem, jmp, bad, res };
5506                         ir_node  *tuple = new_r_Tuple(block, ARRAY_SIZE(in), in);
5507                         return tuple;
5508                 }
5509         } else if (is_Store(mem_pred)) {
5510                 ir_node *pred_store = mem_pred;
5511                 ir_node *value      = get_Store_value(pred_store);
5512
5513                 if (get_Store_ptr(pred_store) != get_Load_ptr(n))
5514                         return n;
5515                 if (get_irn_mode(value) != get_Load_mode(n))
5516                         return n;
5517                 /* all combinations of aligned/unaligned pred/n should be fine so we do
5518                  * not compare the unaligned attribute */
5519                 {
5520                         ir_node  *block = get_nodes_block(n);
5521                         ir_node  *jmp   = new_r_Jmp(block);
5522                         ir_graph *irg   = get_irn_irg(n);
5523                         ir_node  *bad   = new_r_Bad(irg, mode_X);
5524                         ir_node  *res   = value;
5525                         ir_node  *in[pn_Load_max] = { mem, jmp, bad, res };
5526                         ir_node  *tuple = new_r_Tuple(block, ARRAY_SIZE(in), in);
5527                         return tuple;
5528                 }
5529         }
5530
5531         return n;
5532 }
5533
5534 /**
5535  * optimize a trampoline Call into a direct Call
5536  */
5537 static ir_node *transform_node_Call(ir_node *call)
5538 {
5539         ir_node  *callee = get_Call_ptr(call);
5540         ir_node  *adr, *mem, *res, *bl, **in;
5541         ir_type  *ctp, *mtp, *tp;
5542         ir_graph *irg;
5543         type_dbg_info *tdb;
5544         dbg_info *db;
5545         size_t   i, n_res, n_param;
5546         ir_variadicity var;
5547
5548         if (! is_Proj(callee))
5549                 return call;
5550         callee = get_Proj_pred(callee);
5551         if (! is_Builtin(callee))
5552                 return call;
5553         if (get_Builtin_kind(callee) != ir_bk_inner_trampoline)
5554                 return call;
5555
5556         mem = get_Call_mem(call);
5557
5558         if (skip_Proj(mem) == callee) {
5559                 /* memory is routed to the trampoline, skip */
5560                 mem = get_Builtin_mem(callee);
5561         }
5562
5563         /* build a new call type */
5564         mtp = get_Call_type(call);
5565         tdb = get_type_dbg_info(mtp);
5566
5567         n_res   = get_method_n_ress(mtp);
5568         n_param = get_method_n_params(mtp);
5569         ctp     = new_d_type_method(n_param + 1, n_res, tdb);
5570
5571         for (i = 0; i < n_res; ++i)
5572                 set_method_res_type(ctp, i, get_method_res_type(mtp, i));
5573
5574         NEW_ARR_A(ir_node *, in, n_param + 1);
5575
5576         /* FIXME: we don't need a new pointer type in every step */
5577         irg = get_irn_irg(call);
5578         tp = get_irg_frame_type(irg);
5579         tp = new_type_pointer(tp);
5580         set_method_param_type(ctp, 0, tp);
5581
5582         in[0] = get_Builtin_param(callee, 2);
5583         for (i = 0; i < n_param; ++i) {
5584                 set_method_param_type(ctp, i + 1, get_method_param_type(mtp, i));
5585                 in[i + 1] = get_Call_param(call, i);
5586         }
5587         var = get_method_variadicity(mtp);
5588         set_method_variadicity(ctp, var);
5589         /* When we resolve a trampoline, the function must be called by a this-call */
5590         set_method_calling_convention(ctp, get_method_calling_convention(mtp) | cc_this_call);
5591         set_method_additional_properties(ctp, get_method_additional_properties(mtp));
5592
5593         adr = get_Builtin_param(callee, 1);
5594
5595         db  = get_irn_dbg_info(call);
5596         bl  = get_nodes_block(call);
5597
5598         res = new_rd_Call(db, bl, mem, adr, n_param + 1, in, ctp);
5599         if (get_irn_pinned(call) == op_pin_state_floats)
5600                 set_irn_pinned(res, op_pin_state_floats);
5601         return res;
5602 }  /* transform_node_Call */
5603
5604 /**
5605  * Tries several [inplace] [optimizing] transformations and returns an
5606  * equivalent node.  The difference to equivalent_node() is that these
5607  * transformations _do_ generate new nodes, and thus the old node must
5608  * not be freed even if the equivalent node isn't the old one.
5609  */
5610 static ir_node *transform_node(ir_node *n)
5611 {
5612         ir_node *oldn;
5613
5614         /*
5615          * Transform_node is the only "optimizing transformation" that might
5616          * return a node with a different opcode. We iterate HERE until fixpoint
5617          * to get the final result.
5618          */
5619         do {
5620                 oldn = n;
5621                 if (n->op->ops.transform_node != NULL)
5622                         n = n->op->ops.transform_node(n);
5623         } while (oldn != n);
5624
5625         return n;
5626 }  /* transform_node */
5627
5628 /**
5629  * Sets the default transform node operation for an ir_op_ops.
5630  *
5631  * @param code   the opcode for the default operation
5632  * @param ops    the operations initialized
5633  *
5634  * @return
5635  *    The operations.
5636  */
5637 static ir_op_ops *firm_set_default_transform_node(ir_opcode code, ir_op_ops *ops)
5638 {
5639 #define CASE(a)                                         \
5640         case iro_##a:                                       \
5641                 ops->transform_node      = transform_node_##a;  \
5642                 break
5643 #define CASE_PROJ(a)                                         \
5644         case iro_##a:                                            \
5645                 ops->transform_node_Proj = transform_node_Proj_##a;  \
5646                 break
5647 #define CASE_PROJ_EX(a)                                      \
5648         case iro_##a:                                            \
5649                 ops->transform_node      = transform_node_##a;       \
5650                 ops->transform_node_Proj = transform_node_Proj_##a;  \
5651                 break
5652
5653         switch (code) {
5654         CASE(Add);
5655         CASE(And);
5656         CASE(Block);
5657         CASE(Call);
5658         CASE(Cmp);
5659         CASE(Conv);
5660         CASE(End);
5661         CASE(Eor);
5662         CASE(Minus);
5663         CASE(Mul);
5664         CASE(Mux);
5665         CASE(Not);
5666         CASE(Or);
5667         CASE(Phi);
5668         CASE(Proj);
5669         CASE(Rotl);
5670         CASE(Sel);
5671         CASE(Shl);
5672         CASE(Shr);
5673         CASE(Shrs);
5674         CASE(Sub);
5675         CASE(Sync);
5676         CASE_PROJ(Bound);
5677         CASE_PROJ(CopyB);
5678         CASE_PROJ(Store);
5679         CASE_PROJ_EX(Cond);
5680         CASE_PROJ_EX(Div);
5681         CASE_PROJ_EX(Load);
5682         CASE_PROJ_EX(Mod);
5683         default:
5684           /* leave NULL */;
5685         }
5686
5687         return ops;
5688 #undef CASE_PROJ_EX
5689 #undef CASE_PROJ
5690 #undef CASE
5691 }  /* firm_set_default_transform_node */
5692
5693
5694 /* **************** Common Subexpression Elimination **************** */
5695
5696 /** The size of the hash table used, should estimate the number of nodes
5697     in a graph. */
5698 #define N_IR_NODES 512
5699
5700 /** Compares the attributes of two Const nodes. */
5701 static int node_cmp_attr_Const(const ir_node *a, const ir_node *b)
5702 {
5703         return get_Const_tarval(a) != get_Const_tarval(b);
5704 }
5705
5706 /** Compares the attributes of two Proj nodes. */
5707 static int node_cmp_attr_Proj(const ir_node *a, const ir_node *b)
5708 {
5709         return a->attr.proj.proj != b->attr.proj.proj;
5710 }
5711
5712 /** Compares the attributes of two Alloc nodes. */
5713 static int node_cmp_attr_Alloc(const ir_node *a, const ir_node *b)
5714 {
5715         const alloc_attr *pa = &a->attr.alloc;
5716         const alloc_attr *pb = &b->attr.alloc;
5717         return (pa->where != pb->where) || (pa->type != pb->type);
5718 }
5719
5720 /** Compares the attributes of two Free nodes. */
5721 static int node_cmp_attr_Free(const ir_node *a, const ir_node *b)
5722 {
5723         const free_attr *pa = &a->attr.free;
5724         const free_attr *pb = &b->attr.free;
5725         return (pa->where != pb->where) || (pa->type != pb->type);
5726 }
5727
5728 /** Compares the attributes of two SymConst nodes. */
5729 static int node_cmp_attr_SymConst(const ir_node *a, const ir_node *b)
5730 {
5731         const symconst_attr *pa = &a->attr.symc;
5732         const symconst_attr *pb = &b->attr.symc;
5733         return (pa->kind       != pb->kind)
5734             || (pa->sym.type_p != pb->sym.type_p);
5735 }
5736
5737 /** Compares the attributes of two Call nodes. */
5738 static int node_cmp_attr_Call(const ir_node *a, const ir_node *b)
5739 {
5740         const call_attr *pa = &a->attr.call;
5741         const call_attr *pb = &b->attr.call;
5742         return (pa->type != pb->type)
5743                 || (pa->tail_call != pb->tail_call);
5744 }
5745
5746 /** Compares the attributes of two Sel nodes. */
5747 static int node_cmp_attr_Sel(const ir_node *a, const ir_node *b)
5748 {
5749         const ir_entity *a_ent = get_Sel_entity(a);
5750         const ir_entity *b_ent = get_Sel_entity(b);
5751         return a_ent != b_ent;
5752 }
5753
5754 /** Compares the attributes of two Phi nodes. */
5755 static int node_cmp_attr_Phi(const ir_node *a, const ir_node *b)
5756 {
5757         /* we can only enter this function if both nodes have the same number of inputs,
5758            hence it is enough to check if one of them is a Phi0 */
5759         if (is_Phi0(a)) {
5760                 /* check the Phi0 pos attribute */
5761                 return a->attr.phi.u.pos != b->attr.phi.u.pos;
5762         }
5763         return 0;
5764 }
5765
5766 /** Compares the attributes of two Conv nodes. */
5767 static int node_cmp_attr_Conv(const ir_node *a, const ir_node *b)
5768 {
5769         return get_Conv_strict(a) != get_Conv_strict(b);
5770 }
5771
5772 /** Compares the attributes of two Cast nodes. */
5773 static int node_cmp_attr_Cast(const ir_node *a, const ir_node *b)
5774 {
5775         return get_Cast_type(a) != get_Cast_type(b);
5776 }
5777
5778 /** Compares the attributes of two Load nodes. */
5779 static int node_cmp_attr_Load(const ir_node *a, const ir_node *b)
5780 {
5781         if (get_Load_volatility(a) == volatility_is_volatile ||
5782             get_Load_volatility(b) == volatility_is_volatile)
5783                 /* NEVER do CSE on volatile Loads */
5784                 return 1;
5785         /* do not CSE Loads with different alignment. Be conservative. */
5786         if (get_Load_unaligned(a) != get_Load_unaligned(b))
5787                 return 1;
5788
5789         return get_Load_mode(a) != get_Load_mode(b);
5790 }
5791
5792 /** Compares the attributes of two Store nodes. */
5793 static int node_cmp_attr_Store(const ir_node *a, const ir_node *b)
5794 {
5795         /* do not CSE Stores with different alignment. Be conservative. */
5796         if (get_Store_unaligned(a) != get_Store_unaligned(b))
5797                 return 1;
5798
5799         /* NEVER do CSE on volatile Stores */
5800         return (get_Store_volatility(a) == volatility_is_volatile ||
5801                 get_Store_volatility(b) == volatility_is_volatile);
5802 }
5803
5804 /** Compares two exception attributes */
5805 static int node_cmp_exception(const ir_node *a, const ir_node *b)
5806 {
5807         const except_attr *ea = &a->attr.except;
5808         const except_attr *eb = &b->attr.except;
5809
5810         return ea->pin_state != eb->pin_state;
5811 }
5812
5813 #define node_cmp_attr_Bound  node_cmp_exception
5814
5815 /** Compares the attributes of two Div nodes. */
5816 static int node_cmp_attr_Div(const ir_node *a, const ir_node *b)
5817 {
5818         const div_attr *ma = &a->attr.div;
5819         const div_attr *mb = &b->attr.div;
5820         return ma->exc.pin_state != mb->exc.pin_state ||
5821                    ma->resmode       != mb->resmode ||
5822                    ma->no_remainder  != mb->no_remainder;
5823 }
5824
5825 /** Compares the attributes of two Mod nodes. */
5826 static int node_cmp_attr_Mod(const ir_node *a, const ir_node *b)
5827 {
5828         const mod_attr *ma = &a->attr.mod;
5829         const mod_attr *mb = &b->attr.mod;
5830         return ma->exc.pin_state != mb->exc.pin_state ||
5831                    ma->resmode       != mb->resmode;
5832 }
5833
5834 static int node_cmp_attr_Cmp(const ir_node *a, const ir_node *b)
5835 {
5836         const cmp_attr *ma = &a->attr.cmp;
5837         const cmp_attr *mb = &b->attr.cmp;
5838         return ma->relation != mb->relation;
5839 }
5840
5841 /** Compares the attributes of two Confirm nodes. */
5842 static int node_cmp_attr_Confirm(const ir_node *a, const ir_node *b)
5843 {
5844         const confirm_attr *ma = &a->attr.confirm;
5845         const confirm_attr *mb = &b->attr.confirm;
5846         return ma->relation != mb->relation;
5847 }
5848
5849 /** Compares the attributes of two Builtin nodes. */
5850 static int node_cmp_attr_Builtin(const ir_node *a, const ir_node *b)
5851 {
5852         /* no need to compare the type, equal kind means equal type */
5853         return get_Builtin_kind(a) != get_Builtin_kind(b);
5854 }
5855
5856 /** Compares the attributes of two ASM nodes. */
5857 static int node_cmp_attr_ASM(const ir_node *a, const ir_node *b)
5858 {
5859         int i, n;
5860         const ir_asm_constraint *ca;
5861         const ir_asm_constraint *cb;
5862         ident **cla, **clb;
5863
5864         if (get_ASM_text(a) != get_ASM_text(b))
5865                 return 1;
5866
5867         /* Should we really check the constraints here? Should be better, but is strange. */
5868         n = get_ASM_n_input_constraints(a);
5869         if (n != get_ASM_n_input_constraints(b))
5870                 return 1;
5871
5872         ca = get_ASM_input_constraints(a);
5873         cb = get_ASM_input_constraints(b);
5874         for (i = 0; i < n; ++i) {
5875                 if (ca[i].pos != cb[i].pos || ca[i].constraint != cb[i].constraint
5876                     || ca[i].mode != cb[i].mode)
5877                         return 1;
5878         }
5879
5880         n = get_ASM_n_output_constraints(a);
5881         if (n != get_ASM_n_output_constraints(b))
5882                 return 1;
5883
5884         ca = get_ASM_output_constraints(a);
5885         cb = get_ASM_output_constraints(b);
5886         for (i = 0; i < n; ++i) {
5887                 if (ca[i].pos != cb[i].pos || ca[i].constraint != cb[i].constraint
5888                     || ca[i].mode != cb[i].mode)
5889                         return 1;
5890         }
5891
5892         n = get_ASM_n_clobbers(a);
5893         if (n != get_ASM_n_clobbers(b))
5894                 return 1;
5895
5896         cla = get_ASM_clobbers(a);
5897         clb = get_ASM_clobbers(b);
5898         for (i = 0; i < n; ++i) {
5899                 if (cla[i] != clb[i])
5900                         return 1;
5901         }
5902         return 0;
5903 }
5904
5905 /** Compares the inexistent attributes of two Dummy nodes. */
5906 static int node_cmp_attr_Dummy(const ir_node *a, const ir_node *b)
5907 {
5908         (void) a;
5909         (void) b;
5910         return 1;
5911 }
5912
5913 /**
5914  * Set the default node attribute compare operation for an ir_op_ops.
5915  *
5916  * @param code   the opcode for the default operation
5917  * @param ops    the operations initialized
5918  *
5919  * @return
5920  *    The operations.
5921  */
5922 static ir_op_ops *firm_set_default_node_cmp_attr(ir_opcode code, ir_op_ops *ops)
5923 {
5924 #define CASE(a)                              \
5925         case iro_##a:                              \
5926                 ops->node_cmp_attr  = node_cmp_attr_##a; \
5927                 break
5928
5929         switch (code) {
5930         CASE(Const);
5931         CASE(Proj);
5932         CASE(Alloc);
5933         CASE(Free);
5934         CASE(SymConst);
5935         CASE(Call);
5936         CASE(Sel);
5937         CASE(Phi);
5938         CASE(Cmp);
5939         CASE(Conv);
5940         CASE(Cast);
5941         CASE(Load);
5942         CASE(Store);
5943         CASE(Confirm);
5944         CASE(ASM);
5945         CASE(Div);
5946         CASE(Mod);
5947         CASE(Bound);
5948         CASE(Builtin);
5949         CASE(Dummy);
5950         /* FIXME CopyB */
5951         default:
5952                 /* leave NULL */
5953                 break;
5954         }
5955
5956         return ops;
5957 #undef CASE
5958 }  /* firm_set_default_node_cmp_attr */
5959
5960 /*
5961  * Compare function for two nodes in the value table. Gets two
5962  * nodes as parameters.  Returns 0 if the nodes are a Common Sub Expression.
5963  */
5964 int identities_cmp(const void *elt, const void *key)
5965 {
5966         ir_node *a = (ir_node *)elt;
5967         ir_node *b = (ir_node *)key;
5968         int i, irn_arity_a;
5969
5970         if (a == b) return 0;
5971
5972         if ((get_irn_op(a) != get_irn_op(b)) ||
5973             (get_irn_mode(a) != get_irn_mode(b))) return 1;
5974
5975         /* compare if a's in and b's in are of equal length */
5976         irn_arity_a = get_irn_arity(a);
5977         if (irn_arity_a != get_irn_arity(b))
5978                 return 1;
5979
5980         /* blocks are never the same */
5981         if (is_Block(a))
5982                 return 1;
5983
5984         if (get_irn_pinned(a) == op_pin_state_pinned) {
5985                 /* for pinned nodes, the block inputs must be equal */
5986                 if (get_irn_n(a, -1) != get_irn_n(b, -1))
5987                         return 1;
5988         } else if (! get_opt_global_cse()) {
5989                 /* for block-local CSE both nodes must be in the same Block */
5990                 if (get_nodes_block(a) != get_nodes_block(b))
5991                         return 1;
5992         }
5993
5994         /* compare a->in[0..ins] with b->in[0..ins] */
5995         for (i = 0; i < irn_arity_a; ++i) {
5996                 ir_node *pred_a = get_irn_n(a, i);
5997                 ir_node *pred_b = get_irn_n(b, i);
5998                 if (pred_a != pred_b) {
5999                         /* if both predecessors are CSE neutral they might be different */
6000                         if (!is_irn_cse_neutral(pred_a) || !is_irn_cse_neutral(pred_b))
6001                                 return 1;
6002                 }
6003         }
6004
6005         /*
6006          * here, we already now that the nodes are identical except their
6007          * attributes
6008          */
6009         if (a->op->ops.node_cmp_attr)
6010                 return a->op->ops.node_cmp_attr(a, b);
6011
6012         return 0;
6013 }  /* identities_cmp */
6014
6015 /*
6016  * Calculate a hash value of a node.
6017  *
6018  * @param node  The IR-node
6019  */
6020 unsigned ir_node_hash(const ir_node *node)
6021 {
6022         return node->op->ops.hash(node);
6023 }  /* ir_node_hash */
6024
6025
6026 void new_identities(ir_graph *irg)
6027 {
6028         if (irg->value_table != NULL)
6029                 del_pset(irg->value_table);
6030         irg->value_table = new_pset(identities_cmp, N_IR_NODES);
6031 }  /* new_identities */
6032
6033 void del_identities(ir_graph *irg)
6034 {
6035         if (irg->value_table != NULL)
6036                 del_pset(irg->value_table);
6037 }  /* del_identities */
6038
6039 /* Normalize a node by putting constants (and operands with larger
6040  * node index) on the right (operator side). */
6041 void ir_normalize_node(ir_node *n)
6042 {
6043         if (is_op_commutative(get_irn_op(n))) {
6044                 ir_node *l = get_binop_left(n);
6045                 ir_node *r = get_binop_right(n);
6046
6047                 /* For commutative operators perform  a OP b == b OP a but keep
6048                  * constants on the RIGHT side. This helps greatly in some
6049                  * optimizations.  Moreover we use the idx number to make the form
6050                  * deterministic. */
6051                 if (!operands_are_normalized(l, r)) {
6052                         set_binop_left(n, r);
6053                         set_binop_right(n, l);
6054                         hook_normalize(n);
6055                 }
6056         }
6057 }  /* ir_normalize_node */
6058
6059 /*
6060  * Return the canonical node computing the same value as n.
6061  * Looks up the node in a hash table, enters it in the table
6062  * if it isn't there yet.
6063  *
6064  * @param n            the node to look up
6065  *
6066  * @return a node that computes the same value as n or n if no such
6067  *         node could be found
6068  */
6069 ir_node *identify_remember(ir_node *n)
6070 {
6071         ir_graph *irg         = get_irn_irg(n);
6072         pset     *value_table = irg->value_table;
6073         ir_node  *nn;
6074
6075         if (value_table == NULL)
6076                 return n;
6077
6078         ir_normalize_node(n);
6079         /* lookup or insert in hash table with given hash key. */
6080         nn = (ir_node*)pset_insert(value_table, n, ir_node_hash(n));
6081
6082         if (nn != n) {
6083                 /* n is reachable again */
6084                 edges_node_revival(nn);
6085         }
6086
6087         return nn;
6088 }  /* identify_remember */
6089
6090 /**
6091  * During construction we set the op_pin_state_pinned flag in the graph right
6092  * when the optimization is performed.  The flag turning on procedure global
6093  * cse could be changed between two allocations.  This way we are safe.
6094  *
6095  * @param n            The node to lookup
6096  */
6097 static inline ir_node *identify_cons(ir_node *n)
6098 {
6099         ir_node *old = n;
6100
6101         n = identify_remember(n);
6102         if (n != old && get_nodes_block(old) != get_nodes_block(n)) {
6103                 ir_graph *irg = get_irn_irg(n);
6104                 set_irg_pinned(irg, op_pin_state_floats);
6105         }
6106         return n;
6107 }  /* identify_cons */
6108
6109 /* Add a node to the identities value table. */
6110 void add_identities(ir_node *node)
6111 {
6112         if (!get_opt_cse())
6113                 return;
6114         if (is_Block(node))
6115                 return;
6116
6117         identify_remember(node);
6118 }
6119
6120 /* Visit each node in the value table of a graph. */
6121 void visit_all_identities(ir_graph *irg, irg_walk_func visit, void *env)
6122 {
6123         ir_node  *node;
6124         ir_graph *rem = current_ir_graph;
6125
6126         current_ir_graph = irg;
6127         foreach_pset(irg->value_table, ir_node*, node) {
6128                 visit(node, env);
6129         }
6130         current_ir_graph = rem;
6131 }  /* visit_all_identities */
6132
6133 /**
6134  * These optimizations deallocate nodes from the obstack.
6135  * It can only be called if it is guaranteed that no other nodes
6136  * reference this one, i.e., right after construction of a node.
6137  *
6138  * @param n   The node to optimize
6139  */
6140 ir_node *optimize_node(ir_node *n)
6141 {
6142         ir_node   *oldn = n;
6143         ir_graph  *irg  = get_irn_irg(n);
6144         unsigned   iro  = get_irn_opcode(n);
6145         ir_tarval *tv;
6146
6147         /* Always optimize Phi nodes: part of the construction. */
6148         if ((!get_opt_optimize()) && (iro != iro_Phi)) return n;
6149
6150         /* constant expression evaluation / constant folding */
6151         if (get_opt_constant_folding()) {
6152                 /* neither constants nor Tuple values can be evaluated */
6153                 if (iro != iro_Const && (get_irn_mode(n) != mode_T)) {
6154                         /* try to evaluate */
6155                         tv = computed_value(n);
6156                         if (tv != tarval_bad) {
6157                                 ir_node *nw;
6158                                 size_t node_size;
6159
6160                                 /*
6161                                  * we MUST copy the node here temporarily, because it's still
6162                                  * needed for DBG_OPT_CSTEVAL
6163                                  */
6164                                 node_size = offsetof(ir_node, attr) +  n->op->attr_size;
6165                                 oldn = (ir_node*)alloca(node_size);
6166
6167                                 memcpy(oldn, n, node_size);
6168                                 CLONE_ARR_A(ir_node *, oldn->in, n->in);
6169
6170                                 /* ARG, copy the in array, we need it for statistics */
6171                                 memcpy(oldn->in, n->in, ARR_LEN(n->in) * sizeof(n->in[0]));
6172
6173                                 /* note the inplace edges module */
6174                                 edges_node_deleted(n);
6175
6176                                 /* evaluation was successful -- replace the node. */
6177                                 irg_kill_node(irg, n);
6178                                 nw = new_r_Const(irg, tv);
6179
6180                                 DBG_OPT_CSTEVAL(oldn, nw);
6181                                 return nw;
6182                         }
6183                 }
6184         }
6185
6186         /* remove unnecessary nodes */
6187         if (get_opt_algebraic_simplification() ||
6188             (iro == iro_Phi)  ||   /* always optimize these nodes. */
6189             (iro == iro_Id)   ||
6190             (iro == iro_Proj) ||
6191             (iro == iro_Block)  )  /* Flags tested local. */
6192                 n = equivalent_node(n);
6193
6194         /* Common Subexpression Elimination.
6195          *
6196          * Checks whether n is already available.
6197          * The block input is used to distinguish different subexpressions. Right
6198          * now all nodes are op_pin_state_pinned to blocks, i.e., the CSE only finds common
6199          * subexpressions within a block.
6200          */
6201         if (get_opt_cse())
6202                 n = identify_cons(n);
6203
6204         if (n != oldn) {
6205                 edges_node_deleted(oldn);
6206
6207                 /* We found an existing, better node, so we can deallocate the old node. */
6208                 irg_kill_node(irg, oldn);
6209                 return n;
6210         }
6211
6212         /* Some more constant expression evaluation that does not allow to
6213            free the node. */
6214         iro = get_irn_opcode(n);
6215         if (get_opt_algebraic_simplification() ||
6216             (iro == iro_Cond) ||
6217             (iro == iro_Proj))     /* Flags tested local. */
6218                 n = transform_node(n);
6219
6220         /* Now we have a legal, useful node. Enter it in hash table for CSE */
6221         if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
6222                 ir_node *o = n;
6223                 n = identify_remember(o);
6224                 if (o != n)
6225                         DBG_OPT_CSE(o, n);
6226         }
6227
6228         return n;
6229 }  /* optimize_node */
6230
6231
6232 /**
6233  * These optimizations never deallocate nodes (in place).  This can cause dead
6234  * nodes lying on the obstack.  Remove these by a dead node elimination,
6235  * i.e., a copying garbage collection.
6236  */
6237 ir_node *optimize_in_place_2(ir_node *n)
6238 {
6239         ir_tarval *tv;
6240         ir_node   *oldn = n;
6241         unsigned   iro  = get_irn_opcode(n);
6242
6243         if (!get_opt_optimize() && !is_Phi(n)) return n;
6244
6245         if (iro == iro_Deleted)
6246                 return n;
6247
6248         /* constant expression evaluation / constant folding */
6249         if (get_opt_constant_folding()) {
6250                 /* neither constants nor Tuple values can be evaluated */
6251                 if (iro != iro_Const && get_irn_mode(n) != mode_T) {
6252                         /* try to evaluate */
6253                         tv = computed_value(n);
6254                         if (tv != tarval_bad) {
6255                                 /* evaluation was successful -- replace the node. */
6256                                 ir_graph *irg = get_irn_irg(n);
6257
6258                                 n = new_r_Const(irg, tv);
6259
6260                                 DBG_OPT_CSTEVAL(oldn, n);
6261                                 return n;
6262                         }
6263                 }
6264         }
6265
6266         /* remove unnecessary nodes */
6267         if (get_opt_constant_folding() ||
6268             (iro == iro_Phi)  ||   /* always optimize these nodes. */
6269             (iro == iro_Id)   ||   /* ... */
6270             (iro == iro_Proj) ||   /* ... */
6271             (iro == iro_Block)  )  /* Flags tested local. */
6272                 n = equivalent_node(n);
6273
6274         /** common subexpression elimination **/
6275         /* Checks whether n is already available. */
6276         /* The block input is used to distinguish different subexpressions.  Right
6277            now all nodes are op_pin_state_pinned to blocks, i.e., the cse only finds common
6278            subexpressions within a block. */
6279         if (get_opt_cse()) {
6280                 ir_node *o = n;
6281                 n = identify_remember(o);
6282                 if (o != n)
6283                         DBG_OPT_CSE(o, n);
6284         }
6285
6286         /* Some more constant expression evaluation. */
6287         iro = get_irn_opcode(n);
6288         if (get_opt_constant_folding() ||
6289                 (iro == iro_Cond) ||
6290                 (iro == iro_Proj))     /* Flags tested local. */
6291                 n = transform_node(n);
6292
6293         /* Now we can verify the node, as it has no dead inputs any more. */
6294         irn_verify(n);
6295
6296         /* Now we have a legal, useful node. Enter it in hash table for cse.
6297            Blocks should be unique anyways.  (Except the successor of start:
6298            is cse with the start block!) */
6299         if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
6300                 ir_node *o = n;
6301                 n = identify_remember(o);
6302                 if (o != n)
6303                         DBG_OPT_CSE(o, n);
6304         }
6305
6306         return n;
6307 }  /* optimize_in_place_2 */
6308
6309 /**
6310  * Wrapper for external use, set proper status bits after optimization.
6311  */
6312 ir_node *optimize_in_place(ir_node *n)
6313 {
6314         ir_graph *irg = get_irn_irg(n);
6315         /* Handle graph state */
6316         assert(get_irg_phase_state(irg) != phase_building);
6317
6318         if (get_opt_global_cse())
6319                 set_irg_pinned(irg, op_pin_state_floats);
6320
6321         /* FIXME: Maybe we could also test whether optimizing the node can
6322            change the control graph. */
6323         set_irg_doms_inconsistent(irg);
6324         return optimize_in_place_2(n);
6325 }  /* optimize_in_place */
6326
6327 /**
6328  * Calculate a hash value of a Const node.
6329  */
6330 static unsigned hash_Const(const ir_node *node)
6331 {
6332         unsigned h;
6333
6334         /* special value for const, as they only differ in their tarval. */
6335         h = HASH_PTR(node->attr.con.tarval);
6336
6337         return h;
6338 }  /* hash_Const */
6339
6340 /**
6341  * Calculate a hash value of a SymConst node.
6342  */
6343 static unsigned hash_SymConst(const ir_node *node)
6344 {
6345         unsigned h;
6346
6347         /* all others are pointers */
6348         h = HASH_PTR(node->attr.symc.sym.type_p);
6349
6350         return h;
6351 }  /* hash_SymConst */
6352
6353 /**
6354  * Set the default hash operation in an ir_op_ops.
6355  *
6356  * @param code   the opcode for the default operation
6357  * @param ops    the operations initialized
6358  *
6359  * @return
6360  *    The operations.
6361  */
6362 static ir_op_ops *firm_set_default_hash(unsigned code, ir_op_ops *ops)
6363 {
6364 #define CASE(a)                                    \
6365         case iro_##a:                                  \
6366                 ops->hash  = hash_##a; \
6367                 break
6368
6369         /* hash function already set */
6370         if (ops->hash != NULL)
6371                 return ops;
6372
6373         switch (code) {
6374         CASE(Const);
6375         CASE(SymConst);
6376         default:
6377                 /* use input/mode default hash if no function was given */
6378                 ops->hash = firm_default_hash;
6379         }
6380
6381         return ops;
6382 #undef CASE
6383 }
6384
6385 /*
6386  * Sets the default operation for an ir_ops.
6387  */
6388 ir_op_ops *firm_set_default_operations(unsigned code, ir_op_ops *ops)
6389 {
6390         ops = firm_set_default_hash(code, ops);
6391         ops = firm_set_default_computed_value(code, ops);
6392         ops = firm_set_default_equivalent_node(code, ops);
6393         ops = firm_set_default_transform_node(code, ops);
6394         ops = firm_set_default_node_cmp_attr(code, ops);
6395         ops = firm_set_default_get_type_attr(code, ops);
6396         ops = firm_set_default_get_entity_attr(code, ops);
6397
6398         return ops;
6399 }  /* firm_set_default_operations */