gcc/tree-ssa-dom.c

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