gcc/tree-ssa-dom.c

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