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