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