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.                                             */
 770 /* @@@  a+b != b+a ? */
 771 static int
 772 vt_cmp (const void *elt, const void *key)
 773 {
 774   ir_node *a, *b;
 775   int i;
 776
 777   a = (void *)elt;
 778   b = (void *)key;
 779
 780   if (a == b) return 0;
 781
 782   if ((get_irn_op(a) != get_irn_op(b)) ||
 783       (get_irn_mode(a) != get_irn_mode(b))) return 1;
 784
 785   /* compare if a's in and b's in are equal */
 786   /* GL: we optimize only nodes with in arrays of fixed sizes.
 787   if (get_irn_arity (a) != -2) {
 788     ins = get_irn_arity (a);
 789     if (ins != get_irn_arity (b)) return 1;
 790     ain = get_irn_in (a);
 791     bin = get_irn_in (b);
 792   }
 793   */
 794   if (get_irn_arity (a) != get_irn_arity(b))
 795     return 1;
 796
 797   /* compare a->in[0..ins] with b->in[0..ins], i.e., include the block. */
 798   /* do if (*ain++ != *bin++) return 1; while (ins--); */
 799   for (i = -1; i < get_irn_arity(a); i++)
 800     if (get_irn_n(a, i) != get_irn_n(b, i))
 801       return 1;
 802
 803
 804   switch (get_irn_opcode(a)) {
 805   case iro_Const:
 806     return get_irn_const_attr (a) != get_irn_const_attr (b);
 807   case iro_Proj:
 808     return get_irn_proj_attr (a) != get_irn_proj_attr (b);
 809   case iro_Alloc:
 810     return (get_irn_alloc_attr(a).where != get_irn_alloc_attr(b).where)
 811       || (get_irn_alloc_attr(a).type != get_irn_alloc_attr(b).type);
 812   case iro_Free:
 813     return (get_irn_free_attr(a) != get_irn_free_attr(b));
 814   case iro_SymConst:
 815     return (get_irn_symconst_attr(a).num != get_irn_symconst_attr(b).num)
 816       || (get_irn_symconst_attr(a).tori.typ != get_irn_symconst_attr(b).tori.typ);
 817   case iro_Call:
 818     return (get_irn_call_attr(a) != get_irn_call_attr(b));
 819   case iro_Sel:
 820     return (get_irn_sel_attr(a).ent->kind != get_irn_sel_attr(b).ent->kind)
 821       || (get_irn_sel_attr(a).ent->name != get_irn_sel_attr(b).ent->name)
 822       || (get_irn_sel_attr(a).ent->owner != get_irn_sel_attr(b).ent->owner)
 823       || (get_irn_sel_attr(a).ent->ld_name != get_irn_sel_attr(b).ent->ld_name)
 824       || (get_irn_sel_attr(a).ent->type != get_irn_sel_attr(b).ent->type)
 825       || (get_irn_sel_attr(a).ltyp != get_irn_sel_attr(b).ltyp);
 826   case iro_Phi:
 827     return get_irn_phi_attr (a) != get_irn_phi_attr (b);
 828   default: ;
 829   }
 830
 831   return 0;
 832 }
 833
 834 static unsigned
 835 ir_node_hash (ir_node *node)
 836 {
 837   unsigned h;
 838   int i;
 839
 840   /* hash table value = 9*(9*(9*(9*(9*arity+in[0])+in[1])+ ...)+mode)+code */
 841   h = get_irn_arity(node);
 842
 843   /* consider all in nodes... except the block. */
 844   for (i = 0;  i < get_irn_arity(node);  i++) {
 845     h = 9*h + (unsigned long)get_irn_n(node, i);
 846   }
 847
 848   /* ...mode,... */
 849   h = 9*h + (unsigned long) get_irn_mode (node);
 850   /* ...and code */
 851   h = 9*h + (unsigned long) get_irn_op (node);
 852
 853   return h;
 854 }
 855
 856 pset *
 857 new_identities (void)
 858 {
 859   return new_pset (vt_cmp, TUNE_NIR_NODES);
 860 }
 861
 862 void
 863 del_identities (pset *value_table)
 864 {
 865   del_pset (value_table);
 866 }
 867
 868 /* Return the canonical node computing the same value as n.
 869    Looks up the node in a hash table. */
 870 static inline ir_node *
 871 identify (pset *value_table, ir_node *n)
 872 {
 873   ir_node *o = NULL;
 874
 875
 876
 877   if (!value_table) return n;
 878
 879   switch (get_irn_opcode (n)) {
 880   case iro_Add:
 881   case iro_Mul:
 882   case iro_Or:
 883   case iro_And:
 884   case iro_Eor:
 885     {
 886       /* for commutative operators perform  a OP b == b OP a */
 887       if (get_binop_left(n) > get_binop_right(n)) {
 888         ir_node *h = get_binop_left(n);
 889         set_binop_left(n, get_binop_right(n));
 890         set_binop_right(n, h);
 891       }
 892     }
 893   break;
 894   default: break;
 895   }
 896   o = pset_find (value_table, n, ir_node_hash (n));
 897   if (!o) return n;
 898
 899   return o;
 900 }
 901
 902 /* Return the canonical node computing the same value as n.
 903    Looks up the node in a hash table, enters it in the table
 904    if it isn't there yet. */
 905 static ir_node *
 906 identify_remember (pset *value_table, ir_node *node)
 907 {
 908   ir_node *o = NULL;
 909
 910   if (!value_table) return node;
 911
 912   /* lookup or insert in hash table with given hash key. */
 913   o = pset_insert (value_table, node, ir_node_hash (node));
 914
 915   if (o == node) return node;
 916
 917   return o;
 918 }
 919
 920 void
 921 add_identities (pset *value_table, ir_node *node) {
 922   identify_remember (value_table, node);
 923 }
 924
 925 /* garbage in, garbage out. If a node has a dead input, i.e., the
 926    Bad node is input to the node, return the Bad node.  */
 927 static inline ir_node *
 928 gigo (ir_node *node)
 929 {
 930   int i;
 931   ir_op* op = get_irn_op(node);
 932
 933   /* Blocks, Phis and Tuples may have dead inputs, e.g., if one of the
 934      blocks predecessors is dead. */
 935   if ( op != op_Block && op != op_Phi && op != op_Tuple) {
 936     for (i = -1; i < get_irn_arity(node); i++) {
 937       if (is_Bad(get_irn_n(node, i))) {
 938         return new_Bad();
 939       }
 940     }
 941   }
 942 #if 0
 943   /* If Block has only Bads as predecessors it's garbage. */
 944   /* If Phi has only Bads as predecessors it's garbage. */
 945   if (op == op_Block || op == op_Phi)  {
 946     for (i = 0; i < get_irn_arity(node); i++) {
 947       if (!is_Bad(get_irn_n(node, i))) break;
 948     }
 949     if (i = get_irn_arity(node)) node = new_Bad();
 950   }
 951 #endif
 952   return node;
 953 }
 954
 955
 956 /* These optimizations deallocate nodes from the obstack.
 957    It can only be called if it is guaranteed that no other nodes
 958    reference this one, i.e., right after construction of a node.  */
 959 ir_node *
 960 optimize (ir_node *n)
 961 {
 962   tarval *tv;
 963   ir_node *old_n = n;
 964
 965   /* Allways optimize Phi nodes: part of the construction. */
 966   if ((!get_optimize()) && (get_irn_op(n) != op_Phi)) return n;
 967
 968   /* if not optimize return n */
 969   if (n == NULL) {
 970     printf(" attention: empty node!!! \n");
 971     return n;
 972   }
 973
 974   /* constant expression evaluation / constant folding */
 975   if (get_opt_constant_folding()) {
 976     /* constants can not be evaluated */
 977     if  (get_irn_op(n) != op_Const) {
 978       /* try to evaluate */
 979       tv = computed_value (n);
 980       if (tv != NULL) {
 981         /* evaluation was succesful -- replace the node. */
 982         obstack_free (current_ir_graph->obst, n);
 983         return new_Const (get_tv_mode (tv), tv);
 984       }
 985     }
 986   }
 987
 988   /* remove unnecessary nodes */
 989   if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
 990     n = equivalent_node (n);
 991
 992   /** common subexpression elimination **/
 993   /* Checks whether n is already available. */
 994   /* The block input is used to distinguish different subexpressions. Right
 995      now all nodes are pinned to blocks, i.e., the cse only finds common
 996      subexpressions within a block. */
 997   if (get_opt_cse())
 998     n = identify (current_ir_graph->value_table, n);
 999   /* identify found a cse, so deallocate the old node. */
1000   if (n != old_n) {
1001     obstack_free (current_ir_graph->obst, old_n);
1002     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
1003   }
1004
1005   /* Some more constant expression evaluation that does not allow to
1006      free the node. */
1007   if (get_opt_constant_folding())
1008     n = transform_node (n);
1009
1010   /* Remove nodes with dead (Bad) input. */
1011   if (get_opt_unreachable_code())
1012     n = gigo (n);
1013   /* Now we can verify the node, as it has no dead inputs any more. */
1014   irn_vrfy(n);
1015
1016   /* Now we have a legal, useful node. Enter it in hash table for cse */
1017   if (get_opt_cse()) {
1018     n = identify_remember (current_ir_graph->value_table, n);
1019   }
1020
1021 #if 0  /* GL: what's the use of this?? */
1022   if ((current_ir_graph->state & irgs_building) && IR_KEEP_ALIVE (n)) {
1023     assert (~current_ir_graph->state & irgs_keep_alives_in_arr);
1024     pdeq_putr (current_ir_graph->keep.living, n);
1025   }
1026 #endif
1027   return n;
1028 }
1029
1030
1031 /* These optimizations never deallocate nodes.  This can cause dead
1032    nodes lying on the obstack.  Remove these by a dead node elimination,
1033    i.e., a copying garbage collection. */
1034 ir_node *
1035 optimize_in_place (ir_node *n)
1036 {
1037   tarval *tv;
1038   ir_node *old_n = n;
1039
1040   if (!get_optimize()) return n;
1041
1042   /* if not optimize return n */
1043   if (n == NULL) {
1044     /* Here this is possible.  Why? */
1045     return n;
1046   }
1047
1048   /* constant expression evaluation / constant folding */
1049   if (get_opt_constant_folding()) {
1050     /* constants can not be evaluated */
1051     if  (get_irn_op(n) != op_Const) {
1052       /* try to evaluate */
1053       tv = computed_value (n);
1054       if (tv != NULL) {
1055         /* evaluation was succesful -- replace the node. */
1056         n = new_Const (get_tv_mode (tv), tv);
1057         deb_info_copy(n, old_n, id_from_str("const_eval", 10));
1058         return n;
1059         /* xprintf("* optimize: computed node %I\n", n->op->name);*/
1060       }
1061     }
1062   }
1063
1064   /* remove unnecessary nodes */
1065   /*if (get_opt_constant_folding()) */
1066   if (get_opt_constant_folding() || get_irn_op(n) == op_Phi)
1067     n = equivalent_node (n);
1068
1069   /** common subexpression elimination **/
1070   /* Checks whether n is already available. */
1071   /* The block input is used to distinguish different subexpressions.  Right
1072      now all nodes are pinned to blocks, i.e., the cse only finds common
1073      subexpressions within a block. */
1074   if (get_opt_cse())
1075     n = identify (current_ir_graph->value_table, n);
1076
1077   /* identify found a cse, so deallocate the old node. */
1078   if (n != old_n) {
1079     /* The AmRoq fiasco returns n here.  Martin's version doesn't. */
1080   }
1081
1082   /* Some more constant expression evaluation. */
1083   if (get_opt_constant_folding())
1084     n = transform_node (n);
1085
1086   /* Remove nodes with dead (Bad) input. */
1087   if (get_opt_unreachable_code())
1088     n = gigo (n);
1089   /* Now we can verify the node, as it has no dead inputs any more. */
1090   irn_vrfy(n);
1091
1092   /* Now we have a legal, useful node. Enter it in hash table for cse.
1093      Blocks should be unique anyways.  (Except the successor of start:
1094      is cse with the start block!) */
1095   if (get_opt_cse() && (get_irn_opcode(n) != iro_Block))
1096     n = identify_remember (current_ir_graph->value_table, n);
1097
1098   return n;
1099 }