gcc/tree-ssa-dom.c

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