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

   1 /* Copyright (C) 1998 - 2000 by Universitaet Karlsruhe
   2 ** All rights reserved.
   3 **
   4 ** Authors: Christian Schaefer, Goetz Lindenmaier
   5 **
   6 ** iropt --- optimizations intertwined with IR construction.
   7 */
   8
   9 # include "irnode_t.h"
  10 # include "irgraph_t.h"
  11 # include "iropt_t.h"
  12 # include "ircons.h"
  13 # include "irgmod.h"
  14 # include "irvrfy.h"
  15 # include "tv.h"
  16 # include "tune.h"
  17
  18
  19 /* Make types visible to allow most efficient access */
  20 # include "entity_t.h"
  21
  22 /* Trivial inlineable routine for copy propagation.
  23    Does follow Ids, needed to optimize inlined code. */
  24 static inline ir_node *
  25 follow_Id (ir_node *n)
  26 {
  27   while (get_irn_op (n) == op_Id) n = get_Id_pred (n);
  28   return n;
  29 }
  30
  31 static inline tarval *
  32 value_of (ir_node *n)
  33 {
  34   if ((n != NULL) && (get_irn_op(n) == op_Const))
  35     return get_Const_tarval(n);
  36   else
  37     return NULL;
  38 }
  39
  40 /* if n can be computed, return the value, else NULL. Performs
  41    constant folding. GL: Only if n is arithmetic operator? */
  42 tarval *
  43 computed_value (ir_node *n)
  44 {
  45   tarval *res;
  46
  47   ir_node *a = NULL, *b = NULL;  /* initialized to shut up gcc */
  48   tarval *ta = NULL, *tb = NULL; /* initialized to shut up gcc */
  49
  50   res = NULL;
  51
  52   /* get the operands we will work on for simple cases. */
  53   if (is_binop(n)) {
  54     a = get_binop_left(n);
  55     b = get_binop_right(n);
  56   } else if (is_unop(n)) {
  57     a = get_unop_op(n);
  58   }
  59
  60   /* if the operands are constants, get the target value, else set it NULL.
  61      (a and b may be NULL if we treat a node that is no computation.) */
  62   ta = value_of (a);
  63   tb = value_of (b);
  64
  65   /* Perform the constant evaluation / computation. */
  66   switch (get_irn_opcode(n)) {
  67   case iro_Const:
  68     res = get_Const_tarval(n);
  69   case iro_Add:
  70     if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
  71         && (get_irn_mode(a) != mode_p)) {
  72       res = tarval_add (ta, tb);
  73     }
  74     break;
  75   case iro_Sub:
  76     if (ta && tb && (get_irn_mode(a) == get_irn_mode(b))
  77         && (get_irn_mode(a) != mode_p)) {
  78       res = tarval_sub (ta, tb);
  79     } else if (a == b) {
  80       res = tarval_mode_null [get_irn_modecode (n)];
  81     }
  82     break;
  83   case iro_Minus:
  84       if (ta && mode_is_float(get_irn_mode(a)))
  85         res = /*tarval_minus (ta);*/ res;
  86     break;
  87   case iro_Mul:
  88     if (ta && tb) /* tarval_mul tests for equivalent modes itself */ {
  89       res = tarval_mul (ta, tb);
  90     } else {
  91       /* calls computed_value recursive and returns the 0 with proper
  92          mode.  Why is this an extra case? */
  93       tarval *v;
  94       if (   (tarval_classify ((v = computed_value (a))) == 0)
  95           || (tarval_classify ((v = computed_value (b))) == 0)) {
  96         res = v;
  97       }
  98     }
  99     break;
 100   case iro_Abs:
 101     if (ta)
 102       res = /*tarval_abs (ta);*/ res;
 103     /* allowed or problems with max/min ?? */
 104     break;
 105   case iro_And:
 106     if (ta && tb) {
 107       res = tarval_and (ta, tb);
 108     } else {
 109       tarval *v;
 110       if (   (tarval_classify ((v = computed_value (a))) == 0)
 111           || (tarval_classify ((v = computed_value (b))) == 0)) {
 112         res = v;
 113       }
 114     }
 115     break;
 116   case iro_Or:
 117     if (ta && tb) {
 118       res = tarval_or (ta, tb);
 119     } else {
 120       tarval *v;
 121       if (   (tarval_classify ((v = computed_value (a))) == -1)
 122           || (tarval_classify ((v = computed_value (b))) == -1)) {
 123         res = v;
 124       }
 125     }
 126     break;
 127   case iro_Eor: if (ta && tb) { res = tarval_eor (ta, tb); } break;
 128   case iro_Not: if (ta)       { /*res = tarval_not (ta)*/; } break;
 129   case iro_Shl: if (ta && tb) { res = tarval_shl (ta, tb); } break;
 130   case iro_Shr: if (ta && tb) { res = tarval_shr (ta, tb); } break;
 131   case iro_Shrs: if(ta && tb) { /*res = tarval_shrs (ta, tb)*/; } break;
 132   case iro_Rot: if (ta && tb) { /*res = tarval_rot (ta, tb)*/; } break;
 133   case iro_Conv: if(ta)    { res = tarval_convert_to (ta, get_irn_mode (n)); }
 134     break;
 135   case iro_Proj:
 136     {
 137       ir_node *aa, *ab;
 138
 139       a = get_Proj_pred(n);
 140       /* Optimize Cmp nodes.
 141          This performs a first step of unreachable code elimination.
 142          Proj can not be computed, but folding a Cmp above the Proj here is
 143          not as wasteful as folding a Cmp into a Tuple of 16 Consts of which
 144          only 1 is used.
 145          There are several case where we can evaluate a Cmp node:
 146          1. The nodes compared are both the same.  If we compare for
 147             equal, this will return true, else it will return false.
 148             This step relies on cse.
 149          2. The predecessors of Cmp are target values.  We can evaluate
 150             the Cmp.
 151          3. The predecessors are Allocs or void* constants.  Allocs never
 152             return NULL, they raise an exception.   Therefore we can predict
 153             the Cmp result. */
 154       if (get_irn_op(a) == op_Cmp) {
 155         aa = get_Cmp_left(a);
 156         ab = get_Cmp_right(a);
 157         if (aa == ab) { /* 1.: */
 158           /* This is a tric with the bits used for encoding the Cmp
 159              Proj numbers, the following statement is not the same:
 160           res = tarval_from_long (mode_b, (get_Proj_proj(n) == Eq)):    */
 161           res = tarval_from_long (mode_b, (get_Proj_proj(n) & irpn_Eq));
 162         } else {
 163           tarval *taa = computed_value (aa);
 164           tarval *tab = computed_value (ab);
 165           if (taa && tab) { /* 2.: */
 166             /* strange checks... */
 167             ir_pncmp flags = tarval_comp (taa, tab);
 168             if (flags != irpn_False) {
 169               res = tarval_from_long (mode_b, get_Proj_proj(n) & flags);
 170             }
 171           } else {  /* check for 3.: */
 172             ir_node *aaa = skip_nop(skip_Proj(aa));
 173             ir_node *aba = skip_nop(skip_Proj(ab));
 174             if (   (   (/* aa is ProjP and aaa is Alloc */
 175                            (get_irn_op(aa) == op_Proj)
 176                         && (get_irn_mode(aa) == mode_p)
 177                         && (get_irn_op(aaa) == op_Alloc))
 178                     && (   (/* ab is constant void */
 179                                (get_irn_op(ab) == op_Const)
 180                             && (get_irn_mode(ab) == mode_p)
 181                             && (get_Const_tarval(ab) == tarval_p_void))
 182                         || (/* ab is other Alloc */
 183                                (get_irn_op(ab) == op_Proj)
 184                             && (get_irn_mode(ab) == mode_p)
 185                             && (get_irn_op(aba) == op_Alloc)
 186                             && (aaa != aba))))
 187                 || (/* aa is void and aba is Alloc */
 188                        (get_irn_op(aa) == op_Const)
 189                     && (get_irn_mode(aa) == mode_p)
 190                     && (get_Const_tarval(aa) == tarval_p_void)
 191                     && (get_irn_op(ab) == op_Proj)
 192                     && (get_irn_mode(ab) == mode_p)
 193                     && (get_irn_op(aba) == op_Alloc)))
 194               /* 3.: */
 195               res = tarval_from_long (mode_b, get_Proj_proj(n) & irpn_Ne);
 196           }
 197         }
 198       } else {
 199         /* printf(" # comp_val: Proj node, not optimized\n"); */
 200       }
 201     }
 202     break;
 203   default:  ;
 204   }
 205
 206   return res;
 207 }  /* compute node */
 208
 209
 210
 211 /* returns 1 if the a and b are pointers to different locations. */
 212 bool
 213 different_identity (ir_node *a, ir_node *b)
 214 {
 215   assert (get_irn_mode (a) == mode_p
 216           && get_irn_mode (b) == mode_p);
 217
 218   if (get_irn_op (a) == op_Proj && get_irn_op(b) == op_Proj) {
 219     ir_node *a1 = get_Proj_pred (a);
 220     ir_node *b1 = get_Proj_pred (b);
 221     if (a1 != b1 && get_irn_op (a1) == op_Alloc
 222                  && get_irn_op (b1) == op_Alloc)
 223       return 1;
 224   }
 225   return 0;
 226 }
 227
 228
 229 /* equivalent_node returns a node equivalent to N.  It skips all nodes that
 230    perform no actual computation, as, e.g., the Id nodes.  It does not create
 231    new nodes.  It is therefore safe to free N if the node returned is not N.
 232    If a node returns a Tuple we can not just skip it.  If the size of the
 233    in array fits, we transform n into a tuple (e.g., Div). */
 234 static ir_node *
 235 equivalent_node (ir_node *n)
 236 {
 237   int ins;
 238   ir_node *a = NULL; /* to shutup gcc */
 239   ir_node *b = NULL; /* to shutup gcc */
 240   ir_node *c = NULL; /* to shutup gcc */
 241
 242   ins = get_irn_arity (n);
 243
 244   /* get the operands we will work on */
 245   if (is_binop(n)) {
 246     a = get_binop_left(n);
 247     b = get_binop_right(n);
 248   } else if (is_unop(n)) {
 249     a = get_unop_op(n);
 250   }
 251
 252   /* skip unnecessary nodes. */
 253   switch (get_irn_opcode (n)) {
 254   case iro_Block:
 255     {
 256       /* The Block constructor does not call optimize, but mature_block
 257          calls the optimization. */
 258       assert(get_Block_matured(n));
 259
 260       /* A single entry Block following a single exit Block can be merged,
 261          if it is not the Start block. */
 262       /* !!! Beware, all Phi-nodes of n must have been optimized away.
 263          This is true, as the block is matured before optimize is called.   */
 264       if (get_Block_n_cfgpreds(n) == 1
 265           && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
 266         n = get_nodes_Block(get_Block_cfgpred(n, 0));
 267
 268       } else if (n != current_ir_graph->start_block) {
 269         int i;
 270         /* If all inputs are dead, this block is dead too, except if it is
 271            the start block.  This is a step of unreachable code elimination */
 272         for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
 273           if (!is_Bad(get_Block_cfgpred(n, i))) break;
 274         }
 275         if (i == get_Block_n_cfgpreds(n))
 276           n = new_Bad();
 277       }
 278     }
 279     break;
 280
 281   case iro_Jmp:  /* GL: Why not same for op_Raise?? */
 282     /* unreachable code elimination */
 283     if (is_Bad(get_nodes_Block(n)))  n = new_Bad();
 284     break;
 285   /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
 286      See cases for iro_Cond and iro_Proj in transform_node. */
 287   /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
 288   case iro_Or:  if (a == b) {n = a; break;}
 289   case iro_Add:
 290   case iro_Eor:
 291     { tarval *tv;
 292       ir_node *on;
 293       /* After running compute_node there is only one constant predecessor.
 294          Find this predecessors value and remember the other node: */
 295       if ((tv = computed_value (a))) {
 296         on = b;
 297       } else if ((tv = computed_value (b))) {
 298         on = a;
 299       } else break;
 300
 301       /* If this predecessors constant value is zero, the operation is
 302          unnecessary. Remove it: */
 303       if (tarval_classify (tv) == 0) {
 304         n = on;
 305       }
 306     }
 307     break;
 308   case iro_Sub:
 309   case iro_Shl:
 310   case iro_Shr:
 311   case iro_Shrs:
 312   case iro_Rot:
 313     /* these operations are not commutative.  Test only one predecessor. */
 314     if (tarval_classify (computed_value (b)) == 0) {
 315       n = a;
 316       /* Test if b > #bits of a ==> return 0 / divide b by #bits
 317          --> transform node? */
 318     }
 319     break;
 320   case iro_Not:   /* NotNot x == x */
 321   case iro_Minus: /* --x == x */  /* ??? Is this possible or can --x raise an
 322                                      out of bounds exception if min =! max? */
 323     if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
 324       n = get_unop_op(get_unop_op(n));
 325     break;
 326   case iro_Mul:
 327     /* Mul is commutative and has again an other neutral element. */
 328     if (tarval_classify (computed_value (a)) == 1) {
 329       n = b;
 330     } else if (tarval_classify (computed_value (b)) == 1) {
 331       n = a;
 332     }
 333     break;
 334   case iro_Div:
 335     /* Div is not commutative. */
 336     if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
 337       /* Turn Div into a tuple (mem, bad, a) */
 338       ir_node *mem = get_Div_mem(n);
 339       turn_into_tuple(n, 3);
 340       set_Tuple_pred(n, 0, mem);
 341       set_Tuple_pred(n, 1, new_Bad());
 342       set_Tuple_pred(n, 2, a);
 343     }
 344     break;
 345     /* GL: Why are they skipped?  DivMod allocates new nodes --> it's
 346        teated in transform node.
 347   case iro_Mod, Quot, DivMod
 348     */
 349   case iro_And:
 350     if (a == b) n = a;
 351     /* And has it's own neutral element */
 352     else if (tarval_classify (computed_value (a)) == -1) {
 353       n = b;
 354     } else if (tarval_classify (computed_value (b)) == -1) {
 355       n = a;
 356     }
 357     break;
 358   case iro_Conv:
 359     if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
 360       n = a;
 361     } else if (get_irn_mode(n) == mode_b) {
 362       if (get_irn_op(a) == op_Conv &&
 363           get_irn_mode (get_Conv_op(a)) == mode_b) {
 364         n = get_Conv_op(a);     /* Convb(Conv*(xxxb(...))) == xxxb(...) */
 365       }
 366     }
 367     break;
 368
 369   case iro_Phi:
 370     {
 371       /* Several optimizations:
 372          - no Phi in start block.
 373          - remove Id operators that are inputs to Phi
 374          - fold Phi-nodes, iff they have only one predecessor except
 375            themselves.
 376       */
 377       int i, n_preds;
 378       ir_node *block = NULL;     /* to shutup gcc */
 379       ir_node *first_val = NULL; /* to shutup gcc */
 380       ir_node *scnd_val = NULL;  /* to shutup gcc */
 381
 382       n_preds = get_Phi_n_preds(n);
 383
 384       block = get_nodes_Block(n);
 385       assert(get_irn_op (block) == op_Block);
 386
 387       /* there should be no Phi nodes in the Start region. */
 388       if (block == current_ir_graph->start_block) {
 389         n = new_Bad();
 390         break;
 391       }
 392
 393       if (n_preds == 0) {       /* Phi of dead Region without predecessors. */
 394         /* GL: why not return new_Bad? */
 395         break;
 396       }
 397
 398 #if 0
 399       /* first we test for a special case: */
 400       /* Confirm is a special node fixing additional information for a
 401          value that is known at a certain point.  This is useful for
 402          dataflow analysis. */
 403       if (n_preds == 2) {
 404         ir_node *a = follow_Id (get_Phi_pred(n, 0));
 405         ir_node *b = follow_Id (get_Phi_pred(n, 1));
 406         if (   (get_irn_op(a) == op_Confirm)
 407             && (get_irn_op(b) == op_Confirm)
 408             && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
 409             && (get_irn_n(a, 1) == get_irn_n (b, 1))
 410             && (a->data.num == (~b->data.num & irpn_True) )) {
 411           n = follow_Id (get_irn_n(a, 0));
 412           break;
 413         }
 414       }
 415 #endif
 416       /* Find first non-self-referencing input */
 417       for (i = 0;  i < n_preds;  ++i) {
 418         first_val = follow_Id(get_Phi_pred(n, i));
 419         /* skip Id's */
 420         set_Phi_pred(n, i, first_val);
 421         if (   (first_val != n)                            /* not self pointer */
 422                && (get_irn_op(first_val) != op_Bad)        /* value not dead */
 423             && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
 424           break;                         /* then found first value. */
 425         }
 426       }
 427
 428       /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
 429       if (i > n_preds) { n = new_Bad();  break; }
 430
 431       scnd_val = NULL;
 432
 433       /* follow_Id () for rest of inputs, determine if any of these
 434          are non-self-referencing */
 435       while (++i < n_preds) {
 436         scnd_val = follow_Id(get_Phi_pred(n, i));
 437         /* skip Id's */
 438         set_Phi_pred(n, i, scnd_val);
 439         if (   (scnd_val != n)
 440             && (scnd_val != first_val)
 441             && (get_irn_op(scnd_val) != op_Bad)
 442             && !(is_Bad (get_Block_cfgpred(block, i))) ) {
 443           break;
 444         }
 445       }
 446
 447       /* Fold, if no multiple distinct non-self-referencing inputs */
 448       if (i > n_preds) {
 449         n = a;
 450       } else {
 451       /* skip the remaining Ids. */
 452         while (++i < n_preds) {
 453           set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
 454         }
 455       }
 456     }
 457     break;
 458
 459   case iro_Load:
 460     {
 461       a = skip_Proj(get_Load_mem(n));
 462       b = skip_Proj(get_Load_ptr(n));
 463
 464       if (get_irn_op(a) == op_Store) {
 465         if ( different_identity (b, get_Store_ptr(a))) {
 466           /* load and store use different pointers, therefore load
 467              needs not take store's memory but the state before. */
 468           set_Load_mem (n, get_Store_mem(a));
 469         } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
 470         }
 471       }
 472     }
 473       break;
 474   case iro_Store:
 475     /* remove unnecessary store. */
 476     {
 477       a = skip_Proj(get_Store_mem(n));
 478       b = get_Store_ptr(n);
 479       c = skip_Proj(get_Store_value(n));
 480
 481       if (get_irn_op(a) == op_Store
 482           && get_Store_ptr(a) == b
 483           && skip_Proj(get_Store_value(a)) == c) {
 484         /* We have twice exactly the same store -- a write after write. */
 485         n = a;
 486       } else if (get_irn_op(c) == op_Load
 487                  && (a == c || skip_Proj(get_Load_mem(c)) == a)
 488                  && get_Load_ptr(c) == b )
 489                  /* !!!??? and a cryptic test */ {
 490         /* We just loaded the value from the same memory, i.e., the store
 491            doesn't change the memory -- a write after read. */
 492         turn_into_tuple(n, 2);
 493         set_Tuple_pred(n, 0, a);
 494         set_Tuple_pred(n, 1, new_Bad());
 495       }
 496     }
 497     break;
 498
 499   case iro_Proj:
 500     {
 501       a = get_Proj_pred(n);
 502
 503       if ( get_irn_op(a) == op_Tuple) {
 504         /* Remove the Tuple/Proj combination. */
 505         if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
 506           n = get_Tuple_pred(a, get_Proj_proj(n));
 507         } else {
 508           assert(0); /* This should not happen! (GL added this assert) */
 509           n = new_Bad();
 510         }
 511       } else if (get_irn_mode(n) == mode_X &&
 512                  is_Bad(get_nodes_Block(n))) {
 513         /* Remove dead control flow. */
 514         n = new_Bad();
 515       }
 516     }
 517     break;
 518
 519   case iro_Id:
 520     n = follow_Id (n);
 521     break;
 522
 523   default: break;
 524   }
 525
 526   return n;
 527 } /* end equivalent_node() */
 528
 529
 530 /* tries several [inplace] [optimizing] transformations and returns a
 531    equivalent node.  The difference to equivalent_node is that these
 532    transformations _do_ generate new nodes, and thus the old node must
 533    not be freed even if the equivalent node isn't the old one. */
 534 static ir_node *
 535 transform_node (ir_node *n)
 536 {
 537
 538   ir_node *a = NULL, *b;
 539   tarval *ta, *tb;
 540
 541   switch (get_irn_opcode(n)) {
 542   case iro_DivMod: {
 543
 544     int evaluated = 0;
 545     ir_mode *mode;
 546
 547     a = get_DivMod_left(n);
 548     b = get_DivMod_right(n);
 549     mode = get_irn_mode(a);
 550
 551     if (!(   mode_is_int(get_irn_mode(a))
 552           && mode_is_int(get_irn_mode(b))))
 553       break;
 554
 555     if (a == b) {
 556       a = new_Const (mode, tarval_from_long (mode, 1));
 557       b = new_Const (mode, tarval_from_long (mode, 0));
 558       evaluated = 1;
 559     } else {
 560       ta = value_of(a);
 561       tb = value_of(b);
 562
 563       if (tb) {
 564         if (tarval_classify(tb) == 1) {
 565           b = new_Const (mode, tarval_from_long (mode, 0));
 566           evaluated = 1;
 567         } else if (ta) {
 568           tarval *resa, *resb;
 569           resa = tarval_div (ta, tb);
 570           if (!resa) break; /* Causes exception!!! Model by replacing through
 571                                Jmp for X result!? */
 572           resb = tarval_mod (ta, tb);
 573           if (!resb) break; /* Causes exception! */
 574           a = new_Const (mode, resa);
 575           b = new_Const (mode, resb);
 576           evaluated = 1;
 577         }
 578       } else if (tarval_classify (ta) == 0) {
 579         b = a;
 580         evaluated = 1;
 581       }
 582     }
 583     if (evaluated) { /* replace by tuple */
 584       ir_node *mem = get_DivMod_mem(n);
 585       turn_into_tuple(n, 4);
 586       set_Tuple_pred(n, 0, mem);
 587       set_Tuple_pred(n, 1, new_Bad());  /* no exception */
 588       set_Tuple_pred(n, 2, a);
 589       set_Tuple_pred(n, 3, b);
 590       assert(get_nodes_Block(n));
 591     }
 592   }
 593   break;
 594
 595   case iro_Cond: {
 596     /* Replace the Cond by a Jmp if it branches on a constant
 597        condition. */
 598     ir_node *jmp;
 599     a = get_Cond_selector(n);
 600     ta = value_of(a);
 601
 602     if (ta && (get_irn_mode(a) == mode_b)) {
 603       /* It's a boolean Cond, branching on a boolean constant.
 604          Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
 605       jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
 606       turn_into_tuple(n, 2);
 607       if (tv_val_b(ta) == 1)  /* GL: I hope this returns 1 if true */ {
 608         set_Tuple_pred(n, 0, new_Bad());
 609         set_Tuple_pred(n, 1, jmp);
 610       } else {
 611         set_Tuple_pred(n, 0, jmp);
 612         set_Tuple_pred(n, 1, new_Bad());
 613       }
 614     } else if (ta && (get_irn_mode(a) == mode_I)) {
 615       /* I don't want to allow Tuples smaller than the biggest Proj.
 616          Also this tuple might get really big...
 617          I generate the Jmp here, and remember it in link.  Link is used
 618          when optimizing Proj. */
 619       set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 620     } else if (   (get_irn_op(get_Cond_selector(n)) == op_Eor)
 621                && (get_irn_mode(get_Cond_selector(n)) == mode_b)
 622                && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
 623       /* The Eor is a negate.  Generate a new Cond without the negate,
 624          simulate the negate by exchanging the results. */
 625       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 626                                  get_Eor_left(a)));
 627     } else if (   (get_irn_op(get_Cond_selector(n)) == op_Not)
 628                && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
 629       /* A Not before the Cond.  Generate a new Cond without the Not,
 630          simulate the Not by exchanging the results. */
 631       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 632                                  get_Not_op(a)));
 633     }
 634   }
 635   break;
 636
 637   case iro_Proj: {
 638     a = get_Proj_pred(n);
 639
 640     if (  (get_irn_op(a) == op_Cond)
 641         && get_irn_link(a)
 642         && get_irn_op(get_irn_link(a)) == op_Cond) {
 643     /* Use the better Cond if the Proj projs from a Cond which get's
 644        its result from an Eor/Not. */
 645       assert (   (   (get_irn_op(get_Cond_selector(a)) == op_Eor)
 646                      || (get_irn_op(get_Cond_selector(a)) == op_Not))
 647               && (get_irn_mode(get_Cond_selector(a)) == mode_b)
 648               && (get_irn_op(get_irn_link(a)) == op_Cond)
 649               && (get_Cond_selector(get_irn_link(a)) ==
 650                   get_Eor_left(get_Cond_selector(a))));
 651       set_Proj_pred(n, get_irn_link(a));
 652       if (get_Proj_proj(n) == 0)
 653         set_Proj_proj(n, 1);
 654       else
 655         set_Proj_proj(n, 0);
 656     } else if (   (get_irn_op(a) == op_Cond)
 657                && (get_irn_mode(get_Cond_selector(a)) == mode_I)
 658                && value_of(a)) {
 659       /* The Cond is a Switch on a Constant */
 660       if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
 661         /* The always taken branch, reuse the existing Jmp. */
 662         if (!get_irn_link(a)) /* well, if it exists ;-> */
 663           set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 664         assert(get_irn_op(get_irn_link(a)) == op_Jmp);
 665         n = get_irn_link(a);
 666       } else {
 667         /* a never taken branch */
 668         n = new_Bad();
 669       }
 670     }
 671   }
 672   break;
 673   case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
 674     a = get_Eor_left(n);
 675     b = get_Eor_right(n);
 676
 677     if (   (get_irn_mode(n) == mode_b)
 678         && (get_irn_op(a) == op_Proj)
 679         && (get_irn_mode(a) == mode_b)
 680         && (tarval_classify (computed_value (b)) == 1)
 681         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 682       /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
 683       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 684                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 685     else if (   (get_irn_mode(n) == mode_b)
 686              && (tarval_classify (computed_value (b)) == 1))
 687       /* The Eor is a Not. Replace it by a Not. */
 688       /*   ????!!!Extend to bitfield 1111111. */
 689       n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
 690   }
 691   break;
 692   case iro_Not: {
 693     a = get_Not_op(n);
 694
 695     if (   (get_irn_mode(n) == mode_b)
 696         && (get_irn_op(a) == op_Proj)
 697         && (get_irn_mode(a) == mode_b)
 698         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 699       /* We negate a Cmp. The Cmp has the negated result anyways! */
 700       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 701                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 702   }
 703   break;
 704   default: ;
 705   }
 706   return n;
 707 }
 708
 709 /***************** Common Subexpression Elimination *****************/
 710
 711 /* Compare function for two nodes in the hash table.   Gets two     */
 712 /* nodes as parameters.                                             */
 713 /* @@@  a+b != b+a ? */
 714 static int
 715 vt_cmp (const void *elt, const void *key)
 716 {
 717   ir_node *a, *b;
 718   int i;
 719
 720   a = (void *)elt;
 721   b = (void *)key;
 722
 723   if (a == b) return 0;
 724
 725   if ((get_irn_op(a) != get_irn_op(b)) ||
 726       (get_irn_mode(a) != get_irn_mode(b))) return 1;
 727
 728   /* compare if a's in and b's in are equal */
 729   /* GL: we optimize only nodes with in arrays of fixed sizes.
 730   if (get_irn_arity (a) != -2) {
 731     ins = get_irn_arity (a);
 732     if (ins != get_irn_arity (b)) return 1;
 733     ain = get_irn_in (a);
 734     bin = get_irn_in (b);
 735   }
 736   */
 737   if (get_irn_arity (a) != get_irn_arity(b))
 738     return 1;
 739
 740   /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
 741   /* do if (*ain++ != *bin++) return 1; while (ins--); */
 742   for (i = -1; i < get_irn_arity(a); i++)
 743     if (get_irn_n(a, i) != get_irn_n(b, i))
 744       return 1;
 745
 746
 747   switch (get_irn_opcode(a)) {
 748   case iro_Const:
 749     return get_irn_const_attr (a) != get_irn_const_attr (b);
 750   case iro_Proj:
 751     return get_irn_proj_attr (a) != get_irn_proj_attr (b);
 752   case iro_Alloc:
 753     return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
 754       || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
 755   case iro_Free:
 756     return (get_irn_free_attr(a) != get_irn_free_attr(b));
 757   case iro_SymConst:
 758     return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
 759       || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
 760   case iro_Call:
 761     return (get_irn_call_attr(a)->kind != get_irn_call_attr(b)->kind)
 762       || (get_irn_call_attr(a)->arity != get_irn_call_attr(b)->arity);
 763   case iro_Sel:
 764     return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
 765       || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
 766       || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
 767       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
 768       || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
 769       || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
 770   case iro_Phi:
 771     return get_irn_phi_attr (a) != get_irn_phi_attr (b);
 772   default: ;
 773   }
 774
 775   return 0;
 776 }
 777
 778 static unsigned
 779 ir_node_hash (ir_node *node)
 780 {
 781   unsigned h;
 782   int i;
 783
 784   /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
 785   h = get_irn_arity(node);
 786
 787   /* consider all in nodes... except the block. */
 788   for (i = 0;  i < get_irn_arity(node);  i++) {
 789     h = 9*h + (unsigned long)get_irn_n(node, i);
 790   }
 791
 792   /* ...mode,... */
 793   h = 9*h + (unsigned long) get_irn_mode (node);
 794   /* ...and code */
 795   h = 9*h + (unsigned long) get_irn_op (node);
 796
 797   return h;
 798 }
 799
 800 pset *
 801 new_identities (void)
 802 {
 803   return new_pset (vt_cmp, TUNE_NIR_NODES);
 804 }
 805
 806 void
 807 del_identities (pset *value_table)
 808 {
 809   del_pset (value_table);
 810 }
 811
 812 /* Return the canonical node computing the same value as n.
 813    Looks up the node in a hash table. */
 814 static inline ir_node *
 815 identify (pset *value_table, ir_node *n)
 816 {
 817   ir_node *o = NULL;
 818
 819   if (!value_table) return n;
 820
 821   switch (get_irn_opcode (n)) {
 822   case iro_Add:
 823   case iro_Mul:
 824   case iro_Or:
 825   case iro_And:
 826   case iro_Eor:
 827     {
 828       /* for commutative operators perform  a OP b == b OP a */
 829       if (get_binop_left(n) > get_binop_right(n)) {
 830         ir_node *h = get_binop_left(n);
 831         set_binop_left(n, get_binop_right(n));
 832         set_binop_right(n, h);
 833       }
 834     }
 835   break;
 836   default: break;
 837   }
 838   o = pset_find (value_table, n, ir_node_hash (n));
 839   if (!o) return n;
 840
 841   return o;
 842 }
 843
 844 /* Return the canonical node computing the same value as n.
 845    Looks up the node in a hash table, enters it in the table
 846    if it isn't there yet. */
 847 static ir_node *
 848 identify_remember (pset *value_table, ir_node *node)
 849 {
 850   ir_node *o = NULL;
 851
 852   if (!value_table) return node;
 853
 854   /* lookup or insert in hash table with given hash key. */
 855   o = pset_insert (value_table, node, ir_node_hash (node));
 856
 857   if (o == node) return node;
 858
 859   return o;
 860 }
 861
 862 /* garbage in, garbage out. If a node has a dead input, i.e., the
 863    Bad node is input to the node, return the Bad node.  */
 864 static inline ir_node *
 865 gigo (ir_node *node)
 866 {
 867   int i;
 868   ir_op* op = get_irn_op(node);
 869
 870   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
 871      blocks predecessors is dead. */
 872   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
 873     for (i = -1; i < get_irn_arity(node); i++) {
 874       if (is_Bad(get_irn_n(node, i))) {
 875         node = new_Bad();
 876         break;
 877       }
 878     }
 879   }
 880   return node;
 881 }
 882
 883
 884 /* These optimizations deallocate nodes from the obstack.
 885    It can only be called if it is guaranteed that no other nodes
 886    reference this one, i.e., right after construction of a node.  */
 887 ir_node *
 888 optimize (ir_node *n)
 889 {
 890   tarval *tv;
 891   ir_node *old_n = n;
 892
 893   /* Allways optimize Phi nodes: part of the construction. */
 894   if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
 895
 896   /* if not optimize return n */
 897   if (n == NULL) {
 898     printf(" attention: empty node!!! \n");
 899     return n;
 900   }
 901
 902   /* constant expression evaluation / constant folding */
 903   if (get_opt_constant_folding()) {
 904     /* constants can not be evaluated */
 905     if  (get_irn_op(n) != op_Const) {
 906       /* try to evaluate */
 907       tv = computed_value (n);
 908       if (tv != NULL) {
 909         /* evaluation was succesful -- replace the node. */
 910         obstack_free (current_ir_graph->obst, n);
 911         return new_Const (get_tv_mode (tv), tv);
 912       }
 913     }
 914   }
 915
 916   /* remove unnecessary nodes */
 917   if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
 918     n = equivalent_node (n);
 919
 920   /** common subexpression elimination **/
 921   /* Checks whether n is already available. */
 922   /* The block input is used to distinguish different subexpressions. Right
 923      now all nodes are pinned to blocks, i.e., the cse only finds common
 924      subexpressions within a block. */
 925   if (get_opt_cse())
 926     n = identify (current_ir_graph->value_table, n);
 927   /* identify found a cse, so deallocate the old node. */
 928   if (n != old_n) {
 929     obstack_free (current_ir_graph->obst, old_n);
 930     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
 931   }
 932
 933   /* Some more constant expression evaluation that does not allow to
 934      free the node. */
 935   if (get_opt_constant_folding())
 936     n = transform_node (n);
 937
 938   /* Remove nodes with dead (Bad) input. */
 939   n = gigo (n);
 940   /* Now we can verify the node, as it has no dead inputs any more. */
 941   irn_vrfy(n);
 942
 943   /* Now we have a legal, useful node. Enter it in hash table for cse */
 944   if (get_opt_cse()) {
 945     n = identify_remember (current_ir_graph->value_table, n);
 946   }
 947
 948 #if 0  /* GL: what's the use of this?? */
 949   if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
 950     assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
 951     pdeq_putr (current_ir_graph->keep.living, n);
 952   }
 953 #endif
 954   return n;
 955 }
 956
 957
 958 /* These optimizations never deallocate nodes.  This can cause dead
 959    nodes lying on the obstack.  Remove these by a dead node elimination,
 960    i.e., a copying garbage collection. */
 961 ir_node *
 962 optimize_in_place (ir_node *n)
 963 {
 964
 965   tarval *tv;
 966   ir_node *old_n = n;
 967
 968   /* if not optimize return n */
 969   if (n == NULL) {
 970     /* Here this is possible.  Why? */
 971     return n;
 972   }
 973
 974   /* constant expression evaluation / constant folding */
 975   if (get_opt_constant_folding()) {
 976     /* constants can not be evaluated */
 977     if  (get_irn_op(n) != op_Const) {
 978       /* try to evaluate */
 979       tv = computed_value (n);
 980       if (tv != NULL) {
 981         /* evaluation was succesful -- replace the node. */
 982         return new_Const (get_tv_mode (tv), tv);
 983         /* xprintf("* optimize: computed node %I\n", n->op->name);*/
 984       }
 985     }
 986   }
 987
 988   /* remove unnecessary nodes */
 989   if (get_opt_constant_folding())
 990     //  if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
 991     n = equivalent_node (n);
 992
 993   /** common subexpression elimination **/
 994   /* Checks whether n is already available. */
 995   /* The block input is used to distinguish different subexpressions.  Right
 996      now all nodes are pinned to blocks, i.e., the cse only finds common
 997      subexpressions within a block. */
 998   if (get_opt_cse())
 999     n = identify (current_ir_graph->value_table, n);
1000
1001   /* identify found a cse, so deallocate the old node. */
1002   if (n != old_n) {
1003     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
1004   }
1005
1006   /* Some more constant expression evaluation. */
1007   if (get_opt_constant_folding())
1008     n = transform_node (n);
1009
1010   /* Remove nodes with dead (Bad) input. */
1011   n = gigo (n);
1012   /* Now we can verify the node, as it has no dead inputs any more. */
1013   irn_vrfy(n);
1014
1015   /* Now we have a legal, useful node. Enter it in hash table for cse */
1016   if (get_opt_cse()) {
1017     /* aborts ??! set/pset can not handle several hash tables??!
1018        No, suddenly it works. */
1019     n = identify_remember (current_ir_graph->value_table, n);
1020   }
1021
1022   return n;
1023 }