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