gcc/tree-ssa-pre.c

   1 /* SSA-PRE for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
   4    <stevenb@suse.de>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "errors.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29
  30 /* These RTL headers are needed for basic-block.h.  */
  31 #include "rtl.h"
  32 #include "tm_p.h"
  33 #include "hard-reg-set.h"
  34 #include "basic-block.h"
  35 #include "diagnostic.h"
  36 #include "tree-inline.h"
  37 #include "tree-flow.h"
  38 #include "tree-gimple.h"
  39 #include "tree-dump.h"
  40 #include "timevar.h"
  41 #include "fibheap.h"
  42 #include "hashtab.h"
  43 #include "tree-iterator.h"
  44 #include "real.h"
  45 #include "alloc-pool.h"
  46 #include "tree-pass.h"
  47 #include "flags.h"
  48 #include "splay-tree.h"
  49 #include "bitmap.h"
  50 #include "langhooks.h"
  51 /* TODO:
  52
  53    1. Implement load value numbering.
  54    2. Speed up insert_aux so that we can use it all the time.  It
  55       spends most of it's time in quadratic value replacement.
  56    3. Avail sets can be shared by making an avail_find_leader that
  57       walks up the dominator tree and looks in those avail sets.
  58       This might affect code optimality, it's unclear right now.
  59    4. Load motion can be performed by value numbering the loads the
  60       same as we do other expressions.  This requires iterative
  61       hashing the vuses into the values.  Right now we simply assign
  62       a new value every time we see a statement with a vuse.
  63    5. Strength reduction can be performed by anticipating expressions
  64       we can repair later on.
  65 */
  66
  67 /* For ease of terminology, "expression node" in the below refers to
  68    every expression node but MODIFY_EXPR, because MODIFY_EXPR's represent
  69    the actual statement containing the expressions we care about, and
  70    we cache the value number by putting it in the expression.  */
  71
  72 /* Basic algorithm
  73
  74    First we walk the statements to generate the AVAIL sets, the EXP_GEN
  75    sets, and the tmp_gen sets.  AVAIL is a forward dataflow
  76    problem. EXP_GEN sets represent the generation of
  77    values/expressions by a given block.  We use them when computing
  78    the ANTIC sets.  The AVAIL sets consist of SSA_NAME's that
  79    represent values, so we know what values are available in what
  80    blocks.  In SSA, values are never killed, so we don't need a kill
  81    set, or a fixpoint iteration, in order to calculate the AVAIL sets.
  82    In traditional parlance, AVAIL sets tell us the downsafety of the
  83    expressions/values.
  84
  85    Next, we generate the ANTIC sets.  ANTIC is a backwards dataflow
  86    problem.  These sets represent the anticipatable expressions.  An
  87    expression is anticipatable in a given block if it could be
  88    generated in that block.  This means that if we had to perform an
  89    insertion in that block, of the value of that expression, we could.
  90    Calculating the ANTIC sets requires phi translation of expressions,
  91    because the flow goes backwards through phis.  We must iterate to a
  92    fixpoint of the ANTIC sets, because we have a kill set.
  93    Even in SSA form, values are not live over the entire function,
  94    only from their definition point onwards.  So we have to remove
  95    values from the ANTIC set once we go past the definition point of
  96    the leaders that make them up.  compute_antic/compute_antic_aux
  97    performs this computation.
  98
  99    Third, we perform insertions to make partially redundant
 100    expressions fully redundant.
 101
 102    An expression is partially redundant (excluding partial
 103    anticipation) if:
 104
 105    1. It is AVAIL in some, but not all, of the predecessors of a
 106       given block.
 107    2. It is ANTIC in all the predecessors.
 108
 109    In order to make it fully redundant, we insert the expression into
 110    the predecessors where it is not available, but is ANTIC.
 111    insert/insert_aux performs this insertion.
 112
 113    Fourth, we eliminate fully redundant expressions.
 114    This is a simple statement walk that replaces redundant
 115    calculations  with the now available values.  */
 116
 117 /* Representations of value numbers:
 118
 119    Value numbers are represented using the "value handle" approach.
 120    This means that each SSA_NAME (and for other reasons to be
 121    disclosed in a moment, expression nodes and constant nodes) has a
 122    value handle that can be retrieved through get_value_handle.  This
 123    value handle, *is* the value number of the SSA_NAME.  You can
 124    pointer compare the value handles for equivalence purposes.
 125
 126    For debugging reasons, the value handle is internally more than
 127    just a number, it is a VAR_DECL named "value.x", where x is a
 128    unique number for each value number in use.  This allows
 129    expressions with SSA_NAMES replaced by value handles to still be
 130    pretty printed in a sane way.  They simply print as "value.3 *
 131    value.5", etc.
 132
 133    Expression nodes have value handles associated with them as a
 134    cache.  Otherwise, we'd have to look them up again in the hash
 135    table This makes significant difference (factor of two or more) on
 136    some test cases.  They can be thrown away after the Constants have
 137    value handles associated with them so that they aren't special
 138    cased everywhere, and for consistency sake. This may be changed
 139    depending on memory usage vs code maintenance tradeoff.  */
 140
 141 /* Representation of expressions on value numbers:
 142
 143    In some portions of this code, you will notice we allocate "fake"
 144    analogues to the expression we are value numbering, and replace the
 145    operands with the values of the expression.  Since we work on
 146    values, and not just names, we canonicalize expressions to value
 147    expressions for use in the ANTIC sets, the EXP_GEN set, etc.
 148
 149    This is theoretically unnecessary, it just saves a bunch of
 150    repeated get_value_handle and find_leader calls in the remainder of
 151    the code, trading off temporary memory usage for speed.  The tree
 152    nodes aren't actually creating more garbage, since they are
 153    allocated in a special pools which are thrown away at the end of
 154    this pass.
 155
 156    All of this also means that if you print the EXP_GEN or ANTIC sets,
 157    you will see "value.5 + value.7" in the set, instead of "a_55 +
 158    b_66" or something.  The only thing that actually cares about
 159    seeing the value leaders is phi translation, and it needs to be
 160    able to find the leader for a value in an arbitrary block, so this
 161    "value expression" form is perfect for it (otherwise you'd do
 162    get_value_handle->find_leader->translate->get_value_handle->find_leader).*/
 163
 164
 165 /* Representation of sets:
 166
 167    Sets are represented as doubly linked lists kept in topological
 168    order, with an optional supporting bitmap of values present in the
 169    set.  The sets represent values, and the elements can be constants,
 170    values, or expressions.  The elements can appear in different sets,
 171    but each element can only appear once in each set.
 172
 173    Since each node in the set represents a value, we also want to be
 174    able to map expression, set pairs to something that tells us
 175    whether the value is present is a set.  We use a per-set bitmap for
 176    that.  The value handles also point to a linked list of the
 177    expressions they represent via a tree annotation.  This is mainly
 178    useful only for debugging, since we don't do identity lookups.  */
 179
 180
 181 /* A value set element.  Basically a single linked list of
 182    expressions/constants/values.  */
 183 typedef struct value_set_node
 184 {
 185   tree expr;
 186   struct value_set_node *next;
 187 } *value_set_node_t;
 188
 189
 190 /* A value set, which is the head of the linked list, and we also keep
 191    the tail because we have to append for the topolofical sort.  */
 192 typedef struct value_set
 193 {
 194   value_set_node_t head;
 195   value_set_node_t tail;
 196   size_t length;
 197   bool indexed;
 198   bitmap values;
 199
 200 } *value_set_t;
 201
 202 /* All of the following sets, except for TMP_GEN, are indexed.
 203    TMP_GEN is only ever iterated over, we never check what values
 204    exist in it.  */
 205 typedef struct bb_value_sets
 206 {
 207   value_set_t exp_gen;
 208   value_set_t phi_gen;
 209   value_set_t tmp_gen;
 210   value_set_t avail_out;
 211   value_set_t antic_in;
 212   value_set_t new_sets;
 213 } *bb_value_sets_t;
 214
 215 #define EXP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->exp_gen
 216 #define PHI_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->phi_gen
 217 #define TMP_GEN(BB)     ((bb_value_sets_t) ((BB)->aux))->tmp_gen
 218 #define AVAIL_OUT(BB)   ((bb_value_sets_t) ((BB)->aux))->avail_out
 219 #define ANTIC_IN(BB)    ((bb_value_sets_t) ((BB)->aux))->antic_in
 220 #define NEW_SETS(BB)    ((bb_value_sets_t) ((BB)->aux))->new_sets
 221
 222 static struct
 223 {
 224   int eliminations;
 225   int insertions;
 226   int phis;
 227 } pre_stats;
 228
 229 static tree find_leader (value_set_t, tree);
 230 static void value_insert_into_set (value_set_t, tree);
 231 static void insert_into_set (value_set_t, tree);
 232 static void add_to_value (tree, tree);
 233 static value_set_t set_new  (bool);
 234 static bool is_undefined_value (tree);
 235
 236 /* We can add and remove elements and entries to and from sets
 237    and hash tables, so we use alloc pools for them.  */
 238
 239 static alloc_pool value_set_pool;
 240 static alloc_pool value_set_node_pool;
 241 static alloc_pool binary_node_pool;
 242 static alloc_pool unary_node_pool;
 243
 244 /* The value table that maps expressions to values.  */
 245 static htab_t value_table;
 246
 247 /* The phi_translate_table caches phi translations for a given
 248    expression and predecessor.  */
 249 static htab_t phi_translate_table;
 250
 251
 252 /* Map expressions to values.  These are simple pairs of expressions
 253    and the values they represent.  To find the value represented by
 254    an expression, we use a hash table where the elements are {e,v}
 255    pairs, and the expression is the key.  */
 256
 257 typedef struct val_expr_pair_d
 258 {
 259   tree v, e;
 260   hashval_t hashcode;
 261 } *val_expr_pair_t;
 262
 263
 264 /* Hash a {v,e} pair.  We really only hash the expression.  */
 265
 266 static hashval_t
 267 val_expr_pair_hash (const void *p)
 268 {
 269   const val_expr_pair_t ve = (val_expr_pair_t) p;
 270   return ve->hashcode;
 271 }
 272
 273
 274 /* Are {e2,v2} and {e1,v1} the same?  Again, only the expression
 275    matters.  */
 276
 277 static int
 278 val_expr_pair_expr_eq (const void *p1, const void *p2)
 279 {
 280   const val_expr_pair_t ve1 = (val_expr_pair_t) p1;
 281   const val_expr_pair_t ve2 = (val_expr_pair_t) p2;
 282   tree e1 = ve1->e;
 283   tree e2 = ve2->e;
 284   tree te1;
 285   tree te2;
 286   if (e1 == e2)
 287     return true;
 288
 289   te1 = TREE_TYPE (e1);
 290   te2 = TREE_TYPE (e2);
 291   if (TREE_CODE (e1) == TREE_CODE (e2)
 292       && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
 293       && operand_equal_p (e1, e2, 0))
 294     return true;
 295
 296   return false;
 297 }
 298
 299
 300 /* Get the value handle of EXPR.  This is the only correct way to get
 301    the value handle for a "thing".  */
 302
 303 tree
 304 get_value_handle (tree expr)
 305 {
 306   /* We should never see these.  */
 307   if (DECL_P (expr))
 308     abort ();
 309   else if (TREE_CODE (expr) == SSA_NAME)
 310     {
 311       return SSA_NAME_VALUE (expr);
 312     }
 313   else if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
 314     {
 315       cst_ann_t ann = cst_ann (expr);
 316       if (ann)
 317         return ann->common.value_handle;
 318       return NULL;
 319     }
 320   else if (EXPR_P (expr))
 321     {
 322       expr_ann_t ann = expr_ann (expr);
 323       if (ann)
 324         return ann->common.value_handle;
 325       return NULL;
 326     }
 327   abort ();
 328 }
 329
 330
 331 /* Set the value handle for E to V */
 332
 333 void
 334 set_value_handle (tree e, tree v)
 335 {
 336   if (DECL_P (e))
 337     abort ();
 338   else if (TREE_CODE (e) == SSA_NAME)
 339     SSA_NAME_VALUE (e) = v;
 340   else if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
 341     get_cst_ann (e)->common.value_handle = v;
 342   else if (EXPR_P (e))
 343     get_expr_ann (e)->common.value_handle = v;
 344 }
 345
 346 /* A three tuple {e, pred, v} used to cache phi translations in the
 347    phi_translate_table.  */
 348
 349 typedef struct expr_pred_trans_d
 350 {
 351   tree e;
 352   basic_block pred;
 353   tree v;
 354   hashval_t hashcode;
 355 } *expr_pred_trans_t;
 356
 357 /* Return the hash value for a phi translation table entry.  */
 358
 359 static hashval_t
 360 expr_pred_trans_hash (const void *p)
 361 {
 362   const expr_pred_trans_t ve = (expr_pred_trans_t) p;
 363   return ve->hashcode;
 364 }
 365
 366 /* Return true if two phi translation table entries are the same.  */
 367
 368 static int
 369 expr_pred_trans_eq (const void *p1, const void *p2)
 370 {
 371   const expr_pred_trans_t ve1 = (expr_pred_trans_t) p1;
 372   const expr_pred_trans_t ve2 = (expr_pred_trans_t) p2;
 373   tree e1 = ve1->e;
 374   tree e2 = ve2->e;
 375   basic_block b1 = ve1->pred;
 376   basic_block b2 = ve2->pred;
 377   tree te1;
 378   tree te2;
 379
 380   if (b1 != b2)
 381     return false;
 382
 383   if (e1 == e2)
 384     return true;
 385
 386   te1 = TREE_TYPE (e1);
 387   te2 = TREE_TYPE (e2);
 388
 389   if (TREE_CODE (e1) == TREE_CODE (e2)
 390       && (te1 == te2 || lang_hooks.types_compatible_p (te1, te2))
 391       && operand_equal_p (e1, e2, 0))
 392     return true;
 393
 394   return false;
 395 }
 396
 397 /* Search in the phi translation table for the translation of E in
 398    PRED. Return the translated value, if found, NULL otherwise.  */
 399
 400 static inline tree
 401 phi_trans_lookup (tree e, basic_block pred)
 402 {
 403   void **slot;
 404   struct expr_pred_trans_d ugly;
 405   ugly.e = e;
 406   ugly.pred = pred;
 407   ugly.hashcode = iterative_hash_expr (e, (unsigned long) pred);
 408   slot = htab_find_slot_with_hash (phi_translate_table, &ugly, ugly.hashcode,
 409                                    NO_INSERT);
 410   if (!slot)
 411     return NULL;
 412   else
 413     return ((expr_pred_trans_t) *slot)->v;
 414 }
 415
 416
 417 /* Add the tuple mapping {e, pred}->v to the phi translation table.  */
 418
 419 static inline void
 420 phi_trans_add (tree e, tree v, basic_block pred)
 421 {
 422   void **slot;
 423   expr_pred_trans_t new_pair = xmalloc (sizeof (*new_pair));
 424   new_pair->e = e;
 425   new_pair->pred = pred;
 426   new_pair->v = v;
 427   new_pair->hashcode = iterative_hash_expr (e, (unsigned long) pred);
 428   slot = htab_find_slot_with_hash (phi_translate_table, new_pair,
 429                                    new_pair->hashcode, INSERT);
 430   if (*slot)
 431     free (*slot);
 432   *slot = (void *) new_pair;
 433 }
 434
 435 /* Search in TABLE for an existing instance of expression E,
 436    and return its value, or NULL if none has been set.  */
 437
 438 static inline tree
 439 lookup (htab_t table, tree e)
 440 {
 441   void **slot;
 442   struct val_expr_pair_d ugly = {NULL, NULL, 0};
 443   ugly.e = e;
 444   ugly.hashcode = iterative_hash_expr (e,0);
 445   slot = htab_find_slot_with_hash (table, &ugly, ugly.hashcode, NO_INSERT);
 446   if (!slot)
 447     return NULL_TREE;
 448   else
 449     return ((val_expr_pair_t) *slot)->v;
 450 }
 451
 452 /* Add E to the expression set of V.  */
 453
 454 static inline void
 455 add_to_value (tree v, tree e)
 456 {
 457 #if DEBUG_VALUE_EXPRESSIONS
 458   var_ann_t va = var_ann (v);
 459 #endif
 460   /* For values representing numerical constants, we mark
 461      TREE_CONSTANT as true and set the tree chain to the actual
 462      constant.  This is because unlike values involving expressions,
 463      which are only available to use where the expressions are live, a
 464      constant can be remade anywhere, and thus, is available
 465      everywhere.  */
 466   if (TREE_CODE_CLASS (TREE_CODE (e)) == 'c')
 467     {
 468       TREE_CONSTANT (v) = true;
 469       TREE_CHAIN (v) = e;
 470     }
 471   else if (is_gimple_min_invariant (e))
 472     {
 473       TREE_CONSTANT (v) = true;
 474       TREE_CHAIN (v) = e;
 475     }
 476 #if DEBUG_VALUE_EXPRESSIONS
 477   if (va->expr_set == NULL)
 478     va->expr_set = set_new (false);
 479   insert_into_set (va->expr_set, e);
 480 #endif
 481 }
 482
 483 /* Insert E into TABLE with value V, and add E to the value set for V.  */
 484
 485 static inline void
 486 add (htab_t table, tree e, tree v)
 487 {
 488
 489   void **slot;
 490   val_expr_pair_t new_pair = xmalloc (sizeof (struct val_expr_pair_d));
 491   new_pair->e = e;
 492   new_pair->v = v;
 493   new_pair->hashcode = iterative_hash_expr (e, 0);
 494   slot = htab_find_slot_with_hash (table, new_pair, new_pair->hashcode,
 495                                    INSERT);
 496   if (*slot)
 497     free (*slot);
 498   *slot = (void *) new_pair;
 499   set_value_handle (e, v);
 500
 501   add_to_value (v, e);
 502
 503 }
 504
 505 static int pre_uid;
 506
 507 /* Create a new value handle for EXPR.  */
 508 static tree
 509 create_new_value (tree expr)
 510 {
 511   tree a = create_tmp_var_raw (TREE_TYPE (expr), "value");
 512   create_var_ann (a);
 513   var_ann (a)->uid = pre_uid++;
 514
 515   if (dump_file && (dump_flags & TDF_DETAILS))
 516     {
 517       fprintf (dump_file, "Created value ");
 518       print_generic_expr (dump_file, a, dump_flags);
 519       fprintf (dump_file, " for ");
 520       print_generic_expr (dump_file, expr, dump_flags);
 521       fprintf (dump_file, "\n");
 522     }
 523   return a;
 524 }
 525
 526 /* Like lookup, but adds V as the value for E if E does not have a value.  */
 527 static inline tree
 528 lookup_or_add (htab_t table, tree e)
 529 {
 530   tree x = lookup (table, e);
 531   if (x == NULL_TREE)
 532     {
 533       tree v;
 534       v = create_new_value (e);
 535       add (table, e, v);
 536       x = v;
 537     }
 538   set_value_handle (e, x);
 539   return x;
 540 }
 541
 542
 543 /* Search in the bitmap for SET to see if E exists.  */
 544
 545 static inline bool
 546 value_exists_in_set_bitmap (value_set_t set, tree e)
 547 {
 548   if (TREE_CODE (e) != VAR_DECL)
 549     abort ();
 550
 551   if (!set->values)
 552     return false;
 553   return bitmap_bit_p (set->values, get_var_ann (e)->uid);
 554 }
 555
 556 /* Remove E from the bitmap for SET.  */
 557
 558 static void
 559 value_remove_from_set_bitmap (value_set_t set, tree e)
 560 {
 561   if (TREE_CODE (e) != VAR_DECL)
 562     abort ();
 563 #ifdef ENABLE_CHECKING
 564   if (!set->indexed)
 565     abort ();
 566 #endif
 567   if (!set->values)
 568     return;
 569   bitmap_clear_bit (set->values, get_var_ann (e)->uid);
 570 }
 571
 572
 573 /* Insert the value number E into the bitmap of values existing in
 574    SET.  */
 575
 576 static inline void
 577 value_insert_into_set_bitmap (value_set_t set, tree e)
 578 {
 579   if (TREE_CODE (e) != VAR_DECL)
 580     abort ();
 581 #ifdef ENABLE_CHECKING
 582   if (!set->indexed)
 583     abort ();
 584 #endif
 585   if (set->values == NULL)
 586     {
 587       set->values = BITMAP_GGC_ALLOC ();
 588       bitmap_clear (set->values);
 589     }
 590   bitmap_set_bit (set->values, get_var_ann (e)->uid);
 591 }
 592
 593 /* Create a new set.  */
 594
 595 static value_set_t
 596 set_new  (bool indexed)
 597 {
 598   value_set_t ret;
 599   ret = pool_alloc (value_set_pool);
 600   ret->head = ret->tail = NULL;
 601   ret->length = 0;
 602   ret->indexed = indexed;
 603   ret->values = NULL;
 604   return ret;
 605 }
 606
 607
 608 /* Insert EXPR into SET.  */
 609
 610 static void
 611 insert_into_set (value_set_t set, tree expr)
 612 {
 613   value_set_node_t newnode = pool_alloc (value_set_node_pool);
 614   tree val = get_value_handle (expr);
 615   if (DECL_P (expr))
 616     abort ();
 617
 618   if (val == NULL)
 619     abort ();
 620
 621   /* For indexed sets, insert the value into the set value bitmap.
 622      For all sets, add it to the linked list and increment the list
 623      length.  */
 624   if (set->indexed)
 625     value_insert_into_set_bitmap (set, val);
 626
 627   newnode->next = NULL;
 628   newnode->expr = expr;
 629   set->length ++;
 630   if (set->head == NULL)
 631     {
 632       set->head = set->tail = newnode;
 633     }
 634   else
 635     {
 636       set->tail->next = newnode;
 637       set->tail = newnode;
 638     }
 639 }
 640
 641 /* Copy the set ORIG to the set DEST.  */
 642
 643 static void
 644 set_copy (value_set_t dest, value_set_t orig)
 645 {
 646   value_set_node_t node;
 647
 648   if (!orig || !orig->head)
 649     return;
 650
 651   for (node = orig->head;
 652        node;
 653        node = node->next)
 654     {
 655       insert_into_set (dest, node->expr);
 656     }
 657 }
 658
 659 /* Remove EXPR from SET.  */
 660
 661 static void
 662 set_remove (value_set_t set, tree expr)
 663 {
 664   value_set_node_t node, prev;
 665
 666   /* Remove the value of EXPR from the bitmap, decrement the set
 667      length, and remove it from the actual double linked list.  */
 668   value_remove_from_set_bitmap (set, get_value_handle (expr));
 669   set->length--;
 670   prev = NULL;
 671   for (node = set->head;
 672        node != NULL;
 673        prev = node, node = node->next)
 674     {
 675       if (node->expr == expr)
 676         {
 677           if (prev == NULL)
 678             set->head = node->next;
 679           else
 680             prev->next= node->next;
 681
 682           if (node == set->tail)
 683             set->tail = prev;
 684           pool_free (value_set_node_pool, node);
 685           return;
 686         }
 687     }
 688 }
 689
 690 /* Return true if SET contains the value VAL.  */
 691
 692 static bool
 693 set_contains_value (value_set_t set, tree val)
 694 {
 695   /* This is only referring to the flag above that we set on
 696      values referring to numerical constants, because we know that we
 697      are dealing with one of the value handles we created.  */
 698   if (TREE_CONSTANT (val))
 699     return true;
 700
 701   if (set->length == 0)
 702     return false;
 703
 704   return value_exists_in_set_bitmap (set, val);
 705 }
 706
 707 /* Replace the leader for the value LOOKFOR in SET with EXPR.  */
 708
 709 static void
 710 set_replace_value (value_set_t set, tree lookfor, tree expr)
 711 {
 712   value_set_node_t node = set->head;
 713
 714   /* The lookup is probably more expensive than walking the linked
 715      list when we have only a small number of nodes.  */
 716   if (!set_contains_value (set, lookfor))
 717     return;
 718
 719   for (node = set->head;
 720        node;
 721        node = node->next)
 722     {
 723       if (get_value_handle (node->expr) == lookfor)
 724         {
 725           node->expr = expr;
 726           return;
 727         }
 728     }
 729 }
 730
 731 /* Return true if the set contains expression (not value) EXPR.  */
 732
 733 static bool
 734 set_contains (value_set_t set, tree expr)
 735 {
 736   value_set_node_t node;
 737
 738   for (node = set->head;
 739        node;
 740        node = node->next)
 741     {
 742       if (operand_equal_p (node->expr, expr, 0))
 743         return true;
 744     }
 745   return false;
 746 }
 747
 748 /* Subtract set B from set A, and return the new set.  */
 749
 750 static value_set_t
 751 set_subtract (value_set_t a, value_set_t b, bool indexed)
 752 {
 753   value_set_t ret = set_new (indexed);
 754   value_set_node_t node;
 755   for (node = a->head;
 756        node;
 757        node = node->next)
 758     {
 759       if (!set_contains (b, node->expr))
 760         insert_into_set (ret, node->expr);
 761     }
 762   return ret;
 763 }
 764
 765 /* Return true if two sets are equal. */
 766
 767 static bool
 768 set_equal (value_set_t a, value_set_t b)
 769 {
 770   value_set_node_t node;
 771
 772   if (a->length != b->length)
 773     return false;
 774   for (node = a->head;
 775        node;
 776        node = node->next)
 777     {
 778       if (!set_contains_value (b, get_value_handle (node->expr)))
 779         return false;
 780     }
 781   return true;
 782 }
 783
 784 /* Replace the value for EXPR in SET with EXPR.  */
 785 static void
 786 value_replace_in_set (value_set_t set, tree expr)
 787 {
 788   tree val = get_value_handle (expr);
 789
 790   if (set->length == 0)
 791     return;
 792
 793   set_replace_value (set, val, expr);
 794 }
 795
 796 /* Insert the value for EXPR into SET, if it doesn't exist already.  */
 797
 798 static void
 799 value_insert_into_set (value_set_t set, tree expr)
 800 {
 801   tree val = get_value_handle (expr);
 802
 803   /* Constant values exist everywhere.  */
 804   if (TREE_CONSTANT (val))
 805     return;
 806
 807   if (!set_contains_value (set, val))
 808     insert_into_set (set, expr);
 809 }
 810
 811
 812 /* Print out the value_set SET to OUTFILE.  */
 813
 814 static void
 815 print_value_set (FILE *outfile, value_set_t set,
 816                  const char *setname, int blockindex)
 817 {
 818   value_set_node_t node;
 819   fprintf (outfile, "%s[%d] := { ", setname, blockindex);
 820   if (set)
 821     {
 822       for (node = set->head;
 823            node;
 824            node = node->next)
 825         {
 826           print_generic_expr (outfile, node->expr, 0);
 827           if (node->next)
 828             fprintf (outfile, ", ");
 829         }
 830     }
 831
 832   fprintf (outfile, " }\n");
 833 }
 834
 835 /* Print out the expressions that have VAL to OUTFILE.  */
 836 void
 837 print_value_expressions (FILE *outfile, tree val)
 838 {
 839   var_ann_t va = var_ann (val);
 840   if (va && va->expr_set)
 841     print_value_set (outfile, va->expr_set,
 842                      IDENTIFIER_POINTER (DECL_NAME (val)), 0);
 843 }
 844
 845
 846 void
 847 debug_value_expressions (tree val)
 848 {
 849   print_value_expressions (stderr, val);
 850 }
 851
 852
 853 void debug_value_set (value_set_t, const char *, int);
 854
 855 void
 856 debug_value_set (value_set_t set, const char *setname, int blockindex)
 857 {
 858   print_value_set (stderr, set, setname, blockindex);
 859 }
 860
 861 /* Translate EXPR using phis in PHIBLOCK, so that it has the values of
 862    the phis in PRED.  Return NULL if we can't find a leader for each
 863    part of the translated expression.  */
 864
 865 static tree
 866 phi_translate (tree expr, value_set_t set,  basic_block pred,
 867                basic_block phiblock)
 868 {
 869   tree phitrans = NULL;
 870   tree oldexpr = expr;
 871
 872   if (expr == NULL)
 873     return NULL;
 874
 875   /* Phi translations of a given expression don't change,  */
 876   phitrans = phi_trans_lookup (expr, pred);
 877   if (phitrans)
 878     return phitrans;
 879
 880
 881   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
 882     {
 883     case '2':
 884       {
 885         tree oldop1 = TREE_OPERAND (expr, 0);
 886         tree oldop2 = TREE_OPERAND (expr, 1);
 887         tree newop1;
 888         tree newop2;
 889         tree newexpr;
 890
 891         newop1 = phi_translate (find_leader (set, oldop1),
 892                                 set, pred, phiblock);
 893         if (newop1 == NULL)
 894           return NULL;
 895         newop2 = phi_translate (find_leader (set, oldop2),
 896                                 set, pred, phiblock);
 897         if (newop2 == NULL)
 898           return NULL;
 899         if (newop1 != oldop1 || newop2 != oldop2)
 900           {
 901             newexpr = pool_alloc (binary_node_pool);
 902             memcpy (newexpr, expr, tree_size (expr));
 903             create_expr_ann (newexpr);
 904             TREE_OPERAND (newexpr, 0) = newop1 == oldop1 ? oldop1 : get_value_handle (newop1);
 905             TREE_OPERAND (newexpr, 1) = newop2 == oldop2 ? oldop2 : get_value_handle (newop2);
 906             lookup_or_add (value_table, newexpr);
 907             expr = newexpr;
 908             phi_trans_add (oldexpr, newexpr, pred);
 909           }
 910       }
 911       break;
 912     case '1':
 913       {
 914         tree oldop1 = TREE_OPERAND (expr, 0);
 915         tree newop1;
 916         tree newexpr;
 917
 918         newop1 = phi_translate (find_leader (set, oldop1),
 919                                 set, pred, phiblock);
 920         if (newop1 == NULL)
 921           return NULL;
 922         if (newop1 != oldop1)
 923           {
 924             newexpr = pool_alloc (unary_node_pool);
 925             memcpy (newexpr, expr, tree_size (expr));
 926             create_expr_ann (newexpr);
 927             TREE_OPERAND (newexpr, 0) = get_value_handle (newop1);
 928             lookup_or_add (value_table, newexpr);
 929             expr = newexpr;
 930             phi_trans_add (oldexpr, newexpr, pred);
 931           }
 932       }
 933       break;
 934     case 'd':
 935       abort ();
 936     case 'x':
 937       {
 938         tree phi = NULL;
 939         int i;
 940         if (TREE_CODE (expr) != SSA_NAME)
 941           abort ();
 942         if (TREE_CODE (SSA_NAME_DEF_STMT (expr)) == PHI_NODE)
 943           phi = SSA_NAME_DEF_STMT (expr);
 944         else
 945           return expr;
 946
 947         for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 948           if (PHI_ARG_EDGE (phi, i)->src == pred)
 949             {
 950               tree val;
 951               if (is_undefined_value (PHI_ARG_DEF (phi, i)))
 952                 return NULL;
 953               val = lookup_or_add (value_table, PHI_ARG_DEF (phi, i));
 954               return PHI_ARG_DEF (phi, i);
 955             }
 956       }
 957       break;
 958     }
 959   return expr;
 960 }
 961
 962 static void
 963 phi_translate_set (value_set_t dest, value_set_t set, basic_block pred,
 964                    basic_block phiblock)
 965 {
 966   value_set_node_t node;
 967   for (node = set->head;
 968        node;
 969        node = node->next)
 970     {
 971       tree translated;
 972       translated = phi_translate (node->expr, set, pred, phiblock);
 973       phi_trans_add (node->expr, translated, pred);
 974
 975       if (translated != NULL)
 976         value_insert_into_set (dest, translated);
 977     }
 978 }
 979
 980 /* Find the leader for a value (IE the name representing that
 981    value) in a given set, and return it.  Return NULL if no leader is
 982    found.  */
 983
 984 static tree
 985 find_leader (value_set_t set, tree val)
 986 {
 987   value_set_node_t node;
 988
 989   if (val == NULL)
 990     return NULL;
 991
 992   if (TREE_CONSTANT (val))
 993     return TREE_CHAIN (val);
 994
 995   if (set->length == 0)
 996     return NULL;
 997
 998   if (value_exists_in_set_bitmap (set, val))
 999     {
1000       for (node = set->head;
1001            node;
1002            node = node->next)
1003         {
1004           if (get_value_handle (node->expr) == val)
1005             return node->expr;
1006         }
1007     }
1008   return NULL;
1009 }
1010
1011 /* Determine if the expression EXPR is valid in SET.  This means that
1012    we have a leader for each part of the expression (if it consists of
1013    values), or the expression is an SSA_NAME.
1014
1015    NB:  We never should run into a case where we have SSA_NAME +
1016    SSA_NAME or SSA_NAME + value.  The sets valid_in_set is called on,
1017    the ANTIC sets, will only ever have SSA_NAME's or binary value
1018    expression (IE VALUE1 + VALUE2)  */
1019
1020 static bool
1021 valid_in_set (value_set_t set, tree expr)
1022 {
1023   switch (TREE_CODE_CLASS (TREE_CODE (expr)))
1024     {
1025     case '2':
1026       {
1027         tree op1 = TREE_OPERAND (expr, 0);
1028         tree op2 = TREE_OPERAND (expr, 1);
1029         return set_contains_value (set, op1) && set_contains_value (set, op2);
1030       }
1031       break;
1032     case '1':
1033       {
1034         tree op1 = TREE_OPERAND (expr, 0);
1035         return set_contains_value (set, op1);
1036       }
1037       break;
1038     case 'x':
1039       {
1040         if (TREE_CODE (expr) == SSA_NAME)
1041           return true;
1042         abort ();
1043       }
1044     case 'c':
1045       abort ();
1046     }
1047   return false;
1048 }
1049
1050 /* Clean the set of expressions that are no longer valid in the
1051    specified set.  This means expressions that are made up of values
1052    we have no leaders for in the current set, etc.  */
1053
1054 static void
1055 clean (value_set_t set)
1056 {
1057   value_set_node_t node;
1058   value_set_node_t next;
1059   node = set->head;
1060   while (node)
1061     {
1062       next = node->next;
1063       if (!valid_in_set (set, node->expr))
1064         set_remove (set, node->expr);
1065       node = next;
1066     }
1067 }
1068
1069 /* Compute the ANTIC set for BLOCK.
1070
1071 ANTIC_OUT[BLOCK] = intersection of ANTIC_IN[b] for all succ(BLOCK), if
1072 succs(BLOCK) > 1
1073 ANTIC_OUT[BLOCK] = phi_translate (ANTIC_IN[succ(BLOCK)]) if
1074 succs(BLOCK) == 1
1075
1076 ANTIC_IN[BLOCK] = clean(ANTIC_OUT[BLOCK] U EXP_GEN[BLOCK] -
1077 TMP_GEN[BLOCK])
1078
1079 Iterate until fixpointed.
1080
1081 XXX: It would be nice to either write a set_clear, and use it for
1082 antic_out, or to mark the antic_out set as deleted at the end
1083 of this routine, so that the pool can hand the same memory back out
1084 again for the next antic_out.  */
1085
1086
1087 static bool
1088 compute_antic_aux (basic_block block)
1089 {
1090   basic_block son;
1091   edge e;
1092   bool changed = false;
1093   value_set_t S, old, ANTIC_OUT;
1094   value_set_node_t node;
1095
1096   ANTIC_OUT = S = NULL;
1097   /* If any edges from predecessors are abnormal, antic_in is empty, so
1098      punt.  Remember that the block has an incoming abnormal edge by
1099      setting the BB_VISITED flag.  */
1100   if (! (block->flags & BB_VISITED))
1101     {
1102       for (e = block->pred; e; e = e->pred_next)
1103         if (e->flags & EDGE_ABNORMAL)
1104           {
1105             block->flags |= BB_VISITED;
1106             break;
1107           }
1108     }
1109   if (block->flags & BB_VISITED)
1110     {
1111       S = NULL;
1112       goto visit_sons;
1113     }
1114
1115
1116   old = set_new (false);
1117   set_copy (old, ANTIC_IN (block));
1118   ANTIC_OUT = set_new (true);
1119
1120   /* If the block has no successors, ANTIC_OUT is empty, because it is
1121      the exit block.  */
1122   if (block->succ == NULL);
1123
1124   /* If we have one successor, we could have some phi nodes to
1125      translate through.  */
1126   else if (block->succ->succ_next == NULL)
1127     {
1128       phi_translate_set (ANTIC_OUT, ANTIC_IN(block->succ->dest),
1129                          block, block->succ->dest);
1130     }
1131   /* If we have multiple successors, we take the intersection of all of
1132      them.  */
1133   else
1134     {
1135       varray_type worklist;
1136       edge e;
1137       size_t i;
1138       basic_block bprime, first;
1139
1140       VARRAY_BB_INIT (worklist, 1, "succ");
1141       e = block->succ;
1142       while (e)
1143         {
1144           VARRAY_PUSH_BB (worklist, e->dest);
1145           e = e->succ_next;
1146         }
1147       first = VARRAY_BB (worklist, 0);
1148       set_copy (ANTIC_OUT, ANTIC_IN (first));
1149
1150       for (i = 1; i < VARRAY_ACTIVE_SIZE (worklist); i++)
1151         {
1152           bprime = VARRAY_BB (worklist, i);
1153           node = ANTIC_OUT->head;
1154           while (node)
1155             {
1156               tree val;
1157               value_set_node_t next = node->next;
1158               val = get_value_handle (node->expr);
1159               if (!set_contains_value (ANTIC_IN (bprime), val))
1160                 set_remove (ANTIC_OUT, node->expr);
1161               node = next;
1162             }
1163         }
1164       VARRAY_CLEAR (worklist);
1165     }
1166
1167   /* Generate ANTIC_OUT - TMP_GEN */
1168   S = set_subtract (ANTIC_OUT, TMP_GEN (block), false);
1169
1170   /* Start ANTIC_IN with EXP_GEN - TMP_GEN */
1171   ANTIC_IN (block) = set_subtract (EXP_GEN (block),TMP_GEN (block), true);
1172
1173   /* Then union in the ANTIC_OUT - TMP_GEN values, to get ANTIC_OUT U
1174      EXP_GEN - TMP_GEN */
1175   for (node = S->head;
1176        node;
1177        node = node->next)
1178     {
1179       value_insert_into_set (ANTIC_IN (block), node->expr);
1180     }
1181   clean (ANTIC_IN (block));
1182
1183   if (!set_equal (old, ANTIC_IN (block)))
1184     changed = true;
1185
1186  visit_sons:
1187   if (dump_file && (dump_flags & TDF_DETAILS))
1188     {
1189       if (ANTIC_OUT)
1190         print_value_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
1191       print_value_set (dump_file, ANTIC_IN (block), "ANTIC_IN", block->index);
1192       if (S)
1193         print_value_set (dump_file, S, "S", block->index);
1194
1195     }
1196
1197   for (son = first_dom_son (CDI_POST_DOMINATORS, block);
1198        son;
1199        son = next_dom_son (CDI_POST_DOMINATORS, son))
1200     {
1201       changed |= compute_antic_aux (son);
1202     }
1203   return changed;
1204 }
1205
1206 /* Compute ANTIC sets.  */
1207
1208 static void
1209 compute_antic (void)
1210 {
1211   bool changed = true;
1212   basic_block bb;
1213   int num_iterations = 0;
1214   FOR_ALL_BB (bb)
1215     {
1216       ANTIC_IN (bb) = set_new (true);
1217       bb->flags &= ~BB_VISITED;
1218     }
1219
1220   while (changed)
1221     {
1222       num_iterations++;
1223       changed = false;
1224       changed = compute_antic_aux (EXIT_BLOCK_PTR);
1225     }
1226   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1227     fprintf (dump_file, "compute_antic required %d iterations\n", num_iterations);
1228 }
1229
1230 /* Perform insertion of partially redundant values.
1231    For BLOCK, do the following:
1232    1.  Propagate the NEW_SETS of the dominator into the current block.
1233    If the block has multiple predecessors,
1234        2a. Iterate over the ANTIC expressions for the block to see if
1235            any of them are partially redundant.
1236        2b. If so, insert them into the necessary predecessors to make
1237            the expression fully redundant.
1238        2c. Insert a new PHI merging the values of the predecessors.
1239        2d. Insert the new PHI, and the new expressions, into the
1240            NEW_SETS set.
1241    3. Recursively call ourselves on the dominator children of BLOCK.
1242
1243 */
1244 static bool
1245 insert_aux (basic_block block)
1246 {
1247   basic_block son;
1248   bool new_stuff = false;
1249
1250   if (block)
1251     {
1252       value_set_node_t e;
1253       basic_block dom;
1254       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1255       if (dom)
1256         {
1257           e = NEW_SETS (dom)->head;
1258           while (e)
1259             {
1260               insert_into_set (NEW_SETS (block), e->expr);
1261               value_replace_in_set (AVAIL_OUT (block), e->expr);
1262               e = e->next;
1263             }
1264           if (block->pred->pred_next)
1265             {
1266               value_set_node_t node;
1267               for (node = ANTIC_IN (block)->head;
1268                    node;
1269                    node = node->next)
1270                 {
1271                   if (TREE_CODE_CLASS (TREE_CODE (node->expr)) == '2'
1272                       || TREE_CODE_CLASS (TREE_CODE (node->expr)) == '1')
1273                     {
1274                       tree *avail;
1275                       tree val;
1276                       bool by_some = false;
1277                       bool all_same = true;
1278                       tree first_s = NULL;
1279                       edge pred;
1280                       basic_block bprime;
1281                       tree eprime;
1282                       bool cant_insert = false;
1283
1284                       val = get_value_handle (node->expr);
1285                       if (set_contains_value (PHI_GEN (block), val))
1286                         continue;
1287                       if (set_contains_value (AVAIL_OUT (dom), val))
1288                         {
1289                           if (dump_file && (dump_flags & TDF_DETAILS))
1290                             fprintf (dump_file, "Found fully redundant value\n");
1291                           continue;
1292                         }
1293
1294                       avail = xcalloc (last_basic_block, sizeof (tree));
1295                       for (pred = block->pred;
1296                            pred;
1297                            pred = pred->pred_next)
1298                         {
1299                           tree vprime;
1300                           tree edoubleprime;
1301                           bprime = pred->src;
1302                           eprime = phi_translate (node->expr,
1303                                                   ANTIC_IN (block),
1304                                                   bprime, block);
1305
1306                           /* eprime will generally only be NULL if the
1307                              value of the expression, translated
1308                              through the PHI for this predecessor, is
1309                              undefined.  If that is the case, we can't
1310                              make the expression fully redundant,
1311                              because its value is undefined along a
1312                              predecessor path.  We can thus break out
1313                              early because it doesn't matter what the
1314                              rest of the results are.  */
1315                           if (eprime == NULL)
1316                             {
1317                               cant_insert = true;
1318                               break;
1319                             }
1320
1321                           vprime = get_value_handle (eprime);
1322                           if (!vprime)
1323                             abort ();
1324                           edoubleprime = find_leader (AVAIL_OUT (bprime),
1325                                                       vprime);
1326                           if (edoubleprime == NULL)
1327                             {
1328                               avail[bprime->index] = eprime;
1329                               all_same = false;
1330                             }
1331                           else
1332                             {
1333                               avail[bprime->index] = edoubleprime;
1334                               by_some = true;
1335                               if (first_s == NULL)
1336                                 first_s = edoubleprime;
1337                               else if (first_s != edoubleprime)
1338                                 all_same = false;
1339                               if (first_s != edoubleprime
1340                                   && operand_equal_p (first_s, edoubleprime, 0))
1341                                 abort ();
1342                             }
1343                         }
1344
1345                       if (!cant_insert && !all_same && by_some)
1346                         {
1347                           tree temp;
1348                           tree type = TREE_TYPE (avail[block->pred->src->index]);
1349                           tree v;
1350
1351                           if (dump_file && (dump_flags & TDF_DETAILS))
1352                             {
1353                               fprintf (dump_file, "Found partial redundancy for expression ");
1354                               print_generic_expr (dump_file, node->expr, 0);
1355                               fprintf (dump_file, "\n");
1356                             }
1357
1358                           /* Make the necessary insertions. */
1359                           for (pred = block->pred;
1360                                pred;
1361                                pred = pred->pred_next)
1362                             {
1363                               bprime = pred->src;
1364                               eprime = avail[bprime->index];
1365                               if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '2')
1366                                 {
1367                                   tree s1, s2;
1368                                   tree newexpr;
1369                                   s1 = find_leader (AVAIL_OUT (bprime),
1370                                                     TREE_OPERAND (eprime, 0));
1371                                   /* Depending on the order we process
1372                                      DOM branches in, the value may
1373                                      not have propagated to all the
1374                                      dom children yet during this
1375                                      iteration.  In this case, the
1376                                      value will always be in the
1377                                      NEW_SETS for *our* dominator */
1378                                   if (!s1)
1379                                     s1 = find_leader (NEW_SETS (dom),
1380                                                       TREE_OPERAND (eprime, 0));
1381                                   if (!s1)
1382                                     abort ();
1383
1384                                   s2 = find_leader (AVAIL_OUT (bprime),
1385                                                     TREE_OPERAND (eprime, 1));
1386                                   if (!s2)
1387                                     s2 = find_leader (NEW_SETS (dom),
1388                                                       TREE_OPERAND (eprime, 1));
1389                                   if (!s2)
1390                                     abort ();
1391
1392                                   temp = create_tmp_var (TREE_TYPE (eprime),
1393                                                          "pretmp");
1394                                   add_referenced_tmp_var (temp);
1395                                   newexpr = build (TREE_CODE (eprime),
1396                                                    TREE_TYPE (eprime),
1397                                                    s1, s2);
1398                                   newexpr = build (MODIFY_EXPR,
1399                                                    TREE_TYPE (eprime),
1400                                                    temp, newexpr);
1401                                   temp = make_ssa_name (temp, newexpr);
1402                                   TREE_OPERAND (newexpr, 0) = temp;
1403                                   bsi_insert_on_edge (pred, newexpr);
1404                                   bsi_commit_edge_inserts (NULL);
1405
1406                                   if (dump_file && (dump_flags & TDF_DETAILS))
1407                                     {
1408                                       fprintf (dump_file, "Inserted ");
1409                                       print_generic_expr (dump_file, newexpr, 0);
1410                                       fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1411                                     }
1412                                   pre_stats.insertions++;
1413                                   v = lookup_or_add (value_table, eprime);
1414                                   add (value_table, temp, v);
1415                                   insert_into_set (NEW_SETS (bprime), temp);
1416                                   value_insert_into_set (AVAIL_OUT (bprime),
1417                                                          temp);
1418                                   avail[bprime->index] = temp;
1419                                 }
1420                               else if (TREE_CODE_CLASS (TREE_CODE (eprime)) == '1')
1421                                 {
1422                                   tree s1;
1423                                   tree newexpr;
1424                                   s1 = find_leader (AVAIL_OUT (bprime),
1425                                                     TREE_OPERAND (eprime, 0));
1426                                   /* Depending on the order we process
1427                                      DOM branches in, the value may not have
1428                                      propagated to all the dom
1429                                      children yet in the current
1430                                      iteration, but it will be in
1431                                      NEW_SETS if it is not yet
1432                                      propagated.  */
1433
1434                                   if (!s1)
1435                                     s1 = find_leader (NEW_SETS (dom),
1436                                                       TREE_OPERAND (eprime, 0));
1437                                   if (!s1)
1438                                     abort ();
1439
1440                                   temp = create_tmp_var (TREE_TYPE (eprime),
1441                                                          "pretmp");
1442                                   add_referenced_tmp_var (temp);
1443                                   newexpr = build (TREE_CODE (eprime),
1444                                                    TREE_TYPE (eprime),
1445                                                    s1);
1446                                   newexpr = build (MODIFY_EXPR,
1447                                                    TREE_TYPE (eprime),
1448                                                    temp, newexpr);
1449                                   temp = make_ssa_name (temp, newexpr);
1450                                   TREE_OPERAND (newexpr, 0) = temp;
1451                                   bsi_insert_on_edge (pred, newexpr);
1452                                   bsi_commit_edge_inserts (NULL);
1453
1454                                   if (dump_file && (dump_flags & TDF_DETAILS))
1455                                     {
1456                                       fprintf (dump_file, "Inserted ");
1457                                       print_generic_expr (dump_file, newexpr, 0);
1458                                       fprintf (dump_file, " in predecessor %d\n", pred->src->index);
1459                                     }
1460                                   pre_stats.insertions++;
1461                                   v = lookup_or_add (value_table, eprime);
1462                                   add (value_table, temp, v);
1463                                   insert_into_set (NEW_SETS (bprime), temp);
1464                                   value_insert_into_set (AVAIL_OUT (bprime),
1465                                                          temp);
1466                                   avail[bprime->index] = temp;
1467                                 }
1468                             }
1469                           /* Now build a phi for the new variable.  */
1470                           temp = create_tmp_var (type, "prephitmp");
1471                           add_referenced_tmp_var (temp);
1472                           temp = create_phi_node (temp, block);
1473                           add (value_table, PHI_RESULT (temp), val);
1474
1475 #if 0
1476                           if (!set_contains_value (AVAIL_OUT (block), val))
1477                             insert_into_set (AVAIL_OUT (block),
1478                                              PHI_RESULT (temp));
1479                           else
1480 #endif
1481                             value_replace_in_set (AVAIL_OUT (block),
1482                                                  PHI_RESULT (temp));
1483                           for (pred = block->pred;
1484                                pred;
1485                                pred = pred->pred_next)
1486                             {
1487                               add_phi_arg (&temp, avail[pred->src->index],
1488                                            pred);
1489                             }
1490                           if (dump_file && (dump_flags & TDF_DETAILS))
1491                             {
1492                               fprintf (dump_file, "Created phi ");
1493                               print_generic_expr (dump_file, temp, 0);
1494                               fprintf (dump_file, " in block %d\n", block->index);
1495                             }
1496                           pre_stats.phis++;
1497                           new_stuff = true;
1498                           insert_into_set (NEW_SETS (block),
1499                                            PHI_RESULT (temp));
1500                           insert_into_set (PHI_GEN (block),
1501                                            PHI_RESULT (temp));
1502                         }
1503
1504                       free (avail);
1505                     }
1506                 }
1507             }
1508         }
1509     }
1510   for (son = first_dom_son (CDI_DOMINATORS, block);
1511        son;
1512        son = next_dom_son (CDI_DOMINATORS, son))
1513     {
1514       new_stuff |= insert_aux (son);
1515     }
1516
1517   return new_stuff;
1518 }
1519
1520 /* Perform insertion of partially redundant values.  */
1521
1522 static void
1523 insert (void)
1524 {
1525   bool new_stuff = true;
1526   basic_block bb;
1527   int num_iterations = 0;
1528
1529   FOR_ALL_BB (bb)
1530     NEW_SETS (bb) = set_new (true);
1531
1532   while (new_stuff)
1533     {
1534       num_iterations++;
1535       new_stuff = false;
1536       new_stuff = insert_aux (ENTRY_BLOCK_PTR);
1537     }
1538   if (num_iterations > 2 && dump_file && (dump_flags & TDF_STATS))
1539     fprintf (dump_file, "insert required %d iterations\n", num_iterations);
1540 }
1541
1542 /* Return true if EXPR has no defining statement in this procedure,
1543    *AND* isn't a live-on-entry parameter.  */
1544 static bool
1545 is_undefined_value (tree expr)
1546 {
1547
1548 #ifdef ENABLE_CHECKING
1549   /* We should never be handed DECL's  */
1550   if (DECL_P (expr))
1551     abort ();
1552 #endif
1553   if (TREE_CODE (expr) == SSA_NAME)
1554     {
1555       /* XXX: Is this the correct test?  */
1556       if (TREE_CODE (SSA_NAME_VAR (expr)) == PARM_DECL)
1557         return false;
1558       if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (expr)))
1559         return true;
1560     }
1561   return false;
1562 }
1563
1564 /* Compute the AVAIL set for BLOCK.
1565    This function performs value numbering of the statements in BLOCK.
1566    The AVAIL sets are built from information we glean while doing this
1567    value numbering, since the AVAIL sets contain only entry per
1568    value.
1569
1570
1571    AVAIL_IN[BLOCK] = AVAIL_OUT[dom(BLOCK)].
1572    AVAIL_OUT[BLOCK] = AVAIL_IN[BLOCK] U PHI_GEN[BLOCK] U
1573    TMP_GEN[BLOCK].
1574 */
1575
1576 static void
1577 compute_avail (basic_block block)
1578 {
1579   basic_block son;
1580
1581   /* For arguments with default definitions, we pretend they are
1582      defined in the entry block.  */
1583   if (block == ENTRY_BLOCK_PTR)
1584     {
1585       tree param;
1586       for (param = DECL_ARGUMENTS (current_function_decl);
1587            param;
1588            param = TREE_CHAIN (param))
1589         {
1590           if (default_def (param) != NULL)
1591             {
1592               tree val;
1593               tree def = default_def (param);
1594               val = lookup_or_add (value_table, def);
1595               insert_into_set (TMP_GEN (block), def);
1596               value_insert_into_set (AVAIL_OUT (block), def);
1597             }
1598         }
1599     }
1600   else if (block)
1601     {
1602       block_stmt_iterator bsi;
1603       tree stmt, phi;
1604       basic_block dom;
1605
1606       dom = get_immediate_dominator (CDI_DOMINATORS, block);
1607       if (dom)
1608         set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
1609       for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
1610         {
1611           /* Ignore virtual PHIs until we can do PRE on expressions
1612              with virtual operands.  */
1613           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1614             continue;
1615
1616           lookup_or_add (value_table, PHI_RESULT (phi));
1617           value_insert_into_set (AVAIL_OUT (block), PHI_RESULT (phi));
1618           insert_into_set (PHI_GEN (block), PHI_RESULT (phi));
1619         }
1620
1621       for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
1622         {
1623           tree op0, op1;
1624           stmt = bsi_stmt (bsi);
1625           get_stmt_operands (stmt);
1626
1627           if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1628               || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1629               || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1630               || stmt_ann (stmt)->has_volatile_ops)
1631             {
1632               size_t j;
1633               for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1634                 {
1635                   tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1636                   lookup_or_add (value_table, def);
1637                   insert_into_set (TMP_GEN (block), def);
1638                   value_insert_into_set (AVAIL_OUT (block), def);
1639                 }
1640               for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1641                 {
1642                   tree use = USE_OP (STMT_USE_OPS (stmt), j);
1643                   if (TREE_CODE (use) == SSA_NAME)
1644                     {
1645                       lookup_or_add (value_table, use);
1646                       insert_into_set (TMP_GEN (block), use);
1647                       value_insert_into_set (AVAIL_OUT (block), use);
1648                     }
1649                 }
1650               continue;
1651             }
1652           else if (TREE_CODE (stmt) == RETURN_EXPR
1653                    && TREE_OPERAND (stmt, 0)
1654                    && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
1655             stmt = TREE_OPERAND (stmt, 0);
1656
1657           if (TREE_CODE (stmt) == MODIFY_EXPR)
1658             {
1659               op0 = TREE_OPERAND (stmt, 0);
1660               if (TREE_CODE (op0) != SSA_NAME)
1661                 continue;
1662               if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
1663                 continue;
1664               op1 = TREE_OPERAND (stmt, 1);
1665               STRIP_USELESS_TYPE_CONVERSION (op1);
1666               if (TREE_CODE_CLASS (TREE_CODE (op1)) == 'c')
1667                 {
1668                   add (value_table, op0, lookup_or_add (value_table, op1));
1669                   insert_into_set (TMP_GEN (block), op0);
1670                   value_insert_into_set (AVAIL_OUT (block), op0);
1671                 }
1672               else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '2')
1673                 {
1674                   tree bop1, bop2;
1675                   tree val, val1, val2;
1676                   tree newt;
1677                   bop1 = TREE_OPERAND (op1, 0);
1678                   bop2 = TREE_OPERAND (op1, 1);
1679                   val1 = lookup_or_add (value_table, bop1);
1680                   val2 = lookup_or_add (value_table, bop2);
1681
1682                   newt = pool_alloc (binary_node_pool);
1683                   memcpy (newt, op1, tree_size (op1));
1684                   TREE_OPERAND (newt, 0) = val1;
1685                   TREE_OPERAND (newt, 1) = val2;
1686                   val = lookup_or_add (value_table, newt);
1687                   add (value_table, op0, val);
1688                   if (!is_undefined_value (bop1))
1689                     value_insert_into_set (EXP_GEN (block), bop1);
1690                   if (!is_undefined_value (bop2))
1691                     value_insert_into_set (EXP_GEN (block), bop2);
1692                   value_insert_into_set (EXP_GEN (block), newt);
1693                   insert_into_set (TMP_GEN (block), op0);
1694                   value_insert_into_set (AVAIL_OUT (block), op0);
1695                 }
1696               else if (TREE_CODE_CLASS (TREE_CODE (op1)) == '1'
1697                        && !is_gimple_cast (op1))
1698                 {
1699                   tree uop;
1700                   tree val, val1;
1701                   tree newt;
1702                   uop = TREE_OPERAND (op1, 0);
1703                   val1 = lookup_or_add (value_table, uop);
1704                   newt = pool_alloc (unary_node_pool);
1705                   memcpy (newt, op1, tree_size (op1));
1706                   TREE_OPERAND (newt, 0) = val1;
1707                   val = lookup_or_add (value_table, newt);
1708                   add (value_table, op0, val);
1709                   if (!is_undefined_value (uop))
1710                     value_insert_into_set (EXP_GEN (block), uop);
1711                   value_insert_into_set (EXP_GEN (block), newt);
1712                   insert_into_set (TMP_GEN (block), op0);
1713                   value_insert_into_set (AVAIL_OUT (block), op0);
1714                 }
1715               else if (TREE_CODE (op1) == SSA_NAME)
1716                 {
1717                   tree val = lookup_or_add (value_table, op1);
1718                   add (value_table, op0, val);
1719                   if (!is_undefined_value (op1))
1720                     value_insert_into_set (EXP_GEN (block), op1);
1721                   insert_into_set (TMP_GEN (block), op0);
1722                   value_insert_into_set (AVAIL_OUT (block), op0);
1723                 }
1724               else
1725                 {
1726                   size_t j;
1727                   for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1728                     {
1729                       tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1730                       lookup_or_add (value_table, def);
1731                       insert_into_set (TMP_GEN (block), def);
1732                       value_insert_into_set (AVAIL_OUT (block), def);
1733                       if (def != op0)
1734                         abort ();
1735                     }
1736                   for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1737                     {
1738                       tree use = USE_OP (STMT_USE_OPS (stmt), j);
1739                       if (TREE_CODE (use) == SSA_NAME)
1740                         {
1741                           lookup_or_add (value_table, use);
1742                           insert_into_set (TMP_GEN (block), use);
1743                           value_insert_into_set (AVAIL_OUT (block), use);
1744                         }
1745                     }
1746                 }
1747             }
1748           else
1749             {
1750               size_t j;
1751               for (j = 0; j < NUM_DEFS (STMT_DEF_OPS (stmt)); j++)
1752                 {
1753                   tree def = DEF_OP (STMT_DEF_OPS (stmt), j);
1754                   lookup_or_add (value_table, def);
1755                   insert_into_set (TMP_GEN (block), def);
1756                   value_insert_into_set (AVAIL_OUT (block), def);
1757                 }
1758               for (j = 0; j < NUM_USES (STMT_USE_OPS (stmt)); j++)
1759                 {
1760                   tree use = USE_OP (STMT_USE_OPS (stmt), j);
1761                   if (TREE_CODE (use) == SSA_NAME)
1762                     {
1763                       lookup_or_add (value_table, use);
1764                       insert_into_set (TMP_GEN (block), use);
1765                       value_insert_into_set (AVAIL_OUT (block), use);
1766                     }
1767                 }
1768             }
1769         }
1770     }
1771   for (son = first_dom_son (CDI_DOMINATORS, block);
1772        son;
1773        son = next_dom_son (CDI_DOMINATORS, son))
1774     compute_avail (son);
1775
1776 }
1777
1778 /* Eliminate fully redundant computations.  */
1779
1780 static void
1781 eliminate (void)
1782 {
1783   basic_block b;
1784
1785   FOR_EACH_BB (b)
1786     {
1787       block_stmt_iterator i;
1788
1789       for (i = bsi_start (b); !bsi_end_p (i); bsi_next (&i))
1790         {
1791           tree stmt = bsi_stmt (i);
1792
1793           if (NUM_VUSES (STMT_VUSE_OPS (stmt))
1794               || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt))
1795               || NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt))
1796               || stmt_ann (stmt)->has_volatile_ops)
1797             continue;
1798           /* Lookup the RHS of the expression, see if we have an
1799              available computation for it. If so, replace the RHS with
1800              the available computation.  */
1801           if (TREE_CODE (stmt) == MODIFY_EXPR)
1802             {
1803               tree t = TREE_OPERAND (stmt, 0);
1804               tree expr = TREE_OPERAND (stmt, 1);
1805               tree sprime;
1806               /* There is no point in eliminating NOP_EXPR, it isn't
1807                  supposed to generate any code.  */
1808               if (TREE_CODE (expr) == NOP_EXPR
1809                   || (TREE_CODE_CLASS (TREE_CODE (expr)) != '2'
1810                    && TREE_CODE_CLASS (TREE_CODE (expr)) != '1'))
1811                 continue;
1812               sprime = find_leader (AVAIL_OUT (b),
1813                                     lookup (value_table, t));
1814               if (sprime
1815                   && sprime != t
1816                   && may_propagate_copy (sprime, TREE_OPERAND (stmt, 1)))
1817                 {
1818                   if (dump_file && (dump_flags & TDF_DETAILS))
1819                     {
1820                       fprintf (dump_file, "Replaced ");
1821                       print_generic_expr (dump_file, expr, 0);
1822                       fprintf (dump_file, " with ");
1823                       print_generic_expr (dump_file, sprime, 0);
1824                       fprintf (dump_file, " in ");
1825                       print_generic_stmt (dump_file, stmt, 0);
1826                     }
1827                   pre_stats.eliminations++;
1828                   propagate_value (&TREE_OPERAND (stmt, 1), sprime);
1829                   modify_stmt (stmt);
1830                 }
1831             }
1832
1833         }
1834     }
1835 }
1836
1837 /* Main entry point to the SSA-PRE pass.
1838
1839    PHASE indicates which dump file from the DUMP_FILES array to use when
1840    dumping debugging information.  */
1841
1842 static void
1843 execute_pre (void)
1844 {
1845   size_t tsize;
1846   basic_block bb;
1847   pre_uid = num_referenced_vars;
1848   memset (&pre_stats, 0, sizeof (pre_stats));
1849   FOR_ALL_BB (bb)
1850     {
1851       bb->aux = xcalloc (1, sizeof (struct bb_value_sets));
1852     }
1853   phi_translate_table = htab_create (511, expr_pred_trans_hash,
1854                                      expr_pred_trans_eq,
1855                                      free);
1856   value_table = htab_create (511, val_expr_pair_hash,
1857                              val_expr_pair_expr_eq, free);
1858   value_set_pool = create_alloc_pool ("Value sets",
1859                                       sizeof (struct value_set), 30);
1860   value_set_node_pool = create_alloc_pool ("Value set nodes",
1861                                        sizeof (struct value_set_node), 30);
1862   calculate_dominance_info (CDI_POST_DOMINATORS);
1863   calculate_dominance_info (CDI_DOMINATORS);
1864   tsize = tree_size (build (PLUS_EXPR, void_type_node, NULL_TREE,
1865                             NULL_TREE));
1866   binary_node_pool = create_alloc_pool ("Binary tree nodes", tsize, 30);
1867   tsize = tree_size (build1 (NEGATE_EXPR, void_type_node, NULL_TREE));
1868   unary_node_pool = create_alloc_pool ("Unary tree nodes", tsize, 30);
1869
1870   FOR_ALL_BB (bb)
1871     {
1872       EXP_GEN (bb) = set_new (true);
1873       PHI_GEN (bb) = set_new (true);
1874       TMP_GEN (bb) = set_new (false);
1875       AVAIL_OUT (bb) = set_new (true);
1876     }
1877
1878   compute_avail (ENTRY_BLOCK_PTR);
1879
1880   if (dump_file && (dump_flags & TDF_DETAILS))
1881     {
1882       FOR_ALL_BB (bb)
1883         {
1884           print_value_set (dump_file, EXP_GEN (bb), "exp_gen", bb->index);
1885           print_value_set (dump_file, TMP_GEN (bb), "tmp_gen", bb->index);
1886           print_value_set (dump_file, AVAIL_OUT (bb), "avail_out", bb->index);
1887         }
1888     }
1889
1890   /* Insert can get quite slow on an incredibly large number of basic
1891      blocks due to some quadratic behavior.  Until this behavior is
1892      fixed, don't run it when he have an incredibly large number of
1893      bb's.  If we aren't going to run insert, there is no point in
1894      computing ANTIC, either, even though it's plenty fast.  */
1895
1896   if (n_basic_blocks < 4000)
1897     {
1898       compute_antic ();
1899
1900       insert ();
1901     }
1902   eliminate ();
1903
1904   if (dump_file && (dump_flags & TDF_STATS))
1905     {
1906       fprintf (dump_file, "Insertions:%d\n", pre_stats.insertions);
1907       fprintf (dump_file, "New PHIs:%d\n", pre_stats.phis);
1908       fprintf (dump_file, "Eliminated:%d\n", pre_stats.eliminations);
1909     }
1910
1911   free_alloc_pool (value_set_pool);
1912   free_alloc_pool (value_set_node_pool);
1913   free_alloc_pool (binary_node_pool);
1914   free_alloc_pool (unary_node_pool);
1915   htab_delete (value_table);
1916   htab_delete (phi_translate_table);
1917
1918   FOR_ALL_BB (bb)
1919     {
1920       free (bb->aux);
1921       bb->aux = NULL;
1922     }
1923   free_dominance_info (CDI_POST_DOMINATORS);
1924 }
1925
1926 static bool
1927 gate_pre (void)
1928 {
1929   return flag_tree_pre != 0;
1930 }
1931
1932 struct tree_opt_pass pass_pre =
1933 {
1934   "pre",                                /* name */
1935   gate_pre,                             /* gate */
1936   execute_pre,                          /* execute */
1937   NULL,                                 /* sub */
1938   NULL,                                 /* next */
1939   0,                                    /* static_pass_number */
1940   TV_TREE_PRE,                          /* tv_id */
1941   PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
1942   0,                                    /* properties_provided */
1943   0,                                    /* properties_destroyed */
1944   0,                                    /* todo_flags_start */
1945   TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
1946 };