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