gcc/tree-ssa-dom.c

   1 /* SSA Dominator optimizations for trees
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "flags.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "ggc.h"
  31 #include "basic-block.h"
  32 #include "output.h"
  33 #include "errors.h"
  34 #include "expr.h"
  35 #include "function.h"
  36 #include "diagnostic.h"
  37 #include "timevar.h"
  38 #include "tree-dump.h"
  39 #include "tree-flow.h"
  40 #include "domwalk.h"
  41 #include "real.h"
  42 #include "tree-pass.h"
  43 #include "langhooks.h"
  44
  45 /* This file implements optimizations on the dominator tree.  */
  46
  47 /* Hash table with expressions made available during the renaming process.
  48    When an assignment of the form X_i = EXPR is found, the statement is
  49    stored in this table.  If the same expression EXPR is later found on the
  50    RHS of another statement, it is replaced with X_i (thus performing
  51    global redundancy elimination).  Similarly as we pass through conditionals
  52    we record the conditional itself as having either a true or false value
  53    in this table.  */
  54 static htab_t avail_exprs;
  55
  56 /* Structure for entries in the expression hash table.
  57
  58    This requires more memory for the hash table entries, but allows us
  59    to avoid creating silly tree nodes and annotations for conditionals,
  60    eliminates 2 global hash tables and two block local varrays.
  61
  62    It also allows us to reduce the number of hash table lookups we
  63    have to perform in lookup_avail_expr and finally it allows us to
  64    significantly reduce the number of calls into the hashing routine
  65    itself.  */
  66 struct expr_hash_elt
  67 {
  68   /* The value (lhs) of this expression.  */
  69   tree lhs;
  70
  71   /* The expression (rhs) we want to record.  */
  72   tree rhs;
  73
  74   /* The annotation if this element corresponds to a statement.  */
  75   stmt_ann_t ann;
  76
  77   /* The hash value for RHS/ann.  */
  78   hashval_t hash;
  79 };
  80
  81 /* Table of constant values and copies indexed by SSA name.  When the
  82    renaming pass finds an assignment of a constant (X_i = C) or a copy
  83    assignment from another SSA variable (X_i = Y_j), it creates a mapping
  84    between X_i and the RHS in this table.  This mapping is used later on,
  85    when renaming uses of X_i.  If an assignment to X_i is found in this
  86    table, instead of using X_i, we use the RHS of the statement stored in
  87    this table (thus performing very simplistic copy and constant
  88    propagation).  */
  89 static varray_type const_and_copies;
  90
  91 /* Bitmap of SSA_NAMEs known to have a nonzero value, even if we do not
  92    know their exact value.  */
  93 static bitmap nonzero_vars;
  94
  95 /* Track whether or not we have changed the control flow graph.  */
  96 static bool cfg_altered;
  97
  98 /* Bitmap of blocks that have had EH statements cleaned.  We should
  99    remove their dead edges eventually.  */
 100 static bitmap need_eh_cleanup;
 101
 102 /* Statistics for dominator optimizations.  */
 103 struct opt_stats_d
 104 {
 105   long num_stmts;
 106   long num_exprs_considered;
 107   long num_re;
 108 };
 109
 110 /* Value range propagation record.  Each time we encounter a conditional
 111    of the form SSA_NAME COND CONST we create a new vrp_element to record
 112    how the condition affects the possible values SSA_NAME may have.
 113
 114    Each record contains the condition tested (COND), and the the range of
 115    values the variable may legitimately have if COND is true.  Note the
 116    range of values may be a smaller range than COND specifies if we have
 117    recorded other ranges for this variable.  Each record also contains the
 118    block in which the range was recorded for invalidation purposes.
 119
 120    Note that the current known range is computed lazily.  This allows us
 121    to avoid the overhead of computing ranges which are never queried.
 122
 123    When we encounter a conditional, we look for records which constrain
 124    the SSA_NAME used in the condition.  In some cases those records allow
 125    us to determine the condition's result at compile time.  In other cases
 126    they may allow us to simplify the condition.
 127
 128    We also use value ranges to do things like transform signed div/mod
 129    operations into unsigned div/mod or to simplify ABS_EXPRs.
 130
 131    Simple experiments have shown these optimizations to not be all that
 132    useful on switch statements (much to my surprise).  So switch statement
 133    optimizations are not performed.
 134
 135    Note carefully we do not propagate information through each statement
 136    in the block.  ie, if we know variable X has a value defined of
 137    [0, 25] and we encounter Y = X + 1, we do not track a value range
 138    for Y (which would be [1, 26] if we cared).  Similarly we do not
 139    constrain values as we encounter narrowing typecasts, etc.  */
 140
 141 struct vrp_element
 142 {
 143   /* The highest and lowest values the variable in COND may contain when
 144      COND is true.  Note this may not necessarily be the same values
 145      tested by COND if the same variable was used in earlier conditionals.
 146
 147      Note this is computed lazily and thus can be NULL indicating that
 148      the values have not been computed yet.  */
 149   tree low;
 150   tree high;
 151
 152   /* The actual conditional we recorded.  This is needed since we compute
 153      ranges lazily.  */
 154   tree cond;
 155
 156   /* The basic block where this record was created.  We use this to determine
 157      when to remove records.  */
 158   basic_block bb;
 159 };
 160
 161 static struct opt_stats_d opt_stats;
 162
 163 /* This virtual array holds pairs of edges which describe a scheduled
 164    edge redirection from jump threading.
 165
 166    The first entry in each pair is the edge we are going to redirect.
 167
 168    The second entry in each pair is the edge leading to our final
 169    destination block.  By providing this as an edge rather than the
 170    final target block itself we can correctly handle redirections
 171    when the target block had PHIs which required edge insertions/splitting
 172    to remove the PHIs.  */
 173 static GTY(()) varray_type redirection_edges;
 174
 175 /* A virtual array holding value range records for the variable identified
 176    by the index, SSA_VERSION.  */
 177 static varray_type vrp_data;
 178
 179 /* Datastructure for block local data used during the dominator walk.
 180    We maintain a stack of these as we recursively walk down the
 181    dominator tree.  */
 182
 183 struct dom_walk_block_data
 184 {
 185   /* Array of all the expressions entered into the global expression
 186      hash table by this block.  During finalization we use this array to
 187      know what expressions to remove from the global expression hash
 188      table.  */
 189   varray_type avail_exprs;
 190
 191   /* Array of dest, src pairs that need to be restored during finalization
 192      into the global const/copies table during finalization.  */
 193   varray_type const_and_copies;
 194
 195   /* Similarly for the nonzero state of variables that needs to be
 196      restored during finalization.  */
 197   varray_type nonzero_vars;
 198
 199   /* Array of statements we need to rescan during finalization for newly
 200      exposed variables.  */
 201   varray_type stmts_to_rescan;
 202
 203   /* Array of variables which have their values constrained by operations
 204      in this basic block.  We use this during finalization to know
 205      which variables need their VRP data updated.  */
 206   varray_type vrp_variables;
 207
 208   /* Array of tree pairs used to restore the global currdefs to its
 209      original state after completing optimization of a block and its
 210      dominator children.  */
 211   varray_type block_defs;
 212 };
 213
 214 struct eq_expr_value
 215 {
 216   tree src;
 217   tree dst;
 218 };
 219
 220 /* Local functions.  */
 221 static void optimize_stmt (struct dom_walk_data *,
 222                            basic_block bb,
 223                            block_stmt_iterator);
 224 static inline tree get_value_for (tree, varray_type table);
 225 static inline void set_value_for (tree, tree, varray_type table);
 226 static tree lookup_avail_expr (tree, varray_type *, bool);
 227 static struct eq_expr_value get_eq_expr_value (tree, int, varray_type *,
 228                                                basic_block, varray_type *);
 229 static hashval_t avail_expr_hash (const void *);
 230 static hashval_t real_avail_expr_hash (const void *);
 231 static int avail_expr_eq (const void *, const void *);
 232 static void htab_statistics (FILE *, htab_t);
 233 static void record_cond (tree, tree, varray_type *);
 234 static void record_dominating_conditions (tree, varray_type *);
 235 static void record_const_or_copy (tree, tree, varray_type *);
 236 static void record_equality (tree, tree, varray_type *);
 237 static tree update_rhs_and_lookup_avail_expr (tree, tree, varray_type *,
 238                                               stmt_ann_t, bool);
 239 static tree simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *,
 240                                                 tree, stmt_ann_t, int);
 241 static tree simplify_cond_and_lookup_avail_expr (tree, varray_type *,
 242                                                  stmt_ann_t, int);
 243 static tree simplify_switch_and_lookup_avail_expr (tree, varray_type *,
 244                                                    stmt_ann_t, int);
 245 static tree find_equivalent_equality_comparison (tree);
 246 static void record_range (tree, basic_block, varray_type *);
 247 static bool extract_range_from_cond (tree, tree *, tree *, int *);
 248 static void record_equivalences_from_phis (struct dom_walk_data *, basic_block);
 249 static void record_equivalences_from_incoming_edge (struct dom_walk_data *,
 250                                                     basic_block);
 251 static bool eliminate_redundant_computations (struct dom_walk_data *,
 252                                               tree, stmt_ann_t);
 253 static void record_equivalences_from_stmt (tree, varray_type *, varray_type *,
 254                                            int, stmt_ann_t);
 255 static void thread_across_edge (struct dom_walk_data *, edge);
 256 static void dom_opt_finalize_block (struct dom_walk_data *, basic_block);
 257 static void dom_opt_initialize_block_local_data (struct dom_walk_data *,
 258                                                  basic_block, bool);
 259 static void dom_opt_initialize_block (struct dom_walk_data *, basic_block);
 260 static void cprop_into_phis (struct dom_walk_data *, basic_block);
 261 static void remove_local_expressions_from_table (varray_type locals,
 262                                                  unsigned limit,
 263                                                  htab_t table);
 264 static void restore_vars_to_original_value (varray_type locals,
 265                                             unsigned limit,
 266                                             varray_type table);
 267 static void restore_currdefs_to_original_value (varray_type locals,
 268                                                 unsigned limit);
 269 static void register_definitions_for_stmt (stmt_ann_t, varray_type *);
 270 static void redirect_edges_and_update_ssa_graph (varray_type);
 271 static edge single_incoming_edge_ignoring_loop_edges (basic_block);
 272
 273 /* Local version of fold that doesn't introduce cruft.  */
 274
 275 static tree
 276 local_fold (tree t)
 277 {
 278   t = fold (t);
 279
 280   /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR that
 281      may have been added by fold, and "useless" type conversions that might
 282      now be apparent due to propagation.  */
 283   STRIP_USELESS_TYPE_CONVERSION (t);
 284
 285   return t;
 286 }
 287
 288 /* Return the value associated with variable VAR in TABLE.  */
 289
 290 static inline tree
 291 get_value_for (tree var, varray_type table)
 292 {
 293   return VARRAY_TREE (table, SSA_NAME_VERSION (var));
 294 }
 295
 296 /* Associate VALUE to variable VAR in TABLE.  */
 297
 298 static inline void
 299 set_value_for (tree var, tree value, varray_type table)
 300 {
 301   VARRAY_TREE (table, SSA_NAME_VERSION (var)) = value;
 302 }
 303
 304 /* REDIRECTION_EDGES contains edge pairs where we want to revector the
 305    destination of the first edge to the destination of the second edge.
 306
 307    These redirections may significantly change the SSA graph since we
 308    allow redirection through blocks with PHI nodes and blocks with
 309    real instructions in some cases.
 310
 311    This routine will perform the requested redirections and incrementally
 312    update the SSA graph.
 313
 314    Note in some cases requested redirections may be ignored as they can
 315    not be safely implemented.  */
 316
 317 static void
 318 redirect_edges_and_update_ssa_graph (varray_type redirection_edges)
 319 {
 320   basic_block tgt, bb;
 321   tree phi;
 322   unsigned int i;
 323   size_t old_num_referenced_vars = num_referenced_vars;
 324   bitmap virtuals_to_rename = BITMAP_XMALLOC ();
 325
 326   /* First note any variables which we are going to have to take
 327      out of SSA form as well as any virtuals which need updating.  */
 328   for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
 329     {
 330       block_stmt_iterator bsi;
 331       edge e;
 332       basic_block tgt;
 333       tree phi;
 334
 335       e = VARRAY_EDGE (redirection_edges, i);
 336       tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
 337
 338       /* All variables referenced in PHI nodes we bypass must be
 339          renamed.  */
 340       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 341         {
 342           tree result = SSA_NAME_VAR (PHI_RESULT (phi));
 343
 344           if (is_gimple_reg (PHI_RESULT (phi)))
 345             bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
 346           else
 347             bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
 348         }
 349
 350       /* Any variables set by statements at the start of the block we
 351          are bypassing must also be taken our of SSA form.  */
 352       for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
 353         {
 354           unsigned int j;
 355           def_optype defs;
 356           v_may_def_optype v_may_defs;
 357           v_must_def_optype v_must_defs;
 358           tree stmt = bsi_stmt (bsi);
 359           stmt_ann_t ann = stmt_ann (stmt);
 360
 361           if (TREE_CODE (stmt) == COND_EXPR)
 362             break;
 363
 364           get_stmt_operands (stmt);
 365
 366           defs = DEF_OPS (ann);
 367           for (j = 0; j < NUM_DEFS (defs); j++)
 368             {
 369               tree op = DEF_OP (defs, j);
 370               tree var = SSA_NAME_VAR (op);
 371               bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 372             }
 373
 374           v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
 375           for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++)
 376             {
 377               tree op = V_MAY_DEF_RESULT (v_may_defs, j);
 378               tree var = SSA_NAME_VAR (op);
 379               bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 380             }
 381
 382           v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
 383           for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++)
 384             {
 385               tree op = V_MUST_DEF_OP (v_must_defs, j);
 386               tree var = SSA_NAME_VAR (op);
 387               bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
 388             }
 389         }
 390
 391       /* Finally, any variables in PHI nodes at our final destination
 392          must also be taken out of SSA form.  */
 393       for (phi = phi_nodes (tgt); phi; phi = PHI_CHAIN (phi))
 394         {
 395           tree result = SSA_NAME_VAR (PHI_RESULT (phi));
 396
 397           if (is_gimple_reg (PHI_RESULT (phi)))
 398             bitmap_set_bit (vars_to_rename, var_ann (result)->uid);
 399           else
 400             bitmap_set_bit (virtuals_to_rename, var_ann (result)->uid);
 401         }
 402     }
 403
 404   /* Take those selected variables out of SSA form.  This must be
 405      done before we start redirecting edges.  */
 406   if (bitmap_first_set_bit (vars_to_rename) >= 0)
 407     rewrite_vars_out_of_ssa (vars_to_rename);
 408
 409   /* The out of SSA translation above may split the edge from
 410      E->src to E->dest.  This could potentially cause us to lose
 411      an assignment leading to invalid warnings about uninitialized
 412      variables or incorrect code.
 413
 414      Luckily, we can detect this by looking at the last statement
 415      in E->dest.  If it is not a COND_EXPR or SWITCH_EXPR, then
 416      the edge was split and instead of E, we want E->dest->succ.  */
 417   for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
 418     {
 419       edge e = VARRAY_EDGE (redirection_edges, i);
 420       tree last = last_stmt (e->dest);
 421
 422       if (last
 423           && TREE_CODE (last) != COND_EXPR
 424           && TREE_CODE (last) != SWITCH_EXPR)
 425         {
 426 #ifdef ENABLE_CHECKING
 427           /* There should only be a single successor if the
 428              original edge was split.  */
 429           if (EDGE_COUNT (e->dest->succs) != 1)
 430             abort ();
 431 #endif
 432           e = EDGE_SUCC (e->dest, 0);
 433
 434           /* Replace the edge in REDIRECTION_EDGES for the
 435              loop below.  */
 436           VARRAY_EDGE (redirection_edges, i) = e;
 437         }
 438     }
 439
 440   /* If we created any new variables as part of the out-of-ssa
 441      translation, then any jump threads must be invalidated if they
 442      bypass a block in which we skipped instructions.
 443
 444      This is necessary as instructions which appeared to be NOPS
 445      may be necessary after the out-of-ssa translation.  */
 446   if (num_referenced_vars != old_num_referenced_vars)
 447     {
 448       for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
 449         {
 450           block_stmt_iterator bsi;
 451           edge e;
 452
 453           e = VARRAY_EDGE (redirection_edges, i);
 454           for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
 455             {
 456               tree stmt = bsi_stmt (bsi);
 457
 458               if (IS_EMPTY_STMT (stmt)
 459                   || TREE_CODE (stmt) == LABEL_EXPR)
 460                 continue;
 461
 462               if (TREE_CODE (stmt) == COND_EXPR)
 463                 break;
 464
 465               /* Invalidate the jump thread.  */
 466               VARRAY_EDGE (redirection_edges, i) = NULL;
 467               VARRAY_EDGE (redirection_edges, i + 1) = NULL;
 468               break;
 469             }
 470         }
 471     }
 472
 473   /* Now redirect the edges.  */
 474   for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_edges); i += 2)
 475     {
 476       basic_block src;
 477       edge e;
 478
 479       e = VARRAY_EDGE (redirection_edges, i);
 480       if (!e)
 481         continue;
 482
 483       tgt = VARRAY_EDGE (redirection_edges, i + 1)->dest;
 484
 485
 486       if (dump_file && (dump_flags & TDF_DETAILS))
 487         fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
 488                  e->src->index, e->dest->index, tgt->index);
 489
 490       src = e->src;
 491
 492       e = redirect_edge_and_branch (e, tgt);
 493       PENDING_STMT (e) = NULL_TREE;
 494
 495       /* Updating the dominance information would be nontrivial.  */
 496       free_dominance_info (CDI_DOMINATORS);
 497
 498       if ((dump_file && (dump_flags & TDF_DETAILS))
 499           && e->src != src)
 500         fprintf (dump_file, "    basic block %d created\n",
 501                  e->src->index);
 502
 503       cfg_altered = true;
 504     }
 505
 506   VARRAY_CLEAR (redirection_edges);
 507
 508   for (i = old_num_referenced_vars; i < num_referenced_vars; i++)
 509     {
 510       bitmap_set_bit (vars_to_rename, i);
 511       var_ann (referenced_var (i))->out_of_ssa_tag = 0;
 512     }
 513
 514   bitmap_a_or_b (vars_to_rename, vars_to_rename, virtuals_to_rename);
 515
 516   /* We must remove any PHIs for virtual variables that we are going to
 517      re-rename.  Hopefully we'll be able to simply update these incrementally
 518      soon.  */
 519   FOR_EACH_BB (bb)
 520     {
 521       tree next;
 522
 523       for (phi = phi_nodes (bb); phi; phi = next)
 524         {
 525           tree result = PHI_RESULT (phi);
 526
 527           next = PHI_CHAIN (phi);
 528
 529           if (bitmap_bit_p (virtuals_to_rename,
 530                             var_ann (SSA_NAME_VAR (result))->uid))
 531             remove_phi_node (phi, NULL, bb);
 532         }
 533     }
 534
 535   BITMAP_XFREE (virtuals_to_rename);
 536 }
 537
 538 /* Jump threading, redundancy elimination and const/copy propagation.
 539
 540    This pass may expose new symbols that need to be renamed into SSA.  For
 541    every new symbol exposed, its corresponding bit will be set in
 542    VARS_TO_RENAME.  */
 543
 544 static void
 545 tree_ssa_dominator_optimize (void)
 546 {
 547   basic_block bb;
 548   struct dom_walk_data walk_data;
 549   unsigned int i;
 550
 551   for (i = 0; i < num_referenced_vars; i++)
 552     var_ann (referenced_var (i))->current_def = NULL;
 553
 554   /* Mark loop edges so we avoid threading across loop boundaries.
 555      This may result in transforming natural loop into irreducible
 556      region.  */
 557   mark_dfs_back_edges ();
 558
 559   /* Create our hash tables.  */
 560   avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free);
 561   VARRAY_TREE_INIT (const_and_copies, num_ssa_names, "const_and_copies");
 562   nonzero_vars = BITMAP_XMALLOC ();
 563   VARRAY_EDGE_INIT (redirection_edges, 20, "redirection_edges");
 564   VARRAY_GENERIC_PTR_INIT (vrp_data, num_ssa_names, "vrp_data");
 565   need_eh_cleanup = BITMAP_XMALLOC ();
 566
 567   /* Setup callbacks for the generic dominator tree walker.  */
 568   walk_data.walk_stmts_backward = false;
 569   walk_data.dom_direction = CDI_DOMINATORS;
 570   walk_data.initialize_block_local_data = dom_opt_initialize_block_local_data;
 571   walk_data.before_dom_children_before_stmts = dom_opt_initialize_block;
 572   walk_data.before_dom_children_walk_stmts = optimize_stmt;
 573   walk_data.before_dom_children_after_stmts = cprop_into_phis;
 574   walk_data.after_dom_children_before_stmts = NULL;
 575   walk_data.after_dom_children_walk_stmts = NULL;
 576   walk_data.after_dom_children_after_stmts = dom_opt_finalize_block;
 577   /* Right now we only attach a dummy COND_EXPR to the global data pointer.
 578      When we attach more stuff we'll need to fill this out with a real
 579      structure.  */
 580   walk_data.global_data = NULL;
 581   walk_data.block_local_data_size = sizeof (struct dom_walk_block_data);
 582
 583   /* Now initialize the dominator walker.  */
 584   init_walk_dominator_tree (&walk_data);
 585
 586   /* Reset block_forwardable in each block's annotation.  We use that
 587      attribute when threading through COND_EXPRs.  */
 588   FOR_EACH_BB (bb)
 589     bb_ann (bb)->forwardable = 1;
 590
 591   calculate_dominance_info (CDI_DOMINATORS);
 592
 593   /* If we prove certain blocks are unreachable, then we want to
 594      repeat the dominator optimization process as PHI nodes may
 595      have turned into copies which allows better propagation of
 596      values.  So we repeat until we do not identify any new unreachable
 597      blocks.  */
 598   do
 599     {
 600       /* Optimize the dominator tree.  */
 601       cfg_altered = false;
 602
 603       /* Recursively walk the dominator tree optimizing statements.  */
 604       walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 605
 606       /* Wipe the hash tables.  */
 607
 608       if (VARRAY_ACTIVE_SIZE (redirection_edges) > 0)
 609         redirect_edges_and_update_ssa_graph (redirection_edges);
 610
 611       if (bitmap_first_set_bit (need_eh_cleanup) >= 0)
 612         {
 613           cfg_altered = tree_purge_all_dead_eh_edges (need_eh_cleanup);
 614           bitmap_zero (need_eh_cleanup);
 615         }
 616
 617       /* We may have made some basic blocks unreachable, remove them.  */
 618       cfg_altered |= delete_unreachable_blocks ();
 619
 620       /* If the CFG was altered, then recompute the dominator tree.  This
 621          is not strictly needed if we only removed unreachable blocks, but
 622          may produce better results.  If we threaded jumps, then rebuilding
 623          the dominator tree is strictly necessary.  Likewise with EH cleanup.
 624          Free the dominance info first so that cleanup_tree_cfg doesn't try
 625          to verify it.  */
 626       if (cfg_altered)
 627         {
 628           free_dominance_info (CDI_DOMINATORS);
 629           cleanup_tree_cfg ();
 630           calculate_dominance_info (CDI_DOMINATORS);
 631         }
 632
 633       /* If we are going to iterate (CFG_ALTERED is true), then we must
 634          perform any queued renaming before the next iteration.  */
 635       if (cfg_altered
 636           && bitmap_first_set_bit (vars_to_rename) >= 0)
 637         {
 638           rewrite_into_ssa (false);
 639           bitmap_clear (vars_to_rename);
 640
 641           /* The into SSA translation may have created new SSA_NAMES whic
 642              affect the size of CONST_AND_COPIES and VRP_DATA.  */
 643           VARRAY_GROW (const_and_copies, num_ssa_names);
 644           VARRAY_GROW (vrp_data, num_ssa_names);
 645         }
 646
 647       /* Reinitialize the various tables.  */
 648       bitmap_clear (nonzero_vars);
 649       htab_empty (avail_exprs);
 650       VARRAY_CLEAR (const_and_copies);
 651       VARRAY_CLEAR (vrp_data);
 652
 653       for (i = 0; i < num_referenced_vars; i++)
 654         var_ann (referenced_var (i))->current_def = NULL;
 655     }
 656   while (cfg_altered);
 657
 658   /* Remove any unreachable blocks left behind and linearize the CFG.  */
 659   cleanup_tree_cfg ();
 660
 661   /* Debugging dumps.  */
 662   if (dump_file && (dump_flags & TDF_STATS))
 663     dump_dominator_optimization_stats (dump_file);
 664
 665   /* We emptied the hash table earlier, now delete it completely.  */
 666   htab_delete (avail_exprs);
 667
 668   /* It is not necessary to clear CURRDEFS, REDIRECTION_EDGES, VRP_DATA,
 669      CONST_AND_COPIES, and NONZERO_VARS as they all get cleared at the bottom
 670      of the do-while loop above.  */
 671
 672   /* And finalize the dominator walker.  */
 673   fini_walk_dominator_tree (&walk_data);
 674
 675   /* Free nonzero_vars.   */
 676   BITMAP_XFREE (nonzero_vars);
 677   BITMAP_XFREE (need_eh_cleanup);
 678 }
 679
 680 static bool
 681 gate_dominator (void)
 682 {
 683   return flag_tree_dom != 0;
 684 }
 685
 686 struct tree_opt_pass pass_dominator =
 687 {
 688   "dom",                                /* name */
 689   gate_dominator,                       /* gate */
 690   tree_ssa_dominator_optimize,          /* execute */
 691   NULL,                                 /* sub */
 692   NULL,                                 /* next */
 693   0,                                    /* static_pass_number */
 694   TV_TREE_SSA_DOMINATOR_OPTS,           /* tv_id */
 695   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 696   0,                                    /* properties_provided */
 697   0,                                    /* properties_destroyed */
 698   0,                                    /* todo_flags_start */
 699   TODO_dump_func | TODO_rename_vars
 700     | TODO_verify_ssa                   /* todo_flags_finish */
 701 };
 702
 703
 704 /* We are exiting BB, see if the target block begins with a conditional
 705    jump which has a known value when reached via BB.  */
 706
 707 static void
 708 thread_across_edge (struct dom_walk_data *walk_data, edge e)
 709 {
 710   struct dom_walk_block_data *bd
 711     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
 712   block_stmt_iterator bsi;
 713   tree stmt = NULL;
 714   tree phi;
 715
 716   /* Each PHI creates a temporary equivalence, record them.  */
 717   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 718     {
 719       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
 720       tree dst = PHI_RESULT (phi);
 721       record_const_or_copy (dst, src, &bd->const_and_copies);
 722       register_new_def (dst, &bd->block_defs);
 723     }
 724
 725   for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
 726     {
 727       tree lhs, cached_lhs;
 728
 729       stmt = bsi_stmt (bsi);
 730
 731       /* Ignore empty statements and labels.  */
 732       if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
 733         continue;
 734
 735       /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
 736          value, then stop our search here.  Ideally when we stop a
 737          search we stop on a COND_EXPR or SWITCH_EXPR.  */
 738       if (TREE_CODE (stmt) != MODIFY_EXPR
 739           || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
 740         break;
 741
 742       /* At this point we have a statement which assigns an RHS to an
 743          SSA_VAR on the LHS.  We want to prove that the RHS is already
 744          available and that its value is held in the current definition
 745          of the LHS -- meaning that this assignment is a NOP when
 746          reached via edge E.  */
 747       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
 748         cached_lhs = TREE_OPERAND (stmt, 1);
 749       else
 750         cached_lhs = lookup_avail_expr (stmt, NULL, false);
 751
 752       lhs = TREE_OPERAND (stmt, 0);
 753
 754       /* This can happen if we thread around to the start of a loop.  */
 755       if (lhs == cached_lhs)
 756         break;
 757
 758       /* If we did not find RHS in the hash table, then try again after
 759          temporarily const/copy propagating the operands.  */
 760       if (!cached_lhs)
 761         {
 762           /* Copy the operands.  */
 763           stmt_ann_t ann = stmt_ann (stmt);
 764           use_optype uses = USE_OPS (ann);
 765           vuse_optype vuses = VUSE_OPS (ann);
 766           tree *uses_copy = xcalloc (NUM_USES (uses),  sizeof (tree));
 767           tree *vuses_copy = xcalloc (NUM_VUSES (vuses), sizeof (tree));
 768           unsigned int i;
 769
 770           /* Make a copy of the uses into USES_COPY, then cprop into
 771              the use operands.  */
 772           for (i = 0; i < NUM_USES (uses); i++)
 773             {
 774               tree tmp = NULL;
 775
 776               uses_copy[i] = USE_OP (uses, i);
 777               if (TREE_CODE (USE_OP (uses, i)) == SSA_NAME)
 778                 tmp = get_value_for (USE_OP (uses, i), const_and_copies);
 779               if (tmp)
 780                 SET_USE_OP (uses, i, tmp);
 781             }
 782
 783           /* Similarly for virtual uses.  */
 784           for (i = 0; i < NUM_VUSES (vuses); i++)
 785             {
 786               tree tmp = NULL;
 787
 788               vuses_copy[i] = VUSE_OP (vuses, i);
 789               if (TREE_CODE (VUSE_OP (vuses, i)) == SSA_NAME)
 790                 tmp = get_value_for (VUSE_OP (vuses, i), const_and_copies);
 791               if (tmp)
 792                 SET_VUSE_OP (vuses, i, tmp);
 793             }
 794
 795           /* Try to lookup the new expression.  */
 796           cached_lhs = lookup_avail_expr (stmt, NULL, false);
 797
 798           /* Restore the statement's original uses/defs.  */
 799           for (i = 0; i < NUM_USES (uses); i++)
 800             SET_USE_OP (uses, i, uses_copy[i]);
 801
 802           for (i = 0; i < NUM_VUSES (vuses); i++)
 803             SET_VUSE_OP (vuses, i, vuses_copy[i]);
 804
 805           free (uses_copy);
 806           free (vuses_copy);
 807
 808           /* If we still did not find the expression in the hash table,
 809              then we can not ignore this statement.  */
 810           if (! cached_lhs)
 811             break;
 812         }
 813
 814       /* If the expression in the hash table was not assigned to an
 815          SSA_NAME, then we can not ignore this statement.  */
 816       if (TREE_CODE (cached_lhs) != SSA_NAME)
 817         break;
 818
 819       /* If we have different underlying variables, then we can not
 820          ignore this statement.  */
 821       if (SSA_NAME_VAR (cached_lhs) != SSA_NAME_VAR (lhs))
 822         break;
 823
 824       /* If CACHED_LHS does not represent the current value of the undering
 825          variable in CACHED_LHS/LHS, then we can not ignore this statement.  */
 826       if (var_ann (SSA_NAME_VAR (lhs))->current_def != cached_lhs)
 827         break;
 828
 829       /* If we got here, then we can ignore this statement and continue
 830          walking through the statements in the block looking for a threadable
 831          COND_EXPR.
 832
 833          We want to record an equivalence lhs = cache_lhs so that if
 834          the result of this statement is used later we can copy propagate
 835          suitably.  */
 836       record_const_or_copy (lhs, cached_lhs, &bd->const_and_copies);
 837       register_new_def (lhs, &bd->block_defs);
 838     }
 839
 840   /* If we stopped at a COND_EXPR or SWITCH_EXPR, then see if we know which
 841      arm will be taken.  */
 842   if (stmt
 843       && (TREE_CODE (stmt) == COND_EXPR
 844           || TREE_CODE (stmt) == SWITCH_EXPR))
 845     {
 846       tree cond, cached_lhs;
 847       edge e1;
 848
 849       /* Do not forward entry edges into the loop.  In the case loop
 850          has multiple entry edges we may end up in constructing irreducible
 851          region.
 852          ??? We may consider forwarding the edges in the case all incoming
 853          edges forward to the same destination block.  */
 854       if (!e->flags & EDGE_DFS_BACK)
 855         {
 856           FOR_EACH_EDGE (e1, e->dest->preds)
 857             {
 858               if (e1->flags & EDGE_DFS_BACK)
 859                 break;
 860             }
 861           END_FOR_EACH_EDGE;
 862           if (e1)
 863             return;
 864         }
 865
 866       /* Now temporarily cprop the operands and try to find the resulting
 867          expression in the hash tables.  */
 868       if (TREE_CODE (stmt) == COND_EXPR)
 869         cond = COND_EXPR_COND (stmt);
 870       else
 871         cond = SWITCH_COND (stmt);
 872
 873       if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
 874         {
 875           tree dummy_cond, op0, op1;
 876           enum tree_code cond_code;
 877
 878           op0 = TREE_OPERAND (cond, 0);
 879           op1 = TREE_OPERAND (cond, 1);
 880           cond_code = TREE_CODE (cond);
 881
 882           /* Get the current value of both operands.  */
 883           if (TREE_CODE (op0) == SSA_NAME)
 884             {
 885               tree tmp = get_value_for (op0, const_and_copies);
 886               if (tmp)
 887                 op0 = tmp;
 888             }
 889
 890           if (TREE_CODE (op1) == SSA_NAME)
 891             {
 892               tree tmp = get_value_for (op1, const_and_copies);
 893               if (tmp)
 894                 op1 = tmp;
 895             }
 896
 897           /* Stuff the operator and operands into our dummy conditional
 898              expression, creating the dummy conditional if necessary.  */
 899           dummy_cond = walk_data->global_data;
 900           if (! dummy_cond)
 901             {
 902               dummy_cond = build (cond_code, boolean_type_node, op0, op1);
 903               dummy_cond = build (COND_EXPR, void_type_node,
 904                                   dummy_cond, NULL, NULL);
 905               walk_data->global_data = dummy_cond;
 906             }
 907           else
 908             {
 909               TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), cond_code);
 910               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op0;
 911               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1) = op1;
 912             }
 913
 914           /* If the conditional folds to an invariant, then we are done,
 915              otherwise look it up in the hash tables.  */
 916           cached_lhs = local_fold (COND_EXPR_COND (dummy_cond));
 917           if (! is_gimple_min_invariant (cached_lhs))
 918             cached_lhs = lookup_avail_expr (dummy_cond, NULL, false);
 919           if (!cached_lhs || ! is_gimple_min_invariant (cached_lhs))
 920             {
 921               stmt_ann_t ann = get_stmt_ann (dummy_cond);
 922               cached_lhs = simplify_cond_and_lookup_avail_expr (dummy_cond,
 923                                                                 NULL,
 924                                                                 ann,
 925                                                                 false);
 926             }
 927         }
 928       /* We can have conditionals which just test the state of a
 929          variable rather than use a relational operator.  These are
 930          simpler to handle.  */
 931       else if (TREE_CODE (cond) == SSA_NAME)
 932         {
 933           cached_lhs = cond;
 934           cached_lhs = get_value_for (cached_lhs, const_and_copies);
 935           if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
 936             cached_lhs = 0;
 937         }
 938       else
 939         cached_lhs = lookup_avail_expr (stmt, NULL, false);
 940
 941       if (cached_lhs)
 942         {
 943           edge taken_edge = find_taken_edge (e->dest, cached_lhs);
 944           basic_block dest = (taken_edge ? taken_edge->dest : NULL);
 945
 946           if (dest == e->dest)
 947             return;
 948
 949           /* If we have a known destination for the conditional, then
 950              we can perform this optimization, which saves at least one
 951              conditional jump each time it applies since we get to
 952              bypass the conditional at our original destination.
 953
 954              Note that we can either thread through a block with PHIs
 955              or to a block with PHIs, but not both.  At this time the
 956              bookkeeping to keep the CFG & SSA up-to-date has proven
 957              difficult.  */
 958           if (dest)
 959             {
 960               int saved_forwardable = bb_ann (e->src)->forwardable;
 961               edge tmp_edge;
 962
 963               bb_ann (e->src)->forwardable = 0;
 964               tmp_edge = tree_block_forwards_to (dest);
 965               taken_edge = (tmp_edge ? tmp_edge : taken_edge);
 966               bb_ann (e->src)->forwardable = saved_forwardable;
 967               VARRAY_PUSH_EDGE (redirection_edges, e);
 968               VARRAY_PUSH_EDGE (redirection_edges, taken_edge);
 969             }
 970         }
 971     }
 972 }
 973
 974
 975 /* Initialize the local stacks.
 976
 977    AVAIL_EXPRS stores all the expressions made available in this block.
 978
 979    CONST_AND_COPIES stores var/value pairs to restore at the end of this
 980    block.
 981
 982    NONZERO_VARS stores the vars which have a nonzero value made in this
 983    block.
 984
 985    STMTS_TO_RESCAN is a list of statements we will rescan for operands.
 986
 987    VRP_VARIABLES is the list of variables which have had their values
 988    constrained by an operation in this block.
 989
 990    These stacks are cleared in the finalization routine run for each
 991    block.  */
 992
 993 static void
 994 dom_opt_initialize_block_local_data (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
 995                                      basic_block bb ATTRIBUTE_UNUSED,
 996                                      bool recycled ATTRIBUTE_UNUSED)
 997 {
 998 #ifdef ENABLE_CHECKING
 999   struct dom_walk_block_data *bd
1000     = (struct dom_walk_block_data *)VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
1001
1002   /* We get cleared memory from the allocator, so if the memory is not
1003      cleared, then we are re-using a previously allocated entry.  In
1004      that case, we can also re-use the underlying virtual arrays.  Just
1005      make sure we clear them before using them!  */
1006   if (recycled)
1007     {
1008       if (bd->avail_exprs && VARRAY_ACTIVE_SIZE (bd->avail_exprs) > 0)
1009         abort ();
1010       if (bd->const_and_copies && VARRAY_ACTIVE_SIZE (bd->const_and_copies) > 0)
1011         abort ();
1012       if (bd->nonzero_vars && VARRAY_ACTIVE_SIZE (bd->nonzero_vars) > 0)
1013         abort ();
1014       if (bd->stmts_to_rescan && VARRAY_ACTIVE_SIZE (bd->stmts_to_rescan) > 0)
1015         abort ();
1016       if (bd->vrp_variables && VARRAY_ACTIVE_SIZE (bd->vrp_variables) > 0)
1017         abort ();
1018       if (bd->block_defs && VARRAY_ACTIVE_SIZE (bd->block_defs) > 0)
1019         abort ();
1020     }
1021 #endif
1022 }
1023
1024 /* Initialize local stacks for this optimizer and record equivalences
1025    upon entry to BB.  Equivalences can come from the edge traversed to
1026    reach BB or they may come from PHI nodes at the start of BB.  */
1027
1028 static void
1029 dom_opt_initialize_block (struct dom_walk_data *walk_data, basic_block bb)
1030 {
1031   if (dump_file && (dump_flags & TDF_DETAILS))
1032     fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index);
1033
1034   record_equivalences_from_incoming_edge (walk_data, bb);
1035
1036   /* PHI nodes can create equivalences too.  */
1037   record_equivalences_from_phis (walk_data, bb);
1038 }
1039
1040 /* Given an expression EXPR (a relational expression or a statement),
1041    initialize the hash table element pointed by by ELEMENT.  */
1042
1043 static void
1044 initialize_hash_element (tree expr, tree lhs, struct expr_hash_elt *element)
1045 {
1046   /* Hash table elements may be based on conditional expressions or statements.
1047
1048      For the former case, we have no annotation and we want to hash the
1049      conditional expression.  In the latter case we have an annotation and
1050      we want to record the expression the statement evaluates.  */
1051   if (TREE_CODE_CLASS (TREE_CODE (expr)) == '<'
1052       || TREE_CODE (expr) == TRUTH_NOT_EXPR)
1053     {
1054       element->ann = NULL;
1055       element->rhs = expr;
1056     }
1057   else if (TREE_CODE (expr) == COND_EXPR)
1058     {
1059       element->ann = stmt_ann (expr);
1060       element->rhs = COND_EXPR_COND (expr);
1061     }
1062   else if (TREE_CODE (expr) == SWITCH_EXPR)
1063     {
1064       element->ann = stmt_ann (expr);
1065       element->rhs = SWITCH_COND (expr);
1066     }
1067   else if (TREE_CODE (expr) == RETURN_EXPR && TREE_OPERAND (expr, 0))
1068     {
1069       element->ann = stmt_ann (expr);
1070       element->rhs = TREE_OPERAND (TREE_OPERAND (expr, 0), 1);
1071     }
1072   else
1073     {
1074       element->ann = stmt_ann (expr);
1075       element->rhs = TREE_OPERAND (expr, 1);
1076     }
1077
1078   element->lhs = lhs;
1079   element->hash = avail_expr_hash (element);
1080 }
1081
1082 /* Remove all the expressions in LOCALS from TABLE, stopping when there are
1083    LIMIT entries left in LOCALs.  */
1084
1085 static void
1086 remove_local_expressions_from_table (varray_type locals,
1087                                      unsigned limit,
1088                                      htab_t table)
1089 {
1090   if (! locals)
1091     return;
1092
1093   /* Remove all the expressions made available in this block.  */
1094   while (VARRAY_ACTIVE_SIZE (locals) > limit)
1095     {
1096       struct expr_hash_elt element;
1097       tree expr = VARRAY_TOP_TREE (locals);
1098       VARRAY_POP (locals);
1099
1100       initialize_hash_element (expr, NULL, &element);
1101       htab_remove_elt_with_hash (table, &element, element.hash);
1102     }
1103 }
1104
1105 /* Use the SSA_NAMES in LOCALS to restore TABLE to its original
1106    state, stopping when there are LIMIT entries left in LOCALs.  */
1107
1108 static void
1109 restore_nonzero_vars_to_original_value (varray_type locals,
1110                                         unsigned limit,
1111                                         bitmap table)
1112 {
1113   if (!locals)
1114     return;
1115
1116   while (VARRAY_ACTIVE_SIZE (locals) > limit)
1117     {
1118       tree name = VARRAY_TOP_TREE (locals);
1119       VARRAY_POP (locals);
1120       bitmap_clear_bit (table, SSA_NAME_VERSION (name));
1121     }
1122 }
1123
1124 /* Use the source/dest pairs in LOCALS to restore TABLE to its original
1125    state, stopping when there are LIMIT entries left in LOCALs.  */
1126
1127 static void
1128 restore_vars_to_original_value (varray_type locals,
1129                                 unsigned limit,
1130                                 varray_type table)
1131 {
1132   if (! locals)
1133     return;
1134
1135   while (VARRAY_ACTIVE_SIZE (locals) > limit)
1136     {
1137       tree prev_value, dest;
1138
1139       prev_value = VARRAY_TOP_TREE (locals);
1140       VARRAY_POP (locals);
1141       dest = VARRAY_TOP_TREE (locals);
1142       VARRAY_POP (locals);
1143
1144       set_value_for (dest, prev_value, table);
1145     }
1146 }
1147
1148 /* Similar to restore_vars_to_original_value, except that it restores
1149    CURRDEFS to its original value.  */
1150 static void
1151 restore_currdefs_to_original_value (varray_type locals, unsigned limit)
1152 {
1153   if (!locals)
1154     return;
1155
1156   /* Restore CURRDEFS to its original state.  */
1157   while (VARRAY_ACTIVE_SIZE (locals) > limit)
1158     {
1159       tree tmp = VARRAY_TOP_TREE (locals);
1160       tree saved_def, var;
1161
1162       VARRAY_POP (locals);
1163
1164       /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1165          definition of its underlying variable.  If we recorded anything
1166          else, it must have been an _DECL node and its current reaching
1167          definition must have been NULL.  */
1168       if (TREE_CODE (tmp) == SSA_NAME)
1169         {
1170           saved_def = tmp;
1171           var = SSA_NAME_VAR (saved_def);
1172         }
1173       else
1174         {
1175           saved_def = NULL;
1176           var = tmp;
1177         }
1178
1179       var_ann (var)->current_def = saved_def;
1180     }
1181 }
1182
1183 /* We have finished processing the dominator children of BB, perform
1184    any finalization actions in preparation for leaving this node in
1185    the dominator tree.  */
1186
1187 static void
1188 dom_opt_finalize_block (struct dom_walk_data *walk_data, basic_block bb)
1189 {
1190   struct dom_walk_block_data *bd
1191     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
1192   tree last;
1193
1194   /* If we are at a leaf node in the dominator graph, see if we can thread
1195      the edge from BB through its successor.
1196
1197      Do this before we remove entries from our equivalence tables.  */
1198   if (EDGE_COUNT (bb->succs) == 1
1199       && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
1200       && (get_immediate_dominator (CDI_DOMINATORS, EDGE_SUCC (bb, 0)->dest) != bb
1201           || phi_nodes (EDGE_SUCC (bb, 0)->dest)))
1202
1203     {
1204       thread_across_edge (walk_data, EDGE_SUCC (bb, 0));
1205     }
1206   else if ((last = last_stmt (bb))
1207            && TREE_CODE (last) == COND_EXPR
1208            && (TREE_CODE_CLASS (TREE_CODE (COND_EXPR_COND (last))) == '<'
1209                || TREE_CODE (COND_EXPR_COND (last)) == SSA_NAME)
1210            && EDGE_COUNT (bb->succs) == 2
1211            && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0
1212            && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0)
1213     {
1214       edge true_edge, false_edge;
1215       tree cond, inverted = NULL;
1216       enum tree_code cond_code;
1217
1218       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
1219
1220       cond = COND_EXPR_COND (last);
1221       cond_code = TREE_CODE (cond);
1222
1223       if (TREE_CODE_CLASS (cond_code) == '<')
1224         inverted = invert_truthvalue (cond);
1225
1226       /* If the THEN arm is the end of a dominator tree or has PHI nodes,
1227          then try to thread through its edge.  */
1228       if (get_immediate_dominator (CDI_DOMINATORS, true_edge->dest) != bb
1229           || phi_nodes (true_edge->dest))
1230         {
1231           unsigned avail_expr_limit;
1232           unsigned const_and_copies_limit;
1233           unsigned currdefs_limit;
1234
1235           avail_expr_limit
1236             = bd->avail_exprs ? VARRAY_ACTIVE_SIZE (bd->avail_exprs) : 0;
1237           const_and_copies_limit
1238             = bd->const_and_copies ? VARRAY_ACTIVE_SIZE (bd->const_and_copies)
1239                                    : 0;
1240           currdefs_limit
1241             = bd->block_defs ? VARRAY_ACTIVE_SIZE (bd->block_defs) : 0;
1242
1243           /* Record any equivalences created by following this edge.  */
1244           if (TREE_CODE_CLASS (cond_code) == '<')
1245             {
1246               record_cond (cond, boolean_true_node, &bd->avail_exprs);
1247               record_dominating_conditions (cond, &bd->avail_exprs);
1248               record_cond (inverted, boolean_false_node, &bd->avail_exprs);
1249             }
1250           else if (cond_code == SSA_NAME)
1251             record_const_or_copy (cond, boolean_true_node,
1252                                   &bd->const_and_copies);
1253
1254           /* Now thread the edge.  */
1255           thread_across_edge (walk_data, true_edge);
1256
1257           /* And restore the various tables to their state before
1258              we threaded this edge.  */
1259           remove_local_expressions_from_table (bd->avail_exprs,
1260                                                avail_expr_limit,
1261                                                avail_exprs);
1262           restore_vars_to_original_value (bd->const_and_copies,
1263                                           const_and_copies_limit,
1264                                           const_and_copies);
1265           restore_currdefs_to_original_value (bd->block_defs, currdefs_limit);
1266         }
1267
1268       /* Similarly for the ELSE arm.  */
1269       if (get_immediate_dominator (CDI_DOMINATORS, false_edge->dest) != bb
1270           || phi_nodes (false_edge->dest))
1271         {
1272           /* Record any equivalences created by following this edge.  */
1273           if (TREE_CODE_CLASS (cond_code) == '<')
1274             {
1275               record_cond (cond, boolean_false_node, &bd->avail_exprs);
1276               record_cond (inverted, boolean_true_node, &bd->avail_exprs);
1277               record_dominating_conditions (inverted, &bd->avail_exprs);
1278             }
1279           else if (cond_code == SSA_NAME)
1280             record_const_or_copy (cond, boolean_false_node,
1281                                   &bd->const_and_copies);
1282
1283           thread_across_edge (walk_data, false_edge);
1284
1285           /* No need to remove local expressions from our tables
1286              or restore vars to their original value as that will
1287              be done immediately below.  */
1288         }
1289     }
1290
1291   remove_local_expressions_from_table (bd->avail_exprs, 0, avail_exprs);
1292   restore_nonzero_vars_to_original_value (bd->nonzero_vars, 0, nonzero_vars);
1293   restore_vars_to_original_value (bd->const_and_copies, 0, const_and_copies);
1294   restore_currdefs_to_original_value (bd->block_defs, 0);
1295
1296   /* Remove VRP records associated with this basic block.  They are no
1297      longer valid.
1298
1299      To be efficient, we note which variables have had their values
1300      constrained in this block.  So walk over each variable in the
1301      VRP_VARIABLEs array.  */
1302   while (bd->vrp_variables && VARRAY_ACTIVE_SIZE (bd->vrp_variables) > 0)
1303     {
1304       tree var = VARRAY_TOP_TREE (bd->vrp_variables);
1305
1306       /* Each variable has a stack of value range records.  We want to
1307          invalidate those associated with our basic block.  So we walk
1308          the array backwards popping off records associated with our
1309          block.  Once we hit a record not associated with our block
1310          we are done.  */
1311       varray_type var_vrp_records = VARRAY_GENERIC_PTR (vrp_data,
1312                                                         SSA_NAME_VERSION (var));
1313
1314       while (VARRAY_ACTIVE_SIZE (var_vrp_records) > 0)
1315         {
1316           struct vrp_element *element
1317             = (struct vrp_element *)VARRAY_TOP_GENERIC_PTR (var_vrp_records);
1318
1319           if (element->bb != bb)
1320             break;
1321
1322           VARRAY_POP (var_vrp_records);
1323         }
1324
1325       VARRAY_POP (bd->vrp_variables);
1326     }
1327
1328   /* Re-scan operands in all statements that may have had new symbols
1329      exposed.  */
1330   while (bd->stmts_to_rescan && VARRAY_ACTIVE_SIZE (bd->stmts_to_rescan) > 0)
1331     {
1332       tree stmt = VARRAY_TOP_TREE (bd->stmts_to_rescan);
1333       VARRAY_POP (bd->stmts_to_rescan);
1334       mark_new_vars_to_rename (stmt, vars_to_rename);
1335     }
1336 }
1337
1338 /* PHI nodes can create equivalences too.
1339
1340    Ignoring any alternatives which are the same as the result, if
1341    all the alternatives are equal, then the PHI node creates an
1342    equivalence.
1343
1344    Additionally, if all the PHI alternatives are known to have a nonzero
1345    value, then the result of this PHI is known to have a nonzero value,
1346    even if we do not know its exact value.  */
1347
1348 static void
1349 record_equivalences_from_phis (struct dom_walk_data *walk_data, basic_block bb)
1350 {
1351   struct dom_walk_block_data *bd
1352     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
1353   tree phi;
1354
1355   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1356     {
1357       tree lhs = PHI_RESULT (phi);
1358       tree rhs = NULL;
1359       int i;
1360
1361       for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1362         {
1363           tree t = PHI_ARG_DEF (phi, i);
1364
1365           if (TREE_CODE (t) == SSA_NAME || is_gimple_min_invariant (t))
1366             {
1367               /* Ignore alternatives which are the same as our LHS.  */
1368               if (operand_equal_p (lhs, t, 0))
1369                 continue;
1370
1371               /* If we have not processed an alternative yet, then set
1372                  RHS to this alternative.  */
1373               if (rhs == NULL)
1374                 rhs = t;
1375               /* If we have processed an alternative (stored in RHS), then
1376                  see if it is equal to this one.  If it isn't, then stop
1377                  the search.  */
1378               else if (! operand_equal_p (rhs, t, 0))
1379                 break;
1380             }
1381           else
1382             break;
1383         }
1384
1385       /* If we had no interesting alternatives, then all the RHS alternatives
1386          must have been the same as LHS.  */
1387       if (!rhs)
1388         rhs = lhs;
1389
1390       /* If we managed to iterate through each PHI alternative without
1391          breaking out of the loop, then we have a PHI which may create
1392          a useful equivalence.  We do not need to record unwind data for
1393          this, since this is a true assignment and not an equivalence
1394          inferred from a comparison.  All uses of this ssa name are dominated
1395          by this assignment, so unwinding just costs time and space.  */
1396       if (i == PHI_NUM_ARGS (phi)
1397           && may_propagate_copy (lhs, rhs))
1398         set_value_for (lhs, rhs, const_and_copies);
1399
1400       /* Now see if we know anything about the nonzero property for the
1401          result of this PHI.  */
1402       for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1403         {
1404           if (!PHI_ARG_NONZERO (phi, i))
1405             break;
1406         }
1407
1408       if (i == PHI_NUM_ARGS (phi))
1409         bitmap_set_bit (nonzero_vars, SSA_NAME_VERSION (PHI_RESULT (phi)));
1410
1411       register_new_def (lhs, &bd->block_defs);
1412     }
1413 }
1414
1415 /* Ignoring loop backedges, if BB has precisely one incoming edge then
1416    return that edge.  Otherwise return NULL.  */
1417 static edge
1418 single_incoming_edge_ignoring_loop_edges (basic_block bb)
1419 {
1420   edge retval = NULL;
1421   edge e;
1422
1423   FOR_EACH_EDGE (e, bb->preds)
1424     {
1425       /* A loop back edge can be identified by the destination of
1426          the edge dominating the source of the edge.  */
1427       if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
1428         continue;
1429
1430       /* If we have already seen a non-loop edge, then we must have
1431          multiple incoming non-loop edges and thus we return NULL.  */
1432       if (retval)
1433         return NULL;
1434
1435       /* This is the first non-loop incoming edge we have found.  Record
1436          it.  */
1437       retval = e;
1438     }
1439   END_FOR_EACH_EDGE;
1440
1441   return retval;
1442 }
1443
1444 /* Record any equivalences created by the incoming edge to BB.  If BB
1445    has more than one incoming edge, then no equivalence is created.  */
1446
1447 static void
1448 record_equivalences_from_incoming_edge (struct dom_walk_data *walk_data,
1449                                         basic_block bb)
1450 {
1451   int edge_flags;
1452   basic_block parent;
1453   struct eq_expr_value eq_expr_value;
1454   tree parent_block_last_stmt = NULL;
1455   struct dom_walk_block_data *bd
1456     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
1457
1458   /* If our parent block ended with a control statment, then we may be
1459      able to record some equivalences based on which outgoing edge from
1460      the parent was followed.  */
1461   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
1462   if (parent)
1463     {
1464       parent_block_last_stmt = last_stmt (parent);
1465       if (parent_block_last_stmt && !is_ctrl_stmt (parent_block_last_stmt))
1466         parent_block_last_stmt = NULL;
1467     }
1468
1469   eq_expr_value.src = NULL;
1470   eq_expr_value.dst = NULL;
1471
1472   /* If we have a single predecessor (ignoring loop backedges), then extract
1473      EDGE_FLAGS from the single incoming edge.  Otherwise just return as
1474      there is nothing to do.  */
1475   if (EDGE_COUNT (bb->preds) == 1
1476       && parent_block_last_stmt)
1477     {
1478       edge e = single_incoming_edge_ignoring_loop_edges (bb);
1479       if (e && bb_for_stmt (parent_block_last_stmt) == e->src)
1480         edge_flags = e->flags;
1481       else
1482         return;
1483     }
1484   else
1485     return;
1486
1487   /* If our parent block ended in a COND_EXPR, add any equivalences
1488      created by the COND_EXPR to the hash table and initialize
1489      EQ_EXPR_VALUE appropriately.
1490
1491      EQ_EXPR_VALUE is an assignment expression created when BB's immediate
1492      dominator ends in a COND_EXPR statement whose predicate is of the form
1493      'VAR == VALUE', where VALUE may be another variable or a constant.
1494      This is used to propagate VALUE on the THEN_CLAUSE of that
1495      conditional. This assignment is inserted in CONST_AND_COPIES so that
1496      the copy and constant propagator can find more propagation
1497      opportunities.  */
1498   if (TREE_CODE (parent_block_last_stmt) == COND_EXPR
1499       && (edge_flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
1500     eq_expr_value = get_eq_expr_value (parent_block_last_stmt,
1501                                        (edge_flags & EDGE_TRUE_VALUE) != 0,
1502                                        &bd->avail_exprs,
1503                                        bb,
1504                                        &bd->vrp_variables);
1505   /* Similarly when the parent block ended in a SWITCH_EXPR.
1506      We can only know the value of the switch's condition if the dominator
1507      parent is also the only predecessor of this block.  */
1508   else if (EDGE_PRED (bb, 0)->src == parent
1509            && TREE_CODE (parent_block_last_stmt) == SWITCH_EXPR)
1510     {
1511       tree switch_cond = SWITCH_COND (parent_block_last_stmt);
1512
1513       /* If the switch's condition is an SSA variable, then we may
1514          know its value at each of the case labels.  */
1515       if (TREE_CODE (switch_cond) == SSA_NAME)
1516         {
1517           tree switch_vec = SWITCH_LABELS (parent_block_last_stmt);
1518           size_t i, n = TREE_VEC_LENGTH (switch_vec);
1519           int case_count = 0;
1520           tree match_case = NULL_TREE;
1521
1522           /* Search the case labels for those whose destination is
1523              the current basic block.  */
1524           for (i = 0; i < n; ++i)
1525             {
1526               tree elt = TREE_VEC_ELT (switch_vec, i);
1527               if (label_to_block (CASE_LABEL (elt)) == bb)
1528                 {
1529                   if (++case_count > 1 || CASE_HIGH (elt))
1530                     break;
1531                   match_case = elt;
1532                 }
1533             }
1534
1535           /* If we encountered precisely one CASE_LABEL_EXPR and it
1536              was not the default case, or a case range, then we know
1537              the exact value of SWITCH_COND which caused us to get to
1538              this block.  Record that equivalence in EQ_EXPR_VALUE.  */
1539           if (case_count == 1
1540               && match_case
1541               && CASE_LOW (match_case)
1542               && !CASE_HIGH (match_case))
1543             {
1544               eq_expr_value.dst = switch_cond;
1545               eq_expr_value.src = fold_convert (TREE_TYPE (switch_cond),
1546                                                 CASE_LOW (match_case));
1547             }
1548         }
1549     }
1550
1551   /* If EQ_EXPR_VALUE (VAR == VALUE) is given, register the VALUE as a
1552      new value for VAR, so that occurrences of VAR can be replaced with
1553      VALUE while re-writing the THEN arm of a COND_EXPR.  */
1554   if (eq_expr_value.src && eq_expr_value.dst)
1555     record_equality (eq_expr_value.dst, eq_expr_value.src,
1556                      &bd->const_and_copies);
1557 }
1558
1559 /* Dump SSA statistics on FILE.  */
1560
1561 void
1562 dump_dominator_optimization_stats (FILE *file)
1563 {
1564   long n_exprs;
1565
1566   fprintf (file, "Total number of statements:                   %6ld\n\n",
1567            opt_stats.num_stmts);
1568   fprintf (file, "Exprs considered for dominator optimizations: %6ld\n",
1569            opt_stats.num_exprs_considered);
1570
1571   n_exprs = opt_stats.num_exprs_considered;
1572   if (n_exprs == 0)
1573     n_exprs = 1;
1574
1575   fprintf (file, "    Redundant expressions eliminated:         %6ld (%.0f%%)\n",
1576            opt_stats.num_re, PERCENT (opt_stats.num_re,
1577                                       n_exprs));
1578
1579   fprintf (file, "\nHash table statistics:\n");
1580
1581   fprintf (file, "    avail_exprs: ");
1582   htab_statistics (file, avail_exprs);
1583 }
1584
1585
1586 /* Dump SSA statistics on stderr.  */
1587
1588 void
1589 debug_dominator_optimization_stats (void)
1590 {
1591   dump_dominator_optimization_stats (stderr);
1592 }
1593
1594
1595 /* Dump statistics for the hash table HTAB.  */
1596
1597 static void
1598 htab_statistics (FILE *file, htab_t htab)
1599 {
1600   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1601            (long) htab_size (htab),
1602            (long) htab_elements (htab),
1603            htab_collisions (htab));
1604 }
1605
1606 /* Record the fact that VAR has a nonzero value, though we may not know
1607    its exact value.  Note that if VAR is already known to have a nonzero
1608    value, then we do nothing.  */
1609
1610 static void
1611 record_var_is_nonzero (tree var, varray_type *block_nonzero_vars_p)
1612 {
1613   int indx = SSA_NAME_VERSION (var);
1614
1615   if (bitmap_bit_p (nonzero_vars, indx))
1616     return;
1617
1618   /* Mark it in the global table.  */
1619   bitmap_set_bit (nonzero_vars, indx);
1620
1621   /* Record this SSA_NAME so that we can reset the global table
1622      when we leave this block.  */
1623   if (! *block_nonzero_vars_p)
1624     VARRAY_TREE_INIT (*block_nonzero_vars_p, 2, "block_nonzero_vars");
1625   VARRAY_PUSH_TREE (*block_nonzero_vars_p, var);
1626 }
1627
1628 /* Enter a statement into the true/false expression hash table indicating
1629    that the condition COND has the value VALUE.  */
1630
1631 static void
1632 record_cond (tree cond, tree value, varray_type *block_avail_exprs_p)
1633 {
1634   struct expr_hash_elt *element = xmalloc (sizeof (struct expr_hash_elt));
1635   void **slot;
1636
1637   initialize_hash_element (cond, value, element);
1638
1639   slot = htab_find_slot_with_hash (avail_exprs, (void *)element,
1640                                    element->hash, true);
1641   if (*slot == NULL)
1642     {
1643       *slot = (void *) element;
1644       if (! *block_avail_exprs_p)
1645         VARRAY_TREE_INIT (*block_avail_exprs_p, 20, "block_avail_exprs");
1646       VARRAY_PUSH_TREE (*block_avail_exprs_p, cond);
1647     }
1648   else
1649     free (element);
1650 }
1651
1652 /* COND is a condition which is known to be true.   Record variants of
1653    COND which must also be true.
1654
1655    For example, if a < b is true, then a <= b must also be true.  */
1656
1657 static void
1658 record_dominating_conditions (tree cond, varray_type *block_avail_exprs_p)
1659 {
1660   switch (TREE_CODE (cond))
1661     {
1662     case LT_EXPR:
1663       record_cond (build2 (LE_EXPR, boolean_type_node,
1664                            TREE_OPERAND (cond, 0),
1665                            TREE_OPERAND (cond, 1)),
1666                    boolean_true_node,
1667                    block_avail_exprs_p);
1668       record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1669                            TREE_OPERAND (cond, 0),
1670                            TREE_OPERAND (cond, 1)),
1671                    boolean_true_node,
1672                    block_avail_exprs_p);
1673       record_cond (build2 (NE_EXPR, boolean_type_node,
1674                            TREE_OPERAND (cond, 0),
1675                            TREE_OPERAND (cond, 1)),
1676                    boolean_true_node,
1677                    block_avail_exprs_p);
1678       record_cond (build2 (LTGT_EXPR, boolean_type_node,
1679                            TREE_OPERAND (cond, 0),
1680                            TREE_OPERAND (cond, 1)),
1681                    boolean_true_node,
1682                    block_avail_exprs_p);
1683       break;
1684
1685     case GT_EXPR:
1686       record_cond (build2 (GE_EXPR, boolean_type_node,
1687                            TREE_OPERAND (cond, 0),
1688                            TREE_OPERAND (cond, 1)),
1689                    boolean_true_node,
1690                    block_avail_exprs_p);
1691       record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1692                            TREE_OPERAND (cond, 0),
1693                            TREE_OPERAND (cond, 1)),
1694                    boolean_true_node,
1695                    block_avail_exprs_p);
1696       record_cond (build2 (NE_EXPR, boolean_type_node,
1697                            TREE_OPERAND (cond, 0),
1698                            TREE_OPERAND (cond, 1)),
1699                    boolean_true_node,
1700                    block_avail_exprs_p);
1701       record_cond (build2 (LTGT_EXPR, boolean_type_node,
1702                            TREE_OPERAND (cond, 0),
1703                            TREE_OPERAND (cond, 1)),
1704                    boolean_true_node,
1705                    block_avail_exprs_p);
1706       break;
1707
1708     case GE_EXPR:
1709     case LE_EXPR:
1710       record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1711                            TREE_OPERAND (cond, 0),
1712                            TREE_OPERAND (cond, 1)),
1713                    boolean_true_node,
1714                    block_avail_exprs_p);
1715       break;
1716
1717     case EQ_EXPR:
1718       record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1719                            TREE_OPERAND (cond, 0),
1720                            TREE_OPERAND (cond, 1)),
1721                    boolean_true_node,
1722                    block_avail_exprs_p);
1723       record_cond (build2 (LE_EXPR, boolean_type_node,
1724                            TREE_OPERAND (cond, 0),
1725                            TREE_OPERAND (cond, 1)),
1726                    boolean_true_node,
1727                    block_avail_exprs_p);
1728       record_cond (build2 (GE_EXPR, boolean_type_node,
1729                            TREE_OPERAND (cond, 0),
1730                            TREE_OPERAND (cond, 1)),
1731                    boolean_true_node,
1732                    block_avail_exprs_p);
1733       break;
1734
1735     case UNORDERED_EXPR:
1736       record_cond (build2 (NE_EXPR, boolean_type_node,
1737                            TREE_OPERAND (cond, 0),
1738                            TREE_OPERAND (cond, 1)),
1739                    boolean_true_node,
1740                    block_avail_exprs_p);
1741       record_cond (build2 (UNLE_EXPR, boolean_type_node,
1742                            TREE_OPERAND (cond, 0),
1743                            TREE_OPERAND (cond, 1)),
1744                    boolean_true_node,
1745                    block_avail_exprs_p);
1746       record_cond (build2 (UNGE_EXPR, boolean_type_node,
1747                            TREE_OPERAND (cond, 0),
1748                            TREE_OPERAND (cond, 1)),
1749                    boolean_true_node,
1750                    block_avail_exprs_p);
1751       record_cond (build2 (UNEQ_EXPR, boolean_type_node,
1752                            TREE_OPERAND (cond, 0),
1753                            TREE_OPERAND (cond, 1)),
1754                    boolean_true_node,
1755                    block_avail_exprs_p);
1756       record_cond (build2 (UNLT_EXPR, boolean_type_node,
1757                            TREE_OPERAND (cond, 0),
1758                            TREE_OPERAND (cond, 1)),
1759                    boolean_true_node,
1760                    block_avail_exprs_p);
1761       record_cond (build2 (UNGT_EXPR, boolean_type_node,
1762                            TREE_OPERAND (cond, 0),
1763                            TREE_OPERAND (cond, 1)),
1764                    boolean_true_node,
1765                    block_avail_exprs_p);
1766       break;
1767
1768     case UNLT_EXPR:
1769       record_cond (build2 (UNLE_EXPR, boolean_type_node,
1770                            TREE_OPERAND (cond, 0),
1771                            TREE_OPERAND (cond, 1)),
1772                    boolean_true_node,
1773                    block_avail_exprs_p);
1774       record_cond (build2 (NE_EXPR, boolean_type_node,
1775                            TREE_OPERAND (cond, 0),
1776                            TREE_OPERAND (cond, 1)),
1777                    boolean_true_node,
1778                    block_avail_exprs_p);
1779       break;
1780
1781     case UNGT_EXPR:
1782       record_cond (build2 (UNGE_EXPR, boolean_type_node,
1783                            TREE_OPERAND (cond, 0),
1784                            TREE_OPERAND (cond, 1)),
1785                    boolean_true_node,
1786                    block_avail_exprs_p);
1787       record_cond (build2 (NE_EXPR, boolean_type_node,
1788                            TREE_OPERAND (cond, 0),
1789                            TREE_OPERAND (cond, 1)),
1790                    boolean_true_node,
1791                    block_avail_exprs_p);
1792       break;
1793
1794     case UNEQ_EXPR:
1795       record_cond (build2 (UNLE_EXPR, boolean_type_node,
1796                            TREE_OPERAND (cond, 0),
1797                            TREE_OPERAND (cond, 1)),
1798                    boolean_true_node,
1799                    block_avail_exprs_p);
1800       record_cond (build2 (UNGE_EXPR, boolean_type_node,
1801                            TREE_OPERAND (cond, 0),
1802                            TREE_OPERAND (cond, 1)),
1803                    boolean_true_node,
1804                    block_avail_exprs_p);
1805       break;
1806
1807     case LTGT_EXPR:
1808       record_cond (build2 (NE_EXPR, boolean_type_node,
1809                            TREE_OPERAND (cond, 0),
1810                            TREE_OPERAND (cond, 1)),
1811                    boolean_true_node,
1812                    block_avail_exprs_p);
1813       record_cond (build2 (ORDERED_EXPR, boolean_type_node,
1814                            TREE_OPERAND (cond, 0),
1815                            TREE_OPERAND (cond, 1)),
1816                    boolean_true_node,
1817                    block_avail_exprs_p);
1818
1819     default:
1820       break;
1821     }
1822 }
1823
1824 /* A helper function for record_const_or_copy and record_equality.
1825    Do the work of recording the value and undo info.  */
1826
1827 static void
1828 record_const_or_copy_1 (tree x, tree y, tree prev_x,
1829                         varray_type *block_const_and_copies_p)
1830 {
1831   set_value_for (x, y, const_and_copies);
1832
1833   if (!*block_const_and_copies_p)
1834     VARRAY_TREE_INIT (*block_const_and_copies_p, 2, "block_const_and_copies");
1835   VARRAY_PUSH_TREE (*block_const_and_copies_p, x);
1836   VARRAY_PUSH_TREE (*block_const_and_copies_p, prev_x);
1837 }
1838
1839 /* Record that X is equal to Y in const_and_copies.  Record undo
1840    information in the block-local varray.  */
1841
1842 static void
1843 record_const_or_copy (tree x, tree y, varray_type *block_const_and_copies_p)
1844 {
1845   tree prev_x = get_value_for (x, const_and_copies);
1846
1847   if (TREE_CODE (y) == SSA_NAME)
1848     {
1849       tree tmp = get_value_for (y, const_and_copies);
1850       if (tmp)
1851         y = tmp;
1852     }
1853
1854   record_const_or_copy_1 (x, y, prev_x, block_const_and_copies_p);
1855 }
1856
1857 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR.
1858    This constrains the cases in which we may treat this as assignment.  */
1859
1860 static void
1861 record_equality (tree x, tree y, varray_type *block_const_and_copies_p)
1862 {
1863   tree prev_x = NULL, prev_y = NULL;
1864
1865   if (TREE_CODE (x) == SSA_NAME)
1866     prev_x = get_value_for (x, const_and_copies);
1867   if (TREE_CODE (y) == SSA_NAME)
1868     prev_y = get_value_for (y, const_and_copies);
1869
1870   /* If one of the previous values is invariant, then use that.
1871      Otherwise it doesn't matter which value we choose, just so
1872      long as we canonicalize on one value.  */
1873   if (TREE_INVARIANT (y))
1874     ;
1875   else if (TREE_INVARIANT (x))
1876     prev_x = x, x = y, y = prev_x, prev_x = prev_y;
1877   else if (prev_x && TREE_INVARIANT (prev_x))
1878     x = y, y = prev_x, prev_x = prev_y;
1879   else if (prev_y)
1880     y = prev_y;
1881
1882   /* After the swapping, we must have one SSA_NAME.  */
1883   if (TREE_CODE (x) != SSA_NAME)
1884     return;
1885
1886   /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a
1887      variable compared against zero.  If we're honoring signed zeros,
1888      then we cannot record this value unless we know that the value is
1889      nonzero.  */
1890   if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x)))
1891       && (TREE_CODE (y) != REAL_CST
1892           || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y))))
1893     return;
1894
1895   record_const_or_copy_1 (x, y, prev_x, block_const_and_copies_p);
1896 }
1897
1898 /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
1899    hash tables.  Try to simplify the RHS using whatever equivalences
1900    we may have recorded.
1901
1902    If we are able to simplify the RHS, then lookup the simplified form in
1903    the hash table and return the result.  Otherwise return NULL.  */
1904
1905 static tree
1906 simplify_rhs_and_lookup_avail_expr (struct dom_walk_data *walk_data,
1907                                     tree stmt,
1908                                     stmt_ann_t ann,
1909                                     int insert)
1910 {
1911   tree rhs = TREE_OPERAND (stmt, 1);
1912   enum tree_code rhs_code = TREE_CODE (rhs);
1913   tree result = NULL;
1914   struct dom_walk_block_data *bd
1915     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
1916
1917   /* If we have lhs = ~x, look and see if we earlier had x = ~y.
1918      In which case we can change this statement to be lhs = y.
1919      Which can then be copy propagated.
1920
1921      Similarly for negation.  */
1922   if ((rhs_code == BIT_NOT_EXPR || rhs_code == NEGATE_EXPR)
1923       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME)
1924     {
1925       /* Get the definition statement for our RHS.  */
1926       tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
1927
1928       /* See if the RHS_DEF_STMT has the same form as our statement.  */
1929       if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR
1930           && TREE_CODE (TREE_OPERAND (rhs_def_stmt, 1)) == rhs_code)
1931         {
1932           tree rhs_def_operand;
1933
1934           rhs_def_operand = TREE_OPERAND (TREE_OPERAND (rhs_def_stmt, 1), 0);
1935
1936           /* Verify that RHS_DEF_OPERAND is a suitable SSA variable.  */
1937           if (TREE_CODE (rhs_def_operand) == SSA_NAME
1938               && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1939             result = update_rhs_and_lookup_avail_expr (stmt,
1940                                                        rhs_def_operand,
1941                                                        &bd->avail_exprs,
1942                                                        ann,
1943                                                        insert);
1944         }
1945     }
1946
1947   /* If we have z = (x OP C1), see if we earlier had x = y OP C2.
1948      If OP is associative, create and fold (y OP C2) OP C1 which
1949      should result in (y OP C3), use that as the RHS for the
1950      assignment.  Add minus to this, as we handle it specially below.  */
1951   if ((associative_tree_code (rhs_code) || rhs_code == MINUS_EXPR)
1952       && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
1953       && is_gimple_min_invariant (TREE_OPERAND (rhs, 1)))
1954     {
1955       tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
1956
1957       /* See if the RHS_DEF_STMT has the same form as our statement.  */
1958       if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR)
1959         {
1960           tree rhs_def_rhs = TREE_OPERAND (rhs_def_stmt, 1);
1961           enum tree_code rhs_def_code = TREE_CODE (rhs_def_rhs);
1962
1963           if (rhs_code == rhs_def_code
1964               || (rhs_code == PLUS_EXPR && rhs_def_code == MINUS_EXPR)
1965               || (rhs_code == MINUS_EXPR && rhs_def_code == PLUS_EXPR))
1966             {
1967               tree def_stmt_op0 = TREE_OPERAND (rhs_def_rhs, 0);
1968               tree def_stmt_op1 = TREE_OPERAND (rhs_def_rhs, 1);
1969
1970               if (TREE_CODE (def_stmt_op0) == SSA_NAME
1971                   && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_stmt_op0)
1972                   && is_gimple_min_invariant (def_stmt_op1))
1973                 {
1974                   tree outer_const = TREE_OPERAND (rhs, 1);
1975                   tree type = TREE_TYPE (TREE_OPERAND (stmt, 0));
1976                   tree t;
1977
1978                   /* If we care about correct floating point results, then
1979                      don't fold x + c1 - c2.  Note that we need to take both
1980                      the codes and the signs to figure this out.  */
1981                   if (FLOAT_TYPE_P (type)
1982                       && !flag_unsafe_math_optimizations
1983                       && (rhs_def_code == PLUS_EXPR
1984                           || rhs_def_code == MINUS_EXPR))
1985                     {
1986                       bool neg = false;
1987
1988                       neg ^= (rhs_code == MINUS_EXPR);
1989                       neg ^= (rhs_def_code == MINUS_EXPR);
1990                       neg ^= real_isneg (TREE_REAL_CST_PTR (outer_const));
1991                       neg ^= real_isneg (TREE_REAL_CST_PTR (def_stmt_op1));
1992
1993                       if (neg)
1994                         goto dont_fold_assoc;
1995                     }
1996
1997                   /* Ho hum.  So fold will only operate on the outermost
1998                      thingy that we give it, so we have to build the new
1999                      expression in two pieces.  This requires that we handle
2000                      combinations of plus and minus.  */
2001                   if (rhs_def_code != rhs_code)
2002                     {
2003                       if (rhs_def_code == MINUS_EXPR)
2004                         t = build (MINUS_EXPR, type, outer_const, def_stmt_op1);
2005                       else
2006                         t = build (MINUS_EXPR, type, def_stmt_op1, outer_const);
2007                       rhs_code = PLUS_EXPR;
2008                     }
2009                   else if (rhs_def_code == MINUS_EXPR)
2010                     t = build (PLUS_EXPR, type, def_stmt_op1, outer_const);
2011                   else
2012                     t = build (rhs_def_code, type, def_stmt_op1, outer_const);
2013                   t = local_fold (t);
2014                   t = build (rhs_code, type, def_stmt_op0, t);
2015                   t = local_fold (t);
2016
2017                   /* If the result is a suitable looking gimple expression,
2018                      then use it instead of the original for STMT.  */
2019                   if (TREE_CODE (t) == SSA_NAME
2020                       || (TREE_CODE_CLASS (TREE_CODE (t)) == '1'
2021                           && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
2022                       || ((TREE_CODE_CLASS (TREE_CODE (t)) == '2'
2023                            || TREE_CODE_CLASS (TREE_CODE (t)) == '<')
2024                           && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
2025                           && is_gimple_val (TREE_OPERAND (t, 1))))
2026                     result = update_rhs_and_lookup_avail_expr
2027                       (stmt, t, &bd->avail_exprs, ann, insert);
2028                 }
2029             }
2030         }
2031  dont_fold_assoc:;
2032     }
2033
2034   /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
2035      and BIT_AND_EXPR respectively if the first operand is greater
2036      than zero and the second operand is an exact power of two.  */
2037   if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
2038       && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
2039       && integer_pow2p (TREE_OPERAND (rhs, 1)))
2040     {
2041       tree val;
2042       tree op = TREE_OPERAND (rhs, 0);
2043
2044       if (TYPE_UNSIGNED (TREE_TYPE (op)))
2045         {
2046           val = integer_one_node;
2047         }
2048       else
2049         {
2050           tree dummy_cond = walk_data->global_data;
2051
2052           if (! dummy_cond)
2053             {
2054               dummy_cond = build (GT_EXPR, boolean_type_node,
2055                                   op, integer_zero_node);
2056               dummy_cond = build (COND_EXPR, void_type_node,
2057                                   dummy_cond, NULL, NULL);
2058               walk_data->global_data = dummy_cond;
2059             }
2060           else
2061             {
2062               TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GT_EXPR);
2063               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
2064               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
2065                 = integer_zero_node;
2066             }
2067           val = simplify_cond_and_lookup_avail_expr (dummy_cond,
2068                                                      &bd->avail_exprs,
2069                                                      NULL, false);
2070         }
2071
2072       if (val && integer_onep (val))
2073         {
2074           tree t;
2075           tree op0 = TREE_OPERAND (rhs, 0);
2076           tree op1 = TREE_OPERAND (rhs, 1);
2077
2078           if (rhs_code == TRUNC_DIV_EXPR)
2079             t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0,
2080                        build_int_2 (tree_log2 (op1), 0));
2081           else
2082             t = build (BIT_AND_EXPR, TREE_TYPE (op0), op0,
2083                        local_fold (build (MINUS_EXPR, TREE_TYPE (op1),
2084                                           op1, integer_one_node)));
2085
2086           result = update_rhs_and_lookup_avail_expr (stmt, t,
2087                                                      &bd->avail_exprs,
2088                                                      ann, insert);
2089         }
2090     }
2091
2092   /* Transform ABS (X) into X or -X as appropriate.  */
2093   if (rhs_code == ABS_EXPR
2094       && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
2095     {
2096       tree val;
2097       tree op = TREE_OPERAND (rhs, 0);
2098       tree type = TREE_TYPE (op);
2099
2100       if (TYPE_UNSIGNED (type))
2101         {
2102           val = integer_zero_node;
2103         }
2104       else
2105         {
2106           tree dummy_cond = walk_data->global_data;
2107
2108           if (! dummy_cond)
2109             {
2110               dummy_cond = build (LE_EXPR, boolean_type_node,
2111                                   op, integer_zero_node);
2112               dummy_cond = build (COND_EXPR, void_type_node,
2113                                   dummy_cond, NULL, NULL);
2114               walk_data->global_data = dummy_cond;
2115             }
2116           else
2117             {
2118               TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), LE_EXPR);
2119               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
2120               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
2121                 = fold_convert (type, integer_zero_node);
2122             }
2123           val = simplify_cond_and_lookup_avail_expr (dummy_cond,
2124                                                      &bd->avail_exprs,
2125                                                      NULL, false);
2126
2127           if (!val)
2128             {
2129               TREE_SET_CODE (TREE_OPERAND (dummy_cond, 0), GE_EXPR);
2130               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 0) = op;
2131               TREE_OPERAND (TREE_OPERAND (dummy_cond, 0), 1)
2132                 = fold_convert (type, integer_zero_node);
2133
2134               val = simplify_cond_and_lookup_avail_expr (dummy_cond,
2135                                                          &bd->avail_exprs,
2136                                                          NULL, false);
2137
2138               if (val)
2139                 {
2140                   if (integer_zerop (val))
2141                     val = integer_one_node;
2142                   else if (integer_onep (val))
2143                     val = integer_zero_node;
2144                 }
2145             }
2146         }
2147
2148       if (val
2149           && (integer_onep (val) || integer_zerop (val)))
2150         {
2151           tree t;
2152
2153           if (integer_onep (val))
2154             t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
2155           else
2156             t = op;
2157
2158           result = update_rhs_and_lookup_avail_expr (stmt, t,
2159                                                      &bd->avail_exprs,
2160                                                      ann, insert);
2161         }
2162     }
2163
2164   /* Optimize *"foo" into 'f'.  This is done here rather than
2165      in fold to avoid problems with stuff like &*"foo".  */
2166   if (TREE_CODE (rhs) == INDIRECT_REF || TREE_CODE (rhs) == ARRAY_REF)
2167     {
2168       tree t = fold_read_from_constant_string (rhs);
2169
2170       if (t)
2171         result = update_rhs_and_lookup_avail_expr (stmt, t,
2172                                                    &bd->avail_exprs,
2173                                                    ann, insert);
2174     }
2175
2176   return result;
2177 }
2178
2179 /* COND is a condition of the form:
2180
2181      x == const or x != const
2182
2183    Look back to x's defining statement and see if x is defined as
2184
2185      x = (type) y;
2186
2187    If const is unchanged if we convert it to type, then we can build
2188    the equivalent expression:
2189
2190
2191       y == const or y != const
2192
2193    Which may allow further optimizations.
2194
2195    Return the equivalent comparison or NULL if no such equivalent comparison
2196    was found.  */
2197
2198 static tree
2199 find_equivalent_equality_comparison (tree cond)
2200 {
2201   tree op0 = TREE_OPERAND (cond, 0);
2202   tree op1 = TREE_OPERAND (cond, 1);
2203   tree def_stmt = SSA_NAME_DEF_STMT (op0);
2204
2205   /* OP0 might have been a parameter, so first make sure it
2206      was defined by a MODIFY_EXPR.  */
2207   if (def_stmt && TREE_CODE (def_stmt) == MODIFY_EXPR)
2208     {
2209       tree def_rhs = TREE_OPERAND (def_stmt, 1);
2210
2211       /* Now make sure the RHS of the MODIFY_EXPR is a typecast.  */
2212       if ((TREE_CODE (def_rhs) == NOP_EXPR
2213            || TREE_CODE (def_rhs) == CONVERT_EXPR)
2214           && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME)
2215         {
2216           tree def_rhs_inner = TREE_OPERAND (def_rhs, 0);
2217           tree def_rhs_inner_type = TREE_TYPE (def_rhs_inner);
2218           tree new;
2219
2220           if (TYPE_PRECISION (def_rhs_inner_type)
2221               > TYPE_PRECISION (TREE_TYPE (def_rhs)))
2222             return NULL;
2223
2224           /* What we want to prove is that if we convert OP1 to
2225              the type of the object inside the NOP_EXPR that the
2226              result is still equivalent to SRC.
2227
2228              If that is true, the build and return new equivalent
2229              condition which uses the source of the typecast and the
2230              new constant (which has only changed its type).  */
2231           new = build1 (TREE_CODE (def_rhs), def_rhs_inner_type, op1);
2232           new = local_fold (new);
2233           if (is_gimple_val (new) && tree_int_cst_equal (new, op1))
2234             return build (TREE_CODE (cond), TREE_TYPE (cond),
2235                           def_rhs_inner, new);
2236         }
2237     }
2238   return NULL;
2239 }
2240
2241 /* STMT is a COND_EXPR for which we could not trivially determine its
2242    result.  This routine attempts to find equivalent forms of the
2243    condition which we may be able to optimize better.  It also
2244    uses simple value range propagation to optimize conditionals.  */
2245
2246 static tree
2247 simplify_cond_and_lookup_avail_expr (tree stmt,
2248                                      varray_type *block_avail_exprs_p,
2249                                      stmt_ann_t ann,
2250                                      int insert)
2251 {
2252   tree cond = COND_EXPR_COND (stmt);
2253
2254   if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
2255     {
2256       tree op0 = TREE_OPERAND (cond, 0);
2257       tree op1 = TREE_OPERAND (cond, 1);
2258
2259       if (TREE_CODE (op0) == SSA_NAME && is_gimple_min_invariant (op1))
2260         {
2261           int limit;
2262           tree low, high, cond_low, cond_high;
2263           int lowequal, highequal, swapped, no_overlap, subset, cond_inverted;
2264           varray_type vrp_records;
2265           struct vrp_element *element;
2266
2267           /* First see if we have test of an SSA_NAME against a constant
2268              where the SSA_NAME is defined by an earlier typecast which
2269              is irrelevant when performing tests against the given
2270              constant.  */
2271           if (TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
2272             {
2273               tree new_cond = find_equivalent_equality_comparison (cond);
2274
2275               if (new_cond)
2276                 {
2277                   /* Update the statement to use the new equivalent
2278                      condition.  */
2279                   COND_EXPR_COND (stmt) = new_cond;
2280                   ann->modified = 1;
2281
2282                   /* Lookup the condition and return its known value if it
2283                      exists.  */
2284                   new_cond = lookup_avail_expr (stmt, block_avail_exprs_p,
2285                                                 insert);
2286                   if (new_cond)
2287                     return new_cond;
2288
2289                   /* The operands have changed, so update op0 and op1.  */
2290                   op0 = TREE_OPERAND (cond, 0);
2291                   op1 = TREE_OPERAND (cond, 1);
2292                 }
2293             }
2294
2295           /* Consult the value range records for this variable (if they exist)
2296              to see if we can eliminate or simplify this conditional.
2297
2298              Note two tests are necessary to determine no records exist.
2299              First we have to see if the virtual array exists, if it
2300              exists, then we have to check its active size.
2301
2302              Also note the vast majority of conditionals are not testing
2303              a variable which has had its range constrained by an earlier
2304              conditional.  So this filter avoids a lot of unnecessary work.  */
2305           vrp_records = VARRAY_GENERIC_PTR (vrp_data, SSA_NAME_VERSION (op0));
2306           if (vrp_records == NULL)
2307             return NULL;
2308
2309           limit = VARRAY_ACTIVE_SIZE (vrp_records);
2310
2311           /* If we have no value range records for this variable, or we are
2312              unable to extract a range for this condition, then there is
2313              nothing to do.  */
2314           if (limit == 0
2315               || ! extract_range_from_cond (cond, &cond_high,
2316                                             &cond_low, &cond_inverted))
2317             return NULL;
2318
2319           /* We really want to avoid unnecessary computations of range
2320              info.  So all ranges are computed lazily; this avoids a
2321              lot of unnecessary work.  ie, we record the conditional,
2322              but do not process how it constrains the variable's
2323              potential values until we know that processing the condition
2324              could be helpful.
2325
2326              However, we do not want to have to walk a potentially long
2327              list of ranges, nor do we want to compute a variable's
2328              range more than once for a given path.
2329
2330              Luckily, each time we encounter a conditional that can not
2331              be otherwise optimized we will end up here and we will
2332              compute the necessary range information for the variable
2333              used in this condition.
2334
2335              Thus you can conclude that there will never be more than one
2336              conditional associated with a variable which has not been
2337              processed.  So we never need to merge more than one new
2338              conditional into the current range.
2339
2340              These properties also help us avoid unnecessary work.  */
2341            element
2342              = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records, limit - 1);
2343
2344           if (element->high && element->low)
2345             {
2346               /* The last element has been processed, so there is no range
2347                  merging to do, we can simply use the high/low values
2348                  recorded in the last element.  */
2349               low = element->low;
2350               high = element->high;
2351             }
2352           else
2353             {
2354               tree tmp_high, tmp_low;
2355               int dummy;
2356
2357               /* The last element has not been processed.  Process it now.  */
2358               extract_range_from_cond (element->cond, &tmp_high,
2359                                        &tmp_low, &dummy);
2360
2361               /* If this is the only element, then no merging is necessary,
2362                  the high/low values from extract_range_from_cond are all
2363                  we need.  */
2364               if (limit == 1)
2365                 {
2366                   low = tmp_low;
2367                   high = tmp_high;
2368                 }
2369               else
2370                 {
2371                   /* Get the high/low value from the previous element.  */
2372                   struct vrp_element *prev
2373                     = (struct vrp_element *)VARRAY_GENERIC_PTR (vrp_records,
2374                                                                 limit - 2);
2375                   low = prev->low;
2376                   high = prev->high;
2377
2378                   /* Merge in this element's range with the range from the
2379                      previous element.
2380
2381                      The low value for the merged range is the maximum of
2382                      the previous low value and the low value of this record.
2383
2384                      Similarly the high value for the merged range is the
2385                      minimum of the previous high value and the high value of
2386                      this record.  */
2387                   low = (tree_int_cst_compare (low, tmp_low) == 1
2388                          ? low : tmp_low);
2389                   high = (tree_int_cst_compare (high, tmp_high) == -1
2390                           ? high : tmp_high);
2391                 }
2392
2393               /* And record the computed range.  */
2394               element->low = low;
2395               element->high = high;
2396
2397             }
2398
2399           /* After we have constrained this variable's potential values,
2400              we try to determine the result of the given conditional.
2401
2402              To simplify later tests, first determine if the current
2403              low value is the same low value as the conditional.
2404              Similarly for the current high value and the high value
2405              for the conditional.  */
2406           lowequal = tree_int_cst_equal (low, cond_low);
2407           highequal = tree_int_cst_equal (high, cond_high);
2408
2409           if (lowequal && highequal)
2410             return (cond_inverted ? boolean_false_node : boolean_true_node);
2411
2412           /* To simplify the overlap/subset tests below we may want
2413              to swap the two ranges so that the larger of the two
2414              ranges occurs "first".  */
2415           swapped = 0;
2416           if (tree_int_cst_compare (low, cond_low) == 1
2417               || (lowequal
2418                   && tree_int_cst_compare (cond_high, high) == 1))
2419             {
2420               tree temp;
2421
2422               swapped = 1;
2423               temp = low;
2424               low = cond_low;
2425               cond_low = temp;
2426               temp = high;
2427               high = cond_high;
2428               cond_high = temp;
2429             }
2430
2431           /* Now determine if there is no overlap in the ranges
2432              or if the second range is a subset of the first range.  */
2433           no_overlap = tree_int_cst_lt (high, cond_low);
2434           subset = tree_int_cst_compare (cond_high, high) != 1;
2435
2436           /* If there was no overlap in the ranges, then this conditional
2437              always has a false value (unless we had to invert this
2438              conditional, in which case it always has a true value).  */
2439           if (no_overlap)
2440             return (cond_inverted ? boolean_true_node : boolean_false_node);
2441
2442           /* If the current range is a subset of the condition's range,
2443              then this conditional always has a true value (unless we
2444              had to invert this conditional, in which case it always
2445              has a true value).  */
2446           if (subset && swapped)
2447             return (cond_inverted ? boolean_false_node : boolean_true_node);
2448
2449           /* We were unable to determine the result of the conditional.
2450              However, we may be able to simplify the conditional.  First
2451              merge the ranges in the same manner as range merging above.  */
2452           low = tree_int_cst_compare (low, cond_low) == 1 ? low : cond_low;
2453           high = tree_int_cst_compare (high, cond_high) == -1 ? high : cond_high;
2454
2455           /* If the range has converged to a single point, then turn this
2456              into an equality comparison.  */
2457           if (TREE_CODE (cond) != EQ_EXPR
2458               && TREE_CODE (cond) != NE_EXPR
2459               && tree_int_cst_equal (low, high))
2460             {
2461               TREE_SET_CODE (cond, EQ_EXPR);
2462               TREE_OPERAND (cond, 1) = high;
2463             }
2464         }
2465     }
2466   return 0;
2467 }
2468
2469 /* STMT is a SWITCH_EXPR for which we could not trivially determine its
2470    result.  This routine attempts to find equivalent forms of the
2471    condition which we may be able to optimize better.  */
2472
2473 static tree
2474 simplify_switch_and_lookup_avail_expr (tree stmt,
2475                                        varray_type *block_avail_exprs_p,
2476                                        stmt_ann_t ann,
2477                                        int insert)
2478 {
2479   tree cond = SWITCH_COND (stmt);
2480   tree def, to, ti;
2481
2482   /* The optimization that we really care about is removing unnecessary
2483      casts.  That will let us do much better in propagating the inferred
2484      constant at the switch target.  */
2485   if (TREE_CODE (cond) == SSA_NAME)
2486     {
2487       def = SSA_NAME_DEF_STMT (cond);
2488       if (TREE_CODE (def) == MODIFY_EXPR)
2489         {
2490           def = TREE_OPERAND (def, 1);
2491           if (TREE_CODE (def) == NOP_EXPR)
2492             {
2493               int need_precision;
2494               bool fail;
2495
2496               def = TREE_OPERAND (def, 0);
2497
2498 #ifdef ENABLE_CHECKING
2499               /* ??? Why was Jeff testing this?  We are gimple...  */
2500               if (!is_gimple_val (def))
2501                 abort ();
2502 #endif
2503
2504               to = TREE_TYPE (cond);
2505               ti = TREE_TYPE (def);
2506
2507               /* If we have an extension that preserves value, then we
2508                  can copy the source value into the switch.  */
2509
2510               need_precision = TYPE_PRECISION (ti);
2511               fail = false;
2512               if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
2513                 fail = true;
2514               else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
2515                 need_precision += 1;
2516               if (TYPE_PRECISION (to) < need_precision)
2517                 fail = true;
2518
2519               if (!fail)
2520                 {
2521                   SWITCH_COND (stmt) = def;
2522                   ann->modified = 1;
2523
2524                   return lookup_avail_expr (stmt, block_avail_exprs_p, insert);
2525                 }
2526             }
2527         }
2528     }
2529
2530   return 0;
2531 }
2532
2533
2534 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
2535    known value for that SSA_NAME (or NULL if no value is known).
2536
2537    NONZERO_VARS is the set SSA_NAMES known to have a nonzero value,
2538    even if we don't know their precise value.
2539
2540    Propagate values from CONST_AND_COPIES and NONZERO_VARS into the PHI
2541    nodes of the successors of BB.  */
2542
2543 static void
2544 cprop_into_successor_phis (basic_block bb,
2545                            varray_type const_and_copies,
2546                            bitmap nonzero_vars)
2547 {
2548   edge e;
2549
2550   /* This can get rather expensive if the implementation is naive in
2551      how it finds the phi alternative associated with a particular edge.  */
2552
2553   FOR_EACH_EDGE (e, bb->succs)
2554     {
2555       tree phi;
2556       int phi_num_args;
2557       int hint;
2558
2559       /* If this is an abnormal edge, then we do not want to copy propagate
2560          into the PHI alternative associated with this edge.  */
2561       if (e->flags & EDGE_ABNORMAL)
2562         continue;
2563
2564       phi = phi_nodes (e->dest);
2565       if (! phi)
2566         continue;
2567
2568       /* There is no guarantee that for any two PHI nodes in a block that
2569          the phi alternative associated with a particular edge will be
2570          at the same index in the phi alternative array.
2571
2572          However, it is very likely they will be the same.  So we keep
2573          track of the index of the alternative where we found the edge in
2574          the previous phi node and check that index first in the next
2575          phi node.  If that hint fails, then we actually search all
2576          the entries.  */
2577       phi_num_args = PHI_NUM_ARGS (phi);
2578       hint = phi_num_args;
2579       for ( ; phi; phi = PHI_CHAIN (phi))
2580         {
2581           int i;
2582           tree new;
2583           use_operand_p orig_p;
2584           tree orig;
2585
2586           /* If the hint is valid (!= phi_num_args), see if it points
2587              us to the desired phi alternative.  */
2588           if (hint != phi_num_args && PHI_ARG_EDGE (phi, hint) == e)
2589             ;
2590           else
2591             {
2592               /* The hint was either invalid or did not point to the
2593                  correct phi alternative.  Search all the alternatives
2594                  for the correct one.  Update the hint.  */
2595               for (i = 0; i < phi_num_args; i++)
2596                 if (PHI_ARG_EDGE (phi, i) == e)
2597                   break;
2598               hint = i;
2599             }
2600
2601 #ifdef ENABLE_CHECKING
2602           /* If we did not find the proper alternative, then something is
2603              horribly wrong.  */
2604           if (hint == phi_num_args)
2605             abort ();
2606 #endif
2607
2608           /* The alternative may be associated with a constant, so verify
2609              it is an SSA_NAME before doing anything with it.  */
2610           orig_p = PHI_ARG_DEF_PTR (phi, hint);
2611           orig = USE_FROM_PTR (orig_p);
2612           if (TREE_CODE (orig) != SSA_NAME)
2613             continue;
2614
2615           /* If the alternative is known to have a nonzero value, record
2616              that fact in the PHI node itself for future use.  */
2617           if (bitmap_bit_p (nonzero_vars, SSA_NAME_VERSION (orig)))
2618             PHI_ARG_NONZERO (phi, hint) = true;
2619
2620           /* If we have *ORIG_P in our constant/copy table, then replace
2621              ORIG_P with its value in our constant/copy table.  */
2622           new = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (orig));
2623           if (new
2624               && (TREE_CODE (new) == SSA_NAME
2625                   || is_gimple_min_invariant (new))
2626               && may_propagate_copy (orig, new))
2627             {
2628               propagate_value (orig_p, new);
2629             }
2630         }
2631     }
2632   END_FOR_EACH_EDGE;
2633 }
2634
2635
2636 /* Propagate known constants/copies into PHI nodes of BB's successor
2637    blocks.  */
2638
2639 static void
2640 cprop_into_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
2641                  basic_block bb)
2642 {
2643   cprop_into_successor_phis (bb, const_and_copies, nonzero_vars);
2644 }
2645
2646 /* Search for redundant computations in STMT.  If any are found, then
2647    replace them with the variable holding the result of the computation.
2648
2649    If safe, record this expression into the available expression hash
2650    table.  */
2651
2652 static bool
2653 eliminate_redundant_computations (struct dom_walk_data *walk_data,
2654                                   tree stmt, stmt_ann_t ann)
2655 {
2656   v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
2657   tree *expr_p, def = NULL_TREE;
2658   bool insert = true;
2659   tree cached_lhs;
2660   bool retval = false;
2661   struct dom_walk_block_data *bd
2662     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
2663
2664   if (TREE_CODE (stmt) == MODIFY_EXPR)
2665     def = TREE_OPERAND (stmt, 0);
2666
2667   /* Certain expressions on the RHS can be optimized away, but can not
2668      themselves be entered into the hash tables.   */
2669   if (ann->makes_aliased_stores
2670       || ! def
2671       || TREE_CODE (def) != SSA_NAME
2672       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
2673       || NUM_V_MAY_DEFS (v_may_defs) != 0)
2674     insert = false;
2675
2676   /* Check if the expression has been computed before.  */
2677   cached_lhs = lookup_avail_expr (stmt, &bd->avail_exprs, insert);
2678
2679   /* If this is an assignment and the RHS was not in the hash table,
2680      then try to simplify the RHS and lookup the new RHS in the
2681      hash table.  */
2682   if (! cached_lhs && TREE_CODE (stmt) == MODIFY_EXPR)
2683     cached_lhs = simplify_rhs_and_lookup_avail_expr (walk_data,
2684                                                      stmt,
2685                                                      ann,
2686                                                      insert);
2687   /* Similarly if this is a COND_EXPR and we did not find its
2688      expression in the hash table, simplify the condition and
2689      try again.  */
2690   else if (! cached_lhs && TREE_CODE (stmt) == COND_EXPR)
2691     cached_lhs = simplify_cond_and_lookup_avail_expr (stmt,
2692                                                       &bd->avail_exprs,
2693                                                       ann,
2694                                                       insert);
2695   /* Similarly for a SWITCH_EXPR.  */
2696   else if (!cached_lhs && TREE_CODE (stmt) == SWITCH_EXPR)
2697     cached_lhs = simplify_switch_and_lookup_avail_expr (stmt,
2698                                                         &bd->avail_exprs,
2699                                                         ann,
2700                                                         insert);
2701
2702   opt_stats.num_exprs_considered++;
2703
2704   /* Get a pointer to the expression we are trying to optimize.  */
2705   if (TREE_CODE (stmt) == COND_EXPR)
2706     expr_p = &COND_EXPR_COND (stmt);
2707   else if (TREE_CODE (stmt) == SWITCH_EXPR)
2708     expr_p = &SWITCH_COND (stmt);
2709   else if (TREE_CODE (stmt) == RETURN_EXPR && TREE_OPERAND (stmt, 0))
2710     expr_p = &TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
2711   else
2712     expr_p = &TREE_OPERAND (stmt, 1);
2713
2714   /* It is safe to ignore types here since we have already done
2715      type checking in the hashing and equality routines.  In fact
2716      type checking here merely gets in the way of constant
2717      propagation.  Also, make sure that it is safe to propagate
2718      CACHED_LHS into *EXPR_P.  */
2719   if (cached_lhs
2720       && (TREE_CODE (cached_lhs) != SSA_NAME
2721           || may_propagate_copy (*expr_p, cached_lhs)))
2722     {
2723       if (dump_file && (dump_flags & TDF_DETAILS))
2724         {
2725           fprintf (dump_file, "  Replaced redundant expr '");
2726           print_generic_expr (dump_file, *expr_p, dump_flags);
2727           fprintf (dump_file, "' with '");
2728           print_generic_expr (dump_file, cached_lhs, dump_flags);
2729            fprintf (dump_file, "'\n");
2730         }
2731
2732       opt_stats.num_re++;
2733
2734 #if defined ENABLE_CHECKING
2735       if (TREE_CODE (cached_lhs) != SSA_NAME
2736           && !is_gimple_min_invariant (cached_lhs))
2737         abort ();
2738 #endif
2739
2740       if (TREE_CODE (cached_lhs) == ADDR_EXPR
2741           || (POINTER_TYPE_P (TREE_TYPE (*expr_p))
2742               && is_gimple_min_invariant (cached_lhs)))
2743         retval = true;
2744
2745       propagate_tree_value (expr_p, cached_lhs);
2746       ann->modified = 1;
2747     }
2748   return retval;
2749 }
2750
2751 /* STMT, a MODIFY_EXPR, may create certain equivalences, in either
2752    the available expressions table or the const_and_copies table.
2753    Detect and record those equivalences.  */
2754
2755 static void
2756 record_equivalences_from_stmt (tree stmt,
2757                                varray_type *block_avail_exprs_p,
2758                                varray_type *block_nonzero_vars_p,
2759                                int may_optimize_p,
2760                                stmt_ann_t ann)
2761 {
2762   tree lhs = TREE_OPERAND (stmt, 0);
2763   enum tree_code lhs_code = TREE_CODE (lhs);
2764   int i;
2765
2766   if (lhs_code == SSA_NAME)
2767     {
2768       tree rhs = TREE_OPERAND (stmt, 1);
2769
2770       /* Strip away any useless type conversions.  */
2771       STRIP_USELESS_TYPE_CONVERSION (rhs);
2772
2773       /* If the RHS of the assignment is a constant or another variable that
2774          may be propagated, register it in the CONST_AND_COPIES table.  We
2775          do not need to record unwind data for this, since this is a true
2776          assignment and not an equivalence inferred from a comparison.  All
2777          uses of this ssa name are dominated by this assignment, so unwinding
2778          just costs time and space.  */
2779       if (may_optimize_p
2780           && (TREE_CODE (rhs) == SSA_NAME
2781               || is_gimple_min_invariant (rhs)))
2782         set_value_for (lhs, rhs, const_and_copies);
2783
2784       /* alloca never returns zero and the address of a non-weak symbol
2785          is never zero.  NOP_EXPRs and CONVERT_EXPRs can be completely
2786          stripped as they do not affect this equivalence.  */
2787       while (TREE_CODE (rhs) == NOP_EXPR
2788              || TREE_CODE (rhs) == CONVERT_EXPR)
2789         rhs = TREE_OPERAND (rhs, 0);
2790
2791       if (alloca_call_p (rhs)
2792           || (TREE_CODE (rhs) == ADDR_EXPR
2793               && DECL_P (TREE_OPERAND (rhs, 0))
2794               && ! DECL_WEAK (TREE_OPERAND (rhs, 0))))
2795         record_var_is_nonzero (lhs, block_nonzero_vars_p);
2796
2797       /* IOR of any value with a nonzero value will result in a nonzero
2798          value.  Even if we do not know the exact result recording that
2799          the result is nonzero is worth the effort.  */
2800       if (TREE_CODE (rhs) == BIT_IOR_EXPR
2801           && integer_nonzerop (TREE_OPERAND (rhs, 1)))
2802         record_var_is_nonzero (lhs, block_nonzero_vars_p);
2803     }
2804
2805   /* Look at both sides for pointer dereferences.  If we find one, then
2806      the pointer must be nonnull and we can enter that equivalence into
2807      the hash tables.  */
2808   if (flag_delete_null_pointer_checks)
2809     for (i = 0; i < 2; i++)
2810       {
2811         tree t = TREE_OPERAND (stmt, i);
2812
2813         /* Strip away any COMPONENT_REFs.  */
2814         while (TREE_CODE (t) == COMPONENT_REF)
2815           t = TREE_OPERAND (t, 0);
2816
2817         /* Now see if this is a pointer dereference.  */
2818         if (TREE_CODE (t) == INDIRECT_REF)
2819           {
2820             tree op = TREE_OPERAND (t, 0);
2821
2822             /* If the pointer is a SSA variable, then enter new
2823                equivalences into the hash table.  */
2824             while (TREE_CODE (op) == SSA_NAME)
2825               {
2826                 tree def = SSA_NAME_DEF_STMT (op);
2827
2828                 record_var_is_nonzero (op, block_nonzero_vars_p);
2829
2830                 /* And walk up the USE-DEF chains noting other SSA_NAMEs
2831                    which are known to have a nonzero value.  */
2832                 if (def
2833                     && TREE_CODE (def) == MODIFY_EXPR
2834                     && TREE_CODE (TREE_OPERAND (def, 1)) == NOP_EXPR)
2835                   op = TREE_OPERAND (TREE_OPERAND (def, 1), 0);
2836                 else
2837                   break;
2838               }
2839           }
2840       }
2841
2842   /* A memory store, even an aliased store, creates a useful
2843      equivalence.  By exchanging the LHS and RHS, creating suitable
2844      vops and recording the result in the available expression table,
2845      we may be able to expose more redundant loads.  */
2846   if (!ann->has_volatile_ops
2847       && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
2848           || is_gimple_min_invariant (TREE_OPERAND (stmt, 1)))
2849       && !is_gimple_reg (lhs))
2850     {
2851       tree rhs = TREE_OPERAND (stmt, 1);
2852       tree new;
2853       size_t j;
2854
2855       /* FIXME: If the LHS of the assignment is a bitfield and the RHS
2856          is a constant, we need to adjust the constant to fit into the
2857          type of the LHS.  If the LHS is a bitfield and the RHS is not
2858          a constant, then we can not record any equivalences for this
2859          statement since we would need to represent the widening or
2860          narrowing of RHS.  This fixes gcc.c-torture/execute/921016-1.c
2861          and should not be necessary if GCC represented bitfields
2862          properly.  */
2863       if (lhs_code == COMPONENT_REF
2864           && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
2865         {
2866           if (TREE_CONSTANT (rhs))
2867             rhs = widen_bitfield (rhs, TREE_OPERAND (lhs, 1), lhs);
2868           else
2869             rhs = NULL;
2870
2871           /* If the value overflowed, then we can not use this equivalence.  */
2872           if (rhs && ! is_gimple_min_invariant (rhs))
2873             rhs = NULL;
2874         }
2875
2876       if (rhs)
2877         {
2878           v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
2879           v_must_def_optype v_must_defs = V_MUST_DEF_OPS (ann);
2880
2881           /* Build a new statement with the RHS and LHS exchanged.  */
2882           new = build (MODIFY_EXPR, TREE_TYPE (stmt), rhs, lhs);
2883
2884           /* Get an annotation and set up the real operands.  */
2885           get_stmt_ann (new);
2886           get_stmt_operands (new);
2887
2888           /* Clear out the virtual operands on the new statement, we are
2889              going to set them explicitly below.  */
2890           remove_vuses (new);
2891           remove_v_may_defs (new);
2892           remove_v_must_defs (new);
2893
2894           start_ssa_stmt_operands (new);
2895           /* For each VDEF on the original statement, we want to create a
2896              VUSE of the V_MAY_DEF result or V_MUST_DEF op on the new
2897              statement.  */
2898           for (j = 0; j < NUM_V_MAY_DEFS (v_may_defs); j++)
2899             {
2900               tree op = V_MAY_DEF_RESULT (v_may_defs, j);
2901               add_vuse (op, new);
2902             }
2903
2904           for (j = 0; j < NUM_V_MUST_DEFS (v_must_defs); j++)
2905             {
2906               tree op = V_MUST_DEF_OP (v_must_defs, j);
2907               add_vuse (op, new);
2908             }
2909
2910           finalize_ssa_stmt_operands (new);
2911
2912           /* Finally enter the statement into the available expression
2913              table.  */
2914           lookup_avail_expr (new, block_avail_exprs_p, true);
2915         }
2916     }
2917 }
2918
2919 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from
2920    CONST_AND_COPIES.  */
2921
2922 static bool
2923 cprop_operand (stmt_ann_t ann, use_operand_p op_p, varray_type const_and_copies)
2924 {
2925   bool may_have_exposed_new_symbols = false;
2926   tree val;
2927   tree op = USE_FROM_PTR (op_p);
2928
2929   /* If the operand has a known constant value or it is known to be a
2930      copy of some other variable, use the value or copy stored in
2931      CONST_AND_COPIES.  */
2932   val = VARRAY_TREE (const_and_copies, SSA_NAME_VERSION (op));
2933   if (val)
2934     {
2935       tree op_type, val_type;
2936
2937       /* Do not change the base variable in the virtual operand
2938          tables.  That would make it impossible to reconstruct
2939          the renamed virtual operand if we later modify this
2940          statement.  Also only allow the new value to be an SSA_NAME
2941          for propagation into virtual operands.  */
2942       if (!is_gimple_reg (op)
2943           && (get_virtual_var (val) != get_virtual_var (op)
2944               || TREE_CODE (val) != SSA_NAME))
2945         return false;
2946
2947       /* Get the toplevel type of each operand.  */
2948       op_type = TREE_TYPE (op);
2949       val_type = TREE_TYPE (val);
2950
2951       /* While both types are pointers, get the type of the object
2952          pointed to.  */
2953       while (POINTER_TYPE_P (op_type) && POINTER_TYPE_P (val_type))
2954         {
2955           op_type = TREE_TYPE (op_type);
2956           val_type = TREE_TYPE (val_type);
2957         }
2958
2959       /* Make sure underlying types match before propagating a constant by
2960          converting the constant to the proper type.  Note that convert may
2961          return a non-gimple expression, in which case we ignore this
2962          propagation opportunity.  */
2963       if (TREE_CODE (val) != SSA_NAME)
2964         {
2965           if (!lang_hooks.types_compatible_p (op_type, val_type))
2966             {
2967               val = fold_convert (TREE_TYPE (op), val);
2968               if (!is_gimple_min_invariant (val))
2969                 return false;
2970             }
2971         }
2972
2973       /* Certain operands are not allowed to be copy propagated due
2974          to their interaction with exception handling and some GCC
2975          extensions.  */
2976       else if (!may_propagate_copy (op, val))
2977         return false;
2978
2979       /* Dump details.  */
2980       if (dump_file && (dump_flags & TDF_DETAILS))
2981         {
2982           fprintf (dump_file, "  Replaced '");
2983           print_generic_expr (dump_file, op, dump_flags);
2984           fprintf (dump_file, "' with %s '",
2985                    (TREE_CODE (val) != SSA_NAME ? "constant" : "variable"));
2986           print_generic_expr (dump_file, val, dump_flags);
2987           fprintf (dump_file, "'\n");
2988         }
2989
2990       /* If VAL is an ADDR_EXPR or a constant of pointer type, note
2991          that we may have exposed a new symbol for SSA renaming.  */
2992       if (TREE_CODE (val) == ADDR_EXPR
2993           || (POINTER_TYPE_P (TREE_TYPE (op))
2994               && is_gimple_min_invariant (val)))
2995         may_have_exposed_new_symbols = true;
2996
2997       propagate_value (op_p, val);
2998
2999       /* And note that we modified this statement.  This is now
3000          safe, even if we changed virtual operands since we will
3001          rescan the statement and rewrite its operands again.  */
3002       ann->modified = 1;
3003     }
3004   return may_have_exposed_new_symbols;
3005 }
3006
3007 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current
3008    known value for that SSA_NAME (or NULL if no value is known).
3009
3010    Propagate values from CONST_AND_COPIES into the uses, vuses and
3011    v_may_def_ops of STMT.  */
3012
3013 static bool
3014 cprop_into_stmt (tree stmt, varray_type const_and_copies)
3015 {
3016   bool may_have_exposed_new_symbols = false;
3017   stmt_ann_t ann = stmt_ann (stmt);
3018   size_t i, num_uses, num_vuses, num_v_may_defs;
3019   vuse_optype vuses;
3020   v_may_def_optype v_may_defs;
3021   use_optype uses;
3022
3023   uses = USE_OPS (ann);
3024   num_uses = NUM_USES (uses);
3025   for (i = 0; i < num_uses; i++)
3026     {
3027       use_operand_p op_p = USE_OP_PTR (uses, i);
3028       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
3029         may_have_exposed_new_symbols
3030           |= cprop_operand (ann, op_p, const_and_copies);
3031     }
3032
3033   vuses = VUSE_OPS (ann);
3034   num_vuses = NUM_VUSES (vuses);
3035   for (i = 0; i < num_vuses; i++)
3036     {
3037       use_operand_p op_p = VUSE_OP_PTR (vuses, i);
3038       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
3039         may_have_exposed_new_symbols
3040           |= cprop_operand (ann, op_p, const_and_copies);
3041     }
3042
3043   v_may_defs = V_MAY_DEF_OPS (ann);
3044   num_v_may_defs = NUM_V_MAY_DEFS (v_may_defs);
3045   for (i = 0; i < num_v_may_defs; i++)
3046     {
3047       use_operand_p op_p = V_MAY_DEF_OP_PTR (v_may_defs, i);
3048       if (TREE_CODE (USE_FROM_PTR (op_p)) == SSA_NAME)
3049         may_have_exposed_new_symbols
3050           |= cprop_operand (ann, op_p, const_and_copies);
3051     }
3052   return may_have_exposed_new_symbols;
3053 }
3054
3055
3056 /* Optimize the statement pointed by iterator SI.
3057
3058    We try to perform some simplistic global redundancy elimination and
3059    constant propagation:
3060
3061    1- To detect global redundancy, we keep track of expressions that have
3062       been computed in this block and its dominators.  If we find that the
3063       same expression is computed more than once, we eliminate repeated
3064       computations by using the target of the first one.
3065
3066    2- Constant values and copy assignments.  This is used to do very
3067       simplistic constant and copy propagation.  When a constant or copy
3068       assignment is found, we map the value on the RHS of the assignment to
3069       the variable in the LHS in the CONST_AND_COPIES table.  */
3070
3071 static void
3072 optimize_stmt (struct dom_walk_data *walk_data, basic_block bb,
3073                block_stmt_iterator si)
3074 {
3075   stmt_ann_t ann;
3076   tree stmt;
3077   bool may_optimize_p;
3078   bool may_have_exposed_new_symbols = false;
3079   struct dom_walk_block_data *bd
3080     = VARRAY_TOP_GENERIC_PTR (walk_data->block_data_stack);
3081
3082   stmt = bsi_stmt (si);
3083
3084   get_stmt_operands (stmt);
3085   ann = stmt_ann (stmt);
3086   opt_stats.num_stmts++;
3087   may_have_exposed_new_symbols = false;
3088
3089   if (dump_file && (dump_flags & TDF_DETAILS))
3090     {
3091       fprintf (dump_file, "Optimizing statement ");
3092       print_generic_stmt (dump_file, stmt, TDF_SLIM);
3093     }
3094
3095   /* Const/copy propagate into USES, VUSES and the RHS of V_MAY_DEFs.  */
3096   may_have_exposed_new_symbols = cprop_into_stmt (stmt, const_and_copies);
3097
3098   /* If the statement has been modified with constant replacements,
3099      fold its RHS before checking for redundant computations.  */
3100   if (ann->modified)
3101     {
3102       /* Try to fold the statement making sure that STMT is kept
3103          up to date.  */
3104       if (fold_stmt (bsi_stmt_ptr (si)))
3105         {
3106           stmt = bsi_stmt (si);
3107           ann = stmt_ann (stmt);
3108
3109           if (dump_file && (dump_flags & TDF_DETAILS))
3110             {
3111               fprintf (dump_file, "  Folded to: ");
3112               print_generic_stmt (dump_file, stmt, TDF_SLIM);
3113             }
3114         }
3115
3116       /* Constant/copy propagation above may change the set of
3117          virtual operands associated with this statement.  Folding
3118          may remove the need for some virtual operands.
3119
3120          Indicate we will need to rescan and rewrite the statement.  */
3121       may_have_exposed_new_symbols = true;
3122     }
3123
3124   /* Check for redundant computations.  Do this optimization only
3125      for assignments that have no volatile ops and conditionals.  */
3126   may_optimize_p = (!ann->has_volatile_ops
3127                     && ((TREE_CODE (stmt) == RETURN_EXPR
3128                          && TREE_OPERAND (stmt, 0)
3129                          && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR
3130                          && ! (TREE_SIDE_EFFECTS
3131                                (TREE_OPERAND (TREE_OPERAND (stmt, 0), 1))))
3132                         || (TREE_CODE (stmt) == MODIFY_EXPR
3133                             && ! TREE_SIDE_EFFECTS (TREE_OPERAND (stmt, 1)))
3134                         || TREE_CODE (stmt) == COND_EXPR
3135                         || TREE_CODE (stmt) == SWITCH_EXPR));
3136
3137   if (may_optimize_p)
3138     may_have_exposed_new_symbols
3139       |= eliminate_redundant_computations (walk_data, stmt, ann);
3140
3141   /* Record any additional equivalences created by this statement.  */
3142   if (TREE_CODE (stmt) == MODIFY_EXPR)
3143     record_equivalences_from_stmt (stmt,
3144                                    &bd->avail_exprs,
3145                                    &bd->nonzero_vars,
3146                                    may_optimize_p,
3147                                    ann);
3148
3149   register_definitions_for_stmt (ann, &bd->block_defs);
3150
3151   /* If STMT is a COND_EXPR and it was modified, then we may know
3152      where it goes.  If that is the case, then mark the CFG as altered.
3153
3154      This will cause us to later call remove_unreachable_blocks and
3155      cleanup_tree_cfg when it is safe to do so.  It is not safe to
3156      clean things up here since removal of edges and such can trigger
3157      the removal of PHI nodes, which in turn can release SSA_NAMEs to
3158      the manager.
3159
3160      That's all fine and good, except that once SSA_NAMEs are released
3161      to the manager, we must not call create_ssa_name until all references
3162      to released SSA_NAMEs have been eliminated.
3163
3164      All references to the deleted SSA_NAMEs can not be eliminated until
3165      we remove unreachable blocks.
3166
3167      We can not remove unreachable blocks until after we have completed
3168      any queued jump threading.
3169
3170      We can not complete any queued jump threads until we have taken
3171      appropriate variables out of SSA form.  Taking variables out of
3172      SSA form can call create_ssa_name and thus we lose.
3173
3174      Ultimately I suspect we're going to need to change the interface
3175      into the SSA_NAME manager.  */
3176
3177   if (ann->modified)
3178     {
3179       tree val = NULL;
3180
3181       if (TREE_CODE (stmt) == COND_EXPR)
3182         val = COND_EXPR_COND (stmt);
3183       else if (TREE_CODE (stmt) == SWITCH_EXPR)
3184         val = SWITCH_COND (stmt);
3185
3186       if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val))
3187         cfg_altered = true;
3188
3189       /* If we simplified a statement in such a way as to be shown that it
3190          cannot trap, update the eh information and the cfg to match.  */
3191       if (maybe_clean_eh_stmt (stmt))
3192         {
3193           bitmap_set_bit (need_eh_cleanup, bb->index);
3194           if (dump_file && (dump_flags & TDF_DETAILS))
3195             fprintf (dump_file, "  Flagged to clear EH edges.\n");
3196         }
3197     }
3198
3199   if (may_have_exposed_new_symbols)
3200     {
3201       if (! bd->stmts_to_rescan)
3202         VARRAY_TREE_INIT (bd->stmts_to_rescan, 20, "stmts_to_rescan");
3203       VARRAY_PUSH_TREE (bd->stmts_to_rescan, bsi_stmt (si));
3204     }
3205 }
3206
3207 /* Replace the RHS of STMT with NEW_RHS.  If RHS can be found in the
3208    available expression hashtable, then return the LHS from the hash
3209    table.
3210
3211    If INSERT is true, then we also update the available expression
3212    hash table to account for the changes made to STMT.  */
3213
3214 static tree
3215 update_rhs_and_lookup_avail_expr (tree stmt, tree new_rhs,
3216                                   varray_type *block_avail_exprs_p,
3217                                   stmt_ann_t ann,
3218                                   bool insert)
3219 {
3220   tree cached_lhs = NULL;
3221
3222   /* Remove the old entry from the hash table.  */
3223   if (insert)
3224     {
3225       struct expr_hash_elt element;
3226
3227       initialize_hash_element (stmt, NULL, &element);
3228       htab_remove_elt_with_hash (avail_exprs, &element, element.hash);
3229     }
3230
3231   /* Now update the RHS of the assignment.  */
3232   TREE_OPERAND (stmt, 1) = new_rhs;
3233
3234   /* Now lookup the updated statement in the hash table.  */
3235   cached_lhs = lookup_avail_expr (stmt, block_avail_exprs_p, insert);
3236
3237   /* We have now called lookup_avail_expr twice with two different
3238      versions of this same statement, once in optimize_stmt, once here.
3239
3240      We know the call in optimize_stmt did not find an existing entry
3241      in the hash table, so a new entry was created.  At the same time
3242      this statement was pushed onto the BLOCK_AVAIL_EXPRS varray.
3243
3244      If this call failed to find an existing entry on the hash table,
3245      then the new version of this statement was entered into the
3246      hash table.  And this statement was pushed onto BLOCK_AVAIL_EXPR
3247      for the second time.  So there are two copies on BLOCK_AVAIL_EXPRs
3248
3249      If this call succeeded, we still have one copy of this statement
3250      on the BLOCK_AVAIL_EXPRs varray.
3251
3252      For both cases, we need to pop the most recent entry off the
3253      BLOCK_AVAIL_EXPRs varray.  For the case where we never found this
3254      statement in the hash tables, that will leave precisely one
3255      copy of this statement on BLOCK_AVAIL_EXPRs.  For the case where
3256      we found a copy of this statement in the second hash table lookup
3257      we want _no_ copies of this statement in BLOCK_AVAIL_EXPRs.  */
3258   if (insert)
3259     VARRAY_POP (*block_avail_exprs_p);
3260
3261   /* And make sure we record the fact that we modified this
3262      statement.  */
3263   ann->modified = 1;
3264
3265   return cached_lhs;
3266 }
3267
3268 /* Search for an existing instance of STMT in the AVAIL_EXPRS table.  If
3269    found, return its LHS. Otherwise insert STMT in the table and return
3270    NULL_TREE.
3271
3272    Also, when an expression is first inserted in the AVAIL_EXPRS table, it
3273    is also added to the stack pointed by BLOCK_AVAIL_EXPRS_P, so that they
3274    can be removed when we finish processing this block and its children.
3275
3276    NOTE: This function assumes that STMT is a MODIFY_EXPR node that
3277    contains no CALL_EXPR on its RHS and makes no volatile nor
3278    aliased references.  */
3279
3280 static tree
3281 lookup_avail_expr (tree stmt, varray_type *block_avail_exprs_p, bool insert)
3282 {
3283   void **slot;
3284   tree lhs;
3285   tree temp;
3286   struct expr_hash_elt *element = xcalloc (sizeof (struct expr_hash_elt), 1);
3287
3288   lhs = TREE_CODE (stmt) == MODIFY_EXPR ? TREE_OPERAND (stmt, 0) : NULL;
3289
3290   initialize_hash_element (stmt, lhs, element);
3291
3292   /* Don't bother remembering constant assignments and copy operations.
3293      Constants and copy operations are handled by the constant/copy propagator
3294      in optimize_stmt.  */
3295   if (TREE_CODE (element->rhs) == SSA_NAME
3296       || is_gimple_min_invariant (element->rhs))
3297     {
3298       free (element);
3299       return NULL_TREE;
3300     }
3301
3302   /* If this is an equality test against zero, see if we have recorded a
3303      nonzero value for the variable in question.  */
3304   if ((TREE_CODE (element->rhs) == EQ_EXPR
3305        || TREE_CODE  (element->rhs) == NE_EXPR)
3306       && TREE_CODE (TREE_OPERAND (element->rhs, 0)) == SSA_NAME
3307       && integer_zerop (TREE_OPERAND (element->rhs, 1)))
3308     {
3309       int indx = SSA_NAME_VERSION (TREE_OPERAND (element->rhs, 0));
3310
3311       if (bitmap_bit_p (nonzero_vars, indx))
3312         {
3313           tree t = element->rhs;
3314           free (element);
3315
3316           if (TREE_CODE (t) == EQ_EXPR)
3317             return boolean_false_node;
3318           else
3319             return boolean_true_node;
3320         }
3321     }
3322
3323   /* Finally try to find the expression in the main expression hash table.  */
3324   slot = htab_find_slot_with_hash (avail_exprs, element, element->hash,
3325                                    (insert ? INSERT : NO_INSERT));
3326   if (slot == NULL)
3327     {
3328       free (element);
3329       return NULL_TREE;
3330     }
3331
3332   if (*slot == NULL)
3333     {
3334       *slot = (void *) element;
3335       if (! *block_avail_exprs_p)
3336         VARRAY_TREE_INIT (*block_avail_exprs_p, 20, "block_avail_exprs");
3337       VARRAY_PUSH_TREE (*block_avail_exprs_p, stmt ? stmt : element->rhs);
3338       return NULL_TREE;
3339     }
3340
3341   /* Extract the LHS of the assignment so that it can be used as the current
3342      definition of another variable.  */
3343   lhs = ((struct expr_hash_elt *)*slot)->lhs;
3344
3345   /* See if the LHS appears in the CONST_AND_COPIES table.  If it does, then
3346      use the value from the const_and_copies table.  */
3347   if (TREE_CODE (lhs) == SSA_NAME)
3348     {
3349       temp = get_value_for (lhs, const_and_copies);
3350       if (temp)
3351         lhs = temp;
3352     }
3353
3354   free (element);
3355   return lhs;
3356 }
3357
3358 /* Given a condition COND, record into HI_P, LO_P and INVERTED_P the
3359    range of values that result in the conditional having a true value.
3360
3361    Return true if we are successful in extracting a range from COND and
3362    false if we are unsuccessful.  */
3363
3364 static bool
3365 extract_range_from_cond (tree cond, tree *hi_p, tree *lo_p, int *inverted_p)
3366 {
3367   tree op1 = TREE_OPERAND (cond, 1);
3368   tree high, low, type;
3369   int inverted;
3370
3371   /* Experiments have shown that it's rarely, if ever useful to
3372      record ranges for enumerations.  Presumably this is due to
3373      the fact that they're rarely used directly.  They are typically
3374      cast into an integer type and used that way.  */
3375   if (TREE_CODE (TREE_TYPE (op1)) != INTEGER_TYPE)
3376     return 0;
3377
3378   type = TREE_TYPE (op1);
3379
3380   switch (TREE_CODE (cond))
3381     {
3382     case EQ_EXPR:
3383       high = low = op1;
3384       inverted = 0;
3385       break;
3386
3387     case NE_EXPR:
3388       high = low = op1;
3389       inverted = 1;
3390       break;
3391
3392     case GE_EXPR:
3393       low = op1;
3394       high = TYPE_MAX_VALUE (type);
3395       inverted = 0;
3396       break;
3397
3398     case GT_EXPR:
3399       low = int_const_binop (PLUS_EXPR, op1, integer_one_node, 1);
3400       high = TYPE_MAX_VALUE (type);
3401       inverted = 0;
3402       break;
3403
3404     case LE_EXPR:
3405       high = op1;
3406       low = TYPE_MIN_VALUE (type);
3407       inverted = 0;
3408       break;
3409
3410     case LT_EXPR:
3411       high = int_const_binop (MINUS_EXPR, op1, integer_one_node, 1);
3412       low = TYPE_MIN_VALUE (type);
3413       inverted = 0;
3414       break;
3415
3416     default:
3417       return 0;
3418     }
3419
3420   *hi_p = high;
3421   *lo_p = low;
3422   *inverted_p = inverted;
3423   return 1;
3424 }
3425
3426 /* Record a range created by COND for basic block BB.  */
3427
3428 static void
3429 record_range (tree cond, basic_block bb, varray_type *vrp_variables_p)
3430 {
3431   /* We explicitly ignore NE_EXPRs.  They rarely allow for meaningful
3432      range optimizations and significantly complicate the implementation.  */
3433   if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<'
3434       && TREE_CODE (cond) != NE_EXPR
3435       && TREE_CODE (TREE_TYPE (TREE_OPERAND (cond, 1))) == INTEGER_TYPE)
3436     {
3437       struct vrp_element *element = ggc_alloc (sizeof (struct vrp_element));
3438       int ssa_version = SSA_NAME_VERSION (TREE_OPERAND (cond, 0));
3439
3440       varray_type *vrp_records_p
3441         = (varray_type *)&VARRAY_GENERIC_PTR (vrp_data, ssa_version);
3442
3443       element->low = NULL;
3444       element->high = NULL;
3445       element->cond = cond;
3446       element->bb = bb;
3447
3448       if (*vrp_records_p == NULL)
3449         {
3450           VARRAY_GENERIC_PTR_INIT (*vrp_records_p, 2, "vrp records");
3451           VARRAY_GENERIC_PTR (vrp_data, ssa_version) = *vrp_records_p;
3452         }
3453
3454       VARRAY_PUSH_GENERIC_PTR (*vrp_records_p, element);
3455       if (! *vrp_variables_p)
3456         VARRAY_TREE_INIT (*vrp_variables_p, 2, "vrp_variables");
3457       VARRAY_PUSH_TREE (*vrp_variables_p, TREE_OPERAND (cond, 0));
3458     }
3459 }
3460
3461 /* Given a conditional statement IF_STMT, return the assignment 'X = Y'
3462    known to be true depending on which arm of IF_STMT is taken.
3463
3464    Not all conditional statements will result in a useful assignment.
3465    Return NULL_TREE in that case.
3466
3467    Also enter into the available expression table statements of
3468    the form:
3469
3470      TRUE ARM           FALSE ARM
3471      1 = cond           1 = cond'
3472      0 = cond'          0 = cond
3473
3474    This allows us to lookup the condition in a dominated block and
3475    get back a constant indicating if the condition is true.  */
3476
3477 static struct eq_expr_value
3478 get_eq_expr_value (tree if_stmt,
3479                    int true_arm,
3480                    varray_type *block_avail_exprs_p,
3481                    basic_block bb,
3482                    varray_type *vrp_variables_p)
3483 {
3484   tree cond;
3485   struct eq_expr_value retval;
3486
3487   cond = COND_EXPR_COND (if_stmt);
3488   retval.src = NULL;
3489   retval.dst = NULL;
3490
3491   /* If the conditional is a single variable 'X', return 'X = 1' for
3492      the true arm and 'X = 0' on the false arm.   */
3493   if (TREE_CODE (cond) == SSA_NAME)
3494     {
3495       retval.dst = cond;
3496       retval.src = constant_boolean_node (true_arm, TREE_TYPE (cond));
3497       return retval;
3498     }
3499
3500   /* If we have a comparison expression, then record its result into
3501      the available expression table.  */
3502   if (TREE_CODE_CLASS (TREE_CODE (cond)) == '<')
3503     {
3504       tree op0 = TREE_OPERAND (cond, 0);
3505       tree op1 = TREE_OPERAND (cond, 1);
3506
3507       /* Special case comparing booleans against a constant as we know
3508          the value of OP0 on both arms of the branch.  ie, we can record
3509          an equivalence for OP0 rather than COND.  */
3510       if ((TREE_CODE (cond) == EQ_EXPR || TREE_CODE (cond) == NE_EXPR)
3511           && TREE_CODE (op0) == SSA_NAME
3512           && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
3513           && is_gimple_min_invariant (op1))
3514         {
3515           if ((TREE_CODE (cond) == EQ_EXPR && true_arm)
3516               || (TREE_CODE (cond) == NE_EXPR && ! true_arm))
3517             {
3518               retval.src = op1;
3519             }
3520           else
3521             {
3522               if (integer_zerop (op1))
3523                 retval.src = boolean_true_node;
3524               else
3525                 retval.src = boolean_false_node;
3526             }
3527           retval.dst = op0;
3528           return retval;
3529         }
3530
3531       if (TREE_CODE (op0) == SSA_NAME
3532           && (is_gimple_min_invariant (op1) || TREE_CODE (op1) == SSA_NAME))
3533         {
3534           tree inverted = invert_truthvalue (cond);
3535
3536           /* When we find an available expression in the hash table, we replace
3537              the expression with the LHS of the statement in the hash table.
3538
3539              So, we want to build statements such as "1 = <condition>" on the
3540              true arm and "0 = <condition>" on the false arm.  That way if we
3541              find the expression in the table, we will replace it with its
3542              known constant value.  Also insert inversions of the result and
3543              condition into the hash table.  */
3544           if (true_arm)
3545             {
3546               record_cond (cond, boolean_true_node, block_avail_exprs_p);
3547               record_dominating_conditions (cond, block_avail_exprs_p);
3548               record_cond (inverted, boolean_false_node, block_avail_exprs_p);
3549
3550               if (TREE_CONSTANT (op1))
3551                 record_range (cond, bb, vrp_variables_p);
3552
3553                 /* If the conditional is of the form 'X == Y', return 'X = Y'
3554                    for the true arm.  */
3555               if (TREE_CODE (cond) == EQ_EXPR)
3556                 {
3557                   retval.dst = op0;
3558                   retval.src = op1;
3559                   return retval;
3560                 }
3561             }
3562           else
3563             {
3564
3565               record_cond (inverted, boolean_true_node, block_avail_exprs_p);
3566               record_dominating_conditions (inverted, block_avail_exprs_p);
3567               record_cond (cond, boolean_false_node, block_avail_exprs_p);
3568
3569               if (TREE_CONSTANT (op1))
3570                 record_range (inverted, bb, vrp_variables_p);
3571
3572                 /* If the conditional is of the form 'X != Y', return 'X = Y'
3573                    for the false arm.  */
3574               if (TREE_CODE (cond) == NE_EXPR)
3575                 {
3576                   retval.dst = op0;
3577                   retval.src = op1;
3578                   return retval;
3579                 }
3580             }
3581         }
3582     }
3583
3584   return retval;
3585 }
3586
3587 /* Hashing and equality functions for AVAIL_EXPRS.  The table stores
3588    MODIFY_EXPR statements.  We compute a value number for expressions using
3589    the code of the expression and the SSA numbers of its operands.  */
3590
3591 static hashval_t
3592 avail_expr_hash (const void *p)
3593 {
3594   stmt_ann_t ann = ((struct expr_hash_elt *)p)->ann;
3595   tree rhs = ((struct expr_hash_elt *)p)->rhs;
3596   hashval_t val = 0;
3597   size_t i;
3598   vuse_optype vuses;
3599
3600   /* iterative_hash_expr knows how to deal with any expression and
3601      deals with commutative operators as well, so just use it instead
3602      of duplicating such complexities here.  */
3603   val = iterative_hash_expr (rhs, val);
3604
3605   /* If the hash table entry is not associated with a statement, then we
3606      can just hash the expression and not worry about virtual operands
3607      and such.  */
3608   if (!ann)
3609     return val;
3610
3611   /* Add the SSA version numbers of every vuse operand.  This is important
3612      because compound variables like arrays are not renamed in the
3613      operands.  Rather, the rename is done on the virtual variable
3614      representing all the elements of the array.  */
3615   vuses = VUSE_OPS (ann);
3616   for (i = 0; i < NUM_VUSES (vuses); i++)
3617     val = iterative_hash_expr (VUSE_OP (vuses, i), val);
3618
3619   return val;
3620 }
3621
3622 static hashval_t
3623 real_avail_expr_hash (const void *p)
3624 {
3625   return ((const struct expr_hash_elt *)p)->hash;
3626 }
3627
3628 static int
3629 avail_expr_eq (const void *p1, const void *p2)
3630 {
3631   stmt_ann_t ann1 = ((struct expr_hash_elt *)p1)->ann;
3632   tree rhs1 = ((struct expr_hash_elt *)p1)->rhs;
3633   stmt_ann_t ann2 = ((struct expr_hash_elt *)p2)->ann;
3634   tree rhs2 = ((struct expr_hash_elt *)p2)->rhs;
3635
3636   /* If they are the same physical expression, return true.  */
3637   if (rhs1 == rhs2 && ann1 == ann2)
3638     return true;
3639
3640   /* If their codes are not equal, then quit now.  */
3641   if (TREE_CODE (rhs1) != TREE_CODE (rhs2))
3642     return false;
3643
3644   /* In case of a collision, both RHS have to be identical and have the
3645      same VUSE operands.  */
3646   if ((TREE_TYPE (rhs1) == TREE_TYPE (rhs2)
3647        || lang_hooks.types_compatible_p (TREE_TYPE (rhs1), TREE_TYPE (rhs2)))
3648       && operand_equal_p (rhs1, rhs2, OEP_PURE_SAME))
3649     {
3650       vuse_optype ops1 = NULL;
3651       vuse_optype ops2 = NULL;
3652       size_t num_ops1 = 0;
3653       size_t num_ops2 = 0;
3654       size_t i;
3655
3656       if (ann1)
3657         {
3658           ops1 = VUSE_OPS (ann1);
3659           num_ops1 = NUM_VUSES (ops1);
3660         }
3661
3662       if (ann2)
3663         {
3664           ops2 = VUSE_OPS (ann2);
3665           num_ops2 = NUM_VUSES (ops2);
3666         }
3667
3668       /* If the number of virtual uses is different, then we consider
3669          them not equal.  */
3670       if (num_ops1 != num_ops2)
3671         return false;
3672
3673       for (i = 0; i < num_ops1; i++)
3674         if (VUSE_OP (ops1, i) != VUSE_OP (ops2, i))
3675           return false;
3676
3677 #ifdef ENABLE_CHECKING
3678       if (((struct expr_hash_elt *)p1)->hash
3679           != ((struct expr_hash_elt *)p2)->hash)
3680         abort ();
3681 #endif
3682       return true;
3683     }
3684
3685   return false;
3686 }
3687
3688 /* Given STMT and a pointer to the block local definitions BLOCK_DEFS_P,
3689    register register all objects set by this statement into BLOCK_DEFS_P
3690    and CURRDEFS.  */
3691
3692 static void
3693 register_definitions_for_stmt (stmt_ann_t ann, varray_type *block_defs_p)
3694 {
3695   def_optype defs;
3696   v_may_def_optype v_may_defs;
3697   v_must_def_optype v_must_defs;
3698   unsigned int i;
3699
3700   defs = DEF_OPS (ann);
3701   for (i = 0; i < NUM_DEFS (defs); i++)
3702     {
3703       tree def = DEF_OP (defs, i);
3704
3705       /* FIXME: We shouldn't be registering new defs if the variable
3706          doesn't need to be renamed.  */
3707       register_new_def (def, block_defs_p);
3708     }
3709
3710   /* Register new virtual definitions made by the statement.  */
3711   v_may_defs = V_MAY_DEF_OPS (ann);
3712   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
3713     {
3714       /* FIXME: We shouldn't be registering new defs if the variable
3715          doesn't need to be renamed.  */
3716       register_new_def (V_MAY_DEF_RESULT (v_may_defs, i), block_defs_p);
3717     }
3718
3719   /* Register new virtual mustdefs made by the statement.  */
3720   v_must_defs = V_MUST_DEF_OPS (ann);
3721   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
3722     {
3723       /* FIXME: We shouldn't be registering new defs if the variable
3724          doesn't need to be renamed.  */
3725       register_new_def (V_MUST_DEF_OP (v_must_defs, i), block_defs_p);
3726     }
3727 }
3728