gcc/tree-ssa-dom.c

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