gcc/tree-ssa-dom.c

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