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