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       /* We might generate an endless loop, so keep it alive. */
 664       add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
 665     } else if (ta && (get_irn_mode(a) == mode_I) && (get_Cond_kind(n) == dense)) {
 666       /* I don't want to allow Tuples smaller than the biggest Proj.
 667          Also this tuple might get really big...
 668          I generate the Jmp here, and remember it in link.  Link is used
 669          when optimizing Proj. */
 670       set_irn_link(n, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 671       /* We might generate an endless loop, so keep it alive. */
 672       add_End_keepalive(get_irg_end(current_ir_graph), get_nodes_Block(n));
 673     } else if (   (get_irn_op(get_Cond_selector(n)) == op_Eor)
 674                && (get_irn_mode(get_Cond_selector(n)) == mode_b)
 675                && (tarval_classify(computed_value(get_Eor_right(a))) == 1)) {
 676       /* The Eor is a negate.  Generate a new Cond without the negate,
 677          simulate the negate by exchanging the results. */
 678       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 679                                  get_Eor_left(a)));
 680     } else if (   (get_irn_op(get_Cond_selector(n)) == op_Not)
 681                && (get_irn_mode(get_Cond_selector(n)) == mode_b)) {
 682       /* A Not before the Cond.  Generate a new Cond without the Not,
 683          simulate the Not by exchanging the results. */
 684       set_irn_link(n, new_r_Cond(current_ir_graph, get_nodes_Block(n),
 685                                  get_Not_op(a)));
 686     }
 687   }
 688   break;
 689
 690   case iro_Proj: {
 691     a = get_Proj_pred(n);
 692
 693     if (  (get_irn_op(a) == op_Cond)
 694         && get_irn_link(a)
 695         && get_irn_op(get_irn_link(a)) == op_Cond) {
 696     /* Use the better Cond if the Proj projs from a Cond which get's
 697        its result from an Eor/Not. */
 698       assert (   (   (get_irn_op(get_Cond_selector(a)) == op_Eor)
 699                      || (get_irn_op(get_Cond_selector(a)) == op_Not))
 700               && (get_irn_mode(get_Cond_selector(a)) == mode_b)
 701               && (get_irn_op(get_irn_link(a)) == op_Cond)
 702               && (get_Cond_selector(get_irn_link(a)) ==
 703                   get_Eor_left(get_Cond_selector(a))));
 704       set_Proj_pred(n, get_irn_link(a));
 705       if (get_Proj_proj(n) == 0)
 706         set_Proj_proj(n, 1);
 707       else
 708         set_Proj_proj(n, 0);
 709     } else if (   (get_irn_op(a) == op_Cond)
 710                && (get_irn_mode(get_Cond_selector(a)) == mode_I)
 711                && value_of(a)
 712                && (get_Cond_kind(a) == dense)) {
 713       /* The Cond is a Switch on a Constant */
 714       if (get_Proj_proj(n) == tv_val_CHIL(value_of(a))) {
 715         /* The always taken branch, reuse the existing Jmp. */
 716         if (!get_irn_link(a)) /* well, if it exists ;-> */
 717           set_irn_link(a, new_r_Jmp(current_ir_graph, get_nodes_Block(n)));
 718         assert(get_irn_op(get_irn_link(a)) == op_Jmp);
 719         n = get_irn_link(a);
 720       } else {/* Not taken control flow, but be careful with the default! */
 721         if (get_Proj_proj(n) < a->attr.c.default_proj){
 722         /* a never taken branch */
 723           n = new_Bad();
 724         } else {
 725           a->attr.c.default_proj = get_Proj_proj(n);
 726         }
 727       }
 728     }
 729   } break;
 730   case iro_Eor: { /* @@@ not tested as boolean Eor not allowed any more. */
 731     a = get_Eor_left(n);
 732     b = get_Eor_right(n);
 733
 734     if (   (get_irn_mode(n) == mode_b)
 735         && (get_irn_op(a) == op_Proj)
 736         && (get_irn_mode(a) == mode_b)
 737         && (tarval_classify (computed_value (b)) == 1)
 738         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 739       /* The Eor negates a Cmp. The Cmp has the negated result anyways! */
 740       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 741                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 742     else if (   (get_irn_mode(n) == mode_b)
 743              && (tarval_classify (computed_value (b)) == 1))
 744       /* The Eor is a Not. Replace it by a Not. */
 745       /*   ????!!!Extend to bitfield 1111111. */
 746       n = new_r_Not(current_ir_graph, get_nodes_Block(n), a, mode_b);
 747   }
 748   break;
 749   case iro_Not: {
 750     a = get_Not_op(n);
 751
 752     if (   (get_irn_mode(n) == mode_b)
 753         && (get_irn_op(a) == op_Proj)
 754         && (get_irn_mode(a) == mode_b)
 755         && (get_irn_op(get_Proj_pred(a)) == op_Cmp))
 756       /* We negate a Cmp. The Cmp has the negated result anyways! */
 757       n = new_r_Proj(current_ir_graph, get_nodes_Block(n), get_Proj_pred(a),
 758                      mode_b, get_negated_pnc(get_Proj_proj(a)));
 759   }
 760   break;
 761   default: ;
 762   }
 763   return n;
 764 }
 765
 766 /* **************** Common Subexpression Elimination **************** */
 767
 768 /* Compare function for two nodes in the hash table.   Gets two       */
 769 /* nodes as parameters.  Returns 0 if the nodes are a cse.            */
 770 static int
 771 vt_cmp (const void *elt, const void *key)
 772 {
 773   ir_node *a, *b;
 774   int i;
 775
 776   a = (void *)elt;
 777   b = (void *)key;
 778
 779   if (a == b) return 0;
 780
 781   if ((get_irn_op(a) != get_irn_op(b)) ||
 782       (get_irn_mode(a) != get_irn_mode(b))) return 1;
 783
 784   /* compare if a's in and b's in are equal */
 785   /* GL: we optimize only nodes with in arrays of fixed sizes.
 786   if (get_irn_arity (a) != -2) {
 787     ins = get_irn_arity (a);
 788     if (ins != get_irn_arity (b)) return 1;
 789     ain = get_irn_in (a);
 790     bin = get_irn_in (b);
 791   }
 792   */
 793   if (get_irn_arity (a) != get_irn_arity(b))
 794     return 1;
 795
 796   /* for block-local cse and pinned nodes: */
 797   if (!get_opt_global_cse() || (get_op_pinned(get_irn_op(a)) == pinned)) {
 798     if (get_irn_n(a, -1) != get_irn_n(b, -1))
 799       return 1;
 800   }
 801
 802   /* compare a->in[0..ins] with b->in[0..ins] */
 803   for (i = 0; i < get_irn_arity(a); i++)
 804     if (get_irn_n(a, i) != get_irn_n(b, i))
 805       return 1;
 806
 807   switch (get_irn_opcode(a)) {
 808   case iro_Const:
 809     return get_irn_const_attr (a) != get_irn_const_attr (b);
 810   case iro_Proj:
 811     return get_irn_proj_attr (a) != get_irn_proj_attr (b);
 812   case iro_Alloc:
 813     return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
 814       || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
 815   case iro_Free:
 816     return (get_irn_free_attr(a) != get_irn_free_attr(b));
 817   case iro_SymConst:
 818     return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
 819       || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
 820   case iro_Call:
 821     return (get_irn_call_attr(a) != get_irn_call_attr(b));
 822   case iro_Sel:
 823     return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
 824       || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
 825       || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
 826       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
 827       || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
 828       || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
 829   case iro_Phi:
 830     return get_irn_phi_attr (a) != get_irn_phi_attr (b);
 831   default: ;
 832   }
 833
 834   return 0;
 835 }
 836
 837 static unsigned
 838 ir_node_hash (ir_node *node)
 839 {
 840   unsigned h;
 841   int i;
 842
 843   /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
 844   h = get_irn_arity(node);
 845
 846   /* consider all in nodes... except the block. */
 847   for (i = 0;  i < get_irn_arity(node);  i++) {
 848     h = 9*h + (unsigned long)get_irn_n(node, i);
 849   }
 850
 851   /* ...mode,... */
 852   h = 9*h + (unsigned long) get_irn_mode (node);
 853   /* ...and code */
 854   h = 9*h + (unsigned long) get_irn_op (node);
 855
 856   return h;
 857 }
 858
 859 pset *
 860 new_identities (void)
 861 {
 862   return new_pset (vt_cmp, TUNE_NIR_NODES);
 863 }
 864
 865 void
 866 del_identities (pset *value_table)
 867 {
 868   del_pset (value_table);
 869 }
 870
 871 /* Return the canonical node computing the same value as n.
 872    Looks up the node in a hash table. */
 873 static inline ir_node *
 874 identify (pset *value_table, ir_node *n)
 875 {
 876   ir_node *o = NULL;
 877
 878   if (!value_table) return n;
 879
 880   if (get_opt_reassociation()) {
 881     switch (get_irn_opcode (n)) {
 882     case iro_Add:
 883     case iro_Mul:
 884     case iro_Or:
 885     case iro_And:
 886     case iro_Eor:
 887       {
 888         /* for commutative operators perform  a OP b == b OP a */
 889         if (get_binop_left(n) > get_binop_right(n)) {
 890           ir_node *h = get_binop_left(n);
 891           set_binop_left(n, get_binop_right(n));
 892           set_binop_right(n, h);
 893         }
 894       }
 895       break;
 896     default: break;
 897     }
 898   }
 899
 900   o = pset_find (value_table, n, ir_node_hash (n));
 901   if (!o) return n;
 902
 903   return o;
 904 }
 905
 906 /* During construction we set the pinned flag in the graph right when the
 907    optimizatin is performed.  The flag turning on procedure global cse could
 908    be changed between two allocations.  This way we are safe. */
 909 static inline ir_node *
 910 identify_cons (pset *value_table, ir_node *n) {
 911   ir_node *old = n;
 912   n = identify(value_table, n);
 913   if (get_irn_n(old, -1) != get_irn_n(n, -1))
 914     set_irg_pinned(current_ir_graph, floats);
 915   return n;
 916 }
 917
 918 /* Return the canonical node computing the same value as n.
 919    Looks up the node in a hash table, enters it in the table
 920    if it isn't there yet. */
 921 static ir_node *
 922 identify_remember (pset *value_table, ir_node *node)
 923 {
 924   ir_node *o = NULL;
 925
 926   if (!value_table) return node;
 927
 928   /* lookup or insert in hash table with given hash key. */
 929   o = pset_insert (value_table, node, ir_node_hash (node));
 930
 931   if (o == node) return node;
 932
 933   return o;
 934 }
 935
 936 void
 937 add_identities (pset *value_table, ir_node *node) {
 938   identify_remember (value_table, node);
 939 }
 940
 941 /* garbage in, garbage out. If a node has a dead input, i.e., the
 942    Bad node is input to the node, return the Bad node.  */
 943 static inline ir_node *
 944 gigo (ir_node *node)
 945 {
 946   int i;
 947   ir_op* op = get_irn_op(node);
 948
 949   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
 950      blocks predecessors is dead. */
 951   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
 952     for (i = -1; i < get_irn_arity(node); i++) {
 953       if (is_Bad(get_irn_n(node, i))) {
 954         return new_Bad();
 955       }
 956     }
 957   }
 958 #if 0
 959   /* If Block has only Bads as predecessors it's garbage. */
 960   /* If Phi has only Bads as predecessors it's garbage. */
 961   if (op == op_Block || op == op_Phi)  {
 962     for (i = 0; i < get_irn_arity(node); i++) {
 963       if (!is_Bad(get_irn_n(node, i))) break;
 964     }
 965     if (i = get_irn_arity(node)) node = new_Bad();
 966   }
 967 #endif
 968   return node;
 969 }
 970
 971
 972 /* These optimizations deallocate nodes from the obstack.
 973    It can only be called if it is guaranteed that no other nodes
 974    reference this one, i.e., right after construction of a node.  */
 975 ir_node *
 976 optimize (ir_node *n)
 977 {
 978   tarval *tv;
 979   ir_node *old_n = n;
 980
 981   /* Allways optimize Phi nodes: part of the construction. */
 982   if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
 983
 984   /* constant expression evaluation / constant folding */
 985   if (get_opt_constant_folding()) {
 986     /* constants can not be evaluated */
 987     if  (get_irn_op(n) != op_Const) {
 988       /* try to evaluate */
 989       tv = computed_value (n);
 990       if (tv != NULL) {
 991         /* evaluation was succesful -- replace the node. */
 992         obstack_free (current_ir_graph->obst, n);
 993         return new_Const (get_tv_mode (tv), tv);
 994       }
 995     }
 996   }
 997
 998   /* remove unnecessary nodes */
 999   if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1000     n = equivalent_node (n);
1001
1002   /** common subexpression elimination **/
1003   /* Checks whether n is already available. */
1004   /* The block input is used to distinguish different subexpressions. Right
1005      now all nodes are pinned to blocks, i.e., the cse only finds common
1006      subexpressions within a block. */
1007   if (get_opt_cse())
1008     n = identify_cons (current_ir_graph->value_table, n);
1009   /* identify found a cse, so deallocate the old node. */
1010   if (n != old_n) {
1011     obstack_free (current_ir_graph->obst, old_n);
1012     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
1013   }
1014
1015   /* Some more constant expression evaluation that does not allow to
1016      free the node. */
1017   if (get_opt_constant_folding())
1018     n = transform_node (n);
1019
1020   /* Remove nodes with dead (Bad) input. */
1021   if (get_opt_unreachable_code())
1022     n = gigo (n);
1023   /* Now we can verify the node, as it has no dead inputs any more. */
1024   irn_vrfy(n);
1025
1026   /* Now we have a legal, useful node. Enter it in hash table for cse */
1027   if (get_opt_cse()) {
1028     n = identify_remember (current_ir_graph->value_table, n);
1029   }
1030
1031 #if 0  /* GL: what's the use of this?? */
1032   if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
1033     assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
1034     pdeq_putr (current_ir_graph->keep.living, n);
1035   }
1036 #endif
1037   return n;
1038 }
1039
1040
1041 /* These optimizations never deallocate nodes.  This can cause dead
1042    nodes lying on the obstack.  Remove these by a dead node elimination,
1043    i.e., a copying garbage collection. */
1044 ir_node *
1045 optimize_in_place_2 (ir_node *n)
1046 {
1047   tarval *tv;
1048   ir_node *old_n = n;
1049
1050   if (!get_optimize()) return n;
1051
1052   /* if not optimize return n */
1053   if (n == NULL) {
1054     /* Here this is possible.  Why? */
1055     return n;
1056   }
1057
1058   /* constant expression evaluation / constant folding */
1059   if (get_opt_constant_folding()) {
1060     /* constants can not be evaluated */
1061     if  (get_irn_op(n) != op_Const) {
1062       /* try to evaluate */
1063       tv = computed_value (n);
1064       if (tv != NULL) {
1065         /* evaluation was succesful -- replace the node. */
1066         n = new_Const (get_tv_mode (tv), tv);
1067         deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1068         return n;
1069         /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1070       }
1071     }
1072   }
1073
1074   /* remove unnecessary nodes */
1075   /*if (get_opt_constant_folding()) */
1076   if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1077     n = equivalent_node (n);
1078
1079   /** common subexpression elimination **/
1080   /* Checks whether n is already available. */
1081   /* The block input is used to distinguish different subexpressions.  Right
1082      now all nodes are pinned to blocks, i.e., the cse only finds common
1083      subexpressions within a block. */
1084   if (get_opt_cse()) {
1085     n = identify (current_ir_graph->value_table, n);
1086   }
1087
1088   /* identify found a cse, so deallocate the old node. */
1089   if (n != old_n) {
1090     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
1091   }
1092
1093   /* Some more constant expression evaluation. */
1094   if (get_opt_constant_folding())
1095     n = transform_node (n);
1096
1097   /* Remove nodes with dead (Bad) input. */
1098   if (get_opt_unreachable_code())
1099     n = gigo (n);
1100   /* Now we can verify the node, as it has no dead inputs any more. */
1101   irn_vrfy(n);
1102
1103   /* Now we have a legal, useful node. Enter it in hash table for cse.
1104      Blocks should be unique anyways.  (Except the successor of start:
1105      is cse with the start block!) */
1106   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1107     n = identify_remember (current_ir_graph->value_table, n);
1108
1109   return n;
1110 }
1111
1112 /* Wrapper for external use, set proper status bits after optimization */
1113 ir_node *
1114 optimize_in_place (ir_node *n) {
1115   /* Handle graph state */
1116   assert(get_irg_phase_state(current_ir_graph) != phase_building);
1117   if (get_opt_global_cse())
1118     set_irg_pinned(current_ir_graph, floats);
1119   if (get_irg_outs_state(current_ir_graph) == outs_consistent)
1120     set_irg_outs_inconsistent(current_ir_graph);
1121   return optimize_in_place_2 (n);
1122 }