gcc/tree-ssa-dom.c

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