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