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