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