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