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