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