gcc/tree-ssa-dom.c

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