gcc/tree-ssa-dom.c

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