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