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