gcc/tree-ssa-dom.c

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