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