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