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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ir/iropt.c
   4  * Purpose:     iropt --- optimizations intertwined with IR construction.
   5  * Author:      Christian Schaefer
   6  * Modified by: Goetz Lindenmaier
   7  * Created:
   8  * CVS-ID:      $Id$
   9  * Copyright:   (c) 1998-2003 Universität Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12
  13 #ifdef HAVE_CONFIG_H
  14 # include <config.h>
  15 #endif
  16
  17 # include "irnode_t.h"
  18 # include "irgraph_t.h"
  19 # include "iropt_t.h"
  20 # include "ircons.h"
  21 # include "irgmod.h"
  22 # include "irvrfy.h"
  23 # include "tv.h"
  24 # include "dbginfo_t.h"
  25 # include "iropt_dbg.h"
  26
  27 /* Make types visible to allow most efficient access */
  28 # include "entity_t.h"
  29
  30 /* Trivial INLINEable routine for copy propagation.
  31    Does follow Ids, needed to optimize INLINEd code. */
  32 static INLINE ir_node *
  33 follow_Id (ir_node *n)
  34 {
  35   while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
  36   return n;
  37 }
  38
  39 static INLINE tarval *
  40 value_of (ir_node *n)
  41 {
  42   if ((n != NULL) && (get_irn_op(n) == op_Const))
  43     return get_Const_tarval(n); /* might return tarval_bad */
  44   else
  45     return tarval_bad;
  46 }
  47
  48 /* if n can be computed, return the value, else tarval_bad. Performs
  49    constant folding. GL: Only if n is arithmetic operator? */
  50 tarval *
  51 computed_value (ir_node *n)
  52 {
  53   tarval *res;
  54
  55   ir_node *a = NULL, *b = NULL;  /* initialized to shut up gcc */
  56   /* initialized to uniformly filter invalid constants */
  57   tarval *ta = tarval_bad, *tb = tarval_bad;
  58
  59   res = tarval_bad;
  60
  61   /* get the operands we will work on for simple cases. */
  62   if (is_binop(n)) {
  63     a = get_binop_left(n);
  64     b = get_binop_right(n);
  65   } else if (is_unop(n)) {
  66     a = get_unop_op(n);
  67   }
  68
  69   /* if the operands are constants, get the target value, else set it NULL.
  70      (a and b may be NULL if we treat a node that is no computation.) */
  71   ta = value_of (a);
  72   tb = value_of (b);
  73
  74   /* Perform the constant evaluation / computation. */
  75   switch (get_irn_opcode(n)) {
  76   case iro_Const:
  77     res = get_Const_tarval(n);
  78     break;
  79   case iro_SymConst:
  80     if ((get_SymConst_kind(n) == size) &&
  81         (get_type_state(get_SymConst_type(n))) == layout_fixed)
  82       res = new_tarval_from_long (get_type_size(get_SymConst_type(n)), mode_Is);
  83     break;
  84   case iro_Add:
  85     if ((ta != tarval_bad) && (tb != tarval_bad)
  86           && (get_irn_mode(a) == get_irn_mode(b))
  87           && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
  88       res = tarval_add (ta, tb);
  89     }
  90     break;
  91   case iro_Sub:
  92     if ((ta != tarval_bad) && (tb != tarval_bad)
  93           && (get_irn_mode(a) == get_irn_mode(b))
  94           && !(get_mode_sort(get_irn_mode(a)) == irms_reference)) {
  95       res = tarval_sub (ta, tb);
  96     }
  97     break;
  98   case iro_Minus:
  99       if ((ta != tarval_bad) && mode_is_signed(get_irn_mode(a)))
 100         res = tarval_neg (ta);
 101     break;
 102   case iro_Mul:
 103     if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
 104       res = tarval_mul (ta, tb);
 105     } else {
 106       /* a*0 = 0 or 0*b = 0:
 107          calls computed_value recursive and returns the 0 with proper
 108          mode. */
 109       tarval *v;
 110       if ( ( ((v = computed_value (a)) != tarval_bad)
 111                && (v == get_mode_null(get_tarval_mode(v))) )
 112         || ( ((v = computed_value (b)) != tarval_bad)
 113                && (v == get_mode_null(get_tarval_mode(v))) )) {
 114         res = v;
 115       }
 116     }
 117     break;
 118   case iro_Quot:
 119     /* This was missing in original implementation. Why? */
 120     if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
 121       if (tb == get_mode_null(get_tarval_mode(tb))) break;  /* div by zero: return tarval_bad */
 122       res = tarval_quo(ta, tb);
 123     }
 124     break;
 125   case iro_Div:
 126     /* This was missing in original implementation. Why? */
 127     if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
 128       if (tb == get_mode_null(get_tarval_mode(tb))) break;  /* div by zero: return tarval_bad */
 129       res = tarval_div(ta, tb);
 130     }
 131     break;
 132   case iro_Mod:
 133     /* This was missing in original implementation. Why? */
 134     if ((ta != tarval_bad) && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
 135       if (tb == get_mode_null(get_tarval_mode(tb))) break;  /* div by zero: return tarval_bad */
 136       res = tarval_mod(ta, tb);
 137     }
 138     break;
 139   /* for iro_DivMod see iro_Proj */
 140   case iro_Abs:
 141     if (ta != tarval_bad)
 142       res = tarval_abs (ta);
 143     break;
 144   case iro_And:
 145     if ((ta != tarval_bad) && (tb != tarval_bad)) {
 146       res = tarval_and (ta, tb);
 147     } else {
 148       tarval *v;
 149       if (   (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_NULL)
 150           || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_NULL)) {
 151         res = v;
 152       }
 153     }
 154     break;
 155   case iro_Or:
 156     if ((ta != tarval_bad) && (tb != tarval_bad)) {
 157       res = tarval_or (ta, tb);
 158     } else {
 159       tarval *v;
 160       if (   (tarval_classify ((v = computed_value (a))) == TV_CLASSIFY_ALL_ONE)
 161           || (tarval_classify ((v = computed_value (b))) == TV_CLASSIFY_ALL_ONE)) {
 162         res = v;
 163       }
 164     }
 165     break;
 166   case iro_Eor:
 167     if ((ta != tarval_bad) && (tb != tarval_bad)) {
 168       res = tarval_eor (ta, tb);
 169     }
 170     break;
 171   case iro_Not:
 172     if ((ta != tarval_bad)) {
 173       res = tarval_not (ta);
 174     }
 175     break;
 176   case iro_Shl:
 177     if ((ta != tarval_bad) && (tb != tarval_bad)) {
 178       res = tarval_shl (ta, tb);
 179     }
 180     break;
 181   case iro_Shr:
 182     if ((ta != tarval_bad) && (tb != tarval_bad)) {
 183       res = tarval_shr (ta, tb);
 184     }
 185     break;
 186   case iro_Shrs:
 187     if ((ta != tarval_bad) && (tb != tarval_bad)) {
 188      res = tarval_shrs (ta, tb);
 189     }
 190     break;
 191   case iro_Rot:
 192     if ((ta != tarval_bad) && (tb != tarval_bad)) {
 193       /*res = tarval_rot (ta, tb)*/;
 194     }
 195     break;
 196   case iro_Conv:
 197     if (ta != tarval_bad) {
 198       res = tarval_convert_to (ta, get_irn_mode (n));
 199     }
 200     break;
 201   case iro_Proj:  /* iro_Cmp */
 202     {
 203       ir_node *aa, *ab;
 204
 205       a = get_Proj_pred(n);
 206       /* Optimize Cmp nodes.
 207          This performs a first step of unreachable code elimination.
 208          Proj can not be computed, but folding a Cmp above the Proj here is
 209          not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
 210          only 1 is used.
 211          There are several case where we can evaluate a Cmp node:
 212          1. The nodes compared are both the same.  If we compare for
 213             equal, greater equal, ... this will return true, else it
 214             will return false.  This step relies on cse.
 215          2. The predecessors of Cmp are target values.  We can evaluate
 216             the Cmp.
 217          3. The predecessors are Allocs or void* constants.  Allocs never
 218             return NULL, they raise an exception.   Therefore we can predict
 219             the Cmp result. */
 220       if (get_irn_op(a) == op_Cmp) {
 221         aa = get_Cmp_left(a);
 222         ab = get_Cmp_right(a);
 223         if (aa == ab) { /* 1.: */
 224           /* This is a tric with the bits used for encoding the Cmp
 225              Proj numbers, the following statement is not the same:
 226           res = new_tarval_from_long ((get_Proj_proj(n) == Eq), mode_b) */
 227           res = new_tarval_from_long ((get_Proj_proj(n) & Eq), mode_b);
 228         } else {
 229           tarval *taa = computed_value (aa);
 230           tarval *tab = computed_value (ab);
 231           if ((taa != tarval_bad) && (tab != tarval_bad)) { /* 2.: */
 232             /* strange checks... */
 233             pnc_number flags = tarval_cmp (taa, tab);
 234             if (flags != False) {
 235               res = new_tarval_from_long (get_Proj_proj(n) & flags, mode_b);
 236             }
 237           } else {  /* check for 3.: */
 238             ir_node *aaa = skip_nop(skip_Proj(aa));
 239             ir_node *aba = skip_nop(skip_Proj(ab));
 240             if (   (   (/* aa is ProjP and aaa is Alloc */
 241                            (get_irn_op(aa) == op_Proj)
 242                         && (mode_is_reference(get_irn_mode(aa)))
 243                         && (get_irn_op(aaa) == op_Alloc))
 244                     && (   (/* ab is constant void */
 245                                (get_irn_op(ab) == op_Const)
 246                             && (mode_is_reference(get_irn_mode(ab)))
 247                             && (get_Const_tarval(ab) == get_mode_null(get_irn_mode(ab))))
 248                         || (/* ab is other Alloc */
 249                                (get_irn_op(ab) == op_Proj)
 250                             && (mode_is_reference(get_irn_mode(ab)))
 251                             && (get_irn_op(aba) == op_Alloc)
 252                             && (aaa != aba))))
 253                 || (/* aa is void and aba is Alloc */
 254                        (get_irn_op(aa) == op_Const)
 255                     && (mode_is_reference(get_irn_mode(aa)))
 256                     && (get_Const_tarval(aa) == get_mode_null(get_irn_mode(aa)))
 257                     && (get_irn_op(ab) == op_Proj)
 258                     && (mode_is_reference(get_irn_mode(ab)))
 259                     && (get_irn_op(aba) == op_Alloc)))
 260               /* 3.: */
 261               res = new_tarval_from_long (get_Proj_proj(n) & Ne, mode_b);
 262           }
 263         }
 264       } else if (get_irn_op(a) == op_DivMod) {
 265         ta = value_of(get_DivMod_left(a));
 266         tb = value_of(get_DivMod_right(a));
 267         if ((ta != tarval_bad)  && (tb != tarval_bad) && (get_irn_mode(a) == get_irn_mode(b))) {
 268           if (tb == get_mode_null(get_tarval_mode(tb))) break;  /* div by zero: return tarval_bad */
 269           if (get_Proj_proj(n)== 0) /* Div */
 270             res = tarval_div(ta, tb);
 271           else /* Mod */
 272             res = tarval_mod(ta, tb);
 273         }
 274       }
 275     }
 276     break;
 277   default:  ;
 278   }
 279
 280   return res;
 281 }  /* compute node */
 282
 283
 284 #if 0
 285 /* returns 1 if the a and b are pointers to different locations. */
 286 static bool
 287 different_identity (ir_node *a, ir_node *b)
 288 {
 289   assert (mode_is_reference(get_irn_mode (a))
 290           && mode_is_reference(get_irn_mode (b)));
 291
 292   if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
 293     ir_node *a1 = get_Proj_pred (a);
 294     ir_node *b1 = get_Proj_pred (b);
 295     if (a1 != b1 && get_irn_op (a1) == op_Alloc
 296                 && get_irn_op (b1) == op_Alloc)
 297       return 1;
 298   }
 299   return 0;
 300 }
 301 #endif
 302
 303 /* equivalent_node returns a node equivalent to N.  It skips all nodes that
 304    perform no actual computation, as, e.g., the Id nodes.  It does not create
 305    new nodes.  It is therefore safe to free N if the node returned is not N.
 306    If a node returns a Tuple we can not just skip it.  If the size of the
 307    in array fits, we transform n into a tuple (e.g., Div). */
 308 ir_node *
 309 equivalent_node (ir_node *n)
 310 {
 311   int ins;
 312   ir_node *a = NULL; /* to shutup gcc */
 313   ir_node *b = NULL; /* to shutup gcc */
 314   ir_node *c = NULL; /* to shutup gcc */
 315   ir_node *oldn = n;
 316
 317   ins = get_irn_arity (n);
 318
 319   /* get the operands we will work on */
 320   if (is_binop(n)) {
 321     a = get_binop_left(n);
 322     b = get_binop_right(n);
 323   } else if (is_unop(n)) {
 324     a = get_unop_op(n);
 325   }
 326
 327   /* skip unnecessary nodes. */
 328   switch (get_irn_opcode (n)) {
 329   case iro_Block:
 330     {
 331       /* The Block constructor does not call optimize, but mature_block
 332          calls the optimization. */
 333       assert(get_Block_matured(n));
 334
 335       /* Straightening: a single entry Block following a single exit Block
 336          can be merged, if it is not the Start block. */
 337       /* !!! Beware, all Phi-nodes of n must have been optimized away.
 338          This should be true, as the block is matured before optimize is called.
 339          But what about Phi-cycles with the Phi0/Id that could not be resolved?
 340          Remaining Phi nodes are just Ids. */
 341       if ((get_Block_n_cfgpreds(n) == 1) &&
 342           (get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) &&
 343           (get_opt_control_flow_straightening())) {
 344         n = get_nodes_Block(get_Block_cfgpred(n, 0));                     DBG_OPT_STG;
 345
 346       } else if ((get_Block_n_cfgpreds(n) == 2) &&
 347                  (get_opt_control_flow_weak_simplification())) {
 348         /* Test whether Cond jumps twice to this block
 349            @@@ we could do this also with two loops finding two preds from several ones. */
 350         a = get_Block_cfgpred(n, 0);
 351         b = get_Block_cfgpred(n, 1);
 352         if ((get_irn_op(a) == op_Proj) &&
 353             (get_irn_op(b) == op_Proj) &&
 354             (get_Proj_pred(a) == get_Proj_pred(b)) &&
 355             (get_irn_op(get_Proj_pred(a)) == op_Cond) &&
 356             (get_irn_mode(get_Cond_selector(get_Proj_pred(a))) == mode_b)) {
 357           /* Also a single entry Block following a single exit Block.  Phis have
 358              twice the same operand and will be optimized away. */
 359           n = get_nodes_Block(a);                                         DBG_OPT_IFSIM;
 360         }
 361       } else if (get_opt_unreachable_code() &&
 362                  (n != current_ir_graph->start_block) &&
 363                  (n != current_ir_graph->end_block)     ) {
 364         int i;
 365         /* If all inputs are dead, this block is dead too, except if it is
 366            the start or end block.  This is a step of unreachable code
 367            elimination */
 368         for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
 369           if (!is_Bad(get_Block_cfgpred(n, i))) break;
 370         }
 371         if (i == get_Block_n_cfgpreds(n))
 372           n = new_Bad();
 373       }
 374     }
 375     break;
 376
 377   case iro_Jmp:  /* GL: Why not same for op_Raise?? */
 378     /* unreachable code elimination */
 379     if (is_Bad(get_nodes_Block(n)))  n = new_Bad();
 380     break;
 381         /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
 382            See cases for iro_Cond and iro_Proj in transform_node. */
 383         /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
 384   case iro_Or:  if (a == b) {n = a; break;}
 385   case iro_Add:
 386   case iro_Eor: {
 387     tarval *tv;
 388     ir_node *on;
 389     /* After running compute_node there is only one constant predecessor.
 390        Find this predecessors value and remember the other node: */
 391     if ((tv = computed_value (a)) != tarval_bad) {
 392       on = b;
 393     } else if ((tv = computed_value (b)) != tarval_bad) {
 394       on = a;
 395     } else break;
 396
 397     /* If this predecessors constant value is zero, the operation is
 398        unnecessary. Remove it: */
 399     if (tarval_classify (tv) == TV_CLASSIFY_NULL) {
 400       n = on;                                                             DBG_OPT_ALGSIM1;
 401     }
 402   } break;
 403   case iro_Sub:
 404   case iro_Shl:
 405   case iro_Shr:
 406   case iro_Shrs:
 407   case iro_Rot:
 408     /* these operations are not commutative.  Test only one predecessor. */
 409     if (tarval_classify (computed_value (b)) == TV_CLASSIFY_NULL) {
 410       n = a;                                                              DBG_OPT_ALGSIM1;
 411       /* Test if b > #bits of a ==> return 0 / divide b by #bits
 412          --> transform node? */
 413     }
 414     break;
 415   case iro_Not:   /* NotNot x == x */
 416   case iro_Minus: /* --x == x */  /* ??? Is this possible or can --x raise an
 417                                          out of bounds exception if min =! max? */
 418     if (get_irn_op(get_unop_op(n)) == get_irn_op(n)) {
 419       n = get_unop_op(get_unop_op(n));                                    DBG_OPT_ALGSIM2;
 420     }
 421     break;
 422   case iro_Mul:
 423     /* Mul is commutative and has again an other neutral element. */
 424     if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ONE) {
 425       n = b;                                                              DBG_OPT_ALGSIM1;
 426     } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) {
 427       n = a;                                                              DBG_OPT_ALGSIM1;
 428     }
 429     break;
 430   case iro_Div:
 431     /* Div is not commutative. */
 432     if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE) { /* div(x, 1) == x */
 433       /* Turn Div into a tuple (mem, bad, a) */
 434       ir_node *mem = get_Div_mem(n);
 435       turn_into_tuple(n, 3);
 436       set_Tuple_pred(n, 0, mem);
 437       set_Tuple_pred(n, 1, new_Bad());
 438       set_Tuple_pred(n, 2, a);
 439     }
 440     break;
 441   /*
 442   case iro_Mod, Quot, DivMod
 443     DivMod allocates new nodes --> it's treated in transform node.
 444     What about Quot, DivMod?
 445   */
 446   case iro_And:
 447     if (a == b) {
 448       n = a;    /* And has it's own neutral element */
 449     } else if (tarval_classify (computed_value (a)) == TV_CLASSIFY_ALL_ONE) {
 450       n = b;
 451     } else if (tarval_classify (computed_value (b)) == TV_CLASSIFY_ALL_ONE) {
 452       n = a;
 453     }
 454     if (n != oldn)                                                        DBG_OPT_ALGSIM1;
 455     break;
 456   case iro_Conv:
 457   {
 458     ir_mode *n_mode = get_irn_mode(n);
 459     ir_mode *a_mode = get_irn_mode(a);
 460
 461     if (n_mode == a_mode) { /* No Conv necessary */
 462       n = a;                                                              DBG_OPT_ALGSIM3;
 463     } else if (get_irn_op(a) == op_Conv) { /* Conv(Conv(b)) */
 464       ir_mode *b_mode;
 465
 466       b = get_Conv_op(a);
 467       n_mode = get_irn_mode(n);
 468       b_mode = get_irn_mode(b);
 469
 470       if (n_mode == b_mode) {
 471         if (n_mode == mode_b) {
 472           n = b;        /* Convb(Conv*(xxxb(...))) == xxxb(...) */        DBG_OPT_ALGSIM1;
 473         }
 474         else if (mode_is_int(n_mode) || mode_is_character(n_mode)) {
 475           if (smaller_mode(b_mode, a_mode)){
 476             n = b;      /* ConvS(ConvL(xxxS(...))) == xxxS(...) */        DBG_OPT_ALGSIM1;
 477           }
 478         }
 479       }
 480     }
 481     break;
 482   }
 483   case iro_Phi:
 484     {
 485       /* Several optimizations:
 486          - no Phi in start block.
 487          - remove Id operators that are inputs to Phi
 488          - fold Phi-nodes, iff they have only one predecessor except
 489                  themselves.
 490       */
 491       int i, n_preds;
 492
 493       ir_node *block = NULL;     /* to shutup gcc */
 494       ir_node *first_val = NULL; /* to shutup gcc */
 495       ir_node *scnd_val = NULL;  /* to shutup gcc */
 496
 497       if (!get_opt_normalize()) return n;
 498
 499       n_preds = get_Phi_n_preds(n);
 500
 501       block = get_nodes_Block(n);
 502       /* @@@ fliegt 'raus, sollte aber doch immer wahr sein!!!
 503          assert(get_irn_arity(block) == n_preds && "phi in wrong block!"); */
 504       if ((is_Bad(block)) ||                         /* Control dead */
 505           (block == current_ir_graph->start_block))  /* There should be no Phi nodes */
 506         return new_Bad();                            /* in the Start Block. */
 507
 508       if (n_preds == 0) break;           /* Phi of dead Region without predecessors. */
 509
 510 #if 0
 511       /* first we test for a special case: */
 512       /* Confirm is a special node fixing additional information for a
 513          value that is known at a certain point.  This is useful for
 514          dataflow analysis. */
 515       if (n_preds == 2) {
 516         ir_node *a = follow_Id (get_Phi_pred(n, 0));
 517         ir_node *b = follow_Id (get_Phi_pred(n, 1));
 518         if (   (get_irn_op(a) == op_Confirm)
 519             && (get_irn_op(b) == op_Confirm)
 520             && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
 521             && (get_irn_n(a, 1) == get_irn_n (b, 1))
 522             && (a->data.num == (~b->data.num & irpn_True) )) {
 523           n = follow_Id (get_irn_n(a, 0));
 524           break;
 525         }
 526       }
 527 #endif
 528
 529       /* Find first non-self-referencing input */
 530       for (i = 0;  i < n_preds;  ++i) {
 531         first_val = follow_Id(get_Phi_pred(n, i));
 532         /* skip Id's */
 533         set_Phi_pred(n, i, first_val);
 534         if (   (first_val != n)                            /* not self pointer */
 535             && (get_irn_op(first_val) != op_Bad)           /* value not dead */
 536             && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
 537           break;                         /* then found first value. */
 538         }
 539       }
 540
 541       /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
 542       if (i >= n_preds) { n = new_Bad();  break; }
 543
 544       scnd_val = NULL;
 545
 546       /* follow_Id () for rest of inputs, determine if any of these
 547          are non-self-referencing */
 548       while (++i < n_preds) {
 549         scnd_val = follow_Id(get_Phi_pred(n, i));
 550         /* skip Id's */
 551         set_Phi_pred(n, i, scnd_val);
 552         if (   (scnd_val != n)
 553             && (scnd_val != first_val)
 554             && (get_irn_op(scnd_val) != op_Bad)
 555             && !(is_Bad (get_Block_cfgpred(block, i))) ) {
 556           break;
 557         }
 558       }
 559
 560       /* Fold, if no multiple distinct non-self-referencing inputs */
 561       if (i >= n_preds) {
 562         n = first_val;                                     DBG_OPT_PHI;
 563       } else {
 564         /* skip the remaining Ids. */
 565         while (++i < n_preds) {
 566           set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
 567         }
 568       }
 569     }
 570     break;
 571
 572   case iro_Load:
 573     {
 574 #if 0  /* Is an illegal transformation: different nodes can
 575           represent the same pointer value!! */
 576  a = skip_Proj(get_Load_mem(n));
 577  b = get_Load_ptr(n);
 578
 579  if (get_irn_op(a) == op_Store) {
 580    if ( different_identity (b, get_Store_ptr(a))) {
 581          /* load and store use different pointers, therefore load
 582                 needs not take store's memory but the state before. */
 583          set_Load_mem (n, get_Store_mem(a));
 584    } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
 585    }
 586  }
 587 #endif
 588     }
 589         break;
 590   case iro_Store:
 591     /* remove unnecessary store. */
 592     {
 593       a = skip_Proj(get_Store_mem(n));
 594       b = get_Store_ptr(n);
 595       c = skip_Proj(get_Store_value(n));
 596
 597       if (get_irn_op(a) == op_Store
 598           && get_Store_ptr(a) == b
 599           && skip_Proj(get_Store_value(a)) == c) {
 600         /* We have twice exactly the same store -- a write after write. */
 601         n = a;                                                         DBG_OPT_WAW;
 602       } else if (get_irn_op(c) == op_Load
 603                  && (a == c || skip_Proj(get_Load_mem(c)) == a)
 604                  && get_Load_ptr(c) == b ) {
 605         /* We just loaded the value from the same memory, i.e., the store
 606            doesn't change the memory -- a write after read. */
 607         a = get_Store_mem(n);
 608         turn_into_tuple(n, 2);
 609         set_Tuple_pred(n, 0, a);
 610         set_Tuple_pred(n, 1, new_Bad());                               DBG_OPT_WAR;
 611        }
 612     }
 613     break;
 614
 615   case iro_Proj:
 616     {
 617       a = get_Proj_pred(n);
 618
 619       if ( get_irn_op(a) == op_Tuple) {
 620         /* Remove the Tuple/Proj combination. */
 621         if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
 622           n = get_Tuple_pred(a, get_Proj_proj(n));                     DBG_OPT_TUPLE;
 623         } else {
 624           assert(0); /* This should not happen! */
 625           n = new_Bad();
 626         }
 627       } else if (get_irn_mode(n) == mode_X &&
 628                  is_Bad(get_nodes_Block(n))) {
 629         /* Remove dead control flow -- early gigo. */
 630         n = new_Bad();
 631       }
 632     }
 633     break;
 634
 635   case iro_Id:
 636     n = follow_Id (n);                                                 DBG_OPT_ID;
 637     break;
 638
 639   default: break;
 640   }
 641
 642   return n;
 643 } /* end equivalent_node() */
 644
 645 /* do node specific optimizations of nodes predecessors. */
 646 static void
 647 optimize_preds(ir_node *n) {
 648   ir_node *a = NULL, *b = NULL;
 649
 650   /* get the operands we will work on for simple cases. */
 651   if (is_binop(n)) {
 652     a = get_binop_left(n);
 653     b = get_binop_right(n);
 654   } else if (is_unop(n)) {
 655     a = get_unop_op(n);
 656   }
 657
 658   switch (get_irn_opcode(n)) {
 659
 660   case iro_Cmp:
 661     /* We don't want Cast as input to Cmp. */
 662     if (get_irn_op(a) == op_Cast) {
 663       a = get_Cast_op(a);
 664       set_Cmp_left(n, a);
 665     }
 666     if (get_irn_op(b) == op_Cast) {
 667       b = get_Cast_op(b);
 668       set_Cmp_right(n, b);
 669     }
 670     break;
 671
 672   default: break;
 673   } /* end switch */
 674 }
 675
 676
 677 /* tries several [inplace] [optimizing] transformations and returns an
 678    equivalent node.  The difference to equivalent_node is that these
 679    transformations _do_ generate new nodes, and thus the old node must
 680    not be freed even if the equivalent node isn't the old one. */
 681 static ir_node *
 682 transform_node (ir_node *n) {
 683   ir_node *a = NULL, *b;
 684   tarval *ta, *tb;
 685
 686   switch (get_irn_opcode(n)) {
 687   case iro_Div: {
 688     ta = computed_value(n);
 689     if (ta != tarval_bad) {
 690       /* Turn Div into a tuple (mem, bad, value) */
 691       ir_node *mem = get_Div_mem(n);
 692       turn_into_tuple(n, 3);
 693       set_Tuple_pred(n, 0, mem);
 694       set_Tuple_pred(n, 1, new_Bad());
 695       set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
 696     }
 697   } break;
 698   case iro_Mod: {
 699     ta = computed_value(n);
 700     if (ta != tarval_bad) {
 701       /* Turn Mod into a tuple (mem, bad, value) */
 702       ir_node *mem = get_Mod_mem(n);
 703       turn_into_tuple(n, 3);
 704       set_Tuple_pred(n, 0, mem);
 705       set_Tuple_pred(n, 1, new_Bad());
 706       set_Tuple_pred(n, 2, new_Const(get_tarval_mode(ta), ta));
 707     }
 708   } break;
 709   case iro_DivMod: {
 710
 711     int evaluated = 0;
 712     ir_mode *mode;
 713
 714     a = get_DivMod_left(n);
 715     b = get_DivMod_right(n);
 716     mode = get_irn_mode(a);
 717
 718     if (!(mode_is_int(get_irn_mode(a)) &&
 719           mode_is_int(get_irn_mode(b))))
 720       break;
 721
 722     if (a == b) {
 723       a = new_Const (mode, get_mode_one(mode));
 724       b = new_Const (mode, get_mode_null(mode));
 725       evaluated = 1;
 726     } else {
 727       ta = value_of(a);
 728       tb = value_of(b);
 729
 730       if (tb != tarval_bad) {
 731         if (tb == get_mode_one(get_tarval_mode(tb))) {
 732           b = new_Const (mode, get_mode_null(mode));
 733           evaluated = 1;
 734         } else if (ta != tarval_bad) {
 735           tarval *resa, *resb;
 736           resa = tarval_div (ta, tb);
 737           if (resa == tarval_bad) break; /* Causes exception!!! Model by replacing through
 738                                             Jmp for X result!? */
 739           resb = tarval_mod (ta, tb);
 740           if (resb == tarval_bad) break; /* Causes exception! */
 741           a = new_Const (mode, resa);
 742           b = new_Const (mode, resb);
 743           evaluated = 1;
 744         }
 745       } else if (ta == get_mode_null(get_tarval_mode(ta))) {
 746         b = a;
 747         evaluated = 1;
 748       }
 749     }
 750     if (evaluated) { /* replace by tuple */
 751       ir_node *mem = get_DivMod_mem(n);
 752       turn_into_tuple(n, 4);
 753       set_Tuple_pred(n, 0, mem);
 754       set_Tuple_pred(n, 1, new_Bad());  /* no exception */
 755       set_Tuple_pred(n, 2, a);
 756       set_Tuple_pred(n, 3, b);
 757       assert(get_nodes_Block(n));
 758     }
 759   }
 760   break;
 761
 762   case iro_Cond: {
 763     /* Replace the Cond by a Jmp if it branches on a constant
 764        condition. */
 765     ir_node *jmp;
 766     a = get_Cond_selector(n);
 767     ta = value_of(a);
 768
 769     if ((ta != tarval_bad) &&
 770         (get_irn_mode(a) == mode_b) &&
 771         (get_opt_unreachable_code())) {
 772       /* It's a boolean Cond, branching on a boolean constant.
 773                  Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
 774       jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
 775       turn_into_tuple(n, 2);
 776       if (ta == tarval_b_true) {
 777         set_Tuple_pred(n, 0, new_Bad());
 778         set_Tuple_pred(n, 1, jmp);
 779       } else {
 780         set_Tuple_pred(n, 0, jmp);
 781         set_Tuple_pred(n, 1, new_Bad());
 782       }
 783       /* We might generate an endless loop, so keep it alive. */
 784       add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
 785     } else if ((ta != tarval_bad) &&
 786                (get_irn_mode(a) == mode_Iu) &&
 787                (get_Cond_kind(n) == dense) &&
 788                (get_opt_unreachable_code())) {
 789       /* I don't want to allow Tuples smaller than the biggest Proj.
 790          Also this tuple might get really big...
 791          I generate the Jmp here, and remember it in link.  Link is used
 792          when optimizing Proj. */
 793       set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 794       /* We might generate an endless loop, so keep it alive. */
 795       add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
 796     } else if ((get_irn_op(a) == op_Eor)
 797                && (get_irn_mode(a) == mode_b)
 798                && (tarval_classify(computed_value(get_Eor_right(a))) == TV_CLASSIFY_ONE)) {
 799       /* The Eor is a negate.  Generate a new Cond without the negate,
 800          simulate the negate by exchanging the results. */
 801       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 802                                  get_Eor_left(a)));
 803     } else if ((get_irn_op(a) == op_Not)
 804                && (get_irn_mode(a) == mode_b)) {
 805       /* A Not before the Cond.  Generate a new Cond without the Not,
 806          simulate the Not by exchanging the results. */
 807       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 808                                  get_Not_op(a)));
 809     }
 810   }
 811   break;
 812
 813   case iro_Proj: {
 814     a = get_Proj_pred(n);
 815
 816     if ((get_irn_op(a) == op_Cond)
 817         && get_irn_link(a)
 818         && get_irn_op(get_irn_link(a)) == op_Cond) {
 819       /* Use the better Cond if the Proj projs from a Cond which get's
 820          its result from an Eor/Not. */
 821       assert (((get_irn_op(get_Cond_selector(a)) == op_Eor)
 822                || (get_irn_op(get_Cond_selector(a)) == op_Not))
 823               && (get_irn_mode(get_Cond_selector(a)) == mode_b)
 824               && (get_irn_op(get_irn_link(a)) == op_Cond)
 825               && (get_Cond_selector(get_irn_link(a)) == get_Eor_left(get_Cond_selector(a))));
 826       set_Proj_pred(n, get_irn_link(a));
 827       if (get_Proj_proj(n) == 0)
 828         set_Proj_proj(n, 1);
 829       else
 830         set_Proj_proj(n, 0);
 831     } else if ((get_irn_op(a) == op_Cond)
 832                && (get_irn_mode(get_Cond_selector(a)) == mode_Iu)
 833                && value_of(a)
 834                && (get_Cond_kind(a) == dense)
 835                && (get_opt_unreachable_code())) {
 836       /* The Cond is a Switch on a Constant */
 837       if (get_Proj_proj(n) == tarval_to_long(value_of(a))) {
 838         /* The always taken branch, reuse the existing Jmp. */
 839         if (!get_irn_link(a)) /* well, if it exists ;-> */
 840           set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 841         assert(get_irn_op(get_irn_link(a)) == op_Jmp);
 842         n = get_irn_link(a);
 843       } else {/* Not taken control flow, but be careful with the default! */
 844         if (get_Proj_proj(n) < a->attr.c.default_proj){
 845           /* a never taken branch */
 846           n = new_Bad();
 847         } else {
 848           a->attr.c.default_proj = get_Proj_proj(n);
 849         }
 850       }
 851     }
 852   } break;
 853   case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
 854     a = get_Eor_left(n);
 855     b = get_Eor_right(n);
 856
 857     if ((get_irn_mode(n) == mode_b)
 858         && (get_irn_op(a) == op_Proj)
 859         && (get_irn_mode(a) == mode_b)
 860         && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE)
 861         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 862       /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
 863       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 864                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 865     else if ((get_irn_mode(n) == mode_b)
 866              && (tarval_classify (computed_value (b)) == TV_CLASSIFY_ONE))
 867       /* The Eor is a Not. Replace it by a Not. */
 868       /*   ????!!!Extend to bitfield 1111111. */
 869       n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
 870   }
 871   break;
 872   case iro_Not: {
 873     a = get_Not_op(n);
 874
 875     if (   (get_irn_mode(n) == mode_b)
 876         && (get_irn_op(a) == op_Proj)
 877         && (get_irn_mode(a) == mode_b)
 878         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 879       /* We negate a Cmp. The Cmp has the negated result anyways! */
 880       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 881                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 882   }
 883   break;
 884   default: ;
 885   }
 886   return n;
 887 }
 888
 889 /* **************** Common Subexpression Elimination **************** */
 890
 891 /** The size of the hash table used, should estimate the number of nodes
 892     in a graph. */
 893 #define N_IR_NODES 512
 894
 895 /* Compare function for two nodes in the hash table.   Gets two       */
 896 /* nodes as parameters.  Returns 0 if the nodes are a cse.            */
 897 static int
 898 vt_cmp (const void *elt, const void *key)
 899 {
 900   ir_node *a, *b;
 901   int i, irn_arity_a;
 902
 903   a = (void *)elt;
 904   b = (void *)key;
 905
 906   if (a == b) return 0;
 907
 908   if ((get_irn_op(a) != get_irn_op(b)) ||
 909       (get_irn_mode(a) != get_irn_mode(b))) return 1;
 910
 911   /* compare if a's in and b's in are equal */
 912   irn_arity_a = get_irn_arity (a);
 913   if (irn_arity_a != get_irn_arity(b))
 914     return 1;
 915
 916   /* for block-local cse and pinned nodes: */
 917   if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
 918     if (get_irn_n(a, -1) != get_irn_n(b, -1))
 919       return 1;
 920   }
 921
 922   /* compare a->in[0..ins] with b->in[0..ins] */
 923   for (i = 0; i < irn_arity_a; i++)
 924     if (get_irn_n(a, i) != get_irn_n(b, i))
 925       return 1;
 926
 927   switch (get_irn_opcode(a)) {
 928   case iro_Const:
 929     return (get_Const_tarval(a) != get_Const_tarval(b))
 930       || (get_Const_type(a) != get_Const_type(b));
 931   case iro_Proj:
 932     return get_irn_proj_attr (a) != get_irn_proj_attr (b);
 933   case iro_Filter:
 934     return get_Filter_proj(a) != get_Filter_proj(b);
 935   case iro_Alloc:
 936     return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
 937       || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
 938   case iro_Free:
 939     return (get_irn_free_attr(a) != get_irn_free_attr(b));
 940   case iro_SymConst:
 941     return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
 942       || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
 943   case iro_Call:
 944     return (get_irn_call_attr(a) != get_irn_call_attr(b));
 945   case iro_Sel:
 946     return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
 947       || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
 948       || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
 949       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
 950       || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type);
 951   case iro_Phi:
 952     return get_irn_phi_attr (a) != get_irn_phi_attr (b);
 953   case iro_Cast:
 954     return get_Cast_type(a) != get_Cast_type(b);
 955   default: ;
 956   }
 957
 958   return 0;
 959 }
 960
 961 static unsigned
 962 ir_node_hash (ir_node *node)
 963 {
 964   unsigned h;
 965   int i, irn_arity;
 966
 967   /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
 968   h = irn_arity = get_irn_arity(node);
 969
 970   /* consider all in nodes... except the block. */
 971   for (i = 0;  i < irn_arity;  i++) {
 972     h = 9*h + (unsigned long)get_irn_n(node, i);
 973   }
 974
 975   /* ...mode,... */
 976   h = 9*h + (unsigned long) get_irn_mode (node);
 977   /* ...and code */
 978   h = 9*h + (unsigned long) get_irn_op (node);
 979
 980   return h;
 981 }
 982
 983 pset *
 984 new_identities (void)
 985 {
 986   return new_pset (vt_cmp, N_IR_NODES);
 987 }
 988
 989 void
 990 del_identities (pset *value_table)
 991 {
 992   del_pset (value_table);
 993 }
 994
 995 /* Return the canonical node computing the same value as n.
 996    Looks up the node in a hash table. */
 997 static INLINE ir_node *
 998 identify (pset *value_table, ir_node *n)
 999 {
1000   ir_node *o = NULL;
1001
1002   if (!value_table) return n;
1003
1004   if (get_opt_reassociation()) {
1005     switch (get_irn_opcode (n)) {
1006     case iro_Add:
1007     case iro_Mul:
1008     case iro_Or:
1009     case iro_And:
1010     case iro_Eor:
1011       {
1012         /* for commutative operators perform  a OP b == b OP a */
1013         if (get_binop_left(n) > get_binop_right(n)) {
1014           ir_node *h = get_binop_left(n);
1015           set_binop_left(n, get_binop_right(n));
1016           set_binop_right(n, h);
1017         }
1018       }
1019       break;
1020     default: break;
1021     }
1022   }
1023
1024   o = pset_find (value_table, n, ir_node_hash (n));
1025   if (!o) return n;
1026
1027   return o;
1028 }
1029
1030 /* During construction we set the pinned flag in the graph right when the
1031    optimizatin is performed.  The flag turning on procedure global cse could
1032    be changed between two allocations.  This way we are safe. */
1033 static INLINE ir_node *
1034 identify_cons (pset *value_table, ir_node *n) {
1035   ir_node *old = n;
1036   n = identify(value_table, n);
1037   if (get_irn_n(old, -1) != get_irn_n(n, -1))
1038     set_irg_pinned(current_ir_graph, floats);
1039   return n;
1040 }
1041
1042 /* Return the canonical node computing the same value as n.
1043    Looks up the node in a hash table, enters it in the table
1044    if it isn't there yet. */
1045 static ir_node *
1046 identify_remember (pset *value_table, ir_node *node)
1047 {
1048   ir_node *o = NULL;
1049
1050   if (!value_table) return node;
1051
1052   /* lookup or insert in hash table with given hash key. */
1053   o = pset_insert (value_table, node, ir_node_hash (node));
1054
1055   if (o == node) return node;
1056
1057   return o;
1058 }
1059
1060 void
1061 add_identities (pset *value_table, ir_node *node) {
1062   identify_remember (value_table, node);
1063 }
1064
1065 /* garbage in, garbage out. If a node has a dead input, i.e., the
1066    Bad node is input to the node, return the Bad node.  */
1067 static INLINE ir_node *
1068 gigo (ir_node *node)
1069 {
1070   int i, irn_arity;
1071   ir_op* op = get_irn_op(node);
1072
1073
1074   /* remove garbage blocks by looking at control flow that leaves the block
1075      and replacing the control flow by Bad. */
1076   if (get_irn_mode(node) == mode_X) {
1077     ir_node *block = get_nodes_block(node);
1078     if (op == op_End) return node;     /* Don't optimize End, may have Bads. */
1079     if (get_irn_op(block) == op_Block && get_Block_matured(block)) {
1080       irn_arity = get_irn_arity(block);
1081       for (i = 0; i < irn_arity; i++) {
1082         if (!is_Bad(get_irn_n(block, i))) break;
1083       }
1084       if (i == irn_arity) return new_Bad();
1085     }
1086   }
1087
1088   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
1089      blocks predecessors is dead. */
1090   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
1091     irn_arity = get_irn_arity(node);
1092     for (i = -1; i < irn_arity; i++) {
1093       if (is_Bad(get_irn_n(node, i))) {
1094         return new_Bad();
1095       }
1096     }
1097   }
1098 #if 0
1099   /* With this code we violate the agreement that local_optimize
1100      only leaves Bads in Block, Phi and Tuple nodes. */
1101   /* If Block has only Bads as predecessors it's garbage. */
1102   /* If Phi has only Bads as predecessors it's garbage. */
1103   if ((op == op_Block && get_Block_matured(node)) || op == op_Phi)  {
1104     irn_arity = get_irn_arity(node);
1105     for (i = 0; i < irn_arity; i++) {
1106       if (!is_Bad(get_irn_n(node, i))) break;
1107     }
1108     if (i == irn_arity) node = new_Bad();
1109   }
1110 #endif
1111   return node;
1112 }
1113
1114
1115 /* These optimizations deallocate nodes from the obstack.
1116    It can only be called if it is guaranteed that no other nodes
1117    reference this one, i.e., right after construction of a node.  */
1118 ir_node *
1119 optimize_node (ir_node *n)
1120 {
1121   tarval *tv;
1122   ir_node *old_n = n;
1123
1124   /* Allways optimize Phi nodes: part of the construction. */
1125   if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
1126
1127   /* constant expression evaluation / constant folding */
1128   if (get_opt_constant_folding()) {
1129     /* constants can not be evaluated */
1130     if  (get_irn_op(n) != op_Const) {
1131       /* try to evaluate */
1132       tv = computed_value (n);
1133       if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1134         /* evaluation was succesful -- replace the node. */
1135         obstack_free (current_ir_graph->obst, n);
1136         return new_Const (get_tarval_mode (tv), tv);
1137       }
1138     }
1139   }
1140
1141   /* remove unnecessary nodes */
1142   if (get_opt_constant_folding() ||
1143       (get_irn_op(n) == op_Phi)  ||   /* always optimize these nodes. */
1144       (get_irn_op(n) == op_Id)   ||
1145       (get_irn_op(n) == op_Proj) ||
1146       (get_irn_op(n) == op_Block)  )  /* Flags tested local. */
1147     n = equivalent_node (n);
1148
1149   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
1150
1151   /** common subexpression elimination **/
1152   /* Checks whether n is already available. */
1153   /* The block input is used to distinguish different subexpressions. Right
1154      now all nodes are pinned to blocks, i.e., the cse only finds common
1155      subexpressions within a block. */
1156   if (get_opt_cse())
1157     n = identify_cons (current_ir_graph->value_table, n);
1158
1159   if (n != old_n) {
1160     /* We found an existing, better node, so we can deallocate the old node. */
1161     obstack_free (current_ir_graph->obst, old_n);
1162   }
1163
1164   /* Some more constant expression evaluation that does not allow to
1165      free the node. */
1166   if (get_opt_constant_folding() ||
1167       (get_irn_op(n) == op_Cond) ||
1168       (get_irn_op(n) == op_Proj))     /* Flags tested local. */
1169     n = transform_node (n);
1170
1171   /* Remove nodes with dead (Bad) input.
1172      Run always for transformation induced Bads. */
1173   n = gigo (n);
1174
1175   /* Now we can verify the node, as it has no dead inputs any more. */
1176   irn_vrfy(n);
1177
1178   /* Now we have a legal, useful node. Enter it in hash table for cse */
1179   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block)) {
1180     n = identify_remember (current_ir_graph->value_table, n);
1181   }
1182
1183   return n;
1184 }
1185
1186
1187 /* These optimizations never deallocate nodes.  This can cause dead
1188    nodes lying on the obstack.  Remove these by a dead node elimination,
1189    i.e., a copying garbage collection. */
1190 ir_node *
1191 optimize_in_place_2 (ir_node *n)
1192 {
1193   tarval *tv;
1194   ir_node *old_n = n;
1195
1196   if (!get_optimize() && (get_irn_op(n) != op_Phi)) return n;
1197
1198   /* if not optimize return n */
1199   if (n == NULL) {
1200     assert(0);
1201     /* Here this is possible.  Why? */
1202     return n;
1203   }
1204
1205
1206   /* constant expression evaluation / constant folding */
1207   if (get_opt_constant_folding()) {
1208     /* constants can not be evaluated */
1209     if  (get_irn_op(n) != op_Const) {
1210       /* try to evaluate */
1211       tv = computed_value (n);
1212       if ((get_irn_mode(n) != mode_T) && (tv != tarval_bad)) {
1213         /* evaluation was succesful -- replace the node. */
1214         n = new_Const (get_tarval_mode (tv), tv);
1215         __dbg_info_merge_pair(n, old_n, dbg_const_eval);
1216         return n;
1217       }
1218     }
1219   }
1220
1221   /* remove unnecessary nodes */
1222   /*if (get_opt_constant_folding()) */
1223   if (get_opt_constant_folding() ||
1224       (get_irn_op(n) == op_Phi)  ||   /* always optimize these nodes. */
1225       (get_irn_op(n) == op_Id)   ||   /* ... */
1226       (get_irn_op(n) == op_Proj) ||   /* ... */
1227       (get_irn_op(n) == op_Block)  )  /* Flags tested local. */
1228     n = equivalent_node (n);
1229
1230   optimize_preds(n);                  /* do node specific optimizations of nodes predecessors. */
1231
1232   /** common subexpression elimination **/
1233   /* Checks whether n is already available. */
1234   /* The block input is used to distinguish different subexpressions.  Right
1235      now all nodes are pinned to blocks, i.e., the cse only finds common
1236      subexpressions within a block. */
1237   if (get_opt_cse()) {
1238     n = identify (current_ir_graph->value_table, n);
1239   }
1240
1241   /* Some more constant expression evaluation. */
1242   if (get_opt_constant_folding() ||
1243       (get_irn_op(n) == op_Cond) ||
1244       (get_irn_op(n) == op_Proj))     /* Flags tested local. */
1245     n = transform_node (n);
1246
1247   /* Remove nodes with dead (Bad) input.
1248      Run always for transformation induced Bads.  */
1249   n = gigo (n);
1250
1251   /* Now we can verify the node, as it has no dead inputs any more. */
1252   irn_vrfy(n);
1253
1254   /* Now we have a legal, useful node. Enter it in hash table for cse.
1255      Blocks should be unique anyways.  (Except the successor of start:
1256      is cse with the start block!) */
1257   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1258     n = identify_remember (current_ir_graph->value_table, n);
1259
1260   return n;
1261 }
1262
1263 /* Wrapper for external use, set proper status bits after optimization */
1264 ir_node *
1265 optimize_in_place (ir_node *n) {
1266   /* Handle graph state */
1267   assert(get_irg_phase_state(current_ir_graph) != phase_building);
1268   if (get_opt_global_cse())
1269     set_irg_pinned(current_ir_graph, floats);
1270   if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1271     set_irg_outs_inconsistent(current_ir_graph);
1272   /* Maybe we could also test whether optimizing the node can
1273      change the control graph. */
1274   if (get_irg_dom_state(current_ir_graph) == dom_consistent)
1275     set_irg_dom_inconsistent(current_ir_graph);
1276   return optimize_in_place_2 (n);
1277 }