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