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          Remaining Phi nodes are just Ids. */
 303       if (get_Block_n_cfgpreds(n) == 1
 304           && get_irn_op(get_Block_cfgpred(n, 0)) == op_Jmp) {
 305         n = get_nodes_Block(get_Block_cfgpred(n, 0));
 306
 307       } else if ((n != current_ir_graph->start_block) &&
 308                  (n != current_ir_graph->end_block)     ) {
 309         int i;
 310         /* If all inputs are dead, this block is dead too, except if it is
 311            the start or end block.  This is a step of unreachable code
 312            elimination */
 313         for (i = 0; i < get_Block_n_cfgpreds(n); i++) {
 314           if (!is_Bad(get_Block_cfgpred(n, i))) break;
 315         }
 316         if (i == get_Block_n_cfgpreds(n))
 317           n = new_Bad();
 318       }
 319     }
 320     break;
 321
 322   case iro_Jmp:  /* GL: Why not same for op_Raise?? */
 323     /* unreachable code elimination */
 324     if (is_Bad(get_nodes_Block(n)))  n = new_Bad();
 325     break;
 326   /* We do not evaluate Cond here as we replace it by a new node, a Jmp.
 327      See cases for iro_Cond and iro_Proj in transform_node. */
 328   /** remove stuff as x+0, x*1 x&true ... constant expression evaluation **/
 329   case iro_Or:  if (a == b) {n = a; break;}
 330   case iro_Add:
 331   case iro_Eor:
 332     { tarval *tv;
 333       ir_node *on;
 334       /* After running compute_node there is only one constant predecessor.
 335          Find this predecessors value and remember the other node: */
 336       if ((tv = computed_value (a))) {
 337         on = b;
 338       } else if ((tv = computed_value (b))) {
 339         on = a;
 340       } else break;
 341
 342       /* If this predecessors constant value is zero, the operation is
 343          unnecessary. Remove it: */
 344       if (tarval_classify (tv) == 0) {
 345         n = on;
 346       }
 347     }
 348     break;
 349   case iro_Sub:
 350   case iro_Shl:
 351   case iro_Shr:
 352   case iro_Shrs:
 353   case iro_Rot:
 354     /* these operations are not commutative.  Test only one predecessor. */
 355     if (tarval_classify (computed_value (b)) == 0) {
 356       n = a;
 357       /* Test if b > #bits of a ==> return 0 / divide b by #bits
 358          --> transform node? */
 359     }
 360     break;
 361   case iro_Not:   /* NotNot x == x */
 362   case iro_Minus: /* --x == x */  /* ??? Is this possible or can --x raise an
 363                                      out of bounds exception if min =! max? */
 364     if (get_irn_op(get_unop_op(n)) == get_irn_op(n))
 365       n = get_unop_op(get_unop_op(n));
 366     break;
 367   case iro_Mul:
 368     /* Mul is commutative and has again an other neutral element. */
 369     if (tarval_classify (computed_value (a)) == 1) {
 370       n = b;
 371     } else if (tarval_classify (computed_value (b)) == 1) {
 372       n = a;
 373     }
 374     break;
 375   case iro_Div:
 376     /* Div is not commutative. */
 377     if (tarval_classify (computed_value (b)) == 1) { /* div(x, 1) == x */
 378       /* Turn Div into a tuple (mem, bad, a) */
 379       ir_node *mem = get_Div_mem(n);
 380       turn_into_tuple(n, 3);
 381       set_Tuple_pred(n, 0, mem);
 382       set_Tuple_pred(n, 1, new_Bad());
 383       set_Tuple_pred(n, 2, a);
 384     }
 385     break;
 386     /* GL: Why are they skipped?  DivMod allocates new nodes --> it's
 387        teated in transform node.
 388   case iro_Mod, Quot, DivMod
 389     */
 390   case iro_And:
 391     if (a == b) n = a;
 392     /* And has it's own neutral element */
 393     else if (tarval_classify (computed_value (a)) == -1) {
 394       n = b;
 395     } else if (tarval_classify (computed_value (b)) == -1) {
 396       n = a;
 397     }
 398     break;
 399   case iro_Conv:
 400     if (get_irn_mode(n) == get_irn_mode(a)) { /* No Conv necessary */
 401       n = a;
 402     } else if (get_irn_mode(n) == mode_b) {
 403       if (get_irn_op(a) == op_Conv &&
 404           get_irn_mode (get_Conv_op(a)) == mode_b) {
 405         n = get_Conv_op(a);     /* Convb(Conv*(xxxb(...))) == xxxb(...) */
 406       }
 407     }
 408     break;
 409
 410   case iro_Phi:
 411     {
 412       /* Several optimizations:
 413          - no Phi in start block.
 414          - remove Id operators that are inputs to Phi
 415          - fold Phi-nodes, iff they have only one predecessor except
 416            themselves.
 417       */
 418       int i, n_preds;
 419
 420
 421       ir_node *block = NULL;     /* to shutup gcc */
 422       ir_node *first_val = NULL; /* to shutup gcc */
 423       ir_node *scnd_val = NULL;  /* to shutup gcc */
 424
 425       n_preds = get_Phi_n_preds(n);
 426
 427       block = get_nodes_Block(n);
 428       assert(get_irn_op (block) == op_Block);
 429
 430       /* there should be no Phi nodes in the Start region. */
 431       if (block == current_ir_graph->start_block) {
 432         n = new_Bad();
 433         break;
 434       }
 435
 436       if (n_preds == 0) {       /* Phi of dead Region without predecessors. */
 437         /* GL: why not return new_Bad? */
 438         break;
 439       }
 440
 441 #if 0
 442       /* first we test for a special case: */
 443       /* Confirm is a special node fixing additional information for a
 444          value that is known at a certain point.  This is useful for
 445          dataflow analysis. */
 446       if (n_preds == 2) {
 447         ir_node *a = follow_Id (get_Phi_pred(n, 0));
 448         ir_node *b = follow_Id (get_Phi_pred(n, 1));
 449         if (   (get_irn_op(a) == op_Confirm)
 450             && (get_irn_op(b) == op_Confirm)
 451             && (follow_Id (get_irn_n(a, 0)) == follow_Id(get_irn_n(b, 0)))
 452             && (get_irn_n(a, 1) == get_irn_n (b, 1))
 453             && (a->data.num == (~b->data.num & irpn_True) )) {
 454           n = follow_Id (get_irn_n(a, 0));
 455           break;
 456         }
 457       }
 458 #endif
 459
 460       /* Find first non-self-referencing input */
 461       for (i = 0;  i < n_preds;  ++i) {
 462         first_val = follow_Id(get_Phi_pred(n, i));
 463         /* skip Id's */
 464         set_Phi_pred(n, i, first_val);
 465         if (   (first_val != n)                            /* not self pointer */
 466                && (get_irn_op(first_val) != op_Bad)        /* value not dead */
 467             && !(is_Bad (get_Block_cfgpred(block, i))) ) { /* not dead control flow */
 468           break;                         /* then found first value. */
 469         }
 470       }
 471
 472       /* A totally Bad or self-referencing Phi (we didn't break the above loop) */
 473       if (i >= n_preds) { n = new_Bad();  break; }
 474
 475       scnd_val = NULL;
 476
 477       /* follow_Id () for rest of inputs, determine if any of these
 478          are non-self-referencing */
 479       while (++i < n_preds) {
 480         scnd_val = follow_Id(get_Phi_pred(n, i));
 481         /* skip Id's */
 482         set_Phi_pred(n, i, scnd_val);
 483         if (   (scnd_val != n)
 484             && (scnd_val != first_val)
 485             && (get_irn_op(scnd_val) != op_Bad)
 486             && !(is_Bad (get_Block_cfgpred(block, i))) ) {
 487           break;
 488         }
 489       }
 490
 491       /* Fold, if no multiple distinct non-self-referencing inputs */
 492       if (i >= n_preds) {
 493         n = first_val;
 494       } else {
 495       /* skip the remaining Ids. */
 496         while (++i < n_preds) {
 497           set_Phi_pred(n, i, follow_Id(get_Phi_pred(n, i)));
 498         }
 499       }
 500     }
 501     break;
 502
 503   case iro_Load:
 504     {
 505 #if 0  /* Is an illegal transformation: different nodes can
 506           represent the same pointer value!! */
 507       a = skip_Proj(get_Load_mem(n));
 508       b = get_Load_ptr(n);
 509
 510       if (get_irn_op(a) == op_Store) {
 511         if ( different_identity (b, get_Store_ptr(a))) {
 512           /* load and store use different pointers, therefore load
 513              needs not take store's memory but the state before. */
 514           set_Load_mem (n, get_Store_mem(a));
 515         } else if (( 0 /* ???didn't get cryptic test that returns 0 */ )) {
 516         }
 517       }
 518 #endif
 519     }
 520       break;
 521   case iro_Store:
 522     /* remove unnecessary store. */
 523     {
 524       a = skip_Proj(get_Store_mem(n));
 525       b = get_Store_ptr(n);
 526       c = skip_Proj(get_Store_value(n));
 527
 528       if (get_irn_op(a) == op_Store
 529           && get_Store_ptr(a) == b
 530           && skip_Proj(get_Store_value(a)) == c) {
 531         /* We have twice exactly the same store -- a write after write. */
 532         n = a;
 533       } else if (get_irn_op(c) == op_Load
 534                  && (a == c || skip_Proj(get_Load_mem(c)) == a)
 535                  && get_Load_ptr(c) == b )
 536                  /* !!!??? and a cryptic test */ {
 537         /* We just loaded the value from the same memory, i.e., the store
 538            doesn't change the memory -- a write after read. */
 539         turn_into_tuple(n, 2);
 540         set_Tuple_pred(n, 0, a);
 541         set_Tuple_pred(n, 1, new_Bad());
 542       }
 543     }
 544     break;
 545
 546   case iro_Proj:
 547     {
 548       a = get_Proj_pred(n);
 549
 550       if ( get_irn_op(a) == op_Tuple) {
 551         /* Remove the Tuple/Proj combination. */
 552         if ( get_Proj_proj(n) <= get_Tuple_n_preds(a) ) {
 553           n = get_Tuple_pred(a, get_Proj_proj(n));
 554         } else {
 555           assert(0); /* This should not happen! */
 556           n = new_Bad();
 557         }
 558       } else if (get_irn_mode(n) == mode_X &&
 559                  is_Bad(get_nodes_Block(n))) {
 560         /* Remove dead control flow. */
 561         n = new_Bad();
 562       }
 563     }
 564     break;
 565
 566   case iro_Id:
 567     n = follow_Id (n);
 568     break;
 569
 570   default: break;
 571   }
 572
 573   return n;
 574 } /* end equivalent_node() */
 575
 576
 577 /* tries several [inplace] [optimizing] transformations and returns a
 578    equivalent node.  The difference to equivalent_node is that these
 579    transformations _do_ generate new nodes, and thus the old node must
 580    not be freed even if the equivalent node isn't the old one. */
 581 static ir_node *
 582 transform_node (ir_node *n)
 583 {
 584
 585   ir_node *a = NULL, *b;
 586   tarval *ta, *tb;
 587
 588   switch (get_irn_opcode(n)) {
 589   case iro_DivMod: {
 590
 591     int evaluated = 0;
 592     ir_mode *mode;
 593
 594     a = get_DivMod_left(n);
 595     b = get_DivMod_right(n);
 596     mode = get_irn_mode(a);
 597
 598     if (!(   mode_is_int(get_irn_mode(a))
 599           && mode_is_int(get_irn_mode(b))))
 600       break;
 601
 602     if (a == b) {
 603       a = new_Const (mode, tarval_from_long (mode, 1));
 604       b = new_Const (mode, tarval_from_long (mode, 0));
 605       evaluated = 1;
 606     } else {
 607       ta = value_of(a);
 608       tb = value_of(b);
 609
 610       if (tb) {
 611         if (tarval_classify(tb) == 1) {
 612           b = new_Const (mode, tarval_from_long (mode, 0));
 613           evaluated = 1;
 614         } else if (ta) {
 615           tarval *resa, *resb;
 616           resa = tarval_div (ta, tb);
 617           if (!resa) break; /* Causes exception!!! Model by replacing through
 618                                Jmp for X result!? */
 619           resb = tarval_mod (ta, tb);
 620           if (!resb) break; /* Causes exception! */
 621           a = new_Const (mode, resa);
 622           b = new_Const (mode, resb);
 623           evaluated = 1;
 624         }
 625       } else if (tarval_classify (ta) == 0) {
 626         b = a;
 627         evaluated = 1;
 628       }
 629     }
 630     if (evaluated) { /* replace by tuple */
 631       ir_node *mem = get_DivMod_mem(n);
 632       turn_into_tuple(n, 4);
 633       set_Tuple_pred(n, 0, mem);
 634       set_Tuple_pred(n, 1, new_Bad());  /* no exception */
 635       set_Tuple_pred(n, 2, a);
 636       set_Tuple_pred(n, 3, b);
 637       assert(get_nodes_Block(n));
 638     }
 639   }
 640   break;
 641
 642   case iro_Cond: {
 643     /* Replace the Cond by a Jmp if it branches on a constant
 644        condition. */
 645     ir_node *jmp;
 646     a = get_Cond_selector(n);
 647     ta = value_of(a);
 648
 649     if (ta && (get_irn_mode(a) == mode_b)) {
 650       /* It's a boolean Cond, branching on a boolean constant.
 651          Replace it by a tuple (Bad, Jmp) or (Jmp, Bad) */
 652       jmp = new_r_Jmp(current_ir_graph, get_nodes_Block(n));
 653       turn_into_tuple(n, 2);
 654       if (tv_val_b(ta) == 1)  /* GL: I hope this returns 1 if true */ {
 655         set_Tuple_pred(n, 0, new_Bad());
 656         set_Tuple_pred(n, 1, jmp);
 657       } else {
 658         set_Tuple_pred(n, 0, jmp);
 659         set_Tuple_pred(n, 1, new_Bad());
 660       }
 661     } else if (ta && (get_irn_mode(a) == mode_I) && (get_Cond_kind(n) == dense)) {
 662       /* I don't want to allow Tuples smaller than the biggest Proj.
 663          Also this tuple might get really big...
 664          I generate the Jmp here, and remember it in link.  Link is used
 665          when optimizing Proj. */
 666       set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 667     } else if (   (get_irn_op(get_Cond_selector(n)) == op_Eor)
 668                && (get_irn_mode(get_Cond_selector(n)) == mode_b)
 669                && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
 670       /* The Eor is a negate.  Generate a new Cond without the negate,
 671          simulate the negate by exchanging the results. */
 672       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 673                                  get_Eor_left(a)));
 674     } else if (   (get_irn_op(get_Cond_selector(n)) == op_Not)
 675                && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
 676       /* A Not before the Cond.  Generate a new Cond without the Not,
 677          simulate the Not by exchanging the results. */
 678       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 679                                  get_Not_op(a)));
 680     }
 681   }
 682   break;
 683
 684   case iro_Proj: {
 685     a = get_Proj_pred(n);
 686
 687     if (  (get_irn_op(a) == op_Cond)
 688         && get_irn_link(a)
 689         && get_irn_op(get_irn_link(a)) == op_Cond) {
 690     /* Use the better Cond if the Proj projs from a Cond which get's
 691        its result from an Eor/Not. */
 692       assert (   (   (get_irn_op(get_Cond_selector(a)) == op_Eor)
 693                      || (get_irn_op(get_Cond_selector(a)) == op_Not))
 694               && (get_irn_mode(get_Cond_selector(a)) == mode_b)
 695               && (get_irn_op(get_irn_link(a)) == op_Cond)
 696               && (get_Cond_selector(get_irn_link(a)) ==
 697                   get_Eor_left(get_Cond_selector(a))));
 698       set_Proj_pred(n, get_irn_link(a));
 699       if (get_Proj_proj(n) == 0)
 700         set_Proj_proj(n, 1);
 701       else
 702         set_Proj_proj(n, 0);
 703     } else if (   (get_irn_op(a) == op_Cond)
 704                && (get_irn_mode(get_Cond_selector(a)) == mode_I)
 705                && value_of(a)
 706                && (get_Cond_kind(a) == dense)) {
 707       /* The Cond is a Switch on a Constant */
 708       if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
 709         /* The always taken branch, reuse the existing Jmp. */
 710         if (!get_irn_link(a)) /* well, if it exists ;-> */
 711           set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 712         assert(get_irn_op(get_irn_link(a)) == op_Jmp);
 713         n = get_irn_link(a);
 714       } else {/* Not taken control flow, but be careful with the default! */
 715         if (get_Proj_proj(n) < a->attr.c.default_proj){
 716         /* a never taken branch */
 717           n = new_Bad();
 718         } else {
 719           a->attr.c.default_proj = get_Proj_proj(n);
 720         }
 721       }
 722     }
 723   } break;
 724   case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
 725     a = get_Eor_left(n);
 726     b = get_Eor_right(n);
 727
 728     if (   (get_irn_mode(n) == mode_b)
 729         && (get_irn_op(a) == op_Proj)
 730         && (get_irn_mode(a) == mode_b)
 731         && (tarval_classify (computed_value (b)) == 1)
 732         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 733       /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
 734       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 735                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 736     else if (   (get_irn_mode(n) == mode_b)
 737              && (tarval_classify (computed_value (b)) == 1))
 738       /* The Eor is a Not. Replace it by a Not. */
 739       /*   ????!!!Extend to bitfield 1111111. */
 740       n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
 741   }
 742   break;
 743   case iro_Not: {
 744     a = get_Not_op(n);
 745
 746     if (   (get_irn_mode(n) == mode_b)
 747         && (get_irn_op(a) == op_Proj)
 748         && (get_irn_mode(a) == mode_b)
 749         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 750       /* We negate a Cmp. The Cmp has the negated result anyways! */
 751       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 752                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 753   }
 754   break;
 755   default: ;
 756   }
 757   return n;
 758 }
 759
 760 /* **************** Common Subexpression Elimination **************** */
 761
 762 /* Compare function for two nodes in the hash table.   Gets two     */
 763 /* nodes as parameters.                                             */
 764 /* @@@  a+b != b+a ? */
 765 static int
 766 vt_cmp (const void *elt, const void *key)
 767 {
 768   ir_node *a, *b;
 769   int i;
 770
 771   a = (void *)elt;
 772   b = (void *)key;
 773
 774   if (a == b) return 0;
 775
 776   if ((get_irn_op(a) != get_irn_op(b)) ||
 777       (get_irn_mode(a) != get_irn_mode(b))) return 1;
 778
 779   /* compare if a's in and b's in are equal */
 780   /* GL: we optimize only nodes with in arrays of fixed sizes.
 781   if (get_irn_arity (a) != -2) {
 782     ins = get_irn_arity (a);
 783     if (ins != get_irn_arity (b)) return 1;
 784     ain = get_irn_in (a);
 785     bin = get_irn_in (b);
 786   }
 787   */
 788   if (get_irn_arity (a) != get_irn_arity(b))
 789     return 1;
 790
 791   /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
 792   /* do if (*ain++ != *bin++) return 1; while (ins--); */
 793   for (i = -1; i < get_irn_arity(a); i++)
 794     if (get_irn_n(a, i) != get_irn_n(b, i))
 795       return 1;
 796
 797
 798   switch (get_irn_opcode(a)) {
 799   case iro_Const:
 800     return get_irn_const_attr (a) != get_irn_const_attr (b);
 801   case iro_Proj:
 802     return get_irn_proj_attr (a) != get_irn_proj_attr (b);
 803   case iro_Alloc:
 804     return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
 805       || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
 806   case iro_Free:
 807     return (get_irn_free_attr(a) != get_irn_free_attr(b));
 808   case iro_SymConst:
 809     return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
 810       || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
 811   case iro_Call:
 812     return (get_irn_call_attr(a) != get_irn_call_attr(b));
 813   case iro_Sel:
 814     return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
 815       || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
 816       || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
 817       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
 818       || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
 819       || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
 820   case iro_Phi:
 821     return get_irn_phi_attr (a) != get_irn_phi_attr (b);
 822   default: ;
 823   }
 824
 825   return 0;
 826 }
 827
 828 static unsigned
 829 ir_node_hash (ir_node *node)
 830 {
 831   unsigned h;
 832   int i;
 833
 834   /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
 835   h = get_irn_arity(node);
 836
 837   /* consider all in nodes... except the block. */
 838   for (i = 0;  i < get_irn_arity(node);  i++) {
 839     h = 9*h + (unsigned long)get_irn_n(node, i);
 840   }
 841
 842   /* ...mode,... */
 843   h = 9*h + (unsigned long) get_irn_mode (node);
 844   /* ...and code */
 845   h = 9*h + (unsigned long) get_irn_op (node);
 846
 847   return h;
 848 }
 849
 850 pset *
 851 new_identities (void)
 852 {
 853   return new_pset (vt_cmp, TUNE_NIR_NODES);
 854 }
 855
 856 void
 857 del_identities (pset *value_table)
 858 {
 859   del_pset (value_table);
 860 }
 861
 862 /* Return the canonical node computing the same value as n.
 863    Looks up the node in a hash table. */
 864 static inline ir_node *
 865 identify (pset *value_table, ir_node *n)
 866 {
 867   ir_node *o = NULL;
 868
 869   if (!value_table) return n;
 870
 871   switch (get_irn_opcode (n)) {
 872   case iro_Add:
 873   case iro_Mul:
 874   case iro_Or:
 875   case iro_And:
 876   case iro_Eor:
 877     {
 878       /* for commutative operators perform  a OP b == b OP a */
 879       if (get_binop_left(n) > get_binop_right(n)) {
 880         ir_node *h = get_binop_left(n);
 881         set_binop_left(n, get_binop_right(n));
 882         set_binop_right(n, h);
 883       }
 884     }
 885   break;
 886   default: break;
 887   }
 888   o = pset_find (value_table, n, ir_node_hash (n));
 889   if (!o) return n;
 890
 891   return o;
 892 }
 893
 894 /* Return the canonical node computing the same value as n.
 895    Looks up the node in a hash table, enters it in the table
 896    if it isn't there yet. */
 897 static ir_node *
 898 identify_remember (pset *value_table, ir_node *node)
 899 {
 900   ir_node *o = NULL;
 901
 902   if (!value_table) return node;
 903
 904   /* lookup or insert in hash table with given hash key. */
 905   o = pset_insert (value_table, node, ir_node_hash (node));
 906
 907   if (o == node) return node;
 908
 909   return o;
 910 }
 911
 912 void
 913 add_identities (pset *value_table, ir_node *node) {
 914   identify_remember (value_table, node);
 915 }
 916
 917 /* garbage in, garbage out. If a node has a dead input, i.e., the
 918    Bad node is input to the node, return the Bad node.  */
 919 static inline ir_node *
 920 gigo (ir_node *node)
 921 {
 922   int i;
 923   ir_op* op = get_irn_op(node);
 924
 925   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
 926      blocks predecessors is dead. */
 927   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
 928     for (i = -1; i < get_irn_arity(node); i++) {
 929       if (is_Bad(get_irn_n(node, i))) {
 930         return new_Bad();
 931       }
 932     }
 933   }
 934 #if 0
 935   /* If Block has only Bads as predecessors it's garbage. */
 936   /* If Phi has only Bads as predecessors it's garbage. */
 937   if (op == op_Block || op == op_Phi)  {
 938     for (i = 0; i < get_irn_arity(node); i++) {
 939       if (!is_Bad(get_irn_n(node, i))) break;
 940     }
 941     if (i = get_irn_arity(node)) node = new_Bad();
 942   }
 943 #endif
 944   return node;
 945 }
 946
 947
 948 /* These optimizations deallocate nodes from the obstack.
 949    It can only be called if it is guaranteed that no other nodes
 950    reference this one, i.e., right after construction of a node.  */
 951 ir_node *
 952 optimize (ir_node *n)
 953 {
 954   tarval *tv;
 955   ir_node *old_n = n;
 956
 957   /* Allways optimize Phi nodes: part of the construction. */
 958   if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
 959
 960   /* if not optimize return n */
 961   if (n == NULL) {
 962     printf(" attention: empty node!!! \n");
 963     return n;
 964   }
 965
 966   /* constant expression evaluation / constant folding */
 967   if (get_opt_constant_folding()) {
 968     /* constants can not be evaluated */
 969     if  (get_irn_op(n) != op_Const) {
 970       /* try to evaluate */
 971       tv = computed_value (n);
 972       if (tv != NULL) {
 973         /* evaluation was succesful -- replace the node. */
 974         obstack_free (current_ir_graph->obst, n);
 975         return new_Const (get_tv_mode (tv), tv);
 976       }
 977     }
 978   }
 979
 980   /* remove unnecessary nodes */
 981   if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
 982     n = equivalent_node (n);
 983
 984   /** common subexpression elimination **/
 985   /* Checks whether n is already available. */
 986   /* The block input is used to distinguish different subexpressions. Right
 987      now all nodes are pinned to blocks, i.e., the cse only finds common
 988      subexpressions within a block. */
 989   if (get_opt_cse())
 990     n = identify (current_ir_graph->value_table, n);
 991   /* identify found a cse, so deallocate the old node. */
 992   if (n != old_n) {
 993     obstack_free (current_ir_graph->obst, old_n);
 994     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
 995   }
 996
 997   /* Some more constant expression evaluation that does not allow to
 998      free the node. */
 999   if (get_opt_constant_folding())
1000     n = transform_node (n);
1001
1002   /* Remove nodes with dead (Bad) input. */
1003   if (get_opt_unreachable_code())
1004     n = gigo (n);
1005   /* Now we can verify the node, as it has no dead inputs any more. */
1006   irn_vrfy(n);
1007
1008   /* Now we have a legal, useful node. Enter it in hash table for cse */
1009   if (get_opt_cse()) {
1010     n = identify_remember (current_ir_graph->value_table, n);
1011   }
1012
1013 #if 0  /* GL: what's the use of this?? */
1014   if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
1015     assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
1016     pdeq_putr (current_ir_graph->keep.living, n);
1017   }
1018 #endif
1019   return n;
1020 }
1021
1022
1023 /* These optimizations never deallocate nodes.  This can cause dead
1024    nodes lying on the obstack.  Remove these by a dead node elimination,
1025    i.e., a copying garbage collection. */
1026 ir_node *
1027 optimize_in_place (ir_node *n)
1028 {
1029   tarval *tv;
1030   ir_node *old_n = n;
1031
1032   if (!get_optimize()) return n;
1033
1034   /* if not optimize return n */
1035   if (n == NULL) {
1036     /* Here this is possible.  Why? */
1037     return n;
1038   }
1039
1040   /* constant expression evaluation / constant folding */
1041   if (get_opt_constant_folding()) {
1042     /* constants can not be evaluated */
1043     if  (get_irn_op(n) != op_Const) {
1044       /* try to evaluate */
1045       tv = computed_value (n);
1046       if (tv != NULL) {
1047         /* evaluation was succesful -- replace the node. */
1048         n = new_Const (get_tv_mode (tv), tv);
1049         deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1050         return n;
1051         /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1052       }
1053     }
1054   }
1055
1056   /* remove unnecessary nodes */
1057   /*if (get_opt_constant_folding()) */
1058   if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1059     n = equivalent_node (n);
1060
1061   /** common subexpression elimination **/
1062   /* Checks whether n is already available. */
1063   /* The block input is used to distinguish different subexpressions.  Right
1064      now all nodes are pinned to blocks, i.e., the cse only finds common
1065      subexpressions within a block. */
1066   if (get_opt_cse())
1067     n = identify (current_ir_graph->value_table, n);
1068
1069   /* identify found a cse, so deallocate the old node. */
1070   if (n != old_n) {
1071     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
1072   }
1073
1074   /* Some more constant expression evaluation. */
1075   if (get_opt_constant_folding())
1076     n = transform_node (n);
1077
1078   /* Remove nodes with dead (Bad) input. */
1079   if (get_opt_unreachable_code())
1080     n = gigo (n);
1081   /* Now we can verify the node, as it has no dead inputs any more. */
1082   irn_vrfy(n);
1083
1084   /* Now we have a legal, useful node. Enter it in hash table for cse.
1085      Blocks should be unique anyways.  (Except the successor of start:
1086      is cse with the start block!) */
1087   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1088     n = identify_remember (current_ir_graph->value_table, n);
1089
1090   return n;
1091 }