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