gcc/tree-ssa-pre.c

   1 /* SSA-PRE for trees.
   2    Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>
   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 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28
  29 /* These RTL headers are needed for basic-block.h.  */
  30 #include "rtl.h"
  31 #include "tm_p.h"
  32 #include "hard-reg-set.h"
  33 #include "basic-block.h"
  34 #include "diagnostic.h"
  35 #include "tree-inline.h"
  36 #include "tree-flow.h"
  37 #include "tree-gimple.h"
  38 #include "tree-dump.h"
  39 #include "timevar.h"
  40 #include "fibheap.h"
  41 #include "hashtab.h"
  42 #include "tree-iterator.h"
  43 #include "real.h"
  44 #include "alloc-pool.h"
  45 #include "tree-pass.h"
  46 #include "flags.h"
  47
  48
  49 /*
  50
  51    Some of the algorithms are also based on Open64's SSAPRE implementation.
  52
  53    Since the papers are a bit dense to read, take a while to grasp,
  54    and have a few bugs, i'll give a quick rundown:
  55
  56    Normally, in non-SSA form, one performs PRE on expressions using
  57    bit vectors, determining properties for all expressions at once
  58    through bitmap operations and iterative dataflow.
  59
  60    SSAPRE, like most non-SSA->SSA algorithm conversions, operates one
  61    expression at a time, and doesn't use bitvectors or iterative
  62    dataflow.
  63
  64    It answers the question "Given a single hypothetical temporary
  65    variable, what expressions could we eliminate.
  66
  67    To be able to do this, we need an SSA form for expressions.
  68    If you are already confused, you likely think an expression, as
  69    used here, is something like "b_3 = a_2 + 5".  It's not. It's "a +
  70    5". "a_2 + 5" is an *occurrence* of the expression "a + 5".  Just
  71    like PRE, it's lexical equivalence that matters.
  72    Compilers generally give you an SSA form for variables, and maybe
  73    arrays (and/or conditionals).  But not for expressions.
  74
  75    GCC doesn't give you one either, so we have to build it.
  76    Thus, the first steps of SSAPRE are to do just these things.
  77
  78    First we collect lists of occurrences of expressions we are going
  79    to operate on.
  80    Note that:
  81    Unlike the paper, we don't have to ever add newly formed
  82    expressions to the list (for normal SSAPRE, anyway), because we
  83    don't have expressions with more than two operators, and each
  84    operator is either a constant or a variable.  Thus, no second
  85    order effects.
  86
  87    Once we have the lists of occurrences, we process one expression
  88    at a time, doing the following:
  89    1. Using a slightly modified SSA phi placement algorithm, place
  90    expression PHI's for expressions.
  91    2. Using a two step optimistic SSA renaming algorithm, version the
  92    nodes and link phi operands to their real occurrences, if they
  93    exist.  This creates a factored graph of our expression SSA occurrences.
  94    3. Using the factored graph, compute downsafe, avail, and later for
  95    EPHIs (which are SSA versions of the same named bitvector PRE
  96    problems)
  97    4. Using EPHI availability information and versions, compute what
  98    occurrences need to have saves, and what occurrences can be
  99    reloaded from an already saved value.
 100    5. Insert the saves and reloads, and transform EPHIs into regular
 101    phis of the temporary we use for insertion/saving.
 102
 103    See http://citeseer.nj.nec.com/chow97new.html, and
 104    http://citeseer.nj.nec.com/kennedy99partial.html for details of the
 105    algorithm.
 106
 107    kennedy99partial is newer, and is what this implementation is based
 108    on.
 109
 110    For strength reduction addition, see
 111    http://citeseer.nj.nec.com/kennedy98strength.html.
 112
 113    There is also a paper on sparse register promotion using PRE that
 114    contains the basic algorithm for load PRE.  The exact title/url of
 115    the paper escapes me.
 116
 117    Lastly, there is a code hoisting extension that open64 performs
 118    (see opt_ehoist.cxx), but we don't. It's not documented in any
 119    papers, but not that difficult to understand of implement.  */
 120
 121
 122 /* TODOS:
 123    Do strength reduction on a +-b and -a, not just a * <constant>.
 124    */
 125
 126 struct expr_info;
 127 static void clear_all_eref_arrays (void);
 128 static inline bool expr_lexically_eq (const tree, const tree);
 129 static void free_expr_info (struct expr_info *);
 130 static bitmap compute_idfs (bitmap *, tree);
 131 static void set_var_phis (struct expr_info *, tree);
 132 static inline bool names_match_p (const tree, const tree);
 133 static bool is_strred_cand (const tree);
 134 static int pre_expression (struct expr_info *, void *, bitmap);
 135 static bool is_injuring_def (struct expr_info *, tree);
 136 static inline bool okay_injuring_def (tree, tree);
 137 static bool expr_phi_insertion (bitmap *, struct expr_info *);
 138 static tree factor_through_injuries (struct expr_info *, tree, tree, bool *);
 139 static inline tree maybe_find_rhs_use_for_var (tree, tree, unsigned int);
 140 static inline tree find_rhs_use_for_var (tree, tree);
 141 static tree create_ephi_node (basic_block, unsigned int);
 142 static inline int opnum_of_phi (tree, int);
 143 static inline int opnum_of_ephi (const tree, const edge);
 144 static tree subst_phis (struct expr_info *, tree, basic_block, basic_block);
 145 static void generate_expr_as_of_bb (tree, basic_block, basic_block);
 146 static void generate_vops_as_of_bb (tree, basic_block, basic_block);
 147 static void rename_1 (struct expr_info *);
 148 static void process_delayed_rename (struct expr_info *, tree, tree);
 149 static void assign_new_class (tree, varray_type *, varray_type *);
 150 static void create_and_insert_occ_in_preorder_dt_order (struct expr_info *);
 151 static void insert_euse_in_preorder_dt_order (struct expr_info *);
 152 static bool ephi_has_unsafe_arg (tree);
 153 static void reset_down_safe (tree, int);
 154 static void compute_down_safety (struct expr_info *);
 155 static void compute_will_be_avail (struct expr_info *);
 156 static void compute_stops (struct expr_info *);
 157 static bool finalize_1 (struct expr_info *);
 158 static void finalize_2 (struct expr_info *);
 159 static tree occ_identical_to (tree);
 160 static void require_phi (struct expr_info *, basic_block);
 161 static bool really_available_def (tree node);
 162
 163 /* Functions used for an EPHI based depth first search.  */
 164 struct ephi_df_search
 165 {
 166   /* Return true if the ephi has been seen.  */
 167   bool (*seen) (tree);
 168   /* Mark the ephi as seen.  */
 169   void (*set_seen) (tree);
 170   /* Note that the search reaches from one ephi to it's use.  */
 171   void (*reach_from_to) (tree, int, tree);
 172   /* Return true if we should start a search from this PHI.  */
 173   bool (*start_from) (tree);
 174   /* Return true if we should continue the search to this use.  */
 175   bool (*continue_from_to) (tree, int, tree);
 176 };
 177 static bool repl_search_seen (tree);
 178 static void repl_search_set_seen (tree);
 179 static void repl_search_reach_from_to (tree, int, tree);
 180 static bool repl_search_start_from (tree);
 181 static bool repl_search_continue_from_to (tree, int, tree);
 182 static bool stops_search_seen (tree);
 183 static void stops_search_set_seen (tree);
 184 static void stops_search_reach_from_to (tree, int, tree);
 185 static bool stops_search_start_from (tree);
 186 static bool stops_search_continue_from_to (tree, int, tree);
 187 static bool cba_search_seen (tree);
 188 static void cba_search_set_seen (tree);
 189 static bool cba_search_start_from (tree);
 190 static bool cba_search_continue_from_to (tree, int, tree);
 191 struct ephi_df_search cant_be_avail_search = {
 192   cba_search_seen,
 193   cba_search_set_seen,
 194   NULL,
 195   cba_search_start_from,
 196   cba_search_continue_from_to
 197 };
 198
 199 struct ephi_df_search stops_search = {
 200   stops_search_seen,
 201   stops_search_set_seen,
 202   stops_search_reach_from_to,
 203   stops_search_start_from,
 204   stops_search_continue_from_to
 205 };
 206
 207
 208 /* depth-first replacement search used during temp ESSA minimization.  */
 209 struct ephi_df_search replacing_search = {
 210   repl_search_seen,
 211   repl_search_set_seen,
 212   repl_search_reach_from_to,
 213   repl_search_start_from,
 214   repl_search_continue_from_to
 215 };
 216
 217 static void do_ephi_df_search_1 (struct ephi_df_search, tree);
 218 static void do_ephi_df_search (struct expr_info *, struct ephi_df_search);
 219
 220 static inline bool any_operand_injured (tree);
 221 static void code_motion (struct expr_info *);
 222 static tree pick_ssa_name (tree stmt);
 223 #if 0
 224 static tree calculate_increment (struct expr_info *, tree);
 225 #endif
 226 static bool can_insert (tree, int);
 227 static void set_save (struct expr_info *, tree);
 228 static tree reaching_def (tree, tree, basic_block, tree);
 229 static tree do_proper_save (tree , tree, int);
 230 static void process_left_occs_and_kills (varray_type, tree);
 231 static tree create_expr_ref (struct expr_info *, tree, enum tree_code,
 232                              basic_block, tree);
 233 static inline bool ephi_will_be_avail (tree);
 234 static inline tree ephi_at_block (basic_block);
 235 static tree get_default_def (tree, htab_t);
 236 static inline bool same_e_version_real_occ_real_occ (struct expr_info *,
 237                                                      const tree,
 238                                                      const tree);
 239 static inline bool load_modified_phi_result (basic_block, tree);
 240 static inline bool same_e_version_phi_result (struct expr_info *,
 241                                               tree, tree, tree);
 242 static inline bool load_modified_real_occ_real_occ (tree, tree);
 243 static inline bool same_e_version_real_occ_phi_opnd (struct expr_info *,
 244                                                      tree, basic_block,
 245                                                      int, tree, bool *);
 246 static inline bool injured_real_occ_real_occ (struct expr_info *,
 247                                               tree, tree);
 248 static inline bool injured_phi_result_real_occ (struct expr_info *,
 249                                                 tree, tree, basic_block);
 250 static inline bool injured_real_occ_phi_opnd (struct expr_info *,
 251                                               tree, basic_block, int);
 252 static void compute_du_info (struct expr_info *);
 253 static void add_ephi_use (tree, tree, int);
 254 static void insert_one_operand (struct expr_info *, tree, int, tree, edge,
 255                                 tree **);
 256 static void collect_expressions (basic_block, varray_type *);
 257 static int build_dfn_array (basic_block, int);
 258 static int eref_compare (const void *, const void *);
 259
 260
 261 /* Bitmap of E-PHI predecessor operands have already been created.
 262    We only create one phi-pred per block.  */
 263 static bitmap created_phi_preds;
 264
 265 /* PRE dominance frontiers.  */
 266 static bitmap *pre_dfs;
 267
 268 /* Number of redundancy classes.  */
 269 static int class_count = 0;
 270
 271
 272 /* Iterated dominance frontiers cache.  */
 273 static bitmap *idfs_cache;
 274
 275 /* Partial redundancies statistics. */
 276 static struct pre_stats_d
 277 {
 278   int reloads;
 279   int saves;
 280   int repairs;
 281   int newphis;
 282   int ephi_allocated;
 283   int ephis_current;
 284   int eref_allocated;
 285   int exprs_generated;
 286 } pre_stats = {0, 0, 0, 0, 0, 0, 0, 0};
 287
 288
 289 /* USE entry in list of uses of ephi's.  */
 290 struct ephi_use_entry
 291 {
 292   tree phi;
 293   int opnd_indx;
 294 };
 295
 296 /* PRE Expression specific info.  */
 297 struct expr_info
 298 {
 299   /* The actual expression.  */
 300   tree expr;
 301   /* The occurrences. */
 302   varray_type occurs;
 303   /* The kills. */
 304   varray_type kills;
 305   /* The left occurrences. */
 306   varray_type lefts;
 307   /* An array of real occurrences. */
 308   varray_type reals;
 309   /* True if it's a strength reduction candidate. */
 310   bool strred_cand;
 311   /* True if it's a load PRE candidate. */
 312   bool loadpre_cand;
 313   /* The euses/ephis in preorder dt order. */
 314   varray_type euses_dt_order;
 315   /* The name of the temporary for this expression. */
 316   tree temp;
 317 };
 318
 319
 320 /* Cache of expressions generated for given phi operand, to avoid
 321    recomputation and wasting memory.  */
 322 static tree *phi_pred_cache;
 323 static int n_phi_preds;
 324
 325 /* Trying to lookup ephi pred operand indexes takes forever on graphs
 326    that have high connectivity because it's an O(n) linked list
 327    traversal.  Thus, we set up a hashtable that tells us the operand
 328    index for a given edge.  */
 329
 330 typedef struct ephi_pred_index_elt
 331 {
 332   tree ephi;
 333   edge edge;
 334   int opnd;
 335 } ephi_pindex_t;
 336
 337 /* Hash an (ephi, edge, opnd) tuple.  */
 338
 339 static hashval_t
 340 ephi_pindex_hash (const void *p)
 341 {
 342   const ephi_pindex_t *ep = (const ephi_pindex_t *)p;
 343   return htab_hash_pointer (ep->ephi) + htab_hash_pointer (ep->edge);
 344 }
 345
 346 /* Determine equality of an (ephi, edge, opnd) tuple.  */
 347
 348 static int
 349 ephi_pindex_eq (const void *p1, const void *p2)
 350 {
 351   const ephi_pindex_t *ep1 = (const ephi_pindex_t *)p1;
 352   const ephi_pindex_t *ep2 = (const ephi_pindex_t *)p2;
 353
 354   return ep1->ephi == ep2->ephi && ep1->edge == ep2->edge;
 355 }
 356
 357 /* The (ephi, edge) => opnd mapping hashtable.  */
 358 static htab_t ephi_pindex_htab;
 359
 360 /* Add an ephi predecessor to a PHI.  */
 361
 362 static int
 363 add_ephi_pred (tree phi, tree def, edge e)
 364 {
 365   int i = EPHI_NUM_ARGS (phi);
 366   void **slot;
 367   ephi_pindex_t ep, *epp;
 368
 369   EPHI_ARG_PRED (phi, i) = def;
 370   EPHI_ARG_EDGE (phi, i) = e;
 371
 372   ep.ephi = phi;
 373   ep.edge = e;
 374   slot = htab_find_slot (ephi_pindex_htab, (void *)&ep, INSERT);
 375   if (*slot == NULL)
 376     {
 377       epp = xmalloc (sizeof (*epp));
 378       epp->ephi = phi;
 379       epp->edge = e;
 380       epp->opnd = i;
 381       *slot = (void *)epp;
 382     }
 383   else
 384     abort ();
 385
 386   EPHI_NUM_ARGS (phi)++;
 387   return i;
 388 }
 389
 390 /* Create a new EPHI node at basic block BB.  */
 391
 392 static tree
 393 create_ephi_node (basic_block bb, unsigned int add)
 394 {
 395   tree phi;
 396   int len;
 397   edge e;
 398   size_t size;
 399   bb_ann_t ann;
 400
 401   for (len = 0, e = bb->pred; e; e = e->pred_next)
 402     len++;
 403   size = (sizeof (struct tree_ephi_node)
 404           + ((len - 1) * sizeof (struct ephi_arg_d)));
 405
 406   phi = xmalloc (size);
 407   memset (phi, 0, size);
 408   if (add)
 409     {
 410       ann = bb_ann (bb);
 411       if (ann->ephi_nodes == NULL)
 412         ann->ephi_nodes = phi;
 413       else
 414         chainon (ann->ephi_nodes, phi);
 415     }
 416   pre_stats.ephi_allocated += size;
 417   pre_stats.ephis_current += 1;
 418   TREE_SET_CODE (phi, EPHI_NODE);
 419   EPHI_NUM_ARGS (phi) = 0;
 420   EPHI_ARG_CAPACITY (phi) = len;
 421
 422   /* Associate BB to the PHI node.  */
 423   set_bb_for_stmt (phi, bb);
 424
 425   return phi;
 426 }
 427
 428 /* Given DEF (which can be an SSA_NAME or entire statement), and VAR,
 429    find a use of VAR on the RHS of DEF, if one exists. Abort if we
 430    can't find one.  */
 431
 432 static inline tree
 433 find_rhs_use_for_var (tree def, tree var)
 434 {
 435   tree ret = maybe_find_rhs_use_for_var (def, var, 0);
 436   if (!ret)
 437     abort ();
 438   return ret;
 439 }
 440
 441 /* Determine if two trees are referring to the same variable.
 442    Handles SSA_NAME vs non SSA_NAME, etc.  Uses operand_equal_p for
 443    non-trivial cases (INDIRECT_REF and friends).  */
 444
 445 static inline bool
 446 names_match_p (const tree t1, const tree t2)
 447 {
 448   tree name1, name2;
 449
 450   if (t1 == t2)
 451     return true;
 452
 453   if (TREE_CODE (t1) == INDIRECT_REF)
 454     return names_match_p (TREE_OPERAND (t1, 0), t2);
 455
 456   if (TREE_CODE (t2) == INDIRECT_REF)
 457     return names_match_p (t1, TREE_OPERAND (t2, 0));
 458
 459   if (TREE_CODE (t1) == SSA_NAME)
 460     name1 = SSA_NAME_VAR (t1);
 461   else if (DECL_P (t1))
 462     name1 = t1;
 463   else
 464     name1 = NULL_TREE;
 465
 466   if (TREE_CODE (t2) == SSA_NAME)
 467     name2 = SSA_NAME_VAR (t2);
 468   else if (DECL_P (t2))
 469     name2 = t2;
 470   else
 471     name2 = NULL_TREE;
 472
 473   if (name1 == NULL_TREE && name2 != NULL_TREE)
 474     return false;
 475   if (name2 == NULL_TREE && name1 != NULL_TREE)
 476     return false;
 477   if (name1 == NULL_TREE && name2 == NULL_TREE)
 478     return operand_equal_p (t1, t2, 0);
 479
 480   return name1 == name2;
 481 }
 482
 483 /* Given DEF (which can be an SSA_NAME or entire statement), and VAR,
 484    find a use of VAR on the RHS of DEF, if one exists.  Return NULL if
 485    we cannot find one.  */
 486
 487 static inline tree
 488 maybe_find_rhs_use_for_var (tree def, tree var, unsigned int startpos)
 489 {
 490   use_optype uses;
 491   size_t i;
 492
 493   if (SSA_VAR_P (def))
 494     {
 495       if (names_match_p (var, def))
 496         return def;
 497       return NULL_TREE;
 498     }
 499   get_stmt_operands (def);
 500   uses = STMT_USE_OPS (def);
 501
 502   for (i = startpos; i < NUM_USES (uses); i++)
 503     {
 504       tree use = USE_OP (uses, i);
 505       if (names_match_p (use, var))
 506         return use;
 507     }
 508   return NULL_TREE;
 509 }
 510
 511 /* Determine if an injuring def is one which we can repair, and thus,
 512    ignore for purposes of determining the version of a variable.  */
 513
 514 static inline bool
 515 okay_injuring_def (tree inj, tree var)
 516 {
 517   /* Acceptable injuries are those which
 518      1. aren't empty statements.
 519      2. aren't phi nodes.
 520      3. contain a use of VAR on the RHS.  */
 521   if (!inj || IS_EMPTY_STMT (inj)
 522       || TREE_CODE (inj) == PHI_NODE
 523       || !maybe_find_rhs_use_for_var (inj, var, 0))
 524     return false;
 525   return true;
 526 }
 527
 528 /* Return true if INJ is an injuring definition */
 529
 530 static bool
 531 is_injuring_def (struct expr_info *ei, tree inj)
 532 {
 533   /* Things that are never injuring definitions. */
 534   if (!inj || IS_EMPTY_STMT (inj) || TREE_CODE (inj) == PHI_NODE)
 535     return false;
 536
 537   /* Things we can't handle. */
 538   if (TREE_CODE (TREE_OPERAND (inj, 1)) != PLUS_EXPR
 539       && TREE_CODE (TREE_OPERAND (inj, 1)) != MINUS_EXPR)
 540     return false;
 541
 542   /* given inj: a1 = a2 + 5
 543      expr: a3 * c
 544      we are testing:
 545      if (a1 != a3
 546      || ! (a2 exists)
 547      || a2 != a3)
 548      return false
 549
 550      Or, in English,  if either the assigned-to variable in
 551      the injury is different from the first variable in the
 552      expression, or the incremented variable is different from the
 553      first variable in the expression, punt.
 554
 555      This makes sure we have something of the form
 556
 557      a = a {+,-} {expr}
 558      for an expression like "a * 5".
 559
 560      This limitation only exists because we don't know how to repair
 561      other forms of increments/decrements. */
 562   if (!names_match_p (TREE_OPERAND (inj, 0), TREE_OPERAND (ei->expr, 0))
 563       || !TREE_OPERAND (TREE_OPERAND (inj, 1), 0)
 564       || !names_match_p (TREE_OPERAND (TREE_OPERAND (inj, 1), 0),
 565                          TREE_OPERAND (ei->expr, 0)))
 566     return false;
 567
 568   /* If we are strength reducing a multiply, we have the additional
 569      constraints that
 570      1. {expr} is 1
 571      2. {expr} and the RHS of the expression are constants. */
 572   if (TREE_CODE (ei->expr) == MULT_EXPR)
 573     {
 574       tree irhs1;
 575       tree irhs2;
 576       tree irhs;
 577       irhs = TREE_OPERAND (inj, 1);
 578       irhs1 = TREE_OPERAND (irhs, 0);
 579       irhs2 = TREE_OPERAND (irhs, 1);
 580
 581       if (TREE_CODE (irhs2) != INTEGER_CST)
 582         return false;
 583       if (tree_low_cst (irhs2, 0) == 1)
 584         return true;
 585       if (really_constant_p (irhs2)
 586           && really_constant_p (TREE_OPERAND (ei->expr, 1)))
 587         return true;
 588       /* We don't currently support "the injury is inside a loop,expr is
 589          loop-invariant, and b is either loop-invariant or is
 590          another induction variable with respect to the loop." */
 591       return false;
 592     }
 593   return true;
 594 }
 595
 596 /* Find the statement defining VAR, ignoring injuries we can repair.
 597    START is the first potential injuring def. */
 598
 599 static tree
 600 factor_through_injuries (struct expr_info *ei, tree start, tree var,
 601                          bool *injured)
 602 {
 603   tree end = start;
 604
 605   while (is_injuring_def (ei, SSA_NAME_DEF_STMT (end)))
 606     {
 607       if (injured)
 608         *injured = true;
 609       end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var);
 610       if (!okay_injuring_def (SSA_NAME_DEF_STMT (end), var))
 611         break;
 612       if (dump_file)
 613         {
 614           fprintf (dump_file, "Found a real injury:");
 615           print_generic_stmt (dump_file, SSA_NAME_DEF_STMT (end), dump_flags);
 616           fprintf (dump_file, "\n");
 617         }
 618       if (injured)
 619         *injured = true;
 620       end = find_rhs_use_for_var (SSA_NAME_DEF_STMT (end), var);
 621     }
 622   return end;
 623 }
 624
 625 /* Return true if the result of the EPHI, when transformed into a phi,
 626    will be available.  */
 627
 628 static inline bool
 629 ephi_will_be_avail (tree ephi)
 630 {
 631   if (!EPHI_CANT_BE_AVAIL (ephi))
 632     if (EPHI_STOPS (ephi))
 633       return true;
 634
 635   return false;
 636 }
 637
 638 /* EUSE node pool.  We allocate EUSE nodes out of this*/
 639 static alloc_pool euse_node_pool;
 640
 641 /* EREF node pool.  We allocate regular EREF nodes (like EEXIT_NODE)
 642    out of this.  */
 643 static alloc_pool eref_node_pool;
 644
 645
 646 /* To order EREF's in a given block, we assign them each an ID based
 647    on when we see them.  */
 648 static int eref_id_counter = 0;
 649
 650 /* Creation an expression reference of TYPE.  */
 651
 652 static tree
 653 create_expr_ref (struct expr_info *ei, tree expr, enum tree_code type,
 654                  basic_block bb, tree parent)
 655 {
 656   tree ret;
 657   if (type == EPHI_NODE)
 658     {
 659       int len;
 660       edge e;
 661
 662       ret = create_ephi_node (bb, 1);
 663       for (len = 0, e = bb->pred; e; e = e->pred_next)
 664         len++;
 665
 666       EREF_TEMP (ret) = make_phi_node (ei->temp, len);
 667     }
 668   else
 669     {
 670       if (type == EUSE_NODE)
 671         ret = (tree) pool_alloc (euse_node_pool);
 672       else
 673         ret = (tree) pool_alloc (eref_node_pool);
 674       TREE_SET_CODE (ret, type);
 675       memset (ret, 0, tree_size (ret));
 676       TREE_SET_CODE (ret, type);
 677       pre_stats.eref_allocated += tree_size (ret);
 678     }
 679
 680   EREF_NAME (ret) = expr;
 681   set_bb_for_stmt (ret, bb);
 682   EREF_STMT (ret) = parent;
 683   EREF_SAVE (ret) = false;
 684   EREF_ID (ret) = eref_id_counter++;
 685
 686   return ret;
 687 }
 688
 689
 690 /* dfphis is a bitmap of where we need to insert ephis due to the
 691    iterated dominance frontier of an expression.  */
 692
 693 static bitmap dfphis;
 694
 695 /* varphis is a bitmap of where we need to insert ephis due to the
 696    presence of phis for a variable.  */
 697
 698 static bitmap varphis;
 699
 700
 701 /* Function to recursively figure out where EPHI's need to be placed
 702    because of PHI's.
 703    We always place EPHI's where we place PHI's because they are also
 704    partially anticipated expression points (because some expression
 705    alteration reaches that merge point).
 706
 707    We do this recursively, because we have to figure out
 708    EPHI's for the variables in the PHI as well. */
 709
 710 static void
 711 set_var_phis (struct expr_info *ei, tree phi)
 712 {
 713   basic_block bb = bb_for_stmt (phi);
 714   /* If we've already got an EPHI set to be placed in PHI's BB, we
 715      don't need to do this again. */
 716   if (!bitmap_bit_p (varphis, bb->index)
 717         && !bitmap_bit_p (dfphis, bb->index))
 718     {
 719       tree phi_operand;
 720       int curr_phi_operand;
 721       bitmap_set_bit (varphis, bb->index);
 722       for (curr_phi_operand = 0;
 723            curr_phi_operand < PHI_NUM_ARGS (phi);
 724            curr_phi_operand++)
 725         {
 726           phi_operand = PHI_ARG_DEF (phi, curr_phi_operand);
 727           /* For strength reduction, factor through injuries we can
 728              repair. */
 729           if (ei->strred_cand && TREE_CODE (phi_operand) != PHI_NODE)
 730             {
 731               phi_operand = factor_through_injuries (ei, phi_operand,
 732                                                      SSA_NAME_VAR (phi_operand),
 733                                                      NULL);
 734               phi_operand = SSA_NAME_DEF_STMT (phi_operand);
 735               if (dump_file)
 736                 {
 737                   fprintf (dump_file, "After factoring through injuries:");
 738                   print_generic_stmt (dump_file, phi_operand, dump_flags);
 739                   fprintf (dump_file, "\n");
 740                 }
 741             }
 742
 743           /* If our phi operand is defined by a phi, we need to
 744              record where the phi operands alter the expression as
 745              well, and place EPHI's at each point. */
 746           if (TREE_CODE (phi_operand) == PHI_NODE)
 747             set_var_phis (ei, phi_operand);
 748         }
 749     }
 750 }
 751
 752
 753 /* Clear all the expression reference arrays.  */
 754
 755 static void
 756 clear_all_eref_arrays (void)
 757 {
 758   basic_block bb;
 759   bb_ann_t ann;
 760
 761   FOR_ALL_BB (bb)
 762     {
 763       ann = bb_ann (bb);
 764       if (ann->ephi_nodes)
 765         {
 766           free (ann->ephi_nodes);
 767           pre_stats.ephis_current -= 1;
 768         }
 769       ann->ephi_nodes = NULL;
 770     }
 771 }
 772
 773 /* EPHI insertion algorithm.  */
 774
 775 static bool
 776 expr_phi_insertion (bitmap *dfs, struct expr_info *ei)
 777 {
 778   size_t i, j;
 779   vuse_optype vuses;
 780   use_optype uses;
 781   bool retval = true;
 782
 783   dfphis = BITMAP_XMALLOC ();
 784   bitmap_zero (dfphis);
 785   varphis = BITMAP_XMALLOC ();
 786   bitmap_zero (varphis);
 787
 788   /*  Compute where we need to place EPHIS. There are two types of
 789       places we need EPHI's: Those places we would normally place a
 790       PHI for the occurrence (calculated by determining the IDF+ of
 791       the statement), and those places we need an EPHI due to partial
 792       anticipation.  */
 793   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++)
 794     {
 795       tree occurp = VARRAY_TREE (ei->occurs, i);
 796       tree occur = occurp ? occurp : NULL;
 797       tree killp = VARRAY_TREE (ei->kills, i);
 798       tree kill = killp ? killp : NULL;
 799       tree leftp = VARRAY_TREE (ei->lefts, i);
 800       tree left = leftp ? leftp : NULL;
 801       bitmap temp;
 802       stmt_ann_t ann;
 803
 804 #ifdef ENABLE_CHECKING
 805       if ((kill && occur) || (left && occur) || (kill && left))
 806         abort();
 807 #endif
 808       occurp = occur ? occurp : kill ? killp : leftp;
 809       occur = occur ? occur : kill ? kill : left;
 810       temp = compute_idfs (dfs, occur);
 811       bitmap_a_or_b (dfphis, dfphis, temp);
 812       if (kill != NULL)
 813         continue;
 814       get_stmt_operands (occurp);
 815       ann = stmt_ann (occurp);
 816       uses = USE_OPS (ann);
 817       for (j = 0; j < NUM_USES (uses); j ++)
 818         {
 819           tree use = USE_OP (uses, j);
 820           if (ei->strred_cand)
 821             use = factor_through_injuries (ei, use, SSA_NAME_VAR (use),
 822                                            NULL);
 823           if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE)
 824             continue;
 825           set_var_phis (ei, SSA_NAME_DEF_STMT (use));
 826         }
 827       if (ei->loadpre_cand && TREE_CODE (ei->expr) == INDIRECT_REF)
 828         {
 829           vuses = VUSE_OPS (ann);
 830           for (j = 0; j < NUM_VUSES (vuses); j ++)
 831             {
 832               tree use = VUSE_OP (vuses, j);
 833               if (ei->strred_cand)
 834                 use = factor_through_injuries (ei, use, SSA_NAME_VAR (use),
 835                                                NULL);
 836               if (TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE)
 837                 continue;
 838               set_var_phis (ei, SSA_NAME_DEF_STMT (use));
 839             }
 840         }
 841     }
 842   /* Union the results of the dfphis and the varphis to get the
 843      answer to everywhere we need EPHIS. */
 844   bitmap_a_or_b (dfphis, dfphis, varphis);
 845
 846   /* Now create the EPHI's in each of these blocks. */
 847   EXECUTE_IF_SET_IN_BITMAP(dfphis, 0, i,
 848   {
 849     tree ref = create_expr_ref (ei, ei->expr, EPHI_NODE, BASIC_BLOCK (i),
 850                                 NULL);
 851     EREF_PROCESSED (ref) = false;
 852     EPHI_DOWNSAFE (ref) = true;
 853     EPHI_DEAD (ref) = true;
 854   });
 855 #if 0
 856   /* If there are no phis, we don't have anything to optimize,
 857      assuming the dominator optimizer took care of it all.  */
 858   if (bitmap_first_set_bit (dfphis) == -1)
 859     retval = false;
 860 #endif
 861   BITMAP_XFREE (dfphis);
 862   BITMAP_XFREE (varphis);
 863   return retval;
 864
 865 }
 866
 867 /* Return the EPHI at block BB, if one exists.  */
 868
 869 static inline tree
 870 ephi_at_block (basic_block bb)
 871 {
 872   bb_ann_t ann = bb_ann (bb);
 873   if (ann->ephi_nodes)
 874     return ann->ephi_nodes;
 875   else
 876     return NULL_TREE;
 877 }
 878
 879 /* Depth first numbering array.  */
 880 static int *dfn;
 881
 882 /* Build a depth first numbering array to be used in sorting in
 883    dominator order.  */
 884
 885 static int
 886 build_dfn_array (basic_block bb, int num)
 887 {
 888   basic_block son;
 889
 890   if (bb->index >= 0)
 891     dfn[bb->index] = num;
 892
 893   for (son = first_dom_son (CDI_DOMINATORS, bb);
 894        son;
 895        son = next_dom_son (CDI_DOMINATORS, son))
 896     num = build_dfn_array (son, ++num);
 897   return num;
 898 }
 899
 900
 901 /* Compare two EREF's in terms of dominator preorder.  Return -1 if
 902    ELEM1 goes before ELEM2, 1 if ELEM1 goes after ELEM2, and 0 if they
 903    are equal.  */
 904
 905 static int
 906 eref_compare (const void *elem1, const void *elem2)
 907 {
 908   tree t1 = *(tree *)elem1;
 909   tree t2 = *(tree *)elem2;
 910   basic_block bb1, bb2;
 911   if (t1 == t2)
 912     return 0;
 913   bb1 = bb_for_stmt (t1);
 914   bb2 = bb_for_stmt (t2);
 915   if (bb1 == bb2)
 916     {
 917       if (TREE_CODE (t1) == EEXIT_NODE)
 918         return 1;
 919       if (TREE_CODE (t2) == EEXIT_NODE)
 920         return -1;
 921       if (TREE_CODE (t1) == EPHI_NODE)
 922         return -1;
 923       if (TREE_CODE (t2) == EPHI_NODE)
 924         return 1;
 925       if ((TREE_CODE (t1) == EUSE_NODE && EUSE_PHIOP (t1))
 926           && (TREE_CODE (t2) == EUSE_NODE && !EUSE_PHIOP (t2)))
 927         return 1;
 928       if ((TREE_CODE (t1) == EUSE_NODE && !EUSE_PHIOP (t1))
 929           && (TREE_CODE (t2) == EUSE_NODE && EUSE_PHIOP (t2)))
 930         return -1;
 931       if (TREE_CODE (t1) == EUSE_NODE && TREE_CODE (t2) == EUSE_NODE)
 932         return EREF_ID (t1) - EREF_ID (t2);
 933       if (TREE_CODE (t1) == EPHI_NODE && TREE_CODE (t2) == EPHI_NODE)
 934         abort ();
 935
 936     }
 937   else
 938     {
 939       if (dfn[bb1->index] == dfn[bb2->index])
 940         {
 941           if (dominated_by_p (CDI_DOMINATORS, bb1, bb2))
 942             return 1;
 943           else
 944             return -1;
 945         }
 946       else
 947         return (dfn[bb1->index] < dfn[bb2->index]) ? -1 : 1;
 948     }
 949
 950   abort ();
 951 }
 952
 953 /* Create expression references for occurrences, kills, phi operands,
 954    and the like.  At the same time,  insert the occurrences into the
 955    ei->euses_dt_order array in the proper order.  If this function had
 956    any use outside of rename_1, you could split it into two
 957    functions, one creating, one inserting.  */
 958
 959 static void
 960 create_and_insert_occ_in_preorder_dt_order (struct expr_info *ei)
 961 {
 962   size_t i;
 963   edge succ;
 964   tree curr_phi_pred = NULL_TREE;
 965   basic_block block;
 966
 967   /* The ephis references were already created, so just push them into
 968      the euses_dt_order list.  */
 969   FOR_EACH_BB (block)
 970   {
 971     tree ephi = ephi_at_block (block);
 972     /* The ordering for a given BB is EPHI's, real/left/kill
 973        occurrences, phi preds, exit occurrences.   */
 974     if (ephi != NULL_TREE)
 975       VARRAY_PUSH_TREE (ei->euses_dt_order, ephi);
 976   }
 977
 978   /* The non-ephis have to actually be created, so do that, then push
 979      them into the list.  */
 980
 981   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->occurs); i++)
 982       {
 983         tree newref;
 984         tree current;
 985         current = VARRAY_TREE (ei->occurs, i);
 986         current = current ? current : VARRAY_TREE (ei->kills, i);
 987         current = current ? current : VARRAY_TREE (ei->lefts, i);
 988         block = bb_for_stmt (current);
 989         if (VARRAY_TREE (ei->kills, i) != NULL)
 990           {
 991             tree killexpr  = VARRAY_TREE (ei->kills, i);
 992             tree killname = ei->expr;
 993             newref = create_expr_ref (ei, killname, EKILL_NODE, block, killexpr);
 994             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
 995           }
 996         else if (VARRAY_TREE (ei->lefts, i) != NULL)
 997           {
 998             tree occurexpr = VARRAY_TREE (ei->lefts, i);
 999             tree occurname;
1000             occurname = ei->expr;
1001             newref = create_expr_ref (ei, occurname, EUSE_NODE, block,
1002                                       occurexpr);
1003             EUSE_DEF (newref) = NULL_TREE;
1004             EUSE_LVAL (newref) = true;
1005             EREF_CLASS (newref) = -1;
1006             EUSE_PHIOP (newref) = false;
1007             EREF_PROCESSED (newref) = false;
1008             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1009           }
1010         else
1011           {
1012             tree occurexpr = VARRAY_TREE (ei->occurs, i);
1013             tree occurname;
1014             occurname = ei->expr;
1015             newref = create_expr_ref (ei, occurname, EUSE_NODE, block,
1016                                       occurexpr);
1017             EUSE_DEF (newref) = NULL_TREE;
1018             EREF_CLASS (newref) = -1;
1019             EUSE_PHIOP (newref) = false;
1020             EREF_PROCESSED (newref) = false;
1021             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1022           }
1023       }
1024
1025   /* Lastly, we need to create and insert the ephi operand occurrences
1026      into the list.  */
1027   FOR_ALL_BB (block)
1028   {
1029     /* Insert the phi operand occurrences into the list at the
1030        successors.*/
1031     for (succ = block->succ; succ; succ = succ->succ_next)
1032       {
1033         if (succ->dest != EXIT_BLOCK_PTR)
1034           {
1035             tree ephi = ephi_at_block (succ->dest);
1036             if (ephi != NULL
1037                 && !bitmap_bit_p (created_phi_preds, block->index))
1038               {
1039                 tree newref = create_expr_ref (ei, 0, EUSE_NODE, block, NULL);
1040                 curr_phi_pred = newref;
1041                 VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1042                 EUSE_DEF (newref) = NULL_TREE;
1043                 EREF_CLASS (newref) = -1;
1044                 EUSE_PHIOP (newref) = true;
1045                 EREF_SAVE (newref) = false;
1046                 EREF_RELOAD (newref) = false;
1047                 EUSE_INSERTED (newref) = false;
1048                 EREF_PROCESSED (newref) = false;
1049                 bitmap_set_bit (created_phi_preds, block->index);
1050                 add_ephi_pred (ephi, newref, succ);
1051               }
1052             else if (ephi != NULL)
1053               {
1054 #ifdef ENABLE_CHECKING
1055                 if (curr_phi_pred == NULL_TREE)
1056                   abort();
1057 #endif
1058                 add_ephi_pred (ephi, curr_phi_pred, succ);
1059               }
1060           }
1061         else if (succ->dest == EXIT_BLOCK_PTR && !(succ->flags & EDGE_FAKE))
1062           {
1063             /* No point in inserting exit blocks into heap first, since
1064                they'll never be anything on the stack. */
1065             tree newref;
1066             newref = create_expr_ref (ei, ei->expr, EEXIT_NODE,
1067                                       block,
1068                                       NULL);
1069             VARRAY_PUSH_TREE (ei->euses_dt_order, newref);
1070           }
1071       }
1072   }
1073   qsort (ei->euses_dt_order->data.tree,
1074          VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
1075          sizeof (tree),
1076          eref_compare);
1077 }
1078
1079
1080 /* Assign a new redundancy class to the occurrence, and push it on the
1081    renaming stack.  */
1082
1083 static void
1084 assign_new_class (tree occ, varray_type * stack, varray_type * stack2)
1085 {
1086   /* class(occ) <- count
1087      Push(occ, stack)
1088      count <- count + 1
1089   */
1090   EREF_CLASS (occ) = class_count;
1091   VARRAY_PUSH_TREE (*stack, occ);
1092   if (stack2)
1093     VARRAY_PUSH_TREE (*stack2, occ);
1094   class_count++;
1095 }
1096
1097 /* Determine if two real occurrences have the same ESSA version.
1098    We do this by hashing the expressions and comparing the hash
1099    values.  Even if they don't match, we then see if this is a
1100    strength reduction candidate, and if so, if the use is simply
1101    injured.  */
1102
1103 static inline bool
1104 same_e_version_real_occ_real_occ (struct expr_info *ei,
1105                                   const tree def, const tree use)
1106 {
1107   hashval_t expr1val;
1108   hashval_t expr2val;
1109   vuse_optype vuses;
1110   size_t i;
1111   const tree t1 = EREF_STMT (def);
1112   const tree t2 = EREF_STMT (use);
1113
1114   expr1val = iterative_hash_expr (TREE_OPERAND (t1, 1), 0);
1115   expr2val = iterative_hash_expr (TREE_OPERAND (t2, 1), 0);
1116
1117   if (expr1val == expr2val)
1118     {
1119       vuses = STMT_VUSE_OPS (t1);
1120       for (i = 0; i < NUM_VUSES (vuses); i++)
1121         expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val);
1122       vuses = STMT_VUSE_OPS (t2);
1123       for (i = 0; i < NUM_VUSES (vuses); i++)
1124         expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val);
1125       if (expr1val != expr2val)
1126         return false;
1127     }
1128
1129   /* If the def is injured, and the expressions have the same value,
1130      then the use is injured.  */
1131   if (expr1val == expr2val)
1132     {
1133       if (EREF_INJURED (def))
1134         EREF_INJURED (use) = true;
1135       return true;
1136     }
1137
1138   /* Even if the expressions don't have the same value, it might be
1139      the case that the use is simply injured, in which case, it's
1140      still okay.  */
1141   if (expr1val != expr2val && ei->strred_cand)
1142     {
1143       if (injured_real_occ_real_occ (ei, def, use))
1144         {
1145           EREF_INJURED (use) = true;
1146           return true;
1147         }
1148     }
1149   return false;
1150 }
1151
1152 /* Determine if the use occurrence is injured.
1153    TODO: Finish actually implementing this.  */
1154
1155 static inline bool
1156 injured_real_occ_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED,
1157                            tree def ATTRIBUTE_UNUSED,
1158                            tree use ATTRIBUTE_UNUSED)
1159 {
1160   tree defstmt;
1161   tree defvar;
1162
1163   defstmt = EREF_STMT (def);
1164   if (TREE_CODE (TREE_OPERAND (defstmt, 0)) != SSA_NAME)
1165     return false;
1166
1167   defvar = TREE_OPERAND (defstmt, 0);
1168   /* XXX: Implement.  */
1169   return false;
1170
1171 }
1172
1173 /* Determine the operand number of edge E in EPHI.  */
1174
1175 static inline int
1176 opnum_of_ephi (const tree ephi, const edge e)
1177 {
1178   ephi_pindex_t ep, *epp;
1179
1180   ep.ephi = ephi;
1181   ep.edge = e;
1182   epp = htab_find (ephi_pindex_htab, &ep);
1183   if (epp == NULL)
1184     abort ();
1185   return epp->opnd;
1186 }
1187
1188 /* Determine the phi operand index for J in PHI.  */
1189
1190 static inline int
1191 opnum_of_phi (tree phi, int j)
1192 {
1193   int i;
1194   /* We can't just count predecessors, since tree-ssa.c generates them
1195      when it sees a phi in the successor during it's traversal.  So the
1196      order is dependent on the traversal order.  */
1197   for (i = 0 ; i < PHI_NUM_ARGS (phi); i++)
1198     if (PHI_ARG_EDGE (phi, i)->src->index == j)
1199       return i;
1200
1201   abort();
1202 }
1203
1204 /* Generate EXPR as it would look in basic block PRED (using the phi in
1205    block BB).  We do this by replacing the variables with the phi
1206    argument definitions for block J if they are defined by a phi in
1207    block BB.  */
1208
1209 static void
1210 generate_expr_as_of_bb (tree expr, basic_block pred, basic_block bb)
1211 {
1212   use_optype uses = STMT_USE_OPS (expr);
1213   bool replaced_constants = false;
1214   size_t k;
1215
1216   for (k = 0; k < NUM_USES (uses); k++)
1217     {
1218       tree *vp = USE_OP_PTR (uses, k);
1219       tree v = *vp;
1220       tree phi;
1221
1222       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1223         {
1224           if (PHI_RESULT (phi) ==  v)
1225             {
1226               int opnum = opnum_of_phi (phi, pred->index);
1227               tree p = PHI_ARG_DEF (phi, opnum);
1228               replace_exp (vp, p);
1229               if (!phi_ssa_name_p (p))
1230                 replaced_constants = true;
1231               break;
1232             }
1233         }
1234     }
1235
1236   /* If we've substituted in new constants, we must be sure to
1237      simplify the result lest we crash in get_expr_operands.  */
1238   if (replaced_constants)
1239     fold_stmt (&expr);
1240 }
1241
1242 /* Generate VUSE ops as they would look in basic block PRED (using the
1243    phi in block BB).  Done the same way as we do generation of regular
1244    ops for the bb.  */
1245
1246 static void
1247 generate_vops_as_of_bb (tree expr, basic_block pred, basic_block bb)
1248 {
1249   vuse_optype vuses = STMT_VUSE_OPS (expr);
1250   size_t i;
1251
1252   for (i = 0; i < NUM_VUSES (vuses); i++)
1253     {
1254       tree v = VUSE_OP (vuses, i);
1255       tree phi;
1256
1257       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1258         {
1259           if (PHI_RESULT (phi) == v)
1260             {
1261               int opnum = opnum_of_phi (phi, pred->index);
1262               tree p = PHI_ARG_DEF (phi, opnum);
1263               replace_exp (VUSE_OP_PTR (vuses, i), p);
1264               break;
1265             }
1266         }
1267     }
1268 }
1269
1270 /* Make a copy of Z as it would look in basic block PRED, using the PHIs
1271    in BB. */
1272
1273 static tree
1274 subst_phis (struct expr_info *ei, tree Z, basic_block pred, basic_block bb)
1275 {
1276   tree stmt_copy;
1277   size_t i;
1278
1279   /* Return the cached version, if we have one. */
1280   if (pred->index < n_phi_preds
1281       && phi_pred_cache[pred->index] != NULL_TREE)
1282     return phi_pred_cache[pred->index];
1283
1284   /* Otherwise, generate a new expression.  */
1285   pre_stats.exprs_generated++;
1286   stmt_copy = unshare_expr (Z);
1287   create_stmt_ann (stmt_copy);
1288   modify_stmt (stmt_copy);
1289   get_stmt_operands (stmt_copy);
1290   generate_expr_as_of_bb (stmt_copy, pred, bb);
1291   set_bb_for_stmt (stmt_copy, bb);
1292   modify_stmt (stmt_copy);
1293   get_stmt_operands (stmt_copy);
1294
1295   /* If we have vuses on the original statement, and we still have
1296      use_ops on the generated expr, we need to copy the vuses.  */
1297
1298   if (ei->loadpre_cand
1299       && NUM_VUSES (STMT_VUSE_OPS (Z)) != 0
1300       && NUM_USES (STMT_USE_OPS (stmt_copy)) != 0)
1301     {
1302       vuse_optype vuses = STMT_VUSE_OPS (Z);
1303       remove_vuses (stmt_copy);
1304
1305       start_ssa_stmt_operands (stmt_copy);
1306       for (i = 0; i < NUM_VUSES (vuses); i++)
1307         add_vuse (VUSE_OP (vuses, i), stmt_copy);
1308       finalize_ssa_stmt_operands (stmt_copy);
1309
1310       generate_vops_as_of_bb (stmt_copy, pred, bb);
1311     }
1312   else
1313     {
1314       remove_vuses (stmt_copy);
1315       remove_vdefs (stmt_copy);
1316     }
1317
1318   if (pred->index < n_phi_preds)
1319     phi_pred_cache[pred->index] = stmt_copy;
1320   return stmt_copy;
1321 }
1322
1323 /* Determine if def and use_tree should have the same e-version.  We do
1324    this by simply determining if something modifies the expression
1325    between DEF and USE_TREE.  USE_TREE was generated from the OPND_NUM'th
1326    operand of the EPHI in USE_BB.  If it is modified, we determine if
1327    it is simply injured, and thus, okay.  */
1328
1329 static inline bool
1330 same_e_version_real_occ_phi_opnd (struct expr_info *ei, tree def,
1331                                        basic_block use_bb, int opnd_num,
1332                                        tree use_tree, bool *injured)
1333 {
1334   bool not_mod = true;
1335   *injured = false;
1336
1337   if (load_modified_real_occ_real_occ (EREF_STMT (def),
1338                                        use_tree))
1339     not_mod = false;
1340
1341   if (not_mod)
1342     return true;
1343   else if (ei->strred_cand)
1344     {
1345       if (injured_real_occ_phi_opnd (ei, def, use_bb, opnd_num))
1346         return true;
1347     }
1348   return false;
1349 }
1350
1351 /* Determine whether the OPND_NUM'th operand of USE_BB's EPHI is an
1352    injured version of DEF.  */
1353 static inline bool
1354 injured_real_occ_phi_opnd (struct expr_info *ei ATTRIBUTE_UNUSED,
1355                                 tree def ATTRIBUTE_UNUSED,
1356                                 basic_block use_bb ATTRIBUTE_UNUSED,
1357                                 int opnd_num ATTRIBUTE_UNUSED)
1358 {
1359   /* XXX: Implement. */
1360   return false;
1361 }
1362
1363 /* Determine whether the expression is modified between DEF and USE,
1364    by comparing the hash values of the two expressions.  */
1365 static inline bool
1366 load_modified_real_occ_real_occ (tree def, tree use)
1367 {
1368   hashval_t expr1val;
1369   hashval_t expr2val;
1370   vuse_optype vuses;
1371   size_t i;
1372
1373   if (TREE_CODE (def) == VA_ARG_EXPR)
1374     expr1val = iterative_hash_expr (def, 0);
1375   else
1376     expr1val = iterative_hash_expr (TREE_OPERAND (def, 1), 0);
1377
1378   if (TREE_CODE (use) == VA_ARG_EXPR)
1379     expr2val = iterative_hash_expr (use, 0);
1380   else
1381     expr2val = iterative_hash_expr (TREE_OPERAND (use, 1), 0);
1382
1383   if (expr1val == expr2val)
1384     {
1385       vuses = STMT_VUSE_OPS (def);
1386       for (i = 0; i < NUM_VUSES (vuses); i++)
1387         expr1val = iterative_hash_expr (VUSE_OP (vuses, i), expr1val);
1388       vuses = STMT_VUSE_OPS (use);
1389       for (i = 0; i < NUM_VUSES (vuses); i++)
1390         expr2val = iterative_hash_expr (VUSE_OP (vuses, i), expr2val);
1391       if (expr1val != expr2val)
1392         return false;
1393     }
1394   return expr1val != expr2val;
1395 }
1396
1397 /* Determine if the expression is modified between the start of BB,
1398    and the use at USE, ignoring phis.  We do this by simple
1399    domination, because of the properties of SSA.  */
1400 static bool
1401 load_modified_phi_result (basic_block bb, tree use)
1402 {
1403   basic_block defbb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
1404   if (defbb != bb)
1405     {
1406       /* This guards against moving around undefined variables.
1407          However, PARM_DECL is special because it *IS* live on entry,
1408          so it's not really undefined.  */
1409       if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) != PARM_DECL)
1410         return true;
1411       else if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) == PARM_DECL)
1412         return false;
1413       if (dominated_by_p (CDI_DOMINATORS, bb, defbb))
1414         return false;
1415     }
1416   else
1417     {
1418       if (TREE_CODE (SSA_NAME_DEF_STMT (use)) == PHI_NODE)
1419         return false;
1420     }
1421   return true;
1422 }
1423
1424 /* Determine if the variables in EXP are modified between DEF and
1425    USE.  If they are, we have to give a new e-version to the result.
1426    For load PRE, we have to check the vuses too.  For strength
1427    reduction, we need to check whether the modification is a simple
1428    injury.  */
1429
1430 static bool
1431 same_e_version_phi_result (struct expr_info *ei, tree def, tree exp,
1432                                 tree use)
1433 {
1434   stmt_ann_t ann = stmt_ann (exp);
1435   bool not_mod = true;
1436   size_t i;
1437   use_optype real_expuses = USE_OPS (ann);
1438   vuse_optype expuses;
1439
1440
1441   if (NUM_USES (real_expuses) == 0)
1442     return false;
1443
1444   for (i = 0; i < NUM_USES (real_expuses) && not_mod; i++)
1445     {
1446       tree *use1p = USE_OP_PTR (real_expuses, i);
1447       tree use1;
1448       if (!use1p)
1449         continue;
1450       use1 = *use1p;
1451       if (load_modified_phi_result (bb_for_stmt (def), use1))
1452         not_mod = false;
1453     }
1454
1455   if (not_mod && ei->loadpre_cand)
1456     {
1457       expuses = VUSE_OPS (ann);
1458
1459       for (i = 0; i < NUM_VUSES (expuses) && not_mod; i++)
1460         {
1461           tree use1 = VUSE_OP (expuses, i);
1462           if (load_modified_phi_result (bb_for_stmt (def), use1))
1463             not_mod = false;
1464         }
1465     }
1466
1467   if (not_mod)
1468     return true;
1469   else if (ei->strred_cand)
1470     {
1471       if (injured_phi_result_real_occ (ei, def, exp, bb_for_stmt (use)))
1472         {
1473           EREF_INJURED (use) = true;
1474           return true;
1475         }
1476     }
1477
1478   return false;
1479 }
1480
1481 /* Determine whether USE_TREE is an injured version of DEF.  */
1482
1483 static inline bool
1484 injured_phi_result_real_occ (struct expr_info *ei ATTRIBUTE_UNUSED,
1485                              tree def ATTRIBUTE_UNUSED,
1486                              tree use_tree ATTRIBUTE_UNUSED,
1487                              basic_block use_bb ATTRIBUTE_UNUSED)
1488 {
1489   /* XXX: Implement.  */
1490   return false;
1491 }
1492
1493 /* Delayed renaming checks to make sure the optimistic assumptions
1494    about ephi operand versions in rename_1 actually turned out to be
1495    true.  This requires generating the expressions for each ephi
1496    operand, and comparing them to the versions of the occurrence it is
1497    defined by.
1498    Delayed rename handling is done like open64 does it.  Basically,
1499    like the delayed renaming is described in the paper, with
1500    extensions for strength reduction.  */
1501
1502 static void
1503 process_delayed_rename (struct expr_info *ei, tree use, tree real_occ)
1504 {
1505   tree exp_phi = use;
1506   int opnd_num = 0;
1507
1508   /* We only care about operands we actually have DELAYED_RENAME set
1509      on.  */
1510   for (opnd_num = 0; opnd_num < EPHI_NUM_ARGS (exp_phi); opnd_num++)
1511     {
1512       tree opnd = EPHI_ARG_DEF (exp_phi, opnd_num);
1513       if (EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num))
1514         {
1515           tree def;
1516           tree newexp;
1517
1518           /* Mark it as being processed, then generate the ephi
1519              operand expression.  */
1520           EPHI_ARG_DELAYED_RENAME (exp_phi, opnd_num) = false;
1521           def = opnd;
1522           newexp = subst_phis (ei, real_occ,
1523                               EPHI_ARG_EDGE (exp_phi, opnd_num)->src,
1524                               bb_for_stmt (exp_phi));
1525
1526           /* For operands defined by EPHIs, we need to compare the
1527              generated expression and the phi result.
1528              For operands defined by real occurrences, we simply compare
1529              the phi operand and the real occurrence.  */
1530           if (TREE_CODE (def) == EPHI_NODE)
1531             {
1532               tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num);
1533               EREF_STMT (tmp_use) = newexp;
1534               if (same_e_version_phi_result (ei, def, newexp,
1535                                              tmp_use))
1536                 {
1537
1538                   if (EREF_INJURED (tmp_use))
1539                     {
1540                       EREF_INJURED (tmp_use) = false;
1541                       EPHI_ARG_INJURED (exp_phi, opnd_num) = true;
1542                     }
1543                   if (EREF_STMT (def) == NULL)
1544                     {
1545                       /* If it was injured, we need to make up a new
1546                          phi result with the actually injured
1547                          version.  */
1548                       if (EPHI_ARG_INJURED (exp_phi, opnd_num))
1549                         {
1550                           /* XXX: Allocate phi result with correct version.  */
1551
1552                         }
1553                       EREF_STMT (def) = newexp;
1554                       process_delayed_rename (ei, def, newexp);
1555                     }
1556                 }
1557               /* If it's not the same version, the defining ephi can't
1558                  be downsafe, and the operand is not really defined by
1559                  anything.  */
1560               else
1561                 {
1562                   EPHI_DOWNSAFE (def) = false;
1563                   EPHI_ARG_DEF (exp_phi, opnd_num) = NULL;
1564                 }
1565             }
1566           else if (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def))
1567             {
1568               bool injured = false;
1569               if (same_e_version_real_occ_phi_opnd (ei, def,
1570                                                     bb_for_stmt (use),
1571                                                     opnd_num, newexp, &injured))
1572                 {
1573                   tree tmp_use = EPHI_ARG_PRED (exp_phi, opnd_num);
1574                   EPHI_ARG_HAS_REAL_USE (exp_phi, opnd_num) = true;
1575                   /*              EREF_STMT (opnd) = EREF_STMT (def); */
1576                   if (injured || EREF_INJURED (def))
1577                     EREF_INJURED (def) = true;
1578                   if (injured || EREF_INJURED (def))
1579                     EREF_INJURED (opnd) = true;
1580                   else
1581                     EREF_STMT (tmp_use) = EREF_STMT (def);
1582                   if (EUSE_DEF (def) != NULL)
1583                     EPHI_ARG_DEF (exp_phi, opnd_num) = EUSE_DEF (def);
1584                   else
1585                     EPHI_ARG_DEF (exp_phi, opnd_num) = def;
1586                 }
1587               else
1588                 {
1589                   EPHI_ARG_DEF (exp_phi, opnd_num) = NULL;
1590                 }
1591             }
1592         }
1593     }
1594 }
1595
1596 /* For the uninitiated, the algorithm is a modified SSA renaming
1597    algorithm (working on expressions rather than variables) .  We
1598    attempt to determine which expression occurrences have the same
1599    ESSA version (we call it class, for equivalence/redundancy class,
1600    which is what the papers call it.  Open64 calls it e-version), and
1601    which occurrences are actually operands for an EPHI (since this has
1602    to be discovered from the program).
1603
1604    Renaming is done like Open64 does it.  Basically as the paper says,
1605    except that we try to use earlier defined occurrences if they are
1606    available in order to keep the number of saves down. */
1607
1608 static void
1609 rename_1 (struct expr_info *ei)
1610 {
1611   tree occur;
1612   basic_block phi_bb;
1613   size_t i;
1614   varray_type stack;
1615
1616   VARRAY_GENERIC_PTR_NOGC_INIT (stack, 1, "Stack for renaming");
1617
1618   /* Start by creating and inserting the occurrences in preorder,
1619      dominator tree into a list.  */
1620   create_and_insert_occ_in_preorder_dt_order (ei);
1621
1622   /* Walk the occurrences.  */
1623   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1624     {
1625       occur = VARRAY_TREE (ei->euses_dt_order, i);
1626
1627       /* The current occurrence can't have the same version as
1628          something on the top of the stack unless it is in a basic
1629          block dominated by the basic block of the occurrence on the
1630          top of the stack.  */
1631       while (VARRAY_ACTIVE_SIZE (stack) > 0
1632              && !dominated_by_p (CDI_DOMINATORS,
1633                                  bb_for_stmt (occur),
1634                                  bb_for_stmt (VARRAY_TOP_TREE (stack))))
1635
1636         VARRAY_POP (stack);
1637
1638       /* If the stack is empty, we assign a new version since it isn't
1639          dominated by any other version.  */
1640       if (VARRAY_ACTIVE_SIZE (stack) == 0 || VARRAY_TOP_TREE (stack) == NULL)
1641         {
1642           if (TREE_CODE (occur) == EPHI_NODE)
1643             assign_new_class (occur, &stack, NULL);
1644           else if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur))
1645             assign_new_class (occur, &stack, NULL);
1646         }
1647       else
1648         {
1649           if (TREE_CODE (occur) == EUSE_NODE && !EUSE_PHIOP (occur))
1650             {
1651               tree tos = VARRAY_TOP_TREE (stack);
1652
1653               if (TREE_CODE (tos) == EUSE_NODE && !EUSE_PHIOP (tos))
1654                 {
1655                   /* If two real occurrences have the same
1656                      e-version/class, then this occurrence can be
1657                      defined by the prior occurrence (or whatever
1658                      the prior occurrence is defined by, if
1659                      anything).
1660                      Otherwise, we have to assign a new version.
1661                      lvalue occurrences always need a new version,
1662                      since they are definitions. */
1663                   if (!EUSE_LVAL (occur)
1664                       && same_e_version_real_occ_real_occ (ei, tos, occur))
1665                     {
1666
1667
1668                       tree newdef;
1669                       EREF_CLASS (occur) = EREF_CLASS (tos);
1670                       newdef = EUSE_DEF (tos) != NULL ? EUSE_DEF (tos) : tos;
1671                       EUSE_DEF (occur) = newdef;
1672                     }
1673                   else
1674                     assign_new_class (occur, &stack, NULL);
1675                 }
1676               else if (TREE_CODE (tos) == EPHI_NODE)
1677                 {
1678                   /* Here we have an ephi occurrence at the top of the
1679                      stack, and the current occurrence is a real
1680                      occurrence.  So determine if the real occurrence
1681                      has the same version as the result of the phi.
1682                      If so, then this real occurrence is defined by the
1683                      EPHI at the top of the stack.
1684                      If not, the EPHI isn't downsafe (because something
1685                      must change in between the ephi result and the next
1686                      occurrence), and we need a new version for the real
1687                      occurrence.
1688                      lvalues always need a new version. */
1689                   if (!EUSE_LVAL (occur)
1690                       && same_e_version_phi_result (ei, tos, EREF_STMT (occur),
1691                                                     occur))
1692                     {
1693                       EREF_CLASS (occur) = EREF_CLASS (tos);
1694                       EUSE_DEF (occur) = tos;
1695                       EREF_STMT (tos) = EREF_STMT (occur);
1696
1697                       VARRAY_PUSH_TREE (stack, occur);
1698                     }
1699                   else
1700                     {
1701                       EPHI_DOWNSAFE (tos) = false;
1702                       assign_new_class (occur, &stack, NULL);
1703                     }
1704                 }
1705             }
1706           /* EPHI occurrences always get new versions. */
1707           else if (TREE_CODE (occur) == EPHI_NODE)
1708             {
1709               assign_new_class (occur, &stack, NULL);
1710             }
1711           /* EPHI operands are optimistcally assumed to be whatever is
1712              at the top of the stack at the time we hit the ephi
1713              operand occurrence.  The delayed renaming checks this
1714              optimistic assumption for validity.  */
1715           else if (TREE_CODE (occur) == EUSE_NODE && EUSE_PHIOP (occur))
1716             {
1717               basic_block pred_bb = bb_for_stmt (occur);
1718               edge e;
1719               tree tos = VARRAY_TOP_TREE (stack);
1720               for (e = pred_bb->succ; e; e = e->succ_next)
1721                 {
1722                   tree ephi = ephi_at_block (e->dest);
1723                   if (ephi != NULL_TREE)
1724                     {
1725                       int opnum = opnum_of_ephi (ephi, e);
1726
1727                       EPHI_ARG_DELAYED_RENAME (ephi, opnum) = true;
1728                       EPHI_ARG_DEF (ephi, opnum) = tos;
1729                     }
1730                 }
1731             }
1732           /* No EPHI can be downsafe past an exit node.  */
1733           else if (TREE_CODE (occur) == EEXIT_NODE)
1734             {
1735               if (VARRAY_ACTIVE_SIZE (stack) > 0
1736                   && TREE_CODE (VARRAY_TOP_TREE (stack)) == EPHI_NODE)
1737                 EPHI_DOWNSAFE (VARRAY_TOP_TREE (stack)) = false;
1738             }
1739         }
1740     }
1741   if (dump_file && (dump_flags & TDF_DETAILS))
1742     {
1743       size_t i;
1744       fprintf (dump_file, "Occurrences for expression ");
1745       print_generic_expr (dump_file, ei->expr, dump_flags);
1746       fprintf (dump_file, " after Rename 1\n");
1747       for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1748         {
1749           print_generic_expr (dump_file,
1750                               VARRAY_TREE (ei->euses_dt_order, i), 1);
1751           fprintf (dump_file, "\n");
1752         }
1753     }
1754
1755   /* Now process the renames for EPHI's that actually have the result
1756      valid and used.  These will be the EPHI's that have the statement
1757      set above.  */
1758   FOR_EACH_BB (phi_bb)
1759   {
1760     tree ephi = ephi_at_block (phi_bb);
1761     if (ephi != NULL && EREF_STMT (ephi) != NULL)
1762       process_delayed_rename (ei, ephi, EREF_STMT (ephi));
1763   }
1764
1765   /* If we didn't process the delayed rename for an ephi argument,
1766      but thought we needed to, mark the operand as NULL.  Also, if the
1767      operand was defined by an  EPHI, we can mark it not downsafe
1768      because there can't have been a real occurrence (or else we would
1769      have processed a rename for it).  */
1770   FOR_EACH_BB (phi_bb)
1771   {
1772     tree ephi = ephi_at_block (phi_bb);
1773     if (ephi != NULL)
1774       {
1775         int j;
1776         for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1777           {
1778             if (EPHI_ARG_DELAYED_RENAME (ephi, j))
1779               {
1780                 tree def = EPHI_ARG_DEF (ephi, j);
1781                 if (def && TREE_CODE (def) == EPHI_NODE)
1782                   EPHI_DOWNSAFE (def) = false;
1783                 EPHI_ARG_DEF (ephi, j) = NULL;
1784               }
1785           }
1786       }
1787   }
1788   VARRAY_FREE (stack);
1789 }
1790
1791 /* Determine if the EPHI has an argument we could never insert
1792    or extend the lifetime of, such as an argument occurring on
1793    an abnormal edge. */
1794
1795 static bool
1796 ephi_has_unsafe_arg (tree ephi)
1797 {
1798   int i;
1799   for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
1800     if (EPHI_ARG_EDGE (ephi, i)->flags & EDGE_ABNORMAL)
1801       return true;
1802   return false;
1803 }
1804
1805 /* Reset down safety flags for non-downsafe ephis. Uses depth first
1806    search.  */
1807
1808 static void
1809 reset_down_safe (tree currphi, int opnum)
1810 {
1811   tree ephi;
1812   int i;
1813
1814   if (EPHI_ARG_HAS_REAL_USE (currphi, opnum))
1815     return;
1816   ephi = EPHI_ARG_DEF (currphi, opnum);
1817   if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
1818     return;
1819   if (!EPHI_DOWNSAFE (ephi))
1820     return;
1821   EPHI_DOWNSAFE (ephi) = false;
1822   for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
1823     reset_down_safe (ephi, i);
1824 }
1825
1826 /* Compute down_safety using a depth first search.
1827    This propagates not fully anticipated phi assignments upwards.  */
1828
1829 static void
1830 compute_down_safety (struct expr_info *ei)
1831 {
1832   size_t i;
1833   basic_block bb;
1834   FOR_EACH_BB (bb)
1835   {
1836     tree ephi = ephi_at_block (bb);
1837     if (ephi == NULL_TREE)
1838       continue;
1839     if (ephi_has_unsafe_arg (ephi))
1840       EPHI_DOWNSAFE (ephi) = false;
1841   }
1842   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1843     {
1844       int j;
1845       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1846       if (TREE_CODE (ephi) != EPHI_NODE)
1847         continue;
1848
1849       if (!EPHI_DOWNSAFE (ephi))
1850         for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1851           reset_down_safe (ephi, j);
1852
1853     }
1854 }
1855
1856 /* EPHI use node pool. We allocate ephi_use_node's out of this.  */
1857 static alloc_pool ephi_use_pool;
1858
1859 /* Add a use of DEF to it's use list. The use is at operand OPND_INDX
1860    of USE.  */
1861
1862 static void
1863 add_ephi_use (tree def, tree use, int opnd_indx)
1864 {
1865   struct ephi_use_entry *entry;
1866   if (EPHI_USES (def) == NULL)
1867     VARRAY_GENERIC_PTR_INIT (EPHI_USES (def), 1, "EPHI uses");
1868   entry = (struct ephi_use_entry *) pool_alloc (ephi_use_pool);
1869   entry->phi = use;
1870   entry->opnd_indx = opnd_indx;
1871   VARRAY_PUSH_GENERIC_PTR (EPHI_USES (def), entry);
1872 }
1873
1874 /* Compute def-uses of ephis.  */
1875
1876 static void
1877 compute_du_info (struct expr_info *ei)
1878 {
1879   size_t i;
1880   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1881     {
1882       int j;
1883       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1884       if (TREE_CODE (ephi) != EPHI_NODE)
1885         continue;
1886       for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1887         {
1888           tree def = EPHI_ARG_DEF (ephi, j);
1889           if (def != NULL_TREE)
1890             {
1891               if (TREE_CODE (def) == EPHI_NODE)
1892                 add_ephi_use (def, ephi, j);
1893 #ifdef ENABLE_CHECKING
1894               else
1895                 if (! (TREE_CODE (def) == EUSE_NODE && !EUSE_PHIOP (def)))
1896                   abort();
1897 #endif
1898             }
1899         }
1900     }
1901 }
1902
1903 /* STOPS marks what EPHI's/operands stop forward movement. (IE where
1904    we can't insert past).  */
1905
1906 static void
1907 compute_stops (struct expr_info *ei)
1908 {
1909   size_t i;
1910
1911   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1912     {
1913       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
1914       int j;
1915
1916       if (TREE_CODE (ephi) != EPHI_NODE)
1917         continue;
1918       if (EPHI_CANT_BE_AVAIL (ephi))
1919         EPHI_STOPS (ephi) = true;
1920       for (j = 0; j < EPHI_NUM_ARGS (ephi); j++)
1921         if (EPHI_ARG_HAS_REAL_USE (ephi, j))
1922           EPHI_ARG_STOPS (ephi, j) = true;
1923     }
1924   do_ephi_df_search (ei, stops_search);
1925 }
1926
1927 /* Compute will_be_avail property, which consists of cant_be_avail and
1928    stops properties.  */
1929
1930 static void
1931 compute_will_be_avail (struct expr_info *ei)
1932 {
1933   do_ephi_df_search (ei, cant_be_avail_search);
1934   compute_stops (ei);
1935 }
1936
1937 /* Insert the expressions into ei->euses_dt_order in preorder dt order.  */
1938
1939 static void
1940 insert_euse_in_preorder_dt_order (struct expr_info *ei)
1941 {
1942   varray_type new_euses_dt_order;
1943   size_t i;
1944   VARRAY_GENERIC_PTR_NOGC_INIT (new_euses_dt_order, 1, "EUSEs");
1945
1946   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
1947     {
1948       tree ref = VARRAY_TREE (ei->euses_dt_order, i);
1949       if (TREE_CODE (ref) == EUSE_NODE || TREE_CODE (ref) == EPHI_NODE)
1950         VARRAY_PUSH_TREE (new_euses_dt_order, ref);
1951     }
1952   VARRAY_FREE (ei->euses_dt_order);
1953   ei->euses_dt_order = new_euses_dt_order;
1954   qsort (ei->euses_dt_order->data.tree,
1955          VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
1956          sizeof (tree),
1957          eref_compare);
1958
1959 }
1960
1961 /* Determine if we can insert operand OPND_INDX of EPHI.  */
1962
1963 static bool
1964 can_insert (tree ephi, int opnd_indx)
1965 {
1966   tree def;
1967
1968   if (EPHI_ARG_DEF (ephi, opnd_indx) == NULL_TREE)
1969     return true;
1970   def = EPHI_ARG_DEF (ephi, opnd_indx);
1971   if (!EPHI_ARG_HAS_REAL_USE (ephi, opnd_indx))
1972     if (TREE_CODE (def) == EPHI_NODE && !(ephi_will_be_avail (def)))
1973       return true;
1974   return false;
1975 }
1976
1977 /* Find the default definition of VAR.
1978    This is incredibly ugly, since we have to walk back through all
1979    the definitions to find the one defined by the empty statement.  */
1980
1981 static tree
1982 get_default_def (tree var, htab_t seen)
1983 {
1984   def_optype defs;
1985   size_t i;
1986   tree defstmt = SSA_NAME_DEF_STMT (var);
1987
1988   if (IS_EMPTY_STMT (defstmt))
1989     return var;
1990   *(htab_find_slot (seen, var, INSERT)) = var;
1991   if (TREE_CODE (defstmt) == PHI_NODE)
1992     {
1993       int j;
1994       for (j = 0; j < PHI_NUM_ARGS (defstmt); j++)
1995         if (htab_find (seen, PHI_ARG_DEF (defstmt, j)) == NULL)
1996           {
1997             if (TREE_CODE (PHI_ARG_DEF (defstmt, j)) == SSA_NAME)
1998               {
1999                 tree temp = get_default_def (PHI_ARG_DEF (defstmt, j), seen);
2000                 if (temp != NULL_TREE)
2001                   return temp;
2002               }
2003           }
2004     }
2005
2006
2007   defs = STMT_DEF_OPS (defstmt);
2008   for (i = 0; i < NUM_DEFS (defs); i++)
2009     {
2010       tree def = DEF_OP (defs, i);
2011       if (SSA_NAME_VAR (def) == SSA_NAME_VAR (var))
2012         {
2013           if (htab_find (seen, def) != NULL)
2014             return NULL;
2015           return get_default_def (def, seen);
2016         }
2017     }
2018
2019   /* We should never get here.  */
2020   abort ();
2021 }
2022
2023 /* Hunt down the right reaching def for VAR, starting with BB.  Ignore
2024    defs in statement IGNORE, and stop if we hit CURRSTMT.  */
2025
2026 static tree
2027 reaching_def (tree var, tree currstmt, basic_block bb, tree ignore)
2028 {
2029   tree curruse = NULL_TREE;
2030   block_stmt_iterator bsi;
2031   basic_block dom;
2032   tree phi;
2033
2034   /* Check phis first. */
2035   for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
2036     {
2037       if (phi == currstmt)
2038         break;
2039       if (phi == ignore)
2040         continue;
2041       if (names_match_p (var, PHI_RESULT (phi)))
2042         curruse = PHI_RESULT (phi);
2043     }
2044
2045   /* We can't walk BB's backwards right now, so we have to walk *all*
2046      the statements, and choose the last name we find. */
2047   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2048     {
2049       tree stmt = bsi_stmt (bsi);
2050       tree *def;
2051       def_optype defs;
2052       size_t i;
2053
2054       if (stmt == currstmt)
2055         break;
2056
2057       get_stmt_operands (stmt);
2058       defs = STMT_DEF_OPS (stmt);
2059       for (i = 0; i < NUM_DEFS (defs); i++)
2060         {
2061           def = DEF_OP_PTR (defs, i);
2062           if (def && *def != ignore && names_match_p (var, *def))
2063             {
2064               curruse = *def;
2065               break;
2066             }
2067         }
2068     }
2069   if (curruse != NULL_TREE)
2070     return curruse;
2071   dom = get_immediate_dominator (CDI_DOMINATORS, bb);
2072   if (bb == ENTRY_BLOCK_PTR)
2073     {
2074       htab_t temp;
2075       temp = htab_create (7, htab_hash_pointer, htab_eq_pointer, NULL);
2076       curruse = get_default_def (var, temp);
2077       htab_delete (temp);
2078     }
2079   if (!dom)
2080     return curruse;
2081   return reaching_def (var, currstmt, dom, ignore);
2082 }
2083
2084 /* Insert one ephi operand that doesn't currently exist as a use.  */
2085
2086 static void
2087 insert_one_operand (struct expr_info *ei, tree ephi, int opnd_indx,
2088                     tree x, edge succ, tree **avdefsp)
2089 {
2090   /* FIXME.  pre_insert_on_edge should probably disappear.  */
2091   extern void pre_insert_on_edge (edge, tree);
2092   tree expr;
2093   tree temp = ei->temp;
2094   tree copy;
2095   tree newtemp;
2096   basic_block bb = bb_for_stmt (x);
2097
2098   /* Insert definition of expr at end of BB containing x. */
2099   copy = TREE_OPERAND (EREF_STMT (ephi), 1);
2100   copy = unshare_expr (copy);
2101   expr = build (MODIFY_EXPR, TREE_TYPE (ei->expr),
2102                 temp, copy);
2103   expr = subst_phis (ei, expr, bb, bb_for_stmt (ephi));
2104   newtemp = make_ssa_name (temp, expr);
2105   TREE_OPERAND (expr, 0) = newtemp;
2106   copy = TREE_OPERAND (expr, 1);
2107   if (dump_file)
2108     {
2109       fprintf (dump_file, "In BB %d, insert save of ", bb->index);
2110       print_generic_expr (dump_file, expr, dump_flags);
2111       fprintf (dump_file, " to ");
2112       print_generic_expr (dump_file, newtemp, dump_flags);
2113       fprintf (dump_file, " after ");
2114       print_generic_stmt (dump_file, last_stmt (bb), dump_flags);
2115       fprintf (dump_file, " (on edge), because of EPHI");
2116       fprintf (dump_file, " in BB %d\n", bb_for_stmt (ephi)->index);
2117     }
2118
2119   /* Do the insertion.  */
2120   /* ??? Previously we did bizarre searching, presumably to get
2121      around bugs elsewhere in the infrastructure.  I'm not sure
2122      if we really should be using pre_insert_on_edge
2123      or just bsi_insert_after at the end of BB.  */
2124   pre_insert_on_edge (succ, expr);
2125
2126   EPHI_ARG_DEF (ephi, opnd_indx)
2127     = create_expr_ref (ei, ei->expr, EUSE_NODE, bb, 0);
2128   EUSE_DEF (x) = EPHI_ARG_DEF (ephi, opnd_indx);
2129   VARRAY_PUSH_TREE (ei->euses_dt_order, EPHI_ARG_DEF (ephi, opnd_indx));
2130   qsort (ei->euses_dt_order->data.tree,
2131          VARRAY_ACTIVE_SIZE (ei->euses_dt_order),
2132          sizeof (tree),
2133          eref_compare);
2134   EREF_TEMP (EUSE_DEF (x)) = newtemp;
2135   EREF_RELOAD (EUSE_DEF (x)) = false;
2136   EREF_SAVE (EUSE_DEF (x)) = false;
2137   EUSE_INSERTED (EUSE_DEF (x)) = true;
2138   EUSE_PHIOP (EUSE_DEF (x)) = false;
2139   EREF_SAVE (x) = false;
2140   EREF_RELOAD (x) = false;
2141   EUSE_INSERTED (x) = true;
2142   EREF_CLASS (x) = class_count++;
2143   EREF_CLASS (EUSE_DEF (x)) = class_count++;
2144   *avdefsp = xrealloc (*avdefsp, sizeof (tree) * (class_count + 1));
2145   (*avdefsp)[class_count - 2] = x;
2146   (*avdefsp)[class_count - 1] = EUSE_DEF (x);
2147   pre_stats.saves++;
2148 }
2149
2150 /* First step of finalization.  Determine which expressions are being
2151    saved and which are being deleted.
2152    This is done as a simple dominator based availability calculation,
2153    using the e-versions/redundancy classes.  */
2154
2155 static bool
2156 finalize_1 (struct expr_info *ei)
2157 {
2158   tree x;
2159   int nx;
2160   bool made_a_reload = false;
2161   size_t i;
2162   tree *avdefs;
2163
2164   avdefs = xcalloc (class_count + 1, sizeof (tree));
2165
2166   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2167     {
2168       x = VARRAY_TREE (ei->euses_dt_order, i);
2169       nx = EREF_CLASS (x);
2170
2171       if (TREE_CODE (x) == EPHI_NODE)
2172         {
2173           if (ephi_will_be_avail (x))
2174             avdefs[nx] = x;
2175         }
2176       else if (TREE_CODE (x) == EUSE_NODE && EUSE_LVAL (x))
2177         {
2178           avdefs[nx] = x;
2179         }
2180       else if (TREE_CODE (x) == EUSE_NODE && !EUSE_PHIOP (x))
2181         {
2182           if (avdefs[nx] == NULL
2183               || !dominated_by_p (CDI_DOMINATORS, bb_for_stmt (x),
2184                                   bb_for_stmt (avdefs[nx])))
2185             {
2186               EREF_RELOAD (x) = false;
2187               avdefs[nx] = x;
2188               EUSE_DEF (x) = NULL;
2189             }
2190           else
2191             {
2192               EREF_RELOAD (x) = true;
2193               made_a_reload = true;
2194               EUSE_DEF (x) = avdefs[nx];
2195 #ifdef ENABLE_CHECKING
2196               if (EREF_CLASS (x) != EREF_CLASS (avdefs[nx]))
2197                 abort ();
2198 #endif
2199             }
2200         }
2201       else
2202         {
2203           edge succ;
2204           basic_block bb = bb_for_stmt (x);
2205           /* For each ephi in the successor blocks.  */
2206           for (succ = bb->succ; succ; succ = succ->succ_next)
2207             {
2208               tree ephi = ephi_at_block (succ->dest);
2209               if (ephi == NULL_TREE)
2210                 continue;
2211               if (ephi_will_be_avail (ephi))
2212                 {
2213                   int opnd_indx = opnum_of_ephi (ephi, succ);
2214 #ifdef ENABLE_CHECKING
2215                   if (EPHI_ARG_PRED (ephi, opnd_indx) != x)
2216                     abort ();
2217 #endif
2218                   if (can_insert (ephi, opnd_indx))
2219                     {
2220                       insert_one_operand (ei, ephi, opnd_indx, x, succ,
2221                                           &avdefs);
2222                     }
2223                   else
2224                     {
2225                       nx = EREF_CLASS (EPHI_ARG_DEF (ephi,opnd_indx));
2226                       EPHI_ARG_DEF (ephi, opnd_indx) = avdefs[nx];
2227                     }
2228                 }
2229             }
2230         }
2231     }
2232   free (avdefs);
2233   return made_a_reload;
2234 }
2235
2236 /* Mark the necessary SAVE bits on X.  */
2237
2238 static void
2239 set_save (struct expr_info *ei, tree X)
2240 {
2241   if (TREE_CODE (X) == EUSE_NODE && !EUSE_PHIOP (X))
2242     EREF_SAVE (X) = true;
2243   else if (TREE_CODE (X) == EPHI_NODE)
2244     {
2245       int curr_phiop;
2246       for (curr_phiop = 0; curr_phiop < EPHI_NUM_ARGS (X); curr_phiop++)
2247         {
2248           tree w = EPHI_ARG_DEF (X, curr_phiop);
2249           if (!EPHI_ARG_PROCESSED2 (X, curr_phiop))
2250             {
2251               EPHI_ARG_PROCESSED2 (X, curr_phiop) = true;
2252               if (w)
2253                 set_save (ei, w);
2254             }
2255         }
2256     }
2257 }
2258
2259 /* DFS Search function: Return true if PHI is can't be available.  */
2260
2261 static bool
2262 cba_search_seen (tree phi)
2263 {
2264   return EPHI_CANT_BE_AVAIL (phi);
2265 }
2266
2267 /* DFS Search function: Mark PHI as can't be available when seen.  */
2268
2269 static void
2270 cba_search_set_seen (tree phi)
2271 {
2272   EPHI_CANT_BE_AVAIL (phi) = true;
2273 }
2274
2275 /* DFS Search function: Return true if PHI should be marked can't be
2276    available due to a NULL operand.  */
2277
2278 static bool
2279 cba_search_start_from (tree phi)
2280 {
2281   if (!EPHI_DOWNSAFE (phi))
2282     {
2283       int i;
2284       for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2285         if (EPHI_ARG_DEF (phi, i) == NULL_TREE
2286             || EPHI_ARG_EDGE (phi, i)->flags & EDGE_ABNORMAL)
2287           return true;
2288     }
2289   return false;
2290 }
2291
2292 /* DFS Search function: Return true if the used PHI is not downsafe,
2293    unless we have a real use for the operand.  */
2294
2295 static bool
2296 cba_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2297                              int opnd_indx,
2298                              tree use_phi)
2299 {
2300   if (EPHI_ARG_HAS_REAL_USE (use_phi, opnd_indx) &&
2301       !(EPHI_ARG_EDGE (use_phi, opnd_indx)->flags & EDGE_ABNORMAL))
2302     return false;
2303   if (!EPHI_DOWNSAFE (use_phi))
2304     return true;
2305   return false;
2306 }
2307
2308 /* DFS Search function: Return true if this PHI stops forward
2309    movement.  */
2310
2311 static bool
2312 stops_search_seen (tree phi)
2313 {
2314   return EPHI_STOPS (phi);
2315 }
2316
2317 /* DFS Search function:  Mark the PHI as stopping forward movement.  */
2318
2319 static void
2320 stops_search_set_seen (tree phi)
2321 {
2322   EPHI_STOPS (phi) = true;
2323 }
2324
2325 /* DFS Search function:  Note that the used phi argument stops forward
2326    movement.  */
2327
2328 static void
2329 stops_search_reach_from_to (tree def_phi ATTRIBUTE_UNUSED,
2330                             int opnd_indx,
2331                             tree use_phi)
2332 {
2333   EPHI_ARG_STOPS (use_phi, opnd_indx) = true;
2334 }
2335
2336 /* DFS Search function: Return true if the PHI has any arguments
2337    stopping forward movement.  */
2338
2339 static bool
2340 stops_search_start_from (tree phi)
2341 {
2342   int i;
2343   for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2344     if (EPHI_ARG_STOPS (phi, i))
2345       return true;
2346   return false;
2347 }
2348
2349 /* DFS Search function:  Return true if the PHI has any arguments
2350    stopping forward movement.  */
2351
2352 static bool
2353 stops_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2354                                int opnd_indx ATTRIBUTE_UNUSED,
2355                                tree use_phi)
2356 {
2357   return stops_search_start_from (use_phi);
2358 }
2359
2360 /* DFS Search function:  Return true if the replacing occurrence is
2361    known.  */
2362
2363 static bool
2364 repl_search_seen (tree phi)
2365 {
2366   return EPHI_REP_OCCUR_KNOWN (phi);
2367 }
2368
2369 /* DFS Search function:  Set the identical_to field and note the
2370    replacing occurrence is now known.  */
2371
2372 static void
2373 repl_search_set_seen (tree phi)
2374 {
2375   int i;
2376
2377 #ifdef ENABLE_CHECKING
2378   if (!ephi_will_be_avail (phi))
2379     abort ();
2380 #endif
2381
2382   if (EPHI_IDENTICAL_TO (phi) == NULL_TREE)
2383     {
2384       for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2385         {
2386           tree identical_to = occ_identical_to (EPHI_ARG_DEF (phi, i));
2387           if (identical_to != NULL_TREE)
2388             {
2389               if (EPHI_IDENTICAL_TO (phi) == NULL)
2390                 EPHI_IDENTICAL_TO (phi) = identical_to;
2391               if (EPHI_ARG_INJURED (phi, i))
2392                 EPHI_IDENT_INJURED (phi) = true;
2393             }
2394         }
2395     }
2396   EPHI_REP_OCCUR_KNOWN (phi) = true;
2397 }
2398
2399 /* Helper function.  Return true if any argument in the PHI is
2400    injured.  */
2401
2402 static inline bool
2403 any_operand_injured (tree ephi)
2404 {
2405   int i;
2406   for (i = 0; i < EPHI_NUM_ARGS (ephi); i++)
2407     if (EPHI_ARG_INJURED (ephi, i))
2408       return true;
2409   return false;
2410
2411 }
2412
2413 /* DFS Search function:  Note the identity of the used phi operand is
2414    the same as it's defining phi operand, if that phi will be
2415    available, and it's known.  */
2416
2417 static void
2418 repl_search_reach_from_to (tree def_phi, int opnd_indx ATTRIBUTE_UNUSED,
2419                            tree use_phi)
2420 {
2421   if (ephi_will_be_avail (use_phi)
2422       && EPHI_IDENTITY (use_phi)
2423       && EPHI_IDENTICAL_TO (use_phi) == NULL_TREE)
2424     {
2425       EPHI_IDENTICAL_TO (use_phi) = EPHI_IDENTICAL_TO (def_phi);
2426
2427       if (EPHI_IDENT_INJURED (def_phi)
2428           || any_operand_injured (use_phi))
2429         EPHI_IDENT_INJURED (use_phi) = true;
2430     }
2431 }
2432
2433 /* DFS Search function:  Return true if the PHI will be available,
2434    it's an identity PHI, and it's arguments are identical to
2435    something.  */
2436
2437 static bool
2438 repl_search_start_from (tree phi)
2439 {
2440   if (ephi_will_be_avail (phi) && EPHI_IDENTITY (phi))
2441     {
2442       int i;
2443       for (i = 0; i < EPHI_NUM_ARGS (phi); i++)
2444         if (occ_identical_to (EPHI_ARG_DEF (phi, i)) != NULL_TREE)
2445           return true;
2446     }
2447   return false;
2448 }
2449
2450 /* DFS Search function:  Return true if the using PHI is will be available,
2451    and identity.  */
2452
2453 static bool
2454 repl_search_continue_from_to (tree def_phi ATTRIBUTE_UNUSED,
2455                               int opnd_indx ATTRIBUTE_UNUSED,
2456                               tree use_phi)
2457 {
2458   return ephi_will_be_avail (use_phi) && EPHI_IDENTITY (use_phi);
2459 }
2460
2461 /* Mark all will-be-avail ephi's in the dominance frontier of BB as
2462    required.  */
2463
2464 static void
2465 require_phi (struct expr_info *ei, basic_block bb)
2466 {
2467   size_t i;
2468   EXECUTE_IF_SET_IN_BITMAP (pre_dfs[bb->index], 0, i,
2469   {
2470     tree ephi;
2471     ephi = ephi_at_block (BASIC_BLOCK (i));
2472     if (ephi != NULL_TREE
2473         && ephi_will_be_avail (ephi)
2474         && EPHI_IDENTITY (ephi))
2475       {
2476         EPHI_IDENTITY (ephi) = false;
2477         require_phi (ei, BASIC_BLOCK (i));
2478       }
2479   });
2480 }
2481
2482 /* Return the occurrence this occurrence is identical to, if one exists.  */
2483
2484 static tree
2485 occ_identical_to (tree t)
2486 {
2487   if (TREE_CODE (t) == EUSE_NODE && !EUSE_PHIOP (t))
2488     return t;
2489   else if (TREE_CODE (t) == EUSE_NODE && EUSE_PHIOP (t))
2490     return t;
2491   else if (TREE_CODE (t) == EPHI_NODE)
2492     {
2493       if (EPHI_IDENTITY (t) && EPHI_REP_OCCUR_KNOWN (t))
2494         return EPHI_IDENTICAL_TO (t);
2495       else if (!EPHI_IDENTITY (t))
2496         return t;
2497     }
2498   return NULL_TREE;
2499 }
2500
2501 /* Return true if NODE was or is going to be saved.  */
2502 static bool
2503 really_available_def (tree node)
2504 {
2505   if (TREE_CODE (node) == EUSE_NODE
2506       && EUSE_PHIOP (node)
2507       && EUSE_INSERTED (node))
2508     return true;
2509   if (TREE_CODE (node) == EUSE_NODE
2510       && EUSE_DEF (node) == NULL_TREE)
2511     return true;
2512   return false;
2513 }
2514
2515
2516 /* Second part of the finalize step.  Performs save bit setting, and
2517    ESSA minimization.  */
2518
2519 static void
2520 finalize_2 (struct expr_info *ei)
2521 {
2522   size_t i;
2523
2524   insert_euse_in_preorder_dt_order (ei);
2525   /* Note which uses need to be saved to a temporary.  */
2526   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2527     {
2528       tree ref = VARRAY_TREE (ei->euses_dt_order, i);
2529       if (TREE_CODE (ref) == EUSE_NODE
2530           && !EUSE_PHIOP (ref)
2531           && EREF_RELOAD (ref))
2532         {
2533           set_save (ei, EUSE_DEF (ref));
2534         }
2535     }
2536
2537   /* ESSA Minimization.  Determines which phis are identical to other
2538      phis, and not strictly necessary.  */
2539
2540   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2541     {
2542       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2543       if (TREE_CODE (ephi) != EPHI_NODE)
2544         continue;
2545       EPHI_IDENTITY (ephi) = true;
2546       EPHI_IDENTICAL_TO (ephi) = NULL;
2547     }
2548
2549   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2550     {
2551       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2552       if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
2553         continue;
2554       if (ephi_will_be_avail (ephi))
2555         {
2556           int k;
2557           for (k = 0; k < EPHI_NUM_ARGS (ephi); k++)
2558             {
2559               if (EPHI_ARG_INJURED (ephi, k))
2560                 require_phi (ei, EPHI_ARG_EDGE (ephi, k)->src);
2561               else if (EPHI_ARG_DEF (ephi, k)
2562                        && TREE_CODE (EPHI_ARG_DEF (ephi, k)) == EUSE_NODE
2563                        && really_available_def (EPHI_ARG_DEF (ephi, k)))
2564                 require_phi (ei, bb_for_stmt (EPHI_ARG_DEF (ephi, k)));
2565             }
2566         }
2567     }
2568   do_ephi_df_search (ei, replacing_search);
2569 }
2570
2571 /* Perform a DFS on EPHI using the functions in SEARCH. */
2572
2573 static void
2574 do_ephi_df_search_1 (struct ephi_df_search search, tree ephi)
2575 {
2576   varray_type uses;
2577   size_t i;
2578   search.set_seen (ephi);
2579
2580   uses = EPHI_USES (ephi);
2581   if (!uses)
2582     return;
2583   for (i = 0; i < VARRAY_ACTIVE_SIZE (uses); i++)
2584     {
2585       struct ephi_use_entry *use = VARRAY_GENERIC_PTR (uses, i);
2586       if (search.reach_from_to)
2587         search.reach_from_to (ephi, use->opnd_indx, use->phi);
2588       if (!search.seen (use->phi) &&
2589           search.continue_from_to (ephi, use->opnd_indx, use->phi))
2590         {
2591           do_ephi_df_search_1 (search, use->phi);
2592         }
2593     }
2594 }
2595
2596 /* Perform a DFS on the EPHI's, using the functions in SEARCH.  */
2597
2598 static void
2599 do_ephi_df_search (struct expr_info *ei, struct ephi_df_search search)
2600 {
2601   size_t i;
2602   for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
2603     {
2604       tree ephi = VARRAY_TREE (ei->euses_dt_order, i);
2605       if (!ephi || TREE_CODE (ephi) != EPHI_NODE)
2606         continue;
2607       if (!search.seen (ephi)
2608           && search.start_from (ephi))
2609         do_ephi_df_search_1 (search, ephi);
2610     }
2611 }
2612
2613 #if 0
2614 /* Calculate the increment necessary due to EXPR for the temporary. */
2615 static tree
2616 calculate_increment (struct expr_info *ei, tree expr)
2617 {
2618   tree incr;
2619
2620   /*XXX: Currently assume it's like a = a + 5, thus, this will give us the 5.
2621    */
2622   incr = TREE_OPERAND (TREE_OPERAND (expr, 1), 1);
2623   if (TREE_CODE (incr) != INTEGER_CST)
2624     abort();
2625   if (TREE_CODE (ei->expr) == MULT_EXPR)
2626     incr = fold (build (MULT_EXPR, TREE_TYPE (ei->expr),
2627                         incr, TREE_OPERAND (ei->expr, 1)));
2628 #if DEBUGGING_STRRED
2629   if (dump_file)
2630     {
2631       fprintf (dump_file, "Increment calculated to be: ");
2632       print_generic_expr (dump_file, incr, 0);
2633       fprintf (dump_file, "\n");
2634     }
2635 #endif
2636   return incr;
2637 }
2638 #endif
2639
2640
2641 /* Perform an insertion of EXPR before/after USE, depending on the
2642    value of BEFORE.  */
2643
2644 static tree
2645 do_proper_save (tree use, tree expr, int before)
2646 {
2647   basic_block bb = bb_for_stmt (use);
2648   block_stmt_iterator bsi;
2649
2650   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2651     {
2652       if (bsi_stmt (bsi) == use)
2653         {
2654           if (before)
2655             bsi_insert_before (&bsi, expr, BSI_SAME_STMT);
2656           else
2657             bsi_insert_after (&bsi, expr, BSI_SAME_STMT);
2658           return use;
2659         }
2660     }
2661   abort ();
2662 }
2663
2664 /* Get the temporary for ESSA node USE.
2665    Takes into account minimized ESSA.  */
2666 static tree
2667 get_temp (tree use)
2668 {
2669   tree newtemp;
2670   if (TREE_CODE (use) == EPHI_NODE && EPHI_IDENTITY (use))
2671     {
2672       tree newuse = use;
2673       while  (TREE_CODE (newuse) == EPHI_NODE
2674               && EPHI_IDENTITY (newuse))
2675         {
2676 #ifdef ENABLE_CHECKING
2677           if (!EPHI_IDENTICAL_TO (newuse))
2678             abort ();
2679 #endif
2680           newuse = EPHI_IDENTICAL_TO (newuse);
2681           if (TREE_CODE (newuse) != EPHI_NODE)
2682             break;
2683         }
2684       if (TREE_CODE (EREF_TEMP (newuse)) == PHI_NODE)
2685         newtemp = PHI_RESULT (EREF_TEMP (newuse));
2686       else
2687         newtemp = EREF_TEMP (newuse);
2688     }
2689   else
2690     {
2691       if (TREE_CODE (EREF_TEMP (use)) == PHI_NODE)
2692         newtemp = PHI_RESULT (EREF_TEMP (use));
2693       else
2694         newtemp = EREF_TEMP (use);
2695     }
2696   return newtemp;
2697 }
2698
2699 /* Return the side of the statement that contains an SSA name.  */
2700
2701 static tree
2702 pick_ssa_name (tree stmt)
2703 {
2704   if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
2705     return TREE_OPERAND (stmt, 0);
2706   else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
2707     return TREE_OPERAND (stmt, 1);
2708   else
2709     abort ();
2710 }
2711
2712 /* Code motion step of SSAPRE.  Take the save bits, and reload bits,
2713    and perform the saves and reloads.  Also insert new phis where
2714    necessary.  */
2715
2716 static void
2717 code_motion (struct expr_info *ei)
2718 {
2719   tree use;
2720   tree newtemp;
2721   size_t euse_iter;
2722   tree temp = ei->temp;
2723   basic_block bb;
2724
2725   /* First, add the phi node temporaries so the reaching defs are
2726      always right. */
2727   for (euse_iter = 0;
2728        euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2729        euse_iter++)
2730     {
2731
2732       use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2733       if (TREE_CODE (use) != EPHI_NODE)
2734         continue;
2735       if (ephi_will_be_avail (use) && !EPHI_IDENTITY (use))
2736         {
2737           bb = bb_for_stmt (use);
2738           /* Add the new PHI node to the list of PHI nodes for block BB.  */
2739           bb_ann (bb)->phi_nodes = chainon (phi_nodes (bb), EREF_TEMP (use));
2740         }
2741       else if (EPHI_IDENTITY (use))
2742         {
2743           if (dump_file && (dump_flags & TDF_DETAILS))
2744             {
2745               fprintf (dump_file, "Pointless EPHI in block %d\n",
2746                        bb_for_stmt (use)->index);
2747             }
2748         }
2749     }
2750   /* Now do the actual saves and reloads, plus repairs. */
2751   for (euse_iter = 0;
2752        euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2753        euse_iter++)
2754     {
2755       use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2756 #ifdef ENABLE_CHECKING
2757       if (TREE_CODE (use) == EUSE_NODE && EUSE_PHIOP (use)
2758           && (EREF_RELOAD (use) || EREF_SAVE (use)))
2759         abort ();
2760 #endif
2761       if (EREF_SAVE (use) && !EUSE_INSERTED (use))
2762         {
2763           tree newexpr;
2764           tree use_stmt;
2765           tree copy;
2766           basic_block usebb = bb_for_stmt (use);
2767           use_stmt = EREF_STMT (use);
2768
2769           copy = TREE_OPERAND (use_stmt, 1);
2770           copy = unshare_expr (copy);
2771           newexpr = build (MODIFY_EXPR, TREE_TYPE (temp), temp, copy);
2772           newtemp = make_ssa_name (temp, newexpr);
2773           EREF_TEMP (use) = newtemp;
2774           TREE_OPERAND (newexpr, 0) = newtemp;
2775           TREE_OPERAND (use_stmt, 1) = newtemp;
2776
2777           if (dump_file)
2778             {
2779               fprintf (dump_file, "In BB %d, insert save of ",
2780                        usebb->index);
2781               print_generic_expr (dump_file, copy, dump_flags);
2782               fprintf (dump_file, " to ");
2783               print_generic_expr (dump_file, newtemp, dump_flags);
2784               fprintf (dump_file, " before statement ");
2785               print_generic_expr (dump_file, use_stmt, dump_flags);
2786               fprintf (dump_file, "\n");
2787               if (EXPR_HAS_LOCATION (use_stmt))
2788                 fprintf (dump_file, " on line %d\n",
2789                          EXPR_LINENO (use_stmt));
2790             }
2791           modify_stmt (newexpr);
2792           modify_stmt (use_stmt);
2793           set_bb_for_stmt (newexpr, usebb);
2794           EREF_STMT (use) = do_proper_save (use_stmt, newexpr, true);
2795           pre_stats.saves++;
2796         }
2797       else if (EREF_RELOAD (use))
2798         {
2799           tree use_stmt;
2800           tree newtemp;
2801
2802           use_stmt = EREF_STMT (use);
2803           bb = bb_for_stmt (use_stmt);
2804
2805           newtemp = get_temp (EUSE_DEF (use));
2806           if (!newtemp)
2807             abort ();
2808           if (dump_file)
2809             {
2810               fprintf (dump_file, "In BB %d, insert reload of ",
2811                        bb->index);
2812               print_generic_expr (dump_file,
2813                                   TREE_OPERAND (use_stmt, 1), 0);
2814               fprintf (dump_file, " from ");
2815               print_generic_expr (dump_file, newtemp, dump_flags);
2816               fprintf (dump_file, " in statement ");
2817               print_generic_stmt (dump_file, use_stmt, dump_flags);
2818               fprintf (dump_file, "\n");
2819               if (EXPR_HAS_LOCATION (use_stmt))
2820                 fprintf (dump_file, " on line %d\n",
2821                          EXPR_LINENO (use_stmt));
2822             }
2823           TREE_OPERAND (use_stmt, 1) = newtemp;
2824           EREF_TEMP (use) = newtemp;
2825           modify_stmt (use_stmt);
2826           pre_stats.reloads++;
2827         }
2828     }
2829
2830   /* Now do the phi nodes. */
2831   for (euse_iter = 0;
2832        euse_iter < VARRAY_ACTIVE_SIZE (ei->euses_dt_order);
2833        euse_iter++)
2834     {
2835       use = VARRAY_TREE (ei->euses_dt_order, euse_iter);
2836       if (TREE_CODE (use) == EPHI_NODE
2837           && ephi_will_be_avail (use)
2838           && !EPHI_IDENTITY (use))
2839         {
2840           int i;
2841           tree argdef;
2842           bb = bb_for_stmt (use);
2843           if (dump_file)
2844             {
2845               fprintf (dump_file,
2846                        "In BB %d, insert PHI to replace EPHI\n", bb->index);
2847             }
2848           newtemp = EREF_TEMP (use);
2849           for (i = 0; i < EPHI_NUM_ARGS (use); i++)
2850             {
2851               tree rdef;
2852               argdef = EPHI_ARG_DEF (use, i);
2853               if (argdef == use)
2854                 rdef = get_temp (use);
2855               else if (EREF_RELOAD (argdef) || EREF_SAVE (argdef))
2856                 rdef = get_temp (argdef);
2857               else if (TREE_CODE (argdef) == EPHI_NODE)
2858                 rdef = get_temp (argdef);
2859               else if (argdef
2860                   && EPHI_ARG_HAS_REAL_USE (use, i)
2861                   && EREF_STMT (argdef)
2862                   && !EPHI_ARG_INJURED (use, i))
2863                 rdef = pick_ssa_name (EREF_STMT (argdef));
2864               else
2865                 abort ();
2866
2867               if (!rdef)
2868                 abort();
2869               add_phi_arg (&newtemp, rdef, EPHI_ARG_EDGE (use, i));
2870             }
2871
2872           /* Associate BB to the PHI node.  */
2873           set_bb_for_stmt (EREF_TEMP (use), bb);
2874           pre_stats.newphis++;
2875
2876         }
2877     }
2878 }
2879
2880 /* Compute the iterated dominance frontier of a statement.  */
2881
2882 static bitmap
2883 compute_idfs (bitmap * dfs, tree stmt)
2884 {
2885   fibheap_t worklist;
2886   sbitmap inworklist, done;
2887   bitmap idf;
2888   size_t i;
2889   basic_block block;
2890
2891   block = bb_for_stmt (stmt);
2892   if (idfs_cache[block->index] != NULL)
2893     return idfs_cache[block->index];
2894
2895   inworklist = sbitmap_alloc (last_basic_block);
2896   done = sbitmap_alloc (last_basic_block);
2897   worklist = fibheap_new ();
2898   sbitmap_zero (inworklist);
2899   sbitmap_zero (done);
2900
2901   idf = BITMAP_XMALLOC ();
2902   bitmap_zero (idf);
2903
2904   block = bb_for_stmt (stmt);
2905   fibheap_insert (worklist, block->index, (void *)(size_t)block->index);
2906   SET_BIT (inworklist, block->index);
2907
2908   while (!fibheap_empty (worklist))
2909     {
2910       int a = (size_t) fibheap_extract_min (worklist);
2911       if (TEST_BIT (done, a))
2912         continue;
2913       SET_BIT (done, a);
2914       if (idfs_cache[a])
2915         {
2916           bitmap_a_or_b (idf, idf, idfs_cache[a]);
2917           EXECUTE_IF_SET_IN_BITMAP (idfs_cache[a], 0, i,
2918           {
2919             SET_BIT (inworklist, i);
2920             SET_BIT (done, i);
2921           });
2922         }
2923       else
2924         {
2925           bitmap_a_or_b (idf, idf, dfs[a]);
2926           EXECUTE_IF_SET_IN_BITMAP (dfs[a], 0, i,
2927           {
2928             if (!TEST_BIT (inworklist, i))
2929               {
2930                 SET_BIT (inworklist, i);
2931                 fibheap_insert (worklist, i, (void *)i);
2932               }
2933           });
2934         }
2935
2936     }
2937   fibheap_delete (worklist);
2938   sbitmap_free (inworklist);
2939   sbitmap_free (done);
2940   idfs_cache[block->index] = idf;
2941   return idf;
2942
2943 }
2944
2945 /* Return true if EXPR is a strength reduction candidate. */
2946 static bool
2947 is_strred_cand (const tree expr ATTRIBUTE_UNUSED)
2948 {
2949 #if 0
2950         if (TREE_CODE (TREE_OPERAND (expr, 1)) != MULT_EXPR
2951       && TREE_CODE (TREE_OPERAND (expr, 1)) != MINUS_EXPR
2952       && TREE_CODE (TREE_OPERAND (expr, 1)) != NEGATE_EXPR
2953       && TREE_CODE (TREE_OPERAND (expr, 1)) != PLUS_EXPR)
2954     return false;
2955   return true;
2956 #endif
2957   return false;
2958 }
2959
2960
2961
2962 /* Determine if two expressions are lexically equivalent. */
2963
2964 static inline bool
2965 expr_lexically_eq (const tree v1, const tree v2)
2966 {
2967   if (TREE_CODE_CLASS (TREE_CODE (v1)) != TREE_CODE_CLASS (TREE_CODE (v2)))
2968     return false;
2969   if (TREE_CODE (v1) != TREE_CODE (v2))
2970     return false;
2971   switch (TREE_CODE_CLASS (TREE_CODE (v1)))
2972     {
2973     case 'r':
2974     case '1':
2975       return names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0));
2976     case 'x':
2977     case 'd':
2978       return names_match_p (v1, v2);
2979     case '2':
2980       {
2981         bool match;
2982         match = names_match_p (TREE_OPERAND (v1, 0), TREE_OPERAND (v2, 0));
2983         if (!match)
2984           return false;
2985         match = names_match_p (TREE_OPERAND (v1, 1), TREE_OPERAND (v2, 1));
2986         if (!match)
2987           return false;
2988         return true;
2989       }
2990     default:
2991       return false;
2992     }
2993
2994 }
2995
2996 /* Free an expression info structure.  */
2997
2998 static void
2999 free_expr_info (struct expr_info *v1)
3000 {
3001   struct expr_info *e1 = (struct expr_info *)v1;
3002   VARRAY_FREE (e1->occurs);
3003   VARRAY_FREE (e1->kills);
3004   VARRAY_FREE (e1->lefts);
3005   VARRAY_FREE (e1->reals);
3006   VARRAY_FREE (e1->euses_dt_order);
3007 }
3008
3009 /* Process left occurrences and kills due to EXPR.
3010    A left occurrence occurs wherever a variable in an expression we
3011    are PRE'ing is stored to directly in a def, or indirectly because
3012    of a VDEF of an expression that we VUSE.  */
3013
3014 static void
3015 process_left_occs_and_kills (varray_type bexprs, tree expr)
3016 {
3017   size_t i, j, k;
3018
3019   stmt_ann_t ann = stmt_ann (expr);
3020   vdef_optype vdefs;
3021   vuse_optype vuses;
3022   def_optype defs;
3023   defs = DEF_OPS (ann);
3024   vdefs = VDEF_OPS (ann);
3025   if (NUM_DEFS (defs) == 0 && NUM_VDEFS (vdefs) == 0)
3026     return;
3027
3028   for (j = 0; j < VARRAY_ACTIVE_SIZE (bexprs); j++)
3029     {
3030       struct expr_info *ei = VARRAY_GENERIC_PTR (bexprs, j);
3031       tree vuse_name;
3032       tree random_occur;
3033       stmt_ann_t ann;
3034
3035       if (!ei->loadpre_cand)
3036         continue;
3037
3038       /* If we define the variable itself (IE a in *a, or a in a),
3039          it's a left occurrence.  */
3040       for (i = 0; i < NUM_DEFS (defs); i++)
3041         {
3042           if (names_match_p (DEF_OP (defs, i), ei->expr))
3043             {
3044               if (TREE_CODE (expr) == ASM_EXPR)
3045                 {
3046                   ei->loadpre_cand = false;
3047                   continue;
3048                 }
3049               VARRAY_PUSH_TREE (ei->lefts, expr);
3050               VARRAY_PUSH_TREE (ei->occurs, NULL);
3051               VARRAY_PUSH_TREE (ei->kills, NULL);
3052             }
3053         }
3054
3055       /* If we VDEF the VUSE of the expression, it's also a left
3056          occurrence.  */
3057       random_occur = VARRAY_TREE (ei->occurs, 0);
3058       ann = stmt_ann (random_occur);
3059       vuses = VUSE_OPS (ann);
3060       if (NUM_VDEFS (vdefs) != 0)
3061         {
3062           for (k = 0; k < NUM_VUSES (vuses); k++)
3063             {
3064               vuse_name = VUSE_OP (vuses, k);
3065               for (i = 0; i < NUM_VDEFS (vdefs); i++)
3066                 {
3067                   if (names_match_p (VDEF_OP (vdefs, i), vuse_name))
3068                     {
3069                       VARRAY_PUSH_TREE (ei->lefts, expr);
3070                       VARRAY_PUSH_TREE (ei->occurs, NULL);
3071                       VARRAY_PUSH_TREE (ei->kills, NULL);
3072                     }
3073                 }
3074             }
3075         }
3076     }
3077 }
3078
3079 /* Perform SSAPRE on an expression.  */
3080
3081 static int
3082 pre_expression (struct expr_info *slot, void *data, bitmap vars_to_rename)
3083 {
3084   struct expr_info *ei = (struct expr_info *) slot;
3085   basic_block bb;
3086
3087   class_count = 0;
3088   eref_id_counter = 0;
3089
3090   /* If we don't have two occurrences along any dominated path, and
3091      it's not load PRE, this is a waste of time.  */
3092
3093   if (VARRAY_ACTIVE_SIZE (ei->reals) < 2)
3094     return 1;
3095
3096   memset (&pre_stats, 0, sizeof (struct pre_stats_d));
3097
3098   ei->temp = create_tmp_var (TREE_TYPE (ei->expr), "pretmp");
3099   add_referenced_tmp_var (ei->temp);
3100
3101   bitmap_clear (created_phi_preds);
3102   ephi_pindex_htab = htab_create (500, ephi_pindex_hash, ephi_pindex_eq, free);
3103   phi_pred_cache = xcalloc (last_basic_block, sizeof (tree));
3104   n_phi_preds = last_basic_block;
3105
3106   if (!expr_phi_insertion ((bitmap *)data, ei))
3107     goto cleanup;
3108   rename_1 (ei);
3109   if (dump_file && (dump_flags & TDF_DETAILS))
3110     {
3111       size_t i;
3112       fprintf (dump_file, "Occurrences for expression ");
3113       print_generic_expr (dump_file, ei->expr, dump_flags);
3114       fprintf (dump_file, " after Rename 2\n");
3115       for (i = 0; i < VARRAY_ACTIVE_SIZE (ei->euses_dt_order); i++)
3116         {
3117           print_generic_expr (dump_file,
3118                               VARRAY_TREE (ei->euses_dt_order, i), 1);
3119           fprintf (dump_file, "\n");
3120         }
3121     }
3122   compute_down_safety (ei);
3123   compute_du_info (ei);
3124   compute_will_be_avail (ei);
3125
3126   if (dump_file && (dump_flags & TDF_DETAILS))
3127     {
3128       fprintf (dump_file, "EPHI's for expression ");
3129       print_generic_expr (dump_file, ei->expr, dump_flags);
3130       fprintf (dump_file,
3131                " after down safety and will_be_avail computation\n");
3132       FOR_EACH_BB (bb)
3133       {
3134         tree ephi = ephi_at_block (bb);
3135         if (ephi != NULL)
3136           {
3137             print_generic_expr (dump_file, ephi, 1);
3138             fprintf (dump_file, "\n");
3139           }
3140       }
3141     }
3142
3143   if (finalize_1 (ei))
3144     {
3145       finalize_2 (ei);
3146       code_motion (ei);
3147       if (ei->loadpre_cand)
3148         bitmap_set_bit (vars_to_rename, var_ann (ei->temp)->uid);
3149     }
3150
3151   clear_all_eref_arrays ();
3152   if (dump_file)
3153     if (dump_flags & TDF_STATS)
3154       {
3155         fprintf (dump_file, "PRE stats:\n");
3156         fprintf (dump_file, "Reloads:%d\n", pre_stats.reloads);
3157         fprintf (dump_file, "Saves:%d\n", pre_stats.saves);
3158         fprintf (dump_file, "Repairs:%d\n", pre_stats.repairs);
3159         fprintf (dump_file, "New phis:%d\n", pre_stats.newphis);
3160         fprintf (dump_file, "EPHI memory allocated:%d\n",
3161                  pre_stats.ephi_allocated);
3162         fprintf (dump_file, "EREF memory allocated:%d\n",
3163                  pre_stats.eref_allocated);
3164         fprintf (dump_file, "Expressions generated for rename2:%d\n",
3165                  pre_stats.exprs_generated);
3166       }
3167  cleanup:
3168   free (phi_pred_cache);
3169   if (ephi_pindex_htab)
3170     {
3171       htab_delete (ephi_pindex_htab);
3172       ephi_pindex_htab = NULL;
3173     }
3174
3175
3176   return 0;
3177 }
3178
3179
3180 /* Step 1 - Collect the expressions to perform PRE on.  */
3181
3182 static void
3183 collect_expressions (basic_block block, varray_type *bexprsp)
3184 {
3185   size_t k;
3186   block_stmt_iterator j;
3187   basic_block son;
3188
3189   varray_type bexprs = *bexprsp;
3190
3191   for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
3192     {
3193       tree stmt = bsi_stmt (j);
3194       tree expr = stmt;
3195       tree orig_expr = expr;
3196       stmt_ann_t ann;
3197       struct expr_info *slot = NULL;
3198
3199       get_stmt_operands (expr);
3200       ann = stmt_ann (expr);
3201
3202       if (NUM_USES (USE_OPS (ann)) == 0)
3203         {
3204           process_left_occs_and_kills (bexprs, expr);
3205           continue;
3206         }
3207
3208       if (TREE_CODE (expr) == MODIFY_EXPR)
3209         expr = TREE_OPERAND (expr, 1);
3210       if ((TREE_CODE_CLASS (TREE_CODE (expr)) == '2'
3211            || TREE_CODE_CLASS (TREE_CODE (expr)) == '<'
3212            /*|| TREE_CODE_CLASS (TREE_CODE (expr)) == '1'*/
3213            || TREE_CODE (expr) == SSA_NAME
3214            || TREE_CODE (expr) == INDIRECT_REF)
3215           && !ann->makes_aliased_stores
3216           && !ann->has_volatile_ops)
3217         {
3218           bool is_scalar = true;
3219           tree origop0 = TREE_OPERAND (orig_expr, 0);
3220
3221           if (AGGREGATE_TYPE_P (TREE_TYPE (origop0))
3222               || TREE_CODE (TREE_TYPE (origop0)) == COMPLEX_TYPE)
3223             is_scalar = false;
3224
3225           if (is_scalar
3226               && (TREE_CODE (expr) == SSA_NAME
3227                   || (TREE_CODE (expr) == INDIRECT_REF
3228                       && !DECL_P (TREE_OPERAND (expr, 0)))
3229                   ||(!DECL_P (TREE_OPERAND (expr, 0))
3230                      && (!TREE_OPERAND (expr, 1)
3231                          || !DECL_P (TREE_OPERAND (expr, 1))))))
3232             {
3233               for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++)
3234                 {
3235                   slot = VARRAY_GENERIC_PTR (bexprs, k);
3236                   if (expr_lexically_eq (slot->expr, expr))
3237                     break;
3238                 }
3239               if (k >= VARRAY_ACTIVE_SIZE (bexprs))
3240                 slot = NULL;
3241               if (slot)
3242                 {
3243                   VARRAY_PUSH_TREE (slot->occurs, orig_expr);
3244                   VARRAY_PUSH_TREE (slot->kills, NULL);
3245                   VARRAY_PUSH_TREE (slot->lefts, NULL);
3246                   VARRAY_PUSH_TREE (slot->reals, stmt);
3247                   slot->strred_cand &= is_strred_cand (orig_expr);
3248                 }
3249               else
3250                 {
3251                   slot = ggc_alloc (sizeof (struct expr_info));
3252                   slot->expr = expr;
3253                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->occurs, 1, "Occurrence");
3254                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->kills, 1, "Kills");
3255                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->lefts, 1, "Left occurrences");
3256                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->reals, 1, "Real occurrences");
3257                   VARRAY_GENERIC_PTR_NOGC_INIT (slot->euses_dt_order, 1, "EUSEs");
3258
3259                   VARRAY_PUSH_TREE (slot->occurs, orig_expr);
3260                   VARRAY_PUSH_TREE (slot->kills, NULL);
3261                   VARRAY_PUSH_TREE (slot->lefts, NULL);
3262                   VARRAY_PUSH_TREE (slot->reals, stmt);
3263                   VARRAY_PUSH_GENERIC_PTR (bexprs, slot);
3264                   slot->strred_cand = is_strred_cand (orig_expr);
3265                   slot->loadpre_cand = false;
3266                   if (TREE_CODE (expr) == SSA_NAME
3267                       || TREE_CODE (expr) == INDIRECT_REF)
3268                     slot->loadpre_cand = true;
3269                 }
3270             }
3271         }
3272       process_left_occs_and_kills (bexprs, orig_expr);
3273     }
3274   *bexprsp = bexprs;
3275
3276   for (son = first_dom_son (CDI_DOMINATORS, block);
3277        son;
3278        son = next_dom_son (CDI_DOMINATORS, son))
3279     collect_expressions (son, bexprsp);
3280 }
3281
3282 /* Main entry point to the SSA-PRE pass.
3283
3284    PHASE indicates which dump file from the DUMP_FILES array to use when
3285    dumping debugging information.  */
3286
3287 static void
3288 execute_pre (void)
3289 {
3290   int currbbs;
3291   varray_type bexprs;
3292   size_t k;
3293   int i;
3294
3295   if (ENTRY_BLOCK_PTR->succ->dest->pred->pred_next)
3296     if (!(ENTRY_BLOCK_PTR->succ->flags & EDGE_ABNORMAL))
3297       split_edge (ENTRY_BLOCK_PTR->succ);
3298
3299   euse_node_pool = create_alloc_pool ("EUSE node pool",
3300                                       sizeof (struct tree_euse_node), 30);
3301   eref_node_pool = create_alloc_pool ("EREF node pool",
3302                                       sizeof (struct tree_eref_common), 30);
3303   ephi_use_pool = create_alloc_pool ("EPHI use node pool",
3304               sizeof (struct ephi_use_entry), 30);
3305   VARRAY_GENERIC_PTR_INIT (bexprs, 1, "bexprs");
3306   /* Compute immediate dominators.  */
3307   calculate_dominance_info (CDI_DOMINATORS);
3308
3309   /* DCE screws the dom_children up, without bothering to fix it. So fix it. */
3310   currbbs = n_basic_blocks;
3311   dfn = xcalloc (last_basic_block + 1, sizeof (int));
3312   build_dfn_array (ENTRY_BLOCK_PTR, 0);
3313
3314   /* Initialize IDFS cache.  */
3315   idfs_cache = xcalloc (currbbs, sizeof (bitmap));
3316
3317   /* Compute dominance frontiers.  */
3318   pre_dfs = (bitmap *) xmalloc (sizeof (bitmap) * currbbs);
3319   for (i = 0; i < currbbs; i++)
3320      pre_dfs[i] = BITMAP_XMALLOC ();
3321   compute_dominance_frontiers (pre_dfs);
3322
3323   created_phi_preds = BITMAP_XMALLOC ();
3324
3325   collect_expressions (ENTRY_BLOCK_PTR, &bexprs);
3326
3327   ggc_push_context ();
3328
3329   for (k = 0; k < VARRAY_ACTIVE_SIZE (bexprs); k++)
3330     {
3331       pre_expression (VARRAY_GENERIC_PTR (bexprs, k), pre_dfs, vars_to_rename);
3332       free_alloc_pool (euse_node_pool);
3333       free_alloc_pool (eref_node_pool);
3334       free_alloc_pool (ephi_use_pool);
3335       euse_node_pool = create_alloc_pool ("EUSE node pool",
3336                                           sizeof (struct tree_euse_node), 30);
3337       eref_node_pool = create_alloc_pool ("EREF node pool",
3338                                           sizeof (struct tree_eref_common), 30);
3339       ephi_use_pool = create_alloc_pool ("EPHI use node pool",
3340             sizeof (struct ephi_use_entry), 30);
3341       free_expr_info (VARRAY_GENERIC_PTR (bexprs, k));
3342 #ifdef ENABLE_CHECKING
3343       if (pre_stats.ephis_current != 0)
3344         abort ();
3345 #endif
3346       ggc_collect ();
3347     }
3348
3349   ggc_pop_context ();
3350
3351   /* Clean up after PRE.  */
3352   memset (&pre_stats, 0, sizeof (struct pre_stats_d));
3353   free_alloc_pool (euse_node_pool);
3354   free_alloc_pool (eref_node_pool);
3355   free_alloc_pool (ephi_use_pool);
3356   VARRAY_CLEAR (bexprs);
3357   for (i = 0; i < currbbs; i++)
3358     BITMAP_XFREE (pre_dfs[i]);
3359   free (pre_dfs);
3360   BITMAP_XFREE (created_phi_preds);
3361   for (i = 0; i < currbbs; i++)
3362     if (idfs_cache[i] != NULL)
3363       BITMAP_XFREE (idfs_cache[i]);
3364
3365   free (dfn);
3366   free (idfs_cache);
3367 }
3368
3369 static bool
3370 gate_pre (void)
3371 {
3372   return flag_tree_pre != 0;
3373 }
3374
3375 struct tree_opt_pass pass_pre =
3376 {
3377   "pre",                                /* name */
3378   gate_pre,                             /* gate */
3379   execute_pre,                          /* execute */
3380   NULL,                                 /* sub */
3381   NULL,                                 /* next */
3382   0,                                    /* static_pass_number */
3383   TV_TREE_PRE,                          /* tv_id */
3384   PROP_no_crit_edges | PROP_cfg | PROP_ssa,/* properties_required */
3385   0,                                    /* properties_provided */
3386   0,                                    /* properties_destroyed */
3387   0,                                    /* todo_flags_start */
3388   TODO_dump_func | TODO_rename_vars
3389     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
3390 };