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