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