gcc/tree-ssa-dom.c

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