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