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