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